12. Tail inequalities

views comments

What are tail inequalities?
Markov's inequality: Pr[ X > x ] ≤ E[X} / x
Independent random variables
Chebyshev: If X is sum of pairwise-independent 0/1 variables: E[ (X–μ)^2 ] ≤ μ
...and therefore Pr[ (X–μ)^2 > z ] ≤ μ/z
...and therefore Pr[ X > (1+δ)μ ] < 1/δ^2μ for any δ>0
Exponential moment: If X is sum of fully independent 0/1 variables: E[ α^X ] ≤ e^((α–1)μ) for all α>1
...and therefore Pr[ X>x } ≤ e^{x-μ) (μ/x)^x
...and therefore Pr[ X > (1+δ)μ ] < e^(-δ^2μ/3) for any δ>0
Treaps are shallow with high probability
Review of midterm 1 problem 3

	Contact Technology Services to report an issue, offer feedback, or request assistance.
	Technology Services Home \| Kaltura Help \| Privacy Policy
	Illinois Media Space, © 2022 Board of Trustees of the University of Illinois