Past exam of the mathematics course of the University of Cambridge / 2009 / iii / Paper 101 / 4

Let $\tau =T_{-a}\wedge T_b$ for the simple symmetric random walk. From any interior point, $a+b$ successive $+1$ increments force exit through $b$. The conditional probability of this block is $2^{-(a+b)}$, so a blockwise geometric tail bound from a uniform escape probability gives $\tau <\infty$ almost surely.

Apply the bounded optional stopping theorem to $\tau \wedge n$. Since $S_n$ is a martingale, ${\mathbb{E}}_0{S}_{\tau \wedge n}=0$. The stopped positions lie in $[-a,b]$, so the bounded convergence theorem gives ${\mathbb{E}}_0{S}_{\tau }=0$. If $h={\mathbb{P}}_0(T_{-a}<T_b)$, nearest-neighbor jumps ensure $S_{\tau }=-a$ on that event and $S_{\tau }=b$ otherwise. ThusNext apply the bounded optional stopping theorem to the square-minus-time martingale of a simple symmetric random walk:Again the right side converges by the bounded convergence theorem, while the left side increases to ${\mathbb{E}}_0\tau$ by the monotone convergence theorem. ThereforeThis argument justifies passage to the unbounded stopping time rather than applying optional stopping without an integrability check.

For $0<i<N$, the total rate out of $i$ is ${\lambda }_i$. The holding time of the continuous-time Markov chain and its next state satisfyThe holding time is independent of the direction of this jump: the conditional probability of destination $j$ is the rate $q_{ij}$ divided by the total rate ${\lambda }_i$, independently of the elapsed holding duration. This is the exponential-clock construction of a continuous-time Markov chain with the given infinitesimal generator matrix.

At $i=0$ or $i=N$, all rates out are zero. These are absorbing states; the path remains at its initial endpoint and $J_i=\infty$ almost surely. There is no next visited state, so $X_{J_i}$ is not a finite-time jump value at either endpoint. If one separately uses $X_{\infty }$ for the limiting state, that limit is the same endpoint.

The embedded jump chain in the interior is a simple symmetric random walk on $\{0,\dots ,N\}$, stopped at the endpoints. From any interior state it has probability at least $2^{-N}$ of hitting a boundary in the next $N$ jumps, by following successive leftward choices. Thus its number of jumps before absorption is finite almost surely. Each of this finite number of holding times is finite almost surely, so absorption also occurs in finite continuous time. The finite set of positive interior rates causes no explosion; in particular their maximum bounds the total jump rate. When $N=1$, the chain starts at an already absorbing endpoint.

The rates alter the clock but not the sequence of visited states. The gambler's ruin calculation from part (a), translated to an initial state $i$ between endpoints $0,N$, therefore givesThis includes probability one at zero and probability zero at $N$.

Use the positive-integer convention for the geometric distribution:Conditional on $K=k$, independence gives $\mathbb{E}[S\mid K=k]=k/\lambda$. Taking expectations givesThis is the convention required below because a chain starting at $i$ makes at least one visit to $i$. If instead $K$ counts failures on $\{0,1,\dots \}$, its mean is $(1-p)/p$, and the corresponding answer for that different random sum is $(1-p)/(p\lambda )$.

For the chain of part (b), let $K_i$ count visits to $i$, including the initial visit, before absorption. After a departure to $i-1$, gambler's ruin on $\{0,\dots ,i\}$ gives probability $1/i$ of reaching zero before returning to $i$. After a departure to $i+1$, the analogous probability of reaching $N$ before returning is $1/(N-i)$. The departure is equally likely in either direction, so the probability of absorption before a return isAt every return to $i$, the Strong Markov property resets these alternatives. Hence the geometric return count before absorption gives $K_i\sim \mathrm{Geom}(p_i)$ on positive integers. One may construct the chain from its embedded jump chain and a separate sequence of fresh independent exponential clocks. Then its successive holding times at $i$ are independent and identically distributed rate-${\lambda }_i$ exponential random variables, independently of $K_i$, andUsing the first calculation gives the occupation time at an interior state of a variable-rate symmetric walk:For $N=2,i=1$, $p_i=1$ and the only visit is the initial one; the degenerate positive-integer geometric distribution at one handles this case. Other states' rates affect the time of each excursion, but not its probability of return, which explains why only ${\lambda }_i$ appears in this expectation.