A sampling Lov\'{a}sz Local Lemma

1 Introduction

• Sampling was open in the counting regime because conditional variable fixing can increase violation probabilities and destroy the conditions needed for counting.The paper's deletion-only reduction invokes the counter on instances formed by deleting constraints, which inherit the original guarantee.Source: §1 · p. 1

1.1 Results

• Under 4ep(∆+1)^2 ≤1, the sampler returns a satisfying assignment within total-variation distance ε of uniform in (n + m/ε)^O(k∆log D) steps.The condition uses the maximum constraint-violation probability p under independent uniform variable values and maximum dependency-graph degree ∆.Source: §1.1 · pp. 1–2
• With access to relative-approximation counts for every constraint subset, sampling also works under 8pQ ≤1 using (m/ε)^O(log ∆2) counter calls.Each counter call uses relative accuracy ε/(32m); Q measures the actual first- and second-neighborhood sizes.Source: §1.1 · p. 2

1.2 An asymmetric extension

• The asymmetric counting regime extends Liu et al.’s marginal-expansion proof to supply deletion counts for the sampler.The extension builds on marginal expansion and size-budget truncation, adding estimates for the recursion under the product condition.Source: §1.2 · p. 2
• The asymmetric extension supplies deterministic relative-δ approximations to Z(H) and randomized ε-uniform sampling under its product-form condition.The counting and sampling times are respectively (n + m/δ)^O(k∆log D) and (n + m/ε)^O(k∆log D).Source: §1.2 · pp. 2–3
• Replacing (∆+1)^2 by Q+1 can sharpen the symmetric condition when local neighborhoods are smaller, while Q is of order ∆² in the worst case.The stated asymmetric bound is 4ep(Q+1) ≤1.Source: §1.2 · p. 3

2.1 Constraint-wise methods for sampling and the Counting LLL

• Wang and Yin [4] used constraint-wise coupling for atomic CSP counting and sampling, under a domain-dependent condition whose exponent is about 4.82 for Boolean domains and tends to 2 as D grows.Their approach compares formulas differing by one constraint.Source: §2.1 · p. 3
• Liu, Wang, Yin, Zhang, and Zhou [2] established 4ep(∆+1)^2 ≤1 for arbitrary predicates using 2-tree expansion, but left sampling in that regime open.Their deterministic counter runs in (n∆/δ)^O(k∆log D) time at relative accuracy δ.Source: §2.1 · p. 3

2.2 Marginals, marking, and general predicates

• Moitra [7] estimates variable marginals by coupling conditioned distributions; marking preserves randomness during revelation and supports truncated disagreement regions represented by a linear program.Marking also addresses ordinary self-reduction failing after arbitrary pinnings.Source: §2.2 · pp. 3–4
• Later approaches extend projected sampling and state compression to non-Boolean domains or bounded forbidden assignments, while Jain, Pham, and Vuong [20] give arbitrary-predicate counting and sampling under kD^3p∆^7 < c0.He, Wang, and Yin [22] give an expected near-linear-time marginal sampler under kD^2p∆^5 ≤c1, using an oracle for locally forced satisfaction.Source: §2.2 · p. 4

3 How our algorithm works

• The exact sampler inserts constraints one by one, walking from a uniform solution of the current instance to a uniform solution of the enlarged instance.It starts from a uniform assignment and redistributes the mass of solutions eliminated by the inserted constraint among the survivors.Source: §3 · pp. 4–5

3.1 Grouping the transitions

• Families group weighted mutations by skeleton; their weights use deletion counts, and the walk chooses a family by its total permitted weight before choosing a mutation.A stopping option of weight Z(F_i) competes with family choices at solutions of the enlarged instance.Source: §3.1 · p. 5

3.2 Growing the skeleton and specifying its mutations

• Each skeleton is independent in G and connected in G2; its mutable region includes the skeleton and neighboring constraints, while boundary constraints insulate the remainder.The inserted constraint is the root, and skeleton-size parity determines the permitted direction of its satisfaction change; combined flow balance, rather than each mutation, ensures the correct output distribution.Source: §3.2 · pp. 5–6

3.3 Making the process efficient

• Under 8pQ ≤1, normalized family weight decays exponentially with skeleton size, overcoming the growth in skeleton count and making large families unlikely to be selected.The algorithm retains only skeletons of logarithmic size in m/ε; the tail and step bounds, together with accurate relative deletion-count approximations, control the implementation error.Source: §3.3 · p. 6

