Seminar Concentration Inequalities

Contents

If you throw a coin once, then the outcome is impossible to predict: it may come up heads or tails, and, unless your coin is manipulated, it will do either way more or less half of the time. On the other hand, although we cannot say much for individual throws, if you throw your coin, say, 1.000.000 times, then we can say something: it will come up head roughly 500.000 times; more precisely, the fraction of throws that come up heads will be be very close to 1/2.

Actually, we can say much more: the probability that the number of heads is 'far away' from 500.000 is extremely small - exponentially small in the deviation. This is a very strong property, as it guarantees that in the whole universe, even if we had started at the beginning of times to throw coins, then we would never have observed a large deviation.

The topic of this book studies 'concentration of measure', which is nothing else than the study of large deviations in random experiments. Coin tossing is a very simple scenario, but the property of extremely small probabilities for large deviations is omnipresent. However, a rigorous study of it is complex, and it is a rich mathematical topic.


For further information please use the moodle with the code 'ConcInSS24' to subscribe or contact Prof. Dr. Konstantinos Panagiotou via email.