Question about Markov chain derived from a Poisson process Let $(N_t)$ be a Poisson process of rate $\lambda$. Deﬁne $$
X_n = N_n − n,\quad\text{for }\; n = 0, 1, 2, \ldots
$$
Explain why $(X_n)$ is a Markov chain and give its transition probabilities. 
Using Stirling’s formula or otherwise, show that the chain is recurrent if and only if $\lambda = 1$. 
If $\lambda = 1$, is it null recurrent or positive recurrent?
I think the state space is all of the integers and the chain is irreducible.
I think the transition probabilities are 
$$
P(X_{n+1} = k+r \mid X_n = k) = e^{-\lambda}\frac{\lambda^{r+1}}{(r+1)!}
$$
for an integer $k$ and a non-negative integer $r$, and
$$
P(X_{n+1} = k-r \mid X_n = k) = e^{-\lambda}
$$
for $r = 1$ and $0$ otherwise.
I am having trouble with proving that the chain is recurrent, I think I should use the fact that a chain is recurrent if and only if 
$$
\sum_{n=0}^\infty p_{ii}^{(n)}=\infty
$$
I am not sure how to do this, I tried finding the stationary distribution but this is very difficult.
Please help. 
 A: OKay have I have done this. I am not going to give you the solution, but I will offer you some hints: 
You attempted approach to think about $p_{ii}^{(n)}$ is correct
$p_{ii}^{(0)}=1$ - agreed?
what is $p_{ii}^n$? well I think this is the probability of Poisson process jumping $n$ steps in time interval $n$. well the number of jumps in a time interval length $n$ is distributed as ....? so this probability is .... ?
The term should be a nice form $\bigg(\dfrac{n}{e}\bigg)^n/n!$ stirling's formula tell you $n!$ is approximately what? so the term behaves like $\dfrac{1}{n^\alpha}$ for $\alpha = ? <1$ therefore the series diverges.
A: I think we can try to solve the recurrence relation. I don't know if this will work, but here is an idea:
Let $t_i$ be expected amount of time to arrive at $0$ given you are currently at state $i$,. 
$t_1 = p_{10} \times 1 + p_{11} (t_1+1) + p_{12} (t_2 +1) + p_{13} (t_3+1) + ... $
where $p_{ij}$ can be worked out and note $p_{ij} = p_{0,j-i}$ whenever $j\geq i$
get a system of these questions and see you can solve these. (though I hope there is an easier way) I will get back to you later. I need to do something for the next hours, sorry!
