Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Prove that a random walk on $\mathbb{Z}_+ \cup \{0\}$ is transient with $p_{i,i+1}=\frac{i^2+2i+1}{2i^2+2i+1}$ and $p_{i,i-1}=\frac{i^2}{2i^2+2i+1}$.

So since this Markov chain has only a single communicating class we only need prove that $0$ is a transient state. There really isn't much other theory to go off of. I'm basically just trying to find a general formula for $p_{0,0}^{(n)}$ so that I can show that the infinite series $\sum p_{0,0}^{(n)} <\infty$. But I cannot for the life of me come up with a combinatorial formula to find $p_{0,0}^{(n)}$. Can anyone help me come up with this formula? Thanks.

share|cite|improve this question
Did you try using Kolmogorov forward equations to find $\pi_k$ instead? – Alex Apr 26 '13 at 2:26
@Alex I'm not sure I have those at my disposal, could you expand on what those are? – Thoth Apr 26 '13 at 2:46
If all states are transient then $\pi_k =0 \ \forall \ k$. Kolmogorov forward equations are solved using the transition probabilities you have – Alex Apr 26 '13 at 3:09
up vote 2 down vote accepted

An irreducible Markov chain is recurrent if and only if every non-negative, superharmonic function $f$ is constant. Here is a typical non-negative, superharmonic function $f$: select a state, say $0$ and define $f(x)=\mathbb{P}_x(T<\infty)$ where $T:=\inf(n\geq 0: X_n=0)$ is the hitting time of $0$. We want to figure out whether this function is constant or not.

Your Markov chain has extra structure that allows us to calculate this function explicitly. For each $i> 0$, define the ratio $r_i=p_{i,i-1}/p_{i,i+1}$ and define the following function using products of ratios: $$f_z(x)={\sum_{y=x}^z r_{1}\cdots r_y \over \sum_{y=0}^z r_{1}\cdots r_y}.$$ Here $r_{1}\cdots r_0$ is the empty product, equal to 1.

Our function $f$ is the limit of $f_z$ as $z\to\infty$. As Did points out, the reason for the pointwise convergence is that $f_z(x)$ is the probability that the chain hits state $0$ before state $z+1$, starting at $x$.

If $\sum_{y=0}^\infty (r_{1}\cdots r_y)=\infty$, we have $f(x)\equiv 1$ and the chain is recurrent.

If $\sum_{y=0}^\infty (r_{1}\cdots r_y)<\infty$, then $f$ is the non-constant function $$ f(x)={\sum_{y=x}^\infty r_{1}\cdots r_y \over \sum_{y=0}^\infty r_{1}\cdots r_y}.$$ and the chain is transient. The function $f$ is non-constant since $f(x)\to0$ as $x\to\infty$.

In your particular problem, $r_i=i^2/(i+1)^2$ so the products of ratios cancel nicely giving $r_{1}\cdots r_y=1/(y+1)^2$. Since $\sum_{y=0}^\infty 1/(y+1)^2<\infty$ we see that the chain is transient.

share|cite|improve this answer
+1. And a simple reason why $f_z\to f$ pointwise when $z\to\infty$ is that $f_z(x)$ is the probability starting from $x$ to hit $0$ before $z$. – Did Apr 27 '13 at 12:49
@Did Thanks. I will incorporate your comment into the answer. – Byron Schmuland Apr 27 '13 at 12:54
My pleasure. $ $ – Did Apr 27 '13 at 12:55

I'll show you why a similar problem is transient by showing that stationary distribution doesn't exist. Take for example $p_{k-1,k}=\frac{3}{4}, \ p_{k,k-1} = \frac{1}{4}$. This is a reversible MC, just like in your case (the rate of inflow in the state is equal to the rate of outflow), so we can use the detailed balance equation: $$ \frac{3}{4} \pi_{k-1} = \frac{1}{4} \pi_{k}\\ \pi_{k} = 3 \pi_{k-1}=\cdots =3^k \pi_0 $$ Since the standardizing condition is $\sum_{k} \pi_k = 1$, we sum on both sides and get $\pi_0 = \frac{1}{\sum_{k=0}^{\infty}3^k}$, which diverges, so $\pi_0$ and hence $\pi_k$ do not exist.

share|cite|improve this answer
This argument only shows that the chain is null. It could be null recurrent, for instance, if you replace $3/4$ and $1/4$ by $1/2$ above. – Byron Schmuland Apr 26 '13 at 22:32
OK, I agree. Can this answer be extended to incorporate it? – Alex Apr 27 '13 at 0:18

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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