Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Food For Thought Seminar

Paul Horn

UCSD

Concentrate Harder: Concentration inequalities and their use in probabilistic combinatorics.

Abstract:

\indent When dealing with random variables, we are often concerned with their expected value - what we expect them to be. But often this isn't enough; we don't just want to know the expectation, but we are concerned with how close to the expectation our random variable is likely to be. Here is where concentration inequalities come into play: we wish to bound the probability that a random variable differs greatly from it's mean. The use of the inequalities of Markov, Chebyshev, Chernoff, Azuma and beyond have become key fixtures in arguments in probabilistic combinatorics. In this talk we attempt to survey these inequalities, and provide some beautiful (and hopefully illuminating) examples of their use from the literature (and, perhaps, some examples from my 'day job'.) Plus, I will attempt to spell Tchebycheff a different way every time I write it.

October 16, 2008

11:00 AM

AP&M B412

****************************