One dimensional asymmetric Random Walk: Find the 2 step transition probability

Question

$P_{i,j} = p\delta_{i+1,j} + (1-p)\delta_{i-1,j}$

I want to find the 2 step transition probability $P_{i,j}^{(2)}$. So i used the Chapman-Kolmogorov equation:

$P_{i,j}^{(2)} = \sum_k P_{i,k}^{(1)}P_{k,j}^{(1)}$

$\implies = \sum_k [p\delta_{i+1,k} + (1-p)\delta_{i-1,k}] [p\delta_{k+1,j} + (1-p)\delta_{k-1,j}] $

but how do i simplify this to get to it being = $ p^2 \delta_{j,i+2} + 2p(1-p)\delta_{i,j} + (1-p)^2\delta_{j,i-2} $? Im not sure how to get to this step from the previous step.

Answer 1

You have four terms, each with two Kronecker symbols, and $k$ appears twice in each pair of Kronecker symbols. You can use that to perform the sum over $k$. For instance, the first term is

$$ \sum_kp\delta_{i+1,k}p\delta_{k+1,j}=p^2\sum_k\delta_{i+1,k}\delta_{k+1,j}=p^2\sum_k\delta_{i+2,k+1}\delta_{k+1,j}=p^2\delta_{i+2,j} $$

(assuming that $k$ runs over all of $\mathbb Z$, since you didn’t mention any boundaries).

Answer 2

The process you have is a binomial tree with upwards movement probability $p$ and downwards movement probability $1-p$. Starting from state $i$ at time $t=0$, at time $t=2$ one can only reach $\{i+2,i,i-2\}$. Therefore if $j=i+2$, we have $P_{i,j}=P(\textrm{up, up})=p^2$, if $j=i$ we have $P_{i,j}=P(\textrm{up, down)}+P(\textrm{down, up})=2p(1-p)$ and finally if $j=i-2$, then $P_{i,j}=P\textrm{(down, down)}=(1-p)^2$. This is what is expressed in the formula you wanted to prove.