Construction of positive recurrent Markov chain

Let $\{X_i\}_{i\geq 1}$ be i.i.d. with values in $\mathbb N_0$. Define a Markov chain via the following transition matrix:

$$p(0,n) = \mathbb P(X_1 = n-1) \qquad p(m,n) = \mathbb P\left(\sum_{k=1}^m X_k = n\right)$$

Under what conditions is this Markov chain positive recurrent?

I tried to find conditions under which the chain is irreducible and has an invariant distribution, but couldn't pin down the calculation. It would then follow that it is positive recurrent.

• What kind of conditions are you looking for? – Colin McQuillan Apr 13 '13 at 11:32
• I think the only way to have an influence on the problem is via the distribution of $X_i$. – madison54 Apr 13 '13 at 13:30

Your Markov chain is the total population of a branching process with offspring distribution $X$, except that when the population goes extinct (hits state 0) it regenerates a random number of ancestors who again start to grow family trees. Standard results on the extinction of branching processes gets you pretty far.

Let's assume that $\mathbb{P}(X=0)>0$, $\mathbb{P}(X=1)>0$, and $\mathbb{P}(X>1)>0$ so that the chain is irreducible on the state space $\mathbb N_0$.

When $\mathbb{E}(X)<1$, then the expected time to extinction starting with one individual is finite; $\mathbb{E}_1(T_0)<\infty$. Then \begin{eqnarray*} \mathbb{E}_0(T_0)&=&1+\sum p(0,n)\,\mathbb{E}_n(T_0)\\[5pt] &\leq&1+\sum p(0,n)\, n \,\mathbb{E}_1(T_0)\\[5pt] &=&1+(\mathbb{E}(X)+1)\, \mathbb{E}_1(T_0)<\infty. \end{eqnarray*} Therefore the state 0 is positive recurrent and hence the whole chain.

If $\mathbb{E}(X)>1$, the chain is transient. The population will grow to $\infty$ with probability one.

If $\mathbb{E}(X)=1$, extinction is guaranteed so the chain is recurrent. When $\mathbb{E}(X^2)<\infty$ the chain is null since $\mathbb{E}_1(T_0)=\infty$. I'm not sure about the case $\mathbb{E}(X)=1$ and $\mathbb{E}(X^2)=\infty$.

Footnote 1: Where does the equation come from?

Let $(X_n)$ be a Markov chain with state space $\cal S$ and let $B\subset {\cal S}$. Define $$V_B=\inf(n\geq 0: X_n\in B),\qquad T_B=\inf(n\geq 1: X_n\in B),$$ and $$h(x)=\mathbb{E}_x(V_B),\qquad f(x)=\mathbb{E}_x(T_B).$$ Notice that $h(x)=f(x)$ for $x\notin B$. Using the shift operator we write $T_B=1+V_B\circ\theta_1$ so $$f(x)=\mathbb{E}_x(1+V_B\circ\theta_1)=1+\mathbb{E}_x(h(X_1)).$$
In your problem (with $B=\{0\}$), since there are no transitions from $0$ to itself, we get $$\mathbb{P}_0(f(X_1)=h(X_1))=1,$$ and hence $$f(0)=\mathbb{E}_0(T_0)=1 +\mathbb{E}_0(f(X_1))=1 +\sum_n p(0,n)\,\mathbb{E}_n(T_0).$$
• Thanks! Where does the $1$ come from in these equations and why is $\mathbb E_n(T_0)\leq n\mathbb E_1(T_0)$, how general is that inequality? – madison54 Apr 15 '13 at 15:57