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)'));
