betaFeedback

WorksMathematics

Microscopic Probabilities for U-Statistics and Almost-Balanced Permutations

Abstract

We estimate the probability that a vector of U-statistics lies within C/nC/n of a target in the range of typical fluctuations. For sufficiently large CC, we prove a lower bound of the typical Gaussian order under finite variance, and a matching upper bound for bounded kernels. We show that under finite variance alone, stronger concentration may occur, and find the best possible asymptotic upper bound. Our proof is algorithmic, estimating probabilities by counting successful modifications produced by a random algorithm. We apply this result to settle a question of Beniamini, Lavee and Linial (2025), who asked if there exist permutations with kk-order sub-pattern counts at most O(nk−1)O(n^{k-1}) away from one another for k>4k>4. We prove not only existence, but enumerate these permutations up to a constant factor, showing that there are Θ(n!n−(k−1)2/2)Θ(n!n^{-(k-1)^2/2}) such permutations of size nn.

Paper details

vlnc:W_sxgbzs2d
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…