Lecture 2: Stats 217 Summer 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Lecture 2: Stats 217
Summer 2022
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.
Consider the hitting times Tm, −B where m ∈ N, then note that Tm, −B = min(τm , τ−B) and hence Tm, −B ≤ τB . Since E(Tm, −B |S0 = 0) = mB → ∞ as m → ∞, we conclude that
E(τ−B) ≥ lim E(Tm, −B) → ∞
so that E(τ−B) = ∞ . So the gambler has to wait for an infinite amount of time (on average) to hit any −B (in question 3, B = 100).
Finally, recall that P(STm, − B = m|S0 = 0) = B/(m + B) → 0 as m → ∞ which implies P(STm, − B = −B|S0 = 0) = m/(m + B) → 1 as m → ∞ . Now, for any m,
P(τ−B < ∞|S0 = 0) ≥ P(STm, − B = −B|S0 = 0)
implying, taking limit as m → ∞ , P(τ−B < ∞|S0 = 0) = 1.
2022-07-16