Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

• The chapter assembles expectations, variances, coupon collection, standard concentration inequalities, stochastic domination, and bounds for geometric or non-fully independent variables, often with applications.Its purpose is to collect tools repeatedly used in the field and explain or reference typical applications.Source: §1.1 · p. 3
• Known Chernoff bounds for binary variables extend to negatively correlated variables, requiring 1-negative correlation for upper tails and 0-negative correlation for lower tails.The result is identified as original to the chapter’s authors.Source: §1.1 · p. 3
• All commonly known Chernoff bounds can be derived from only two bounds.This is listed among the chapter’s original results.Source: §1.1 · p. 4
• A bounded-differences variant requires only that variable t have bounded influence on the expected contribution of variables t + 1 through n.It is presented as a compromise between classic bounded differences and martingale methods for iterative algorithms.Source: §1.1 · p. 4
• An elementary two-stage rounding trick yields simple proofs for deviation and point-probability properties of sums of independent binary random variables.The deviation result assumes Var[X] ≥ 1 and guarantees a constant-probability excess over the expectation by a quantity involving Ω; the point-probability result is bounded using Var[X].Source: §1.1 · p. 4
• The chapter also provides elementary guidance for selecting Chernoff deviation parameters and converting tail bounds into expectations.These reformulations are intended to save users time while keeping attention on the harder random processes in nature-inspired heuristics.Source: §1.1 · p. 4

1.2 Notation

• The chapter defines N := {1, 2, . . .}, N_0 := N ∪ {0}, [a..b] := {x ∈ Z | a ≤ x ≤ b}, and 0^0 := 1.The notation is standard and requires little additional explanation.Source: §1.2 · p. 4

1.3 Elementary Probability Theory

• The exposition assumes basic probability knowledge and focuses on discrete random variables, while allowing arithmetic operations on variables defined over the same probability space.Probability spaces are usually left implicit for intuitive accessibility.Source: §1.3 · p. 5
• Bernoulli random variables take only 0 and 1, with their distribution determined by the probability of being 1; they commonly indicate whether an event occurs.For example, a die-roll indicator equals 1 when the die shows 6 and 0 otherwise.Source: §1.3 · p. 5
• Summing independent binary variables with common success probability p yields a binomial random variable, denoted X ∼ Bin(n, p), which counts successes across n trials.Indicator variables therefore provide a direct way to count occurrences such as sixes in repeated die rolls.Source: §1.3 · pp. 5–6
• A geometric random variable Y ∼ Geom(p) records the first success in independent trials with success probability p.Some sources instead count failures and use Y − 1, so definitions must be checked when comparing results.Source: §1.3 · p. 6

1.4 Useful Inequalities

• The section introduces inequalities for estimating probabilities that arise naturally in randomized search heuristics.These tools support the broader probabilistic analysis developed in the chapter.Source: §1.4 · p. 6

1.4.1 Switching Between Exponential and Polynomial Terms

• Bounds such as 1 + x ≤ e^x convert polynomial expressions into exponential terms, with estimates strongest near zero and useful for factors like (1 − x)^y.The section also records Bernoulli’s inequality and Weierstrass product inequalities, including an upper bound attributed to [RS14, Lemma 8] and a sharper result from [DGWY17, Lemma 8(c) of the arxiv version].Source: §1.4.1 · pp. 6–9

1.4.2 Harmonic Number

• The harmonic number H_n is frequently encountered and can generally be approximated by ln n, while H_n − ln n decreases monotonically to γ ≈ 0.5772156649.The simple logarithmic estimate is usually sufficient, whereas the Euler–Mascheroni constant supports sharper non-asymptotic estimates.Source: §1.4.2 · pp. 9–10

1.4.3 Binomial Coefficients and Stirling’s Formula

• Binomial coefficients admit elementary crude estimates and sharper Stirling-based bounds, while large-deviation bounds can estimate binomial sums and individual coefficients away from the middle.The section notes applications in randomized search heuristics and [DW14], including mutation rates differing from 1/n.Source: §1.4.3 · pp. 10–12

1.5 Union Bound

• For arbitrary events E1, . . . , En, the union bound follows directly from σ-additivity and requires no independence assumptions.It is tight when the events are disjoint.Source: §1.5 · pp. 12–13, §1.5.2 · p. 15

1.5.1 Example: The (1+1) EA Solving the Needle Problem

