Which states are recurrent and which states are transient? Consider 
$$P = 
\left(
\begin{array}{ccccc}
 p_0 & 1-p_0  & 0 & 0 & \cdots \\
 p_1 & 0 & 1-p_1  & 0 & \cdots \\
 p_2 & 0  & 0 & 1-p_2 & \cdots \\
 \vdots & \vdots & \vdots & \vdots & \vdots
\end{array}
\right)$$
It is obvious all states are recurrent from the graph but how to prove it in the formula? something like show f(00)=1
 A: First off, this chain is irreducible, so either every state is recurrent or every state is transient.
Second, the probability that the chain started at $0$ reaches state $n$ before its next return to $0$ is $\prod_{i=0}^{n-1} (1-p_i)$. Thus the probability that it diverges to infinity before returning to $0$ is $\prod_{i=0}^\infty (1-p_i)$. Thus everything hinges on whether this product is $0$ or not. As usual with infinite products, we tend to study them by looking at their logarithm, so you are looking at whether $\sum_{i=1}^\infty \ln(1-p_i)$ is infinite or not. By a Taylor expansion argument, this is the same as asking whether $\sum_{i=1}^\infty p_i=\infty$ or not. If this sum is infinite, then the chain is not recurrent (because it will eventually fail to return to $0$ with probability 1, since it will get "infinitely many attempts" at a Bernoulli trial). If the sum is finite, then the chain is recurrent.
In terms of the $p_{i,i}$ and $f_{i,i}$ notation that you are acquainted with, you can calculate $f_{0,0}^{(n)}=p_{n-1} \prod_{j=0}^{n-2} (1-p_j)$, since you return to $0$ from $0$ in exactly $n$ steps if and only if you move to the right exactly $n-1$ times and then jump back to $0$. 
To continue in this method, if you introduce $q_j=1-p_j$ then you are now looking at $\sum_{n=1}^N (1-q_{n-1}) \prod_{j=0}^{n-2} q_j=(1-q_0)+(1-q_1)q_0+(1-q_2)q_0 q_1+\dots$ which telescopes, becoming $1-\prod_{j=0}^{N-1} q_j$, so again the question of recurrence comes down to whether $\prod_{j=0}^\infty q_j=0$ or not. It is just that in the previous way of looking at the problem it was easier to compute $1-\sum_{k=1}^n f_{0,0}^{(k)}$ (i.e. the probability that the first return to $0$ doesn't occur in the first $n$ time steps) "by inspection", rather than actually evaluating the terms and summing them. (This is basically the same reason why the CDF of the geometric distribution is simpler than the PMF.)
A: If $\pi$ is a stationary distribution for $P$, that is, $\pi P=\pi$, then we must have
\begin{align}
\pi_0 &= \sum_{i=0}^\infty p_i\pi_i\tag1\\
\pi_i &= (1-\pi_{i-1})\pi_{i-1},\ i\geqslant 1\tag2
\end{align}
Clearly $P$ cannot have a stationary distribution if $\sum_{i=0}^\infty p_i=\infty$. If the sum is finite, use the recurrence from $(2)$ to find an expression for $\pi_i$ in terms of $\pi_0$, then use $(1)$ to find $\pi_0$ explicitly and hence the rest of the $\pi_i$.
