14 Rules for Moments (Expectation, Variance), Estimating Probabilities (Markov, Chebyshev), Chernoff Bounds

Lecture from: 03.04.2025 | Video: Homelab

We’ve established what variance is and some of its basic properties. Now, let’s explore how variance behaves with sums and products of random variables. This will lead us to powerful tools called concentration inequalities, which allow us to bound the probability that a random variable deviates far from its expected value.

Recap: Expectation and Variance

• Expected Value $E[X]$: The average value of $X$. We desire to quantify exactly that $Pr[|X-E[X]|\text{ is "large"}]\text{ is "small"}$.

• Variance $Var[X]=E[(X-E[X]{)}^2]=E[X^2]-(E[X]{)}^2$: Measures the expected squared deviation from the mean. A small variance suggests $X$ is usually close to $E[X]$.

• Property of Variance: $Var[aX+b]=a^{2}Var[X]$. Adding a constant $b$ shifts the distribution but doesn’t change its spread (variance). Scaling by $a$ scales the variance by $a^2$.

Rules for Moments: Expectation and Variance

Let’s now summarize how expectation and variance behave when working with multiple random variables. These foundational properties are often referred to as rules for moments, where:

• The first moment is the expectation: $E[X]$.
• The second central moment is the variance: $Var[X]=E[(X-E[X]{)}^2]$.

1. Linearity of Expectation

This holds for all random variables $X$ and $Y$, regardless of whether they are dependent or independent. This property - linearity of expectation - is one of the most powerful and broadly applicable tools in probability. This is always true.

2. Product of Expectations

This identity holds if $X$ and $Y$ are independent.

Proof (for independent $X,Y$):

By independence: $Pr[X=x,Y=y]=Pr[X=x]\cdot Pr[Y=y]$.

However, this fails for dependent variables.

Counterexample: Let $X$ be a Bernoulli($\frac{1}{2}$) variable, and let $Y=X$. Then:

• $E[X]=E[Y]=1/2$, so $E[X]E[Y]=1/4$
• But $XY=X^2=X$ since $X\in 0,1$, so $E[XY]=E[X]=1/2$

Thus, $E[XY]\ne E[X]E[Y]$ when $X$ and $Y$ are dependent.

3. Variance of a Sum

This identity holds if $X$ and $Y$ are independent.

Proof (for independent $X,Y$):

Let ${\mu }_X=E[X],{\mu }_Y=E[Y]$. Then:

By linearity of expectation:

The final term is the covariance:

The final term is the covariance:

If $X$ and $Y$ are independent, then so are $(X-{\mu }_X)$ and $(Y-{\mu }_Y)$, since subtracting constants does not affect independence. Therefore:

But:

So:

Thus, under independence:

In fact, this result extends to sums of more than two variables: If $X_1,\dots ,X_n$ are pairwise independent, then:

Pairwise independence is sufficient here, which is strictly weaker than full (mutual) independence.

4. Variance of a Product

This is false in general, even when $X$ and $Y$ are independent.

Counterexample: Let $X,Y$ be independent Bernoulli($\frac{1}{2}$) variables:

• $E[X]=E[Y]=1/2$
• $Var[X]=Var[Y]=1/4$
• So $Var[X]\cdot Var[Y]=(1/4{)}^2=1/16$

Now let $Z=XY$:

• $Z=1$ only when $X=Y=1$ (probability $1/4$), and $0$ otherwise.
• So $Z\sim \text{Bernoulli}(1/4)$
• $E[Z]=1/4$
• $Var[Z]=E[Z^2]-(E[Z]{)}^2=1/4-(1/4{)}^2=1/4-1/16=3/16$

Clearly, $Var[XY]=3/16\ne 1/16=Var[X]Var[Y]$

Summary of Moment Rules

Estimating Probabilities: Concentration Inequalities

We know the expectation $E[X]$ gives the average value of a random variable. But how likely is it that $X$ takes a value far from its mean?

The goal is to bound:

for some deviation $t>0$. These bounds are called concentration inequalities — they describe how tightly $X$ is concentrated around its mean.

