I have the next problem:
Consider a homogeneous Markov chain $\{X_n: n = 0,1,2, ... \} $ with state space $E = \{0,1,2, ... \} $, with the following transition probabilities where $ 0 <\theta <$ 1
$$p_{ij} = \begin{cases} \theta &\mbox{if } j=i+1\\ 1-\theta&\mbox{if } j=i\\ 0 & \mbox{otherwise.} \end{cases}$$
and initial distribution $v_0(0)=1$, ie starts in the zero state with probability 1.
Explicitly calculate the probability of transition in $ m $ steps $ p_ {ij } $ for any state $ i, j \ in E $.
This is my solution
Let the powers of the transition matrix:
$$P=\left[\begin{array}{ccccc} 1-\theta & \theta & 0 & 0 & ...\\ 0 & 1-\theta& \theta & 0 &...\\ 0 & 0 & 1-\theta& \theta & ...\\ \colon& \colon &\colon &\colon & \ddots \end{array}\right]$$
and :
$$P^2=\left[\begin{array}{cccccc} (1-\theta)^2 & 2\theta(1-\theta) & \theta^2 & 0 & 0 & ...\\ 0 & (1-\theta)^2 & 2\theta(1-\theta) & \theta^2 & 0 & ...\\ 0 & 0 & (1-\theta)^2 & 2\theta(1-\theta) & \theta^2 & ...\\ \colon & \colon &\colon & \colon & \colon & \ddots \end{array}\right]$$
$$P^3=\left[\begin{array}{cccccc} (1-\theta)^3 & 3\theta(1-\theta)^2 & 3\theta^2(1-\theta) &\theta^3 & 0 & ...\\ 0 & (1-\theta)^3 & 3\theta(1-\theta)^2 & 3\theta^2(1-\theta) & \theta^3 & ...\\ 0 & 0 & (1-\theta)^3 & 3\theta(1-\theta)^2 & 3\theta^2(1-\theta) & ...\\ \colon & \colon &\colon & \colon & \colon & \ddots \end{array}\right]$$
and we note that each has a binomial coefficient Newton with $x=1-\theta $ and $y=\theta $
$$1=(x+y)^m= \sum_{k=0}^m {m \choose k}(1-\theta)^{m-k}\theta^k = (1-\theta)^m+...+{m \choose j}(1-\theta)^{m-j}\theta^j+...+\theta^m$$ Then the transition probabilities in $ m $ steps are:
$$p_{ij}^{(m)} = \begin{cases} (1-\theta)^m &\mbox{if } j=i\\ {m \choose j}(1-\theta)^{m-j}\theta^j &\mbox{if } i<j<i+m\\ \theta^m &\mbox{if } j=i+m\\ 0 &\mbox{otherwise.} \end{cases}$$
am I correct?
Not quite correct. All OK until you translate your binomial expansion into your answer: $k$ should translate to $j-i$ instead of $j$. Also, cases $1$ and $3$ are just instances of case $2$, so we can simplify accordingly.
$$p_{ij}^{(m)} = \begin{cases} {m \choose j-i}(1-\theta)^{m-j+i}\theta^{j-i} &\mbox{if } i \leq j\leq i+m\\ 0 &\mbox{otherwise.} \end{cases}$$