Marčenko-Pastur Law for Kendall’s Tau
Afonso S. Bandeira∗, Asad Lodhia†, and Philippe Rigollet‡

arXiv:1611.04505v2 [math.ST] 21 Jan 2017

January 24, 2017

Abstract
We prove that Kendall’s Rank correlation matrix converges to the Marčenko Pastur law, under the
assumption that observations are i.i.d random vectors X1 , . . . , Xn with components that are independent
and absolutely continuous with respect to the Lebesgue measure. This is the first result on the empirical
spectral distribution of a multivariate U -statistic.

1

Introduction

Estimating the association between two random variables X, Y ∈ IR is a central statistical problem. As such
many methods have been proposed, most notably Pearson’s correlation coefficient. While this measure of
association is well suited to the Gaussian case, it may be inaccurate in other cases. This observation has
led statisticians to consider other measures of associations such as Spearman’s ρ and Kendall’s τ that can
be proved to be more robust to heavy-tailed distributions (see, e.g., [LHY+ 12]). In a multivariate setting,
covariance and correlation matrices are preponderant tools to understand the interaction between variables.
They are also used as building blocks for more sophisticated statistical questions such as principal component
analysis or graphical models.
The past decade has witnessed an unprecedented and fertile interaction between random matrix theory
and high-dimensional statistics (see [PA14] for a recent survey). Indeed, in high-dimensional settings, traditional asymptotics where the sample size tends to infinity fail to capture a delicate interaction between
sample size and dimension and random matrix theory has allowed statisticians and practitioners alike to
gain valuable insight on a variety of multivariate problems.
The terminology “Wishart matrices” is often, though sometimes abusively, used to refer to p × p random
matrices of the form X⊤ X/n, where X is an n × p random matrix with independent rows (throughout this
paper we restrict our attention to real random matrices). The simplest example arises where X has i.i.d
standard Gaussian entries but the main characteristics are shared by a much wider class of random matrices.
This universality phenomenon manifests itself in various aspects of the limit distribution, and in particular
in the limiting behavior of the empirical spectral distribution of the matrix. Let W = X⊤ X/n be a p × p
Wishart matrix and denote by λ1 , . . . , λp its eigenvalues; then the empirical spectral distribution µ̂p of W is
the distribution on IR defined as the following mixture of Dirac point masses at the λj s:
p

1X
δλk .
µ̂p =
p
k=1

Assuming that the entries of X are independent, centered and of unit variance, it can be shown that µp
converges weakly to the Marčenko-Pastur distribution under weak moment conditions (see [EKYY12] for
the weakest condition).
While this development alone has led to important statistical advances, it fails to capture more refined
notions of correlations, notably more robust ones involving ranks and therefore dependent observations. A
first step in this direction was made by [YK86], where the matrix X is assumed to have independent rows
∗ NYU,

Courant Institute of Mathematical Sciences: bandeira@cims.nyu.edu
Department of Mathematics: lodhia@math.mit.edu
‡ MIT, Department of Mathematics: rigollet@math.mit.edu
† MIT,

1

with isotropic distribution. More recently, this result was extended in [BZ08, O’R12] and covers for example
the case of Spearman’s ρ matrix that is based on ranks, which is also a Wishart matrix of the form X⊤ X/n.
The main contribution of this paper is to derive the limiting distribution of Kendall’s τ matrix, a cousin of
Spearman’s ρ matrix but which is not of the Wishart type but rather a matrix whose entries are U -statistics.
Kendall’s τ matrix is a very popular surrogate for correlation matrices but an understanding the fluctuations
of its eigenvalues is still missing. Interestingly, Marčenko-Pastur results have been used as heuristics, without
justification, precisely for Kendall’s τ in the context of certain financial applications [CCL+ 15].
As it turns out, the limiting distribution of µ̂p is not exactly Marčenko-Pastur, but rather an affine
transformation of it. Our main theorem below gives the precise form of this transformation.
Theorem 1. Let X1 , . . . , Xn , be n independent random vectors in IRp whose components Xi (k) are independent random variables that have a density with respect to the Lebesgue measure on IR. Then as n → ∞
and np → γ > 0 the empirical spectral distribution of τ converges in probability to
2
1
Y + ,
3
3
where Y is distributed according to the standard Marčenko-Pastur law with parameter γ (see Theorem 4 for
the appropriate definition).
Figure 1 illustrates numerically the result of Theorem 1.

