The Infinite Lake

@Kunal Gupta – I can give you an "easy" explanation of the problem, if not of the solution I posted. Let $E_n$ be the expected number of moves to reach the left-most lilypad, given that the frog starts $n$ lilypads to the right. Of course $E_0 = 0$ . By conditioning on the outcome of the first jump, we have that $E_n \; = \; \tfrac12(1 + E_{n-1}) + \tfrac12(1 + E_{n+1}) \; = \; 1 + \tfrac12(E_{n-1} + E_{n+1}) \hspace{2cm} n \ge 1$ Let us assume that $E_1$ is finite (this is the number we are asked to calculate). It is then clear by induction that $E_n$ is finite for all $n \ge 0$ (just use the recurrence relation to calculate $E_2$ , $E_3$ , and so on up).

If we solve the recurrence relation, we must have $E_n \; = \; A + Bn - n^2$ for some constants $A,B$ . Since $E_0 = 0$ , we deduce that $A=0$ , and hence $E_n = Bn - n^2$ . Even though we do not know what $B$ is, it is clear that that formula must have $E_n$ negative for large enough $n$ , which is not possible.

Thus we deduce that $E_1$ is infinite.