Verify that $X_n$ is a martingale Let $P_{ij}=e^{-i}i^j/j!,\;i,j=0,1,...$ be the transition probabilities for a Markov chain $X_n$. We consider $P_{00}=1$. (a) Verify that $X_n$ is a martingale. (b) Derive the inequality
$$\Pr\{\max_{0\leq n<\infty} X_n\geq a\mid X_0=i\}\leq i/a$$
for $i,a,=1,2,...$. (c) Prove that $\lim_{n\rightarrow\infty}X_n=0$ with probability one.
(a) I am having trouble showing that $X_n$ is a martingale. Can I get some help with this part? I know I need to show that $E[X_{n+1}\mid \mathcal{F}_n]=X_n$. Then using the definition of expectation, I'd get $E[X_n]=\sum_j^\infty jP(j)$. How do I know that I sum over $j$ and not over $i$?
For part (b), since $X_n$ is a martingale, we can consider a stopping time $T=\max_{0\leq a<\infty}(X_n)$ and the stopped martingale $X_{T\wedge a}$. Then we have
$$i=X_0=E[X_{T\wedge a}]=E[X_{T\wedge a}\cap T\geq n]+E[X_{T\wedge a}<n]\geq aP(T\geq n)+0$$
Thus, we have $P(T\geq a)\leq \frac{1}{a}$.
(c) I am not sure about this part but I would like to understand part (a) first because I would like to see how to verify that $X_n$ is a martingale from the transition probabilities.
 A: Hope this helps.
For part (a), to check that $E[X_{n+1}|\mathscr{F}_n]=X_n$, we have that the process is Markov with discrete state space, so we can express the conditional expectation of $X_{n+1}$ wrt $\mathscr{F}_n$ as
$$E[X_{n+1}|\mathscr{F}_{n}]=\sum_{k\in \mathbb{N}\cup \{0\}}E[X_{n+1}|X_{n}=k]\mathbf{1}_{\{X_n=k\}}$$
and (see Poisson distribution)
$$E[X_{n+1}|X_{n}=k]=\sum_{j\in \mathbb{N}}j\frac{e^{-k}k^j}{j!}=k$$
So
$$E[X_{n+1}|\mathscr{F}_{n}]=\sum_{k\in \mathbb{N}}k\mathbf{1}_{\{X_n=k\}}=X_n$$

For part (b) we use Doob's maximal inequality. Suppose $X_0=j$. Recall that a martingale is also a supermartingale so
$$aP\bigg(\max_{k\leq n}X_k\geq a\bigg)\stackrel{\textrm{Doob}}{\leq} E[X_n]=j$$
and (consider that the state space is discrete)
$$\bigg\{\sup_{n \in \mathbb{N}}X_n\geq  a\bigg\}=\bigg\{\sup_{n \in \mathbb{N}}\max_{k\leq n}X_k\geq  a\bigg\}=\bigcup_{n \in \mathbb{N}}\bigg\{\max_{k\leq n}X_k\geq a\bigg\}$$
and since $\{\max_{k\leq n}X_k \geq a\}\subseteq \{\max_{k\leq n+1}X_k\geq a\},\,\forall n$, we get by continuity of measures
$$aP\bigg(\sup_{n \in \mathbb{N}}X_n\geq  a\bigg)\leq j$$

For part (c) I will just present an informal argument. I will assume that the stationary distribution $\pi$ exists and we find it:
$$\pi_j=\sum_{k \in \mathbb{N}\cup\{0\}}P_{kj}\pi_k\in [0,1],\,\forall j$$
consider that
$$\pi_0=\sum_{k \in \mathbb{N}\cup\{0\}}e^{-k}\pi_k=\pi_0+\pi_1e^{-1}+(...)$$
By subtracting $\pi_0$ from both sides, we obtain that $\pi_k=0,\,\forall k >0$, so $\pi_0=1$ necessarily.
