Refine search
Actions for selected content:
1 results
The k-window statistic in a random permutation
- Part of
-
- Journal:
- Journal of Applied Probability , First View
- Published online by Cambridge University Press:
- 03 September 2026, pp. 1-20
-
- Article
-
- You have access
- HTML
- Export citation
-
We introduce a new permutation statistic, which we call the k-window statistic, for permutations of
$\{1,2,\ldots, n\}$. The aim is to add to the repertoire of potentially useful tools in the design of efficient algorithms. The k-window statistic counts the number of elements that are at a displacement at most k from their natural positions in the ascendingly sorted permutation. We find the exact mean and exact variance of the k-window statistic, revealing phases in the mean and variance in the different regimes of k. We find a weak (or even strong) law of large numbers in the regime where 
$k=k_n$ is growing but remains 
${\mathrm{o}} (n)$. Via a representation of the statistic into dependent heterogeneous weakly correlated indicators, we establish the complete spectrum of distributions as 
$k_n$ spans its entire range using an appropriate method for each regime.
