The law of the iterated logarithm for random permutations (Q1280864): Difference between revisions

Let \(\sigma\in S_n\) denote a permutation on \(n\) elements, and let \(\omega(\sigma)\) (respectively, \(\omega(\sigma, m)\)) denote the number of cycles in its representation (respectively, of length \(m\)). Further, \(\nu_n\) (condition) denotes the number of \(\sigma\) satisfying condition, divided by \(n!\). The central limit theorem for \(\omega(\sigma)\), i.e. for \(\Phi\) the standard normal cumulative distribution function \(\nu_n(\omega(\sigma)- \log n< x\sqrt{\log n})\to \Phi(x)\), was established in 1942, and subsequently extended to a functional form. This paper supplies an analogue to the law of the iterated logarithm, \[ \lim_{x\to\infty} \limsup_{n\to\infty} \nu_n \Biggl(\max_{x\leq m\leq n} {|\omega(\sigma, m)- \log m|\over \sqrt{2\log m\log\log m}}\geq 1+ \delta\Biggr)= 0. \] The proofs rely on comparing the distribution of \(\omega(\sigma, m)\) with that of a sum of independent Poisson variables. The results are valid for linear functions of \(\sigma\). An extension to a functional law of the iterated logarithm is promised for a subsequent paper.