ABSTRACT
This chapter aims to some basic large deviation concepts and techniques including concentration inequalities, rate function, Cramer's theorem, type analysis, and Sanov's theorem. It considers hypothesis testing and presents large deviation results pertaining to the error exponents of several standard hypothesis testing methods. The chapter discusses some fundamental concentration inequalities. Large deviation techniques offer simple and insightful ways to compute the decaying rate of rare event probabilities, and have found numerous applications in communication and computer networks, sensing systems, computational biology, statistical mechanics, and risk analysis. Sanov's theorem is one such result that determines the probability of a set of nontypical types. The chapter also considers applications of large deviation analysis for hypothesis testing which is frequently encountered in various sensing, communication, and medical testing systems.