• For all η > 0 and c > 0, the first L := 2^cn search points of the (1 + 1) EA, or any unbiased algorithm, stay far from the needle optimum with probability at least 1−2^(c−2 ln(2)η²)n.The proof combines a Chernoff bound for each uniformly distributed search point with a union bound, despite strong correlations between successive points.Source: §1.5.1 · pp. 14–15

1.5.2 Lower Bounds, Bonferroni Inequalities

• When L = o(2^n) independent blind-search iterations target the needle optimum, Pr[T ≤ L] = (1 − o(1))L2^−n, making the union-bound estimate asymptotically tight.The second Bonferroni inequality supplies the matching correction needed for this lower-bound estimate.Source: §1.5.2 · pp. 15–16
• Bonferroni inequalities bound event-union probabilities by truncating inclusion-exclusion, with the inequality direction determined by whether the truncation index k is odd or even.The first omitted term controls the error direction: odd k yields an upper bound, while even k yields a lower bound.Source: §1.5.2 · p. 16

1.6 Expectation and Variance

• Expectation and variance are two key characteristic numbers of a random variable.Source: §1.6 · p. 17

1.6.1 Expectation

• Expectation can be recovered from tails: the tail-sum formula supports exponential-tail estimates and gives a geometric variable with success probability p expected waiting time 1/p.The same approach transforms tail information into expectation bounds and supplies a correct waiting-time proof.Source: §1.6.1 · pp. 17–18
• Linearity of expectation applies to arbitrary random variables, enabling formulas for binomial variables, mutation and crossover distances, even under dependencies.For standard-bit mutation, E[H(x,z)] = pn; for uniform and 1-point crossover, the expected distance is 1/2(H(x,x∗) + H(y,x∗)).Source: §1.6.1 · pp. 18–19

1.6.2 Markov’s Inequality

• Markov’s inequality bounds upper deviations for non-negative variables, while its reverse form handles variables bounded above; the first moment method gives Pr[X ≥1] ≤ E[X].It is useful with limited information and can match the union bound when combined with linearity of expectation.Source: §1.6.2 · p. 20

1.6.3 Chebyshev’s Inequality

• Chebyshev’s inequality uses variance for two-sided deviation bounds, while Cantelli gives a one-sided alternative and the second moment method can establish positivity.For blind random search, independence yields Pr[T ≤L] = Pr[X > 0] ≥ 1 − 1/(L2−n), improving the corresponding Bonferroni estimate when E[X] is large.Source: §1.6.3 · pp. 21–23

1.7 Conditioning

• Conditioning on an event C with Pr[C] > 0 creates a new probability space, with conditional expectations defined analogously; E[X | Y] instead denotes a function of Y.The conditional random variable (X | C) assigns probability Pr[X = x] / Pr[C] to x.Source: §1.7 · pp. 23–24

1.7.1 Decomposing Events

• For an intersection A1 ∩ A2, conditioning enables the factorization Pr[A1 ∩ A2] = Pr[A1] Pr[A2 | A1].This decomposition is useful when the component probabilities, including the conditional probability, can be computed directly.Source: §1.7.1 · p. 24

1.7.2 Case Distinctions

• A partition C1, . . . , Ck supports case distinctions by analyzing the problem conditional on each Ci and applying the laws of total probability and total expectation.The section states these laws formally for an event A and random variable X.Source: §1.7.2 · p. 24

1.7.3 Excluding Rare Events

• Conditioning on an almost-sure event changes event probabilities only slightly, allowing rare unwanted events to be excluded while correcting unconditional calculations by a minor amount.For standard-bit mutation, the chapter gives the example of conditioning on no more than n1/4 bits flipping in the first n2 applications, with probability 1−2−Ω(n1/4), as used in Theorems 7 and 8 of. Conditioning can nevertheless destroy independence among bit-flip events.Source: §1.7.3 · pp. 24–25

1.7.4 Conditional Binomial Random Variables:

• For X ∼ Bin(n, p), conditioning on X ≥ k yields the stronger stochastic-domination statement that (X | X ≥ k) is dominated by k + Bin(n − k, p), from which tail bounds can be obtained [DD18, Lemma 1].The chapter notes that the intuitive expression k + p(n − k) is an upper bound despite the argument behind it being incorrect.Source: §1.7.4 · pp. 25–26

