A simple case of random walk

140 Views Asked by At

$\forall n \in \mathbb{N}$ we can either move from state $S_n$ to state $S_{n+1}$ with probability $p$ or to state $S_{n-1}$ with probability $q=1-p$. Also we move from state $S_0$ to state $S_{1}$ with probability $p$ or stay at state $S_{0}$ with probability $q=1-p$.

I need to figure out the probability of being in any state after $k \to \infty$ steps, but can't figure it out. Of course it is only possible when $q>p$.

A reference would be fine because I couldn't find any specific material about this particular case.

1

There are 1 best solutions below

0
On BEST ANSWER

This turns out to be a very straightforward recurrence problem. We'll presume that there's a stationary distribution $\left\{x_n\right\}$, where $x_n$ is the limiting probability of being in state $S_n$ after $k\to\infty$ many steps. For the moment, we'll leave $x_0$ as an unknown.

Since $x_0=qx_0+qx_1$ (the probability of staying in $S_0$ plus that of moving left from $S_1$), $x_1=\frac{p}{q}x_0$.

By induction, we'll show that in fact $x_n=\left(\frac{p}{q}\right)^nx_0$. Supposing this for $x_n$ and $x_{n-1}$, we'll prove that it holds for $x_{n+1}$. We know that $x_n=px_{n-1}+qx_{n+1}$. Solving for $x_{n+1}$, we find $$x_{n+1}=\frac{1}{q}x_n-\frac{p}{q}x_{n-1}=\frac{p^n}{q^{n+1}}x_0-\frac{p^n}{q^n}x_0=\frac{p^n}{q^{n+1}}\left(1-q\right)x_0=\left(\frac{p}{q}\right)^{n+1}x_0.$$

Now, we just ensure that the sum of the probabilities is 1.

$$\sum_{n=0}^{\infty}{x_n}=\sum_{n=0}^{\infty}{\left(\frac{p}{q}\right)^nx_0}=\frac{q}{q-p}x_0,$$ so we must have $x_0=\frac{q-p}{q}=1-\frac{p}{q}$.

Thus, the limiting probability of being in state $S_n$ is $x_n=\left(\frac{p}{q}\right)^n\left(1-\frac{p}{q}\right)$.