06 Estimating Probabilities

In the realm of probability, we often find ourselves in situations where calculating exact probabilities is either computationally infeasible or analytically intractable. Imagine trying to determine the precise probability of a complex event in a large, intricate system. Direct computation may be overwhelmingly complex. This is where the art of estimating probabilities becomes invaluable. Instead of seeking exact values, we aim to find bounds or approximations that provide useful insights into the likelihood of events. These estimations, while not perfectly precise, can be sufficient for making informed decisions and understanding the behavior of random systems.

Markov’s Inequality: A First Bound (2.7.1)

We begin with a remarkably simple yet surprisingly useful tool for probability estimation: Markov’s Inequality. Markov’s Inequality provides an upper bound on the probability that a non-negative random variable exceeds a certain threshold, using only its expectation. It’s a testament to the power of expectation as a single-number summary of a distribution.

Satz 2.67 (Markov’s Inequality): Let $X$ be a non-negative random variable, and let $t$ be any positive real number ($t>0$). Then the probability that $X$ is greater than or equal to $t$ is bounded by the ratio of its expectation to $t$:

$$Pr[X\ge t]\le \frac{E[X]}{t}$$

Or, equivalently, in a slightly rearranged form:

$$Pr[X\ge t\cdot E[X]]\le \frac{1}{t}$$

This inequality is remarkably general, holding for any non-negative random variable, regardless of its specific distribution. This generality is both its strength and its weakness. It is widely applicable but can sometimes provide loose bounds compared to distribution-specific estimates.

Proof of Markov’s Inequality: The proof is a beautiful example of probabilistic reasoning based on the definition of expectation. Recall that for a non-negative random variable $X$, its expectation is defined as:

$$E[X]=\sum _{x\in W_X}x\cdot Pr[X=x]$$

Since $X$ is non-negative, all values in its range $W_X$ are greater than or equal to zero. We can split the sum into two parts: values of $x$ that are less than $t$ and values of $x$ that are greater than or equal to $t$:

$$E[X]=\sum _{x\in W_X}x\cdot Pr[X=x]=\underset{\ge 0}{\underbrace{\sum _{x\in W_X,x<t}x\cdot Pr[X=x]}}+\underset{\ge {\sum }_{x\in W_X,x\ge t}t\cdot Pr[X=x]}{\underbrace{\sum _{x\in W_X,x\ge t}x\cdot Pr[X=x]}}$$

Since $X$ is non-negative, the first term is non-negative. In the second term, for all $x\ge t$, we have $x\ge t$. Therefore, we can lower bound the second term by replacing $x$ with $t$:

$$E[X]\ge \sum _{x\in W_X,x\ge t}t\cdot Pr[X=x]=t\cdot \sum _{x\in W_X,x\ge t}Pr[X=x]=t\cdot Pr[X\ge t]$$

Dividing both sides by $t$ (since $t>0$), we arrive at Markov’s Inequality:

$$Pr[X\ge t]\le \frac{E[X]}{t}$$

Markov’s Inequality provides a simple, expectation-based bound on tail probabilities for non-negative random variables. It is often used as a starting point for more refined probability estimations.

Chebyshev’s Inequality: Leveraging Variance (2.7.1)

While Markov’s Inequality is powerful in its generality, it only utilizes the expectation of the random variable. To obtain tighter bounds, we can incorporate information about the variance, which measures the spread of the distribution around its mean. This leads us to Chebyshev’s Inequality, a refinement of Markov’s Inequality that utilizes both expectation and variance.

Satz 2.68 (Chebyshev’s Inequality): Let $X$ be a random variable with expectation $E[X]$ and variance $Var[X]$. For any real number $t>0$, the probability that the absolute deviation of $X$ from its expectation is greater than or equal to $t$ is bounded by the ratio of the variance to $t^2$:

$$Pr[|X-E[X]|\ge t]\le \frac{Var[X]}{t^2}$$

Or, equivalently, using the standard deviation $\sigma =\sqrt{Var[X]}$:

$$Pr[|X-E[X]|\ge k\cdot \sigma ]\le \frac{1}{k^2}$$

Chebyshev’s Inequality provides a bound on the probability of deviations from the mean, using variance to quantify the spread. The bound decreases quadratically with increasing $t$, indicating that larger deviations from the mean become increasingly less probable as variance decreases.