Figure 1: Histogram of the eigenvalues the Kendall τ matrix for n = 2, 000, p = 1, 000. The superimposed red
line is the probability density function 23 Y + 13 , where Y is distributed according to the standard MarčenkoPastur law with parameter γ = 1/2.
Notation: For any integer k ≥ 1 we write [k] = {1, . . . , k}. We denote by Ip the identity matrix of
IRp . For a vector x ∈ IRp , we denote by x(j) it’s jth coordinate. For any p × p matrix M , we denote by
diag(M ) the p × p diagonal matrix with the same diagonal elements as M and any real number r, we define
Dr (M ) = M − diag(M ) + rIp . In other words, the operator Dr replaces each diagonal element of a matrix
by the value r. We denote sign the sign function with convention that sign(0) = 1. We define the Frobenius
norm of a p × p matrix H as kHk2F := Tr(H ⊤ H). Finally, we define Unif([a, b]) to be the uniform distribution
on the interval [a, b].

2

2

Kendall’s Tau

The (univariate) Kendall τ statistic [Ess24, Lin25, Lin29, Ken38] is defined as follows. Let (Y1 , Z1 ), . . . , (Yn , Zn )
be n independent samples of a pair (Y, Z) ∈ IR × IR of real-valued random variables. Then the (empirical)
Kendall τ between Y and Z is defined as
X
1
sign(Yi − Yj ) · sign(Zi − Zj ) .
τ (Y, Z) = n
2

1≤i<j≤n

The statistic τ takes values in [−1, 1] and it is not hard to see that it can be expressed as
τ=

1

