A prophet inequality for L p-bounded dependent

random variables

Adam Ose¸kowski

Received: 21 March 2014 / Accepted: 21 May 2014

© The Author(s) 2014. This article is published with open access at Springerlink.com

Abstract Let X = (Xn)n 1≥be a sequence of arbitrarily dependent nonnegative ran-

dom variables satisfying the boundedness condition

sup EX τp ≤ t,
τ

where t > 0, 1 < p < ∞ are fixed numbers and the supremum is taken over
all finite stopping times of X . Let M= E supn Xn and V supτ EX τ denote the
expected supremum and the optimal expected return of the sequence X , respectively.
We establish the prophet inequality

V te
M≤V+ log
p−1 Vp

and show that the bound on the right is the best possible. The proof of the inequality
rests on Burkholder’s method and exploits properties of certain special functions.
The proof of the sharpness is somewhat indirect, but we also provide an indication
how the extremal sequences can be constructed.

Keywords Prophet inequality Optimal

· stopping Bellman
· function
Best constants ·

Research partially supported by the NCN grant DEC-2012/05/B/ST1/00412.

A. Ose¸kowski (B)
Department of Mathematics, Informatics and Mechanics, University of Warsaw,
Banacha 2, 02-097 Warsaw,
Poland e-mail:
ados@mimuw.edu.pl
A prophet inequality for L p -bounded dependent random
variables

Mathematics Subject Classification (2010) Primary 60G40 ·60E15;

Secondary 62L15

1 Introduction

The purpose of the paper is to establish a sharp estimate between the expected
supre- mum of a sequence = X ≥ (Xn)n 1 of L -bounded random variables and the
p

opti- mal expected return (i.e., optimal stopping value) of X . Such comparisons are
called “prophet inequalities” in the literature and play a distinguished role in the
theory of optimal stopping, as evidenced in the papers of Allaart [1], Allaart and
Monticino [2], Assaf et al. [4,5], Boshuizen [3,6], Hill [8,9], Hill and Kertz [10–
12], Kennedy
[13,14], Kertz [15,16], Krengel, Sucheston and Garling [17–19], Tanaka [24,25]
and many others.
We start with the necessary background and notation. Assume that X = (Xn)n ≥ 1
is a sequence of (possibly dependent) random variables defined on the probability
space (▲, F , P). With no loss of generality, we may assume that this probability
space is the interval [0, 1 ] equipped with its Borel subsets and Lebesgue measure. Let
( F n)n 1 =≥(σ(X 1 , X 2 , . . . , Xn))n 1 be the natural filtration of X . The problem can
be generally
≥
stated as follows: under some boundedness condition on X , find universal
inequalities which compare M = E supn Xn, the expected supremum of the sequence,
with V sup
= τ EXτ , the optimal stopping value of the sequence; here τ runs over the
class T of all finite stopping times adapted F to ≥
( n)n 1. The term “prophet
inequality”
arises from the optimal-stopping interpretation of M , which is the optimal expected
return of a player endowed with complete foresight; this player observes the
sequence X and may stop whenever he wants, incurring a reward equal to the
variable at the time of stopping. With complete foresight, such a player obviously
stops always when the largest value is observed, and on the average, his reward is
equal to M . On the other hand, the quantity V corresponds to the optimal return of
the non-prophet player.
Let us mention here several classical results in this direction; for an excellent
expo- sition on the subject, we refer the interested reader to the survey by Hill and
Kertz [12]. The first universal prophet inequality is due to Krengel, Sucheston and
Garling [17,18]: if X1, X2, . . . are independent and nonnegative, then
M ≤ 2V

and the constant 2 is the best possible. The next result, coming from [8] and [10],
states that if X1, X2, . . . are independent and take values in [0, 1], then
1
M−V ≤
4

and

M ≤ V − V 2.

Both estimates are sharp: equalities may hold for some non-trivial sequences X . Anal-
ogous inequalities for other types of variables X1, X2, . . . (e.g., arbitrarily-dependent
A prophet inequality for L p -bounded dependent random
variables

and uniformly bounded, i.i.d., averages of independent r.v.’s, exchangeable r.v.’s,

etc.), as well as for other stopping options (for instance, stopping with partial recall,
stopping several times, using only threshold stopping rules, etc.) have been studied
intensively in the literature and have found many interesting applications. We refer
the reader to the papers cited at the beginning.
The motivation for the results obtained in this paper comes from the following
statement proved by Hill and Kertz [11]: if X1, X2, . . . are arbitrarily dependent and
take values in [0, 1], then we have the sharp bound

M ≤ V − V log V. (1.1)

There is a very natural problem concerning the L p-version of this result, where p is
a fixed number between 1 and infinity. For example, consider the following
interest- ing question. Suppose that X1, X2, . . . are nonnegative random variables
satisfyingn sup
≤ n EX
p
1. What is the analogue of (1.1)? Unfortunately, as we will
see in Sect. 5 below, there is no non-trivial prophet inequality in this setting. More
precisely, for any K > 0 one can construct a sequence X bounded in L = p
which
satisfies
≥ V 1 and M K .
We will work under the more restrictive assumption

