14
$\begingroup$

Standard Problem description

In this question The Frog Problem (puzzle in YouTube video) a frog has to jump from leaf to leaf on a row of leaves. And the question is how long it takes on average to reach the end.

In that specific case the frog only jumps to the leaves in front of him with each leaf having equal probability. It is computed that the expectation value for the number of steps to reach the end is $J_n = \sum_{k=1}^n 1/k $, when the frog has $n$ leaves in front of him.

New extended problem

But what is the solution when the frog can also remain still and go one step backwards. (there are infinitely many leaves behind the frog, the game only ends when the frog has no leaves in front of him)

frog game

This would lead to a recurrence relation like: $$J_{n} = (n+1) J_{n-1} - n J_{n-2}-1$$

To make the solution final we need to know $J_0$ and $J_1$.

It is trivial that the expected number of steps for a frog with zero leaves in front of him is 0 ($J_0 = 0$).

But what is $J_1$? What is the expected number of steps for a frog that has only one leaf to go?


Derivation/intuition of the recurrence relation:

$$J_{n+1} = (n+2) J_{n} - (n+1) J_{n-1}-1$$

There are $n+2$ leaves to go to. The $n$ leaves in front of the frog and the one leaf on which the frog is sitting is the same situation as the frog who has $n-1$ leaves in front of him/her. The one leaf backwards results in the frog being in the situation of a frog that has $n+1$ leaves in front of him/her but he took an extra step.

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

Solution attempt 1

It seems like the solution is close to $J_n = c + \sum_{k=1}^n 1/k$ with some constant $c$... but not exactly. When I fill that expression into the recurrence relation then I get to:

$$\begin{array}{rcl} J_{n} &=& (n+1) J_{n-1} - n J_{n-2}-1 \\ c + \sum_{k=1}^n \frac{1}{k} &=& (n+1) \left(c + \sum_{k=1}^{n-1} \frac{1}{k} \right) - n \left(c + \sum_{k=1}^{n-2} \frac{1}{k} \right) -1 \\ \sum_{k=1}^n \frac{1}{k} &=& (n+1) \left(\sum_{k=1}^{n-1} \frac{1}{k} \right) - n \left(\sum_{k=1}^{n-2} \frac{1}{k} \right) -1 \\ \frac{1}{n} + \frac{1}{n-1} &=& (n+1)\frac{1}{n -1} -1\\ \frac{1}{n} + \frac{1}{n-1} &=& \frac{2}{n -1} \\ \end{array}$$

which is a contradiction.

Solution attempt 2

Simulation by Markov chain (this results into something that looks like $J_n = c + \sum_{k=1}^n 1/k$ but as shown before that can not be true.)

simulation results

nm <- 50
library(expm)

for (n in 1:40) {
  # stochastic Matrix
  M <- pracma::Toeplitz(c(rep(1,nm+1)),c(1,1,rep(0,nm-1))) / c(2:(nm+2)) 
  M[1,1:2] <- c(1,0)                                               

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

  # mean number of steps by computing 1-F(0)
  E <- sum(1-Vm[1,])
  ev[n] <- E
}

n <- 1:40
plot(n,ev,xlim=c(0,20))

title("simulated \n expected number of steps",cex.main=1)

H <- cumsum(1/n)
mod <- lm(ev-H~1)
lines(n,H+coef(mod)[1])

coef(mod)

legend(0,6.6, c("simulation","2.325547 + H_n") ,cex=0.7, lty=c(NA,1), pch = c(1,NA))

Jn <- ev[-c(1,2)]
Jn1 <- ev[-c(1,40)]
Jn2 <- ev[-c(39,40)]
np <- n[-c(1,2)]

plot(Jn, (np+1)*Jn1 - (np) * Jn2 -1,
     xlab = expression(J[n]),
     ylab = expression((n+1)%*%J[n-1]-n%*%J[n-2]-1 ))
lines(c(0,10),c(0,10))

title("testing recurrence relation", cex.main=1)

In this answer to the simpler solution. The motion of the frog is not computed by using the recurrence relation, but instead by writing down the probability distribution where the frog might be after $k$ jumps.

In that case the distribution is like a diffusing wave, which will eventually be absorbed completely in the final leaf. In this case we can not compute it because there is a tiny number of frogs that will never reach the goal. But maybe we solve the puzzle with this starting point by finding some explicit solution or by changing the expression to include the backwards leaves?


