Basic tail and concentration bounds

C H A P T E R21 Basic tail and concentration bounds2In a variety of settings, it is of interest to obtain bounds onthe tails of a random3variable, or two-sided inequalities that guarantee that a random variable is close to its4mean or median. In this chapter, we explore a number of elementary techniques for5obtaining both deviation and concentration is an entrypoint to more6advanced literature on large deviation bounds and concentration of Classical bounds8 One way in which to control a tail probabilityP[X t] is by controlling the moments of9the random variableX. Gaining control of higher-order moments leads to correspond-10ingly sharper bounds on tail probabilities, ranging from Markov s inequality (which11requires only existence of the first moment) to the Chernoff bound (which requires12existence of the moment generating function).13 From Markov to Chernoff14 The most elementary tail bound isMarkov s inequality: given a non-negative randomvariableXwith finite mean, we haveP[X t] E[X]tfor allt >0.

(2.5) 1 As we explore in Exercise 2.3, the moment bound (2.3) with the optimal choice of kis 2 never worse than the bound (2.5) based on the moment-generating function. Nonethe-3 less, the Chernoff bound is most widely used in practice, possibly due to the ease of 4 manipulating moment generating functions. Indeed, a variety of important tail ...

Loading..

Information

Related search queries