Geometric distribution

**fatalaccidents** · January 30th 2013, 06:33 AM

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!

**HallsofIvy** · January 30th 2013, 06:59 AM

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.

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!

**fatalaccidents** · January 30th 2013, 09:16 AM

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

**fatalaccidents** · January 31st 2013, 06:28 AM

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

Thread: Geometric distribution

LinkBack

Thread Tools

Display