Stochastic Processes Solution – Problem 34: Find the expected time for a simple random walk starting from the origin to first reach

Question

Consider the $[-N,N]^2$ grid. Remove all horizontal edges except those on the $x$ -axis (resulting in a comb-shaped graph). Find the expected time for a simple random walk starting from the origin to first reach $(N,0)$ .

Step-by-step solution

Let the vertex set of the two-dimensional grid be $V = \{(x,y) : x,y \in \mathbb{Z}, -N \le x \le N, -N \le y \le N\}$ . The random walk starts from the origin $(0,0)$ , and the goal is to first reach $(N,0)$ . Let $E(x,y)$ denote the expected number of steps from point $(x,y)$ to reach $(N,0)$ . Since $(N,0)$ is an absorbing wall, $E(N,0) = 0$ . By the symmetry of the graph about the $x$ -axis and the simple random walk rules, $E(x,y) = E(x,-y)$ , so we only need to consider $y \ge 0$ . Let $F(x) = E(x,0)$ denote the expected time starting from a point on the $x$ -axis.

For fixed $x \in \{-N, \dots, N-1\}$ , consider the vertical point $(x,k)$ where $1 \le k \le N$ . When $1 \le k < N$ , the node $(x,k)$ can only move vertically with two neighbors, each with transition probability $1/2$ . The equation is $E(x,k) = 1 + \frac{1}{2}E(x,k-1) + \frac{1}{2}E(x,k+1)$ , yielding the second-order difference equation $E(x,k+1) - 2E(x,k) + E(x,k-1) = -2$ . When $k = N$ , the node $(x,N)$ has only one neighbor $(x,N-1)$ , giving $E(x,N) = 1 + E(x,N-1)$ . The general solution is $E(x,k) = -k^2 + c_1 k + c_2$ with $c_2 = F(x)$ . Applying the boundary condition yields $c_1 = 2N$ . Therefore $E(x,k) = -k^2 + 2Nk + F(x)$ , and in particular $E(x,1) = F(x) + 2N - 1$ .

For interior nodes $x \in \{-N+1, \dots, N-1\}$ , the node $(x,0)$ has 4 neighbors. Using symmetry and substituting $E(x,1) = F(x) + 2N - 1$ , we obtain $F(x+1) - 2F(x) + F(x-1) = -(4N + 2)$ . The general solution is $F(x) = -(2N+1)x^2 + Ax + B$ .

Right boundary: $F(N) = 0$ gives $B = (2N+1)N^2 - AN$ . Left boundary: at $x=-N$ , the node $(-N,0)$ has only 3 neighbors, yielding $F(-N) - F(-N+1) = 4N + 1$ , which gives $A = -4N^2 - 4N$ .

Substituting: $B = (2N+1)N^2 + (4N^2 + 4N)N = 6N^3 + 5N^2$ . The expected time from the origin is $F(0) = B = 6N^3 + 5N^2$ .

Final answer

$6N^3 + 5N^2$

Marking scheme

The following is the grading rubric. Please grade according to the three parts below.

1. Checkpoints (Total 7 Points)

Note: This problem contains two main computational modules (vertical branch analysis, horizontal spine analysis). Map the student's solution to the following checkpoints. Award points per checkpoint; no double counting.

1. Vertical Branch Analysis (3 points)

*This part evaluates the student's derivation of the vertical (tooth) random walk properties.*

[1 pt] Establish the vertical model: Write the difference equation for vertical nodes $E(x,k)$ ( $E(x,k) = 1 + \frac{1}{2}E(x,k-1) + \frac{1}{2}E(x,k+1)$ with boundary conditions), or explicitly identify this as a one-dimensional random walk problem with absorption at 0 and reflection at N.
[2 pts] Derive the vertical expected increment: Correctly solve for the expected time increment from $(x,1)$ back to the $x$ -axis, i.e., obtain $E(x,1) = F(x) + 2N - 1$ or state that the expected number of steps from $(x,1)$ to $(x,0)$ is $2N-1$ .
*Note: If only the general solution form is written without determining coefficients, award 0 points.*

2. Horizontal Spine Recursion (2 points)

[1 pt] Establish the spine equation: Write the state transition equation for $F(x)$ at interior $x$ -axis nodes, correctly substituting the vertical result.
[1 pt] Derive the spine difference relation: Simplify to the correct second-order nonhomogeneous linear difference equation $F(x+1) - 2F(x) + F(x-1) = -(4N+2)$ .

3. Boundary Conditions and Final Solution (2 points)

[1 pt] Left boundary treatment ( $x=-N$ ): Correctly handle the degree change at $x=-N$ (degree 3), obtaining $F(-N) - F(-N+1) = 4N+1$ or correctly finding $A = -4N^2-4N$ .
[1 pt] Final result: Combining with $F(N)=0$ , compute the exact answer $6N^3 + 5N^2$ .

2. Zero-credit items

Only restating the problem conditions or defining variables.
Only stating $F(N)=0$ or $E(x,y)=E(x,-y)$ without substantive computation.
Only the final answer with no derivation.
Incorrectly assuming the graph is a simple 1D walk or resistance network without correcting for degree differences.

3. Deductions

[-1 pt] Arithmetic error: Correct approach but algebraic simplification or arithmetic errors lead to an incorrect final result.
[-1 pt] Logical gap: Directly writing the general solution without any derivation.
[-2 pts] Boundary condition error: Ignoring that $x=-N$ has degree 3, incorrectly treating it as a degree-4 interior node.

Total (max 7)

Stochastic Processes – Problem 34: Find the expected time for a simple random walk starting from the origin to first reach