Markov's inequality

Markov's inequality bounds the probability that a nonnegative random variable is at least a positive threshold by its expectation divided by that threshold.

Expected value: The probability-weighted average of a random variable's possible values. The inequality uses this average to bound the chance of a large value.
Chebyshev's inequality: A probability bound that limits deviations from a mean using variance. Applying Markov's inequality to squared deviations yields this stronger, centered bound.
Cantelli's inequality: A one-sided variance-based bound on deviations from a random variable's mean. It improves a one-sided tail estimate by using both the mean and variance.
First-passage time: The time at which a stochastic process first reaches a specified state or set. If this time is nonnegative with finite expectation, Markov's inequality bounds unusually long waits.
Indicator function: A function equal to one when a condition holds and zero otherwise. An indicator of the threshold event turns its probability into an expectation.
Chernoff bound: An exponential tail bound derived from expectations of exponential transforms. It strengthens basic expectation bounds when exponential moments are available.
Hoeffding's inequality: An exponential concentration bound for sums of independent bounded random variables. Boundedness and independence yield exponential decay rather than Markov's reciprocal-threshold bound.
Randomized algorithm: An algorithm whose behavior depends on random choices during execution. Expected running time can bound the probability that a randomized algorithm runs exceptionally long.
Tail probability: The probability that a random variable exceeds a specified value. Markov's inequality gives a general upper bound on this probability.
Weak law of large numbers: A theorem stating that sample averages converge in probability to their expected value. Markov's inequality can prove convergence when applied to suitable nonnegative deviations.

Linked from 14 pages