X1, X2, . . . are nonnegative and satisfy sup EX pτ ≤ t, (1.2)

τ ∈T

where t is a given positive number. For instance, this holds true, if the sequence X
possesses a majorant ξ which satisfies Eξ p ≤ t
. The main result of the paper is the
following.
Theorem 1.1 Let t > 0, 1 < p < ∞ be fixed and suppose that X1, X2, . . . satisfy
(1.2). Then
V te
M≤V+ log (1.3)
p−1 Vp
and the inequality is sharp: the bound on the right cannot be replaced by a smaller
number.
Note that this statement generalizes the inequality (1.1) of Hill and Kertz: it suffices
to take t= 1 and let p go∞to to recover the bound. On the other hand, the
expression on the right of (1.3) explodes
↓ as p 1, which indicates that there is no
prophet inequality in the limit=case p 1.
A few words about the proof. Our approach is based on the following two-step
pro- cedure: first we show that it suffices to establish (1.3) under the additional
assumption that X is a nonnegative supermartingale; second, we prove that in the
supermartingale setting, the validity of (1.3) is equivalent to the existence of a
certain special function which enjoys appropriate majorization and convexity
properties. In the literature this equivalence is often referred to as Burkholder’s
method or Bellman function method, and it has turned out to be extremely efficient
in numerous problems in probability and analysis: consult e.g. [7,20,21,26] and
references therein.
A prophet inequality for L p -bounded dependent random
variables

We have organized the paper as follows. In the next section we reduce the
problem to the supermartingale setting. Section 3 contains the description of
Burkholder’s method (or rather its variant which is needed in the study of (1.3) for
supermartingales). In Sect. 4 we apply the method and provide the proof of
Theorem 1.1. In the final part of the paper we show that there are no interesting
prophet inequalities in the case when the variables X1, X2, . . . are only assumed to
be bounded in L p.

2 A reduction

In this section we show how to relate (1.3) to a certain inequality for nonneg-
ative supermartingales. Throughout, we use the notation X ∗ = supn≥1 Xn and
∗
X m = sup1≤n ≤m X n for the maximal and the truncated maximal function of
X.
Recall that V = supτ EXτ . We start with the observation that it is enough to
deal with finite sequences only (in this paper we say that X is finite, if it is of the
form (X 1 , X 2 , . . .−, X N 1, X N , X N , X N , . . .) for some deterministic N ). This is
straightfor-
ward: suppose we have successfully established the prophet inequality in this
special case, and pick an arbitrary, possibly non-finite X . Then for any fixed N , the
truncated sequence X N = (X 1 , X 2 , . . . , X N −1 , X N , X N , X N , . . .) is finite, inherits
optimal expected return does not exceed V . Since the function V›→ V V log te
(1.2) an d it s p−1 V
p

is nondecreasing on (0, t 1/p], an application of (1.3) gives

V te
E(X N )∗ ≤ V + log .
p−1 V p

It remains to let N →∞ and use Lebesgue’s monotone convergence theorem.

Lemma 2.1 Suppose that X = (Xn)n≥1 is an arbitrarily dependent finite sequence of
random variables satisfying X1 ≡ 0 and (1.2). Then there is a finite
supermartingale Y = (Yn)n≥1 adapted to the filtration of X, which satisfies

Yn ≥ Xn almost surely for all n, (2.1)

P (Y1 = V ) = 1 (2.2)

and
sup EYτ p ≤ t, sup EYτ ≤ V. (2.3)
τ ∈T τ ∈T
Note that the additional assumption X1 ≡ 0 is not restrictive at all: we can always
replace the initial sequence X1, X2, . . . with 0, X1, X2, .. ., and the prophet inequality
remains the same. In the proof of the above lemma we will need the notion of essential
supremum, a well-known object in the optimal stopping theory. Let us briefly recall its
definition, for details and properties we refer the reader to the monographs of Peskir
and Shiryaev [22] and Shiryaev [23].
Definition 2.1 Let (Zα)α∈I be a family of random variables. Then there is a
= ∈
A prophet inequality for L p -bounded dependent random
variables
countable subset J of I such that the random variable Z supα J Zα satisfies the
following two properties:
A prophet inequality for L p -bounded dependent random
variables

(i) P(Zα ≤ Z) = 1 for each α ∈ I ,

