The Simple Random Walk

Suppose that

X X 1 X 2

is a sequence of independent random variables, each taking values 1 and

1

with probabilities

p

and

1 p

respectively. In this section, we will study the partial sum process

Y Y 0 Y 1 Y 2

associated with

X

. Thus,

The sequence

Y

is the simple random walk with parameter

p

. At each step, our random walker moves either one unit to the right (with probability

p

) or one unit to the left (with probability

1 p

). The walker could accomplish this by tossing a coin with probability of heads

p

at each step, to determine whether to move right or move left. Other types of random walks are studied in the chapter on Markov Chains.

Let $μ$ and $σ$ denote the mean and standard deviation, respectively of a step $X$ . Show that

$μ 2 p 1$
$σ 2 4 p 1 p$

Let $I j 1 2 X j 1$ for $j$ . Show that $I j 1$ if $X j 1$ and $I j 0$ if $X j 1$ .

Hence,

I I 1 I 2

is a sequence of Bernoulli trials. In terms of the random walker,

I j

is the indicator variable for the event that the

i

step is to the right.

Let $Z n j 1 n I j$ for $n$ .

Show that $Y n 2 Z n n$ for $n$ .
Show that $Z n$ has the binomial distribution with trial parameter $n$ and success parameter $p$ .

In terms of the walker,

Z n

is the number of steps to the right in the first

n

steps.

Use the results of the previous exercise to show that $Y n$ has probability density function

Y n k n n k 2 p n k 2 1 p n k 2, k n n 2 n 2 n

Show that

$Y n n 2 p 1$
$Y n 4 n p 1 p$

The Symmetric Simple Random Walk

Suppose now that

p 1 2

. In this case,

Y Y 0 Y 1

is called the symmetric, simple random walk. The symmetric random walk can be analyzed using some special and clever combinatorial arguments.

Show that the random vector $X n X 1 X 2 X n$ is uniformly distributed on $S 11 n$ , and therefore

X n A A 2 n, A S

Show that $Y n$ has probability density function

Y n k n n k 2 1 2 n, k n n 2 n 2 n

Show that $Y n$ has mean and variance given by

$Y n 0$
$Y n n$

In the random walk simulation, select the final position. Vary the number of steps and note the shape and location of the probability density function and the mean/standard deviation bar. For selected values of the parameter, run the simulation 1000 times, updating every 10 runs. Note the apparent convergence of the empirical density and moments to the true density and moments.

In the random walk simulation, select the final position and set the number of steps to 50. Run the simulation 1000 times, updating every 10 runs. Compute and compare the following:

$6 Y 50 10$
The relative frequency of the event $6 Y 50 10$
The normal approximation to $6 Y 50 10$

The Maximum Position

Consider again the simple, symmetric random walk. Let

M n Y 0 Y 1 Y n

, the maximum position during the first

n

steps. Note that

M n

takes values in the set

01 n

. The distribution of

M n

can be derived from a simple and wonderful idea known as the reflection principle.

Show that $M n m$ if and only if $Y i m$ for some $i 01 n$ .

Suppose that $k m n$ . Show that for each path that satisfies $M n m$ and $Y n k$ there is another path that satisfies $Y n 2 m k$ . Hint: The second path is obtained from the first path by reflecting in the line $y m$ , after the first path hits $m$ .

Use the results of the previous two exercises and the fact that the paths are equally likely to show that

M n m Y n k Y n 2 m k, k m n

Use the result of the previous exercise to show that

M n m Y n k Y n 2 m k Y n 2 m 1 k, k m n

Use the result of the previous exercise to show that for $n$ and $m 01 n$

M n m Y n m n m n 2 1 2 n m and n have the same parity (both even or both odd) Y n m 1 n m n 1 2 1 2 n m and n have opposite parity (one even and one odd)

In the random walk simulation, select the maximum value variable. Vary the number of steps and note the shape and location of the density function and the mean/standard deviation bar. Now set the number of steps to 30 and run the simulation 1000 times with an update frequency of 10. Note the apparent convergence of the relative frequency function and empirical moments to the true density function and moments.

Show that for any $n$ , the probability density function of $M n$ is decreasing.

The result in Exercise 17 is a bit surprising; in particular, the single most likely value for the maximum is 0!

Explicitly compute the probability density function, mean, and standard deviation of $M 5$ .

A fair coin is tossed 10 times. Find the probability that the difference between the number of heads and the number of tails is never greater than 4.

The Last Visit to 0

Consider again the simple, symmetric random walk. Our next topic is the last visit to 0 during the first

2 n

steps:

Note that since visits to 0 can only occur at even times,

L 2 n

takes the values in the set

02 2 n

. This random variable has a strange and interesting distribution known as the discrete arcsine distribution. Along the way to our derivation, we will discover some other interesting results as well.

Show that

L 2 n 2 k Y 2 k 0 Y 2 k 1 0 Y 2 n 0, k 01 n

Use independence, symmetry and the result of the previous exercise to show that

L 2 n 2 k Y 2 k 0 Y 1 0 Y 2 0 Y 2 n 2 k 0, k 01 n

We know the first factor on the right from the distribution of

Y 2 k

. Thus, we need to compute the second factor, the probability that our random walk never returns to 0 during a time interval.

Use results for the maximum position to show that

