Expected Value, Stepping Stones Puzzle

Question

My son asked me this, and so far I have failed to answer it...

To complete a task a player must cover nine stepping stones to reach the opposite bank of a river. To be clear, the tenth step is onto the opposite bank, and that is the end. On each go, the player takes a number of steps, with equal likelihood, from 1 up to the number remaining. So, e.g., on the first go, the player takes between 1 and 10 steps with equal chance. The puzzle is: what is the expected value of the number of goes required to cross the river?

Answer 1

I'll treat this as self-study and provide hints to help you get unstuck. Please reply in the comments if this is helpful and where you get stuck again.

Let $E_i$ denote the expected number of steps when you are $i$ stones away from the opposite bank. That is, $E_1$ means that we are on the very last stone. In this case, we will take a single step with probability one, and the expectation is

$$ E_1 = 1. $$

If we are two stones away from the opposite bank and want to calculate $E_2$, there are two possibilities:

• With probability $\frac{1}{2}$, we make a single (two-stone) step and are done. This contributes $\frac{1}{2}\times 1$ to $E_2$.
• With probability $\frac{1}{2}$, we make a one-stone step and are in the situation above. This contributes $\frac{1}{2}\times (1+E_1)$ to $E_2$.

Overall,

$$ E_2 = \frac{1}{2}\times 1 + \frac{1}{2}\times (1+E_1) = 1.5. $$

The key observation is that we can express $E_2$ as a function of $E_1$. Now, can you express $E_3$ as a function of $E_1$ and $E_2$?

---

EDIT: per above, we get a recurrence relationship.

$$ E_n = \frac{1}{n}\times 1+\frac{1}{n}\times(1+E_{n-1})+\dots+\frac{1}{n}\times(1+E_1) = 1+\frac{1}{n}\sum_{k=1}^{n-1}E_k. $$

Here is a simple dynamic programming approach to calculating these numbers in R:

n.stones <- 10

expectation <- rep(NA,n.stones)
expectation[1] <- 1
for ( ii in 2:n.stones ) expectation[ii] <- mean(1+c(0,expectation[1:(ii-1)]))
expectation[n.stones]

This yields 2.93.

Since I don't trust myself, I like to verify things like this via simulation:

n.sims <- 1e4
steps <- rep(0,n.sims)
for ( jj in 1:n.sims ) {
    stones <- n.stones
    while ( stones > 0 ) {
        steps[jj] <- steps[jj]+1
        stones <- stones-sample(x=stones,size=1)
    }
}
mean(steps)

hist(steps,breaks=seq(0.5,n.stones+0.5),col="grey",xlab="")
abline(v=mean(steps),lwd=2)
abline(v=expectation[n.stones],lwd=2,col="red")
legend("topright",lwd=2,col=c("black","red"),
    legend=c(paste("Simulated expectation:",round(mean(steps),2)),
                        paste("Theoretical expectation:",round(expectation[n.stones],2))))

This looks good - the simulated and theoretical values are practically on top of each other.

If we normalize the $E_n$ values by multiplying by $n!$, we get something that is identical to the sequence of unsigned Stirling numbers of the second kind, sequence A000254:

expectation*factorial(1:n.stones)
 [1]        1        3       11       50      274     1764    13068   109584  1026576 10628640

Your son's homework: prove that we indeed get $E_n=\frac{s(n+1,2)}{n!}$.

Answer 2

Following discussion with my son, this is his answer:

The expected value for the number of goes to complete ten steps, E(10) is Sum (1/r) with r running from 1 to 10. For n steps (n-1 stones in the river, one extra step to get onto the bank) the answer is Sum (1/r) with r running from 1 to n. This leads to a simple recurrence relation: E(n) = E(n-1) + 1/n.

Method:

If the first go is ten steps, then the expected value is 1. If the first go is nine steps, the expected value is 2. If the first go is eight steps, then the expected value is 2 1/2, because on the second go we either finish or take one step and join the pattern that follows from a first go of nine steps. If the first go is seven steps the expected value is 2 5/6, because on the second go we either finish or join the pattern that follows from eight or nine on the first go, so we average over those three values: 2, 3 1/2, 3 = 2 5/6.

And on we go through all the possible first steps. At the end we average over the ten possible first steps, which were all equally likely.

This is how he first did it, then he pattern spotted a formula for the case of n which simplified to Sum (1/r), r running from 1 to n.

However, there is a more direct approach, which he later found.

In the above description, when we move down from, say, landing on eight first go to landing on seven first go, we then add in, at the next stage, a 1/3 chance of landing on 8 next go, and thus drawing in the pattern starting at 8 again, but now with a further 1/3 contribution to the overall sum. Similarly, when we land on six first go, the pattern starting on eight provides a further 1/4 contribution to the overall sum.

With this way of thinking still in mind, consider more directly landing on 10, finishing. The expected value for the number of goes to achieve this is a sum that accumulates exactly as Sum (1/r) r running from 1 to 10. Why? Because it gets 1 from ten steps in one go, 1/2 from landing on 9 first, 1/3 from 8 first, 1/4 from 7 first etc. If we calculate this we get the exact same answer (2.92....) as provided by Stephan.