Random Walk

Topics: Stochastic Process

---

(definition)

Let $\left\{X_n\mid n\in \mathbb{N}\right\}$ be a stochastic process with $S=\mathbb{Z}$ as its state set. Note that it has a discrete parameter set $\mathbb{N}=\{0,1,2,\dots \}$.

Let $X_0=a$ and let, for any $n\in \mathbb{N}$:

$$\mathbb{P}\left(X_{n+1}=j\mid X_n=i\right)=\{\begin{array}{ll}p& \text{if }j=i+1\\ q& \text{if }j=i-1\\ 0& \text{otherwise}\end{array}$$

We call such a stochastic process a random walk. When $X_0=a=0$, we call it a simple random walk.

Do note that these probabilities don’t depend on the specific $k$ and, as such, we say that they are homogeneous across time. A simple random walk is a Markov process.

We can deduce several formulae that make it easier to obtain the transition probabilities in a random walk.

Formal Definition §

(definition)

Let ${\epsilon }_1,{\epsilon }_2,\dots$ be a sequence of iid random variables such that, for any $k$:

• $\mathbb{P}({\epsilon }_k=1)=p$
• $\mathbb{P}({\epsilon }_k=-1)=q$

…where $p+q=1$.

With that, we define a random walk as the stochastic process $\left\{X_n\mid n\in \mathbb{N}\right\}$ where $X_0=a$ and, for $n\ge 1$:

$$X_n=X_0+{\epsilon }_1+{\epsilon }_2+\cdots +n$$

Recall that when $X_0=a=0$, we call it a simple random walk.

Symmetrical and Asymmetrical Walks §

(definition)

Recall that $p+q=1$. When $p=q=\frac{1}{2}$, we say that the random walk is symmetrical. When $p\ne q$, we say it is asymmetrical.

Expected Value and Variance §

(theorem)

For any integer $n\ge 0$, we have:

$$\begin{array}{rl}\mathbb{E}[X_n]& =n(p-q)\\ \mathrm{Var}(X_n)& =4npq\end{array}$$