Generalized Random Walk
Definition
A stochastic process $\left\{ X_{n} \right\}$ whose state space is the set of integers $\left\{ \cdots , -2 , -1, 0 , 1 , 2 , \cdots \right\}$ and starts from state $0$ is referred to as a generalized random walk if the probability of decreasing by $1$ in the next step is $p$, and the probability of increasing by $1$ is $(1-p)$.
Explanation
A random walk, which is a very simple example among stochastic processes, typically has equal probabilities of moving left or right. A generalized random walk simply varies these probabilities. It is not difficult to guess that if the probabilities of moving left or right are the same, the process would oscillate around the starting state $0$. However, if one side has a higher probability, it would diverge towards that side over time.
On the other hand, one can consider the gambler’s ruin problem as a case where the state space is finite.
Theorem
If $\displaystyle p = {{1} \over {2}}$, then state $0$ is recurrent, and if $\displaystyle p \ne {{1} \over {2}}$, then state $0$ is transient.
Proof
If $\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)}= \infty$, then $0$ is recurrent, and if $\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)} < \infty$, then $0$ is transient. Firstly, the probability of returning to state $0$ after an odd number of moves is certainly $0$, hence $$ p_{00}^{ ( 2n - 1 )} = 0 $$ Returning to state $0$ after $2n $ moves means moving left exactly $n$ times and right $n$ times, so $$\displaystyle p_{00}^{ ( 2n )} = \binom{2n}{n} p^{n} (1-p)^{n}$$ Now, it is sufficient to check whether this diverges or converges.
Stirling’s approximation: $$\lim_{n \to \infty} {{n!} \over { n^{ n + 1/2} e^{- n} \sqrt{ 2 \pi } }} = 1$$
Calculating factorials is hard, and since $n$ is assumed to be infinite, Stirling’s approximation is used. $$ \begin{align*} p_{00}^{ ( 2n )} \approx& {{ (2n)^{2n + 1/2} e^{-2n} \sqrt{ 2 \pi } } \over { \left( n^{n + 1/2} e^{-n} \sqrt{ 2 \pi } \right)^{2} }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ (2n)^{2n } \sqrt{2n} } \over { \left( n^{n } \right)^{2} n \sqrt{ 2 \pi } }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ 4^{n} n^{2n} \sqrt{ 2n } } \over { n^{2n} n \sqrt{ 2 \pi } }} \left( p ( 1 - p ) \right)^{n} \\ =& {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} \end{align*} $$
Case 1. $\displaystyle p = {{1} \over {2}}$
p-series test: $\displaystyle \sum _{ n=1 }^{ \infty }{ 1 \over {n^p} }$ converging is equivalent to $p>1$.
By the p-test, $\displaystyle \sum_{n=1}^{\infty} {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} = {{1} \over { \sqrt{ \pi } }} \sum_{n=1}^{\infty} {{1} \over { \sqrt{n} } }$ diverges, and state $0$ is recurrent.
Case 2. $\displaystyle p \ne {{1} \over {2}}$
Ratio test: for $\displaystyle r = \lim_{n \to \infty} { {|a_{n+1}|} \over {|a_{n}|} }$, if $r<1$ then $\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }}$ absolutely converges, if $r>1$ then $\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }}$ diverges.
$$\lim_{ n \to \infty } \left| {{ {{ \left( 4 p ( 1 - p ) \right)^{n+1} } \over { \sqrt{ \pi ( n + 1 ) } }} } \over { {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} }} \right| = \lim_{n \to \infty } {{ 4 p ( 1 - p ) } \over { \sqrt{ (n+1) / n } }} = 4p (1 - p) < 1$$ Therefore, by the ratio test, $$\sum_{n=1}^{\infty} {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }}$$ converges and state $0$ is transient.
■