Geometric distribution

Printable View

January 30th 2013, 06:33 AM
fatalaccidents

Geometric distribution

Hey guys,

I need help on this problem. I feel like I'm misunderstanding the question entirely.

Consider a set of n items, and let fi, i = 0, ..., n-1 denote the probability of encountering item i (for instance, if the items represent words of the English language, fi is the frequency at which the i-th word appears in text). Let us assume that the probabilities follow a Geometric distribution, i.e.
fi = c x 2^(-i-1)

a) determine the value of the constant c.
* I think that the sum of all geometric sums is equal to 1, but I can't figure out how this helps me find the constant.

b) What is the expected number of comparisons to find a key (a key I'm assuming is just an element) in a list of size n ordered by frequency (i.e., the most frequent item is first in the list, the second most frequent item is second, etc.
* There must be some way to get a frequency layout like f(most freq) = .33 f2 = .25 f3 = .15 ...... but I'm not sure how to get this.

Any suggestions that could get me on the right path to solving this problem would be greatly appreciated. Thanks for your time!
January 30th 2013, 06:59 AM
HallsofIvy

Re: Geometric distribution

Quote:

Originally Posted by fatalaccidents

Hey guys,

I need help on this problem. I feel like I'm misunderstanding the question entirely.

Consider a set of n items, and let fi, i = 0, ..., n-1 denote the probability of encountering item i (for instance, if the items represent words of the English language, fi is the frequency at which the i-th word appears in text). Let us assume that the probabilities follow a Geometric distribution, i.e.
fi = c x 2^(-i-1)

a) determine the value of the constant c.
* I think that the sum of all geometric sums is equal to 1, but I can't figure out how this helps me find the constant.

The reason this is called a "geometric distribution" is that this sum is a "geometric series": $\sum_{i= 0}^{n-1}c(1/2)^{i+1}= c\sum_{j=1}^n (1/2)^j$ (I have switched indices from i to j= i+1 to simplify). There is a simple formula for such a sum, I'll bet your textbook gives it.

Quote:

b) What is the expected number of comparisons to find a key (a key I'm assuming is just an element) in a list of size n ordered by frequency (i.e., the most frequent item is first in the list, the second most frequent item is second, etc.
* There must be some way to get a frequency layout like f(most freq) = .33 f2 = .25 f3 = .15 ...... but I'm not sure how to get this.

Any suggestions that could get me on the right path to solving this problem would be greatly appreciated. Thanks for your time!
January 30th 2013, 09:16 AM
fatalaccidents

Re: Geometric distribution

Well, I don't have a text that has the sum in it because it is a data structures class, but I did find this:

$a + ar + a r^2 + a r^3 + \cdots + a r^{n-1} = \sum_{k=0}^{n-1} ar^k= a \, \frac{1-r^{n}}{1-r}$

I'm not trying to be dense, but I'm still not sure how I'm supposed to answer the question. Is the a variable in this the constant, and if so what am I supposed to set the sum equal to so I can solve for a?

Again, I'm not sure if I'm looking at the right formula, but it also doesn't seem to help me answer the last question either. Sorry, but I must be missing something (Headbang)
January 31st 2013, 06:28 AM
fatalaccidents

Re: Geometric distribution

Does anyone know how to go about getting the answer for part B? I'm totally stuck on this problem. Thanks in advance.