Prove that a random walk on $\mathbb{Z}_+\cup \{0\}$ is transient

Question

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.

Answer 1

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.

Answer 2

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.