Y 1 0 Y 2 0 Y 2 j 0 M 2 j 0 2 j j 1 2 2 j

Use symmetry (which is just the reflection principle at $y 0$ ), to show that

Y 1 0 Y 2 0 Y 2 n 0 2 n n 1 2 2 n

Show that $Y 1 0 Y 2 0 Y 2 j 0 Y 1 1 Y 2 1 Y 2 j 1$

Use independence, symmetry, and the result of the previous exercise to show that

Y 1 0 Y 2 0 Y 2 j 0 Y 1 1 Y 1 0 Y 2 0 Y 2 j 1 0

Show that $Y 2 j 1 0$ implies $Y 2 j 0$ .

Use the result of the previous exercises to show that

Y 1 0 Y 2 0 Y 2 j 0 2 j j 1 2 2 j 1

Use symmetry and the result of the pervious exercise to show that

Y 1 0 Y 2 0 Y 2 j 0 2 j j 1 2 2 j

Use the result of Exercise 22 and Exercise 28 to show that the probability density function of $L 2 n$ is

L 2 n 2 k 2 k k 2 n 2 k n k 1 2 2 n, k 01 n

In the random walk simulation, choose the last visit to 0 and then vary the number of steps with the scroll bar. Note the shape and location of the density function and the mean/standard deviation bar. For various values of the parameter, run the simulation 1000 times with an update frequency of 10 and watch the apparent convergence of the empirical density function and moments to the true probability density function and moments.

Show that

$L 2 n 2 k L 2 n 2 n 2 k$ so the probability density function is symmetric about $n$ .
$L 2 n 2 j L 2 n 2 k$ if and only if $j k$ and $2 k n$ , so the probability density function is $u$ -shaped.

In particular, 0 and

2 n

are the most likely values. The arcsine distribution is quite surprising. Since we are tossing a fair coin to determine the steps of the walker, you might easily think that the random walk should be positive half of the time and negative half of the time, and that it should return to 0 frequently. But in fact, the arcsine law implies that with probability

1 2

, there will be no return to 0 during the second half of the walk, from time

n 1

2 n

, regardless of

n

, and it is not uncommon for the walk to stay positive (or negative) during the entire time from 1 to

2 n

Explicitly compute the probability density function, mean, and variance of $L 10$ .

The Ballot Problem and the First Return to Zero

The Ballot Problem

Suppose that in an election, candidate

A

receives

a

votes and candidate

B

receives

b

votes where

a b

. Assuming a random ordering of the votes, what is the probability that

A

is always ahead of

B

in the vote count? This is an historically famous problem known as the Ballot Problem, that was solved by Joseph Louis Bertrand in 1887. The ballot problem is intimately related to simple random walks.

Comment on the validity of the assumption that the voters are randomly ordered for a real election.

The ballot problem can be solved by using a simple conditional probability argument to obtain a recurrence relation. Let

f a b

denote the probability that

A

is always ahead of

B

in the vote count.

Condition on the candidate that receives the last vote to show that

f a b a a b f a 1 b b a b f a b 1

Use the initial condition $f 10 1$ and induction on the number of votes $n a b$ to show that

f a b a b a b

In the ballot experiment, vary the parameters $a$ and $b$ and note the change the ballot probability. For selected values of the parameters, run the experiment 1000 times with and update frequency of 10 and note the apparent convergence of the relative frequency to the true probability.

In an election for mayor of a small town, Mr. Smith received 4352 votes while Ms. Jones received 7543 votes. Compute the probability that Jones was always ahead of Smith in the vote count.

Relation to Random Walks

Given $Y n k$ , show that

There are $n k 2$ steps to the right and $n k 2$ steps to the left.
All possible orderings of the steps to the right and the steps to the left are equally likely.

Use the previous exercise and the ballot probability to show that for $k 0$ ,

Y 1 0 Y 2 0 Y n 1 0 Y n k k n

In the ballot experiment, vary the parameters $a$ and $b$ and note the change the ballot probability. For selected values of the parameters, run the experiment 1000 times with an update frequency of 10 and note the apparent convergence of the relative frequency to the true probability.

An American roulette wheel has 38 slots; 18 are red, 18 are black, and 2 are green. Fred bet $1 on red, at even stakes, 50 times, winning 22 times and losing 28 times. Find the probability that Fred's net fortune was always negative.

The Distribution of the First Zero

Consider again the simple random walk with parameter

p

, as in the last subsection. Let

T

denote the time of the first return to 0:

Note that returns to 0 can only occur at even times; it may also be possible that the random walk never returns to 0. Thus,

T

takes values in the set

24

Show that

T 2 n T 2 n Y 2 n 0 T 2 n Y 2 n 0 Y 2 n 0

Use the ballot problem to show that

T 2 n Y 2 n 0 1 2 n 1

Use the results of the previous two exercises to show that

T 2 n 2 n n 1 2 n 1 p n 1 p n, n

Fred and Wilma are tossing a fair coin; Fred gets a point for each head and Wilma gets a point for each tail. Find the probability that their scores are equal for the first time after $n$ tosses, for each $n 246810$ .

6. The Simple Random Walk

The Basic Process

The Symmetric Simple Random Walk

The Maximum Position

The Last Visit to 0

The Ballot Problem and the First Return to Zero

The Ballot Problem

Relation to Random Walks

The Distribution of the First Zero