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.
 A: 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. 
A: 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.