n (# {concordant pairs} − # {discordant pairs}) ,
2

Where a pair (i, j) is said to be concordant if Yi −Yj and Zi −Zj have the same sign and discordant otherwise.
It is known that the Kendall τ statistic is asymptotically Gaussian (see, e.g., [Ken38]). Specifically, if Y
and Z are independent, then as n → ∞,


√
4
.
(1)
nτ (Y, Z)
N 0,
9
This property has been central to construct independence tests between two random variables X and Y (see,
e.g, [KG90]).
Kendall’s τ stastistic can be extended to the multivariate case. Let X1 , . . . , Xn , be n independent copies
of a random vector X ∈ IRp , with independent coordinates X(1), . . . , X(p). The (empirical) Kendall τ
matrix of X is defined to be the p × p matrix whose entries τ kl are given by
X


1
sign Xi (k) − Xj (k) · sign Xi (l) − Xj (l) 1 ≤ k, l ≤ p .
(2)
τ kl := τ (X(k), X(l)) = n
2

1≤i<j≤n

n
2

Note that the τ can be written as the sum of
τ =

1


n
2

X

1≤i<j≤n



rank-one random matrices:



sign Xi − Xj ⊗ sign Xi − Xj ,

(3)

where the sign function is taken entrywise.
It is easy to see that τ ii = 1 for all i. Together with (1), it implies that the matrix
τ̄ =

3
1
τ − Ip
2
2

√
is such that IE[ nτ̄ ] → Ip and Var[τ̄ ij ] → 1I{i 6= j} as n → ∞. This suggests that if the empirical spectral
distribution of τ̄ converges to a Marčenko-Pastur distribution, it should be a standard Marčenko-Pastur
distribution. This heuristic argument supports the affine transformation arising in Theorem 1. However, the
matrix τ is not Wishart and the Marčenko-Pastur limit distribution does not follow from standard arguments.
Nevertheless, Kendall’s τ is a U -statistic which are known to satisfy the weakest form of universality, namely
a Central Limit Theorem under general conditions [Hoe48, dlPG99]. In this paper, we show that in the case
of the Kendall τ matrix, this universality phenomenon extends to the empirical spectral distribution.

3

Proof of Theorem 1

For any pair (i, j) such that 1 ≤ i, j ≤ n and i 6= j, let A(i,j) be the vector

A(i,j) := sign Xi − Xj ,

and recall from (3) that

τ =

1
n
2



X

1≤i<j≤n

3

A(i,j) ⊗ A(i,j) .

Akin to most asymptotic results on U -statistics, we utilize a variant of Hoeffding’s (a.k.a. Efron-Stein,
a.k.a ANOVA) decomposition [Hoe48]:
A(i,j) = Ā(i,j) + Ā(i,·) + Ā(·,j)

(4)

where


Ā(i,·) := IE A(i,j) Xi ,



Ā(·,j) := IE A(i,j) Xj
and Ā(i,j) := A(i,j) − Ā(·,j) − Ā(i,·) .

It is easy to check that each of the vectors in the right-hand side of (4) are centered and are orthogonal
to each other with respect to the inner product IE[v ⊤ w] where v, w ∈ IRp . These random vectors can be
expressed conveniently thanks to the following Lemma.
Lemma 2. For k ∈ [p], let Fk denote the cumulative distribution function of X(k). Fix i ∈ [n] and let
Ui ∈ IRp is a random vector with kth coordinate given by Ui (k) = 2Fk (Xi (k)) − 1 ∼ Unif([−1, 1]). Then
Ā(i,·) = −Ā(·,i) = Ui .

Proof. For any i ∈ [n], observe that since the components of X have a density, then IP Xi (k) = Xj (k) Xi = 0
so that





IE sign Xi (k) − Xj (k) Xi = IP Xi (k) > Xj (k)) Xi − IP Xi (k) < Xj (k)) Xi = 2Fk (Xi (k)) − 1 .

The observation that Ā(i,·) = −Ā(·,i) follows from the fact that A(i,j) = −A(j,i) .
Using (4) we obtain the equality:


⊤
(2)
(2)
(3)
(1)
+ M(i,j) ,
A(i,j) ⊗ A(i,j) = M(i,j) + M(i,j) + M(i,j)

where

(5)

(1)

M(i,j) := Ip + D0 [{Ā(i,·) + Ā(·,j) } ⊗ {Ā(i,·) + Ā(·,j) }],
(2)

M(i,j) := D0 [Ā(i,j) ⊗ {Ā(i,·) + Ā(·,j) }],
(3)

M(i,j) := D0 [Ā(i,j) ⊗ Ā(i,j) ].
By the relation Ā(i,·) = −Ā(·,i) from Lemma 2 we have
X

1≤i<j≤n

{Ā(i,·) + Ā(·,j) } ⊗ {Ā(i,·) + Ā(·,j) } = (n − 1)

n
X
i=1

Ā(i,·) ⊗ Ā(i,·) −

n
X

(i,j)∈[n]2 :i6=j

Ā(i,·) ⊗ Ā(j,·) .

Using Lemma 2 yields:
1

n
2

n

X

1≤i<j≤n

(1)
M(i,j)

2X
1
= Ip +
D0 [Ui ⊗ Ui ] − n D0
n i=1
2

"

X

(i,j)∈[n]2 :i6=j

#

Ui ⊗ Uj .

(6)

Next, note that, the coordinates of each Ui , i = 1, . . . , n are mutually independent so that IE[Ui ] = 0 and


1
IE Ui ⊗ Ui = IE[T 2 ]Ip = Ip ,
3

(7)

where T ∼ Unif([−1, 1]). Theorem 4 implies as n → ∞ and np → γ > 0, the empirical spectral distribution
of
n
2X
Ui ⊗ Ui
n i=1
4

