Markov Chain Martingales Dembo 6.1.18

Question

I would really appreciate any help with part b of this problem. thanks!

Answer 1

Loose hints:

(b1) Assume for future contradiction that some subset $S$ of states (besides $0, N$) are not transient... If you start from $x\in S$, what would happen to $\tau_{\{0,N\}}$?

(b2) What does $\tau_N < \tau_0$ mean? Then use the fact that the chain is a martingale (and find an appropriate stopping time).

Answer 2

Here $0$ and $N$ are absorbing states, so if $\mathbb P(\tau_{\{0,N\}}<\infty\mid X_0=x)>0$ for $x\in \mathbb S\setminus\{0,N\}$ then there is a positive probability of absorption when starting at state $x$, and hence $\rho_{xx} = \mathbb P(T_x<\infty\mid X_0 = x)<1$, where $T_x=\inf\{n\geqslant 1:X_n=x\}$. In other words, starting at $x$, there is a positive probability that the process never returns to $x$, and hence is transient.

That $\{X_n\}$ is a martingale for any initial distribution means for any nonnegative integer $n$, $\mathbb E[X_{n+1}\mid X_n] = X_n$. This is equivalent to $$ \sum_{j\in\mathbb S} j\cdot\mathbb P(X_{n+1}=j\mid X_n=i) = i,\ i\in\mathbb S. $$ Now, clearly $\mathbb E[X_1\mid X_0=i]$. If we assume that $\mathbb E[X_{n-1}\mid X_0=i]=i$ for some $n\geqslant 1$, then we have \begin{align} \mathbb E[X_n\mid X_0=i] &= \sum_{j=0}^N j\cdot \mathbb P(X_n=j\mid X_0=i)\\ &= \sum_{j=0}^N \sum_{k=0}^N j\cdot\mathbb P(X_1=k\mid X_0=i)\mathbb P(X_{n-1}=j\mid X_0=k)\\ &= \sum_{k=0}^N \mathbb P(X_1 = k\mid X_0 = i)\sum_{j=0}^N j\cdot \mathbb P(X_{n-1}=j\mid X_0=k)\\ &= \sum_{k=0}^n \mathbb P(X_1=k\mid X_0=i)\mathbb E[X_{n-1}\mid X_0=k]\\ &= \sum_{k=0}^n k\cdot \mathbb P(X_1=k\mid X_1=i)\\ &=\mathbb E[X_1\mid X_0=i]\\ &= i, \end{align} so by induction we have that $i=\mathbb E[X_n\mid X_0=i] = \sum_{j=0}^N j\cdot\mathbb P(X_n=j\mid X_0=i)$ for all $n\geqslant 1$. It follows, taking the limit as $n\to\infty$ that $$ i=\lim_{n\to\infty} 0\cdot \mathbb P(X_n=0\mid X_0=i) + \sum_{j=1}^{N-1}j\cdot \mathbb P(X_n = j\mid X_0=i) + N\cdot \mathbb P(X_n=N\mid X_0=i). $$ Since $\lim_{n\to\infty} \mathbb P(X_n=j\mid X_0=i)=0$ for transient states $j$, we have $$ i = N\cdot \lim_{n\to\infty}\mathbb P(X_n=N\mid X_0=i), $$ that is, $$ \mathbb P(\tau_N<\tau_0) = \lim_{n\to\infty}\mathbb P(X_n=N\mid X_0=i) = \frac iN, $$ as was to be shown.