Chapter 40: Randomized Algorithms and Approximate Counting

Can nearly uniform samples replace impossible exact enumeration?

A large finite space can contain too many objects to list, yet permit samples that answer a narrower question. Sampling estimates a frequency, average, or ratio; it does not automatically reveal the space's cardinality. The distribution of the samples, the rarity of the event, and dependence between observations determine what can be guaranteed.

Let $\Omega$ be a finite known ambient space, let $E\subseteq\Omega$ be a recognizable event, and let $\pi$ be uniform on $\Omega$. Write $p=\pi(E)$ and $Z=|E|=|\Omega|p$. For independent uniform samples $X_1,\ldots,X_m$, the estimator $\widehat p=m^{-1}\sum_i1_E(X_i)$ is unbiased. Hoeffding's inequality gives

$$ \Pr(|\widehat p-p|\gt a)\le2\exp(-2ma^2),\qquad a\gt0. $$

Consequently $m\ge\log(2/\delta)/(2a^2)$ provides additive error at most $a$ with confidence at least $1-\delta$. An additive probability estimate becomes additive count error $|\Omega|a$, which may be enormous in a large ambient space.

Now suppose each independent sample has law $\mu$ rather than $\pi$. Define total variation distance by

$$ \|\mu-\pi\|_{\mathrm{TV}}=\tfrac12\sum_{x\in\Omega}|\mu(x)-\pi(x)| =\max_{A\subseteq\Omega}|\mu(A)-\pi(A)|. $$

If this distance is at most $\eta$, then $|\mu(E)-p|\le\eta$. Hoeffding controls variation about $\mu(E)$, not directly about $p$. Combining the two bounds gives

$$ \Pr(|\widehat p-p|\gt a+\eta)\le\delta \quad\text{when}\quad m\ge\frac{\log(2/\delta)}{2a^2}. $$

This clean error budget assumes independent observations. Consecutive states of one Markov chain are generally dependent and cannot be inserted into the same proof without additional analysis.

The foundation experiment uses $\Omega=\{0,1\}^3$. Interpret bits as selected vertices on the path $a-b-c$. A selection is an independent set precisely when neither adjacent pair is simultaneously one. The five valid strings are $000,001,010,100,101$, so $p=5/8$ and $Z=5$.

To illustrate approximate sampling, start at $000$ and repeatedly select one of the three coordinates uniformly and refresh it with a fair independent bit. Uniform measure is stationary. Couple this chain with a stationary copy by choosing the same coordinates and new bits. Once every coordinate has been refreshed, their states agree. The chance some coordinate remains unrefreshed after $t$ steps is at most $3(2/3)^t\le3e^{-t/3}$, proving a TV bound rather than merely suggesting convergence from a histogram.

Taking $t=18$ makes this bound below $1/100$. Restart independently for each sample. With $a=1/25$, $\eta=1/100$, $\delta=1/20$, and $m=1153$, the probability error is at most $1/20$ with confidence at least $19/20$. The count estimate $8\widehat p$ is then within $2/5$ of five. All ingredients needed for the final investigation appear here; the numbered sections are optional extensions. Direct independent fair bits would sample this toy cube exactly and more cheaply. The chain is used to expose the proof obligations that arise in harder spaces.

40.1 Randomized generation and randomized search

Optional extension; not required to complete the chapter foundation.

A uniform generator gives every feasible object equal probability. A randomized search algorithm merely needs to locate a feasible object; its distribution may be highly biased. A Las Vegas algorithm has correct outputs with random running time, while a Monte Carlo algorithm has a stated probability of error or failure within its prescribed time budget. Neither label alone supplies an accuracy or runtime bound.

Fisher–Yates generation starts with an ordered array of $n$ distinct objects. For positions $i=n-1$ down to one, choose an integer uniformly from zero through $i$ and swap it with position $i$. Each permutation corresponds to exactly one sequence of choices, with probability $1/n!$. There are $n-1$ swaps, giving $O(n)$ array operations under the stated uniform-integer random primitive. Implementing those integers from fair bits requires its own unbiased generation procedure; simple modulo reduction can introduce bias.