converges in probability to (2/3)Y , where Y is distributed according to the standard Marčenko-Pastur law
with parameter γ. Moreover,
!2
2
p
n
n
X
 2



1
2X
4 X
C
2
2
diag Ui ⊗ Ui − Ip = 2
IE
→ 0,
IE
Ui (k) − IE Ui (k)
≤
p
n i=1
3
pn
n
i=1
1
IE
p

1

n D0
2

"

X

(i,j)∈[n]2 :i6=j

Ui ⊗ Uj

k=1

F
2

#

=
F

1

X

IE

n 2
2
(k,l)∈[p]
:k6
=
l
2

p

(

X

)2

Ui (k)Uj (l)

(i,j)∈[n]2 :i6=j

≤

Cp
→ 0,
n2

for some constant C > 0 independent of n. By Lemma 5, the normalized Frobenius norm bounds the Lévy
distance between spectral measures. An application of Lemma 5, together with (6), triangle inequality and
the above bounds yields the following result.
Proposition 3. As n → ∞ and

p
n

→ γ > 0, the empirical spectral distribution µ̃p of
1

n
2

converges in probability to the law of
Pastur law with parameter γ.

2
3Y

X

(1)

M(i,j)

1≤i<j≤n

+ 13 , where Y is distributed according to the standard Marčenko-

Let µ̂τp denote the empirical spectral distribution of τ . Using Lemma 5 once more, we show that the
Lévy distance between µ̂τp and µ̃p converges to zero. This implies Theorem 1 by Proposition 3. To that end,
observe that by (5) and triangle inequality:
1
1
IE τ − n
p
2

X

(1)

M(i,j)

1≤i<j≤n

2
F

≤

2
IE
p

1

n
2

X

1≤i<j≤n

(2)

M(i,j)

2

1
+ IE
p
F

1

n
2

X

(3)

M(i,j)

1≤i<j≤n

2

.

(8)

F

 (3)
