inequalities Hoeffding’s Inequality Given n ( n > 0 ) n(n>0) n ( n > 0 ) i.i.d. random variables X 1 , X 2 , . . . , X n ∼ i i d X_1,X_2,...,X_n \overset{iid}{\sim} X 1 , X 2 , . . . , X n ∼ i i d that are almost surely bounded – meaning P ( X ∉ [ a , b ] ) = 0 \mathbf{P}(X \notin [a,b])=0 P ( X ∈ / [ a , b ] ) = 0 : P ( ∣ X n ˉ − E [ X ] ∣ ≥ ϵ ) ≤ 2 exp ( − 2 n ϵ 2 ( b − a ) 2 ) for all ϵ > 0 \mathbf{P}\left(\left| \bar{X_n} - \mathbb{E}[X]\right| \ge \epsilon\right) \le 2 \exp\left(-{2n\epsilon^2 \over (b-a)^2}\right) \qquad \text{for all }\epsilon \gt 0 P ( ∣ ∣ X n ˉ − E [ X ] ∣ ∣ ≥ ϵ ) ≤ 2 exp ( − ( b − a ) 2 2 n ϵ 2 ) for all ϵ > 0 Unlike for the central limit theorem, here the sample size n n n does not need to be large. Markov inequality For a random variable X ≥ 0 X\ge 0 X ≥ 0 with mean μ > 0 \mu \gt 0 μ > 0 , and any number t > 0 t \gt 0 t > 0 : P ( X ≥ t ) ≤...