Motivation
A sum of independent indicator variables counts successes in repeated random trials. Its expectation gives a useful center, but does not by itself say how unlikely a large deviation is. Markov's inequality bounds a nonnegative random variable using its expectation; applying it directly to the number of successes often gives a weak answer. The key idea here is to apply Markov to an exponential of the sum. Independence then turns the expectation of a product into a product of expectations, producing an exponentially decreasing tail bound.
The bounds are useful even when the indicators have different success probabilities. They are upper bounds, not exact probabilities, and the independence assumption is doing real work. We derive the precise expressions first, then a convenient simplified form and concrete sample-size estimates.
Definitions
Let be independent Bernoulli variables, with and . Put and . The variables need not be identically distributed. A multiplicative upper tail is the event for ; a multiplicative lower tail is for . These thresholds are real numbers even though is integer-valued; the inequalities have their usual meaning.
For , the moment-generating expression is . All expectations here are finite because . The result is meaningful when ; if , all and almost surely, so multiplicative deviations require separate interpretation.
Theorems
Theorem 3.1.1
(Multiplicative Chernoff bounds)
For independent Bernoulli variables with mean sum , and ,
For ,
Theorem 3.1.2
(Convenient quadratic bounds)
Under the same assumptions, for ,
Consequently for .
Proof sketch or proof idea
Proof
(Exponential moment and Markov's inequality)
For any real , independence and give
For , Markov's inequality applied to gives
Choose to obtain the upper-tail expression. This choice minimizes the displayed exponential bound because its exponent has derivative and positive second derivative.
For the lower tail take . Exponentiation reverses the event's direction: implies . Markov again gives the same expression with negative . Choosing yields the stated lower bound. The reversal is essential; using a positive exponential in that step would bound the wrong event.
For the simplified upper bound, set . Then and is not everywhere nonnegative, so that observation alone does not prove the claim. Instead, is concave on , is zero at , and is positive at because . A concave function lies above its chord, so throughout the interval and . To see , integrate the pointwise identity on ; the right side is nonnegative and positive except at one point, while the linear term integrates to .
For the lower bound, set . Here and for . Thus , giving the lower quadratic estimate. At the endpoint , independence gives , completing the stated lower-tail range. Finally apply the union bound to the upper and lower events; independence between those two events is not needed.
Proof X-ray
Where independence enters
Where each hypothesis enters: independence is used exactly once, to write as the product ; Markov's inequality needs only nonnegativity. The key move is the exponential, which turns a sum into a product and leaves the parameter as a free knob to be optimized afterwards. The inequality then reduces every factor to , so only survives. For the lower tail, a negative reverses the event inclusion. The simplified forms close by a calculus comparison on , which is why they are stated only in that range. Without independence the factorization fails, as the identical-variables counterexample later shows.
Worked examples
Worked example 3.1.3
(Independent coin tosses)
Toss a fair coin times and let count heads. Then . Taking gives . The sharper expression is . Neither number is the exact binomial probability.
Worked example 3.1.4
(A lower-tail guarantee)
Suppose independent trials succeed with probabilities , so . The probability of at most successes is bounded using by . This is a guarantee on the chance of a shortfall, not a statement that exactly successes always occur.
Worked example 3.1.5
(A sample size for a relative estimate)
Let independent Bernoulli samples have common unknown success probability , and estimate it by . If a known lower bound holds, then for the theorem gives
To make this at most , it suffices to take and round up to an integer. The lower bound is needed to choose this relative-error sample size in advance.
Common mistakes
Counterexample mode
Identical means do not replace independence
Let be a fair Bernoulli variable and take every . Then , but . The independent-variable upper bound at tends to zero exponentially in . Thus identical marginal distributions alone are insufficient; all variables here are perfectly dependent.
Common mistake
(Mixing absolute and relative deviations)
Do not insert an absolute error into a relative-error bound without conversion. An event corresponds to only if , and the convenient quadratic upper bound above additionally assumes . For larger deviations use the first theorem or prove another bound with its own stated range. A bound greater than one is valid but uninformative; it can always be combined with the trivial upper bound of one.
Choosing the exponential parameter
The parameter in the proof is not a property of the random experiment. It is a knob available to us because Markov's inequality holds for every positive threshold applied to every nonnegative random variable. For an upper tail we may choose any positive , derive a valid bound, and then choose the one giving the smallest right-hand side. The minimizing value depends on the deviation threshold. If one picks a convenient but nonoptimal parameter, the result remains valid; it may simply be weaker.
Concept lensAnalytic
The bound as an exponential of a rate function
For , the best bound over is . This supremum is the Legendre transform of , and it equals . So the first theorem says the tail is at most , where is the rate function of a Poisson variable with mean .
The direction of the exponential is equally important for a lower tail. When is negative, increasing decreases . A small value of is thus converted into a large value of a nonnegative variable, which is precisely the kind of event Markov controls. Both arguments use the same moment bound, but the sign and the monotonicity of the exponential distinguish the events. Writing down the event inclusion before applying Markov is a reliable way to prevent a sign error.
The product estimate uses the mean but discards other information. Specifically, can be loose, and multiplying those inequalities retains only the sum of the . If the exact probabilities are known, one may keep the product and optimize its Markov bound numerically. For equal probabilities, the exact distribution is binomial, and one may instead sum the corresponding binomial probabilities. The simple bounds are valuable because they give a portable guarantee without requiring those exact calculations.
Worked example 3.1.6
(A union bound across many counters)
Suppose each of counters is a sum of independent indicators with mean . Independence is required within each counter, but different counters may share randomness. For each one the lower-tail probability of falling to at most is at most . The probability that at least one counter falls that low is therefore at most . The union bound remains valid with shared randomness across counters. It is incorrect to multiply the individual failure probabilities without establishing independence of the failure events.
Comparing multiplicative and additive estimates
The companion concentration note proves an additive Hoeffding inequality for independent Bernoulli variables and uses it to amplify majority votes. Its bound for an upward deviation by is ; the multiplicative bound here instead scales with the mean. Both are valid under their stated assumptions, but neither should be declared universally better without comparing the actual exponents. When successes are rare, can be much smaller than , and the multiplicative estimate can capture this sparsity.
For example, let independent indicators each have success probability , so . To bound the probability of at least successes, use . The quadratic multiplicative estimate gives ; the additive Hoeffding estimate with gives . The sharper multiplicative formula gives . All three are upper bounds on the same event, and one is free to use the smallest valid bound. The exact probability, if needed, can be calculated from the binomial distribution for this equal-probability example.
The different denominators explain the contrast. Hoeffding's bound uses only the number of bounded independent variables and the additive displacement. The multiplicative argument uses the sum of their success probabilities to bound the moment-generating function. A small mean supplies additional information, but the advantage depends on the event and parameters. In another parameter range Hoeffding may be sharper. Comparing numerical estimates is a mathematical step; selecting a named inequality without checking its hypotheses and scale is not sufficient.
A threshold specified independently of the mean
Sometimes a design target supplies an absolute threshold while only an upper bound on the mean is known. If , the upper-tail proof gives a useful guarantee without pretending that is the true mean. For every ,
because . Choosing gives
Common mistake
(Using an upper bound on the mean for a lower tail)
This calculation uses the upper bound in the correct direction. For a lower tail the sign of is negative, so substituting an upper bound on in the same manner would reverse the relevant inequality; a lower bound on is the useful information there.
As an illustration, suppose the sum of independent indicator means is at most and the undesired threshold is . Then the displayed result bounds the event by . No assertion that the mean equals five is needed. If the upper bound is zero, every indicator has mean zero and the sum is zero almost surely, so positive thresholds have probability zero directly.
The upper-threshold argument also explains how to use a rounded numerical estimate safely. A certified upper bound on the mean may replace the actual mean for an upper-tail calculation through the displayed inequality. An approximate estimate without a certified direction cannot automatically be substituted. In code, track whether a computed quantity is an upper or lower bound, along with the strict conditions on its use.
Relative and absolute accuracy
For the sample proportion, relative error is proportional to the unknown . When is small, even a small absolute error can be a large relative error. The lower bound in the example ensures enough expected successes for the multiplicative estimate to be informative uniformly over all permitted . If there is no positive lower bound, no finite sample size selected solely from and can provide the displayed relative guarantee uniformly for all positive : values of can be chosen so small that seeing no successes is very likely.
To see this directly, fix and choose a sufficiently small positive . The probability of seeing no successes is , which tends to one as . On this event , and its relative error is one. For any , the event therefore violates the desired relative accuracy. This argument does not say that estimation is impossible when is known or when an adaptive procedure has additional assumptions; it explains the limitation of a fixed sample size uniform over all positive probabilities.
An absolute-error guarantee asks instead for with a fixed . Its appropriate sample complexity can be studied using other concentration bounds that do not require a known lower bound on . One must not silently replace one problem with the other: for instance, an absolute error of is small when but is ten times when . The quantity being estimated determines which failure event the mathematics should bound.
Interpreting the bound in an algorithm
A probability statement describes the distribution induced by a specified algorithm and input. It does not identify which individual executions succeed. If the algorithm can verify its own output, a failed verification may permit a retry; the cost and independence of retries must then be analyzed. If no such verification is available, the tail estimate still bounds the probability of an inaccurate answer, but it does not enable the algorithm to recognize that answer after the fact.
It is also useful to distinguish a tail bound from a guarantee on the expectation. A mean of does not forbid a result of , and a tiny probability of such a result does not make the result impossible. When a design requires failure probability at most , the calculation must show that the numerical upper bound is no larger than . If the bound is , for example, it is not a proof of a target even if the exact probability happens to be smaller. One can increase the number of trials, use the sharper expression, or calculate an exact probability if the model supports it.
The stated upper and lower tail inequalities include equality at the threshold. For an integer-valued count a real threshold such as can be implemented as in the upper-tail event or in the lower-tail event. The probabilistic inequality remains valid as written; rounding the threshold in the wrong direction changes the event and can produce an invalid numerical conclusion. Explicitly identifying this integer event is especially useful when checking code against the analytic bound.
Summary
Exponentiating the count lets independence factor the expectation, and Markov's inequality converts that expectation into upper and lower tail estimates. For deviations that are a fixed fraction of the mean, failure probability decreases exponentially with the mean. The sample-size application requires independence and a positive known lower bound on the success probability.
Exercises
Quick check
(For independent fair coin tosses, use the quadratic bound to estimate the chance of at least heads.)
Compute , then find with .
Solution · Answer
Here and , so the probability is at most .
Quick check
(Let count independent successes each with probability . Bound .)
Find with and use the lower-tail bound.
Solution · Answer
Here and , giving .
Quick check
(Why is the theorem not applicable to for all , where is a single Bernoulli variable with success probability ?)
Compare with the product of the marginals.
Solution · Answer
The variables are not independent: for example, , whereas the product of their marginal probabilities is . The needed factorization of the exponential expectation is invalid.
Quick check
(For relative error , known and failure target , give a sufficient integer sample size from the displayed formula.)
Evaluate and round up.
Solution · Answer
The formula gives , so is sufficient. The result is an upper-bound guarantee, not a claim of the smallest possible sample size.