• A walk with initial mass a, stopping mass τ, and arc weights W stops almost surely with output law τ/M*, while expected visits to each state are at most d(x)/M*.The proof sums stepwise visit probabilities, then shows the upper bounds on stopped mass are attained because total initial and stopping mass agree.Source: §4 · p. 7
• For an insertion F → J, choosing a(x) = Z(J)1{x satisfies F} and M* = Z(F)Z(J) makes the lemma's initial and terminal laws µF and µJ.The required net outflow is at assignments satisfying F but violating the inserted constraint; net inflow is required at solutions of J.Source: §4 · pp. 7–8
• The flow is split into mutation families, and the visit bound limits their expected selections by normalized family weight, including repeated uses.A warm start from the uniform solution of the preceding instance makes aggregate bounds over the walk useful without a separate bound at every intermediate state.Source: §4 · p. 8

5.2 The weights and directions of the mini-flows

• Each permitted local mutation receives weight equal to the number of satisfying outside completions, while skeleton parity directs the arc according to whether it repairs or violates the inserted constraint.The grouped inclusion–exclusion identity turns alternating signs into directions, so arc weights stay nonnegative and the combined mini-flows satisfy the required balance.Source: §5 · p. 8, §5.2 · pp. 10–11

5.1 Choosing the variables of a mutation

• The branching construction generates a skeleton A and mutable region B; A determines B, its constraint scopes are disjoint, and A ∪ B is connected in G.The resulting pairs partition the inclusion–exclusion subsets by their expansion branches.Source: §5.1 · p. 9, §5.2 · p. 11

5 Constructing the insertion flow

• The resulting exact insertion flow transforms µF into µJ for every satisfiable J; composing insertions from µ∅ gives µH, without requiring a local-lemma hypothesis for correctness.Efficiency remains a separate issue because the ideal sampler may have exponentially many possible mutations.Source: §5.2 · p. 12

6 An exponential tail for the insertion process

• At most m(1 + 4p) steps are needed in expectation, and the probability of ever choosing |A| > ℓ is at most 4mp(23/25)^ℓ.The bound sums expected selections across insertions; independence between insertions is not needed.Source: §6 · p. 12

6.1 The single-pair bound

• For a skeleton of size r, the local root-orientation and two-endpoint tests give a small factor p(2p)^(r−1), while a conditional local-lemma bound controls the count ratio after deleting nearby constraints.The proof uses the conditional local lemma to show restoring each deleted constraint preserves at least a 1 − t fraction of solutions.Source: §6.1 · pp. 13–14

6.2 Summing over skeletons

• The number of size-r skeletons is bounded by counting connected sets in the distance-two graph; summable coefficients then combine with exponential weight decay to give the tail.The coefficients are controlled using generating functions for rooted labeled trees, yielding the stated geometric tail without an extra geometric-series factor.Source: §6.2 · pp. 14–15

7 Approximate sampling

• Each trial starts from a uniform product assignment, attempts all m constraint insertions, and either returns a solution or reports failure.Only small skeletons are retained, counts are approximated, and the total walk steps are capped.Source: §7 · p. 15

7.1 The truncated insertion process

• A trial retains skeletons of size at most L, uses precomputed relative-accuracy-η deletion counts, and chooses each mutation family by its total permitted arc weight.It then samples a uniform allowed destination; the family weight includes the number of permitted destinations.Source: §7.1 · p. 16

7.2 Error along the exact walk

• The trial couples to the ideal sampler until a first discrepancy, bounding omitted selections along the complete ideal execution rather than assuming each insertion starts uniformly.This accounts for count error over the ideal expected number of steps, not the larger worst-case step cap.Source: §7.2 · pp. 17–18
• The error bound ε(1/4 + p) combines omitted mutations, approximate weights, the step cap, and failed random draws.The step cap costs at most Pr[N > T] ≤ EN/T, and the omitted-family and total-step expectations are bounded in (27).Source: §7.2 · pp. 17–19

7.3 Returning a satisfying assignment

• If all bounded trials fail, the algorithm returns a fixed satisfying assignment, and the resulting output law remains within ε of uniform.The fallback is constructed by a deterministic LLL algorithm; the probability of using it is at most ε/4.Source: §7.3 · pp. 19–20

7.4 Running time

• The algorithm returns a satisfying assignment within total-variation distance ε of uniform, with running time (n + m/ε)^O(kΔ log D).The running-time bound uses L = O(log(m/ε)) and Δ₂ ≤ Δ(Δ−1).Source: §7.3 · p. 20, §7.4 · p. 21

8 Asymmetric sampling

• The asymmetric tail bounds the mass of skeletons larger than ℓ by C x_c z^-ℓ, yielding at most (1 + C)m expected steps and Cmz^-L expected omitted-family selections.The cutoff is L = ⌈log_z(16m/ε)⌉.Source: §8 · p. 22
• The implementation retains the Section 7 sampler and changes the cutoff to L = ⌈log_z(16m/ε)⌉; conditioning, repetition, and enumeration give the claimed bounds.For C = 23/96, the original cutoff is unchanged.Source: §8 · p. 22
• A deterministic fallback assignment is obtained using Harris’s asymmetric bound, with running time (n + m)^O(k log D)D^O(k) and no counting calls.The argument uses the same runtime formula and local-table calculation as the cited deterministic LLL result [6].Source: §8 · p. 22

9 Counting for the asymmetric sampler

• The counting proof extends Liu et al.’s marginal expansion and size-budget truncation to supply deletion counts in the additional asymmetric regime.The weighted estimates control the same recursion under the product condition.Source: §9 · p. 22

9.1 The marginal recursion

• The marginal recursion expands each constraint’s violation probability into signed local-family terms, whose coefficients require local assignment enumeration rather than counting calls.The expansion is averaged over the product distribution, and its recursive ratios involve proper subformulas.Source: §9.1 · p. 23

9.2 A weighted stability bound

• A weighted stability bound controls omitted terms and contracts child errors when measured relative to each root’s witness.The argument uses inflated factors to bound child derivatives.Source: §9.2 · p. 24

9.3 The bounded recursion and its accuracy

• The bounded recursion clips estimates to [0, t_c], rounds them on a budget-dependent grid, and controls rounding, omitted terms, and retained-child errors.The resulting product estimate achieves the stated relative error for 0 < δ ≤ 1/2.Source: §9.3 · pp. 24–25

9.4 Running time and the symmetric corollary

• The counter’s work and error bounds do not depend on 1/4 − C, so they hold for every C < 1/4, even arbitrarily close to the boundary.Using this counter at accuracy ε/(32m) supplies the deletion counts for sampling under the product condition.Source: §9.4 · pp. 25–26
• The symmetric corollary recovers the sufficient condition 4ep(Q + 1) ≤ 1, with Q + 1 ≤ (Δ + 1)^2.When Q ∼ Δ², the leading constant remains 4e.Source: §9.4 · p. 26

A Supporting estimates

• The supporting estimates address numerical tail bounds, retained-mutation generation, and construction of the fallback assignment.Source: A Supporting estimates · p. 28

• Setting a0=3/20 and t=a0/Q, Bernoulli’s inequality gives κ ≤ (20/17)^2.Source: §A.1 · p. 28
• The verification uses ∆^2 ≤ Q−1 and logarithm bounds for 0<u<1.Source: §A.1 · p. 28
• The estimates yield θ ≤ e^(13/10)/4 < 23/25, after an intermediate bound of 9/170 < 1.Source: §A.1 · p. 28
• A final sign check establishes that the last bracket is negative.Source: §A.1 · p. 28

• Candidate pairs come from rooted ordered trees of size r≤L mapped into the graph joining constraints at distance exactly two, with the root fixed at the inserted constraint.There are at most 4^(r−1)∆^(r−1) such maps.Source: §A.2 · p. 28
• The procedure keeps distinct injective images inside the prefix that are independent in G, then replays the vulnerability rule by expanding exactly at members of each image.A pair is retained only if its expansion set is precisely that image.Source: §A.2 · p. 28
• Lemma 2 guarantees that this enumeration generates all retained pairs in poly(n,m,L)P time.Source: §A.2 · p. 28

• Under 8pQ ≤ 1, if 0 < aH < 1/2 and e(∆ + 1) max_c p_c^(1−aH) ≤ 1, Harris’s algorithm finds a satisfying assignment in (n + m)^(O(1/aH)) D Tloc time.Source: §A.3 · p. 28
• Choosing aH=1/(4k⌈log2 D⌉) uses the bound pc≥D^(−k) for each constraint.Source: §A.3 · p. 28
• The finder costs (n+m)^(O(k log D))D^(O(k)) and makes no counting calls.Local conditional probabilities are computed with at most D^k predicate evaluations each, plus polynomial input-preparation work.Source: §A.3 · p. 28