To show that (8) goes to zero, we notice that the collection of matrices M(i,j) 1≤i<j≤n satisfies
(
n
⊤
o
(3)
IEkM(i,j) k2F for (i, j) = (i′ , j ′ )
(3)
(3)
IE Tr M(i,j) M(i′ ,j ′ ) =
0
otherwise .
To see this, expand
o
⊤
n
(3)
(3)
IE Tr M(i,j) M(i′ ,j ′ ) =

X

(k,l)∈[p]2 :k6=l



(9)

IE[{A(i,j) (k) − Ui (k) + Uj (k)}{A(i′ ,j ′ ) (k) − Ui′ (k) + Uj ′ (k)}]

× IE[{A(i,j) (l) − Ui (l) + Uj (l)}{A(i′ ,j ′ ) (l) − Ui′ (l) + Uj ′ (l)}] ,

(10)

and notice that each expectation is zero unless (i, j) = (i′ , j ′ ) by Tower property and Lemma 2. Note that
when (i, j) = (i′ , j ′ ), the expression (10) is bounded by Cp2 for some C > 0. The equation (9) also holds
 (2)
(2)
for the collection of matrices M(i,j) 1≤i<j≤n and we also have IEkM(i,j) k2 ≤ Cp2 by a similar argument.
Therefore the right side of (8) is bounded by:

Cp
Cp
′ ′
4
′ ′
 × card (i, j, i , j ) ∈ [n] : (i, j) = (i , j ) ≤ 2 ,
n 2
n
2

for some constant C > 0, which vanishes as n → ∞. This concludes the proof of Theorem 1.
Acknowledgements: The authors would like to thank Alice Guionnet for helpful comments and discussions. A. S. B. was supported by Grant NSF-DMS-1541100. Part of this work was done while A. S. B. was
with the Department of Mathematics at MIT. A. L. was supported by Grant NSF-MS-1307704. P. R was
supported by Grants NSF-DMS-1541099, NSF-DMS-1541100 and DARPA-BAA-16-46 and a grant from the
MIT NEC Corporation.

5

A

The standard Marčenko-Pastur law

We include here the definition of the standard Marčenko-Pastur law and a bound on the distance between
empirical spectral distributions of two matrices.
Theorem 4 (Marčenko-Pastur law [BS10, Theorem 3.6]). Let X1 , . . . , Xn be independent copies of a random
vector X ∈ IRp such that
IE[X] = 0,
IE[X ⊗ X] = Ip .
√
√
Suppose that n → ∞, np → γ > 0 and define a = (1 − γ)2 , and b = (1 + γ)2 . Then the empirical spectral
distribution of the matrix
n
1X
Xi ⊗ Xi ,
n i=1
converges almost surely to the standard Marčenko-Pastur law which has density:

 1 p(b − x)(x − a),
if a ≤ x ≤ b,
pγ (x) = 2πxγ
0,
otherwise,

and has a point mass 1 −

1
γ

at the origin if γ > 1.

Lemma 5 ([BS10, Corollary A.41]). Let A and B be two p × p normal matrices, with empirical spectral
distributions µ̂A and µ̂B . Then
1
L(µ̂A , µ̂B )3 ≤ kA − Bk2F ,
p
where L(µ̂A , µ̂B ) is the Lévy distance between the distribution functions µ̂A and µ̂B .

References
[BS10]

Z. Bai and J. W. Silverstein. Spectral analysis of large dimensional random matrices. Springer
Series in Statistics. Springer, New York, second edition, 2010.

[BZ08]

Z. Bai and W. Zhou. Large sample covariance matrices without independence structures in
columns. Statist. Sinica, 18(2):425–442, 2008.

[CCL+ 15] F. Crénin, D. Cressey, S. Lavaud, J. Xu, and P. Clauss. Random matrix theory applied to
correlations in operational risk. Journal of Operational Risk, 10(4):45–71, December 2015.
[dlPG99]

V. H. de la Peña and E. Giné. Decoupling. Probability and its Applications (New York). SpringerVerlag, New York, 1999.

[EKYY12] L. Erdős, A. Knowles, H.-T. Yau, and J. Yin. Spectral statistics of Erdős-Rényi Graphs II:
Eigenvalue spacing and the extreme eigenvalues. Comm. Math. Phys., 314(3):587–640, 2012.
[Ess24]

F. Esscher. On a method of determining correlation from the ranks of the variates. Scandinavian
Actuarial Journal, 1924(1):201–219, 1924.

[Hoe48]

W. Hoeffding. A class of statistics with asymptotically normal distribution. Ann. Math. Statistics,
19:293–325, 1948.

[Ken38]

M. G. Kendall. A new measure of rank correlation. Biometrika, 30(1/2):81–93, 1938.

[KG90]

M. Kendall and J. D. Gibbons. Rank correlation methods. A Charles Griffin Title. Edward
Arnold, London, fifth edition, 1990.

[LHY+ 12] H. Liu, F. Han, M. Yuan, J. Lafferty, and L. Wasserman. High-dimensional semiparametric
Gaussian copula graphical models. Ann. Statist., 40(4):2293–2326, 2012.

6

[Lin25]

J. W. Lindeberg. Über die korrelation. Den VI skandinaviske Matematikerkongres i København,
pages 437–446, 1925.

[Lin29]

J. Lindeberg. Some remarks on the mean error of the percentage of correlation. Nordic Statistical
Journal, 1:137–141, 1929.

[O’R12]

S. O’Rourke. A note on the Marchenko-Pastur law for a class of random matrices with dependent
entries. Electron. Commun. Probab., 17:no. 28, 13, 2012.

[PA14]

D. Paul and A. Aue. Random matrix theory in statistics: a review. J. Statist. Plann. Inference,
150:1–29, 2014.

[YK86]

Y. Q. Yin and P. R. Krishnaiah. Limit theorems for the eigenvalues of product of largedimensional random matrices when the underlying distribution is isotropic. Teor. Veroyatnost. i
Primenen., 31(2):394–398, 1986.

7

