In the mini-course to come, we will go through lots of concentration inequalities. There is a unite way to think about them which I will try to explain in this post.
Consider a sequence of i.i.d. random variables Consider their empirical mean
The interesting point about it is that for any (so, in a sense, the scaling is natural), but concentrates above its mean:
In fact, as we will see in the next post,
i.e. with exponentially high probability.
This is the simplest example of the concentration of measure phenomenon, when a function which is weakly dependent on many independent random variables concentrates around its mean or median. A collateral goal of the course is to observe similar properties in different settings: with broader classes of functions (Lipschitz functions, norms, quadratic forms, etc.), distributions of and mutual dependency in the sequence e.g. martingales.