This lecture introduces the simple symmetric random walk.

1    Simple symmetric random walk

Take X1 , X2 , ... iid Rademacher random variables (also called symmetric Bernoulli) i.e. P(Xi  =

1) = P(Xi  = −1) = 0.5 for each i. Fix S0  and define Sn  = S0  + ∑ Xi . Then Sn  denotes the

Head and losing $1 for Tail.

1.1    Hitting times

Assume for simplicity, S0   =  0.  Then the wealth at time n, Sn   =  ∑ Xi .  We can ask the

• What is the probability that the gambler is up by $200 before being down by $100?

•  Suppose the gambler stops playing once she is up by $200 or down by $100.  How many rounds does she expect to play?

•  Suppose the gambler stops once she is down by $100. What is the probability that she will stop? How many rounds does she expect to play?

• Is the fairness of the coin crucial in answering these questions?

We will now see that there is a very clean machinery to answer these questions, namely the concept of hitting times. Fix integers A, B > 0 and define

TA, −B  := min{n ≥ 0 : Sn  = A or Sn  = −B}

so TA, −B  is the first time the random walk (that is, the gambler) hits A or B .  Also define, for −B  ≤ k  ≤ A, f (k) = P(ST   = A|S0   = k) i.e.  the chance that the gambler reaches A before hitting −B, starting from k .

•  (Question 1) A = 200, B = 100. Want f (0).

•  (Question 2) A = 200, B = 100. Want E(T200, −100 |S0  = 0).

Note that in the definition of f (·), we implicitly assumed that T is a well-defined number i.e. T < ∞, which in turn is equivalent to saying the random walk hits A or −B at some finite time, since otherwise ST  is not defined. In fact, P(T = ∞|S0  = 0) = 0. What does this mean? Since the RW has step size 1, avoiding both A and −B means the RW is somehow constrained in the set {−B + 1, ..., A − 1}. This seems strange, because just when the walk hits −B + 1 or A − 1, the next coin toss somehow magically becomes 1 and −1 respectively to avoid −B and A. This seems

absurd. We will see a simple method to prove that P(T = ∞|S0  = 0) = 0.

Theorem 1.1. P(T = ∞|S0  = 0) = 0.

Proof.  Let g(k) = P(T = ∞|S0   = k) for −B  ≤ k  ≤ A. We consider the following first step decomposition:

g(k) = P(T = ∞, X1  = 1|S0  = k) + P(T = ∞, X1  = −1|S0  = k)

= P(T = ∞|X1  = 1, S0  = k)P(X1  = 1|S0  = k) + P(T = ∞|X1  = −1, S0  = k)P(X1  = −1|S0  = k)

= P(T = ∞|S1  = k + 1) ×  + P(T = ∞|S1  = k − 1) × 

=  (g(k + 1) + g(k − 1))

Note that g(A)  =  0, g(−B)  =  0.  Let g ∗ =  maxk g(k) and let k ∗ be a value of k for which g(k∗ ) = g ∗ . Then as g(k∗ ) is an average of g(k∗ + 1) and g(k∗ − 1), both of these two must be equal to g ∗ as well.  By induction, it follows that for all −B  ≤ k  ≤ A, g(k)  =  g ∗ , but since g(−B) = g(A) = 0, we must have g ∗ = 0 implying all g(k) = 0 for −B ≤ k ≤ A. In particular,

g(0) = 0, which is what we wanted to prove.

Now, we derive an expression for f (k).

k + B

Theorem 1.2. For −B ≤ k ≤ A, f (k) =

Proof.  We again use the first step decomposition.

f (k) = P(ST  = A|S0  = k)

= (P(ST  = A|S0  = k + 1) + P(ST  = A|S0  = k − 1))

= (f (k + 1) + f (k − 1))

So we see that f (·) satisfies the same recursion as g(·) with the exception that f (A) = 1, f (B) = 0 (why?). So the "maximum" argument won’t work any more, and this needs to be solved directly. We get from the above relation that f (k + 1) − f (k)  =  f (k) − f (k − 1) for each k .  So the consecutive differences are equal; let d be the value of this common difference. Then

f (A) − f (−B) =   (f (k + 1) − f (k)) = (A + B)d

k=−B

and using the fact that f (A) = 1, f (B) = 0 we get d =  . Thus,

f (k) = f (k) − f (−B) =   (f (l + 1) − f (l)) = (k + B)d =  .

This immediately answers the first question.

•  (Answer 1) Plugging A = 200, B = 100, k = 0, we get f (0) = (0 + 100)/(200 + 100) = 1/3.

Interpretation:  Suppose Alice and Bob are betting on the outcomes of fair coin tosses.  If the outcome is heads, Alice wins $1 from Bob, whereas if the outcome is tails, Bob wins $1 from Alice. The game continues until either Alice or Bob is ruined. If Alice and Bob start with $A and $B respectively, we want to find the probability that Alice ruins Bob i.e. Alice wins everything. Let us define a random walk representing Alice’s earnings. Clearly the walk starts from S0  = A. We are interested in the hitting time T  = TA+B,0  representing the first time Alice ruins Bob or Alice loses everything. We seek to find P(ST  = A + B|S0  = A) which, according to the formula above, equals

A + 0               A    

(A + B) + 0      A + B

Finally, let us look at the other questions involving the expected number of games the gambler has to play.  In other words, we are interested in h(k)  = E(T |S0   =  k) where T  = TA, −B  and −B ≤ k ≤ A. By now it is evident that we need to develop some kind of recursion using first step decomposition to solve for h(k).

Theorem 1.3. h(k) = (A − k)(k + B) for −B ≤ k ≤ A.

Proof.  See homework.

This enables us to answer the second 

question.

•  (Answer 2) A = 200, B = 100, k = 0, then h(0) = 200 × 100 = 20000.

Now we turn to the third question. Define the hitting time τr  = min{n ≥ 0 : Sn  = r}, the first time the random walk hits integer r .

•  (Question 3) B = 100. Want P(τ−100  < ∞|S0  = 0) and E(τ−100 |S0  = 0).

This hitting time looks very similar to the hitting time we have been talking about, but we are missing the upper boundary (which is ∞) so we create a sequence of (our original) hitting times with finite upper boundaries so that we can directly apply the results developed thus far.