Tail Inequalities

Rajeev Motwani, Prabhakar RaghavanCambridge 1995 · DOI · OpenAlex

Abstract

IN this chapter we present some general bounds on the tail of the distribution of the sum of independent random variables, with some extensions to the case of dependent or correlated random variables. These bounds are derived via the use of moment generating functions and result in “Chernoff-type” or “exponential" tail bounds. These Chernoff bounds are applied to the analysis of algorithms for global wiring in chips and routing in parallel communications networks. For applications in which the random variables of interest cannot be modeled as sums of independent random variables, martingales are a powerful probabilistic tool for bounding the divergence of a random variable from its expected value. We introduce the concept of conditional expectation as a random variable, and use this to develop a simplified definition of martingales. Using measure theoretic ideas, we provide a more general description of martingales. Finally, we present an exponential tail bound for martingales and apply it to the analysis of an occupancy problem.
BibTeX
@inproceedings{motwani1995tail,
  author = {Rajeev Motwani and Prabhakar Raghavan},
  title = {{Tail Inequalities}},
  booktitle = {Cambridge},
  year = {1995},
  doi = {10.1017/cbo9780511814075.005},
}

Loading related content...

Figure