Large Deviations Theory (cont.)

Advanced Stochastic Processes. LECTURE 4 Large Deviations theory continued Outline of Lecture • Large deviations lower bound. • Examples. • Bankruptcy problem. 4.1. Large deviations lower bound We have established an upper bound on the probability of large deviations � 1≤i≤n Xi P( > a) ≤ e−l(a)n , n where l(a) = supθ (aθ − log M (θ)) = aθ∗ − log M (θ∗ ) is the Legendre transform corresponding to the distribution of random variable X1 . Perhaps the most surprising result of the theory of large deviations is that this upper bound is tight. The following theorem states that. The course packet contains the proof on pages 15-17. It involves an important and useful technique called change of measures. Theorem 4.1. Given an i.i.d. sequence X1 , . . . , Xn , . . ., suppose E[eθX1 ] < ∞ for all θ in some interval [0, θ0 ). Let a > E[X1 ]. Then for every � > 0 there exists a sufficiently large n0 such that for all n > n0 � 1≤i≤n Xi P( > a) ≥ e−(l(a)−�)n , n where l(a) = aθ∗ − log M (θ∗ ) is the Legendre transform corresponding to the distribution of X1 . Theorem 3.4 from the previous lecture and Theorem 4.1 can be combined into the following result. 1 2 Theorem 4.2. Given an i.i.d. sequence X1 , . . . , Xn , . . ., suppose E[eθX1 ] < ∞ for θ ∈ [0, θ0 ). Let a > E[X1 ]. Then P lim log P( 1≤i≤n Xi n n n→∞ > a) = −l(a). P Equivalently, we say that the probability of large deviations satisfies P( −l(a)n+o(n) e when n is large. 1≤i≤n n Xi > a) = 4.2. Examples Let us go over the examples of some distributions and compute their corresponding Legendre transforms. • Exponential distribution with parameter λ. Recall that M (θ) = λ/(λ − θ) when θ < λ and M (θ) = ∞ otherwise. Therefore when θ < λ λ ) λ−θ θ = sup(aθ − log λ + log(λ − θ)). l(a) = sup(aθ − log θ Setting the derivative of g(θ) = aθ − log λ + log(λ − θ) equal to zero we obtain the equation a − 1/(λ − θ) = 0 which has the unique solution θ∗ = λ − 1/a. Therefore l(a) = a(λ − 1/a) − log λ + log(λ − λ + 1/a) = aλ − 1 − log λ + log(1/a) = aλ − 1 − log λ − log a. Let us see the meaning of this expression. First note that the function l(a) is indeed convex: For large deviations regime we need to consider a > 1/λ. When a = 1/λ, we obtain l(a) = 0 giving e−l(a)n = 1 - useless bound. However, when a is bigger than 1/λ, l(a) becomes bigger than zero (this involves a tradeoff between increasing the linear function aλ and decreasing the function log(1/a), but one can show that the first one ”beats”), and the bound becomes meaningful. The large deviations bound then tells us that when a > 1/λ � 1≤i≤n Xi P( > a) ≈ e−(aλ−1−log λ−log a)n . n Say λ = 1 and a = 1.2. Then the approximation gives us ≈ e−(.2−log 1.2)n . On the other hand recall that the process X1 , X1 + X2 , . . . , X1 + X2 · · · + Xn , . . . is�a Poisson process with parameter λ = 1. Therefore we can compute the probability P( 1≤i≤n Xi > 1.2n) exactly: it is the probability that the Poisson process has at most n − 1 events before LECTURE 4. LARGE DEVIATIONS time 1.2n. Thus � P( 1≤i≤n Xi n > 1.2) = P( � 3 Xi > 1.2n) 1≤i≤n = � (1.2n)k −1.2n e . k! 0≤k≤n−1 It is not at all clear how revealing this expression is. In hindsight, we know that it is approximately e−(.2−log 1.2)n , obtained via large deviations theory. θ2 • Standard Normal distribution. Recall that M (θ) = e 2 when X1 has the standard Normal distribution. The expected value µ = 0. Thus we fix a > 0 and obtain θ2 l(a) = sup(aθ − ) 2 θ 2 a = , 2 ∗ achieved at θ = a. Again we see that l(a) is (as it should be) a convex function of a. Thus for a > 0, the large deviations theory predicts that � a2 1≤i≤n Xi > a) ≈ e− 2 n . P( n P Xi Again we could compute this probability directly. We know that 1≤in≤n is distributed as a Normal random variable with mean zero and variance 1/n. Thus � √ � ∞ t2 n n 1≤i≤n Xi P( > a) = √ e− 2 dt. n 2π a After a little bit of technical�work one could show that this integral is ”dominated” by a+� its part around a, namely, a ·, which is further approximated by the value of the function itself at a, namely √ a2 n √ e− 2 n . 2π This is consistent with the value given by the large deviations theory. Simply the lower order magnitude term approximation on the log scale. √ n √ 2π disappears in the • Poisson distribution. Suppose X has a Poisson distribution with parameter λ. Recall θ that in this case M (θ) = ee λ−λ . Then l(a) = sup(aθ − (eθ λ − λ)). θ Setting derivative to zero we obtain θ∗ = log(a/λ) and l(a) = a log(a/λ) − (a − λ). In this case as well we can compute the large deviations probability explicitly. The sum X1 + · · · + Xn of Poisson random variables is also a Poisson random variable with parameter λn. Therefore � � (λn)m P( Xi > an) = e−λn . m! m>an 1≤i≤n But again it is hard to infer a more explicit rate of decay using this expression 4 4.3. Applications 4.3.1. Insurance bankruptcy problem Imagine an insurance company which has capital x at time t = 0. During periods t = 1, 2, . . . it pays claims � in the amount of Yt ≥ 0. The wealth receives revenues Xt ≥ 0 from premiums and� of the company at time t is then St � x + 1≤i≤t Xi − 1≤i≤t Yt . The company is declared bankrupt if at some point St ≤ 0 (no borrowing is allowed). Assume X1 , . . . , Xt , . . . is i.i.d. and Y1 , . . . , Yt , . . . is also i.i.d. with expected values E[X1 ], E[Y1 ], respectively and also that the two processes are independent of each other. How likely is it that the bankruptcy occurs? Namely, what is P(inf t≥0 St < 0)? This problem is also known as Gambler’s ruin problem. It can be solved exactly when Xt , Yt take values 0, 1. In more general case solution becomes quite messy. Here we use large deviations type bounds to obtain simple bounds on the bankruptcy probability. But first we rule out some cases. P Xi −Yi says that 1≤i≤tt converges almost surely to E[X1 ]−E[Y1 ]. Suppose E[X1 ] < E[Y1 ]. The SLLN� Therefore, almost surely, the sum 1≤i≤t Xi − Yi becomes smaller than any fixed value including starting capital x. Therefore inf t≥0 St = −∞ almost surely. We conclude that the bankruptcy probability is P(inf t≥0 St < 0) = 1 The case E[X1 ] = E[Y1 ] will be analyzed later when we study Brownian motion. Now we focus on the case of interest: E[X1 ] > E[Y1 ]. Our goal is to show that, provided the corresponding exponential moment generating functions E[eθX1 ], E[eθY1 ] are finite in some common interval [0, θ0 ), the bankruptcy probability is order e−cx for some constant c > 0. Namely, it is exponentially unlikely as a function of the starting capital x. For simplicity introduce Zt = Yt −Xt . Then Zt , t ≥ 0 is an i.i.d. sequence with µ � E[Z1 ] < 0. Note that whenever θ ∈ [0, θ0 ), we have M (θ) � E[eθZ1 ] = E[eθY1 ]E[e−θX1 ] ≤ E[eθY1 ] < ∞. Here we use the fact e−θX1 ≤ 1. Now we fix t and consider � P(St < 0) = P(x − Zi < 0) = P( � 1≤i≤t Zi > x). 1≤i≤t We let at = x/t. We have at > 0 > µ ∀ t. Then the Chernoff bound (Theorem 4.2) tells us that this probability is ≤ e−l(at )t , where l(at ) is the Legendre transform l(at ) = supθ (at θ − log M (θ)). Now since µ < 0, then by Proposition 2 from Lecture 3, there exists θ∗ ∈ [0, θ0 ) such that l(0) = 0θ∗ − log M (θ∗ ) = − log M (θ∗ ) > 0. Using this value θ = θ∗ we obtain l(at ) ≥ at θ∗ − log M (θ∗ ) ∀ t implying for all t, P(St < 0) ≤ e−at θ ∗ t+log M (θ ∗ )t = e−θ ∗ x+log M (θ ∗ )t . LECTURE 4. LARGE DEVIATIONS Therefore P(inf St < 0) ≤ t≥0 � 5 P(St < 0) t≥0 ≤ � e−θ ∗ x+log M (θ ∗ )t t≥0 = � ∗ e−θ x M (θ∗ )t t≥0 ∗ e−θ x = , 1 − M (θ∗ ) (which probability law are we using in the first inequality?) where the finiteness of the ratio is guaranteed since log M (θ∗ ) < 0. We see that indeed the bankruptcy probability decays at least ∗ with the rate e−θ x . This is not necessarily the optimum rate as we did not optimize over θ (did we?) and moreover we did not prove a matching lower bound. Usually, in applications as in this one, the upper bound is more important. 4.4. Additional reading materials • Course packet Sections 1.2-1.5 . • Dembo and Zeitouni [1] Section 2.1 and 2.2 . The large deviations theorems in our lecture notes are called Cramer’s bounds in this book. The first section discusses the method of types and gives a information-theoretic take on large deviations theory.