logo

Generalized Random Walk 📂Probability Theory

Generalized Random Walk

Definition

20190122_111840.png

A stochastic process {Xn}\left\{ X_{n} \right\} whose state space is the set of integers {⋯ ,−2,−1,0,1,2,⋯ }\left\{ \cdots , -2 , -1, 0 , 1 , 2 , \cdots \right\} and starts from state 00 is referred to as a generalized random walk if the probability of decreasing by 11 in the next step is pp, and the probability of increasing by 11 is (1−p)(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 00. 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 p=12\displaystyle p = {{1} \over {2}}, then state 00 is recurrent, and if p≠12\displaystyle p \ne {{1} \over {2}}, then state 00 is transient.

Proof

If ∑n=1∞p00(n)=∞\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)}= \infty, then 00 is recurrent, and if ∑n=1∞p00(n)<∞\displaystyle \sum_{n=1}^{\infty} p_{00}^{(n)} < \infty, then 00 is transient. Firstly, the probability of returning to state 00 after an odd number of moves is certainly 00, hence p00(2n−1)=0 p_{00}^{ ( 2n - 1 )} = 0 Returning to state 00 after 2n2n moves means moving left exactly nn times and right nn times, so p00(2n)=(2nn)pn(1−p)n\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→∞n!nn+1/2e−n2π=1\lim_{n \to \infty} {{n!} \over { n^{ n + 1/2} e^{- n} \sqrt{ 2 \pi } }} = 1

Calculating factorials is hard, and since nn is assumed to be infinite, Stirling’s approximation is used. p00(2n)≈(2n)2n+1/2e−2n2π(nn+1/2e−n2π)2(p(1−p))n=(2n)2n2n(nn)2n2π(p(1−p))n=4nn2n2nn2nn2π(p(1−p))n=(4p(1−p))nπn \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. p=12\displaystyle p = {{1} \over {2}}

p-series test: ∑n=1∞1np\displaystyle \sum _{ n=1 }^{ \infty }{ 1 \over {n^p} } converging is equivalent to p>1p>1.

By the p-test, ∑n=1∞(4p(1−p))nπn=1π∑n=1∞1n\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 00 is recurrent.

Case 2. p≠12\displaystyle p \ne {{1} \over {2}}

Ratio test: for r=lim⁡n→∞∣an+1∣∣an∣\displaystyle r = \lim_{n \to \infty} { {|a_{n+1}|} \over {|a_{n}|} }, if r<1r<1 then ∑n=1∞an\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }} absolutely converges, if r>1r>1 then ∑n=1∞an\displaystyle \sum _{ n=1 }^{ \infty }{ { a }_{ n }} diverges.

lim⁡n→∞∣(4p(1−p))n+1π(n+1)(4p(1−p))nπn∣=lim⁡n→∞4p(1−p)(n+1)/n=4p(1−p)<1\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, ∑n=1∞(4p(1−p))nπn\sum_{n=1}^{\infty} {{ \left( 4 p ( 1 - p ) \right)^{n} } \over { \sqrt{ \pi n } }} converges and state 00 is transient.

■

See also