Written by StackExchangeStrike

$\endgroup$
  • 1
    $\begingroup$ What do you mean by "with equal probability"? And are there $n$ leaves? Do you mean that there are $n$ leaves, the frog starts on the 1st one, and he next jumps onto one of the ones ahead of him, with equal probability to jump to each one? And the entire process ends when he arrives at the last leaf? $\endgroup$ – S. Kolassa - Reinstate Monica Sep 14 at 11:55
  • $\begingroup$ It is indeed much as you describe. Iterative steps where the frog will jump to a leaf in front of him with equal probability untill he reaches the end. That is the problem in the link. In this case the frog can also jump to the same place or one leaf backwards. In the other question I already commented on an alternative solution strategy that should work here as well. $\endgroup$ – Sextus Empiricus Sep 14 at 12:58
  • $\begingroup$ I don't understand the question because it's incomplete: although it expands the set of possible transitions, it doesn't specify their probabilities. What are they? And what are the probabilities when the frog is as far from the end as possible, where there is no possibility of jumping backwards? $\endgroup$ – whuber Oct 4 at 13:20
  • 1
    $\begingroup$ If $\mu$ can become as small as you like then the fraction of frogs with a position $x>0$ must get as close to zero as you like. $\endgroup$ – Sextus Empiricus Oct 8 at 20:33
  • 1
    $\begingroup$ try to solve it with $n$ possible tiles and then compute $\lim_{n -> \infty} J_1$ and so on $\endgroup$ – quester Oct 10 at 10:20
3
$\begingroup$

No going back case only

I'm addressing the zero-length jumps case only, i.e. no going back and the frog is allowed to remain still at a given step. Without considering a clock-like device and assuming that remaining still in one clock tick counts as one jump means just considering the other's puzzle conditions. It does not have to be a precise clock or stick to equal time intervals, just give a tick every now and then which trigger the need for a jump by the frog.

When on leaf 1, there is a probability $\frac12$ to jump to the target leaf 0 and $\frac12$ to remain on leaf 1. The probability of taking exactly $k$ jumps to land on the target has probability $\left(\frac12\right)^k$, that is $\left(\frac12\right)^{k-1}$ of remaining still in the first $k-1$ ticks and $\frac12$ to land on leaf 1 on the $k$-th tick. So the expected value is:

$$J_1 = \sum_{k=1}^{\infty}k\left(\frac12\right)^k = \frac{\frac12}{\left(1-\frac12\right)^2} = 2$$

(thanks wikipedia).

Generalizing for $n > 1$, we can land on leaf $0..n$ at the next tick, each with probability $\frac1{n+1}$. Each case implies taking the jump of the tick, then taking the average number of jumps from the leaf we land on:

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

Interestingly, this allows us to find $J_1 = 1 + \frac12J_1 = 2$ but without much sweating with the harmonic series. Evolving the equation:

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

This relation does not hold for $n = 0$ because it would lead to $0 = 1$. Assuming $n > 1 \Rightarrow n - 1 > 0$:

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

Subtracting the last two equations:

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

that is exactly the same relation we have if the frog is only allowed to advance, although with different edge conditions ($n > 1$ and $J_1 = 2$). So, the bottom line is:

$$ J_0 = 0 $$ $$ n>0 : J_{n} = 1 + \sum_{k=1}^{n}\frac1k $$

i.e. on average there will be exactly 1 jump more than the previous case where the frog can only advance, except for $J_0$ in which case the frog will always just remain still.

It is interesting that the recurrent relation holds for $n>1$ but the non-recurrent formula holds also for $n = 1$.

A few simulations seem to support the result above.

$\endgroup$
  • 1
    $\begingroup$ +1 for your try on that problem. I will review it later (I am a bit surprised that it only takes one step more and believe you might have made a mistake somewhere). But the real reason for the question here is the problem with the step backwards. That case is a lot more difficult. You can not solve it solely with the recurrence relation because it requires two variables as starting condition: $J_1$ and $J_0$. And a solution needs to be found to determine $J_1$. $\endgroup$ – Sextus Empiricus Sep 16 at 8:37
  • $\begingroup$ Yup please review. As I was writing, I did a couple of simulations and they seem to support the result at a first glance. $\endgroup$ – polettix Sep 16 at 8:43
  • $\begingroup$ I get the same, both in simulation and formula (initially I had it wrong but the simulations convinced me I made an error). $$J_n = \underbrace{1/(n+1) (J_n+1)}_{\text{remain in same place}} + \underbrace{n/(n+1) (J_{n-1})}_{\text{the other options}} $$ or $$J_{n} = J_{n-1} + 1/n$$ $\endgroup$ – Sextus Empiricus Sep 16 at 9:30
