Journal of Convex Analysis Volume 2 (1995), No.1/2, 229–240

Polyhedral Approximation of Convex Sets With an Application to Large Deviation Probability Theory

Peter E. Ney^{1}

University of Wisconsin, Dept. of Mathematics, 480 Lincoln Drive, Madison, WI 53706, USA.

Stephen M. Robinson^{2}^{,}^{∗}

University of Wisconsin, Dept. of Industrial Engineering, 1513 University Avenue, Madison, WI 53706-1572, USA. e-mail: smr@cs.wisc.edu

Received 8 June 1994 Revised manuscript received 6 January 1995

Dedicated to R. T. Rockafellar on his 60th Birthday

We extend the well known large deviation upper bound for sums of independent, identically distributed random variables in IR^{d} by weakening the requirement that the rate function have compact level sets (the classical Cramér condition). To do so we establish an apparently new theorem on approximation of closed convex sets by polytopes.

Keywords : Large deviations, Cramér condition, rate function, polyhedral convex sets, polytopes

1991 Mathematics Subject Classification: 60F10, 52A20, 52A25

1. Introduction

Let X_{1}, X_{2}, … be independent random variables taking values in IR^{d}, 1 ≤ d < ∞, with common probability law μ( ·) = P {X_{i} ∈ · }, and expectation EX_{i} = m = ∫ xdμ(x) when it exists (the following discussion does not require existence of an expectation). Let S_{n} = ∑_{i=1}^{n} X_{i}. The law of large numbers says that S_{n}/n → m almost surely. Large deviation theory is concerned with the behavior of S_{n}/n away from its central

1 sponsored by an award from the Alexander von Humboldt Stiftung at the University of Frankfurt a.M. 2 sponsored by the National Science Foundation under Grant CCR-9109345 and the Air Force Systems

Command, USAF, under Grant F49620-93-1-0068. The US Government has certain rights in this material, and is authorized to reproduce and distribute reprints for Governmental purposes notwithstanding any copyright notation thereon.

∗ corresponding author.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

230 P. E. Ney / S. M. Robinson : Polyhedral approximation of convex sets

tendency. A classical result, due originally to Cramér [1], states that there exists a convex, lower semicontinuous function I : IR^{d} → IR_{+}, such that

lim inf n^{−1} log P {S_{n}/n ∈ G} ≥ − inf_{x∈G} I(x)  (1.1)

for each open subset G of IR^{d}, and that under some hypotheses

lim sup n^{−1} log P {S_{n}/n ∈ F } ≤ − inf_{x∈F} I(x)  (1.2)

for each closed F. I(x) is called the rate function, and {S_{n}} is said to satisfy the large deviation principle (LDP). Convex duality theory plays an important role in the above results, because great interest attaches to properties of I( ·), and because it can be shown that

I(x) = Λ^{∗}(x),  (1.3)

where Λ(α) = log E exp⟨α, X_{1}⟩, α ∈ IR^{d}, and Λ^{∗} is the convex conjugate of Λ. The function Λ is convex, proper, and (by Fatou’s lemma) closed, with Λ(0) = 0. The inequality (1.1) holds for all d (with no further hypotheses). Also (1.2) is known to hold for d = 1, and it holds for d > 1 if F is compact, or is closed and convex. For general closed F (1.2) is known to hold if

0 ∈ int dom Λ,  (C)

where dom Λ is the effective domain {α ∈ IR^{d} | Λ(α) < +∞}. This condition (known as the Cramér condition) ensures that the level sets of Λ^{∗},

L_{a}(Λ^{∗}) = {x | Λ^{∗}(x) ≤ a},

