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

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.

-
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? –  catamite 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
add comment

## 2 Answers

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.

-
+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
add comment

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.

-
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
add comment