Expected number of iterations of an advertisement selecting algorithm

118 Views Asked by At

There is an advertisement directory with $m$ pages and $n(i)$ denotes the number of ads in page $i, i = 1, \dots, m$. Assume that $\forall i, \ n(i) \le N$
An algorithm is defined as follows:
Pick a page at random, call it page $i$. Accept it with probability $\frac {n(i)}{N}$, if rejected, pick another page at random and repeat, if accepted, pick an ad on page $i$ at random.
Iff this algorithm picked $k$ pages at random, it was iterated $k$ times.
Find the expected number of iterations.
If $A_j$ denotes the event that a page was successfully picked on iteration $j$ and $C_i$ the event that page $i$ was first picked at random, I calculate $$\mathbb{P}(A_1)=\sum_{i=1}^m \mathbb{P}(A_1|C_i)\mathbb{P}(C_i)=\sum_{i=1}^m \frac{n(i)}{mN}$$ Then, the probability that the algorithm iterates $k$ times is the probability that it fails to choose a page on the first $k-1$ attempts, and then picks one successfully on try $k$, therefore giving by (I assume the independence of the iterations) $$\mathbb{P}(A_k)=(1-\mathbb{P}(A_1))^{k-1}\mathbb{P}(A_1)$$ To find the expected value, calculate $$\sum_{k=1}^{\infty} k\mathbb{P}(A_k)=\frac {1}{\mathbb{P}(A_1)}=\frac {mN}{\sum_{i=1}^m n(i)}$$ However, the book says The number of iterations is geometric with mean $N \sqrt{N}$
I am unsure as to whether I am not seeing how $\frac {1}{N\mathbb{P}(A_1)}=\sqrt{N}$ or if my calculations were incorrect or if my whole approach was entirely misguided. How can I know which one of these three alternatives is the cause of my mistake?