Results 1 to 4 of 4

Math Help - Geometric distribution

  1. #1
    Newbie
    Joined
    Jan 2013
    From
    MS
    Posts
    3

    Question 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!
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,313
    Thanks
    1291

    Re: Geometric distribution

    Quote Originally Posted by fatalaccidents View Post
    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!
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Jan 2013
    From
    MS
    Posts
    3

    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
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2013
    From
    MS
    Posts
    3

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Geometric distribution
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: December 1st 2011, 04:35 PM
  2. Geometric distribution
    Posted in the Advanced Statistics Forum
    Replies: 4
    Last Post: July 28th 2011, 06:24 AM
  3. Geometric Distribution HELP!
    Posted in the Advanced Statistics Forum
    Replies: 0
    Last Post: November 15th 2009, 10:16 AM
  4. geometric distribution
    Posted in the Statistics Forum
    Replies: 3
    Last Post: November 14th 2009, 03:53 AM
  5. Geometric distribution
    Posted in the Math Topics Forum
    Replies: 1
    Last Post: November 15th 2008, 01:19 PM

Search Tags


/mathhelpforum @mathhelpforum