Manhattan phone book There is a famous question in How Would You Move Mount Fuji? book: on average, how many times (n) would you have to flip open the Manhattan phone book to find a specific name? We assume that the phone book has 1000 pages and we open 2 pages at a time. What distribution should be used? How to calculate n to get 95% probability of finding a specific name?
 A: I assume you may revisit the same two pages (ie, you're randomly opening the book each time). The probability of getting it right each time is $\frac{1}{500}$ so the probability you got it wrong after $n$ checks is $$p_n={\left(\frac{499}{500}\right)}^n$$
If the probability of being wrong after $n$ checks is $5\%$ or less, you're looking for $p_n \leq 0.05$. This occurs for $n\geq 1497$, which is a pretty bad result considering you could've exhausted the search in $500$ checks.

Perhaps a more realistic assumption is that you can't visit the same two pages right after checking them. This shouldn't substantially change the result. The probability of getting it right the first time is stil $\frac{1}{500}$, but for each guess thereafter the chance increases to $\frac{1}{499}$. Hence, the probability of getting it wrong after $n$ checks is
$$p_n=\frac{499}{500}{\left(\frac{498}{499}\right)}^{n-1}$$
And solving for $n$ again we get $n\geq 1494$. Still terrible.

Now, suppose you can't revisit pages at all. Since pairs of pages act as a unit, for simplicity I will refer to pairs of pages simply by pages, assume the book has $500$ pages, and that you check a single page per go.
When you are about to open the book for the $i$-th time, you have checked $i-1$ pages, so there are $500- (i-1)=501-i$ pages unchecked. The chance of you getting it right is $\frac{1}{501-i}$, and hence of you getting it wrong is $\frac{500-i}{501-i}$.
Thus, the probability that after the first $n$ checks you got it wrong is:
$$p_n=\prod_{i=1}^n{\frac{500-i}{501-i}}$$
which you can see is a 'telescoping product' that yields $p_n=\frac{500-n}{500}=1-\frac{n}{500}$. Now Setting $p_n\leq 0.05$ yields $n\geq 475$ which is much more reasonable in particular because it is less than $500$.