3
$\begingroup$

Solution for $J_1$

But what is J1? What is the expected number of steps for a frog that has only one leaf to go?

The solution is $J_1 = 2(e-1)$ and other terms $J_n$ can be expressed as a sum.

Rewriting the recurrence relation as a sum

The recurrence relation is not gonna solve the problem entirely (because one term in the initial conditions is not known), but it does allow us to express $J_n$ as an expression in terms of a finite sum.

The recurrence relation can be rewritten. (for n>3)

$$J_n - J_{n-1} = n (J_{n-1} - J_{n-2})-1 $$

let $D_n = J_n - J_{n-1}$

$$D_n = n D_{n-1}-1 $$

and with starting point $D_2 = 2x $ and we can write (note the recurrence relation is a bit different for $n = 2$ as @quester noted in the comments):

$$\begin{array}{rcrcrcrcrcr} D_1 &=& 3 + 2\,x \\\\ D_2 &=& 2\,x\\ D_3 &=& \overbrace{6 \,x}^{\times 3} &-&1\\ D_4 &=& \rlap{\overbrace{\hphantom{\begin{array}5040\,x&-&7\cdot 6\cdot 5\cdot 4 \end{array}}}^{\times 4}} 24\,x&-&4 &-& 1 \\ D_5&=& \rlap{\overbrace{\hphantom{\begin{array}5040\,x&-&7\cdot 6\cdot 5\cdot 4 &-& 7\cdot 6\cdot 5 \end{array}}}^{ \times 5}} 120\,x&-&5\cdot 4 &-& 5 &-& 1 \\\\ D_6&=& 720\,x&-&6\cdot 5\cdot 4 &-& 6\cdot 5 &-& 6 &- & 1 \\\\ D_7&=& 5040\,x&-&7\cdot 6\cdot 5\cdot 4 &-& 7\cdot 6\cdot 5 &-& 7\cdot 6 &- & 7 &-&- 1 \\\\ D_k &=& k! x &-&\rlap{\sum_{l=3}^{k} \frac{k!}{l!}} \\ \end{array}$$

and

$$ J_n = x \sum_{k=1}^n k! -\sum_{k=3}^n\sum_{l=3}^{k} \frac{k!}{l!} $$


Closed form expression for $x$

Lets rewrite $D_k$

$$\begin{array}{} D_k &=& k! x - \sum_{l=3}^{k} \frac{k!}{l!}\\ &=& k! \left(x - \sum_{l=0}^k \frac{1!}{l!} - 2.5 \right)\end{array}$$

If we conjecture that $\lim_{k \to \infty }D_k$ is positive and finite then this leads to the requirement $\lim_{k \to \infty }\left(x - \sum_{l=0}^k \frac{1!}{l!} - 2.5 \right)= 0$ and

$$x = \lim_{k \to \infty } \left(\sum_{l=0}^k \frac{1!}{l!} - 2.5\right) = e-2.5 \approx 0.2182818 $$

The argument that $\lim_{k \to \infty }D_k$ is finite is still a conjecture but it seems plausible to me.

Closed form expression for $D_k$

Filling in $x$ into the expression of $D_k$ will lead to:

$$\begin{array}{} J_1 &=& D_1 & = & 2e-2 \\ &&D_2 & = & 2e-5 \\ &&D_k & = & k! \left( e - \sum_{l=0}^k \frac{1}{l!}\right) \\ \end{array}$$


Is $J_n$ finite?

