Upper bounds on probabilities of large deviations for sums of bounded independent random variables may be extended to handle functions which depend in a limited way on a number of independent random variables. This ‘method of bounded differences’ has over the last dozen or so years had a great impact in probabilistic methods in discrete mathematics and in the mathematics of operational research and theoretical computer science. Recently Talagrand introduced an exciting new method for bounding probabilities of large deviations, which often proves superior to the bounded differences approach. In this chapter we introduce and survey these two approaches and some of their applications.
Weitere Kapitel dieses Buchs durch Wischen aufrufen
- Springer Berlin Heidelberg
Neuer Inhalt/© ITandMEDIA