LECTURE 3

Double stakes until a win. Let X_{1}, X_{2}, … be a sequence of Bernoulli trials, i.e. independent with P (X_{i} = 1) = p, P (X_{i} = −1) = 1 − p. Let F_{n} = σ(X_{1}, …, X_{n}) and suppose that a_{n} is measurable with respect to F_{n−1}. a_{n} is the strategy, and your winnings at time n are

S_{n} = ∑_{j=1}^{n} a_{j}X_{j}.

Clearly if p = 1/2 the game is fair and Y_{n} = X_{1} + ⋯ + X_{n} is a martingale. A particular strategy is

a_{n} = \{ \begin{matrix}2^{n−1} & if X_{1} = X_{2} = ⋯ = X_{n−1} = −1, \\ 0 & otherwise. \end{matrix}

The player simply doubles his bet until he wins, and then leaves the table. Note that if he wins on the nth trial, he has lost a total of 1 + 2 + 2^{2} + 2^{n−2} = 2^{n−1} − 1 and gained 2^{n−1} so he is up 1. On the other hand E[S_{n}] = 0 since S_{0} = 0 and S_{n} is a martingale.

Stopping times. Let (Ω, F, P) be a probability space, F_{n} a filtration. A stopping time τ is a non-negative random variable which has the property that

{ω : τ(ω) ≤ n} ∈ F_{n} for each n.

In words: The decision to stop by time n can be made with only information up to and including that at time n .

Examples. 1. The time when the player wins in the doubling example is a stopping time.

2. Let S_{n} be a simple random walk. The first time to hit level a,

τ(ω) = min{n : S_{n}(ω) = a}

is a stopping time. The last time to hit a,

σ(ω) = max{n : S_{n}(ω) = a}

is not a stopping time because you cannot know it is the last without looking into the future.

The stopped σ-field is given by

F_{τ} = {A ∈ F : A ∩ {τ = n} ∈ F_{n} for all n}.

F_{τ} is the information you have when you stop.

Theorem (Optional stopping). Let X_{n} be a martingale with respect to F_{n} and τ and σ bounded stopping times, i.e. σ, τ ≤ C for some C < ∞ with σ ≤ τ almost surely. Then

E[X_{τ} | F_{σ}] = X_{σ} a.s.

Proof. Going back to the definition of conditional expectation, what we need to show is that for every A ∈ F_{σ},

∫_{A} X_{τ} dP = ∫_{A} X_{σ}dP.

It would be enough to show that for each ℓ,

∫_{A∩{σ=ℓ}} X_{τ} dP = ∫_{A∩{σ=ℓ}} X_{σ}dP

because then we could just sum over ℓ and get what we want. Now the right hand side is just

∫_{A∩{σ=ℓ}} X_{ℓ}dP

By the martingale property, since A ∩ {σ = ℓ} ∈ F_{ℓ},

∫_{A∩{σ=ℓ}} X_{ℓ}dP = ∫_{A∩{σ=ℓ}} X_{C}dP.

On the other hand, the left hand side

∫_{A∩{σ=ℓ}} X_{τ} dP = ∑_{m=ℓ}^{C} ∫_{A∩{σ=ℓ}∩{τ=m}} X_{τ} dP.

By the martingale property, since A ∩ {σ = ℓ} ∩ {τ = m} ∈ F_{m},

∑_{m=ℓ}^{C} ∫_{A∩{σ=ℓ}∩{τ=m}} X_{τ} dP = ∑_{m=ℓ}^{C} ∫_{A∩{σ=ℓ}∩{τ=m}} X_{C}dP.

Summing over m we get the same thing on both sides, which completes the proof.

Distribution of hitting times. Let S_{n} be a simple symmetric random walk starting at 0. Let

τ(ω) = min{n : S_{n} = a}.

This is called the hitting time or the first passage time. We will now use the optional stopping theorem to compute the distribution of the random variable τ. The first thing is to note that for any λ,

exp{λS_{n} − n log G(λ)}

is a martingale, where G(λ) = E[e^{λX_{i}}] = (e^{λ} + e^{−λ})/2. Now τ is not a bounded stopping time, but for each fixed N < ∞, τ ∧ N is a bounded stopping time. By the optional stopping time theorem with σ = 0,

E[exp{λS_{τ∧N} − τ ∧ N log G(λ)}] = 1.

Letting N → ∞ by the bounded convergence theorem we get

E[exp{λa − τ log G(λ)}] = 1.

Let h(γ) be the inverse function of log G(λ) on the positive axis. Then we have

E[e^{γτ}] = e^{h(γ)a}.

One can check that P (τ = n) = 0 unless n and a have the same parity, in which case

P (τ = n) = \frac{a}{n}\binom{n}{\frac{n+a}{2}}2^{−n}.

It is most interesting to study this for a large. Then one can check by the normal approximation that as a → ∞,

P (τ ≤ ta^{2}) → \sqrt{\frac{2}{π}} ∫_{t^{−1/2}}^{∞} e^{−x^{2}/2}dx.

Another simple thing to check (for which you don’t have to invert the Laplace transform) is the expected waiting time:

E[τ] = \frac{d}{dγ} e^{h(γ)a}|_{γ=0} = ∞.

Although you hit level a with probability 1, the expected time to do so is infinite.

Reflection principle. There is another way to compute the hitting time distribution above. This is the reflection principle, which is roughly the same thing as the method of images for partial differential equations. It says that for simple symmetric random walks

P ( max_{1≤i≤n} S_{i} ≥ a) = 2P (S_{n} ≥ a).

This is because for every path that ends above a we can produce a path that has a maximum above a but ends below a by reflecting the part of the path after the first time that it hits a.

Suppose we want to know the probability that at time n − 1 the random walk is at a − 1, and that its maximum up to time n − 1 is ≤ a − 1. This is just the probability that at time n − 1 the walk is at a − 1 minus the probability that at time n − 1 the walk is at a − 1 and the maximum up to time n − 1 is ≥ a. But by reflection this is just

P (X_{n−1} = a − 1) − P (X_{n−1} = a + 1).

So now the probability that τ = n is just 1/2 this

P (τ = n) = \frac{1}{2}(P (X_{n−1} = a − 1) − P (X_{n−1} = a + 1)).

After a short computation you get the same answer as before.

Misuse of the optional stopping time theorem. Consider the doubling example. Let τ be the first time that you win. From the computation we did we know that S_{τ} = 1. But S_{n} is a martingale with S_{0} = 0 so the optional stopping theorem would say that E[S_{τ}] = 0. The reason it does not work is that τ is not a bounded stopping time. Introducing τ ∧ N as in the previous case doesn’t work either because although E[S_{τ∧N}] = 0 the integrand is not bounded so it is not true that lim n → ∞E[S_{τ∧N}] = E[lim n → ∞S_{τ∧N}].

PROBLEMS.

1. i. Let X be a random variable on (Ω, F, P) with E[|X|] < ∞. Let F_{1} ⊂ F_{2} ⊂ ⋯ ⊂ F be a filtration in F and define

X_{n} = E[X | F_{n}].

Show that X_{n} is a martingale with respect to F_{n}. ii. Let Y_{1}, Y_{2}, … be independent random variables with P (Y_{i} = 0) = P (Y_{i} = 2) =

1/2. Let F_{n} = σ(Y_{1}, …, Y_{n}) and

X_{n} = ∏_{i=1}^{n} Y_{i}.

Show that X_{n} is a martingale with respect to F_{n}, but that there exists no integrable random variable X such that

X_{n} = E[X | F_{n}].

2. Let X_{1}, X_{2}, … be a sequence of i.i.d. random variables with mean 0 and let S_{n} = X_{1} + ⋯ + X_{n}. Show that the sequences

M_{n}^{1} = S_{n}^{2} − nσ^{2}, σ^{2} = E[X_{j}^{2}],
M_{n}^{2} = e^{λS_{n}−n log G(λ)}, G(λ) = E[e^{λX_{j}}],

and

M_{n}^{3} = e^{izS_{n}−n log ϕ(z)}, ϕ(z) = E[e^{izX_{j}}],

are martingales with respect to F_{n} = σ(X_{1}, …, X_{n}).

3. i. Show that every martingale M_{n}, F_{n} has uncorrelated increments, i.e. if t_{1} < t_{2} <

t_{3} < t_{4} then the two increments M_{t_{4}} − M_{t_{3}} and M_{t_{2}} − M_{t_{1}} are uncorrelated. ii. Let M_{n} and N_{n} be two martingales with respect to F_{n}. Show that

E[M_{n}N_{n}] = ∑_{i=1}^{n} E[(M_{n} − M_{n−1})(N_{n} − N_{n−1})] + E[M_{0}N_{0}].

3. Suppose X_{1}, X_{2}, … are random variables and we know that the joint densities of (X_{1}, …, X_{n}) are either p_{n}(x_{1}, …, x_{n}) or q_{n}(x_{1}, …, x_{n}). But we do not know which. To decide, statisticians introduce the likelyhood ratios

L_{n} = \frac{q_{n}(X_{1}, …, X_{n})}{p_{n}(X_{1}, …, X_{n})}.

Lets suppose the densities are positive and continuous so we don’t have to worry about anything crazy. The idea is that if p_{n} are the right densities then the ratio should be very little because the observed values of X_{1}, …, X_{n} will tend to be where p_{n} is large. On the other hand if q_{n} are right, then the ratio should be very big. Problem: Show that if p_{n} are correct, then L_{n} is a martingale with respect to

F_{n} = σ(X_{1}, …, X_{n}).

4. An urn contains r red and g green balls. At each time step a ball is drawn at random. It is then replaced in the urn along with c balls of the same colour. Let X_{n} be the proportion of green balls. Show that X_{n} is a martingale.

5. (Branching processes) Let X_{1}, X_{2}, … be a sequence of non-negative integer valued random variables which have the property that, given X_{1}, …, X_{n}, the variable X_{n+1} is a sum Y_{1}^{n} +⋯+Y_{X_{n}}^{n} of random variables, again taking only integer values. You can think of X_{n} individuals in the nth generation and the ith individual gives birth to Y_{i}^{n} children. Assume the whole array Y_{i}^{n} are independent and indentically distributed. Problem. Find a normalization z_{n} so that X_{n}/z_{n} is a martingale.