Random walk from state $i$ to state $j$

Question

If the particle is at state $i$, then the probability that it will be at state $j$ after $n$ transitions is the probability that $(n − i + j)/2$ of these steps are to the right and $n − [(n − i + j)/2] = (n + i − j)/2$ are to the left.

How do we get the formula $(n − i + j)/2$?

Answer 1

Suppose a particle on the number line moves in $n$ unit steps (each step is $\pm 1$) from position $i$ to position $j$, where $i,j$ are integers.

Let $L$ be the number of steps to the left, and let $R$ be the number of steps to the right.

Then for fixed $i,j,n$, we get the system \begin{cases} R+L=n\\[4pt] i+(R-L)=j\\[4pt] \end{cases} of $2$ equations in the $2$ unknowns $R,L$.

Solving the system for $R,L$ yields the fornulas in question.

Answer 2

I will assume that each transition is one step to the right or one step to the left. Suppose there are $k$ steps to the right. Then there are $n-k$ steps to the left. Starting from $i$ you will end up at $i+k-(n-k)$. We want this to be equal to $j$. Solve the equation $i+k-(n-k)=j$ to find $k$.