We can argue that $J_n$ (the mean number of steps to reach the finish) is finite for any starting point $n$, because the mean position from the finish is decreasing to zero bounded by an exponential decay.

  • The mean distance from the finish: Say a frog starts in position $x$. Then after one jump the frog will be somewhere in position $0 \leq y \leq x+1$ (each option with probability $\frac{1}{x+2}$), and if $y \neq 0$ then after after two jumps the frog will be somewhere in position $0 \leq z \leq y+1$ (each option with probability $\frac{1}{y+2}$). Then the mean position $\bar{z}$ of a frog that started at $x$ and makes two jumps will be: $$ \sum_{y=1}^{x+1}\sum_{z=1}^{y+1}\frac{z}{(x+2)(y+2)} = \frac{x^2+5x+4}{4x+8} \underbrace{\leq\frac{10}{12}x}_{\text{if $x\geq1$}}$$ So whatever the position of the frog, after two jumps, he will be on average at least 1/6 closer to the finish.

  • Probability a frog is still in the game: Note that the probability of a frog still in the game relates to the mean distance of a frog in the game. The mean distance after $k$ jumps is $\mu_{\bar{x},k} \sum_{x=1}^\infty x f(x,k)$, where $f(x,k)$ is the probability of the frog to be in position $x$ after $k$ jumps. The probability of a frog to be still in the game is: $$ 1-F_{(\text{finished at or before jump k})}(k)=\sum_{x=1}^\infty f(x,k) < \mu_{\bar{x},k} \leq x_{start} \left(\frac{10}{12} \right)^{k/2}$$.

  • Finiteness of $J_n$ The mean number of steps necessary can be found by $\sum_{k=0}^\infty k f(k)$ with $f(k)$ the probability that it takes $k$ steps. But you can also take $\sum_{k=0}^\infty 1-F(x)$ with $F(k)$ the probability that it takes $k$ or less steps (note that the integral of the CDF is related to the mean or more generaly the expected value of any quantity is related to the quantile function). And since $1−F(k)$ is smaller than some decreasing exponential function of $k$, so must be the sum smaller than the integral/sum of that function and that is finite.


Starting with a simpler problem

With the recurrence relation $D_n = n D_{n-1} - 1$ it is problematic to solve the case because the starting condition is not defined.

We can instead try to pose a simpler problem (suggested in the comments by @quester and @Hans). Let's say that there are only $m+2$ leaves (instead of infinite), and thus the frog with only $m$ leaves in front of him will not be able to jump backwards. Then $J_m = J_{m-1}$ (the frog in point $m$ has the same options as the frog in point $m-1$) and we will have

$$D_{m} = m! \left(x_m - \sum_{l=0}^m \frac{1!}{l!} - 2.5 \right) = 0$$

which gives a solution for $x_{m}$ as:

$$x_m = \sum_{l=0}^m \frac{1!}{l!} - 2.5 $$

and the limit of $x_m$ as we start adding leaves is:

$$\lim_{m\to \infty} x_m = \lim_{m\to \infty} \sum_{l=0}^m \frac{1!}{l!} -2.5 = e-2.5$$


Written by StackExchangeStrike

$\endgroup$
  • $\begingroup$ +1. Very astute touch introducing $D_n$. I obtained the general expression of $D_n$ through an exponential generating function. How do you obtain yours? Could you please write out your derivation? $\endgroup$ – Hans Oct 10 at 9:40
  • 1
    $\begingroup$ @Hans I have changed the formatting of the equation, placing it in an area that has a triangular form. Each next row is $n$ times the former minus $1$. $\endgroup$ – Sextus Empiricus Oct 10 at 10:02
  • $\begingroup$ The solution to $J_1$ comes from postulating $D_n\to 0$ as $n\to\infty$ without justification. To fix an idea, how about starting from a finite sequence of $N$ leaves allowing no backward jumping when the frog is on the $N$'th leaf? Then let $N\to\infty$ and see where that leads us. $\endgroup$ – Hans Oct 10 at 17:58
  • $\begingroup$ What do you think of my suggestion? $\endgroup$ – Hans Oct 11 at 4:12
  • $\begingroup$ @Hans you are right that $D_n \to 0$ is still a conjecture (but note that the only other option is $D_n \to \pm \infty$ which indeed needs to be disproven but seems very unplausible). Your suggestion to use a finite sequence (backward jumping stopping at a certain position) may work (quester also made that suggestion). $\endgroup$ – Sextus Empiricus Oct 11 at 8:11
1
$\begingroup$

Yes, your recurrence relation holds. I can confirm this with computational solution. Mine is not a simulation though, and can efficiently calculate the expected value with arbitrary precision.