are compact, a fact that plays a role in the proofs. The validity of (1.2) for general closed F, without the condition (C), has been an open question with some interesting history. Slaby [10] produced a counterexample when F was open, and Dinwoodie [4] extended this to a counterexample for closed F with d = 3. Yet there are many interesting cases in which (1.2) holds for closed F, and for general F, without (C). In this paper we give some general sufficient conditions under which this is true. A basic difference between our approach and that usually used in proofs of (1.2) is that the latter tries to approximate F itself by halfspaces or balls, whereas we try to approximate the level sets of Λ^{∗}. In the process we use some apparently new results on the approximation of convex sets by polyhedral convex sets (Theorems 2.1 and 2.2), and on the separation of the level sets of convex functions by polyhedra (Theorem 2.3). Some of these results make use of the principle of cancellation (subtraction) of convex sets established by Rådström [6], in the support-function form studied definitively by Hörmander [5]. For background on large deviation theory the reader is referred to Varadhan [11], Deuschel and Stroock [3], or Dembo and Zeitouni [2]. For background on convexity the reference is of course Rockafellar [9].

2. Results

Here is an outline of our approach to the problem. Let

a = Λ^{∗}(F) := inf_{x∈F} Λ^{∗}(x).

Assume that a is positive, and suppose that for each ϵ > 0 we can find a finite collection of open halfspaces H_{1}, …, H_{N} such that the intersection

P = ∩_{i=1}^{N}H_{i}

satisfies

L_{a−ϵ} ⊂ P ⊂ L_{a}.  (2.1)

Then for each i, Λ^{∗}(H_{i}^{c}) ≥ a − ϵ, where the superscript c denotes the complement of a set. There is also no loss of generality in assuming that Λ^{∗}(H_{i}^{c}) ≤ a, for if, e.g., Λ^{∗}(H_{1}^{c}) > a , then L_{a} would be contained in H_{1}. We claim that in such a case P′ := ∩_{i=2}^{N}H_{i} ⊂ L_{a}, so that H_{1} could be discarded. Indeed, if this were not so we could find a point z contained in P′ but not in L_{a}. Let x ∈ P, and consider the line segment [x, z]. This segment is a subset of P′, and by identifying it with part of the real line we can consider it to be ordered with x < z. Now z belongs to the open complement of L_{a}, so the segment [x, z] crosses the boundary of L_{a} at a point w < z. Then w ∈ H_{1}, which is open; accordingly, if we take w′ close enough to w with w < w′ < z then w′ ∈ H_{1}. But then w′ ∈ P, contradicting our assumption that P ⊂ L_{a}. Thus we may assume that for i = 1, …, N

a − ϵ ≤ Λ^{∗}(H_{i}^{c}) ≤ a.  (2.2)

We also note that F ⊂ cl L_{a}^{c}. To see this, let x ∈ F; if Λ^{∗}(x) > a then x ∈ L_{a}^{c}, so suppose Λ^{∗}(x) = a. As a > 0 = −Λ(0) = inf Λ^{∗}, there is some point p ∈ IR^{d} with Λ^{∗}(p) < a. By prolonging the line segment [p, x] slightly beyond x we obtain a point x′ at which, by convexity, Λ^{∗}(x′) > a. Therefore x′ ∈ L_{a}^{c}, so x ∈ cl L_{a}^{c} and so F ⊂ cl L_{a}^{c} as asserted. Now from the fact that P ⊂ L_{a} we obtain

L_{a}^{c} ⊂ P^{c} = ∪_{i=1}^{N}H_{i}^{c}.

The set on the right is closed, and so we have

F ⊂ cl L_{a}^{c} ⊂ ∪_{i=1}^{N}H_{i}^{c}.

Now we can argue that

P {S_{n}/n ∈ F } ≤ P {S_{n}/n ∈ ∪_{i=1}^{N}H_{i}^{c}} ≤ ∑_{i=1}^{N} P {S_{n}/n ∈ H_{i}^{c}}.  (2.3)

But H_{i}^{c} is closed and convex, so from the known fact that (1.2) holds for such sets we deduce that

lim sup n^{−1} log P {S_{n}/n ∈ H_{i}^{c}} ≤ −Λ^{∗}(H_{i}^{c}).  (2.4)

Applying this to (2.3) we find with some calculation that

lim sup n^{−1} log P {S_{n}/n ∈ F } ≤ − inf_{i=1}^{N} Λ^{∗}(H_{i}^{c}) ≤ −Λ^{∗}(F) + ϵ.  (2.5)

