Probability Inequalities

Competitive programming sometimes uses randomized algorithms. Their correctness and time and space complexity usually depend on the premise that “the probability of certain random events is very small.” For example, the complexity of quicksort depends on the event that “the chosen pivot is almost the minimum or maximum element” being rare.

This article briefly introduces several tools for analyzing randomized algorithms and gives a few simple applications.

Union Bound

Let $A_1, \cdots, A_m$ be random events. Then

$$P\left\{ \bigcup_{i=1}^m A_i \right\} \leq \sum_{i=1}^m P\{A_i\}$$

That is, the probability that at least one event in a collection occurs is no greater than the sum of the probabilities of the individual events.

In fact, this conclusion can be strengthened slightly:

• The probability that at least one event in a collection occurs is at least the sum of the probabilities of the individual events, minus the sum of the probabilities that each pair occurs simultaneously.
• The probability that at least one event in a collection occurs is at most the sum of the probabilities of the individual events, minus the sum of the probabilities that each pair occurs simultaneously, plus the sum of the probabilities that each triple occurs simultaneously.
• …

As the number of levels increases, the alternating upper and lower bounds become tighter. This series of conclusions is formally similar to the inclusion–exclusion principle, and its proof is similar as well; we omit it here.

Markov Inequality

Let $X$ be a nonnegative random variable. Then for any positive real number $a$,

$$P\{ X \geq a \} \leq \frac{EX}{a}$$

In fact, because Markov's inequality itself uses no distributional information about the random variable beyond its expectation, the bound obtained by applying it directly is usually quite loose.

Proof

Let $I$ be the indicator function of the event $X \geq a$. Then

$$I \leq \frac{X}{a}$$

Consequently,

$$P\{ X \geq a \} = EI \leq E \left[ \frac{X}{a} \right] = \frac{EX}{a}$$

Chebyshev Inequality

Let $X$ be a random variable. Then for any $a > 0$,

$$P \{ |X - EX| \geq a \} \leq \frac{DX}{a^2}$$

In particular, when $a$ is set to $k\sigma$,

$$P \{ |X - EX| \geq k\sigma \} \leq \frac{1}{k^2}$$

where $\sigma$ is the standard deviation of $X$.

Proof

By the given condition,

$$P \{ |X - EX| \geq a \} = P \{ (X - EX)^2 \geq a^2 \}$$

Since $(X - EX)^2$ is nonnegative, Markov's inequality gives

$$P \{ (X - EX)^2 \geq a^2 \} \leq \frac{E(X - EX)^2}{a^2} = \frac{DX}{a^2}$$

Chernoff Inequality

The general Chernoff inequality can be obtained by applying Markov's inequality directly to the random variable $\mathrm{e}^{tX}$:

Let $X$ be a random variable. Then for any $t > 0$,

$$P\{ X \geq a \} = P\{ \mathrm{e}^{tX} > \mathrm{e}^{ta} \} \leq \frac{E \mathrm{e}^{tX}}{\mathrm{e}^{ta}}$$

Similarly, when $t < 0$,

$$P\{ X \leq a \} = P\{ \mathrm{e}^{tX} > \mathrm{e}^{ta} \} \leq \frac{E \mathrm{e}^{tX}}{\mathrm{e}^{ta}}$$

Chernoff Inequality for a Sum of Poisson Trials

The random variables involved in competitive programming are usually not so “general”; we can describe them using Poisson trials from probability theory.

A Poisson trial is a random experiment with only two possible outcomes.

The outcome of one Poisson trial can be represented by a random variable taking the value $0$ or $1$, denoted $X$, with probability distribution

$$P\{ X = i \} = \begin{cases} p_i, & i = 1 \\ 1 - p_1, & i = 0 \end{cases}$$

For Poisson trials, we have the following result:

For $n$ independent Poisson trials $X_1, X_2, \cdots, X_n$, let $X = \sum_{i=1}^{n} X_i$ and $\mu = EX$. Then for any $0 < \epsilon < 1$,

$$P\left\{ |X - \mu| \geq \epsilon \mu \right\} \leq 2 \exp\left( - \frac{1}{3} \mu \epsilon^2 \right)$$

Hoeffding Inequality

If $X_1, \cdots, X_n$ are mutually independent real random variables with $X_i\in [a_i,b_i]$, and $X=\sum\limits_{i=1}^n X_i$, then

$$P\{ |X - EX| \geq \epsilon \} \leq 2\exp \left( \frac {-2\epsilon^2}{\sum\limits_{i=1}^n (b_i-a_i)^2} \right)$$

Both the Chernoff and Hoeffding inequalities bound how far a random variable can deviate from its expected value. Their proofs are rather lengthy; interested readers can consult the relevant chapters of Probability and Computing.

Empirically, if $EX$ is not too close to $a_1+\cdots+a_n$, the bound given by this inequality is often relatively tight. If it is very close—for example, in UOJ #72 New Solution—the bound is often quite loose, and Chernoff's inequality is a better choice.

Example Applications

Example: Estimating Pi by Random Point Sampling

Consider the following algorithm for estimating the exact value of $\pi$:

In the square region $[-1, 1]^2$, generate $n$ points uniformly at random. Let the number of points that fall inside the unit disk $x^2 + y^2 \leq 1$ be $m$. Then $\dfrac{4m}{n}$ can be used as an approximation to $\pi$.