Proof of Chebyshev’s Inequality: The proof elegantly reduces Chebyshev’s Inequality to Markov’s Inequality by considering the squared deviation from the mean, $(X-E[X]{)}^2$, which is always a non-negative random variable.

Let $Y=(X-E[X]{)}^2$. Then $Y$ is a non-negative random variable, and its expectation is the variance of $X$: $E[Y]=E[(X-E[X]{)}^2]=Var[X]$. We want to bound the probability $Pr[|X-E[X]|\ge t]$. This event is equivalent to the event $(X-E[X]{)}^2\ge t^2$, which is the event $\{Y\ge t^2\}$. Applying Markov’s Inequality to the non-negative random variable $Y$ with threshold $t^2$, we get:

$$Pr[|X-E[X]|\ge t]=Pr[(X-E[X]{)}^2\ge t^2]=Pr[Y\ge t^2]\le \frac{E[Y]}{t^2}=\frac{Var[X]}{t^2}$$

This completes the proof of Chebyshev’s Inequality. By squaring the deviation and applying Markov’s Inequality, Chebyshev’s Inequality leverages the variance to provide a tighter bound on tail probabilities compared to Markov’s Inequality alone.

Chernoff Bounds: Exponential Tail Bounds for Sums of Independent Bernoulli Variables (2.7.2)

For sums of independent Bernoulli random variables, we can obtain even tighter bounds on tail probabilities than those provided by Markov’s or Chebyshev’s Inequalities. These tighter bounds are known as Chernoff bounds. Chernoff bounds exploit the specific structure of sums of independent Bernoulli variables to provide exponential decay in the tail probabilities, offering much sharper estimates for rare events.

Satz 2.70 (Chernoff Bounds): Let $X_1,\dots ,X_n$ be independent Bernoulli random variables with $Pr[X_i=1]=p_i$ and $Pr[X_i=0]=1-p_i$. Let $X={\sum }_{i=1}^n{X}_i$ be the sum of these variables, and let $\mu =E[X]={\sum }_{i=1}^n{p}_i$ be the expected value of $X$. Then, for any $\delta >0$:

(i) Upper Tail Bound (δ > 0): For $0<\delta \le 1$:

$$Pr[X\ge (1+\delta )\mu ]\le e^{-\frac{1}{3}{\delta }^2\mu }$$

(ii) Lower Tail Bound (δ > 0): For $0<\delta \le 1$:

$$Pr[X\le (1-\delta )\mu ]\le e^{-\frac{1}{2}{\delta }^2\mu }$$

(iii) Very Large Deviations (t ≥ 2eμ): For $t\ge 2e\mu$:

$$Pr[X\ge t]\le 2^{-t}$$

Chernoff bounds provide exponential tail bounds, meaning that the probability of deviations from the mean decays exponentially with the size of the deviation. This is a much faster decay than the polynomial decay provided by Chebyshev’s Inequality, making Chernoff bounds significantly tighter for sums of independent Bernoulli variables.

Proof Sketch of Chernoff Bound (iii): The proof of Chernoff bounds typically involves a technique called the moment-generating function method. For bound (iii), we consider the probability $Pr[X\ge t]$ and apply Markov’s Inequality to the random variable $Y=4^X$. By carefully bounding the expectation of $Y$, $E[4^X]$, and applying Markov’s Inequality, we can derive the exponential tail bound. The details of the proof are somewhat technical and involve calculus and properties of exponential functions.

Chernoff bounds are indispensable tools in the analysis of randomized algorithms, particularly for analyzing the probability of success or failure, tail probabilities of performance measures, and concentration of random variables around their means. They provide sharp probabilistic estimates that are crucial for designing and evaluating efficient and reliable randomized algorithms.

In summary, this section has explored powerful techniques for estimating probabilities when exact calculations are difficult or unnecessary. Markov’s and Chebyshev’s Inequalities provide general bounds based on expectation and variance, while Chernoff bounds offer tighter, exponential tail bounds specifically for sums of independent Bernoulli variables. These tools are essential for probabilistic analysis and algorithm design, allowing us to reason about random phenomena and make informed decisions in the face of uncertainty.

Prev: 05 Multiple Random Variables | Next: 07 Randomized Algorithms