Random Walk on a Table -- Expected Steps to Fall Off
A robot is placed on a one-dimensional table of length $L$ cm, at a distance $x$ cm from the left edge (so it is $L - x$ cm from the right edge). At each step, the robot moves 1 cm to the left with probability $p$ and 1 cm to the right with probability $q = 1 - p$. The robot falls off when it reaches either edge.
- Find the expected number of steps $E_x$ until the robot falls off, as a function of $x$, $L$, $p$, and $q$.
- Simplify for the symmetric case $p = q = 1/2$.
- Verify your formula with a sanity check: what happens at $x = 0$, $x = L$, and $x = L/2$ in the symmetric case?
Hints
- Set up the recurrence $E_i = 1 + p E_{i-1} + q E_{i+1}$ with boundary conditions $E_0 = E_L = 0$. This is a second-order linear difference equation.
- For the symmetric case, define $D_i = E_{i+1} - E_i$ and show that $D_i - D_{i-1} = -2$, which telescopes to give $E_i = i(L - i)$.
- For the biased case, the characteristic equation $qr^2 - r + p = 0$ has roots $r = 1$ and $r = p/q$. Find a particular solution of the form $ci$ and apply boundary conditions.
Worked Solution
How to Think About It: This is the gambler's ruin problem in disguise. The robot's position is the gambler's fortune, the table edges are the absorbing barriers at 0 and $L$, and we want the expected duration of the game rather than the ruin probability. The recurrence is straightforward: from position $i$, you spend one step and then you are at $i-1$ or $i+1$ with probabilities $p$ and $q$. Boundary conditions: $E_0 = E_L = 0$ (you have already fallen off). The recurrence is a second-order linear difference equation with constant coefficients, so you can solve it by standard techniques.
Quick Estimate: For the symmetric case with $L = 100$ and $x = 30$: the formula (which we will derive) gives $E_{30} = 30 \times (100 - 30) = 2100$ steps. Intuitively, the expected duration scales quadratically in $L$ for a symmetric random walk -- doubling the table length quadruples the expected time. The maximum is at the center: $E_{L/2} = L^2/4$.
Approach: Set up the recurrence $E_i = 1 + p E_{i-1} + q E_{i+1}$ with $E_0 = E_L = 0$ and solve as a linear difference equation.
Formal Solution:
*The Recurrence:*
For $1 \leq i \leq L-1$:
$$E_i = 1 + p E_{i-1} + q E_{i+1}, \quad E_0 = E_L = 0$$
Rearranging: $q E_{i+1} - E_i + p E_{i-1} = -1$.
*Case 1: Symmetric walk ($p = q = 1/2$):*
The recurrence becomes:
$$\frac{1}{2} E_{i+1} - E_i + \frac{1}{2} E_{i-1} = -1$$
or equivalently $E_{i+1} - 2E_i + E_{i-1} = -2$.
Let $D_i = E_{i+1} - E_i$. Then $D_i - D_{i-1} = -2$, so $D_i = D_0 - 2i$.
Summing: $E_i = E_0 + \sum_{j=0}^{i-1} D_j = \sum_{j=0}^{i-1}(D_0 - 2j) = i D_0 - i(i-1)$.
Using $E_L = 0$: $L D_0 - L(L-1) = 0$, so $D_0 = L - 1$.
Therefore:
$$E_i = i(L-1) - i(i-1) = i(L - i)$$
*Sanity checks:* $E_0 = 0$ and $E_L = 0$ (good). $E_{L/2} = L^2/4$ (maximum at center). $E_1 = L - 1$ and $E_{L-1} = L - 1$ (symmetric).
*Case 2: Biased walk ($p \neq q$):*
The homogeneous equation $q E_{i+1} - E_i + p E_{i-1} = 0$ has characteristic equation $q r^2 - r + p = 0$, giving roots $r = 1$ and $r = p/q$.
The general solution to the inhomogeneous equation is:
$$E_i = A + B \left(\frac{p}{q}\right)^i + \frac{i}{q - p}$$
(The particular solution $i/(q-p)$ works when $p \neq q$.)
Applying $E_0 = 0$: $A + B = 0$, so $B = -A$.
Applying $E_L = 0$: $A - A(p/q)^L + L/(q-p) = 0$, giving:
$$A = \frac{L}{(q-p)(1 - (p/q)^L)}$$
Therefore:
$$E_i = \frac{L}{(q-p)} \cdot \frac{1 - (p/q)^i}{1 - (p/q)^L} - \frac{i}{q-p}$$
which can also be written as:
$$E_i = \frac{1}{q - p}\left(\frac{L(1 - (p/q)^i)}{1 - (p/q)^L} - i\right)$$
Answer: For a symmetric walk ($p = q = 1/2$), the expected number of steps to fall off from position $x$ is $E_x = x(L - x)$. For a biased walk ($p \neq q$), the formula is $E_x = \frac{1}{q-p}\left(\frac{L(1-(p/q)^x)}{1-(p/q)^L} - x\right)$.
Intuition
The symmetric case $E_x = x(L-x)$ is one of the most elegant results in random walk theory. It says the expected game duration is maximized at the center of the table and equals zero at the boundaries -- both intuitively obvious. The quadratic scaling $E \sim L^2$ reflects the diffusive nature of random walks: it takes $O(L^2)$ steps to diffuse a distance $L$. This is the discrete analog of the continuous result that the expected exit time of Brownian motion from an interval $[0, L]$ starting at $x$ is $x(L-x)$.
The biased case introduces exponential terms $(p/q)^i$, and the expected duration is no longer symmetric in $x$. When the walk is biased toward one edge, the robot falls off that edge quickly from nearby positions, reducing the expected time. In the extreme limit $p/q \to 0$ or $p/q \to \infty$, the duration becomes approximately linear in the distance to the nearer edge. This same framework -- gambler's ruin with absorbing barriers -- appears in option pricing (binomial trees), population genetics (fixation times), and queueing theory (busy periods).