The Frog Problem (puzzle in YouTube video)

Question

There is an interesting puzzle in YouTube video Can you solve The Frog Problem?. I'll try to give an equivalent formulation here.

A frog is on one side of the pond and wants to get on the other side. There are $n$ lily leaves ahead in a line, the $n$-th leave laying on the other end of the pond and being the destination. Whatever the position the frog is at any time, it will only go ahead and the probability to land on one of the leaves left in front of it (including the destination) is uniform. So, for example, if there are 10 leaves ahead, there is a probability of $\frac{1}{10}$ that it will land on any of them.

What is the expected value for the number of jumps it will take the frog to arrive to the destination leaf? The answer cannot be a recursive expression.

I think I have a solution, I'll report it as an answer below.

Answer 1

This is an interesting problem, and polettix gives the solution for the immediate problem of finding the expected number of jumps. I'm going to try looking at the broader issue of the distribution of the time it takes to get to the last lily-pad. This broader analysis allows us to find the probabilities of any state, and any of the moments of the distribution.

This analysis can be framed as a problem of finding the distribution of the "hitting time" for the absorbing state of a discrete Markov chain. It is relatively simple to program this Markov chain in statistical software and extract the resulting distribution of the hitting times, thus giving a complete solution to the Frog Problem.

---

Setting up the problem as a Markov chain: To set up the problem, we use states $x = 0,1,2,...,n$, where state $x=0$ is the frog on the river-bank, and the remaining states are for the frog being on lily-pads $1,...,n$ respectively. We let $\{ X_t | t =0,1,2,3,... \}$ be the random process in the problem, with the frog being at lily-pad $X_t$ immediately after jump $t$. The process is a strictly monotone discrete Markov chain with the $(n+1) \times (n+1)$ transition probability matrix:

$$\mathbf{P} = \begin{bmatrix} 0 & 1/n & 1/n & \cdots & 1/n & 1/n & 1/n \\ 0 & 0 & 1/(n-1) & \cdots & 1/(n-1) & 1/(n-1) & 1/(n-1) \\ 0 & 0 & 0 & \cdots & 1/(n-2) & 1/(n-2) & 1/(n-2) \\ \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots \\ 0 & 0 & 0 & \cdots & 0 & 1/2 & 1/2 \\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ 0 & 0 & 0 & \cdots & 0 & 0 & 1 \\ \end{bmatrix}.$$

The number of jumps to the last lily-pad is the hitting time for state $n$, which is:

$$T \equiv \min \{ t \in \mathbb{N} | X_t = n \}.$$

Our goal will be to find the probability mass function for the random variable $T$, which provides a full solution to the frog problem (i.e., it fully describes the behaviour of the number of jumps to the last lily-pad).

---

Finding the probability mass function: Since the frog progresses by at least one lily-pad at each jump, it takes at most $n$ jumps to reach the last lily-pad, so we must have $1 \leqslant T \leqslant n$. The cumulative distribution function for this time is:

$$F_T(t) = \mathbb{P}(T \leqslant t) = \mathbb{P}(X_t = n) = [\mathbf{P}^t]_{0,n}.$$

Thus, the probability mass function for the time is:

$$p_T(t) = \begin{cases} 1/n & & \text{for } t = 1, \\[6pt] [\mathbf{P}^t]_{0,n} - [\mathbf{P}^{t-1}]_{0,n} & & \text{for } t > 1. \\[6pt] \end{cases}$$

This mass function fully describes the distribution of the time taken for the frog to reach the last lily-pad, and so it can be considered to be a complete solution to the Frog problem. To facilitate computation, we can program this distribution in R as the dfrog function. This is a vectorised function that generates values from the probability mass function for an argument vector T and parameter n.

dfrog <- function(n, T = 1:n) {

#Create transition probability matrix
P <- matrix(0, nrow = n+1, ncol = n+1);
for (i in 1:n) { 
for (j in i:n) { 
    P[i, j+1] <- 1/(n+1-i);  } }
P[n+1, n+1] <- 1;

#Generate CDF and PMF vectors
PP  <- P;
CDF <- rep(0, n);
for (t in 1:n) {   
    CDF[t] <- PP[1, n+1];
    PP <- PP %*% P; }
PMF <- diff(c(0, CDF));

#Generate output vector
OUT <- rep(0, length(T));
for (i in 1:length(T)) { OUT[i] <- PMF[T[i]]; }

OUT; }

We can use this function to generate and plot the probability mass function. The plot below shows the distribution of the number of jumps when there are $n=20$ lily-pads. As can be seen, the frog will usually take 3-4 jumps to reach the last lily-pad in this case.

#Load ggplot and set theme
library(ggplot2);
THEME <- theme(plot.title    = element_text(hjust = 0.5, size = 14, face = 'bold'),
               plot.subtitle = element_text(hjust = 0.5, face = 'bold'));

#Plot the PMF
n    <- 20;
DATA <- data.frame(Jumps = 1:n, Probability = dfrog(n));
ggplot(aes(x = Jumps, y = Probability), data = DATA) + 
    geom_bar(stat = 'identity', fill = 'darkgreen') +
    THEME +
    ggtitle('PMF of number of jumps to last lily-pad') +
    labs(subtitle = paste0('(Frog problem with n = ', n, ' lily-pads)'));

Answer 2

Instead of using the recursive relation for the expected number $J_n = J_{n-1} + \frac{1}{n}$ we could also try a more mechanistic approach by computing every path that the frog can take and the distribution of the probability of the position of the frog after $k$ jumps.

This can be quickly computed using a Markov chain.

