7
$\begingroup$

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.

  1. 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?

$\endgroup$
  • $\begingroup$ Question 1. is unclear ... number of flips we need for what? To read every page in the book? To reach the last page in the book? What does it mean? $\endgroup$ – Ross Presser Aug 21 at 13:47
  • 1
    $\begingroup$ edited for clarity, though it should be implicitly clear that it's often not possible to read every page in the book, and the expected value of flips to read every page is trivial. $\endgroup$ – user815048 Aug 21 at 20:13
6
$\begingroup$

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)$.

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
2
$\begingroup$

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}$$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.