Question: to guarantee that, with probability at least $(1 - \delta)$, the algorithm returns a result with relative error at most $\epsilon$, how should $n$ be chosen?

Solution

Let $X_i$ indicate the event that the $i$-th randomly generated point lies inside the unit disk. Then the total number of points inside the disk is $X = \sum_{i=1}^{n} X_i$. We need to find a suitable $n$ such that

$$P\left\{ \left| \frac{4X}{n} - \pi \right| \geq \epsilon \pi \right\} \leq \delta$$

The above is equivalent to

$$P\left\{ \left| X - \frac{\pi}{4}n \right| \geq \epsilon \cdot \frac{\pi}{4}n \right\} \leq \delta$$

By the Chernoff inequality, it suffices to require

$$2 \exp\left( - \frac{1}{3} \epsilon^2 \cdot \frac{\pi}{4}n \right) \leq \delta$$

From this we obtain

$$n \geq \frac{12}{\pi} \epsilon^{-2} \ln \frac{2}{\delta}$$

Thus the desired accuracy can be achieved when $n = \Omega(\epsilon^{-2} \ln \frac{1}{\delta})$.

Example: Lottery Problem

A box contains $n$ balls, exactly $k$ of which correspond to prizes. You repeatedly draw a ball independently and uniformly at random, returning it to the box after each draw. How many draws guarantee, with probability at least $(1 - \epsilon)$, that every prize ball is drawn at least once?

Solution

If there is only one prize ball, then $M=n\log\epsilon^{-1}$ draws suffice, because the probability that all $M$ draws miss it is

$$\Big(1-\dfrac 1n\Big)^{n\log\epsilon^{-1}}\leq e^{\log\epsilon}=\epsilon$$

Now suppose there are $k>1$ prize balls. By the Union Bound, it suffices to ensure that the probability of missing each prize ball is at most $\dfrac \epsilon k$. Therefore the answer is $n \log \dfrac{k}{\epsilon}$.

Example: Randomly Selecting Half of the Elements

Give an algorithm that selects from $n$ elements, uniformly at random, a subset of size $\dfrac{n}{2}$, assuming $n$ is even. The only random source available is a fair coin; try to minimize the number of coin flips (the minimum is not required).

Solution

First consider the following algorithm:

• By flipping $n$ coins, choose one subset uniformly at random from all subsets.
• Repeat this process until the selected subset has size exactly $\dfrac n2$.
  • Notice that subsets of size $\dfrac n2$ account for at least $\dfrac 1n$ of all subsets, so the expected number of repetitions is $\leq n$.

This algorithm requires an expected $n^2$ coin flips.

Another algorithm is as follows:

• We can implement a uniformly random choice of one element using an expected $2\lceil\log_2 n\rceil$ coin flips from $n$ elements.
  • Specifically, generate a binary number with $\lceil\log_2 n\rceil$ bits uniformly at random. If it is greater than or equal to $n$, generate again; otherwise, select the element with that number (numbered from 0) and finish.
• Then choose one element from all elements, then one from the remaining elements, and so on, until $\dfrac n2$ elements have been selected.

This algorithm requires an expected $n\lceil\log_2 n\rceil$ coin flips.

Combine the two algorithms:

• First use the first algorithm to obtain a random subset.
• If the subset has fewer than $\dfrac n2$ elements, repeatedly add elements using the second algorithm until its size reaches $\dfrac n2$.
• If the subset has more than $\dfrac n2$ elements, repeatedly remove elements using the second algorithm until its size decreases to $\dfrac n2$.

Try to analyze the number of operations required by the second and third steps, that is, the number of additions or removals:

• Let the 0–1 random variable $X_i$ indicate whether $i$ is selected into the initial subset, and let $X:=X_1+\cdots+X_n$ be the subset size. Then the number of operations required by the second and third steps is $\big|X-\mathrm{E}[X]\big|$. Taking $t=c\cdot\sqrt n$ in Hoeffding's inequality, where $c$ is any constant, gives $\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2\mathrm{e}^{-c^2}$. In other words, by allowing a deviation on the order of $\Theta(\sqrt n)$, we can obtain an arbitrarily small constant failure probability.

We have now shown that, with high probability, the algorithm uses at most $n+\Theta(\sqrt n\log n)$ coin flips.

• Here $n$ comes from the coin flips used to obtain the initial subset; $\Theta(\sqrt n\log n)$ is the total cost of the $\Theta(\sqrt n)$ additions or removals.

Expected Complexity

Let us analyze the expected number of coin flips from another perspective.

Use Hoeffding's inequality to bound the expected number of operations in the second and third steps:

$$E|X - EX| = \int_0^\infty P\{ |X - E[X]| \geq t \} \mathrm{d}t \leq 2 \int_0^\infty \exp \left(-\frac {t^2}{n}\right) \mathrm{d}t=\sqrt{\pi n}$$

Therefore, the expected number of coin flips needed by the second and third steps is $\sqrt{\pi n}\cdot2\lceil\log_2 n\rceil$.

In total, this algorithm requires an expected $n+2\sqrt{\pi n}\lceil\log_2 n\rceil$ coin flips.

Exercise: Balls and Bins

Throw $n$ balls independently and uniformly at random into $n$ boxes. Prove that, with probability at least $1 - \dfrac{1}{n}$, the number of balls in the fullest box is at least $\Omega \left( \dfrac{\log n}{\log \log n} \right)$.