Stochastic Processes Solution – Problem 21: Prove your conclusions

Question

Remove all horizontal edges from the two-dimensional integer lattice except those on the $x$ -axis, obtaining a "comb-shaped" graph. Is the simple random walk on this graph (i.e., at each step one jumps uniformly at random to a neighbor of the current position) recurrent? Is it positive recurrent? Prove your conclusions.

Step-by-step solution

Step 1. Vertex set: $V(G) = \mathbb{Z}^2$ ; edges: all vertical edges are kept, and only horizontal edges on the $x$ -axis are kept. At $(m,0)$ : degree 4, transition probability $1/4$ each; at $(m,n)$ with $n\neq 0$ : degree 2, probability $1/2$ each.

Step 2. Recurrence. Off the $x$ -axis, the walk moves only vertically, equivalent to a 1D symmetric SRW, which is recurrent. So the walk returns to the $x$ -axis with probability 1. On the $x$ -axis, the effective horizontal displacement is a 1D symmetric SRW (vertical excursions return to the same $x$ -coordinate). Since 1D SRW is recurrent, the walk is recurrent.

Step 3. Not positive recurrent. From the origin, with probability $1/2$ the first step goes to $(0,\pm1)$ . The return time equals $1 + H$ where $H$ is the 1D SRW first-passage time from $\pm1$ to $0$ , which has $E[H]=\infty$ . Similarly, with probability $1/2$ the first step goes to $(\pm1,0)$ , and the 1D SRW return time also has infinite expectation. By the law of total expectation, $E[T] = \infty$ . The walk is null recurrent.

Final answer

The simple random walk is recurrent but not positive recurrent (i.e., it is null recurrent). QED.

Marking scheme

1. Checkpoints (max 7 pts total)

Part 1: Recurrence (3 pts)

Graph structure and transition probabilities [1 pt]: Correctly state on-axis degree 4 (prob. 1/4 each) and off-axis degree 2 (prob. 1/2 each, vertical only).
Recurrence argument [2 pts] [additive]:
[1 pt] Off-axis movement equivalent to 1D symmetric SRW, returns to $x$ -axis with prob. 1.
[1 pt] Effective horizontal displacement on $x$ -axis is 1D symmetric SRW, hence recurrent.
*Alternative (Rayleigh monotonicity)*: subgraph of $\mathbb{Z}^2$ , use recurrence of $\mathbb{Z}^2$ + resistance monotonicity: 2 pts.

Part 2: Positive Recurrence (4 pts) (score one chain only)

Chain A: Mean Return Time

Criterion: state positive recurrence requires $E[T]<\infty$ . [1 pt]
Core: leaving origin involves sub-process with $E=\infty$ (1D SRW return time). [2 pts]
Conclusion via total expectation: $E[T]=\infty$ , null recurrent. [1 pt]

Chain B: Stationary Distribution

Criterion: positive recurrence requires normalizable stationary distribution. [1 pt]
Invariant measure $\mu_x \propto \deg(x)$ , total $\sum \deg(v)=\infty$ . [2 pts]
No probability stationary distribution exists, not positive recurrent. [1 pt]

Total (max 7)

2. Zero-credit items

Only answering "recurrent" or "not positive recurrent" with no justification.
Claiming "since it is part of 2D lattice, it is positive recurrent" (2D lattice is null recurrent).

3. Deductions

Logical confusion (getting $E[T]=\infty$ but concluding positive recurrent or transient): -2 pts.
Missing symmetry mention for 1D SRW: -1 pt.
Undefined symbols without context: -1 pt.

Stochastic Processes – Problem 21: Prove your conclusions