Exactness, Criticality, and Memory in Mean-Field Sampling
Abstract
How much information must a sequential generator retain after it has emitted part of a sample? We answer this question for rank-one quadratic Gibbs distributions in a write-only, finite-state interface with a free clock and read-only transition kernels. For every nonzero coupling and arbitrary finite external fields, the minimum state count at a cut is the smaller number of attainable weighted sums on its two sides. A single stochastic generator simultaneously attains these cutwise lower bounds by switching from a prefix sum to a sampled suffix sum. In the homogeneous Curie–Weiss model, exact generation consequently needs states at every nonzero coupling. Allowing fixed total-variation error produces a different classification: the optimal width is at criticality and at each fixed positive noncritical coupling. The critical lower bound uses a robust near-diagonal mixture inequality, while the upper bound quantizes a Gaussian auxiliary field. Finally, arbitrarily small dyadic heterogeneity can raise exact memory to bits without changing the fixed-error classification. These results separate algebraic distinguishability from statistically necessary memory; they do not bound uniform implementation time or arithmetic workspace.
Then back it, or bet against it.
Related papers
Open the market on this paper to see 7 more related papers.