Since ϵ > 0 was arbitrary, it follows that (1.2) holds for F. We will determine conditions on the probability measure μ( ·) and the set F that suffice for (2.1). We start by summarizing the convexity results we will need, then give the large deviation results. Proofs are in Section 3.

2.1. Convexity results

Let us start with an arbitrary closed proper convex function f : IR^{d} → (−∞, +∞] satisfying f(0) = 0. For a convex set C, let cone C be the cone generated by C (that is, the set of all positive scalar multiples of points of C). Let dom f = {α | f(α) < +∞}; note that 0 ∈ dom f. We write rc C for the recession cone of C, defined to be the set

{y ∈ IR^{d} | x + λy ∈ C for each x ∈ C and λ ≥ 0},

and I_{C} and I_{C}^{∗} for its indicator and support functions respectively. We denote the Euclidean unit ball in IR^{d} by B = {x | ∥x∥ ≤ 1}, and the unit sphere by S = {x | ∥x∥ = 1}. The distance from the point x to the set X is

d(x, X) = inf_{y∈X} ∥x − y∥,

and for sets R and T in IR^{d},

e(R, T) = sup_{r∈R} d(r, T) = inf{ρ ≥ 0 | T + ρB ⊃ R}

is called the excess of R over T. An earlier version of the following theorem appeared in the unpublished report [7].

Theorem 2.1. Let C be a nonempty closed subset of IR^{d}. Then the following are equivalent:

(a) C is convex, rc C is polyhedral, and e[C, rc C] < +∞.

(b) There is a polyhedral convex cone Z such that for each positive ϵ there exists a finite collection { x_{1}, …, x_{k} } of points of IR^{d} so that with Q := conv { x_{1}, …, x_{k} } one has Q + Z ⊂ C ⊂ Q + Z + ϵB.

Further, if (b) holds then Z = rc C and the points x_{i} lie in C.

If (b) holds, we say that C can be approximated by a polytope. Here and later we use the term “polytope” interchangeably with “polyhedral convex set” to denote the intersection of finitely many closed halfspaces. (Thus the set P introduced just prior to (2.1) is not a polytope.) Let f^{∗} denote the convex conjugate of f, and for 0 ≤ a < ∞ write

L_{a} = L_{a}(f^{∗}) = {x | f^{∗}(x) ≤ a}.

Theorem 2.2. (Approximation) Assume that a > 0 and that

K := cone dom f is polyhedral  (H1)

(that is, K is the intersection of a finite collection of closed halfspaces). Then L_{a} can be approximated by a polytope.

When a > 0, the support function I_{L_{a}}^{∗} of L_{a} can be written as

I_{L_{a}}^{∗}(α) = cone (f + a)(α) := inf_{τ>0} τ^{−1}[f(τα) + a];  (2.6)

for details see Theorems 9.7 and 13.5 and Corollary 13.2.1 of [9]. If

For some a > 0 and each α ∈ K ∩ S the infimum in (2.6) is attained,  (H2)

we shall say later that f satisfies (H2) at a. We show in Lemma 3.2 below that if f satisfies (H2) at a then in fact it satisfies (H2) at every value in (0, a].

Theorem 2.3. (Separation) Let 0 < a < b < +∞. Assume that (H1) holds and that f satisfies (H2) at b. Then there is a positive δ such that

L_{a} + δB ⊂ L_{b}.  (2.7)

Corollary 2.4. (of Theorems 2.2 and 2.3) Under the hypotheses of Theorem 2.3 there exists a polytope V such that

L_{a} ⊂ V ⊂ L_{b}.  (2.8)

The hypothesis (H1) is an easily visualized geometric condition, but (H2) might be less easy to visualize. For that reason we state here a condition that is stronger than (H2) but is also more geometric. Its proof is given after Lemma 3.2 in Section 3.

Proposition 2.5. Let f be as above and let a > 0. If for some positive δ

L_{a} + δB ⊂ dom f^{∗},  (2.9)

then f satisfies (H2) at a.

2.2. Large deviation results

Finally, we use the above convexity results to prove (in Section 3 below) the following theorem.

