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.

  • $\begingroup$ What kind of conditions are you looking for? $\endgroup$ – Colin McQuillan Apr 13 '13 at 11:32
  • $\begingroup$ I think the only way to have an influence on the problem is via the distribution of $X_i$. $\endgroup$ – 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's start with some boundary theory for Markov chains.

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).$$

  • $\begingroup$ 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? $\endgroup$ – madison54 Apr 15 '13 at 15:57
  • $\begingroup$ @madison54 I've added a footnote to explain the equation better. Perhaps later I will add another to explain the inequality. $\endgroup$ – user940 Apr 15 '13 at 18:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.