Expected Value of flipping through a book

Question

Suppose that a book has $N$ pages, and we read through the book as follows. We start from page 0, and if we're on page $i$, we randomly flip to a page $i + 1, i + 2, ..., N$ with equal probability.

1. What is the expected value of number of flips we need to finish the book?

Intuition tells me that we can, on average, expect to halve the number of pages remaining. This yields $\log_2(N)$, but I'm having trouble formalizing it.

2. If $N = 26$, what is the probability we flip to page 13 at some point? Assume we start at page 0.

I let $P_i$ be the probability we land on page 13 eventually, starting from page $i$. Then, $P_{13} = 1$, and in general, $$P_{i} = \frac{1}{26 - i}\sum_{k = i + 1}^{13}P_k$$

Evaluating terms like $P_{12}, P_{11}, P_{10}$, I see that all of these values are $\frac{1}{14}$, including $P_0$. Is there a more intuitive reason for such a simple answer?

Answer 1

Let's consider the equivalent problem in which we start at page $n$ and flip backwards through the book, going to each of the pages $0, 1, ..., n - 1$ with equal probability. Let $E_n$ be the expected number of flips. Then we have $E_0 = 0$ and

$E_n = 1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i$

Then in particular we have

\begin{equation} \begin{split} E_{n + 1} &= 1 + \frac{1}{n + 1} \sum\limits_{i = 0}^{n} E_i \\ &= 1 + \frac{E_n}{n + 1} + \frac{n}{n + 1} \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i \\ &= 1 + \frac{E_n}{n + 1} + \frac{n}{n + 1} (1 + \frac{1}{n} \sum\limits_{i = 0}^{n - 1} E_i) - \frac{n}{n + 1} \\ &= 1 - \frac{n}{n + 1} + \frac{1}{n + 1} E_n + \frac{n}{n + 1} E_n \\ &= \frac{1}{n + 1} + E_n \end{split} \end{equation}

whenever $n \geq 1$ (and the identity is easily verified when $n = 0$ as well).

Then by induction, we have $E_n = \sum\limits_{j = 1}^n \frac{1}{j}$, the $n$th harmonic number. This will be asymptotically very close to $\log_e(n)$.

Answer 2

Let $P_n$ be the expected number of flips in a book with $n$ pages. Then $P_0=0,\ P_1=1$ and $$P_n=1+\frac1n\sum_{k=0}^{n-1}P_k,\tag1$$ because we have to make one flip, and then we're equally likely to have any number of pages from $0$ to $n-1$ left to flip through.

We get $$\begin{align} P_1&=1\\ P_2&=\frac32\\ P_3&=\frac{11}6\\ P_4&=\frac{50}{24}\\ P_5&=\frac{174}{120} \end{align}$$

The denominators are obviously $n!$, so we look for the numerators in OEIS and find A000254, the unsigned Stirling numbers of the first kind.

OESI gives the recurrence $$a_{n+1}=(n+1)a_n+n!$$ for the unsigned Stirling numbers of the first kind, and dividing through by $(n+1)!$ we get $$P_{n+1}=P_n+\frac1{n+1}$$ which clearly gives $$P_n=\sum_{k=1}^n\frac1k=H_n,$$ the $n$th harmonic number. To complete the problem, we must show that the harmonic numbers satisfy the recurrence $(1)$.

Your turn.

Answer 3

Here is how I approached the first part of the problem. Consider a book with exactly $n$ pages. Let $P_1$ denote the first page you flipped to, and let $X_n$ represent the number of pages you flipped until you get to the last page. Note $P_1$ is uniformly distributed on the set $\{1,...,n\}$ and $E(X_1)=1$. Using the total law of expectation we get for $n\geq2$ that $$E(X_n)=\sum_{k=1}^{n}E(X_n|P_1=k)P(P_1=k)=\frac{1}{n}\sum_{k=1}^{n}E(X_n|P_1=k)$$

Notice $E(X_n|P_1=k)=1+E(X_{n-k})$ and so $$E(X_n)=\frac{1}{n}\sum_{k=1}^{n}\Big[1+E(X_{n-k})\Big]=1+\frac{E(X_0)+\dots+E(X_{n-1})}{n}$$ Replace $n$ with $n+1$ to get $$E(X_{n+1})=1+\frac{E(X_0)+\dots+E(X_{n})}{n+1}$$ Combining the previous two equations unveils the relation $$(n+1)(E(X_{n+1})-1)=(n+1)E(X_n)-n$$ which is equivalent to saying $$E(X_{n+1})=E(X_n)+\frac{1}{n+1}$$ So finally $$E(X_n)=\sum_{k=1}^{n}\frac{1}{k}$$