I didn't make this problem up, I found it on the Numberphile Youtube channel, but it was new to me and I thought it was interesting.
A frog is on the left-hand bank of a river. In the river are 10 stepping stones as shown.
The frog crosses the river, always moving to the right, by random hops. At each hop it chooses which of the remaining stones it will hop to at random, with equal probability for each remaining stone.
What is the expected number, i.e. the average number, of hops it will make before reaching the other bank?
Comments
New comment
? my head hurts
New comment
My analysis is this.
The frog could hop to stone 1 with probability 1/10, yes? And that adds 1 hop x 1/10 = 1/10 to the expected number of hops.
Otherwise stone 1 may as well not exist, so then we fall back on the expected number for 9 stones. That means
expected number for 10 stones = 1/10 + expected number for 9 stones
= 1/10 + 1/9 + expected number for 8 stones
and so carrying in this fashion on we get
expected number for 10 stones = 1/10 + 1/9 + 1/8 + ... + 1/2 + 1/1.
Neat! And easy to see the parallel result for any number, not just 10.
New comment
... I'll stick to the criminology