Markov’s Inequality

This is the most basic concentration inequality. It applies to any non-negative random variable and requires only the expectation.

Intuitive explanation:

Theorem (Markov’s Inequality)

Let $X\ge 0$ be a non-negative random variable. Then for any $t>0$:

Proof

We split the expectation as follows:

Since all terms are non-negative, the first sum is non-negative, so:

Each $x\ge t$, so replacing $x$ with $t$ in this sum gives:

Rearranging:

This is a one-sided inequality: it only bounds the probability that $X$ is large. It’s general, but can be loose since it only uses the mean.

Chebyshev’s Inequality

Chebyshev’s inequality gives a two-sided bound using both the mean and the variance.

Theorem (Chebyshev’s Inequality)

Let $X$ have mean $\mu =E[X]$ and finite variance $\text{Var}[X]$. Then for any $t>0$:

Proof

Let $Y=(X-\mu {)}^2$. This is a non-negative random variable. The event:

So:

Apply Markov’s Inequality to $Y$:

But $E[Y]=E[(X-\mu {)}^2]=\text{Var}[X]$, so:

Interpretation

Smaller variance means tighter concentration around the mean. The tail probability decays quadratically in $t$.

Letting $t=C\sigma$, where $\sigma =\sqrt{\text{Var}[X]}$, we get:

Examples:

• Deviation of 2 standard deviations: $\le \frac{1}{4}$
• Deviation of 10 standard deviations: $\le \frac{1}{100}$

Variance of Common Distributions

These are useful when applying Chebyshev’s inequality:

• Bernoulli($p$): $E[X]=p$, $\text{Var}[X]=p(1-p)$

• Binomial($n,p$): $X=X_1+\cdots +X_n$, with $X_i\sim \text{Bernoulli}(p)$ and independent $E[X]=np$, $\text{Var}[X]=np(1-p)$

• Poisson($\lambda$): $E[X]=\lambda$, $\text{Var}[X]=\lambda$

• Geometric($p$): $E[X]=\frac{1}{p}$, $\text{Var}[X]=\frac{1-p}{p^2}$

Example: Coupon Collector with Chebyshev

Let $X$ be the total time to collect all $n$ coupons. Then:

where $X_i\sim \text{Geo}(p_i)$, and $p_i=\frac{n-i+1}{n}$.

We know:

To apply Chebyshev, compute the variance:

Substitute $p_i=\frac{n-i+1}{n}$, and after simplification:

So:

Applying Chebyshev

Let $C>0$. Then:

This shows that $X$ is sharply concentrated around $n\ln n$.

Sharper Example

Let $t=n\sqrt{\ln n}$. Then:

So even deviations of size $o(E[X])$ (like $n\sqrt{\ln n}$) become unlikely for large $n$.

Chernoff Bounds: Concentration for Sums of Random Variables

Chebyshev’s inequality is useful for bounding how far a random variable might stray from its expected value, but it’s often too loose, especially for sums of independent random variables. This is where Chernoff bounds become powerful.

Chernoff bounds provide exponentially decreasing bounds on tail probabilities — i.e. the probability that a sum of independent random variables deviates significantly from its expected value.

Setting: Sums of Independent Bernoulli Variables

Suppose $X_1,\dots ,X_n$ are independent Bernoulli random variables with $\mathbb{P}[X_i=1]=p_i$, and let

Then Chernoff bounds give the following tail bounds:

Chernoff Bounds (Standard Forms)

For $0<\delta \le 1$:

• Upper tail:

  $$\mathbb{P}[X\ge (1+\delta )\mu ]\le \exp \left(-\frac{{\delta }^2\mu }{3}\right)$$

• Lower tail:

  $$\mathbb{P}[X\le (1-\delta )\mu ]\le \exp \left(-\frac{{\delta }^2\mu }{2}\right)$$

These bounds are exponentially decreasing in ${\delta }^2\mu$, which gives much tighter control than Chebyshev’s $1/{\delta }^2$ behavior.

Examples