1.8.1 The Notion of Stochastic Domination

• Stochastic domination compares random variables through their cumulative distributions, with X ⪯ Y meaning Pr[X ≤ λ] ≥ Pr[Y ≤ λ] for every λ.The relation is equivalent to the existence of a coupling in which the copy of X is point-wise at most the copy of Y.Source: §1.8.1 · p. 27, §1.8.4 · p. 33

1.8.2 Stochastic Domination in Runtime Analysis

• For runtime analysis, stochastic domination bounds an algorithm’s runtime by a sum of independent geometric random variables, yielding expectation and high-probability bounds.The domination-version fitness level method assumes a probability p_i of moving from level A_i to A_≥i+1, and recovers the classic fitness level theorem’s expectation bound.Source: §1.8.2 · p. 29

1.8.3 Domination by Independent Random Variables

• Sequential domination shows that dependent discrete random variables can be compared with independent variables, transferring domination to their sums.The comparison is conditioned on every feasible history and extends to sums over arbitrary subsets through inherited sequential domination.Source: §1.8.3 · p. 30

1.8.4 Coupling

• Coupling constructs variables with the required marginal distributions on one probability space, often making point-wise comparisons easier than direct distributional calculations.For standard-bit mutation rates p ≤ q, shared uniform random numbers give ˜X_p ≤ ˜X_q with probability one and therefore X_p ⪯ X_q.Source: §1.8.4 · pp. 31–32
• The coupling results establish X ⪯ Y exactly when a coupling exists with ˜X ≤ ˜Y, and give analogous domination relations for binomial and geometric distributions.These include Bin(n,p) ⪯ Bin(n,q) for p ≤ q, Bin(n,p) ⪯ Bin(m,p) for n ≤ m, X ⪯ (X | X ≥ x) ⪯ X + x, and Geom(p) ⪯ Geom(q) for p > 0.Source: §1.8.4 · pp. 32–33

1.8.5 Domination in Fitness or Distance

• The section extends domination beyond runtimes to fitness or distance comparisons, using it with coupling to give a shorter proof for Witt’s mutation-based runtime result.The discussed (µ, p) mutation-based algorithms initialize µ uniform independent search points and generate offspring through standard-bit mutation with static rate p; the class includes corresponding (µ + λ) and (µ, λ) EAs.Source: §1.8.5 · pp. 33–34
• The comparison uses sequentially generated initial individuals and selects the last maximal-fitness initial point without changing its distribution, ensuring the runtime definition also covers initially optimal solutions.The runtime T(A, f) counts the first generated optimum, including among the µ initial individuals.Source: §1.8.5 · p. 34
• T((1 + 1) EAµ, OneMax) ⪯ T(A, f) for every (µ, p) mutation-based algorithm A and fitness function f with a unique global optimum.This domination enables lower bounds for many algorithms on essentially arbitrary fitness functions by analyzing the (1 + 1) EAµ on OneMax.Source: §1.8.5 · p. 34
• If |x|1 ≤ |y|1, standard-bit mutation with rate p preserves this ordering stochastically for the offspring, so |x′|1 ⪯ |y′|1.This offspring relation is the key local domination step used in the alternate proof of Theorem 1.8.11.Source: §1.8.5 · p. 34
• The coupling constructs runs with |˜x(t)|1 ≤ |˜y(t)|1 for every t, making the OneMax process reach |˜y(t)|1 = n no later than A reaches its optimum.The coupled sequence has the same distribution as the (1 + 1) EAµ run, yielding the runtime domination.Source: §1.8.5 · p. 35
• [BE08] proves its fitness-domination result by induction over time t, comparing the two distributions manually with an argument called an Abel transform rather than simply coupling the processes.Source: §1.8.5 · p. 36

