BernsteinUngleichung

The Bernstein inequality is a fundamental result in probability theory that provides an upper bound on the probability that the sum of independent and identically distributed random variables deviates from its expected value. More specifically, for a sum of independent random variables $X_1, X_2, \dots, X_n$ with $E[X_i] = 0$ for all $i$, the Bernstein inequality states that for any $\epsilon > 0$,

$P(\sum_{i=1}^n X_i \ge \epsilon) \le \exp\left(-\frac{\epsilon^2/2}{\text{Var}(S_n) + \frac{\epsilon}{3} M}\right)$

where $S_n = \sum_{i=1}^n X_i$, $\text{Var}(S_n)$ is the variance of the sum, and $M$ is a constant related to the maximum possible value of the random variables. A simpler version often seen assumes the random variables are bounded. In such cases, for $E[X_i] = 0$ and $|X_i| \le M$ for all $i$, the inequality simplifies.

The Bernstein inequality is particularly useful in scenarios where one needs strong concentration bounds, such as in machine learning and statistics. It offers a tighter bound than Markov's inequality or Chebyshev's inequality when the underlying random variables have certain properties, especially boundedness or exponential moments. This allows for more precise statements about the likelihood of deviations in sums of random processes, which is crucial for analyzing algorithms and statistical procedures. The inequality has various forms and generalizations depending on the assumptions made about the random variables.