Theorem 2.6. Let Λ(α) = log E exp⟨α, X_{1}⟩. Assume that Λ satisfies (H1) (i.e., that cone dom Λ is polyhedral) and that Λ satisfies (H2) at Λ^{∗}(F). Then the large deviation upper bound (1.2) holds for F.

Note that (H2) was used only to obtain the inclusions (2.7) and (2.8). To obtain the large deviation result (1.2) for closed F a variety of other sufficient conditions can be formulated (see Section 4 below). However, once the Cramér hypothesis is dropped, we know of no conditions that are specified simply and directly in terms of the measure μ or its generating function exp Λ( ·). The attractiveness of the present result is that it uses a simple condition on Λ, in terms of a well known quantity from convexity theory. We also point out that under the Cramér condition (C), cone dom Λ = IR^{d} so that (H1) holds for all d ≥ 1. In Section 4 some examples are given where the probabilistic quantities are identified.

3. Proofs

The proof of Theorem 2.1 is deferred to the end of this section. We start with three lemmas, the first two of which concern the function f of Subsection 2.1. The proof of Proposition 2.5 follows Lemma 3.2.

Lemma 3.1. Assume (H1). Then for some positive ϵ,

sup{f(α) | α ∈ K ∩ ϵB} =: A_{ϵ} < +∞.

Proof. As K is polyhedral by (H1), it has a finite set of generators, say g_{1}, …, g_{r}. As K = cone dom f there is no loss of generality in taking each g_{i} to be in dom f. Define a multifunction Γ from IR^{r} to IR^{d} by