• For RLS on strictly monotonically increasing functions, the optimization time is exactly a coupon collecting time and is at most the classic coupon collector time.The missing 1-bits act as coupons: repeated bit flips are discarded, while new 1-bits advance the search.Source: §1.9 · pp. 36–37
• E[Tn] = nHn = (1 + o(1))n ln n for collecting all n coupon types.The process decomposes into waiting times for successive new coupon types.Source: §1.9 · p. 37
• A union-bound argument over coupons gives tail bounds for Tn by bounding the probability that some coupon is still missing after t rounds.A fixed coupon is absent for t rounds with probability (1 − 1/n)^t.Source: §1.9 · pp. 37–38
• The coupon collector also has a lower-bound analysis based on negative correlation among events that individual coupon types have appeared by a given time.The cited result addresses a previously missing good lower bound for the collecting time.Source: §1.9 · p. 38
• For the (1 + 1) EA on any function with a unique global maximum, the coupon-collector intuition yields a lower bound on optimization time.Initially missing bits must each be flipped at least once, motivating a coupon collector started with an initial stake of missing bits; the argument is explicitly described as non-rigorous intuition, while Theorem 1.9.4 formalizes a bound.Source: §1.9 · p. 39
• For OneMax, the (1 + 1) EA satisfies E[T] ≥ en ln n − O(n), and this lower bound extends to every function with a unique optimum.This improves earlier bounds of E[T] ≥ en ln n − O(n log log n) from and.Source: §1.9 · p. 39

Motivation

• Large deviation inequalities bound the probability that a random variable deviates excessively from its expectation, often enabling high-probability guarantees across many iterations via a union bound.They are especially useful because stronger tail bounds cover more iterations.Source: §1.10 · p. 40

Core bounds

• Multiplicative Chernoff bounds show that constant-factor deviations for sums of independent [0, 1] variables occur with probability negatively exponential in the expectation.The section also presents an additive Chernoff bound with probability exp(−2λ2 for deviations exceeding λ.Source: §1.10 · p. 40
• Large deviation bounds can use pessimistic expectation estimates, while bounded differences extends additive Chernoff bounds to functions of independent variables with individually small influence.These tools provide practical guidance when exact expectations or independence of the output itself are unavailable.Source: §1.10 · p. 40

Advanced results

• Bounds usually stated for independent sums also apply to negatively correlated variables, including distributions from sampling without replacement or with partial replacement.This extends standard tail-bound techniques beyond independence.Source: §1.10 · p. 41
• The section develops large deviation bounds for sums of independent geometrically distributed variables, which are particularly useful for analyzing randomized search heuristics.Such bounds are rarely used in analyses of classic randomized algorithms.Source: §1.10 · p. 41
• Theorem 1.10.28 weakens bounded differences by requiring each variable to influence only the expected outcome from later variables, potentially simplifying iterative-heuristic proofs.This condition is weaker than requiring bounded influence under every conditioning and may replace some martingale tail-bound arguments.Source: §1.10 · p. 41

1.10.1 Chernoff Bounds for Sums of Independent Bounded Random Variables

• Chernoff bounds apply to sums of independent variables with bounded ranges, including arbitrary bounded real values rather than only Bernoulli variables.The section uses the common name “Chernoff inequalities” for bounds historically associated with Bernstein, Chernoff, and Hoeffding.Source: §1.10.1 · p. 41

1.10.1.1 Multiplicative Chernoff Bounds for the Upper Tail

• Multiplicative upper-tail bounds are often the right tool when constant-factor deviations suffice, with tail regimes scaling as exp(−Θ(δ log(δ)E[X])), exp(−Θ(δE[X])), or exp(−Θ(δ^2E[X])).Hoeffding’s strongest bound does not require identically distributed variables and is optimal within the exponential-moments method under its assumptions [Hoe63].Source: §1.10.1.1 · pp. 42–43
• For standard-bit mutation, Chernoff bounds show that across n^c2 applications with mutation rate α/n, exceeding (c1+c2+o(1)) ln n bits has probability at most n^−c1.The bounds are independent of n and depend only mildly on α, supporting evolutionary-algorithm analyses.Source: §1.10.1.1 · p. 45

1.10.1.2 Multiplicative Chernoff Bounds for the Lower Tail

• Upper- and lower-tail multiplicative bounds are equivalent through complementing variables, and constant-factor deviations from expectation occur with exponentially small probability.The lower-tail formulation can provide a better exponent constant, including 1/2 in the relevant bound.Source: §1.10.1.2 · pp. 46–47

1.10.1.3 Additive Chernoff Bounds

• Additive Chernoff bounds are symmetric between tails and invariant under additive rescaling, becoming slightly stronger than simplified multiplicative bounds when E[X] is close to n/2.They also bound Hamming distances of uniformly random search points, a standard ingredient in lower-bound arguments.Source: §1.10.1.3 · p. 48

1.10.1.4 Chernoff Bounds Using the Variance

• Variance-sensitive Chernoff bounds can be significantly stronger than earlier estimates for independent variables satisfying Xi ≤ E[Xi] + 1, with analogous lower-tail bounds obtained by replacing Xi with −Xi.The section derives these estimates from Hoeffding’s result.Source: §1.10.1.4 · p. 50
• The bounds extend to lower tails and to variables satisfying Xi ≤ E[Xi] + b by scaling from the unit-bound case, with analogous lower-tail estimates when Xi ≥ E[Xi] − b.The resulting theorem is equivalent to Theorem 1.10.12 and Corollary 1.10.13.Source: §1.10.1.4 · pp. 51–52
• Variance-sensitive Chernoff bounds can replace the expectation of X by its variance, but offer little advantage when binary variables have small Pr[Xi = 1].They are more useful when Pr[Xi = 1] is close to 1.Source: §1.10.1.4 · p. 51
• For standard-bit mutation, the number of ones can have large expectation but variance np(1 − p), so variance-sensitive bounds yield better estimates when p is small.This applies even when the parent search point contains many ones; the same reasoning can estimate Hamming distance to another search point, including a unique optimum, and appeared in [DGWY17].Source: §1.10.1.4 · p. 51
• When high precision is unnecessary, separately bounding flipped zeros and ones with standard Chernoff bounds can avoid variance-sensitive bounds, despite more technical computations.Several research works use this workaround.Source: §1.10.1.4 · p. 51
• Variance-sensitive Chernoff bounds also apply to ant colony and estimation-of-distribution algorithms when pheromone values or frequencies near 0 or 1 produce small variance.Examples are given in [Wit17].Source: §1.10.1.4 · p. 51

1.10.1.5 Relation Between the Different Chernoff Bounds

• 1.10.1.5 Relation Between the Different Chernoff Bounds: Variance-based Chernoff bounds imply essentially all preceding bounds, except the additive bound for variables with different ranges.The strongest variance-sensitive bound also implies the strongest forms of Theorems 1.10.1 and 1.10.5; the exception can be significantly stronger for unequal ranges.Source: §1.10.1.5 · pp. 52–53
• 1.10.1.5 Relation Between the Different Chernoff Bounds: Subtracting expectations removes Hoeffding’s common-expectation assumption without changing variances or centered distributions.This yields the versions corresponding to Theorems 1.10.12 and 1.10.14 and connects Theorem 1.10.12 to Theorem 1.10.1.Source: §1.10.1.5 · pp. 52–53
• 1.10.1.5 Relation Between the Different Chernoff Bounds: For unequal variable ranges, Theorem 1.10.9 can yield exp(−Θ(λ log λ)) estimates where the strongest variance-based bound is weaker.The example uses independent variables with n−1 variables having range (n−1)^−1/2 and one variable having range 1.Source: §1.10.1.5 · p. 53

1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration)

