Consider the simple symmetric random walk , , i.i.d., with . (Note .) Let , and . Prove:

Stochastic Processes Solution – Problem 38: Prove:

Question

Consider the simple symmetric random walk $\{S_n, n \geq 0\}$ , $S_n = x + \sum_{k=1}^{n} \xi_k$ , $\{\xi_k\}_{k=1}^{\infty}$ i.i.d., with $P(\xi_k = 1) = P(\xi_k = -1) = \frac{1}{2}$ . (Note $S_0 = x$ .) Let $N = \inf\{n \geq 0 : S_n \notin (a,b)\}$ , and $x \in (a,b)$ . Prove:

$\begin{array}{l}{(i)\ P(S_N = a) = \frac{b-x}{b-a}} \\ {(ii)\ E[N] = (b-x)(x-a).}\end{array}$

Step-by-step solution

Step 1. Prove part (i). First show $\{S_n\}$ is a martingale with respect to the natural filtration $\mathcal{F}_n = \sigma(\xi_1, \dots, \xi_n)$ . Since $\xi_k$ are i.i.d. with $E[\xi_k]=0$ : $E[S_{n+1} | \mathcal{F}_n] = S_n + E[\xi_{n+1}] = S_n.$ So $\{S_n\}$ is a martingale. Define the stopping time $N = \inf\{n \ge 0 : S_n \notin (a,b)\}$ . Since the random walk on a finite interval must exit, $N < \infty$ a.s. and $E[N] < \infty$ . Before time $N$ , $S_n$ is bounded in $(a,b)$ , so $|S_{n \wedge N}| \le \max(|a|, |b|) + 1$ . By the optional stopping theorem: $E[S_N] = E[S_0] = x.$

Step 2. Use the distribution of $S_N$ to solve for the probability. $S_N$ can only take values $a$ or $b$ . Let $P(S_N = a) = p_a$ , then $P(S_N = b) = 1 - p_a$ . Substituting into the expectation: $E[S_N] = a \cdot p_a + b \cdot (1 - p_a) = x.$ Solving: $p_a(b - a) = b - x$ , so $p_a = \frac{b-x}{b-a}$ . Hence $P(S_N = a) = \frac{b-x}{b-a}$ . Part (i) is proved.

Step 3. Prove part (ii). Construct the process $M_n = S_n^2 - n$ . Compute: $E[S_{n+1}^2 | \mathcal{F}_n] = E[(S_n + \xi_{n+1})^2 | \mathcal{F}_n] = S_n^2 + 2S_n E[\xi_{n+1}] + E[\xi_{n+1}^2] = S_n^2 + 1.$ Therefore $E[S_{n+1}^2 - (n+1) | \mathcal{F}_n] = S_n^2 - n = M_n$ , so $\{S_n^2 - n\}$ is also a martingale.

Step 4. Apply the optional stopping theorem to $M_n$ to find $E[N]$ . Since $E[N] < \infty$ and increments are bounded, OST applies: $E[S_N^2 - N] = E[S_0^2] = x^2.$ So $E[N] = E[S_N^2] - x^2$ . Using the probabilities from Step 2: $E[S_N^2] = a^2 \cdot \frac{b-x}{b-a} + b^2 \cdot \frac{x-a}{b-a}.$ Simplifying: $E[N] = \frac{a^2(b-x) + b^2(x-a)}{b-a} - x^2 = -ab + x(b+a) - x^2 = (b-x)(x-a).$ Part (ii) is proved.

Final answer

(i) QED. (ii) QED.

Marking scheme

The following is the complete grading rubric for this problem and official solution.

1. Checkpoints (max 7 pts total)

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

Chain A: Martingale Approach (Based on Official Solution)

*Part 1: Probability proof (3 pts)*

[additive] Verify $\{S_n\}$ is a martingale (show $E[S_{n+1}|\mathcal{F}_n] = S_n$ or use the independent zero-mean increment property). (1 pt)
[additive] Apply the optional stopping theorem (OST) to get $E[S_N] = x$ (implicitly or explicitly noting $N<\infty$ and boundedness). (1 pt)
[additive] Set up $a P(S_N=a) + b(1-P(S_N=a)) = x$ and solve $P(S_N=a) = \frac{b-x}{b-a}$ . (1 pt)

*Part 2: Expectation proof (4 pts)*

[additive] Construct and verify $\{S_n^2 - n\}$ is a martingale (must show $E[\xi^2]=1$ and key computations). (1 pt)
[additive] Apply OST again to get $E[S_N^2 - N] = x^2$ (or equivalently $E[N] = E[S_N^2] - x^2$ ). (1 pt)
[additive] Substitute the probability distribution from part 1 to compute $E[S_N^2] = a^2 p_a + b^2(1-p_a)$ . (1 pt)
[additive] Complete the algebraic simplification from $E[S_N^2]-x^2$ to the final form $(b-x)(x-a)$ . (1 pt)

Chain B: Difference Equation / Gambler's Ruin Approach

*Part 1: Probability proof (3 pts)*

[additive] Set up the difference equation $u(x) = \frac{1}{2}u(x+1) + \frac{1}{2}u(x-1)$ with boundary conditions $u(a)=1, u(b)=0$ . (1 pt)
[additive] Identify the general solution as linear: $u(x)=C_1 x + C_2$ . (1 pt)
[additive] Apply boundary conditions to solve for constants and obtain the final probability formula. (1 pt)

*Part 2: Expectation proof (4 pts)*

[additive] Set up the nonhomogeneous difference equation $v(x) = 1 + \frac{1}{2}v(x+1) + \frac{1}{2}v(x-1)$ with $v(a)=0, v(b)=0$ . (1 pt)
[additive] Determine the general solution structure (particular solution $-x^2$ plus homogeneous solution $C_1 x + C_2$ ). (1 pt)
[additive] Apply boundary conditions to set up and solve the system for $C_1, C_2$ . (1 pt)
[additive] Substitute back and simplify to the final form $(b-x)(x-a)$ . (1 pt)

Total (max 7)

2. Zero-credit items

Citing Gambler's Ruin formulas or $E[N]=\mathrm{Var}(S_N)$ without derivation.
Only copying definitions or target formulas without substantive derivation.
Only verifying specific numerical cases rather than a general proof.

3. Deductions

-1: Logical gap, e.g., claiming "this is a martingale" without verification, or writing the general solution without the difference equation.
-1: Missing key qualifiers (e.g., not mentioning finiteness/boundedness of $N$ as a prerequisite for applying the theorem).
-1: Boundary condition error (e.g., swapping the probability values of $a, b$ ).
-1: Algebraic error leading to a mismatched final result.
-2: Conceptual confusion, e.g., treating $S_N$ as a constant, or assuming $E[S_N^2] = (E[S_N])^2$ .

Stochastic Processes – Problem 38: Prove: