Skip to content

Probability Inequalities

In algorithm competitions, randomized algorithms are sometimes used. The correctness and time/space complexity of these algorithms often rely on the premise that "the probability of certain random events occurring is very small." For example, the complexity of quicksort depends on the fact that the event "the chosen pivot element is almost the smallest or largest element" occurs relatively infrequently.

This article will briefly introduce some tools for analyzing randomized algorithms and provide a few simple application examples.

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 group occurs does not exceed the sum of the probabilities of each individual event occurring.

In fact, this conclusion can be slightly strengthened:

  • The probability that at least one event in a group occurs is no less than the sum of the probabilities of each event occurring, minus the sum of the probabilities of every two events occurring simultaneously.
  • The probability that at least one event in a group occurs is no more than the sum of the probabilities of each event occurring, minus the sum of the probabilities of every two events occurring simultaneously, plus the sum of the probabilities of every three events occurring simultaneously.
  • ……

As the number of layers increases, the alternating upper and lower bounds become tighter. This series of conclusions resembles the inclusion-exclusion principle in form, and the proof process is also similar to inclusion-exclusion, which is omitted here.

Markov's Inequality

Let \(X\) be a non-negative random variable. Then for any positive real number \(a\),

\[ P\{ X \geq a \} \leq \frac{EX}{a} \]

In fact, since Markov's inequality itself does not use any information about the distribution of the random variable other than its expectation, the bounds obtained by directly applying this inequality are usually loose.

Proof

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

\[ I \leq \frac{X}{a} \]

Thus,

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

Chebyshev's 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 taken as \(k\sigma\),

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

where \(\sigma\) is the standard deviation of \(X\).

Proof

From the given, we have

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

Note that \((X - EX)^2\) is non-negative. Therefore, by Markov's inequality,

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

Chernoff Bound

The general Chernoff bound can be derived by directly applying Markov's inequality 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, for \(t < 0\),

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

Chernoff Bound for Sums of Poisson Trials

Random variables involved in algorithm competitions are usually not that "general"; we can describe them using Poisson trials from probability theory.

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

The outcome of a single Poisson trial can be described by a random variable \(X\) taking values \(0\) or \(1\), 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 conclusion:

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's Inequality

If \(X_1, \cdots, X_n\) are mutually independent real random variables with \(X_i\in [a_i,b_i]\), and let \(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 Chernoff's inequality and Hoeffding's inequality bound the extent to which a random variable deviates from its expected value. The proofs of these two inequalities are lengthy; interested readers can refer to the relevant chapters in the book 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 Approach), the bound is often loose, and it is better to use Chernoff's inequality in such cases.

Application Examples

Example: Estimating Pi by Random Point Sampling

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

Randomly generate \(n\) points in the square region \([-1, 1]^2\). Let \(m\) be the number of points that fall into the unit disk \(x^2 + y^2 \leq 1\). Then \(\dfrac{4m}{n}\) can be taken as an approximation of \(\pi\).

Question: To ensure that the above algorithm returns a result with relative error not exceeding \(\epsilon\) with probability at least \((1 - \delta)\), how should \(n\) be chosen?

Answer

Let \(X_i\) denote the event "the \(i\)-th randomly generated point lies inside the unit circle." Then the total number of points inside the circle is \(X = \sum_{i=1}^{n} X_i\). We need to find an appropriate \(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 \]

According to Chernoff's inequality, we only need to set

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

which yields

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

That is, when \(n = \Omega(\epsilon^{-2} \ln \frac{1}{\delta})\), the required accuracy can be achieved.

Example: Lottery Problem

A box contains \(n\) balls, exactly \(k\) of which correspond to grand prizes. You perform several independent, equally probable random draws, each time returning the ball to the box after drawing. How many draws are needed to guarantee with probability at least \((1 - \epsilon)\) that every prize ball is drawn at least once?

Answer

If there is only one prize ball, then drawing \(M=n\log\epsilon^{-1}\) times is sufficient, because the probability of missing it in all \(M\) draws is

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

Now there are \(k>1\) prize balls. Then by the Union Bound, we only need to ensure that the probability of missing each prize ball does not exceed \(\dfrac \epsilon k\). Thus the answer is \(n \log \dfrac{k}{\epsilon}\).

Example: Randomly Selecting Half the Elements

Design an algorithm that selects a subset of size \(\dfrac{n}{2}\) uniformly at random from \(n\) elements, given that \(n\) is even. The only random source you can use is a fair coin, and you should minimize the number of coin tosses (not necessarily the minimum).

Solution

First, we can think of the following algorithm:

  • By tossing the coin \(n\) times, we can uniformly select a random subset from all subsets.
  • Repeat this process until the selected subset size is exactly \(\dfrac n2\).
    • Note 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 expects to toss the coin \(n^2\) times.

Another algorithm:

  • We can implement random selection of one out of \(n\) elements with an expected \(2\lceil\log_2 n\rceil\) coin tosses.
    • Specific method: randomly generate a \(\lceil\log_2 n\rceil\)-bit binary number. If it is greater than or equal to \(n\), regenerate; otherwise, select the element with the corresponding index (index starting from 0) and end the process.
  • Then we select one element from all elements, then another from the remaining elements, and so on, until \(\dfrac n2\) elements are selected.

This algorithm expects to toss the coin \(n\lceil\log_2 n\rceil\) times.

Combine the two algorithms:

  • First, use the first algorithm to randomly obtain a subset.
  • If the subset size is less than \(\dfrac n2\), use the second algorithm to repeatedly add elements until the size reaches \(\dfrac n2\).
  • If the subset size exceeds \(\dfrac n2\), use the second algorithm to repeatedly delete elements until the size is reduced to \(\dfrac n2\).

Try to analyze the number of operations (i.e., the number of additions/deletions) required in the second and third steps:

  • Define the 0-1 random variable \(X_i\) to indicate whether element \(i\) is selected into the initial subset. Let \(X:=X_1+\cdots+X_n\) denote the subset size. Then the number of operations required in the second and third steps equals \(\big|X-\mathrm{E}[X]\big|\). In Hoeffding's inequality, take \(t=c\cdot\sqrt n\) (where \(c\) is an arbitrary constant) to obtain \(\mathrm{Pr}\Big[\big|X-\mathrm{E}[X]\big|\geq t\Big]\leq 2\mathrm{e}^{-c^2}\). That is, by allowing an offset of \(\Theta(\sqrt n)\), we can achieve an arbitrarily small constant failure probability.

So far we have shown: this algorithm can, with high probability, guarantee that the number of coin tosses is within \(n+\Theta(\sqrt n\log n)\).

  • Here, \(n\) comes from the coin tosses to obtain the initial subset; \(\Theta(\sqrt n\log n)\) is the total cost of \(\Theta(\sqrt n)\) additions/deletions.
Calculating Expected Complexity

Let's analyze from another perspective and try to compute the expected number of coin tosses for this algorithm.

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} \]

Thus, the expected number of coin tosses required for the second and third steps is \(\sqrt{\pi n}\cdot2\lceil\log_2 n\rceil\).

In summary, this algorithm expects to toss \(n+2\sqrt{\pi n}\lceil\log_2 n\rceil\) coins.

Exercise: Balls and Bins

\(n\) balls are thrown independently and uniformly at random into \(n\) bins. Prove that with probability \(1 - \dfrac{1}{n}\), the bin with the most balls contains at least \(\Omega \left( \dfrac{\log n}{\log \log n} \right)\) balls.

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用