Notes on Snell Envelops and Examples

Example (Secretary Problem): Conside a pool of N candidates whose qualifications are represented by unknown numbers {a_{1} > a_{2} > ⋯ > a_{N}} from best to last. They are interviewed sequentially in a random order and we denote the corresponding qualification by {Y_{1}, Y_{2}, …, Y_{N}}. That is, {Y_{1}, Y_{2}, …, Y_{N}} is a random permutation of {a_{1}, a_{2}, …, a_{N}} and we assume all N! permutations are equally likely. Candidates that are dismissed cannot be recalled.

The values of {Y_{1}, Y_{2}, …, Y_{N}} are not observable, what one observes is the “relative rank”

X_{n} ≐ ∑_{k=1}^{n} 1_{{Y_{n}≤Y_{k}}}.

So X_{n} is the rank of the n-th candidate among the n candidates that have been interviewed.

The question is how one chooses a stopping time τ with respect to the information generated by {X_{1}, X_{2}, …, X_{N}} so as to maximize the probability P (Y_{τ} = a_{1}) of selecting the best candidate.

solution: Observe that {X_{1}, X_{2}, …, X_{N}} are indepedent random variables and that

P (X_{n} = 1) = P (X_{n} = 2) = ⋯ = P (X_{n} = n) = 1/n

for every n.

Since Y_{n} cannot be determined by the value of {X_{1}, X_{2}, …, X_{n}} (i.e., Y_{n} is not measurable wrt to the σ-algebra generated by {X_{1}, X_{2}, …, X_{n}}), the first thing we want to do is to rewrite P (Y_{τ} = a_{1}) in terms of X_{i}’s. To this end, note that

P (Y_{n} = a_{1}|X_{1}, …, X_{n}) = f_{n}(X_{n})

where

