$n$ cards are arranged in a line, starting with card $1$ on the far left and ending with card $n$ on the far right. You are playing the following game: starting at card 1, you pick a card to the right at random and advance to this card. You repeat this behavior until you reach card $n$. What is the expected value of the number of rounds you will need to finish the game?
My thoughts so far:
Every outcome of the game corresponds to a unique increasing sequence $x_1, x_2, \ldots, x_{m – 1}, n$, where $m$ is the number of rounds needed to finish the game. We have $2^{n – 1}$ possible sequences, which are not equally likely. We can quickly see this by noting that the sequence ${n}$ has a probability of $\frac{1}{n}$, while the sequence ${1, 2, \ldots, n}$ has a probability of $\frac{1}{n!}$.
The probability of an arbitrary sequence $x_1, x_2,\ldots, x_{m – 1}, m$ is thus $\frac{1}{n (x_1 – 1) (x_2 – 1) \cdots (x_{m – 1} – 1)}$
Theoretically, this gives us $P(m) = \sum \frac{1}{n (x_1 – 1) (x_2 – 1) \cdots (x_{m – 1} – 1)}$, which could then be used to derive the expected value. But I haven't figured out a nice way to express this sum, and I suspect there must be a more elegant approach.
I also considered an alternate approach. Let $X_1$ be the number of rounds we need to pass the first card, $X_2$ be the number of additional rounds we need to surpass the second card after we've already surpassed the first card, and so on, where $X_i$ is the number of additional rounds we need to pass the ith card after we've already passed the $i-1$th card, for indexes $1 \leq i \leq n – 1$.
Each random variable $X_i$ is Bernoulli, with value 0 if the we never land on card $i$, and with value 1 if we do land on card $i$ (requiring an extra hop to then jump over it). From here, we have
\begin{align*}
E(m) &= E(X_1) + E(X_2) + \cdots + E(X_{n – 1})\\
&= P\text{(Stop on Card 1)} + P\text{(Stop on Card 2)} + \cdots + P\text{(Stop on Card $n – 1$)}
\end{align*}
Unfortunately, I'm afraid I'm stuck here.
Best Answer
Let $X_n$ denote the random variable associated with the number of rounds when there are $n$ cards. By computing the first few values of $\mathbb{E}[X_n]$ we may conjecture a closed form involving the harmonic numbers:
$$\mathbb{E}[X_n]=H_{n-1}=\sum_{k=1}^{n-1}\frac1n$$
To prove this, note that $\mathbb{E}[X_n|\text{The first card is } n-k]=1+\mathbb{E}[X_k]$, so by the law of total expectation,
$$\mathbb{E}[X_n]=\sum_{k=1}^{n-1}\frac1{n-1}\mathbb{E}[X_n|\text{The first card is } n-k]=1+\frac1{n-1}\sum_{k=1}^{n-1}\mathbb{E}[X_k]$$
Now, all that remains is to show that
$$\begin{split} \sum_{k=1}^{n-1}H_{k-1}&=\sum_{k=1}^{n-1}\sum_{m=1}^{k-1}\frac1m\\ &=\sum_{m=1}^{n-2}\frac{n-m-1}{m}\\ &=(n-1)H_{n-2}-(n-2)\\ &=(n-1)H_{n-1}-(n-1)\\ H_{n-1}&=1+\frac1{n-1}\sum_{k=1}^{n-1}H_{k-1} \end{split}$$
Since $H_{n-1}$ satisfies the same recurrence as $\mathbb{E}[X_n]$ and $H_0=0=\mathbb{E}[X_1]$, then $\mathbb{E}[X_n]=H_{n-1}$ for all $n\geq 1$, as desired.