Γ(λ) = \{ \begin{matrix}∑_{i=1}^{r} λ_{i}g_{i} & if λ_{1}, …, λ_{r} ≥ 0, \\ ∅ & otherwise. \end{matrix}

Then K = Γ(IR^{r}). By [8, Proposition 2] the set K ∩ B is contained in Γ(M) for some bounded subset M of IR^{r}. Accordingly, there is a positive constant ζ such that any k ∈ K can be written as k = ∑_{i=1}^{r} λ_{i}g_{i}, with each λ_{i} in the interval [0, ζ∥k∥]. Define ϵ = (rζ)^{−1}. If k ∈ K ∩ ϵB, then we can write k = ∑_{i=0}^{r} λ_{i}g_{i} with λ_{0} := 1 − ∑_{i=1}^{r} λ_{i} ∈ [0, 1] and g_{0} = 0. But then by convexity

f(k) ≤ ∑_{i=0}^{r} λ_{i}f(g_{i}) ≤ max_{i=0}^{r} f(g_{i}) =: A_{ϵ},

which proves Lemma 3.1.

Lemma 3.2. Let 0 < a < b < +∞. If f satisfies (H2) at b then it also satisfies (H2) at a.

Proof. If K is the origin then (H2) holds vacuously, so let α ∈ K ∩ S. By hypothesis there is some positive τ_{b} such that

cone (f + b)(α) = τ_{b}^{−1}[f(τ_{b}^{−1}α) + b].

For any positive τ we have

τ_{b}^{−1}[f(τ_{b}α)+a]+τ_{b}^{−1}(b−a) = τ_{b}^{−1}[f(τ_{b}α)+b] ≤ τ^{−1}[f(τα)+b] = τ^{−1}[f(τα)+a]+τ^{−1}(b−a),

so that

τ^{−1}[f(τα) + a] ≥ τ_{b}^{−1}[f(τ_{b}α) + a] + (τ_{b}^{−1} − τ^{−1})(b − a).

Accordingly, in seeking the infimum in the definition of cone (f + a)(α) we may restrict τ to the interval (0, τ_{b}]. Also, we assumed that f was lower semicontinuous with f(0) = 0. As a > 0 we see that

lim_{τ→0+} τ^{−1}[f(τα) + a] = +∞,

and so we may further restrict τ to [τ_{0}, τ_{b}], where τ_{0} is some small positive number. Now lower semicontinuity of f implies that the infimum of τ^{−1}[f(τα) + a] is attained.

Proof of Proposition 2.5. As before, the claim is vacuously true if K is the origin, so we can fix an element α ∈ K ∩ S. Recall that the recession function of f, which we write rec f, is the support function of dom f^{∗} [9, Theorem 13.3]. As we assumed f(0) = 0 we have

rec f(α) = sup_{τ>0} τ^{−1}[f(0 + τα) − f(0)] = sup_{τ>0} τ^{−1}f(τα),

and we note for future reference that this difference quotient is nondecreasing in τ [9, Theorem 23.1]. As cone (f + a) = I_{L_{a}}^{∗}, the hypothesis (2.9) yields

cone (f + a) + δ∥ · ∥ ≤ rec f.

From the definitions of cone (f +a) and rec f, we find that there are positive ρ and σ such that

ρ^{−1}[f(ρα) + a] < cone (f + a)(α) + δ/2, σ^{−1}f(σα) > rec f(α) − δ/2.

From the above inequalities we obtain

ρ^{−1}[f(ρα) + a] < σ^{−1}f(σα).

As the right-hand side is nondecreasing in σ, we see that ρ < σ and that whenever τ ≥ σ we have

ρ^{−1}[f(ρα) + a] < τ^{−1}f(τα) < τ^{−1}[f(τα) + a],

so in looking for the infimum in the definition of cone (f + a)(α) we need only consider τ ∈ (0, σ]. Now we can finish the proof as we did in Lemma 3.2.

The following lemma is related to more general results in the literature, but as we want a tailored form of the result and do not need the extra generality, we give a simple direct proof.

Lemma 3.3. Let C be a closed convex subset of IR^{n}. Then

e[C, rc C] = sup{ I_{C}^{∗}(α) | α ∈ B ∩ (rc C)^{∘} }.  (3.1)

Proof. Write Z for rc C. This cone is closed because C is closed [9, Theorem 8.2]. Denote by σ the supremum on the right side of (3.1). Choose any c ∈ C, and let z be the closest point in Z to c. Then c = z + ζ with z ∈ Z, ζ ∈ Z^{∘}, and ⟨z, ζ⟩ = 0. Evidently ∥ζ∥ = d[c, Z]. Suppose for the moment that ζ ≠ 0 and write ϕ = ζ/∥ζ∥. Then ϕ ∈ B∩Z^{∘}, and

d[c, Z] = ∥ζ∥ = ⟨ϕ, ζ⟩ = ⟨ϕ, c⟩ ≤ I_{C}^{∗}(ϕ) ≤ σ,

and d[c, Z] ≤ σ also in the case ζ = 0 because then c ∈ Z. Now by taking the supremum over c ∈ C we find that e[C, Z] ≤ σ. For the opposite inequality, let α ∈ B ∩ Z^{∘}. Let c ∈ C and let z and ζ be as above. Then

⟨α, c⟩ = ⟨α, z + ζ⟩ ≤ ⟨α, ζ⟩ ≤ d[c, Z],

where we used the Schwarz inequality and the fact that ∥ζ∥ = d[c, Z]. Now take the supremum over c ∈ C to obtain I_{C}^{∗}(α) ≤ e[C, Z], then the supremum over α ∈ B ∩ Z^{∘} to conclude that σ ≤ e[C, Z].

Proof of Theorem 2.2. We apply Theorem 2.1 to C = L_{a}, a closed convex set. By [9, Theorem 27.1(f)], we have rc L_{a} = K^{∘}. Under (H1) this cone is polyhedral. The equation (2.6) implies that I_{L_{a}}^{∗} ≤ f + a, and then Lemma 3.1 tells us that I_{L_{a}}^{∗}(α) has a finite supremum on K ∩ B (recall that this function is positively homogeneous). Then from Lemma 3.3 we obtain e[L_{a}, K^{∘}] < +∞, which implies that condition (a) of Theorem 2.1 is satisfied. The conclusion of Theorem 2.2 then follows from (b) of Theorem 2.1.

Proof of Theorem 2.3. If K is the origin then f = I_{{0}} and f^{∗} is identically zero, so the conclusion of the theorem holds. Therefore suppose K is not the origin; choose such a and b, and fix any α ∈ K ∩ S. Use the attainment hypothesis to find a positive t_{b} with

cone (f + b)(α) = t_{b}^{−1}[f(t_{b}α) + b].

Then

cone (f + a)(α) = inf_{t>0} t^{−1}[f(tα) + a] ≤ t_{b}^{−1}[f(t_{b}α) + a] < cone (f + b)(α).

Now for fixed a > 0 cone (f + a)(α) is closed [9, Theorem 9.7] and convex (as a function of α); its effective domain is K, which is polyhedral, and therefore it is continuous on K by [9, Theorem 10.2]. If a < b, then the difference cone (f + b) − cone (f + a) is a continuous, strictly positive function on the compact set K ∩ S. It must therefore have a positive minimum there, say δ. As cone (f + c) is positively homogeneous for each c, it follows that for each α ∈ K one has the inequality

cone (f + a)(α) + δ∥α∥ ≤ cone (f + b)(α).

But since cone (f + a) = I_{L_{a}}^{∗} and δ∥ · ∥ = I_{δB}^{∗}, it follows that L_{a} + δB ⊂ L_{b}.

Proof of Corollary 2.4. Note first that by (H2) and Theorem 2.3, for some positive δ

L_{a} + δB ⊂ L_{b}.  (3.2)

Theorem 2.2 says we can obtain a polytope V such that

V ⊂ L_{b} ⊂ V + δB.  (3.3)

Now (3.2) and (3.3) together imply L_{a} + δB ⊂ V + δB, which in turn implies the support function inequality

I_{L_{a}}^{∗} + δ∥ · ∥ ≤ I_{V}^{∗} + δ∥ · ∥.

Subtracting δ∥ · ∥ from both sides we obtain I_{L_{a}}^{∗} ≤ I_{V}^{∗}, and as V is closed this implies that L_{a} ⊂ V. Combining this with (3.3), we obtain (2.8).

Proof of Theorem 2.6. Choose any closed subset F of IR^{d} and let a = Λ^{∗}(F). The bound (1.2) holds trivially if a = 0, so we may assume a > 0. Our hypotheses, together with Corollary 2.4, imply that for any η ∈ (0, a) we can find a polytope V satisfying

L_{η} ⊂ V ⊂ L_{a}.  (3.4)

We show that we then have (2.1), and the argument of Section 2 then completes the proof. Let ϵ ∈ (0, a) and choose η ∈ (a − ϵ, a). By Lemma 3.2, Λ satisfies (H2) at η, and then by Theorem 2.3 we have for some positive γ and for the V given by (3.4) the inclusion

L_{a−ϵ} + γB ⊂ L_{η} ⊂ V,  (3.5)

so that V must have nonempty interior. If we write V = ∩_{i=1}^{N}C_{i}, where the C_{i} are closed halfspaces whose corresponding interiors (open halfspaces) we denote by H_{i}, we have int V = ∩_{i=1}^{N}H_{i} by [9, Theorem 6.5]. Then (3.4) and (3.5) imply

L_{a−ϵ} ⊂ int L_{η} ⊂ int V ⊂ V ⊂ L_{a},

so that we have (2.1).

Proof of Theorem 2.1.

(a) implies (b): Write Z for rc C. Lemma 3.3, together with our finiteness assumption on e[C, Z], tells us that the effective domain dom I_{C}^{∗} of the support function I_{C}^{∗} is exactly Z^{∘} (we always have cl dom I_{C}^{∗} = Z^{∘}; the point is that here we can remove the closure symbol). But Z^{∘} is polyhedral (because Z was assumed to be), hence locally simplicial. Therefore [9, Theorem 10.2] tells us that I_{C}^{∗} is continuous on Z^{∘}. Now fix ϵ > 0. For each c ∈ C define Ψ_{c} = { α ∈ Z^{∘} ∩ S | I_{C}^{∗}(α) ≥ ⟨α, c⟩ + ϵ }. Recall that for each α ∈ IR^{n}, I_{C}^{∗}(α) is the pointwise supremum of the linear functions ⟨α, c⟩ for c ∈ C. Therefore the intersection of the Ψ_{c} over c ∈ C is empty. But the Ψ_{c} are compact sets because I_{C}^{∗} is continuous on Z^{∘}, so there is a finite subset { c_{1}, …, c_{k} } of C such that the intersection of the Ψ_{c_{i}} for i = 1, …, k is empty. Therefore, for each α ∈ Z^{∘} there is at least one index i with I_{C}^{∗}(α) ≤ ⟨α, c_{i}⟩ + ϵ∥α∥. Writing s(α) = sup_{i=1}^{k}⟨α, c_{i}⟩, we have I_{C}^{∗} ≤ s + ϵ∥ · ∥ + I_{Z^{∘}}; note that we have used here the fact that the effective domain of I_{C}^{∗} is exactly Z^{∘}. But s is the support function of the set Q := conv { c_{1}, …, c_{k} }, ϵ∥ · ∥ is the support function of ϵB, and I_{Z^{∘}} = I_{Z}^{∗} is the support function of Z. Writing P = Q + Z, we have C ⊂ P + ϵB; note that the sum on the right is closed because Q + ϵB is compact and Z is closed. But P ⊂ C because Q ⊂ C and Z = rc C.

(b) implies (a): Let ϵ > 0 and suppose that Q and Z are as stated in (b). Write P = Q + Z; then as P + ϵB is closed and convex we have P ⊂ C ⊂ cl conv C ⊂ P + ϵB; accordingly, e[cl conv C, C] ≤ e[P + ϵB, P] = ϵ. As ϵ was arbitrary and C is closed, we have C = cl conv C and hence C is convex. Again, because the sets involved are closed, the inclusion P ⊂ C ⊂ P + ϵB implies rc P ⊂ rc C ⊂ rc (P + ϵB) = rc P, and therefore rc C = rc P = Z, which is polyhedral. Finally, the triangle inequality for the excess e[ · , ·] implies that e[C, rc C] ≤ e[C, P + ϵB] + e[P + ϵB, rc C]. The first term on the right is zero; the second is e[Q + ϵB + Z, Z], which is obviously finite. This proves (a). For the final claim, note that we have already shown, under (b), that Z = rc C. As 0 ∈ Z and Q + Z ⊂ C we have Q ⊂ C, so the x_{i} lie in C.

4. Examples and remarks

In this section we first give three examples, the first illustrating a situation in which the Cramér condition fails but our hypotheses apply. The second is a situation in which our hypothesis (H2) is satisfied for some but not all a, and some but not all level sets separate, but in which the Cramér condition is satisfied (so that the large deviation upper bound holds). Thus, separation of level sets is not a necessary condition for (1.2). The third example is a situation in which our hypotheses are not satisfied and in which we do not know whether or not the large deviation upper bound holds. We then conclude with some brief remarks on a possible extension of our approach.

Example 4.1. Λ is not finite on a neighborhood of the origin (i.e., the Crámer condition fails), but Theorem 2.6 applies. A specific case illustrating this is Example 2.2 of Dinwoodie [4]: μ on IR^{2} is the direct product of a normal and a Cauchy distribution. Here clearly 0 ∉ int dom Λ, but Theorem 2.6 holds. More generally, if μ is any measure on IR^{d} such that the convex hull of its support is all of IR^{d}, then dom Λ^{∗} = IR^{d}, so by Proposition 2.5 Λ satisfies (H2) for all a. If in this situation d = 2 and the cone generated by dom Λ is any closed cone that is not all of IR^{2} (e.g., the closed negative quadrant) then the Cramér condition fails. However, Theorem 2.6 applies because (H1) holds (any closed convex cone in IR^{2} is trivially polyhedral). This would be the case, for instance, if μ is the mixture of a Gaussian measure on IR^{2} with any measure whose support is the positive quadrant and which has “large” tails.

Example 4.2. Λ satisfies (H2) for some but not all a, some but not all level sets separate, but the large deviation upper bound (1.2) still holds. Consider the simple binomial distribution P {X_{1} = 1} = 1 − P {X_{1} = 0} = 1/3. In this case Λ(α) = log(2 + e^{α}) − log 3, and

Λ^{∗}(x) = \{ \begin{matrix}x log x + (1 − x) log(1 − x) − (1 − x) log 2 + log 3 & if 0 ≤ x ≤ 1, \\ +∞ & otherwise. \end{matrix}

As dom Λ = IR, the Cramér condition (C) applies, so (1.2) holds. The effective domain of Λ^{∗} is the interval [0, 1]; we have Λ^{∗}(0) = log(3/2) and Λ^{∗}(1) = log 3, and the graph has a vertical tangent at each of these points. Let ξ_{b}(s) = s^{−1}[Λ(s) + b]. Then

cone (Λ + b)(α) = \{ \begin{matrix}α inf_{s>0} ξ_{b}(s) & if α ≥ 0, \\ α inf_{s<0} ξ_{b}(s) & if α < 0. \end{matrix}

If b ∈ (0, log(3/2)) then (H2) must hold (use the Proposition), and the level sets of Λ^{∗} separate. If b = log(3/2) then (H2) does not hold because the infimum of ξ_{b}(s) for s < 0 is not attained; however, the separation condition (2.7) does hold. For b > log(3/2) (H2) cannot hold because the level sets of Λ^{∗} separate on the right (near 1) only.

Example 4.3. The hypotheses of Theorem 2.6 are not satisfied. Let Z be a Cauchy random variable in IR and let X = (Z, Z^{2}) ∈ IR^{2}. Then

dom Λ = {(α_{1}, α_{2}) ∈ IR^{2} | α_{2} < 0 or (α_{1}, α_{2}) = (0, 0)}.

This is not a closed cone (hence not polyhedral), so (H1) is violated. One can show in this case (with a fair amount of calculating) that Corollary 2.4 fails: that is, the level sets of Λ^{∗} cannot be separated by polyhedra. We do not know whether the large deviation upper bound holds in this case for all closed sets. We conclude by sketching a possible extension of the approach we have taken. Note that in this paper the set F in the upper bound (1.2) has been quite arbitrary, e.g. not necessarily closed. Suppose we now add the condition that F is closed, and write F = (F ∩ tB) ∪ (F ∩ tB^{c}), where B is the unit ball, and t is to be thought of as “large.” Then

P {S_{n}/n ∈ F } = P {S_{n}/n ∈ F ∩ tB} + P {S_{n}/n ∈ F ∩ tB^{c}}.

Since F ∩ tB is compact, (1.2) is known to hold for this set. As Λ^{∗}(F ∩ tB) ≥ Λ^{∗}(F), it suffices to prove that (1.2) holds for F ∩ tB^{c} for some finite t. One could attack this problem by separation methods analogous to those used here, modified to take advantage of the fact that the set F ∩ tB^{c} contains only elements far from the origin. However, that is beyond the scope of this paper.

References

[1] H. Cramér: On a new limit theorem in the theory of probability, in Colloquium on the Theory of Probability, Hermann, Paris, 1937.

[2] A. Dembo, O. Zeitouni: Large Deviations Techniques and Applications, Jones and Bartlett, Boston, 1993.

[3] J. D. Deuschel, D. W. Stroock: Large Deviations, Academic Press, Boston, 1989.

[4] I. H. Dinwoodie: A note on the upper bound for i.i.d. large deviations, Annals of Probability 19, 1991, 1732–1736.

[5] L. Hörmander: Sur la fonction d’appui des ensembles convexes dans un espace localement convexe, Arkiv för Matematik 3, 1955, 181–186.

[6] H. Rådström: An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. 3, 1952, 165–169.

[7] S. M. Robinson: An embedding theorem for unbounded convex sets, Technical Summary Report 1321, Mathematics Research Center, University of Wisconsin–Madison, Madison, WI, 1973.

[8] S. M. Robinson: Some continuity properties of polyhedral multifunctions, Mathematical Programming Study 14, 1981, 206–214.

[9] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

[10] M. Slaby: On the upper bound for large deviations for sums of i.i.d. random vectors, Annals of Probability 16, 1988, 978–990.

[11] S. R. S. Varadhan: Large Deviations and Applications, CBMS–NSF Regional Conference Series in Applied Mathematics No. 46, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1984.