f_{n}(x) ≐ \{ \begin{matrix}n/N ; & if x = 1 \\ 0 ; & if x > 1 \end{matrix}

Therefore

P (Y_{τ} = a_{1}) = ∑_{k=1}^{n} E[1_{{Y_{n}=a_{1}}}1_{{τ=n}}]

= ∑_{k=1}^{n} E [E[1_{{Y_{n}=a_{1}}}1_{{τ=n}}|X_{1}, …, X_{n}]]

= ∑_{k=1}^{n} E [1_{{τ=n}}E[1_{{Y_{n}=a_{1}}}|X_{1}, …, X_{n}]]

= ∑_{k=1}^{n} E [1_{{τ=n}}f_{n}(X_{n})]
= Ef_{τ} (X_{τ}).

Now we can write down the DPE

V_{N}(x) ≡ f_{N}(x)
V_{n}(x) = max \{f_{n}(x), \frac{1}{n + 1} ∑_{k=1}^{n+1} V_{n+1}(k)\} .

It is not difficult to show (by a verification argument) that

sup_{τ} P (Y_{τ} = a_{1}) = V_{1}(1)

and the optimal stopping time is

σ^{∗} ≐ inf{n ≥ 1 : V_{n}(X_{n}) = f_{n}(X_{n})}.

Since the solution to the DPE has an explicit form

V_{n}(x) = \{ \begin{matrix}n/N ; & if x = 1 \\ \frac{n}{N} [\frac{1}{N−1} + ⋯ + \frac{1}{n}] ; & if x > 1 \end{matrix} ; n ≥ m(N)

and

V_{n}(x) ≡ \frac{m(N) − 1}{N} [\frac{1}{N − 1} + ⋯ + \frac{1}{m(N) − 1}]; n < m(N),

where m(N) is the unique integer such that

∑_{k=m(N)}^{N−1} \frac{1}{k} ≤ 1 < ∑_{k=m(N)−1}^{N−1} \frac{1}{k} ,

it is not difficult to check that

σ^{∗} = inf{n ≥ m(N) : X_{n} = 1}.

That is, the optimal policy is to let the first m(N) − 1 candidates go and continue interviewing candidated until the first time at which the current candidate is the best among the those examined so far. The maximal probability is

sup_{τ} P (Y_{τ} = a_{1}) = V_{1}(1) = \frac{m(N) − 1}{N} [\frac{1}{N − 1} + ⋯ + \frac{1}{m(N) − 1}] .

When N is large, it is not difficult to see that m(N)/N ≈ 1/e and V_{1}(1) ≈ 1/e, where 1/e ≈ 36.8%.

1 Snell envelope

Consider a sequence of integrable random variables Y = {Y_{n} : n = 0, 1, …} adapted to a filtration 𝔽 = {ℱ_{n}} defined on a complete probability space (Ω, ℱ, ℙ). For simplicity we assume {Y_{n}} is uniformly bounded. This condition can be relaxed and all the results below hold as long as sup_{n} Y_{n}^{+} is integrable.

Remark 1. In this section, whenever we mention stopping times, unless explicitly pointed out otherwise, we are assuming that the stopping time is finite with probability one.

We consider the infinite horizon problem

v_{0} ≐ sup_{τ} E[Y_{τ}].

In a nutshell, we will prove that there exists a supermartingale {Z_{n}} such that

v_{0} = E[Z_{n}]

for every n ≥ 0, and the optimal stopping time is

σ^{∗} = inf{n ≥ 0 : Y_{n} = Z_{n}},

whenever σ^{∗} is finite with probability one. As we will see, the supermartingale can be represented in the form

Z_{n} = esssup_{τ≥n}E[Y_{τ} |ℱ_{n}].

This supermartingale Z is called “Snell envelope” and will turn out to be the smallest supermartingale that dominates Y.

1.1 Essential supremum

In this section we will introduce the concept of essential supremum, which is very useful to resolve the measurability issue when the supremum of a collection of uncountable functions are concerned.

Consider an arbitrary family of random variables g : Ω → ℝ̄ ≐ ℝ∪{+∞} defined on a complete probability space (Ω, ℱ, P). The essential supremum of G is a random variable ℓ : Ω → ℝ̄ such that

1. For every g ∈ G, ℓ ≥ g almost surely.

2. If h ≥ g almost surely for every g ∈ G, then h ≥ ℓ almost surely.

Proposition 1. Essential supremum always exists, and there exists a sequence {g_{n}} ⊂ G such that

esssup(G) = sup_{n} g_{n}, a.s.

Proof. We can assume all the random variables g taking values in [0, 1] (otherwise, use a monotone bijection from ℝ̄ to [0, 1]). Let 𝒞 be the collection of all countable subset of G. For every C ∈ 𝒞, define pointwise

ℓ_{C} ≐ sup_{g∈C} g.

Let

v ≐ sup_{C∈𝒞} E[ℓ_{C}].

We claim that the supremum in the definition of v is attained. Indeed, consider a maximizing sequence {C_{1}, C_{2}, …} so that

v = lim_{n} ↑ E[ℓ_{C_{n}}].

Define C^{∗} ≐ C_{1} ∪ C_{2} ∪ ⋯, then C^{∗} ∈ 𝒞, and

E[ℓ_{C_{n}}] ≤ E[ℓ_{C^{∗}}] ≤ v.

We conclude E[ℓ_{C^{∗}}] = v. Let ℓ^{∗} ≐ ℓ_{C^{∗}}. We want to show that ℓ^{∗} is the essential supremum. Consider any g ∈ G, define

C ≐ 𝒞^{∗} ∪ {g} ∈ 𝒞.

We have

v ≥ E[ℓ_{C}] = E[ℓ^{∗} ∨ g] ≥ E[ℓ^{∗}] = v.

It follows that ℓ^{∗} ∨g = ℓ^{∗}, or ℓ^{∗} ≥ g, almost surely. Moreover, for any h such that h ≥ g almost surely, we have h ≥ ℓ_{C} almost surely for every C ∈ 𝒞. In particular,

h ≥ ℓ^{∗}

almost surely. Finally, since 𝒞^{∗} is countable, one can arrange it in a sequence {g_{n}} so that

ℓ^{∗} = ℓ_{C^{∗}} = sup_{g∈C^{∗}} g = sup_{n} g_{n}.

This completes the proof.

Remark 2. It is not difficult to see that essential supremum is unique up to almost sure equivalence.

Remark 3. When the set G is directed upwards in the sense that for every pair g_{1}, g_{2} ∈ G, there exists g ∈ G such that g ≥ g_{1} ∨ g_{2} almost surely, one can argue that there exists a non-decreasing sequence {g_{n}} ⊂ G such that

esssup(G) = lim_{n} ↑ g_{n}.

1.2 Snell envelope

The Snell envelope is defined as the process Z = {Z_{n}} given by

Z_{n} ≐ esssup_{τ≥n}E[Y_{τ} |ℱ_{n}].

We have the following result.

Theorem 1. The process Z satisfies the DPE

Z_{n} = max{Y_{n}, E[Z_{n+1}|ℱ_{n}]}

and

v_{n} ≐ sup_{τ≥n} E[Y_{τ}] = E[Z_{n}]

for every n ≥ 0. In particular, Z is the smallest supermartingale that dominates Y.

Proof. The random variable Z_{n} is bounded, ℱ_{n}-measurable and satisfies Y_{n} ≤ Z_{n}.

We claim that the collection of random variables {E[Y_{τ} |ℱ_{n}] : τ ≥ n} are directed upwards. In fact, let τ_{1}, τ_{2} be two stopping times. Let

A ≐ {E[Y_{τ_{1}}|ℱ_{n}] ≥ E[Y_{τ_{2}}|ℱ_{n}]}.

Then A ∈ ℱ_{n} and the random time

τ ≐ τ_{1} · 1_{A} + τ_{2} · 1_{A^{c}}

is indeed a stopping time. It follows that

E[Y_{τ} |ℱ_{n}] = 1_{A}E[Y_{τ_{1}}|ℱ_{n}] + 1_{A^{c}}E[Y_{τ_{2}}|ℱ_{n}] = max{E[Y_{τ_{1}}|ℱ_{n}], E[Y_{τ_{2}}|ℱ_{n}]}.

Thanks to Remark 3, there exists a sequence of stopping times {τ_{k}} such that τ_{k} ≥ n, and

Z_{n} = lim_{k} ↑ E[Y_{τ_{k}}|ℱ_{n}].

Using MCT (the conditional expectation version), we have

E[Z_{n}|ℱ_{n−1}] = lim_{k} ↑ E[E[Y_{τ_{k}}|ℱ_{n}]|ℱ_{n−1}] = lim_{k} E[Y_{τ_{k}}|ℱ_{n−1}] ≤ Z_{n−1}.

It follows that

Z_{n} ≥ max{Y_{n}, E[Z_{n+1}|ℱ_{n}]}.

On the other hand, for any stooping time τ ≥ n, we write

Y_{τ} = Y_{n}1_{{τ=n}} + Y_{τ∨(n+1)}1_{{τ>n}}.

And

E[Y_{τ} |ℱ_{n}] = 1_{{τ=n}}Y_{n} + 1_{{τ>n}}E[Y_{τ∨(n+1)}|ℱ_{n}]
= 1_{{τ=n}}Y_{n} + 1_{{τ>n}}E[E[Y_{τ∨(n+1)}|ℱ_{n+1}]|ℱ_{n}]
≤ 1_{{τ=n}}Y_{n} + 1_{{τ>n}}E[Z_{n+1}|ℱ_{n}]
≤ max{Y_{n}, E[Z_{n+1}|ℱ_{n}]}.

Taking supremum on the left-hand-side, we have Z_{n} ≤ max{Y_{n}, E[Z_{n+1}|ℱ_{n}]}. Therefore equality holds.

Furthermore, by MCT, E[Z_{n}] = lim_{k} ↑ E[E[Y_{τ_{k}}|ℱ_{n}]] = lim_{k} ↑ E[Y_{τ_{k}}], we have

E[Z_{n}] ≤ sup_{τ≥n} E[Y_{τ}] = v_{n}.

But by definition of Z_{n}, E[Z_{n}] ≥ E[Y_{τ}] for every τ ≥ n. It follows that

E[Z_{n}] = sup_{τ≥n} E[Y_{τ}] = v_{n}.

Finally, note the DPE implies that {Z_{n}} is a supermartingale. Let Z′ be another supermartingale that dominates Y (thus bounded from below). By optional sampling theorem, for every τ ≥ n,

Z′_{n} ≥ E[Z′_{τ} |ℱ_{n}] ≥ E[Y_{τ} |ℱ_{n}].

Thus Z′_{n} ≥ Z_{n}. This completes the proof.

Theorem 2. The supremum v_{0} = sup_{τ} E[Y_{τ}] is attained if and only if the stopping time

σ^{∗} ≐ inf{n ≥ 0 : Z_{n} = Y_{n}}

is finite with probability one. In this case, σ^{∗} is indeed optimal.

Proof. We first assume that σ^{∗} is finite almost surely. We claim that the process {Z_{σ^{∗}∧n} : n ≥ 0} is a martingale wrt to {ℱ_{n}}. Indeed,

E[Z_{σ^{∗}∧(n+1)}|ℱ_{n}] = 1_{{σ^{∗}≤n}}Z_{σ^{∗}} + 1_{{σ^{∗}>n}} · E[Z_{n+1}|ℱ_{n}]
= 1_{{σ^{∗}≤n}}Z_{σ^{∗}} + 1_{{σ^{∗}>n}} · Z_{n}
= Z_{σ^{∗}∧n}.

In particular, we have, thanks to DCT and Theorem 1,

v_{0} = E[Z_{0}] = lim_{n} E[Z_{σ^{∗}∧n}] = E[Z_{σ^{∗}}] = E[Y_{σ^{∗}}],

or σ^{∗} is optimal.

Now assume that there exists an optimal stopping time ρ, and we wish to show σ^{∗} is finite. It suffices to show that Z_{ρ} = Y_{ρ}. But Y_{ρ} ≤ Z_{ρ} and by optional sampling theorem,

E[Y_{ρ}] = v_{0} = E[Z_{0}] ≥ E[Z_{ρ}].

Therefore, Y_{ρ} = Z_{ρ} almost surely.

Exercise. For every stopping time ρ, show that

Z_{ρ} = esssup_{τ≥ρ}E[Y_{τ} |ℱ_{ρ}]

and

E[Z_{ρ}] = sup_{τ≥ρ} E[Y_{τ}].

Exercise (A pathwise approach to optimal stopping). A supermartingale Z = {Z_{n}} admits the Doob’s Decomposition

Z = M − A

where M = {M_{n}} is a martigale wrt to {ℱ_{n}}, and A = {A_{n}} is a nondecreasing process such that A_{0} = 0 and A_{n} is ℱ_{n−1}-measurable. The decompsition is unique, and it is determined recursively by

M_{0} = Z_{0}, M_{n} = M_{n−1} + Z_{n} − E[Z_{n}|ℱ_{n−1}]

and

A_{0} = 0, A_{n} = A_{n−1} + Z_{n−1} − E[Z_{n}|ℱ_{n−1}].

Let M_{∞} ≐ lim_{n} M_{n}. Define a non-adapted process λ_{n} ≐ M_{∞} − M_{n}. Then

v_{0} = E[sup_{n}(Y_{n} + λ_{n})].

Moreover, if σ^{∗} is finite with probability one, then the supremum sup_{n}(Y_{n} + λ_{n}) is attained at σ^{∗} almost surely.

Exercise (Prophet Inequality). Let Y = {Y_{n}} be a sequence of non-negative, independent random variables, and ℱ_{n} is the σ-algebra generated by (Y_{0}, Y_{1}, …, Y_{n}). Show that

E[sup_{n} Y_{n}] ≤ 2v_{0}.