A simple geometric distribution word problem

Question

I am stuck with what should be a simple probability problem.
There is an algorithm for choosing advertisements from $m$ pages. The $i$th 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 loop

The 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 = bar{n}/n$, where $ bar{n} = sum_{i=1}^{m}n(i)/m$.
If the above is correct, then the expected number of iterations should be $n/bar{n}$.
However, my book (Ross) tells me the solution is $nsqrt{n}$.
Where is my mistake?

quasi · Accepted Answer

You've made no mistake; the book's answer is wrong (answer keys can have errors).

For example, suppose every page has the same number, $k;$say, of advertisements, where $0 < k le n$.

Then if $e$ is the expected number of iterations, we get
$$
e
=
left(frac{k}{n}right)
{cdot,}
1
+
left(frac{n-k}{n}right)
{cdot,}
(1+e)
$$
which yields $e={large{frac{n}{k}}}$, not $e=nsqrt{n}$.

Note:$;$The book's answer $nsqrt{n}$ typographically resembles $n/bar{n}$, so it's possibly an error by the publisher, not the author.

A simple geometric distribution word problem

One Answer

Add your own answers!

Ask a Question