Sharp collision criteria for frozen color histograms

Overview

Abstract

Let a fixed probability law select an n-element subset of a finite ground set, and color every ground element independently once, with prescribed positive probabilities q_1,...,q_m. We compare the conditional histogram law after freezing the coloring with Mult(n,q). Under upper negative-cylinder inequalities, the normalized marginal collision sum tau = (1/n) sum_e Pr(e in S)^2 determines expected chi-square convergence: the distance tends to zero if and only if (m-1)tau does, and is asymptotic to (m-1)tau in that regime. The statements are uniform over positive color probabilities, without a minimum-probability assumption. For fixed positive q and fixed m >= 2, expected total variation tends to zero if and only if tau does. The necessary half follows from an explicit covariance statistic and holds for every fixed-size subset law. The proof combines the classical multinomial overlap kernel with negative-cylinder factorial moments. An explicit diffuse non-real-stable family separates the hypotheses from real stability; spanning-tree and fixed matroid-base-rounding laws give applications.

Keywords multinomial approximation · negative dependence · frozen coloring · collision probability · total variation · matroid rounding