In the past week or so I have been playing around with various metrics on , as a continuation of the previous post. Most notably I looked at the Spearman’s distance, which is the analogue of the footrule and defined as
The task is to find their correlations. Once that’s done, the multivariate central limit theorem usually follows from the vector valued version of the Hoeffding’s combinatorial central limit theorem, which states
Theorem 10 Let be an square matrix with for all where stands for the ith row average and similarly for . Also let . For a permutation , define the following generalized diagonal sum:
Then for uniformly chosen from :
where . and the following central limit theorem holds
for some absolute constant .
This result is initially due to Wassily Hoeffding, later improved by Motoo and finally proved in complete generality and with error bound by Bolthausen, using Stein’s method. We will visit Bolthausen’s argument in a later post.
In the case of the statistics, are of order whereas is of order , hence the error term above is bounded by . Here the matrix is given by .
Similarly we can take linear combinations of different
where . Then the above combinatorial CLT also applies to and we basically establish the joint normality of for any finite collection of ‘s.
It remains to compute the correlation between pairs of and , which are the same as and .
The computation mimics the calculation done for the inversion and footrule distance. We used mathematica to compute quantities of the form . The correlation is then given by
Below we tabulated a few mathematica assisted computation of correlations for various pairs of and ‘s:
One observes that as and get further apart in ratio, their correlation goes to . This is reminiscent to the phenomena of separation of scale I used to prove asymptotic independence of various quantities on . I would like to thank James Zhao for simulation results that corrected my initial computation of the correlation between the footrule and the spearman’s distance. Some further simulation suggests that the footrule and the longest increasing subsequence length (aka Ulam’s distance) are significantly correlated in the limit: it converges to something around . But if one looks at the following distance defined by
Then simulation suggests the correlation between Ulam’s distance and is asymptotically very weak if not . With I obtained an empirical correlation of and with it drops to . It will be interesting to prove that they are actually asymptotically independent. Note that Ulam’s distance does not converge to the standard normal upon linear transformation in the limit . So vanishing correlation does not imply that it is independent from . One would also like to understand the underlying reason why Ulam’s distance is highly correlated with some quantities such as , but independent with others, such as the the length of the longest decreasing subsequence of a permutation, a result that follows from the connection between permutations to Young diagrams under Plancherel measure via the RSK algorithm, and the latter with eigenvalues of Gaussian unitary ensemble, a result proved independently by Borodin, Okounkov, Olshanski and Johansson. See the article Asymptotics of Plancherel Measures for Symmetric groups by the first group.