• 1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration): The sharpest Chernoff bounds are often near-tight, so sharper bounds may not rescue an otherwise unprovable target.Lower bounds on deviations are nevertheless important when parallel offspring rely on the best sample exceeding its expectation.Source: §1.10.1.6 · pp. 53–54
• 1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration): Anti-concentration is harder to use; the section therefore gives brief guidance, including binomial-tail estimates and a general independent-binary-variable result.The general result extends earlier special cases, while requiring a variance restriction for meaningful guarantees.Source: §1.10.1.6 · pp. 54–55
• 1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration): Binomial-coefficient estimates, normal approximation, and order statistics provide complementary routes to lower-tail probabilities and best-of-k deviations.The maximum of k independent samples has a constant-probability threshold when an individual sample reaches that threshold with probability Θ(1/k).Source: §1.10.1.6 · pp. 54, 59
• 1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration): A two-stage rounding trick extends anti-concentration arguments from identically distributed binary variables to sums with different success probabilities.The construction first preserves each expectation through an intermediate rounding and then rounds to a binary outcome without changing that expectation.Source: §1.10.1.6 · p. 54
• 1.10.1.6 Tightness of Chernoff Bounds, Lower Bounds for Deviations (Anti-Concentration): Additional tools cover extremal deviation configurations, Feige’s inequality for staying on one side of the expectation, and specialized binomial guarantees.These results support analyses of randomized search heuristics, including evolutionary and estimation-of-distribution algorithms.Source: §1.10.1.6 · p. 60