# stochastic Matrix
M <- pracma::Toeplitz(c(0,rep(1,10)),rep(0,11)) / c(1,1:10) 
M[1,1] <- 1                                               

# positions of frogs after k steps
V <- c(rep(0,10),1)
Vm <- sapply(0:10, FUN = function(k) V %*% (M %^% k))

# mean number of steps by computing 1-F(0)
sum(1-Vm[1,])

giving $2.928968$

The mass distribution, $p(x,k)$, for the probability to be at distance $x$ from the 'finish-leaf' in the $k$-th step would look like the following:

---

This method has one downside. It is not very easy to derive the final charming result that the expectation value for the number of steps is equal to the n-th harmonic number $\sum_{k=1}^n 1/k$.

In the comments I suggested that these distributions $p(x,k)$ would be like polynomial functions. However that is wrong. It is more complicated.

The distribution follows the relation:

$$p(x,k) = \sum_{y=x+1}^N \frac{p(y,k-1)}{j}$$

where $p(x,k)$ is a sum of the probabilities for the position of the frog in the $(k-1)$-th step, and $N$ is the number of leaves (generalizing from $N=10$). To start this relation we use $p(N,0)=1$.

This could be expanded as

$$p(x,k) = \frac{1}{N} \sum_{l_1=x+1}^{N-k} \sum_{l_2=l_1+1}^{N-k+1} ... \sum_{l_k=l_{k-1}+1}^{N-1} \frac{1}{l_1 \cdot l_2 \cdot ... l_k}$$

which is some sort of generalization of the Harmonic number.

You could describe it more compact as

$$p(x,k) = \frac{1}{N} \sum_{S \in S_{k,[x,...,N-1]}} \prod_{a \in S} \frac{1}{a}$$

where the sum is over all k-subsets $S$ in $S_{k,[x,...,N-1]}$, the set of all k-subset of $[x,...,N-1]$, and the product is over all the numbers $a$ in the subset $S$. For instance a subset $\lbrace 3,5,7 \rbrace$ would represent that the frog jumped from position 10 to 7 to 5 and to 3. The probability for the frog to follow this path is $\frac{1}{10 \cdot 7 \cdot 5 \cdot 3}$.

I am not sure yet how to continue from here to obtain the final result... I imagine you could use some recursive relation.

Answer 3

We will call $J_n$ the expected value for the jumps when there are $n$ leaves ahead. We set also $J_0 = 0$, which is consistent with the fact that if the frog has no leaf ahead it needs to do exactly $0$ jumps to arrive at destination.

We will name/number the leaves according to their distance from the destination. So the destination will be leaf $0$, the one immediately before $1$ and so on up to leaf $n-1$ that is the one in front of the frog. There are in total $n$ leaves and the probability to jump on any of them with one leap is $\frac{1}{n}$ according to the puzzle indications.

When the frog takes this first leap, it will land on leaf $k$, with $k \in \{0, ... n-1\}$ and, from that point, the expected value of remaining leaps will be $J_k$. Considering that these events are mutually exclusive, we get the following:

$$J_n = \sum_{k=0}^{n-1}\frac{1}{n}(1 + J_k)$$

where the $1$ represents the first leap to reach position $k$. As there are $n$ elements in the sum, it can be rearranged as:

$$J_n = 1 + \frac{1}{n} \sum_{k=0}^{n-1}J_k$$

which is indeed a bit too recursive. With simple arithmetics we can further rearrange it as follows:

$$n(J_n - 1) = \sum_{k=0}^{n-1}J_k$$

This relation is generic and can be also rewritten with $n-1$ instead of $n$:

$$(n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-2}J_k$$

Subtracting the two relations we get:

$$n(J_n - 1) - (n-1)(J_{n-1} - 1) = \sum_{k=0}^{n-1}J_k - \sum_{k=0}^{n-2}J_k = J_{n-1}$$

that is:

$$n(J_n - 1) = (n-1)(J_{n-1} - 1) + J_{n-1} = nJ_{n-1} - (n-1)$$ $$J_n - 1 = J_{n-1} - \frac{n-1}{n}$$ $$J_n = J_{n-1} + \frac{1}{n}$$

Still recursive, but at least the $n$-th element is expressed in terms of $n-1$-th element only.

Now considering that $J_0 = 0$ the relation above can be collapsed to:

$$J_n = \sum_{k = 1}^{n}\frac{1}{k}$$

which is the answer to the puzzle.

Answer 4

Like Martijn Weterings, I tried the "compute all possibilities" approach.

At the start, the frog has $n$ choices each with $\frac{1}{n}$ probability. After that, the choices remaining depend on the initial choice. But the set of the probabilities of the remaining steps is easy enough to see: it's the reciprocals of the Power Set on $\{1,...,n-1\}$.

That is, for $n=3$, the probabilities of each step are (in reciprocal):

{ 3 } -- one jump of 3
{ 3, 1 } -- jump of 2 (with a 1/3 probability) then a jump of 1 (with 1/1 probability)
{ 3, 2 } -- 1 then 2
{ 3, 2, 1 } -- 1 then 1 then 1

The expected value of these is just the size of the set divided by the product of the elements of the set.

Since each set always starts with $n$, we move it out of the summation.

The expected number of jumps to get across to the nth leaf is:

$$ \frac{1}{n} \sum_{\textbf{x}\in{\mathbb{P}(\{1,...,n-1\})}} \frac{|\textbf{x}|+1}{\prod \textbf{x}} $$

I'm not sure what approach can be used to simply this form into the $$\sum_{k=1}^n \frac{1}{k}$$ form, but the equivalence of the two checks for the $n$ I've tried (2,3,10,20)