# Lesson 31 Random Walk

## Theory

The random walk (also known as the “drunkard’s walk”) is an example of a random process evolving over time, like the Poisson process (Lesson 17).

The setup for the random walk is as follows. A drunk man is stumbling home from a bar. Because of his inebriated state, each step he takes is equally likely to be one step forward or one step backward, independent of any other step.

In other words, the $$i$$th step is a random variable $$Z_i$$, with p.m.f.

$\begin{array}{r|cc} z & -1 & 1 \\ \hline f(z) & 0.5 & 0.5 \end{array}$

and the $$Z_i$$s are independent.

The drunkard’s position after $$n$$ steps is $X_n = Z_1 + Z_2 + \ldots + Z_n.$ (We assume that he starts at the origin $$X_0 = 0$$.)

Shown below are three possible realizations of the random walk. A realization of a random process over time is called a sample path. We plot the three sample paths below, each of which shows the position of the drunkard $$X_n$$ as a function of $$n$$. Although all three sample paths start at 0 at $$n=0$$, they diverge very quickly. ## Essential Practice

Answer the following questions about the random walk. You should use linearity of expectation and properties of covariance as much as possible.

1. What is the distribution of $$X_2$$, the drunkard’s position after just $$2$$ steps? (This is not a named distribution. Just make a table showing the possible values and their probabilities.)
2. Calculate $$E[Z_i]$$ and $$\text{Var}[Z_i]$$.
3. Calculate $$E[X_3]$$ and $$\text{Var}[X_3]$$.
4. Consider $$X_3$$ and $$X_5$$. Do you think their covariance is positive, negative, or zero? Calculate $$\text{Cov}[X_3, X_5]$$.