The k -window statistic in a random permutation

We introduce a new permutation statistic, which we call the k -window statistic, for permutations of StartSet 1 comma 2 comma ellipsis comma n EndSet { 1 , 2 , … , n } \1,2,…, 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 equals k Subscript n k = k n k=kₙ is growing but remains normal o left parenthesis n right parenthesis o ( n ) o (n) . Via a representation of the statistic into dependent heterogeneous weakly correlated indicators, we establish the complete spectrum of distributions as k Subscript n k n kₙ spans its entire range using an appropriate method for each regime.