Mathematical Foundations for Signal Processing, Communications, and Networking

Chapter 9    Large Deviations

Hongbin Li^‡

^‡ Stevens Institute of Technology, USA

9.1      Introduction

The theory of large deviations is concerned about the probabilities of rare events. Consider, for example, tossing a fair die n times. There are 6 possible outcomes per toss and a total of 6ⁿ possible outcomes. What is the probability of the average of the throws being close to $\frac{1+2+3+4+5+6}{2}=3.5?$ This is a small deviation event for large n, since by the law of large numbers, the probability is close to 1 and, in average, each face of the die appears about n/6 times. What is the probability of the average of the throws being about 4, or the probability of getting each of faces 1 to 5 with about 1 percent of the throws and face 6 with ...