Solved example. The compatibility matrix

$$ A=\begin{pmatrix}1&1&0\\0&1&1\\1&0&1\end{pmatrix} $$

allows exactly the assignments $(1,2,3)$ and $(2,3,1)$. A uniform permutation proposal accepts with probability $2/6=1/3$. Repeating until success has expected three proposals and gives each accepted assignment probability one half. After $r$ independent proposals, the failure probability is $(2/3)^r$. If no feasible assignment exists, unbounded repetition never terminates, so a search algorithm must address that case separately.

Choosing uniformly among compatible unused jobs at each recursive step is different. Worker one chooses job one or two with probability one half. Under job one, worker two chooses two or three equally: the first completes, the second gets stuck. Under job two, completion is forced. The two successful assignments therefore have unconditional probabilities $1/4$ and $1/2$, and conditional probabilities $1/3$ and $2/3$. Random local choices do not guarantee uniform global objects.

Exercise. How many uniform permutation proposals ensure failure probability at most $1/10$ in this example? Hint: solve $(2/3)^r\le1/10$. Solution: six proposals suffice, since $(2/3)^5\gt1/10$ and $(2/3)^6=64/729\lt1/10$. This is a success guarantee for the particular acceptance probability, not for arbitrary compatibility matrices.

40.2 Rejection sampling and importance sampling

Optional extension; not required to complete the chapter foundation.

For a known target distribution $\pi$ and a proposal $q$ with $q(x)\gt0$ wherever $\pi(x)\gt0$, suppose $\pi(x)\le Mq(x)$. Propose $X\sim q$ and accept with probability $\pi(X)/(Mq(X))$. Then the joint probability of proposing and accepting $x$ is $\pi(x)/M$, so acceptance occurs with probability $1/M$ and the accepted law is exactly $\pi$. The expected number of proposals is $M$.

For an unnormalized target $w(x)$, use an envelope $w(x)\le Cq(x)$ and accept with probability $w(x)/(Cq(x))$. The acceptance probability is $Z/C$, where $Z=\sum_xw(x)$, and the accepted law is $w/Z$. This does not require knowing $Z$ beforehand, but a useful envelope can be difficult to find.

In general, $\sum_x h(x)$ can be estimated unbiasedly by $h(X)/q(X)$. Missing proposal support creates an uncorrectable omission, and very small proposal probabilities can create large weights and variance. Ratios of empirical weighted sums used in self-normalized importance sampling are generally biased at finite sample size; their analysis differs from the simple unbiased estimator above.

Exercise. Give a proposal with zero variance for this particular event-count estimator. Hint: it need only cover the support of $h=1_E$. Solution: sample $x_3,x_4$ equally and never sample the others. Then $H=2$ always. This proposal is valid for summing $1_E$, but not for sampling the full uniform target, whose support includes all four objects.

40.3 Markov-chain Monte Carlo

Optional extension; not required to complete the chapter foundation.

A finite Markov chain has transition probabilities $P(x,y)$ summing to one in each row. A stationary distribution satisfies $\pi P=\pi$. Detailed balance, $\pi(x)P(x,y)=\pi(y)P(y,x)$, is a sufficient condition. Irreducibility connects all states through positive-probability paths, and aperiodicity prevents oscillation between forced time classes. Together these ensure convergence to the unique stationary distribution, but give no useful finite running time without a quantitative mixing bound.

Language-independent pseudocode. Initialize a bit vector. At each step select a coordinate uniformly, generate a fair independent bit, and replace that coordinate. Return the state after a specified number of steps. To obtain independent endpoint observations, restart from the same fixed state using fresh independent randomness for each run. Retaining every step of one run instead creates a correlated sample sequence.

For this cube chain, a specified neighboring state is reached with probability $1/(2n)$ and the current state is retained with probability $1/2$. Its transition matrix is symmetric, so the uniform distribution is stationary. Any bit vector can be reached by prescribed refreshes, and the self-loop gives aperiodicity.

from fractions import Fraction
from math import ceil, log
from random import Random


def refresh_sample(n, steps, rng, start=0):
    if type(n) is not int or n < 1:
        raise ValueError("n must be a positive integer")
    if type(steps) is not int or steps < 0:
        raise ValueError("steps must be a nonnegative integer")
    if type(start) is not int or not 0 <= start < (1 << n):
        raise ValueError("start must encode an n-bit state")
    state = start
    for _ in range(steps):
        coordinate = rng.randrange(n)
        bit = 1 << coordinate
        state = (state & ~bit) | (rng.getrandbits(1) << coordinate)
    return state


def exact_distribution(n, steps, start=0):
    if type(n) is not int or n < 1:
        raise ValueError("n must be a positive integer")
    if type(steps) is not int or steps < 0:
        raise ValueError("steps must be a nonnegative integer")
    if type(start) is not int or not 0 <= start < (1 << n):
        raise ValueError("start must encode an n-bit state")
    law = [Fraction(0) for _ in range(1 << n)]
    law[start] = Fraction(1)
    for _ in range(steps):
        next_law = [Fraction(0) for _ in law]
        for state, probability in enumerate(law):
            for coordinate in range(n):
                for value in (0, 1):
                    destination = ((state & ~(1 << coordinate))
                                   | (value << coordinate))
                    next_law[destination] += probability / (2 * n)
        law = next_law
    return law


def independent_on_three_vertex_path(state):
    a, b, c = ((state >> i) & 1 for i in range(3))
    return not (a and b) and not (b and c)


if __name__ == "__main__":
    assert exact_distribution(2, 1) == [Fraction(1, 2),
                                        Fraction(1, 4),
                                        Fraction(1, 4), Fraction(0)]
    assert exact_distribution(2, 2) == [Fraction(3, 8),
                                        Fraction(1, 4),
                                        Fraction(1, 4), Fraction(1, 8)]
    valid = [s for s in range(8) if independent_on_three_vertex_path(s)]
    assert len(valid) == 5
    eta, sampling_error, failure = 0.01, 0.04, 0.05
    steps = ceil(3 * log(3 / eta))
    trials = ceil(log(2 / failure) / (2 * sampling_error ** 2))
    rng = Random(400040)
    counts = [0] * 8
    for _ in range(trials):
        counts[refresh_sample(3, steps, rng)] += 1
    successes = sum(counts[s] for s in valid)
    probability_estimate = successes / trials
    print("steps per restart:", steps, "independent restarts:", trials)
    print("state frequencies:", counts)
    print("successes:", successes)
    print("probability estimate:", probability_estimate)
    print("count estimate:", 8 * probability_estimate)

Solved exact check. For two coordinates, starting from zero, the one-step law is $(1/2,1/4,1/4,0)$ and the two-step law is $(3/8,1/4,1/4,1/8)$ in integer-mask order. Their TV distances from uniform are $1/4$ and $1/8$. These are exact rational computations rather than empirical frequencies.

A refresh run uses $t$ updates and one $n$-bit state. Under a word model with a fitting mask, each update has constant bit-operation cost plus the random-coordinate primitive; arbitrary-size Python integers incur costs depending on mask length. Exact distribution enumeration instead uses $O(tn2^n)$ rational operations and $O(2^n)$ rational cells, and is included only for small-case validation. Seeded pseudorandom output is reproducible experimental evidence; the probability proof models independent ideal random choices.

Exercise. Why would always flipping a chosen bit, rather than refreshing it, fail aperiodicity on the cube? Hint: every flip changes parity. Solution: the chain alternates between even and odd Hamming weight, giving period two. Refreshing has self-loop probability one half, eliminating that forced alternation.

40.4 Mixing times and coupling

Optional extension; not required to complete the chapter foundation.

For a chain with stationary law $\pi$, define its worst-start mixing time by

$$ t_{\mathrm{mix}}(\eta)=\min\{t:\max_x\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}}\le\eta\}. $$

A coupling jointly constructs two random variables with prescribed marginal laws. The coupling inequality says their TV distance is at most their probability of disagreement: for any event, the two indicators differ only when the variables differ. A Markovian coupling can give a convergence bound if coupled states remain equal after meeting.

Couple two cube refresh chains with identical chosen coordinates and refresh bits, one started arbitrarily and one at stationarity. Previously refreshed coordinates agree forever. Coordinate $i$ is untouched after $t$ steps with probability $(1-1/n)^t$. A union bound gives, for $n\ge2$,

$$ \max_x\|P^t(x,\cdot)-\pi\|_{\mathrm{TV}} \le n(1-1/n)^t\le ne^{-t/n}. $$

Thus $t\ge n\log(n/\eta)$ suffices. For $n=1$, one refresh is already exactly uniform. The coupon-collection bound need not equal the exact TV distance; it is a sufficient guarantee.

Solved example. For $n=2$ and positive $t$, the law from $00$ is

$$ \left(\tfrac14+2^{-t-1},\ \tfrac14,\ \tfrac14,\ \tfrac14-2^{-t-1}\right). $$

Substitution into the transition recurrence proves the formula by induction from $t=1$. Its TV distance is $2^{-t-1}$. The coupling union bound is $2(1/2)^t$, four times this exact value. At $t=0$ the TV distance is $3/4$, so the positive-time formula must not be used there.

The Markov transition kernel contracts TV distance, so a valid worst-start bound remains valid at later times. This does not make consecutive retained states independent. Coupling controls a marginal distribution, while a concentration theorem for a trajectory must additionally address joint dependence.

Exercise. Give a sufficient refresh count for $n=3$ and $\eta=1/100$. Hint: use the exponential bound. Solution: $\lceil3\log300\rceil=18$ steps suffice. Indeed $3e^{-6}\lt1/100$. The sharper union bound $3(2/3)^{18}$ is smaller still; either proves the requested tolerance.

40.5 Glauber dynamics

Optional extension; not required to complete the chapter foundation.

Glauber dynamics updates one coordinate conditional on the others. For graph independent sets with fugacity $\lambda\gt0$, the target is

$$ \pi_\lambda(S)=\frac{\lambda^{|S|}}{Z_G(\lambda)},\qquad Z_G(\lambda)=\sum_{S\text{ independent}}\lambda^{|S|}. $$

Choose a vertex uniformly. If one of its neighbors is occupied, set it unoccupied. Otherwise make it occupied with probability $\lambda/(1+\lambda)$ and unoccupied with probability $1/(1+\lambda)$. This conditional update preserves independent-set feasibility. At $\lambda=1$, the stationary distribution is uniform over independent sets, not over all subsets.

For two states differing by inserting one permitted vertex, their stationary-weight ratio is $\lambda$, while the forward/backward transition ratio is also $\lambda$. This verifies detailed balance. Removing occupied vertices leads to the empty set, and valid vertices can then be added in any order, proving irreducibility. Positive probabilities of retaining a state give aperiodicity. None of these facts alone proves rapid mixing on arbitrary graphs or fugacities.

Solved example. On $a-b-c$, the five independent sets have weights $1,\lambda,\lambda,\lambda,\lambda^2$, so $Z_G(\lambda)=1+3\lambda+\lambda^2$. At $\lambda=1$, all five probabilities are $1/5$. In state order $\varnothing,\{a\},\{b\},\{c\},\{a,c\}$, the transition matrix is

$$ P=\begin{pmatrix} 1/2&1/6&1/6&1/6&0\\ 1/6&2/3&0&0&1/6\\ 1/6&0&5/6&0&0\\ 1/6&0&0&2/3&1/6\\ 0&1/6&0&1/6&2/3 \end{pmatrix}. $$

Its rows sum to one and it is symmetric, confirming the uniform stationary law. The singleton center has a larger self-loop than the empty set because its two neighbors cannot be inserted.

A crude quantitative bound is possible on this fixed example. In three updates, select $a,b,c$ in that order and choose removal whenever a fair choice is needed. This has probability at least $(1/6)^3=1/216$ from every state and ends at the empty set. Thus every three-step transition law has a common mass $1/216$ there. Coupling those common masses gives TV at most $(1-1/216)^{\lfloor t/3\rfloor}$. The bound proves convergence quantitatively here; extending the same prescribed-update argument to $n$ vertices would have exponentially small common mass and would not prove a polynomial mixing bound.