• $\mu =\mathbb{E}[X]=100$
• Try different values of $\delta$: 0.1, 0.5, 1.0

1. $\delta =0.1$ (10% above the mean)

🟠 Quite likely — about a 71.7% upper bound.

2. $\delta =0.5$ (50% above the mean)

🟢 Very unlikely — less than 0.03%.

3. $\delta =1.0$ (100% above the mean, i.e., double the expectation)

🔵 Astronomically unlikely — almost zero.

Intuition:

The probability decays exponentially fast as you move further above the expected value. The larger the deviation ($\delta$) or the expected value ($\mu$), the sharper the drop.

Comparing Chebyshev and Chernoff for $X\sim \text{Bin}(n,1/2)$

Suppose $X\sim \text{Bin}(n,1/2)$. Then:

• $\mathbb{E}[X]=n/2$
• $\text{Var}[X]=n/4$
• ${\sigma }_X=\sqrt{\text{Var}[X]}=\sqrt{n}/2$

Let’s study the probability of a deviation of size $t=\delta \mu =\delta n/2$. Rewriting in terms of standard deviations:

So we’re asking: What is the probability that $X$ deviates from its mean by more than $C{\sigma }_X$?

Chebyshev’s Bound

Substitute $\delta =C/\sqrt{n}$ (i.e. deviation of $C\cdot {\sigma }_X$):

Interpretation: Chebyshev decays only polynomially in $C$. This means even for large deviations (e.g., $C=10$), the bound is still only $1/100$.

Chernoff’s Bound (Upper Tail)

For $X\sim \text{Bin}(n,1/2)$, $\mu =n/2$, so:

Substitute $\delta =C/\sqrt{n}$, then:

Interpretation: Chernoff decays exponentially in $C^2$, giving much smaller probabilities for large deviations.

General Chernoff Bounds (Summary)

Let $X=\sum X_i$, where $X_i\sim \text{Bern}(p_i)$ are independent.

Let $\mu =\mathbb{E}[X]=\sum p_i$.

Then for all $0<\delta \le 1$:

1. $\mathbb{P}[X\ge (1+\delta )\mu ]\le e^{-{\delta }^2\mu /3}$

2. $\mathbb{P}[X\le (1-\delta )\mu ]\le e^{-{\delta }^2\mu /2}$

3. For large deviations: If $t\ge 2e\mu$, then

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

Idea Behind the Proof (MGFs and Markov)

We apply Markov’s inequality, not directly to $X$, but to an exponential transformation of $X$:

Let $s>0$. Then:

So we want to bound $\mathbb{E}[e^{sX}]$.

Because $X=\sum X_i$ and the $X_i$ are independent:

Each $X_i\sim \text{Bern}(p_i)$, so:

Therefore:

The optimal value of $s$ depends on $t$, and we can choose it to minimize this upper bound. The algebra is technical, but with this approach we can derive the exponential bounds.

Example Quick Bound Using $4^X$

To get a quick bound on large deviations ($t\ge 2e\mu$):

Let $Y=4^X=e^{X\ln 4}$, and suppose we want $\mathbb{P}[X\ge t]$. Then:

Using the same independence and Bernoulli MGF trick:

Now observe that for any real number $x$, we have $1+x\le e^x$. Applying this to each factor:

So:

If we want to make the bound even simpler, observe that:

So to ensure $\mathbb{P}[X\ge t]\le 2^{-t}$, it’s enough that:

Basically if $\frac{e^{3\mu }}{2^t}<1$ which happens if the numerator is smaller than then denominator, then we can upper bound by $2^{-t}$.

A conservative sufficient condition is:

Under this condition, the tail bound becomes very simple:

Conclusion

Chernoff bounds are powerful tools for analyzing sums of independent random variables. Unlike Chebyshev, which offers general but loose control, Chernoff bounds exploit independence to yield strong exponential concentration.

These results are foundational in randomized algorithms, probabilistic method, machine learning, and theoretical computer science.

Continue here: 15 Randomized Algorithms, Monte Carlo vs Las Vegas, Reducing Error Probability