1.10.1.7 Proofs of the Chernoff Bounds

• The same proof strategy can establish Chernoff bounds for particular distributions where classic bounds are inapplicable or insufficient.Such applications appear in [OW12].Source: §1.10.1.7 · p. 61
• Chernoff proofs apply Markov’s inequality to e^(hX), factor the exponential moment using independence, and optimize h.This central argument also supports extensions to negatively correlated variables.Source: §1.10.1.7 · p. 61
• For Xi in [0,1], convexity reduces the worst-case exponential moment to a distribution concentrated at 0 and 1, yielding the strongest multiplicative Chernoff bound.The bound follows by rewriting t = (1 + δ)E[X].Source: §1.10.1.7 · pp. 61–62
• Chernoff inequalities usually hold strictly rather than tightly, except for two-point variables, single-point tail events, or empty tail events.These strict inequalities generally have only cosmetic consequences.Source: §1.10.1.7 · p. 62

1.10.1.8 Chernoff Bounds with Estimates for the Expectation

• Chernoff bounds remain valid when E[X] is replaced by an upper bound µ+ or by a lower bound µ−≤E[X], subject to the specific bounds explicitly identified in the cited passages.For µ+, this includes Theorem 1.10.1 (including equations (1.10.7) and (1.10.8) and Corollary 1.10.4), Theorem 1.10.10, additive bounds (1.10.13) and (1.10.15), and Theorems 1.10.12 and 1.10.14; for µ−, equations (1.10.14) and (1.10.16) and Corollary 1.10.13.Source: §1.10.1.8 · pp. 62–63
• For upper tails, adding γ(1 − Xi) constructs Yi ≥ Xi with E[Y] = µ+, so the exact-expectation Chernoff bound for Y implies the estimate-based bound for X.The construction assumes (1 + δ)µ+ ≤ n and γ ≤ 1.Source: §1.10.1.8 · p. 63
• The same monotonicity argument extends multiplicative variance-based bounds: the constructed Y has variance at most that of X, so upper-estimate substitutions remain valid.This applies to multiplicative versions such as equation (1.10.29).Source: §1.10.1.8 · p. 63

1.10.2 Chernoff Bounds for Sums of Dependent Random Variables

• Three dependent-variable settings recover essentially the usual Chernoff bounds despite the absence of full independence.The section covers unconditional sequential domination, negative correlation, and hypergeometric distributions.Source: §1.10.2 · p. 64

1.10.2.1 Unconditional Sequential Domination

• Unconditional sequential domination bounds upper and lower tails by corresponding Chernoff bounds for sums of independent dominating variables.The approach applies when each iteration has a conditional success probability independent of the past; it was used in shortest-path analyses and in.Source: §1.10.2.1 · p. 64

1.10.2.2 Negative Correlation

• 1-negative correlation yields the independent-variable Chernoff upper-tail bounds, while 0-negative correlation yields the corresponding lower-tail bounds.The results also permit replacing the exact expectation by an upper bound µ+ for upper tails or a lower bound µ− for lower tails.Source: §1.10.2.2 · pp. 65, 67

1.10.2.3 Hypergeometric Distribution

• Hypergeometric variables arise from sampling without replacement, whose negatively correlated indicators therefore satisfy the usual Chernoff bounds for independent binary variables.Symmetry in the sample size and subset size allows bounds depending on the number of variables to use min{n, m}; the result extends to independent families of such samples and was used in [DD18].Source: §1.10.2.3 · pp. 67, 69

1.10.3 Chernoff Bounds for Functions of Independent Variables, Martingales, and Bounds for Maxima

• The method of bounded conditional expectations controls functions of independent variables when changing one current variable alters the expected future outcome by at most c_i.This condition is motivated by the sequential use of randomness in randomized search heuristics and is presented as a weak version of McDiarmid’s Theorem 3.7.Source: §1.10.3 · p. 71
• For the cGA on a function with a neutral bit, the new theorem bounds the probability that the bit frequency reaches an absorbing state within the first T iterations.The proof represents the process using independent random variables and applies a conditional-influence bound, whereas the classic bounded-differences condition does not directly apply to this construction.Source: §1.10.3 · pp. 72–73
• The bounded-differences and bounded-conditional-expectations results are special cases of the Azuma-Hoeffding inequality for martingales, which has applications in randomized search heuristics [DK15, Köt16, DDY16b].The section notes that the conditional version can be more natural than bounded differences when current randomness has limited influence on the expected future result.Source: §1.10.3 · pp. 71, 73

