PreprintarXiv licencearXiv
Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution
Abstract
We establish variance upper bounds for the minimum perfect matching problem in general metric spaces under a geometric partition condition. As a principal application, let Hn be the minimum perfect matching cost of n independent uniform points in [0,1]d, where n is even and d≥2. We prove Var(Hn)≤ C d n1−2/d, where C is independent of n and d. This removes the logarithmic losses in earlier upper bounds in every dimension (Talagrand, 1995); in particular, the variance remains bounded in dimension two, answering an open question (Rhee, 1994). The proof relies on constructing a rapidly mixing Markov process with a multinomial stationary distribution.
Related
- Discrete total variation under the multinomial, Part 2: variance under the uniform null
- LQG solution for POMDP without estimating states: A minimum variance approach
- Perfect matchings in planar 3-connected graphs: girth five and minimum degree five
- On $4$-perfect-matching covers of cubic graphs with two adjacent odd circuits in a $2$-factor
- Discrete total variation under the multinomial, Part 3: expectation under a general distribution
BibTeX
@misc{feng2026variance,
title = {{Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution}},
author = {Shi Feng},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14337},
eprint = {2610.14337},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14337},
}
RIS
TY - UNPB
TI - Variance Bounds for Minimum Perfect Matching Problem by Random Walk on Multinomial Distribution
AU - Shi Feng
PY - 2026
DA - 2026/10/09
PB - arXiv
DO - 10.48550/arxiv.2610.14337
UR - https://arxiv.org/abs/2610.14337
AB - We establish variance upper bounds for the minimum perfect matching problem in general metric spaces under a geometric partition condition. As a principal application, let H_n be the minimum perfect matching cost of n independent uniform points in [0,1]^d, where n is even and d≥2. We prove Var(H_n)≤ C d n^1−2/d, where C is independent of n and d. This removes the logarithmic losses in earlier upper bounds in every dimension (Talagrand, 1995); in particular, the variance remains bounded in dimension two, answering an open question (Rhee, 1994). The proof relies on constructing a rapidly mixing Markov process with a multinomial stationary distribution.
ER -