Exercise. At $\lambda=2$, compute the probability of the two-endpoint independent set. Hint: its weight is four. Solution: $Z=1+6+4=11$, so its probability is $4/11$. The empty set has probability $1/11$, and each singleton $2/11$. Uniformity applies only at fugacity one in this model.

40.6 Rapid mixing and approximate sampling

Optional extension; not required to complete the chapter foundation.

A family of chains is rapidly mixing when its mixing time is bounded polynomially in the encoded instance size and $\log(1/\eta)$, under a specified model that also permits efficient transitions. A finite chain eventually mixing is a much weaker statement. The cube refresh family has $t=O(n\log(n/\eta))$, with an efficient coordinate update, so it provides a concrete rapidly mixing family.

Solved approximation guarantee. Use $n=3$, eighteen updates, and independent restarts. The endpoint law $\mu$ has TV at most $\eta=1/100$ from uniform. For the independent-set event, $|\mu(E)-5/8|\le1/100$. For $m=1153$ independent endpoints and $a=1/25$,

$$ 2e^{-2ma^2}\le1/20, $$

so $\Pr(|\widehat p-5/8|\le1/20)\ge19/20$. The algorithm performs $18\cdot1153=20754$ updates. Increasing sample size reduces the $a$ term but does not remove a fixed mixing bias $\eta$.

For a bounded statistic $f\in[0,1]$, the same TV bound controls expectation bias by $\eta$. One proof writes $f(x)=\int_0^1 1_{\{f(x)\gt s\}}\,ds$ and applies the event bound inside the integral. Hoeffding then applies to independent bounded observations as well.

If samples come from one long chain, neither arbitrary thinning nor apparent low autocorrelation automatically certifies independence. A valid alternative is a theorem for dependent Markov observations with its hypotheses checked. Another sufficient route is independent restarts, as used here. A more conservative joint-coupling route runs each restarted sample to error at most $\delta/(2m)$, couples all $m$ endpoints to ideal samples, and spends $\delta/2$ on the probability any coupling fails; this is a different error allocation.

Exercise. With fixed bias tolerance $\eta=0.01$, can more samples alone prove total additive error $0.005$ using this analysis? Hint: the bias term remains. Solution: no. Even zero sampling variation would leave a possible bias of $0.01$. The chain must be run longer to obtain a smaller proved TV tolerance, or another bias-control argument must be supplied.

40.7 Fully polynomial randomized approximation schemes (FPRAS)

Optional extension; not required to complete the chapter foundation.

An FPRAS for a nonnegative count $Z(I)$ takes instance $I$, relative tolerance $0\lt\varepsilon\lt1$, and failure probability $0\lt\delta\lt1$, and outputs $\widehat Z$ satisfying

