A simple geometric distribution word problemThere is an algorithm for choosing advertisements from m pages. The ith page has n(i) advertisements, with n(i) less than some number n.Here is how the algorithm works:- Choose a random page from m pages- Accept that page with probability n(i)/n- If accepted, choose an ad from those on the page- Else repeat the loopThe question: What is the expected number of iterations taken by the algorithm?This (I think) reduces to a geometric distribution with mean 1/p where p is the probability of accepting an ad on any particular iteration.I have verified that the probability of accepting any of the m pages (and therefore accepting an advertisement) is p = n ¯ / n, where n ¯ = ∑ i = 1 m n ( i ) / m.If the above is correct, then the expected number of iterations should be n / n ¯ .However, my book (Ross) tells me the solution is n n

Question

A simple geometric distribution word problemThere is an algorithm for choosing advertisements from m pages. The ith page has n(i) advertisements, with n(i) less than some number n.Here is how the algorithm works:- Choose a random page from m pages- Accept that page with probability n(i)/n- If accepted, choose an ad from those on the page- Else repeat the loopThe question: What is the expected number of iterations taken by the algorithm?This (I think) reduces to a geometric distribution with mean 1/p where p is the probability of accepting an ad on any particular iteration.I have verified that the probability of accepting any of the m pages (and therefore accepting an advertisement) is   p  =            n      ¯            /    n, where             n      ¯        =      ∑          i      =      1              m        n  (  i  )      /    m.If the above is correct, then the expected number of iterations should be   n      /              n      ¯      .However, my book (Ross) tells me the solution is   n      n

antanklatyz · Accepted Answer

Step 1For example, suppose every page has the same number, ksay, of advertisements, where   0  &amp;lt;  k  ≤  n.Then if e is the expected number of iterations, we get   e  =      (          k      n        )        ⋅        1  +      (                  n        −        k            n        )        ⋅        (  1  +  e  ) which yields   e  =                              n          k                    , not   e  =  n      n  Step 2The book&#039;s answer   n      n   typographically resembles   n      /              n      ¯      , so it&#039;s possibly an error by the publisher, not the author.

A simple geometric distribution word problem. What is the expected number of iterations taken by the algorithm?

Open question

Answer & Explanation

New Questions in High school geometry