A randomized algorithm needs a guarantee about its chance of failure, not just an average running time or expected answer. Concentration inequalities convert information about a random variable into bounds on exceptional events. We begin with two elementary bounds and show exactly where independence enters amplification.
Definitions
Theorem 3.2.1
(Markov's inequality)
If and , then , provided the expectation is finite.
Proof
(Pointwise comparison)
Pointwise, . Taking expectations and dividing by proves the claim.
Counterexample mode
Markov's inequality fails without nonnegativity
Let equal or with probability each. Then , so Markov's bound with would give , yet the true probability is . The inequality holds once the variable is nonnegative.
Theorem 3.2.2
(Chebyshev's inequality)
If has finite mean and variance , then for ,
Proof
(Markov applied to a squared deviation)
Apply Markov to the nonnegative variable with threshold .
For independent random variables of common mean and variance , their average has variance . Hence . Independence makes the cross-covariances vanish; identical distribution is stronger than necessary if the means and variance bounds are stated separately. The bound may exceed one, in which case replacing it by one gives the useful probability bound.
Amplifying a decision procedure
Suppose independent trials each return the correct answer with probability at least , and run an odd number of trials. Let indicate failure and . Then and, by independence, . Majority fails only if , implying . Chebyshev gives
This is a polynomially decreasing upper bound; sharper concentration estimates can give exponential decay. Repetition alone is insufficient if trials share randomness: if all answers copy the same random trial, majority has exactly the original failure probability. Also, an upper bound on the average number of errors alone does not establish independence.
Exercises
Worked example 3.2.3
(Averaging runs under Chebyshev)
An unbiased estimator has variance on each independent run. Averaging runs gives variance . With , Chebyshev bounds the probability of error at least by ; it does not assert that the true probability equals .
Quick check
(A nonnegative random variable has expectation 3. Bound the probability it is at least 12.)
Apply Markov with .
Solution · Answer
Markov gives .
Quick check
(For independent unbiased estimates with variance at most 9, how many runs suffice for the average to deviate by at least 1 with probability at most under Chebyshev?)
Apply Chebyshev to the average, whose variance is at most .
Solution · Answer
The average has variance at most , so the probability is at most . It suffices to take . This is a sufficient bound, not necessarily the minimum for a particular distribution.
Theorem/proposition
Markov's inequality can be applied after a change of scale. If and is finite, monotonicity of the exponential gives
The parameter is free. A useful bound follows by computing or bounding the exponential moment and then choosing to make the right side small. This argument does not by itself require independence; independence matters when factoring the exponential moment of a sum.
Theorem 3.2.4
(Hoeffding bound for independent Bernoulli trials)
Let be independent Bernoulli variables, not necessarily identically distributed, with means . Put and . For every ,
Proof
(Hoeffding's bound via the exponential moment)
For a Bernoulli variable with mean , define
We have . Differentiating twice shows , where ; the endpoint cases follow directly. Integrating twice gives for . Independence factors the exponential moment, so
Choosing yields the stated exponent.
Proof X-ray
Where the Hoeffding proof uses its hypotheses
Where each hypothesis enters: boundedness of each gives , hence the quadratic cap whatever the mean . Independence is used once, to multiply the exponential moments. The key move is to cap the logarithm of the moment-generating function by its second derivative: because the mean is subtracted, and is the variance of a tilted Bernoulli variable. The closing step is an optimization: is smallest at , where it equals . Without independence the product of moments is unavailable, as the repetition counterexample later in this note shows.
For independent decision trials with failure probabilities at most , majority failure implies . The bound is therefore at most . This is exponential in the number of trials. To make it at most , it suffices to choose an odd . The logarithm is natural. The statement is about a fixed input: each trial must have the success guarantee on that same input and use fresh independent randomness.
Worked examples
Worked example 3.2.5
(Majority vote over 180 runs)
Suppose each independent run fails with probability exactly and take , counting a tied vote as failure. Chebyshev's bound above gives , while the exponential bound gives . The latter is a guarantee, not the exact binomial tail. For majority voting one normally takes an odd count; with 181 trials the same formulas give at most and respectively. The weaker bound can still be valuable when only a variance is known and boundedness or a suitable exponential moment is unavailable.
Quick check
(Independent Bernoulli variables have total mean 40. Bound the probability that their sum is at least 50 if there are 100 variables.)
Use the Hoeffding bound with equal to the excess over the mean.
Solution · Answer
Here and , so Hoeffding gives . The variables need not have the same individual success probability.
One-sided versus two-sided bounds
The upper-tail inequality controls a deviation above the mean. Applying it to the independent Bernoulli variables controls a deviation below the mean. Combining the events by the union bound gives
The union bound does not require independence of the two events. It follows from and expectation. Independence was required earlier, to bound each exponential moment. A factor of two appears because two possible directions of error are being covered. When the right side exceeds one it remains true but is uninformative; a probability is always at most one.
For independent Bernoulli samples with common mean , take . Then
To make this at most , it suffices that . This bound holds uniformly over the unknown value , so the sample size can be fixed before observing samples. It gives a guarantee over the random sampling procedure: it is not a statement that a fixed observed interval has a random probability of containing the fixed parameter.
Worked example 3.2.6
(Sample size for a Bernoulli mean)
To estimate a Bernoulli mean within with failure probability at most , it suffices to take , so 185 independent samples suffice. The bound may be conservative; it does not assert that 185 is the smallest possible sample size for every distribution or every estimator.
Several simultaneous estimates
Suppose there are quantities, and estimate each using independent samples within that quantity. If each estimate has error at least with probability at most , the probability that at least one estimate fails is at most . No independence between the estimates for different quantities is required for this last step. With Bernoulli samples, choosing
per quantity is sufficient. Here is a positive integer and . The logarithmic dependence on is useful, but obtaining separate samples of size may still require observations if no samples can be shared. A proof must account for the actual sampling cost, rather than treating the probability bound itself as a running-time analysis.
Worked example 3.2.7
(Ten simultaneous estimates)
For , and , the formula requires , so 300 observations per quantity suffice. Even if the ten failure events are strongly correlated, the union bound remains valid as long as each individual estimate satisfies its stated bound.
Dependence can defeat repetition
Counterexample mode
Repetition without independence
Let be a single Bernoulli random variable with , and set for every trial. Each trial separately has failure probability , but the majority fails exactly when , regardless of the number of repetitions. In this case and , not . The omitted covariance terms explain the discrepancy.
Independent randomness is therefore a mathematical condition on the joint distribution, not merely a promise that an algorithm was executed several times. Reusing a random seed, a common randomized preprocessing step, or a common sample can create dependence. Some dependent procedures admit other concentration arguments, but their guarantees need a separate proof.
Quick check
(Each of five estimators fails with probability at most . What upper bound can be proved for the probability that at least one fails, with no assumption on their dependence?)
Which bound needs no independence?
Solution · Answer
The union bound gives . The events need not be disjoint or independent; if they overlap, the sum can overcount the union.
Quick check
(Independent Bernoulli samples have mean . How many samples suffice to estimate within with failure probability at most by the two-sided bound?)
Solve for .
Solution · Answer
It is enough that . Thus 1060 samples suffice. The inequality bounds failure defined using and hence also the event of error strictly greater than .
What can an expectation alone guarantee?
Markov's inequality is sometimes the best possible statement when only the mean and nonnegativity are known. Fix and let with probability and otherwise. Then and , so Markov's bound is attained. A stronger universal bound requires further information about the distribution.
This fact matters for running-time analysis. If a nonnegative running time has finite expectation at most for some , Markov gives . It does not imply that every run finishes by , or that the failure probability decays exponentially in the threshold. An algorithm with expected running time may have rare much longer runs; the mean controls their contribution to the average but does not eliminate them.
Worked example 3.2.8
(A rare long run)
Let with probability and otherwise. Its expectation is one, yet a run takes 100 time units with probability one percent. The event has probability , exactly the Markov bound . This example is an abstract running-time model; an actual algorithm may have a positive minimum cost, which can be included by adding a constant.
Common mistakes
Common mistake
(A per-input guarantee is not a simultaneous guarantee)
Suppose a decision algorithm has a separate error probability at most on each input. For any one fixed input, fresh independent repetitions support the majority bound above. It does not follow that a single random choice makes the algorithm correct on every possible input simultaneously. If the input set is finite and one needs simultaneous correctness, a union bound over that set may help, but its size must be included in the calculation. If inputs are chosen adaptively after seeing the randomness, even the interpretation of the per-input guarantee changes and requires a separate argument.
For example, if there are fixed inputs and the amplified failure probability per input is at most , the probability of at least one failure is at most . This uses no independence across inputs. Choosing odd suffices to make the bound at most . It establishes existence of a random seed sequence that works for all those inputs with positive probability when , but it does not automatically provide an efficient deterministic way to find that sequence.
Quick check
(A nonnegative algorithm runtime has expectation at most 20 seconds. What does Markov imply about exceeding 100 seconds?)
Compare the threshold with the expectation.
Solution · Answer
Since , the probability is at most . The inequality does not imply that the runtime is bounded by 100 seconds.
Summary
The available assumptions determine which bound applies. Markov uses nonnegativity and a finite mean; Chebyshev applies Markov to a squared deviation and uses a finite variance. The exponential bound here adds independent bounded Bernoulli trials and obtains a stronger tail. The union bound then combines failure events without requiring those events to be independent. In each application, identify the random experiment, the event of interest, and the hypotheses before substituting numbers. An upper bound can be loose, exceed one, or be achieved in special cases; it is never automatically the exact probability. Finally, a high-probability guarantee for a fixed input is not the same as a simultaneous guarantee for every input. When the hypotheses fail, a counterexample may invalidate the conclusion even if the numerical formula looks plausible.