$$ \Pr\bigl((1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z\bigr)\ge1-\delta $$

in time polynomial in input length, $1/\varepsilon$, and $\log(1/\delta)$. A constant-confidence definition can be amplified by independent runs and a median. When $Z=0$, the successful outcome must be zero; zero-count handling is part of the algorithm, not a relative-error calculation dividing by zero.

For independent uniform ambient samples with success probability $p\gt0$, multiplicative Chernoff gives

$$ \Pr(|\widehat p-p|\gt\varepsilon p)\le2e^{-m\varepsilon^2p/3}. $$

Thus $m\ge3\log(2/\delta)/(\varepsilon^2p)$ suffices. To turn this into an implementable a priori bound, use a known lower bound on $p$. If that lower bound is inverse-polynomial and event membership is efficient, this yields a polynomial method. If $p$ is exponentially small, the sample requirement may be exponential even though generating each ambient sample is easy. TV bias must likewise be small compared with $\varepsilon p$ to support relative accuracy.

Solved example. For the five valid subsets of the three-vertex path, $p=5/8$. With $\varepsilon=1/10$ and $\delta=1/20$, the Chernoff sufficient count is $m\ge480\log40$, so 1771 independent exact uniform samples suffice. This is relative error at most ten percent, unlike a generic additive tolerance. A known lower bound $p\ge1/2$ would give the conservative implementable requirement $m\ge600\log40$, or 2214 samples.

A major established FPRAS exists for the permanent of a matrix with nonnegative rational entries: Jerrum, Sinclair, and Vigoda (2004). The input encoding includes the entry bit lengths. Its analysis uses carefully designed sampling and counting stages; naive rejection of random permutations is not its proof. The Markov-chain construction and polynomial mixing analysis are omitted prerequisites here, and no best runtime exponent is claimed.

Exercise. If exactly one of $n!$ permutations is valid, what acceptance probability does uniform-permutation rejection have? Hint: each permutation has probability $1/n!$. Solution: the probability is $1/n!$ and the expected proposal count is $n!$. This does not invalidate the permanent FPRAS; it shows why a different algorithmic construction is required.

40.8 Approximate counting and #P-completeness

Optional extension; not required to complete the chapter foundation.

The class $\#P$ consists of functions counting accepting computations of polynomial-time nondeterministic machines; equivalently, one can count polynomial-length witnesses satisfying an efficiently checkable relation with an appropriate encoding. Exact counting difficulty concerns producing the full integer answer. Approximate counting asks for a different output contract and need not have the same complexity.

For a zero–one matrix, the permanent counts compatible worker–job bijections. A proposed bijection is efficiently checked, placing the count in $\#P$. Computing this permanent exactly is $\#P$-complete, a classical theorem of Valiant (1979). Its exact reduction proof is omitted. Yet the nonnegative permanent has the established FPRAS above. Exact hardness therefore does not by itself prohibit a randomized relative approximation for the same count.

Solved example. The $3\times3$ compatibility matrix from Section 40.1 has permanent two. Checking six permutations, the subset DP, and inclusion–exclusion all give this exact value. A relative approximation with $\varepsilon=1/4$ permits a successful estimate anywhere in $[3/2,5/2]$. An additive estimate with error ten would provide no meaningful information here. The numerical output contract must accompany the word “approximation.”

Zero detection can differ from positive-count estimation. For a zero–one permanent, a bipartite matching algorithm determines whether the count is zero in polynomial time. This special feasibility fact supports zero handling; it cannot be assumed for every $\#P$ witness relation. Nor does membership in $\#P$ automatically supply an FPRAS.

Exercise. Why is outputting the integer one for every positive permanent not a relative approximation scheme? Hint: consider an all-ones matrix. Solution: its permanent is $n!$, so the ratio of the estimate to the truth is $1/n!$. It lies outside any fixed small relative-error interval for sufficiently large $n$. Recognizing positivity is not approximating magnitude.

40.9 Sampling–counting equivalence and reductions

Optional extension; not required to complete the chapter foundation.

Self-reducibility expresses solutions through smaller residual instances after fixing choices. If exact counts $Z_0,Z_1$ of the two branches are known, choosing branch $i$ with probability $Z_i/(Z_0+Z_1)$ and repeating generates a uniform solution. Products of these conditional probabilities telescope, giving each complete solution probability $1/Z$. Uniform selection among branches would instead ignore their differing numbers of completions.

The converse uses ratios of nested solution families $\Omega_0\supseteq\cdots\supseteq\Omega_r$, ending with a singleton. Let $p_i=|\Omega_i|/|\Omega_{i-1}|$. Then

$$ Z=|\Omega_0|=\frac1{\prod_{i=1}^r p_i}. $$

Samples uniform in the current family estimate the next ratio. To obtain polynomial cost, the depth must be polynomial and selected ratios must stay inverse-polynomial rather than becoming arbitrarily rare. In a bounded-branching reduction, choosing a heavy branch supplies such a lower bound; estimating which branch is heavy requires its own accuracy and failure budget.

Solved example. Among the five independent sets of $a-b-c$, first require $a$ absent, leaving three; then $b$ absent, leaving two; then $c$ absent, leaving one. The ratios are $3/5,2/3,1/2$, whose product is $1/5$. Their reciprocal recovers the count five without estimating the tiny probability of a long arbitrary witness in an ambient cube.

For explicit error propagation, suppose $0\lt\varepsilon\le1/2$ and every estimate satisfies $|\widehat p_i/p_i-1|\le\gamma=\varepsilon/(4r)$. Then $|\log(\widehat Z/Z)|\le2r\gamma=\varepsilon/2$, yielding $(1-\varepsilon)Z\le\widehat Z\le(1+\varepsilon)Z$. Allocate failure at most $\delta/r$ per stage and use a union bound. An approximate sampler's TV error must be small relative to $\gamma p_i$, not just a fixed constant, so ratio estimation retains its relative accuracy.

Under appropriate efficiently checkable self-reducibility hypotheses, almost-uniform generation and randomized approximate counting are interreducible. The full primary framework is Jerrum, Valiant, and Vazirani (1986). The general reduction machinery is omitted; the displayed telescoping example and product-error bound are explicit. This equivalence is not a claim for arbitrary unrelated sample spaces or encodings.

Exercise. What goes wrong if a chosen ratio is $2^{-n}$? Hint: count successes required by a relative estimator. Solution: a direct Bernoulli estimate can need exponentially many samples to see enough successes. An efficient sampler for the parent family does not by itself make that rare conditional event easy to estimate. Heavy-branch selection or another reduction is necessary.

40.10 Randomized rounding and discrepancy minimization

Optional extension; not required to complete the chapter foundation.

Sections 52.1 and 52.9 are optional later background for the fuller discrepancy treatment, not entry requirements. This bridge introduces the quantities and an elementary bound; for a primary constructive development see Bansal, Constructive Algorithms for Discrepancy Minimization.

For a fractional vector $x\in[0,1]^n$, independent randomized rounding sets $X_i=1$ with probability $x_i$. It preserves each marginal expectation and any linear objective in expectation. It does not automatically preserve hard constraints in every outcome. Discrepancy asks for a simultaneous bound on signed row sums: for a set system $S_1,\ldots,S_M$ on $[n]$ and signs $\chi_i\in\{-1,1\}$, define

$$ \operatorname{disc}(\chi)=\max_j\left|\sum_{i\in S_j}\chi_i\right|. $$

With independent fair signs, a row of size at most $s\ge1$ has tail at most $2\exp(-u^2/(2s))$. A union bound therefore gives discrepancy at most $\sqrt{2s\log(2M/\delta)}$ with probability at least $1-\delta$. This is an elementary independent-sign guarantee, not a sharp general discrepancy theorem.

Solved example. Round $x=(1/2,1/2,1/2)$ independently on the three-vertex path. The fractional edge constraints $x_a+x_b\le1$ and $x_b+x_c\le1$ hold, but only five of the eight rounded strings are independent sets. Thus exact feasibility occurs with probability $5/8$, even though all marginals are correct.

For sets $S_1=\{a,b\}$ and $S_2=\{b,c\}$, write $\chi_i=2X_i-1$. Both row sums are zero exactly for strings $010$ and $101$, giving discrepancy zero with probability $1/4$; the other six strings have discrepancy two. A dependent rule choosing $010$ or $101$ equally retains every marginal at one half, satisfies both edge constraints, and achieves discrepancy zero always. This particular dependence is useful for these two rows; it does not establish a general dependent-rounding theorem for arbitrary constraint families.

Expectation preservation, feasibility, and small discrepancy are three different guarantees. Conditioning on feasibility can change marginals, just as rejection changes a proposal distribution. Advanced discrepancy algorithms coordinate rounding decisions to control many rows; their general geometric and algorithmic proofs are outside this section, and no unverified optimal bound is asserted.

Exercise. Under uniform sampling conditioned on being an independent set of this path, compute the occupancy probabilities of $a,b,c$. Hint: count their appearances among the five valid strings. Solution: the endpoint probabilities are $2/5$ each and the center probability is $1/5$. Conditioning the independent half-rounding changed its marginals. The balanced dependent rule above instead preserves them by selecting a different distribution on feasible sets.

Analyze a sampling experiment and state an approximation guarantee

The investigation separates exact enumeration, a mixing proof, a concentration proof, and a reproducible randomized trace. It connects randomized generation with rounding by interpreting the same bits as selected vertices and as signed balancing decisions. Use the code for exploration, while retaining explicit assumptions about ideal randomness in the theorem.

Worked solution: exact objects and coupling. The independent-set event has probability $5/8$ under cube measure. The balanced strings $010,101$ have probability $1/4$ there, and $2/5$ under uniform measure on the five independent sets. Under the latter measure, endpoint occupancies are $2/5$ and center occupancy $1/5$.

The refresh matrix is symmetric, so uniform measure is stationary. Prescribed coordinate updates reach any state, and self-loop probability one half ensures aperiodicity. Coupling with a stationary copy using the same refreshes makes agreement permanent coordinate by coordinate. A coordinate is untouched with probability $(2/3)^t$, so TV is at most $3(2/3)^t\le3e^{-t/3}$. At $t=18$, the exponential bound is below $0.01$. These structural and quantitative claims concern the actual transition rule, not its observed frequency plot.

Worked solution: approximation guarantee. Let $p_\mu=\mu(E)$. TV implies $|p_\mu-5/8|\le0.01$. The restarted endpoints are independent under the ideal random-choice model, so Hoeffding gives

$$ \Pr(|\widehat p-p_\mu|\gt0.04)\le2e^{-2(1153)(0.04)^2}\le0.05. $$

Therefore $|\widehat p-5/8|\le0.05$ with probability at least $0.95$. Multiplying by eight gives $|8\widehat p-5|\le0.4$ on that event. Rounding this tiny instance's count estimate to the nearest integer recovers five with the same confidence because $0.4\lt1/2$. This does not yield efficient exact counting in general: to round a count from an ambient space of size $2^n$, additive probability accuracy below $2^{-n-1}$ would be required.

The raw estimate also has relative count error at most $0.4/5=0.08$ on the same event, using this known toy count. The demonstrated theorem is an explicit instance guarantee, not an FPRAS for arbitrary independent-set inputs. Sampling variation and mixing bias remain separate even when their sum is later expressed as relative error.

Worked solution: experiment and exact validation. The reference run with seed 400040 reports frequencies [165, 136, 144, 135, 132, 140, 150, 151] in integer-mask order. There are 717 event successes, giving $\widehat p=717/1153\approx0.621856$ and $8\widehat p=5736/1153\approx4.974848$. These observed errors lie inside the proved interval, but that one run does not establish the confidence theorem. To reproduce a coordinate-order string, read bit zero as $a$, bit one as $b$, and bit two as $c$. Compute $\mu=P^{18}(000,\cdot)$ with exact rational arithmetic, then verify $\tfrac12\sum_s|\mu(s)-1/8|\le0.01$. The exact computation gives $\|\mu-\pi\|_{\mathrm{TV}}=65536/129140163$, smaller than the chosen tolerance. This is a finite calculation checking the toy endpoint law; the coupling argument proves the general refresh bound without enumerating $2^n$ states.

The seeded trace contains 20754 coordinate updates. Its observed estimate need not equal five exactly, and a different seed can produce a different estimate. The theorem permits failure on up to a specified probability budget under its random model; it does not guarantee that every seed lies within the error interval.

Application and extension. Random selections can model feasible resource subsets when adjacent tasks compete, while signed choices can model balancing two teams across overlapping workloads. The path example shows why preserving expected usage does not ensure conflict-free selections or balanced workloads. The dependent two-state rule proves both properties for this small constraint system; larger systems require a separate construction and analysis.

For a rare event consisting of one specified $n$-bit string, the uniform probability is $2^{-n}$. The sufficient multiplicative-Chernoff sample bound scales as $O(2^n\varepsilon^{-2}\log(1/\delta))$ for the direct indicator estimator, and the probability of seeing no success in $m$ samples is $(1-2^{-n})^m$. Rapid mixing of the ambient cube does not remove rarity. Sampling–counting reductions instead seek well-conditioned intermediate ratios; importance sampling seeks a useful proposal, and discrepancy methods seek correlated decisions. Each tool solves a different obstruction and must carry its own explicit guarantee.