Poisson occupancy of paths on permuted regular graphs
Abstract
In the classical occupancy problem, B balls are placed independently and uniformly into d boxes. We study a graph analogue of this model. Let G be a directed r-regular graph on d vertices and fix a vertex i. Consider all paths of length L starting from i, and let NL(i,j) denote the number of such paths ending at a vertex j. Thus the vertices play the role of boxes and the rL paths play the role of balls. In general, these occupancies depend strongly on the geometry of G. We show that inserting independent uniform permutations between successive layers restores the classical Poisson behavior at the empirical level. Although the path endpoints remain strongly dependent, their empirical occupancy distribution has the same limiting Poisson law as independent balls thrown into boxes. More precisely, at the critical scale rL/d→λ∈(0,∞), provided rL/d → 0, the empirical path multiplicity distribution converges in Wasserstein distance to Pois(λ), independently of the geometry of the underlying graphs. We also prove a local Poisson limit theorem and a Berry-Esseen bound for the empirical distribution functions. These estimates determine the full total-variation transition of the normalized path multiplicities toward uniformity. For arbitrary doubly stochastic kernels, we further establish exact covariance and Frobenius norm identities, together with an exact contraction formula for the chi-square divergence. As applications, we study synchronous opinion averaging, obtaining an explicit cutoff profile for equal-size groups and quantitative convergence to consensus for heterogeneous group sizes.
Related
- The upper bounds on occupancy fraction and variance fraction for linear regular uniform hypergraphs
- Global existence for the semilinear regular Euler-Poisson-Darboux-Tricomi equation, II
- Lattice paths on snake graphs for q-deformed rationals
- The Maximum Number of Shortest Paths in Graphs
- Oriented paths with two blocks in bipartite oriented graphs
BibTeX
@misc{chiclana2026poisson,
title = {{Poisson occupancy of paths on permuted regular graphs}},
author = {Rafael Chiclana},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14724},
eprint = {2610.14724},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14724},
}
RIS
TY - UNPB
TI - Poisson occupancy of paths on permuted regular graphs
AU - Rafael Chiclana
PY - 2026
DA - 2026/10/26
PB - arXiv
DO - 10.48550/arxiv.2610.14724
UR - https://arxiv.org/abs/2610.14724
AB - In the classical occupancy problem, B balls are placed independently and uniformly into d boxes. We study a graph analogue of this model. Let G be a directed r-regular graph on d vertices and fix a vertex i. Consider all paths of length L starting from i, and let N_L(i,j) denote the number of such paths ending at a vertex j. Thus the vertices play the role of boxes and the r^L paths play the role of balls. In general, these occupancies depend strongly on the geometry of G. We show that inserting independent uniform permutations between successive layers restores the classical Poisson behavior at the empirical level. Although the path endpoints remain strongly dependent, their empirical occupancy distribution has the same limiting Poisson law as independent balls thrown into boxes. More precisely, at the critical scale r^L/d→λ∈(0,∞), provided rL/d → 0, the empirical path multiplicity distribution converges in Wasserstein distance to Pois(λ), independently of the geometry of the underlying graphs. We also prove a local Poisson limit theorem and a Berry-Esseen bound for the empirical distribution functions. These estimates determine the full total-variation transition of the normalized path multiplicities toward uniformity. For arbitrary doubly stochastic kernels, we further establish exact covariance and Frobenius norm identities, together with an exact contraction formula for the chi-square divergence. As applications, we study synchronous opinion averaging, obtaining an explicit cutoff profile for equal-size groups and quantitative convergence to consensus for heterogeneous group sizes.
ER -