Is there any simple formula for this probability distribution of random walk? Assume $\{S_n\}_{n\geq 0}$ transits as follows: 


*

*$S_0=0$,

*for $k\geq 1$, $P(S_{n+1}=k+1|S_n=k)=\alpha$, $P(S_{n+1}=k|S_n=k)=\beta$ and $P(S_{n+1}=k-1|S_n=k)=1-\alpha-\beta$, where $\alpha,\beta\in(0,1)$ and $1-\alpha-\beta>0$.

*for $k=0$, $P(S_{n+1}=1|S_n=k)=\alpha$ and $P(S_{n+1}=0|S_n=0)=1-\alpha$.
If $P_n$ is the distribution of $S_n$, is there any simple formula for $P_n$?
Thanks.
 A: I'm not sure there's a simple formulation for the distribution $P_n(k)$.
Let $P_n(k)$ have a $z$-transform defined by
$$
Q_n(z) = \sum_{k=0}^\infty P_n(k) z^k
$$
Let $\gamma = 1-\alpha-\beta$.  Then the distribution $P_{n+1}(k)$ is given by
$$
P_{n+1}(k) = \alpha P_n(k-1) + \beta P_n(k) + \gamma P_n(k+1), \qquad k \geq 1
$$
$$
P_{n+1}(0) = (\beta+\gamma) P_n(0) + \gamma P_n(1)
$$
Then
$$
\begin{align}
Q_{n+1}(z) & = \alpha zQ_n(z) + \beta Q_n(z) + \gamma P_n(0)
             + \frac{\gamma}{z} [Q_n(z) - P_n(0)] \\
           & = \Bigl(\alpha z+\beta+\frac{\gamma}{z}\Bigr) Q_n(z)
             + \Bigl(\gamma-\frac{\gamma}{z}\Bigr) P_n(0)
\end{align}
$$
Since $P_n(0) = Q_n(0)$, we can rewrite this slightly as
$$
\begin{align}
Q_{n+1}(z) & = \Bigl(\alpha z+\beta+\frac{\gamma}{z}\Bigr) Q_n(z)
             + \Bigl(\gamma-\frac{\gamma}{z}\Bigr) Q_n(0) \\
           & = \frac{(\alpha z^2+\beta z+\gamma) Q_n(z)
             + (\gamma z-\gamma) Q_n(0)}{z}
\end{align}
$$
However, I'm not sure one can do much with that recurrence.  One can get the equilibrium distribution $P_n(k) \to P(k)$, but that's more easily determined through the usual birth-death approach as
$$
P(k) = \Bigl(1-\frac{\alpha}{\gamma}\Bigr) \Bigl(\frac{\alpha}{\gamma}\Bigr)^k
$$
under the assumption that the system is ergodic (i.e., that $\alpha < \gamma$).
