Hopping frogs on an infinitely long row of cells

Question

There is a row of cells that is infinitely long in both directions.

The cells are numbered with integers $...,-2,-1,0,1,2,...$ from left to right.

Initially, all cells are empty. At each time step,

• Each frog will independently jump either left by 1 cell or right by 2 cells with equal probability.
• All frogs at cell 0 are removed.
• One frog is placed at cell 0.

After a sufficiently long time, what is the expected number of frogs $p_n$ in cell $n$?

---

Source: The exact source is unknown. I got a similar puzzle of going upstairs/downstairs from a friend and re-phrased it into cells and frogs as I think it is clearer in this way.

What I tried:

• Using recurrence $p_n=\frac12(p_{n-2}+p_{n+1})$ but the boundary condition $p_0=1$ is not sufficient.
• Simulation shows $p_n\rightarrow0.854...$ for $n>0$ and $p_n\rightarrow0$ for $n<0$.

  import numpy as np
  n=10000
  p=np.zeros(4*n)
  o=2*n
  for _ in range(n):
      p[2:-1]=(p[:-3]+p[3:])/2
      p[o]=1
  print(p[o-1000],p[o+1000]) # 1.0288682133996791e-209 0.8541019662496823
  

Answer 1

This feels more like a math problem than a puzzle but it has some nice twists.

Part 1: Let's solve the equation

$$p_n=\frac12(p_{n-2}+p_{n+1}) \\ p_{n+1} - 2p_n + p_{n-2} = 0 \\ p_{n+3} - 2p_{n+2} + p_n = 0$$ If we search solutions of the form $p_n = \lambda^n$ we get $$\lambda^{n+3} - 2 \lambda^{n+2} + \lambda^n = 0\\ \lambda^3 - 2 \lambda^2 + 1 = 0\\ (\lambda - 1)(\lambda^2 - \lambda - 1) = 0$$ $$\lambda \in \{1, \varphi, \psi\}$$ where $\varphi = \frac{1+\sqrt{5}}{2}$ and $\psi = \frac{1-\sqrt{5}}{2} = \frac{-1}{\varphi}$

We can verify that $p_n = 1$, $p_n = \varphi^n$ and $p_n = \psi^n$ for example verify the equation. All the solutions to the equation are actually of the form $$p_n = A + B\varphi^n + C\psi^n$$ But wait... none of these solutions correspond to the simulation! What is going wrong?

Part 2: An analogy

Let's consider the situation where the frogs only go one cell to the right.

If we try the same approach, we get the equation $p_n = p_{n-1}$ which has solutions of the form $p_n = A$. We could try using the "boundary condition" $p_0 = 1$ to get $A = 1$ and conjecture that we expect one frog on every cell if we wait long enough. It is a stable solution, but not the limit solution reached from the initial state, because no frog can go to the left and end up on a negative cell.

The special rule on cell $0$ should not be used as a boundary condition, and instead can justify a different solution on the negative cells and on the positive cells:

• For $n < 0$, the equation $p_n = p_{n-1}$ holds, and $p_n = A_1$.
• For $n > 0$, the equation $p_n = p_{n-1}$ holds, and $p_n = A_2$.
• For $n = 0$ we just have $p_0 = 1$, which gives us in turn $A_2 = 1$.
• We need an extra argument like "no frog can reach a negative square" to declare that a limit solution should verify $A_1 = 0$
• Even then it is not fully clear that the limit solution is reached (well in this simple case it is clear).

Part 3: A multi-part solution

• For $n < 0$, the equation $p_n=\frac12(p_{n-2}+p_{n+1})$ holds, so $p_n = A_1 + B_1\varphi^n + C_1\psi^n$
• For $n > 0$, the equation $p_n=\frac12(p_{n-2}+p_{n+1})$ holds, so $p_n = A_2 + B_2\varphi^n + C_2\psi^n$
• We can prove by induction that the expected number of frogs in cell $n$ is lower than $1$ at all times (Thx @Nitrodon). This gives us $B_2 = 0$.
• We can prove by induction that the expected number of frogs in cell $n$ is lower than $\varphi^n$ at all times (Thx @Nitrodon), in particular $\lim_{n \to -\infty} p_n = 0$. This gives us $B_1 = 0$ and $A_1 = 0$
• We have $p_0 = 1$ so this gives us $C_1 = 1$
• We have $p_{-1} = \varphi^{-1}$ and $p_0 = 1$ so this gives us $C_2 = \frac{1}{\varphi^4}$ and $A_2 = 1 - \frac{1}{\varphi^4}$

In the end, if we wait long enough, we expect $p_n = \varphi^n$ for $n \leq 0$ and $p_n = 1-\frac{1}{\varphi^4} + \frac{1}{\varphi^4} \frac{-1}{\varphi^n}$ for $n \geq 0$, which matches the simulation.