Explicit Expressions for Many mixed moments of the Number of Inversions and Spearman's Rho and a partial (elementary!) proof that they are Jointly asymptotically normal with Correlation 1 By Shalosh B. Ekhad Let's define two "measures of disarray" on permutations of length n, let's \ call them inv(pi) and RHO(pi) inv(pi) is the familiar number of inversions, the number of pairs 1<=ipi[j] , and the less natural one, called Spearman's RHO n ----- \ 2 RHO(pi) = ) (pi[i] - i) / ----- i = 1 The variance of inv is famously n (2 n + 5) (n - 1) ------------------- 72 and in Maple notation 1/72*n*(2*n+5)*(n-1) The variance of RHO, less famously (first found by Diaconis and Graham) is 2 2 n (n - 1) (n + 1) ------------------- 36 and in Maple notation 1/36*n^2*(n-1)*(n+1)^2 The covariance is 2 n (n - 1) (n + 1) ------------------ 36 and in Maple notation 1/36*n*(n-1)*(n+1)^2 hence the asymptotic correlation is 1 -------------------------------- The mixed , 1, 1, moment (about the means) of The number of inveresions and Spearman's RHO is 2 n (n - 1) (n + 1) ------------------ 36 and in Maple notation 1/36*n*(n-1)*(n+1)^2 The mixed , 1, 2, moment (about the means) of The number of inveresions and Spearman's RHO is 0 and in Maple notation 0 The mixed , 1, 3, moment (about the means) of The number of inveresions and Spearman's RHO is 2 4 3 2 2 n (n - 1) (25 n - 9 n - 65 n + 21 n + 40) (n + 1) ------------------------------------------------------ 10800 and in Maple notation 1/10800*n^2*(n-1)*(25*n^4-9*n^3-65*n^2+21*n+40)*(n+1)^2 -------------------------------- The mixed , 2, 1, moment (about the means) of The number of inveresions and Spearman's RHO is 0 and in Maple notation 0 The mixed , 2, 2, moment (about the means) of The number of inveresions and Spearman's RHO is 4 3 2 2 n (n - 1) (150 n - n - 429 n + 64 n + 96) (n + 1) ----------------------------------------------------- 64800 and in Maple notation 1/64800*n*(n-1)*(150*n^4-n^3-429*n^2+64*n+96)*(n+1)^2 The mixed , 2, 3, moment (about the means) of The number of inveresions and Spearman's RHO is 0 and in Maple notation 0 -------------------------------- The mixed , 3, 1, moment (about the means) of The number of inveresions and Spearman's RHO is 3 2 2 n (n - 1) (50 n + 27 n - 185 n + 12) (n + 1) ----------------------------------------------- 21600 and in Maple notation 1/21600*n*(n-1)*(50*n^3+27*n^2-185*n+12)*(n+1)^2 The mixed , 3, 2, moment (about the means) of The number of inveresions and Spearman's RHO is 0 and in Maple notation 0 The mixed , 3, 3, moment (about the means) of The number of inveresions and Spearman's RHO is 8 7 6 5 4 3 n (n - 1) (12250 n - 14749 n - 61634 n + 104612 n + 74872 n - 226915 n 2 2 - 13860 n + 136224 n + 13824) (n + 1) /38102400 and in Maple notation 1/38102400*n*(n-1)*(12250*n^8-14749*n^7-61634*n^6+104612*n^5+74872*n^4-226915*n ^3-13860*n^2+136224*n+13824)*(n+1)^2 hence the limit of the scaled mixed moments up to the 3rd are [1 0 3] [ ] [0 3 0] [ ] [3 0 15] and this happens to be EXACTLY the same as those of the joint normal distibu\ tion with correlation 1 This gives a partial (elementary!) proof of the joint asymptotic normality o\ f (inv,Spearman) with correlattion 1 more precisely, here are the first few terms of the asymptotic expansion, pr\ oving that these two measures of disarray are only asumptotically normal\ with correlation 1, but not exactly so. [ 1 35 325 11875 109375 2034375 19078125 [1 - --- + ----- - ------ + ------- - ------- + -------- - --------- [ 4 n 2 3 4 5 6 7 [ 32 n 128 n 2048 n 8192 n 65536 n 262144 n 1 483 573 1 ] + O(----) , 0 , 3 - ----- + ------ + O(----)] 8 100 n 2 3 ] n 160 n n ] [ 113 57 1857 1761 8997 44601 1 ] [0 , 3 - ---- + ----- - ------ + ----- - ----- + ------ + O(----) , 0] [ 25 n 2 3 4 5 6 7 ] [ 10 n 100 n 40 n 80 n 160 n n ] [ 363 3777 59223 2074881 22271061 1 [3 - ----- + ------ - ------- + -------- - --------- + O(----) , 0 , [ 100 n 2 3 4 5 6 [ 800 n 3200 n 51200 n 204800 n n 5931 4850061 1 ] 15 - ----- + -------- + O(----)] 100 n 2 3 ] 39200 n n ] Let's now do it in Maple notation The asympotic expansion of the scaled mixed , 1, 1, moment of the pair (inv,Spearman Rho) is 1 35 325 11875 109375 2034375 19078125 1 1 - --- + ----- - ------ + ------- - ------- + -------- - --------- + O(----) 4 n 2 3 4 5 6 7 8 32 n 128 n 2048 n 8192 n 65536 n 262144 n n and in Maple notation it is 1-1/4/n+35/32/n^2-325/128/n^3+11875/2048/n^4-109375/8192/n^5+2034375/65536/n^6-\ 19078125/262144/n^7+O(1/n^8) The asympotic expansion of the scaled mixed , 1, 2, moment of the pair (inv,Spearman Rho) is 0 and in Maple notation it is 0 The asympotic expansion of the scaled mixed , 1, 3, moment of the pair (inv,Spearman Rho) is 483 573 1 3 - ----- + ------ + O(----) 100 n 2 3 160 n n and in Maple notation it is 3-483/100/n+573/160/n^2+O(1/n^3) The asympotic expansion of the scaled mixed , 2, 1, moment of the pair (inv,Spearman Rho) is 0 and in Maple notation it is 0 The asympotic expansion of the scaled mixed , 2, 2, moment of the pair (inv,Spearman Rho) is 113 57 1857 1761 8997 44601 1 3 - ---- + ----- - ------ + ----- - ----- + ------ + O(----) 25 n 2 3 4 5 6 7 10 n 100 n 40 n 80 n 160 n n and in Maple notation it is 3-113/25/n+57/10/n^2-1857/100/n^3+1761/40/n^4-8997/80/n^5+44601/160/n^6+O(1/n^7 ) The asympotic expansion of the scaled mixed , 2, 3, moment of the pair (inv,Spearman Rho) is 0 and in Maple notation it is 0 The asympotic expansion of the scaled mixed , 3, 1, moment of the pair (inv,Spearman Rho) is 363 3777 59223 2074881 22271061 1 3 - ----- + ------ - ------- + -------- - --------- + O(----) 100 n 2 3 4 5 6 800 n 3200 n 51200 n 204800 n n and in Maple notation it is 3-363/100/n+3777/800/n^2-59223/3200/n^3+2074881/51200/n^4-22271061/204800/n^5+O (1/n^6) The asympotic expansion of the scaled mixed , 3, 2, moment of the pair (inv,Spearman Rho) is 0 and in Maple notation it is 0 The asympotic expansion of the scaled mixed , 3, 3, moment of the pair (inv,Spearman Rho) is 5931 4850061 1 15 - ----- + -------- + O(----) 100 n 2 3 39200 n n and in Maple notation it is 15-5931/100/n+4850061/39200/n^2+O(1/n^3)