(ii) if Z˜ is another random variable satisfying (i) in the place of Z , then P(Z ≤ Z˜ ) =
1.
The random variable Z is called the essential supremum of (Zα)α∈I .
Proof of Lemma 2.1 We will use some basic facts from the optimal stopping theory;
for details, we refer the reader to Chapter I in Peskir and Shiryaev [22]. Suppose
that X (X
= 1 , X 2 , . . . , X N , X N , X N , . . .) is a finite sequence and let Y be the Snell
envelope of X , i.e., the smallest adapted supermartingale majorizing the sequence
(Xn)n≥1. It is a well-known fact that for each n the variable Yn is given by the formula

Yn = ess sup E(Xσ |Fn) : σ ∈ Tn ,

where T n denotes the class of all finite adapted stopping times not smaller than n. Since
σ ≡ n belongs to n, the inequality (2.1) is given for free. To show (2.2), observe
that Y1 is a constant random variable, since the σ -algebra F =1 σ(X 1) is trivial. Thus
the bound Y1 ≥ V follows directly from the above formula for Y1 and the definition
of an essential supremum. On the other hand, for any finite stopping time σ we
have
≥ V EX=σ E(Xσ|F1) almost surely, which implies P(V≥ Y1) 1, again from the
definition =of an essential supremum. This gives (2.2). Since the sequence X
stabilizes after N steps, so does Y and therefore the second estimate in (2.3) holds
true, directly from (2.2) and the supermartingale property. To prove the first bound
in (2.3), recall that Y can be alternatively defined by the backward induction

YN = X N , Yn = max X n , E(Yn+1|Fn) , n = 1, 2, . . . , N − 1.

This implies that Yn = E(Xτn |Fn), where the stopping time τn is given by

τn = inf k ∈ {n, n + 1 , . . . , N } : Yk = X k .

Thus, if we fix an arbitrary τ ∈ T , then

N N

Yτ = Yτ ∧N = Yn 1{τ ∧N =n} = 1{τ ∧N =n}E Xτn |Fn ,

n=1 n=1

which gives
N N

τ n τ σ
n=1 n=1 n

p
EY p = E E 1{τ∧N=n} Xτ |Fn ≤ E 1{τ∧N=n} X p = EX p,

N 1{τ∧N=n}τn. We easily check that σ is a stopping time: for any

where σ =
A prophet inequalityn for L p -bounded dependent random
=1
variables , the
1≤k≤
N eventN k

n=1 n=1

{σ = k } = ({τ ∧ N = n}∩ {τn = k}) = ({τ ∧ N = n}∩ {τn = k})

A prophet inequality for L p -bounded dependent random
variables

belongs to Fk. Therefore, the boundedness assumption (1.2) implies τ EY ≤ t , as

p

desired.
Therefore, it suffices to establish the inequality (1.3) under the additional assump- tion that the process X is
a finite supermartingale and the variable X1 is constant almost surely. By some standard approximation
arguments, we may further restrict ourselves to the class of simple supermartingales; recall that the sequence
X (Xn)n≥1 is called simple, if for each n the random variable=Xn takes only a finite number of values. We
are ready to apply Burkholder’s method, which is introduced in the next section.

3 Burkholder’s method

Now we will describe the main tool which will be used to establish the inequality (1.3). Distinguish the set

D = {(x, y, t) ∈ [0, ∞) × [0, ∞) × [0, ∞) : x p ≤ t, x ≤ y}

and, for each (x, y, t) ∈ D, let S(x, y, t) denote the class of all simple, finite and
p
nonnegative supermartingales X = (Xn)n≥1 satisfying X1 ≡ x and supττ EX ≤ t ,
where the supremum is taken over all stopping times adapted to the natural filtration of X . Suppose that we
are interested in the explicit formula for the function

∗
B(x, y, t) = sup E X n ∨ y ,

where the supremum is taken over all positive integers n and all X ∈ S(x, y, t). The key idea in the study of this
problem is to introduce the class C which consists of all functions B : D → R satisfying

B(x, y, t) ≥ y for any (x, y, t) ∈ D, (3.1) and the following

concavity-type property: if α ∈ [0, 1], (x, y, t) ∈ D and (x±, x± ∨

y, t±) ∈ D satisfy αx− + (1 − α)x+ ≤ x and αt− + (1 − α)t+ ≤ t , then

B(x, y, t) ≥ α B(x−, x− ∨ y, t−) + (1 − α)B(x+, x+ ∨ y, t+). (3.2)

We turn to the main result of this section. Recall that the probability space is the interval [0, 1] with its
Borel subsets and Lebesgue measure.
Theorem 3.1 The function B is the least element of the class C. Proof It is convenient to

split the reasoning into two parts.

∗
Step 1. First we will show that B belongs to the class C. The majorization (3.1) is imme- diate, since X n ∨ y ≥
y. The main difficulty lies in proving the concavity property (3.2). Fix the parameters α, x , t , x±, t± as in the
statement and pick arbitrary super- martingales X − ∈ S(x−, y, t−), X + ∈ S(x+, y, t+). We splice these two
processes into one sequence X = (Xn)n≥1 by setting X1 ≡ x and, for n ≥ 2,