Consider the random walk on $\mathbb{Z}=\{\ldots,-2,-1,0,1,2,\ldots\}$ with transition probabilities $$ p_{i,j}= \begin{cases} p & \text{if } j=i+1,\\ 1-p &\text{if } j=i-1,\\ 0 &\text{otherwise} \end{cases} $$ Find $p_{i,j}^{(n)}=P(X_n=j \mid X_0=i)$ and deduce that the random walk is irreducible.
Should I derive a general formula similar to a binomial model with recombining trees and then prove it by induction or what? Can anyone give me a hint?
Denote this Markov chain is $\{X_{n}, n\in\mathbb{N}\}$.
Suppose the Markov chain is irreducible. Then all states communicate with each other. So $1-p=P_{i,i-1}>0$ and $p=P_{i,i+1}>0$. Thus, $p\in(0,1)$.
Suppose the $p\in(0,1)$. For any state $x, y\in \mathbb{Z}$ with $x>y$, we denote $n=x-y$. Note that for some $n\geq 0$, $$P^{n}_{xy}=\mathbb{P}(X_n=y\mid X_{0}=x)\geq \mathbb{P}(X_{0}=x, X_1=x-1, X_2=x-2, \cdots, X_n=y)=(1-p)^n>0$$
Similarly, $$P^{n}_{yx}=\mathbb{P}(X_n=x\mid X_{0}=y)\geq \mathbb{P}(X_{0}=y, X_1=y+1, X_2=y+2, \cdots, X_n=x)=p^n>0.$$
So all states clearly communicate with each other which implies that this Markov chain is irreducible.