Probability and Statistics - shivamvats/notes GitHub Wiki
-
Law of Large Numbers: The sample average, i.e. results from performing an experiment repeatedly gets closer to the expected value as the sample size gets larger (perform more experiments). Exceptions: Cauchy distribution (doesn't have an expected value) and Pareto distributions (expectation is infinite).
-
Central Limit Theorem: The law of large numbers tells us that
u -> mu
asymptotically, whereu
is the sample average andmu
is the expectation. But how does the erroru - mu
behave? The Central Limit Theorem says that the error approximately behaves normally:sqrt(n)(u - mu) -(in distribution)> N(0, sigma^2)
-
Gilvenko-Cantelli Theorem: The empirical CDF converges to the true CDF with enough data.
-
Markov's Inequality: If the mean of a +ve random variable is small, its probability mass can't go too far from it.
Pr(X >= t) <= EX/t
-
Chebyshev's Inequality: Builds on Markov's inequality. The probability of a random variable X deviating by
k x std
from its mean is upper bounded by``1/k^2``.Pr(|X - mu| >= k x std) <= 1/k^2
-
Chernoff Method: Give a tighter upper bound than Chebyshev's Inequality.
-
Gaussian and Sub-Gaussian Tail Bounds: For Gaussians and sub-Gaussians:
Pr(|X - mu| >= k x std) <= 2 x exp(-k^2/2)
orPr(|X - mu| >= u) <= 2 x exp(-u^2/2(std)^2)
Note that this is much tighter than the more general Chebyshev's inequality.
-
Log-normal Distribution: If
x
is distributed as a normal distribution, thenu = ln(x)
is distributed as a log-normal distribution. Ifu
has a distributionA(mu, sigma^2)
, theny = e^a u^b
is distributed asA(a + bmu, b^2 sigma^2)
.