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

Stochastic Processes Solution – Problem 50: Prove:

Question

Consider the simple symmetric random walk $\{S_{n},n\geqslant0\}$ , $S_{n}=x+\sum_{k=1}^{n}\xi_{k}$ , where $\{\xi_{k}\}_{k=1}^{\infty}$ are i.i.d. with $P\left(\xi_{k}=1\right)=P\left(\xi_{k}=-1\right)=\frac{1}{2}$ . (Note $S_{0}=x$ .) Let $N=\inf\{n\geqslant0,S_{n}\notin(a,b)\}$ , with $x\in(a,b)$ . Prove:

$\begin{array}{l}{(i)\ P\left(S_{N}=a\right)=\displaystyle\frac{b-x}{b-a}}\\ {(ii)\ E\left[N\right]=(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 $\mathcal{F}_n = \sigma(\xi_1, \dots, \xi_n)$ . Since $E[\xi_k]=0$ , $E[S_{n+1} | \mathcal{F}_n] = S_n$ . Define the stopping time $N = \inf\{n \ge 0, S_n \notin (a, b)\}$ . Since the random walk must exit the finite interval, $N < \infty$ a.s. and $|S_{n \wedge N}| \le \max(|a|, |b|) + 1$ . By the optional stopping theorem: $E[S_N] = E[S_0] = x$ .

Step 2. Since $S_N \in \{a, b\}$ , let $P(S_N=a) = p_a$ . Then $a p_a + b(1 - p_a) = x$ , giving $p_a = \frac{b-x}{b-a}$ .

Step 3. Prove part (ii). Construct $M_n = S_n^2 - n$ . Verify $E[M_{n+1} | \mathcal{F}_n] = M_n$ using $E[\xi_{n+1}] = 0$ and $E[\xi_{n+1}^2] = 1$ . So $\{S_n^2 - n\}$ is also a martingale.

Step 4. Apply the optional stopping theorem to $M_n$ : $E[S_N^2 - N] = x^2$ , so $E[N] = E[S_N^2] - x^2$ . Using the probabilities from part (i): $E[S_N^2] = a^2 \frac{b-x}{b-a} + b^2 \frac{x-a}{b-a}$ . Simplifying: $E[N] = (b-x)(x-a)$ .

Final answer

(i) QED. (ii) QED.

Marking scheme

The following is the complete rubric for this problem.

1. Checkpoints (max 7 pts total)

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

Chain A: Martingale Approach (Official Solution)

*Part (i): Probability proof (3 pts)*

Verify $\{S_n\}$ is a martingale (show $E[S_{n+1}|\mathcal{F}_n] = S_n$ ). (1 pt)
Apply the optional stopping theorem to get $E[S_N] = x$ (implicitly or explicitly noting $N<\infty$ and boundedness). (1 pt)
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 (ii): Expectation proof (4 pts)*

Construct and verify $\{S_n^2 - n\}$ is a martingale (showing $E[\xi^2]=1$ ). (1 pt)
Apply the optional stopping theorem to get $E[S_N^2 - N] = x^2$ . (1 pt)
Substitute the probability distribution from part (i) to compute $E[S_N^2]$ . (1 pt)
Complete the algebra to obtain $(b-x)(x-a)$ . (1 pt)

Chain B: Difference Equation / Gambler's Ruin Approach

*Part (i) (3 pts)*

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)
Identify the general solution as linear $u(x)=C_1 x + C_2$ . (1 pt)
Solve for constants and obtain the final formula. (1 pt)

*Part (ii) (4 pts)*

Set up the non-homogeneous 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)
Determine the general solution structure (particular solution $-x^2$ plus homogeneous $C_1 x + C_2$ ). (1 pt)
Solve for constants from boundary conditions. (1 pt)
Substitute back and simplify to $(b-x)(x-a)$ . (1 pt)

Total (max 7)

2. Zero-credit items

Citing standard Gambler's Ruin formulas or $E[N]=Var(S_N)$ without derivation.
Merely copying definitions or target formulas.
Only verifying specific numerical cases.

3. Deductions

-1: Logical jumps (e.g., claiming martingale without verification).
-1: Missing key qualifiers (e.g., not mentioning finiteness of $N$ ).
-1: Boundary condition errors.
-1: Algebra errors leading to mismatched final result.
-2: Conceptual confusion (e.g., treating $S_N$ as constant or assuming $E[S_N^2] = (E[S_N])^2$ ).

Stochastic Processes – Problem 50: Prove: