PaperlayerView exact revision on arXiv

Source-linked AI summary

Probabilistic Tools for the Analysis of Randomized Optimization Heuristics

Benjamin Doerr

arXiv:1801.06733v6cs.DScs.DMcs.NEmath.PR

TL;DR

Analyses of randomized search heuristics use probabilistic methods that differ from those common in classic randomized-algorithm analysis. This chapter collects elementary and specialized tools, including inequalities, stochastic domination, coupling, and bounds for dependent variables, and illustrates their use in search-heuristic analyses.

  • Problem

    After about 20 years of theoretical analysis, randomized search heuristics still relied on probabilistic methods differing from those used for classic randomized algorithms.

  • Method

    The chapter synthesizes probabilistic tools including Markov, Chebyshev, and Chernoff inequalities, stochastic domination, coupling, and bounds for negatively correlated variables.

  • Results

    The collected tools yield analyses such as high-probability bounds showing that exponentially many early search points on the needle function remain far from the optimum.

  • Takeaways & Limitations

    The tools support analysis of randomized search heuristics and may also be useful for classic randomized algorithms and discrete random structures.

  • Takeaways & Limitations

    Lower bounds for deviations from expectation are harder to handle, so the chapter gives only brief guidance and refers readers to the literature.

Abstract

from arXiv · show

This chapter collects several probabilistic tools that proved to be useful in the analysis of randomized search heuristics. This includes classic material like Markov, Chebyshev and Chernoff inequalities, but also lesser known topics like stochastic domination and coupling or Chernoff bounds for geometrically distributed random variables and for negatively correlated random variables. Most of the results presented here have appeared previously, some, however, only in recent conference publications. While the focus is on collecting tools for the analysis of randomized search heuristics, many of these may be useful as well in the analysis of classic randomized algorithms or discrete random structures.

1.1 Introduction

The chapter collects probabilistic tools used in analyzing randomized search heuristics, combining standard inequalities with specialized results and several stated contributions.

  • The chapter collects expectations, variances, coupon collector processes, Markov, Chebyshev, and Chernoff-Hoeffding bounds.
  • It also covers stochastic domination, coupling, geometric-variable tail bounds, and bounds for not fully independent variables.
  • The large majority of results and applications appeared previously, while some stated results are presented as original.
  • All 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.
  • All commonly known Chernoff bounds can be deduced from only two bounds.
  • A bounded-differences variant limits the influence of each variable on the expected result from later variables, providing a compromise between bounded-differences and martingale methods.

1.2 Notation

The chapter uses standard notation for positive and nonnegative integers, integer intervals, and the convention 0^0 := 1.

  • Positive integers are denoted by N, nonnegative integers by N_0, and integer intervals by [a..b].
  • The convention 0^0 := 1 is used.

1.3 Elementary Probability Theory

This section introduces discrete random variables, binary indicators, binomial and geometric distributions, and basic operations on variables over a common probability space.

  • All random variables are assumed discrete, taking at most countably many values.
  • Random variables defined on the same probability space can be added or multiplied by a number.
  • A binary or Bernoulli random variable takes only 0 and 1, with its distribution determined by Pr[X = 1].
  • Indicator random variables encode events as binary values and can be summed to count occurrences.
  • A binomial random variable is the sum of n independent binary variables, each equal to one with probability p, denoted Bin(n, p).
  • A geometric random variable records the first success in an independent sequence with success probability p, denoted Geom(p).

1.4 Useful Inequalities

The chapter assembles elementary inequalities and estimates for exponential expressions, harmonic numbers, binomial coefficients, and binomial tails used in randomized-search analysis.

  • The section introduces inequalities that estimate probabilities arising naturally in randomized search heuristics.
  • 1.4.1 Switching Between Exponential and Polynomial Terms: The inequality 1 + x ≤ e^x supports switching between polynomial and exponential expressions.
  • 1.4.1 Switching Between Exponential and Polynomial Terms: The estimates in Lemma 1.4.2 are strongest for x close to zero, as also shown in Figure 1.1.
  • Bernoulli’s inequality gives (1 + x)^r ≥ 1 + rx for x ≥ −1 and r ∈ {0} ∪ [1, ∞).
  • The Weierstrass product inequalities provide lower and upper bounds for products involving p_1, ..., p_n ∈ [0, 1].
  • Harmonic numbers are defined by H_n and can be approximated using integrals, with H_n − ln n decreasing toward the Euler-Mascheroni constant.
  • Crude binomial-coefficient estimates are often sufficient, while Stirling’s formula supplies stronger estimates when needed.
  • Large-deviation bounds can estimate sums of binomial coefficients and single coefficients, especially away from the middle.

1.5 Union Bound

The union bound provides assumption-free probability estimates, while Bonferroni inequalities refine them using inclusion–exclusion. Applied to randomized search on the needle function, these tools yield exponential-time lower bounds and can replace more elaborate drift arguments.

  • Union bound: The union bound applies without independence assumptions and bounds the probability of any event in a finite union by the sum of their probabilities.It is tight when the events are disjoint.
  • Example: The (1+1) EA Solving the Needle Problem: On the needle function, all reasonable randomized search heuristics require exponential time to find the unique optimum.The (1 + 1) EA is used as a simple example.
  • Example: The (1+1) EA Solving the Needle Problem: For the (1 + 1) EA, with probability at least 1−2(c−2 ln(2)η^2)n, the first 2^cn search points remain farther than (1/2−η)n from the optimum.The result also applies to any unbiased black-box optimization algorithm.
  • Example: The (1+1) EA Solving the Needle Problem: The proof combines Chernoff bounds with a union bound because search points are uniformly distributed until the optimum is found.A coupling-style continuation after hitting the optimum preserves the needed containment argument.
  • Example: The (1+1) EA Solving the Needle Problem: For heavily correlated search points, the union bound still proves the needle-function lower bound, showing that independence is unnecessary.Consecutive auxiliary search points have expected Hamming distance exactly one.
  • Lower Bounds, Bonferroni Inequalities: Bonferroni inequalities alternate upper and lower bounds by truncating the inclusion–exclusion formula; the second inequality improves lower bounds for non-disjoint events.For blind random search, if L=o(2^n), then Pr[T≤L]=(1−o(1))L2^−n, so the union bound is asymptotically tight.

1.6 Expectation and Variance

Expectation and variance are central descriptors of random variables and support elementary analyses of waiting times, sums, mutation operators, and deviations. Markov’s and Chebyshev’s inequalities convert moment information into probability bounds, while tail-sum arguments recover expectations from tails.

  • Expectation: Expectation and variance are key characteristic numbers, and linearity of expectation computes sums without requiring independence.This makes expectation useful for decomposing complicated variables into simpler indicator variables.
  • Expectation: Tail-sum identities transform distribution-tail information into expectation bounds and support runtime analyses and drift-theorem proofs.The chapter also derives expectations from exponential tail bounds.
  • Expectation: A geometric random variable with success probability p has expected waiting time 1/p.The waiting-time proof sums the tail probabilities Pr[X≥i]=(1−p)i−1.
  • Expectation: For standard-bit mutation, E[H(x,z)]=pn and E[H(z,x∗)]=H(x,x∗)+p(n−2H(x,x∗)).Uniform and 1-point crossover yield the same expected distance because linearity ignores dependencies.
  • Markov’s Inequality: Markov’s inequality bounds upper deviations for non-negative random variables, and its first-moment form gives Pr[X≥1]≤E[X].It is especially useful when little information is available or the expectation is small.
  • Chebyshev’s Inequality: Chebyshev’s inequality uses variance to bound deviations from the expectation and thereby measures concentration around the mean.For the needle search example, it gives Pr[T≤L]≥1−1/(L2^−n), improving the Bonferroni estimate when E[X] is large.

1.7 Conditioning

Conditioning creates a new probability space in which desired events can be assumed, enabling conditional probability and expectation calculations. It is useful for excluding rare events, but can alter dependencies; near-certain conditioning limits the resulting changes.

  • Conditioning: Conditioning on an event C with positive probability changes event probabilities and defines conditional expectations within the restricted probability space.The chapter distinguishes conditioning on an event from conditional expectation with respect to a random variable.
  • Conditioning: The product rule computes Pr[A1∩A2] as Pr[A1]Pr[A2|A1], while partition-based laws combine conditional probabilities or expectations across cases.These identities support case-based analyses of randomized heuristics.
  • Excluding Rare Events: Conditioning can exclude rare unwanted events, such as more than n^1/4 bits flipping in any of the first n^2 mutation applications, with probability 1−2^−Ω(n^1/4).The resulting high-probability event can then be assumed during the analysis.
  • Excluding Rare Events: Conditioning on a rare-event exclusion changes the probability space and can destroy independence among bit-flip events.When the conditioning event has probability 1−p, event probabilities change only by a small amount controlled by p.
  • Conditional Binomial Variables: For binomial X∼Bin(n,p), conditioning on X≥k yields the stronger stochastic-domination statement (X|X≥k) is dominated by k+Bin(n−k,p).This bound can also be used to obtain tail bounds for the conditional variable.

1.8 Stochastic Domination and Coupling

Stochastic domination and coupling provide complementary ways to compare randomized processes, including runtime distributions and distances from optima. The chapter develops these tools and applies them to derive runtime comparisons for mutation-based algorithms.

  • Coupling: Coupling realizes two random variables on a common probability space so that pointwise comparison becomes possible.Domination is equivalent to the existence of a coupling with X̃ ≤ Ỹ.
  • Stochastic domination: Stochastic domination compares random variables through their distribution functions, even when they are defined on different probability spaces.Y dominates X when Pr[X ≤ λ] ≥ Pr[Y ≤ λ] for every λ.
  • Runtime analysis: Stochastic domination formalizes when one runtime is always preferable: if A’s runtime dominates B’s, algorithm B is preferable from the runtime perspective.The relation also yields comparisons of expectations and other monotone functions.
  • Basic comparison results: The framework supports comparisons for binomial and geometric variables, including monotonicity in success probabilities and sample sizes.The chapter states X ⪯ Y for Bin(n,p) versus Bin(n,q) and for Geom(p) versus Geom(q) under the stated conditions.
  • Domination in fitness or distance: Domination arguments extend beyond runtime distributions by comparing fitness or distance trajectories, enabling lower bounds on essentially arbitrary fitness functions through OneMax.The chapter presents this as an application of domination to mutation-based algorithms.
  • Domination in fitness or distance: For any mutation-based algorithm on a function with a unique optimum, the runtime on OneMax by (1 + 1) EAµ stochastically dominates the comparison runtime.The proof couples search points so the comparison process is at least as close to the optimum at every time.

1.9 The Coupon Collector Process

The coupon collector process models the time needed to obtain every one of n equally likely coupon types and serves as a central tool in randomized-algorithm analysis. Its expectation and concentration bounds explain analogous runtime behavior in randomized search heuristics.

  • Applications to search heuristics: The coupon collector process appears directly in randomized local search on strictly monotone functions, where missing bits act as coupons.The optimization time is exactly a coupon collecting time with an initial stake of coupons and is at most the classic process started with none.
  • Expectation: The expected time to collect all n coupons is E[T_n] = nH_n = (1 + o(1))n ln n.The process gains a new coupon with probability (n−k)/n after k distinct types have been collected.
  • Process structure: Coupon collecting time is the sum of waiting times for successive new coupons, each modeled by an independent geometric random variable.This decomposition supports both expectation calculations and tail bounds.
  • Concentration: Chebyshev’s inequality, geometric-variable Chernoff bounds, and a union bound provide increasingly informative concentration results for T_n.The union-bound approach considers the probability that a particular coupon is missed for t rounds.
  • Applications to search heuristics: A lower bound known for OneMax transfers to every function with a unique optimum through the stochastic-domination theorem.The cited result gives E[T] ≥ e n ln n − O(n) for OneMax and states that this lower bound extends to all such functions.

1.10 Large Deviation Bounds

This section introduces large-deviation tools for bounding unlikely deviations from expected values, emphasizing their usefulness in randomized search heuristics. It highlights standard Chernoff bounds alongside results for negative correlation, geometric variables, and iterative dependencies.

  • Purpose: High-probability bounds complement expectation calculations by controlling rare bad events across many iterations.A union bound can show that events with very small per-iteration probability remain unlikely over a large number of iterations.
  • Core tools: Simple multiplicative Chernoff bounds show that constant-factor deviations of sums of independent [0, 1] variables have probability exponentially small in the expectation.These bounds are often sufficient when asymptotic order matters more than exact constants.
  • Core tools: Additive Chernoff bounds control deviations of sums of n independent [0, 1] variables by an additive term λ with probability exp(−2λ^2).
  • Extensions: The chapter extends large-deviation reasoning beyond independence to negatively correlated variables, including distributions from sampling without replacement or partial replacement.
  • Extensions: It presents large-deviation bounds for sums of independent geometrically distributed variables, which are particularly useful for randomized search heuristics.
  • Extensions: A bounded-differences variant requires only bounded influence on the expected future outcome and may simplify analyses of iterative improvement heuristics.The authors contrast this with the stronger classic assumption and suggest it may yield elementary alternatives to martingale tail bounds.

1.10.1 Chernoff Bounds for Sums of Independent Bounded Random Variables

This section develops Chernoff bounds for sums of independent bounded random variables and explains how their forms apply to randomized search heuristics. It covers upper and lower tails, practical parameter choices, and examples involving mutation distances.

  • Setup: Chernoff and Hoeffding bounds apply to sums of independent variables in bounded ranges, including [0, 1], without requiring identical distributions.Hoeffding’s strongest bound does not require the variables to be identically distributed.
  • Multiplicative bounds: Multiplicative bounds are often preferable when constant-factor deviations are tolerable and larger deviations must be shown unlikely.
  • Multiplicative bounds: The upper-tail bounds divide into superexponential, exponential, and quadratic regimes according to the deviation parameter δ.The corresponding tail orders are exp(−Θ(δ log(δ)E[X])), exp(−Θ(δE[X])), and exp(−Θ(δ^2E[X])).
  • Applications: Chernoff bounds can be parameterized through δ so that the strong-bound tail expression (e/δ)^δ falls below a desired probability.
  • Applications: For standard-bit mutation with constant rate α, the probability of flipping more than (c1+c2+o(1)) ln n bits in any of the first n^c2 applications is at most n^−c1.
  • Multiplicative bounds: Constant-factor deviations from the expectation occur with exponentially small probability for sums of independent bounded variables.
  • Variance-sensitive bounds: Variance-sensitive bounds can be stronger than expectation-based bounds when binary variables have small success probabilities and small variance relative to their expectation.

1.10.1.5 Relation Between the Different Chernoff Bounds

This section relates the chapter’s Chernoff bounds and develops elementary tools for lower bounds on deviations. Variance-based bounds imply nearly all earlier bounds, while the two-stage rounding trick extends anti-concentration arguments to non-identically distributed binary variables.

  • Relations: Variance-based Chernoff bounds imply all other discussed bounds except the additive bound for variables with different ranges.
  • Relations: The variance-based implication does not require the common-expectation assumption used in the corresponding result of Hoeffding’s paper.Centering variables by subtracting their expectations preserves variance and the distribution of X−E[X].
  • Relations: The additive bound for variables with different ranges can be significantly stronger than variance-based bounds when ranges are heterogeneous.The section illustrates this with variables whose first n−1 ranges differ from the final variable’s range.
  • Tightness: Sharp Chernoff bounds are often near-tight, so failure to prove a desired statement may not be remedied by seeking sharper Chernoff inequalities.
  • Anti-concentration: Lower bounds for deviations, or anti-concentration results, are harder to use than upper-tail bounds and are treated only briefly.The chapter points readers to mathematical literature and notes specialized approaches for binomial variables.
  • Anti-concentration: The two-stage rounding trick converts a binary variable with probability p into an expectation-preserving construction suitable for extending binomial arguments.It first rounds p to an intermediate variable and then randomly rounds that outcome to {0,1}.

1.10.1.7 Proofs of the Chernoff Bounds

This section explains Chernoff proofs through exponential moments, Markov’s inequality, independence, and an optimized parameter choice. It also shows that many bounds remain valid when exact expectations are replaced by suitable estimates.

  • Extensions: The central exponential-moment argument can also be adapted to distributions for which classic Chernoff bounds are unavailable or insufficient.
  • Exponential-moment method: Chernoff proofs begin by applying Markov’s inequality to the nonnegative exponential transform e^(hX).Independence then factorizes the resulting exponential moment into the product of the individual moments.
  • Exponential-moment method: For [0, 1]-valued variables, convexity reduces the worst-case exponential moment to variables concentrated at 0 and 1.Optimizing h after this reduction yields the strongest multiplicative Chernoff bound.
  • Tightness: Chernoff bounds are generally strict rather than absolutely tight, except in specific two-point, single-point, or empty-tail cases.
  • Expectation estimates: Upper-tail Chernoff bounds remain valid when E[X] is replaced by an upper bound µ+ ≥ E[X].Lower-tail bounds analogously remain valid when E[X] is replaced by a lower bound µ− ≤ E[X].
  • Expectation estimates: A coupling construction with Yi ≥ Xi transfers upper-tail bounds from a variable with the exact expectation to one using the estimate µ+.

1.10.2 Chernoff Bounds for Sums of Dependent Random Variables

This section explains how Chernoff bounds remain useful when independence is absent, using sequential domination and negative correlation. Appropriate one-sided negative-correlation conditions, including those in hypergeometric sampling, recover standard tail bounds.

  • Overview: Known Chernoff bounds apply in several settings where dependencies prevent full independence.The section treats sequential processes, stochastic domination, and negatively correlated binary variables.
  • Sequential domination: Unconditional sequential domination bounds a dependent sum by a sum of independent random variables, transferring upper-tail Chernoff bounds.The analogous subdomination argument transfers lower-tail bounds.
  • Negative correlation: 1-negative correlation suffices for upper-tail Chernoff bounds, while 0-negative correlation suffices for lower-tail bounds.Negative correlation constrains all-one or all-zero events relative to independent variables.
  • Negative correlation: Negative correlation transfers exponential-moment upper bounds from an independent comparison sum to the dependent sum.The moment comparison yields every Chernoff bound available for the corresponding independent variables.
  • Hypergeometric distribution: Sampling without replacement produces negatively correlated indicators, so hypergeometric sums satisfy the usual Chernoff bounds for independent binary variables.Symmetry in the sample and population counts can reduce the relevant variable count to min{n, m} for some bounds.

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

This section develops concentration bounds for functions of independent variables when direct bounded differences are unsuitable, and relates them to martingale inequalities. A conditional-influence theorem is illustrated on a neutral-bit process in the compact genetic algorithm.

  • Conditional bounded differences: The conditional-influence method yields concentration bounds for functions of independent variables, including sequential randomized processes.The cGA example represents the process through independent random inputs and bounds each conditional influence by 2/K.
  • Conditional bounded differences: The method of bounded conditional expectations limits each variable’s influence on the expected future outcome rather than on every fixed continuation.This condition is presented as a compromise between classic bounded differences and martingale methods.
  • cGA example: For a neutral cGA bit, the probability of reaching absorbing frequency states within T iterations is bounded by 2 exp(...).The result concerns the frequency converging to 0 or 1 during the first T iterations.
  • cGA example: The classic bounded-differences condition can fail for the cGA modeling construction because changing an early random input may drastically alter later outcomes.The chapter therefore motivates the conditional version for iterative randomized algorithms.
  • Martingales: The Azuma-Hoeffding inequality provides a martingale formulation, and the bounded-differences results are presented as special cases or related extensions.The chapter notes applications of these martingale results in randomized search heuristics.

1.10.4 Chernoff Bounds for Geometric Random Variables

This section gives Chernoff-type bounds for sums of geometric random variables and applies them to runtime analyses of randomized search heuristics. It also highlights when bounds based only on the smallest success probability are overly pessimistic.

  • Basic geometric bounds: Sums of geometric random variables require specialized bounds because geometric variables are unbounded.For a common success probability, the sum is closely related to a shifted negative binomial distribution.
  • Different success probabilities: Theorem 1.10.33 handles independent geometric variables with different success probabilities, but its tail bound depends only on pmin.The smallest success probability corresponds to the largest variance and can dominate concentration.
  • Different success probabilities: When success probabilities vary significantly, bounds using more detailed probability information can be stronger than pmin-based estimates.The chapter points to Witt’s result as an improved alternative in this regime.
  • Runtime applications: Geometric-sum bounds yield runtime tail estimates for several heuristics, including the (1 + 1) EA on OneMax and arbitrary functions.The OneMax bound gives Pr[T ≥ (1 + δ)en ln n] ≤ n^-δ, while the arbitrary-function result gives Pr[T ≥ γn^n] ≤ e^-γ.
  • Runtime applications: A superior representation for sorting can produce substantially lighter runtime tails, changing the bound from inverse-polynomial to negative-exponential.The chapter presents this as an effect visible beyond expected-runtime improvement.
  • Runtime applications: Probabilistic runtime bounds from drift-style analyses can imply domination by a shifted geometric random variable.This extracts distributional information even when the original proof does not explicitly provide a runtime distribution.

1.10.5 Tail Bounds for the Binomial Distribution

This section presents sharper tail estimates for binomial random variables than general independent-binary bounds. It emphasizes elementary derivations, tight point-probability estimates, and cases where improvements have limited demonstrated algorithmic impact.

  • Binomial-specific bounds: Binomial-specific tail bounds can be slightly stronger than bounds for general sums of independent binary variables.The chapter includes estimates for upper tails and binomial probability functions.
  • Elementary estimates: A union-bound derivation expresses the event X ≥ k through all k-subsets whose corresponding variables equal one.This yields a simple binomial-tail estimate based on counting subsets and the probability p^k.
  • Applications: Although Klar’s bound is often significantly stronger than the elementary estimate, the chapter reports no known randomized-search-heuristic analysis improved by it.This limits the demonstrated practical impact of the sharper bound within the stated application area.
  • Elementary estimates: The point-probability estimate is close to tight because Pr[X = k] is at most Pr[X ≥ k].The stated gap is bounded by a multiplicative factor involving k, p, and n.
  • Applications: For p = 1/n, the typical standard-bit mutation rate, one listed binomial estimate can be substantially better in many cases.The improvement follows from comparing the relevant exponential factors.
Loading 1801.06733v6…