A person is standing on $0$ on the $x$-axis at $t=0$. After each second, the person can either move one unit to the right (with probability $a$), move one unit to the left (with probability $b$), or stay where he is (with probability $1-a-b$). Find the probability that, at time $T$, the person is at $+d$ on the $x$-axis?
My try :
Let $P(x,t)$ be the probability that the person is at $x$ at time $t$. Then the following holds good : $$P(x,t)=a\cdot P(x-1,t-1)+b\cdot P(x+1,t-1)+(1-a-b)\cdot P(x,t-1)$$
With the initial conditions $P(0,0)=1$, $P(1,0)=0$ and $P(0,1)=1-a-b$.
How do I solve this recurrence relation using a generating function? I know how to solve one variable recursions using a generating function, but what about this?
Please help me out. Thank you.
The generating function approach is to consider $G(s,t)=\sum\limits_xP(x,t)s^x$ for every $t\geqslant0$ and to note that $G(s,0)=1$ and $G(s,t+1)=(as+bs^{-1}+1-a-b)\cdot G(s,t)$ for every $t\geqslant0$ hence $$G(s,t)=(as+bs^{-1}+1-a-b)^t.$$ Each $P(x,t)$ is the coefficient of $s^x$ in $G(s,t)$. Various formulas for $P(x,t)$ as a sum can be deduced, for example, introducing $c=ab(1-a-b)^{-2}$, for every $|x|\leqslant t$, $$P(x,t)=a^x(1-a-b)^{t-x}\sum_j\frac{t!\,c^j}{j!(j+x)!(t-x-2j)!}\mathbf 1_{0\leqslant x+j\leqslant x+2j\leqslant t}.$$