20 1. BASICS ON LARGE DEVIATIONS

is stochastically bounded. Then there is a θ 0 such that

sup

n

E exp θYn/cn ∞. (1.3.2)

Furthermore, if

lim inf

n→∞

cmn/cn 1 (1.3.3)

for some m 1, then (1.3.2) holds for all θ 0.

Proof. We first show that for any s, t 0 and n ≥ 1,

max

1≤k≤n

P Yk ≥ s + t + C ≤ P max

1≤k≤n

Yk ≥ s max

1≤k≤n

P Yk ≥ t . (1.3.4)

Set

Ts = inf j ≥ 1; Yj ≥ s .

Notice that for any j ≥ 1,

Yj − Yj−1 ≤ Y1

d

= Y1 ≤ C a.s.

For any 1 ≤ k ≤ n,

P Yk ≥ s + t + C = P Ts ≤ k − 1; Yk ≥ s + t + C

≤

k−1

j=1

P Ts = j, Yk − Yj−1 ≥ t + C ≤

k−1

j=1

P Ts = j, Yk − Yj ≥ t

where the second step follows from the fact that YTs−1 ≤ s. By sub-additivity,

Yk − Yj ≤ Yk−j

d

= Yk−j and Yk−j is independent of {Ts = j}. Therefore,

P Yk ≥ s + t + C ≤

k−1

j=1

P Ts = j P Yk−j ≥ t

≤ P Ts ≤ n max

1≤k≤n

P Yk ≥ t = P max

1≤k≤n

Yk ≥ s max

1≤k≤n

P Yk ≥ t .

Taking maximum over k on the left hand side leads to (1.3.4).

For any N 0 and integers m, n ≥ 1, by (1.3.4),

max

1≤k≤n

P Yk ≥ m(Ncn + C) ≤ P max

1≤k≤n

Yk ≥ Ncn

m

.

In particular,

P Yn ≥ m(Ncn + C) ≤ P max

1≤k≤n

Yk ≥ Ncn

m

.

By assumption, one can make N 0 suﬃciently large, so that

P max

1≤k≤n

Yk ≥ Ncn ≤

e−2

n = 1, 2, · · · .

Therefore,

sup

n≥1

P Yn ≥ m(Ncn + C) ≤

e−2m

m = 1, 2, · · · .