Poisson occupancy of paths on permuted regular graphs

Source 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 $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\toλ\in(0,\infty)$, provided $rL/d \to 0$, the empirical path multiplicity distribution converges in Wasserstein distance to $\operatorname{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.