Sharp collision criteria for frozen color histograms
Loading original first page…
Abstract
A probability law selects fixed-size subsets of a finite ground set, whose elements are independently colored once. We compare the histogram law conditional on that frozen coloring with the prescribed multinomial law. Under upper negative-cylinder inequalities, the normalized marginal collision sum gives a sharp criterion for expected chi-square convergence and its leading coefficient, uniformly over positive varying color probabilities and color counts. A covariance statistic gives a linear collision lower bound for expected total variation without any dependence hypothesis on the subset law. Under the upper-cylinder hypothesis, we obtain an exact convergence criterion for binary colors with varying probabilities that combines subset collisions and color rarity. For a fixed positive color vector, the same hypothesis gives total-variation convergence exactly when the collision sum vanishes. A non-real-stable example and applications to spanning trees and matroid-base rounding illustrate the scope.
Read the full paper in the original PDF.
Edition files
- Color_histogram_collision_criteria.pdf110.6 KiB · pdf
SHA-256
9a804e7bfe56f5a3727e483998979e76260815f4ad13ddbe2dc66374e34deff8 - Color_histogram_collision_criteria_package.zip131.2 KiB · package
SHA-256
da838fa562cc8917f7c2322afb2403a60de9d490c1379824595e118c83260517
Available editions
Research details
- Subjects
- Mathematics · Combinatorics and Graph Theory · Probability and Statistics
- Keywords
- multinomial approximation, negative dependence, frozen coloring, collision probability, total variation, matroid rounding
- Manuscript date
- 2026-10-26
- Reader reuse
- none
Scope
A probability law selects fixed-size subsets of a finite ground set, whose elements are independently colored once.
Disclosures
Author-posted preprint. OpenAI ChatGPT and Codex assisted exploration, literature comparison, drafting, derivation, and internal proof and code checks, as disclosed in the manuscript. The author assumes responsibility for all content.
Reproduction
Complete searchable manuscript and 13-member source package with editable sources and necessary reader-facing verification material. Build instructions and computational scope are stated in the package; proofs are given in the manuscript.
References and related resources
- P. Diaconis and R. C. Griffiths. Reproducing kernel orthogonal polynomials on the multinomial distribution (2019). arXiv:1802.07122v3.
- W.-L. Loh. Stein’s method and multinomial approximation. Annals of Applied Probability 2(3) (1992), 536-554.
- S. G. Bobkov. Generalized symmetric polynomials and an approximate de Finetti representation. Journal of Theoretical Probability 18 (2005), 399-412.
- B. Roos. On Bobkov’s approximate de Finetti representation via approximation of permanents of complex rectangular matrices (2014). arXiv:1203.2871v2.
- Y. Han and J. Niles-Weed. Approximate independence of permutation mixtures. Annals of Statistics 54(3) (2026), 1594-1621; arXiv:2408.09341v3.
- Y. Han and J. Niles-Weed. Elementary symmetric polynomial inequalities for centered vectors and matrices (2026). arXiv:2607.23836v1.
- S. Schubr. Moment certificates for homogeneous stable count laws. Luminary Research Archive, edition 6 (2026).
- J. Borcea, P. Brändén and T. M. Liggett. Negative dependence and the geometry of polynomials. Journal of the American Mathematical Society 22 (2009), 521-567.
- C. Chekuri, J. Vondrák and R. Zenklusen. Dependent randomized rounding for matroid polytopes and applications (2009). arXiv:0909.4348v2.