1.3. LDP BY SUB-ADDITIVITY 19

1.3. LDP by sub-additivity

A random sequence {Yn}n≥1 is said to be sub-additive, if for any n, m ≥ 1, there

is a random variable Ym such that

Yn+m ≤ Yn + Ym,

Ym

d

= Ym and Ym is independent of {Y1, · · · , Yn}.

In particular, a deterministic sub-additive sequence {a(n)} is defined by the

inequality a(n + m) ≤ a(n) + a(m).

Lemma 1.3.1. For any deterministic sub-additive sequence {a(n)}, the equality

lim

n→∞

n−1a(n)

= inf

m≥1

m−1a(m)

holds in the extended real line [−∞, ∞).

Proof. All we need is to show that

lim sup

n→∞

n−1a(n)

≤ inf

m≥1

m−1a(m).

(1.3.1)

Let m ≥ 1 be fixed but arbitrary. For any big n, write n = km + r, where k ≥ 1

and 0 ≤ r m are integers. By sub-additivity,

a(n) ≤ ka(m) + a(r).

Consequently,

lim sup

n→∞

n−1a(n)

≤

m−1a(m).

Taking infimum over m on the right hand side leads to (1.3.1).

Given a sub-additive random sequence {Yn}n≥1 and θ 0, we have that

E exp θYn+m ≤ E exp θYn E exp θYm .

Consequently,

a(n) ≡ log E exp θYn n = 1, 2, · · ·

is a deterministic sub-additive sequence. Consequently, we have the following corol-

lary.

Corollary 1.3.2. Let {Yn}n≥1 be sub-additive. For any θ 0, the equality

lim

n→∞

1

n

log E exp θYn = inf

m≥1

1

m

log E exp θYm

holds in the extended real line [−∞, ∞].

In the following theorem, we establish exponential integrability for Yn.

Theorem 1.3.3. Let {Yn} be a sub-additive random sequence such that Y1 ≤ C

a.s. for some constant C 0. Let cn ≥ 1 be a deterministic sequence such that the

normalized sequence

max

k≤n

Yk/cn n = 1, 2, · · ·