Stochastic Processes Solution – Problem 37: Prove that this Markov chain is positive recurrent

Question

Starting from the number 0, a fair coin is flipped each time. If the coin lands heads, the number increases by 1; if it lands tails, the number is divided by 2 and rounded down (floor). Prove that this Markov chain is positive recurrent.

Step-by-step solution

Step 1. The state space of this Markov chain is $S=\{0,1,2,\dots\}$ . The transition probabilities are $p_{i,i+1}=\frac{1}{2}$ and $p_{i,\lfloor i/2 \rfloor}=\frac{1}{2}$ . For any states $i, j \in S$ , from $0$ one can reach state $j$ in $j$ steps with probability $(1/2)^j$ (via the path $0 \to 1 \to \dots \to j$ ); from any state $i$ , repeated floor-halving reaches $0$ in finitely many steps. Hence the chain is irreducible.

Step 2. Apply the Foster-Lyapunov criterion. Construct the Lyapunov function $V(i) = i$ , so $V(i) \ge 0$ and $V(i) \to \infty$ as $i \to \infty$ . The one-step mean drift is $\Delta V(i) = E[V(X_{n+1}) - V(X_n) \mid X_n = i] = \frac{1}{2}(i+1) + \frac{1}{2}\lfloor i/2 \rfloor - i$ .

Step 3. When $i$ is even, say $i = 2k$ : $\lfloor i/2 \rfloor = k = i/2$ , so $\Delta V(i) = \frac{1}{2}(i+1) + \frac{i}{4} - i = \frac{1}{2} - \frac{i}{4}$ . When $i$ is odd, say $i = 2k+1$ : $\lfloor i/2 \rfloor = k = (i-1)/2$ , so $\Delta V(i) = \frac{1}{2}(i+1) + \frac{i-1}{4} - i = \frac{1}{4} - \frac{i}{4}$ .

Step 4. Take the finite set $F = \{0, 1, 2\}$ . For $i \notin F$ (i.e., $i \ge 3$ ): if $i$ is even ( $i \ge 4$ ), $\Delta V(i) = \frac{1}{2} - \frac{i}{4} \le -\frac{1}{2}$ ; if $i$ is odd ( $i \ge 3$ ), $\Delta V(i) = \frac{1}{4} - \frac{i}{4} \le -\frac{1}{2}$ . Hence for all $i \notin F$ , $\Delta V(i) \le -\frac{1}{2}$ .

Step 5. For states in $F$ , $E[V(X_{n+1}) \mid X_n = i]$ is clearly finite. By Foster's theorem, since there exists a Lyapunov function $V$ , a finite set $F$ , and a constant $\epsilon = \frac{1}{2} > 0$ such that the mean drift is at most $-\epsilon$ outside $F$ and finite inside $F$ , the irreducible chain is positive recurrent.

Final answer

QED.

Marking scheme

This rubric is based on the official solution (Foster-Lyapunov criterion).

1. Checkpoints (max 7 pts total)

Score exactly one chain | take the maximum subtotal among chains; do not add points across chains.

Chain A: Foster-Lyapunov Criterion / Pakes' Lemma (Recommended)

Irreducibility
State that the chain is irreducible (e.g., from 0 any state $j$ is reachable, and any state $j$ eventually returns to 0). [1 pt]
Lyapunov function choice
Construct $V(i) = i$ (or $V(i)=ci$ , $c>0$ ; or another valid function with $V(i) \to \infty$ ). [1 pt]
Mean drift computation (Heavy Lifting)
Write the correct expression for $\Delta V(i)$ combining both transition probabilities. [1 pt]
Correctly simplify to obtain the expression with a negative dominant term (e.g., $\frac{1}{2} - \frac{i}{4}$ ). [1 pt]
Drift bound analysis
Argue that for sufficiently large $i$ (or outside a finite set $F$ ), the drift is at most $-\epsilon$ for some $\epsilon > 0$ . [2 pts]
*If only qualitatively stating "drift tends to $-\infty$ " without specifying the finite set $F$ and uniform bound, award 1 pt.*
Criterion conclusion
Cite Foster-Lyapunov criterion (or Foster's theorem / Pakes' lemma) to conclude positive recurrence. [1 pt]

Chain B: Direct Definition / Stationary Distribution Existence

Irreducibility: State irreducibility. [1 pt]
Balance equations: Correctly write the balance equations for $\pi$ . [1 pt]
Series convergence proof (Heavy Lifting): Rigorously prove $\sum \pi_j < \infty$ . [4 pts]
Conclusion: State existence of a normalizable stationary distribution implies positive recurrence. [1 pt]

Total (max 7)

2. Zero-credit items

Only copying transition rules without derivation.
Only listing definitions of Markov chain or positive recurrence without connecting to the problem.
Incorrectly claiming "since transition probabilities sum to 1, the chain is positive recurrent."
Only computing specific paths without a general proof.
Claiming the chain is null recurrent or transient.

3. Deductions

Logical contradiction: Computing $\Delta V(i) \ge 0$ but concluding positive recurrence. (-2 pts)
Missing condition: Completely ignoring the finite set $F$ in Foster's theorem. (-1 pt)
Conceptual error: Confusing recurrence with positive recurrence. (-1 pt)

Stochastic Processes – Problem 37: Prove that this Markov chain is positive recurrent