1.10.3.1 Tail Bounds for Maxima and Minima of Partial Sums

• Tail bounds for a sum of independent variables transfer directly to the event that any partial sum exceeds the corresponding additive upper or lower threshold.The same deviation parameter λ is used across all partial sums, and the result supports maxima and minima through a stopped martingale argument.Source: §1.10.3.1 · p. 74
• The maxima bound does not yield a uniform relative-deviation statement such as Pr[∃i ∈[1..n] : S_i ≥(1 + δ)E[S_i]] ≤p because λ does not scale with i.For non-negative summands, the theorem additionally gives a trivial uniform bound.Source: §1.10.3.1 · p. 74

Motivation

• Because geometric random variables are unbounded, the preceding Chernoff bounds cannot be applied directly to their sums.Chernoff-type bounds for such sums were first used in randomized search-heuristic analysis in 2007, while strong bounds for substantially different success probabilities appeared later in.Source: §1.10.4 · pp. 74–75

Identical success probabilities

• For independent geometric variables with common success probability p, their sum is closely related to a negative binomial distribution, enabling Chernoff bounds derived from Bernoulli sums.The sum X of n such variables satisfies X ∼ NB(n, 1 − p) + n, and the resulting estimates are most useful for relatively large p.Source: §1.10.4 · p. 75

Different success probabilities

• For differing success probabilities, Theorem 1.10.33 bounds the tail using only p_min, which can be overly pessimistic when the probabilities vary substantially.This dependence is partly justified because the smallest success probability corresponds to the largest variance, but Witt’s result can provide stronger estimates in heterogeneous cases.Source: §1.10.4 · pp. 76–77

Proportional success probabilities

• When success probabilities are proportional to i, the section gives stronger tail bounds than the general heterogeneous estimate, including the bound Cn(1 + ln n).This setting frequently occurs in randomized search-heuristic analyses, and the cited result is from [DD18, Lemma 4].Source: §1.10.4 · pp. 77–78

Runtime applications

• The cited results give runtime bounds: E[T] ≤ enHn and Pr[T ≥ (1 + δ)en ln n] ≤ n−δ, while E[T] ≤ nn and Pr[T ≥ γnn] ≤ e−γ.The first bounds hold for all δ ≥ 0, and the second for all γ ≥ 0.Source: §1.10.4 · p. 78

Representation effects

• A superior representation can improve both expected runtime and tail behavior, changing sorting-runtime tails from inverse-polynomial to negative-exponential.The tree-based representation for sorting has tail bound Pr[T ≥ (1 + δ)E[T]] ≤ exp(−δ^2n/(2 + 2δ)).Source: §1.10.4 · p. 78

Motivation

• Binomial-specific tail bounds provide small improvements over general independent 0,1-variable bounds used in randomized search heuristics.The section motivates these bounds as stronger alternatives whose differences are usually small.Source: §1.10.5 · p. 80

Elementary estimate

• An elementary union-bound argument derives a simple binomial tail estimate by covering X ≥ k with events fixing k successful Bernoulli trials.For each k-subset T, the event that all trials in T equal 1 has probability p^k.Source: §1.10.5 · p. 80

Stronger tail bound

• Klar’s tail bound is often significantly stronger than Lemma 1.10.37, although no improvement to an existing randomized-search-heuristic analysis is known.The estimate is also described as tight up to the factor stated in the section, with Lemma 1.10.38 giving a slightly weaker related estimate.Source: §1.10.5 · pp. 80–81

Application to mutation rates

• For p = 1/n, the typical standard-bit-mutation rate, Lemma 1.10.38 yields substantially better estimates in many cases.The comparison follows from the section’s exponential estimate involving (1−p)^(n−k).Source: §1.10.5 · p. 81

Probability-function estimates

• Theorem 1.10.39 gives probability-function estimates for X ∼ Bin(n,p) with np ≥ 1 and k = np + h ∈ N, from which tail bounds follow by summing over k′ ≥ k.The theorem separately specifies a case with k < n and h > 0.Source: §1.10.5 · p. 81