I start with the probability transition matrix A. It's defined as follows:

  • A(i,j) = 1, for i=j=1
  • A(i,j) = 1/(i+1), for j <= i+1
  • A(i,j) = 0, otherwise

A(i,j) is the probability of jumping of a frog from a leave i to a leave j. I feel that there can be an analytical solution, but can't figure out how to find it. It involves the summation of series of $A^k k$, where the matrix A is lower triangular and has a very specific structure.

So, when a frog is one leave i and it already made K jumps by this time and so far the expected value is mu, then we update mu by adding (K+1)*A(i,1). Then we proceed to evaluate jumps to all other possible leaves. If you look at the algorithm, you'll realize that although the recurrence relation holds, it is not very useful in practical sense. Since, calculation of your $J_1$ quantity takes almost as much time as any other $J_n$.

In my algorithm I stop updating when the contribution of the step in recursion becomes small. Yes, I also use recursive algorithm but it's different than yours.

Here's Python code:

import numpy as np

def make_a(n):
  # transition matrix
  a = np.zeros((n, n+1))
  a[0, 0] = 1
  for i in np.arange(1, n):
    a[i, :i+2] = 1 / (i+2)
  return a


def tail(a, k, tol=0.0000001):
  # contribution of k+1 jumps to expected value
  a1 = np.dot(a[1:], make_a(a.shape[0])[1:, :])
  step = a1[0] * (k+1) 
  mu = step
  # print(mu)
  if step > tol:
    mu += tail(a1, k+1, tol)
  return mu


print('check transition table\n', make_a(3))

print('\nexpected num of jumps')
nmax = 20
res = np.zeros(nmax+1)
for n in np.arange(1, nmax+1):
  a = make_a(n+1)
  mu = a[n, 0]
  mu += tail(a[n, :], 1)
  res[n] = mu
  print(n, mu)

print('\ncheck recurrence')
for n in np.arange(3, n+1):
  print(n, (n+1)*res[n-1] - n * res[n-2] - res[n] - 1)

Output:

check transition table
 [[1.         0.         0.         0.        ]
 [0.33333333 0.33333333 0.33333333 0.        ]
 [0.25       0.25       0.25       0.25      ]]

expected num of jumps
1 3.436534083355339
2 3.8731001121305035
3 4.182794921405534
4 4.421556445498667
5 4.615373828428799
6 4.778288520921278
7 4.9187100088637985
8 5.042032360521892
9 5.151942546724475
10 5.2510537683227705
11 5.3412868828615885
12 5.4240942337384
13 5.500600055423081
14 5.57169208948773
15 5.638090948773811
16 5.70036294996792
17 5.758995464909636
18 5.814389400777605
19 5.866883015395631
20 5.916764301539716

check recurrence
1 3.277050462102693e-06
2 1.771300699093814e-05
3 -9.762464467044651e-06
4 -1.0394911689637354e-05
5 -1.8640495164312654e-05
6 4.9551882066012354e-05
7 -9.021279734788834e-06
8 -9.35957247438779e-06
9 -9.676957560600385e-06
10 -9.976410992429408e-06
11 -1.026028613448915e-05
12 -1.0530479119807978e-05
13 -1.8348316348060223e-05
14 0.00010974738318303423
15 -8.494641865475216e-06
16 -8.666917073796299e-06
17 -8.83312660171498e-06
18 -8.993783568556069e-06
$\endgroup$
  • $\begingroup$ Actually the number of leaves is supposed to extend backwards without end. But even when there is a limit then I do not believe your solution is correct. The survival rate is not decreasing by (1-1/n) each step (that would only be the case when the frog is moving one step forwards). $\endgroup$ – Sextus Empiricus Oct 4 at 14:43
  • $\begingroup$ The frog only goes 1 step backwards but all possible steps forward. After the first step the probabiltity to finish should be roughly doubled. $\endgroup$ – Sextus Empiricus Oct 4 at 16:57
  • $\begingroup$ See the simulations. $\endgroup$ – Sextus Empiricus Oct 4 at 16:58
  • $\begingroup$ Aksakal, this computation with a transition matrix is nice, in my question I showed it in R code. But, can we also get an exact expression in terms of a finite number arguments (just like in the standard problem description)? $\endgroup$ – Sextus Empiricus Oct 5 at 14:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.