Markov Chain Martingales Dembo 6.1.18 
I would really appreciate any help with part b of this problem. thanks!
 A: 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.
A: 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).
