Chernoff bounds in combinatorial models

Let X be the sum of independent Bernoulli variables, with possibly different success probabilities and positive total mean mu. Independence factors the exponential moment into a product. The elementary inequality one plus u is at most the exponential of u bounds each factor. Exponential Markov then introduces a positive parameter lambda, which can be optimized after the threshold is chosen. Merely knowing the mean and variance is insufficient to justify this factorization or the resulting exponential decay.

The optimized upper-tail expression involves the entropy-like function $h(\delta)=(1+\delta)\log(1+\delta)-\delta$. A convenient weaker bound replaces h by $\delta^2/(2+\delta)$ for nonnegative delta. Its constants are less sharp but its arithmetic is transparent. At a finite integer threshold r above mu, use delta equal to r divided by mu minus one. Rounding r in the wrong direction can turn an estimate for a smaller event into an unsupported bound for the event actually requested.

For a lower tail, use a negative exponential parameter, or equivalently a positive parameter on minus X. The standard multiplicative lower bound applies for delta between zero and one. It is not obtained by simply substituting a negative delta into a memorized upper-tail denominator. These bounds remain useful for nonidentical Bernoulli probabilities because the derivation depends on their sum, not on equality of their individual probabilities. When the mean is zero, the Bernoulli sum is zero almost surely and needs separate treatment.

Suppose a construction has M constraints, each with failure probability at most q. The probability of any failure is at most Mq, regardless of dependencies between the constraint events. Thus exponentially small marginal tails can withstand a polynomial number of checks. For example, if every relevant mean exceeds a suitable constant times log M, fixed relative deviations can often be excluded simultaneously. This requires a uniform lower bound on those means and a count of all constraints; checking only one representative constraint is not a simultaneous theorem.

A vertex degree in G(n,p) is a sum of independent edge indicators, so a Chernoff estimate applies directly to that degree. Degree counts at two different vertices share an edge and are not independent. Nevertheless a union bound can combine their individual estimates. By contrast, the triangle count is a sum of overlapping indicators, and applying the independent-summand formula to that sum is generally unjustified. One must expose independent edges through a different theorem or explicitly account for triangle dependencies.

A bound larger than one should be capped at one, and a small graph may give a weak result even when the asymptotic method is effective. Compare the proven upper bound with an exact binomial tail when available; their difference is the cost of a convenient inequality, not a contradiction. The distribution instrument displays a fully independent model with exact masses, which makes this gap inspectable. It should not be interpreted as empirical evidence for an arbitrary dependent combinatorial count.