arXiv:1709.04606v1 [] 14 Sep 2017

Goodness-of-Fit Tests for Random Partitions via Symmetric
Polynomials
Chao Gao
University of Chicago
September 15, 2017

Abstract
We consider goodness-of-fit tests with i.i.d. samples generated from a categorical
distribution (p1 , ..., pk ). We test the null hypothesis whether pj = qπ(j) for some label
permutation π. The uncertainty of label permutation implies that the null hypothesis
is composite instead of being singular. In this paper, we construct a testing procedure
using statistics that are defined as indefinite integrals of some symmetric polynomials.
This method is aimed directly at the invariant signal of the problem, and avoids the need
of matching the unknown labels. The asymptotic distribution of the testing statistic is
shown to be chi-squared, and its power is proved to be nearly optimal under a local
alternative hypothesis. Various degenerate structures of the null hypothesis are carefully
analyzed in the paper. A two-sample version of the test is also studied.
Keywords: hypothesis testing, elementary symmetric polynomials, Lagrange interpolating polynomials, Vandermonde matrix, minimax optimality.

1

Introduction

Consider a categorical distribution parameterized by (p1 , ..., pk ). We have i.i.d. observations
X1 , ..., Xn that follow P(Xi = j) = pj . A classic goodness-of-fit testing problem is to test
whether or not pj = qj for j ∈ [k], where q1 , ..., qk are some given numbers. One solution
is given by the famous Pearson’s chi-squared test [12]. In this traditional formulation, it is
assumed that the labels (1, ...., k) of (p1 , ..., pk ) correspond to those of (q1 , ..., qk ), so that pj
can be directly compared with qj for each j ∈ [k]. However, this assumption is not satisfied
in some interesting applications. We give three examples below:
1. Clustering models. In a typical probabilistic setting of cluster analysis, the event {Xi =
j} means that the ith item belongs to the jth cluster, and pj is the population frequency
of the jth cluster. Here, the cluster label j does not carry any real meaning, and is
present only for notational convenience. In a cluster analysis setting, the underlying
object of interest is the partition of the n items instead of the cluster labels. In other
1

words, what really matters to statisticians is the value of I{Xi = Xi′ } for every pair
i 6= i′ . Therefore, a clustering model with population frequency (p1 , ..., pk ) is equivalent
to that with (pπ(1) , ..., pπ(k) ) with some permutation π.
2. Word frequency analysis. Consider two text corpora of two different languages. The
word frequencies are denoted by (p1 , ..., pk ) and (q1 , ..., qk ), respectively. An interesting
problem in comparative linguistics is to study whether the two languages share common
features by comparing (p1 , ..., pk ) with (q1 , ..., qk ). For languages that are not necessarily
etymologically related, the correspondence between words of the two languages are
usually unclear or unknown. Therefore, a reasonable comparison of word frequencies
between two languages can be conducted through comparing (p1 , ..., pk ) with a reordered
vector (qπ(1) , ..., qπ(k) ) for some permutation π.
3. Simple substitution cipher. In cryptography, a simple substitution cypher changes every
character in a message to a different character systematically. Let {1, ..., k} be a finite
alphabet of characters, and (Y1 , ..., Yn ) denote a message to be encrypted. A simple
substitution cypher is defined by a permutation σ on the alphabet {1, ..., k}. This
results in the encrypted message (X1 , ..., Xn ) with Xi = σ(Yi ) for each i ∈ [n]. Suppose
each Yi is independently distributed by P(Yi = j) = qj . Then, each Xi independently
follows P(Xi = j) = pj , where pj = qπ(j) with π = σ −1 . If only the encrypted message
is observed, inference of the probability vector (q1 , ..., qk ) is only possible up to an
unknown permutation.
Inspired by the above examples, in this paper, we consider a twist of the traditional
formulation of the hypothesis testing problem. We consider the following null hypothesis:
H0 : pj = qπ(j) ,

for some π ∈ Sk ,

(1)

where Sk is the set of all permutations of [k]. This null hypothesis implies that the labels


1, ..., k do not have any meaning. For example, the vectors 21 , 14 , 14 and 14 , 14 , 12 are considered equivalent. Given observations X1 , ..., Xn , one can immediately define summary statisP
tics nj = ni=1 I{Xi = j} for j ∈ [k], which are sufficient. Since the labels of n1 , ..., nk are irrelevant, these sufficient statistics result in a random partition of the integer n. There are two
ways to code such a random partition [14]: (i) by the order statistics n(1) ≥ n(2) ≥ ... ≥ n(k) ;
P
(ii) by the numbers of terms of various sizes ml = kj=1 I{nj = l} for l ∈ [n]. It is easy to
P
P
see that nl=1 ml = k and nl=1 lml = n. These two representations are equivalent because
one can be derived from the other.
Inference of the probability vector (p1 , ..., pk ) up to a label permutation using random
partitions have been extensively studied in Bayesian statistics. The problem serves as a
foundation for random partition models, cluster analysis and species distribution modeling.
Priors that induce various exchangeable properties have been developed for the equivalent
class {(pπ(1) , ..., pπ(k) ) : π ∈ Sk }. See [7, 14, 11, 6] and references therein. In this paper, we
take a frequentist point of view that is complementary to the Bayesian literature, and we do
2

not treat the equivalent class {(pπ(1) , ..., pπ(k) ) : π ∈ Sk } as random. The theory of hypothesis
testing is developed within a frequentist decision-theoretic framework.
With the unknown permutation π in the null hypothesis, the classical chi-squared test
by Pearson does not work anymore. Our idea of the test is based on the following class of
statistics:


k

X
f (nj ) : f ∈ F ,
(2)


j=1

where F is the class of all measurable functions. For each f ∈ F, the distribution of
Pk
j=1 f (nj ) is identical for pj = qπ(j) with any π ∈ Sk . This is because (2) is a class of
P
P
statistics that are invariant to the label permutation π. That is, kj=1 f (nj ) = kj=1 f (nπ(j) )
for any π ∈ Sk . Moreover, it is easy to see that these statistics are all functions of the random
P
P
partition because kj=1 f (nj ) = kj=1 f (n(j) ).
Choosing an appropriate class of f ’s is important. We propose to use k functions f1 , ..., fk
that satisfy the identifiability and the orthogonality conditions. The identifiability condition
P
P
requires that the k equations kj=1 fl (pj ) = kj=1 fl (qj ) for l ∈ [k] hold if and only if pj = qπ(j)
for some π ∈ Sk . With this condition, testing whether the null hypothesis holds is equivalent
to testing whether the k equations hold. The orthogonality condition requires that the k
vectors (fl′ (q1 ), ..., fl′ (qk ))T for l ∈ [k] are orthogonal to each other. Intuitively speaking,
P
this condition ensures that the information carried by the k statistics kj=1 fl (nj ) for l ∈ [k]
are mutually exclusive, which is a key ingredient that leads to optimal power under a local
alternative.
In this paper, we choose f1 , ..., fk to be indefinite integrals of Lagrange interpolation
polynomials. The choice of these polynomials satisfies the above-mentioned identifiability
and orthogonality conditions. We prove that the testing statistic constructed from the k
functions is asymptotically distributed by a chi-squared distribution. Moreover, we show
that the power of the test is nearly optimal under a local alternative hypothesis within a
decision-theoretic framework.
Our approach that uses symmetric polynomials bypasses the problem of unknown permutation π. It falls into the general umbrella of methods of moments, which are commonly used
for problems that impose equivalence relations to the signals through the action of a group of
transformations. For example, various method-of-moments techniques have been applied to
problems including Gaussian mixture models [10], mixed membership models [2], dictionary
learning [4], topic models [1] and multi-reference alignment [13]. Recently, this idea was also
applied to the problems of network testing by [8, 5], where the group action there is row and
column permutations of the adjacency matrix of a random network.
The rest of the paper is organized as follows. In Section 2, we introduce definitions of
some useful symmetric polynomials and the related Vandermonde matrix. Before getting
into the testing problem for random partitions, we first solve an easier version of the problem
with Gaussian observations in Section 3 and Section 4. The test using random partitions is
given in Section 5. The optimality of our test is discussed in Section 6. In Section 7, we
consider a two-sample version of the problem. Finally, Section 8 is a discussion section, where
3

we briefly analyze the property of the test on the boundary of degeneracy and discuss some
open problems. The proofs of all results in the paper are given in Section 9.
We close this section by introducing the notation used in the paper. For a, b ∈ R, let
a ∨ b = max(a, b) and a ∧ b = min(a, b). For an integer m, [m] denotes the set {1, 2, ..., m}.
Given a set S, |S| denotes its cardinality, and IS is the associated indicator function. We
use P and E to denote generic probability and expectation whose distribution is determined
from the context. The noncentral chi-squared distribution with degrees of freedom k and
noncentrality parameter δ2 is denoted as χ2k,δ2 . We will also use χ2k,δ2 for the associated
random variables.

2

Symmetric Polynomials and Vandermonde Matrix

Define a polynomial with roots µ1 , ..., µk ∈ R by
f (t) =

k
Y

(t − µj ).

j=1

It can be organized as
k
X
(−1)k−j ek−j (µ1 , ..., µk )tj .
f (t) =

(3)

j=0

The coefficient before tj is (−1)k−j ek−j (µ1 , ..., µk ), and ek−j (µ1 , ..., µk ) is called the elementary symmetric polynomial. For l ∈ {1, ..., k}, the lth elementary symmetric polynomial
is
X
µj 1 · · · µj l .
el (µ1 , ..., µk ) =
1≤j1 <···<jl ≤k

When l = 0, we use the convention e0 (µ1 , ..., µk ) = 1.
The elementary symmetric polynomials can be efficiently calculated through Newton’s
identities. Define the lth power sum
pl (µ1 , ..., µk ) =

k
X

µlj .

(4)

j=1

Newton’s identities can be summarized through the formula
l

el (µ1 , ..., µk ) =

1X
(−1)j−1 el−j (µ1 , ..., µk )pj (µ1 , ..., µk ),
l

(5)

j=1

for l = 1, ..., k.
Finally, we introduce an interesting relation between elementary symmetric polynomials
and Vandermonde matrix (see Chapter 0.9.11 of [9]). Given µ1 , ..., µk that take k distinct
values, define a matrix E(µ1 , ..., µk ) ∈ Rk×k , whose (j, l)th entry is
(−1)j−1

ek−j (µ1 , ..., µl−1 , µl+1 , ..., µk )
Q
.
j∈[k]\{l} (µj − µl )
4

(6)

The Vandermonde matrix V (µ1 , ..., µk ) ∈ Rk×k has µl−1
on its (j, l)th entry. Interestingly,
j
we have
E(µ1 , ..., µk )V (µ1 , ..., µk ) = V (µ1 , ..., µk )E(µ1 , ..., µk ) = Ik .
(7)
This relation implies a formula for the determinant of E(µ1 , ..., µk ):
det(E(µ1 , ..., µk )) =

3

The Gaussian Case

1
1
=Q
.
det(V (µ1 , ..., µk ))
1≤j<l≤k (µl − µj )

(8)

Before working with categorical distributions, we first study data generated from a Gaussian
distribution. This allows us to grasp the mathematical essence of the problem without dealing with the dependence and heteroskedasticity of categorical distributions. We consider a
Gaussian random vector X ∼ N (θ, n−1 Ik ). The mean vector θ ∈ Rk consists of k numbers
θ1 , ..., θk . Throughout the paper, we assume k ≥ 2 and it is a constant that does not vary
with n. We would like to test whether the k numbers are identical to µ1 , ..., µk after some
permutation of labels. To be rigorous, introduce a distance between two vectors θ and µ,
v
u k
uX
ℓ(θ, µ) = min t (θj − µπ(j) )2 ,
π∈Sk

j=1

where Sk is the set of all permutations on [k]. Then, the hypothesis testing problem is
H0 : ℓ(θ, µ) = 0,

H1 : ℓ(θ, µ) > 0.

Throughout this section, we assume minj6=l |µj − µl | > 0. The case minj6=l |µj − µl | = 0 is
degenerate and will be studied in the next section.
We use the notation µπ to denote a k-dimensional vector whose jth entry is µπ(j) . Then,
the null hypothesis can also be written as
θ ∈ {µπ : π ∈ Sk }.
In other words, there is an equivalent class of probability distributions {N (µπ , n−1 Ik ) : π ∈
Sk }. Thus, it is natural to consider summary statistics whose distributions are invariant
under this equivalent class. This leads to the class of summary statistics


k
X

f (Xj ) : f ∈ F ,


j=1

where F is the set of all measurable functions. For X ∼ N (θ, n−1 Ik ), it is easy to see that
P
the distribution of kj=1 f (Xj ) only depends on the equivalent class {N (θk , n−1 Ik ) : π ∈ Sk }.
This fact holds for an arbitrary f ∈ F.
Since the degree of freedom
is k, our strategy is to construct a
nP of the null hypothesis
o
k
testing procedure based on
j=1 fl (Xj ) : l ∈ [k] . In other words, we need to choose the k
functions f1 (·), ..., fk (·). The following two conditions are proposed:
5

1. Identifiability. Assume minj6=l |µj − µl | > 0. Then the equations
k
X

fl (θj ) =

k
X

fl (µj ),

l = 1, ..., k,

(9)

j=1

j=1

hold, if and only if ℓ(θ, µ) = 0.
2. Orthogonality. Assume minj6=l |µj − µl | > 0. Then for any l, h ∈ [h],
(
k
X
1, l = h,
fl′ (µj )fh′ (µj ) =
0, l 6= h.
j=1
We give a few remarks regarding the two conditions. The first condition of identifiability is
natural. It is naturally required by the structure of the problem, and is necessary for the test
to have power under the alternative hypothesis. The second condition implies information
independence among the k summary statistics.
The k functions we propose to satisfy the two conditions are
RQ
j∈[k]\{l} (t − µj )
fl (t) = Q
, l = 1, ..., k.
(10)
j∈[k]\{l} (µl − µj )

The derivatives

fl′ (t)

=

Q
(t−µj )
Q j∈[k]\{l}
j∈[k]\{l} (µl −µj )

are called Lagrange interpolating polynomials, and

it is easy to check that the second condition of orthogonality holds. Now we check the first
condition of identifiability. By (3), we have
Y

(t − µj ) =

j∈[k]\{l}

k−1
X

(−1)k−1−j ek−1−j (µ1 , ..., µl−1 , µl+1 , ..., µk )tj .

j=0

This implies
fl (t) =

k
X
j=1

(−1)k−j

ek−j (µ1 , ..., µl−1 , µl+1 , ..., µk ) tj
Q
.
j
j∈[k]\{l} (µl − µj )

(11)

Therefore, the equations (9) can be written as

k
X
ek−j (µ1 , ..., µl−1 , µl+1 , ..., µk )
Q
(−1)k−j
∆j = 0,
j∈[k]\{l} (µl − µj )

l = 1, ..., k.

j=1

P
P
where ∆j = 1j kh=1 θhj − 1j kh=1 µjh . In view of the definition of the matrix E(µ1 , ..., µk ) in
(6), we have a compact organization of the equations
E(µ1 , ..., µk )∆ = 0.
When the assumption minj6=l |µj − µl | > 0 holds, the matrix E(µ1 , ..., µk ) has full rank and
is invertible according to (7) and (8), which immediately implies ∆ = 0. Equivalently,
pj (θ1 , ..., θk ) = pj (µ1 , ..., µk ),
6

j = 1, ..., k.

The definition of the power sum pj (· · · ) is given in (4). By Newton’s identities (5), we have
ej (θ1 , ..., θk ) = ej (µ1 , ..., µk ),

j = 1, ..., k.

Finally, the relation between elementary symmetric polynomials and roots in (3) implies that
Qk
Qk
j=1 (t − θj ) and
j=1 (t − µj ) are the same polynomials. Hence, we obtain the conclusion
ℓ(θ, µ) = 0. The other direction trivially holds. This verifies the condition of identifiability
for the functions f1 , ..., fk .
P
Remark 3.1. The computation of the statistic kj=1 fl (Xj ) for each l ∈ [k] is straightforward,
thanks to the formula (11). According to (11), we can write
k
X

fl (Xj ) =

j=1

k
X
i=1

ek−i (µ1 , ..., µl−1 , µl+1 , ..., µk )
Q
(−1)k−i
i∈[k]\{l} (µl − µi )

Pk

i
j=1 Xj

i

.

P
P
In other words, kj=1 fl (Xj ) is a linear combination of empirical moments { kj=1 Xji : i ∈
[k]}. To compute the elementary symmetric polynomial ek−i (µ1 , ..., µl−1 , µl+1 , ..., µk ) in the
coefficient, one can recursively apply Newton’s identities (5). The overall complexity of comP
puting kj=1 fl (Xj ) requires O(k2 ) products.
We propose the testing statistic
T =n

k
X
l=1




k
X
j=1

fl (Xj ) −

k
X
j=1

2

fl (µj ) .

(12)

When the value of T is large, the equations (9) are unlikely to hold. Thus, the null hypothesis
will be rejected when T exceeds some threshold. The asymptotic distribution of T can be
derived under the null hypothesis.
Condition A. Assume µ1 , ..., µk are k different numbers that do not vary with n.
Some possible extensions beyond Condition A will be discussed in Section 6.
Theorem 3.1. Under Condition A, T

χ2k as n → ∞ under the null hypothesis.

For a chi-squared random variable χ2k , define a number χ2k (α) such that

P χ2k ≤ χ2k (α) = 1 − α.

Then, a testing function is


φα = I T > χ2k (α) .

By Theorem 3.1, its asymptotic Type-1 error is α. The next result characterizes the regime
where the asymptotic power of the test tends to 1. It is a consequence of the fact that the
functions f1 , ..., fk satisfy the identifiability condition.
Theorem 3.2. Under Condition A, the following two statements are equivalent
7

1. limn→∞

√

nℓ(θ, µ) = ∞;

2. limn→∞ Pθ T > χ2k (α) = 1, for any constant α ∈ (0, 1),

where the probability Pθ denotes N (θ, n−1 Ik ).
√
Theorem 3.2 shows that limn→∞ nℓ(θ, µ) = ∞ is the necessary and sufficient condition
√
for the asymptotic power of the test to be one. For a local alternative such that nℓ(θ, µ) =
O(1), the test will have a non-trivial power between 0 and 1. This contiguous regime will be
studied in Section 6.

4

Degeneracy of the Problem

In the last section, we construct a chi-squared test under the assumption that minj6=l |µj −
µl | > 0. When minj6=l |µj − µl | = 0, the identifiability condition of the functions f1 , ..., fk
defined in (10) does not hold. We need to construct summary statistics based on new functions
in this degenerate case.
Assume there is a partition of the set [k]. That is, for some d ≤ k, we have ∪dh=1 Ch = [k],
and for any g, h ∈ [d] such that g 6= h, Cg ∩ Ch = ∅. We assume
µj = νh , for all j ∈ Ch .
Moreover, we require that ming6=h |νg − νh | > 0. To motivate the appropriate functions that
we will propose, we consider two extreme cases. The first case is when d = k. Then, the
condition minj6=l |µj − µl | > 0 still holds, and we can still use the functions f1 , ..., fk defined
in (10). The second case is when d = 1. This implies µ1 = µ2 = · · · = µk = ν1 . Then, we can
use the function
g(t) = (t − ν1 )2 .
(13)
Pk
This leads to an obvious chi-squared statistic Tg = n j=1 g(Xj ).
For a general d, we need to borrow ideas from both extreme cases. We define functions
f1 , ..., fd that are modifications from (10). Define
RQ
g∈[d]\{h} (t − νg )
fh (t) = Q
, h = 1, ..., d.
(14)
g∈[d]\{h} (νh − νg )
We also need another function to ensure identifiability. Define
Qd
2
g=1 (t − νg )
.
g(t) = Pd Q
2
g=1
h∈[d]\{g} (t − νh )

(15)

The function g(t) is well defined when d ≥ 2. When d = 1, we use the definition given by (13).
The following proposition shows that the functions f1 , ..., fd , g together ensure identifiability
via the equations
k
k
X
X
fh (µj ), h = 1, ..., d,
(16)
fh (θj ) =
j=1

j=1

8

and

k
X

g(θj ) =

k
X

g(µj ).

(17)

j=1

j=1

Proposition 4.1. Assume ming6=h |νg − νh | > 0. We have the following conclusions.
1. When d = 1, the equation (17) holds if and only if ℓ(θ, µ) = 0.
2. When 2 ≤ d ≤ k − 1, the equations (16) and (17) hold if and only if ℓ(θ, µ) = 0.
3. When d = k, the equations (16) hold if and only if ℓ(θ, µ) = 0.
The first conclusion of the above proposition is obvious. The last conclusion is proved in
Section 3. Here we show the second conclusion. Using a similar argument that we used in
Section 3, the equations (16) can be written as
E(ν1 , ..., νd )∆ = 0,
P
where ∆ ∈ Rd is a vector with the hth entry being ∆h = h1 kj=1 θjh −
words, we have
k
k
X
X
µhj , for h = 1, ..., d.
θjh =
j=1

1
h

Pk

h
j=1 µj .

In other

j=1

The equation (17) immediately implies that each θj only takes value in the set {ν1 , ..., νd }.
Therefore, there exists a partition [k] = ∪dh=1 Dh such that Dg ∩ Dh = ∅ for all g 6= h, and
θj = νg for all j ∈ Dg . This leads to
k
X

θjh =

k
X
j=1

|Dg |νgh .

g=1

j=1

We also have

d
X

µhj =

d
X
g=1

|Cg |νgh .

Hence, we obtain the equations
d
X
g=1

|Dg |νgh =

d
X
g=1

|Cg |νgh ,

for h = 0, 1, ..., d − 1.

Pd
Pd
The equation for h = 0 holds because
g=1 |Dg | =
g=1 |Cg | = k. Again, with matrix
notation, these equations can be written as V (ν1 , ..., νd )r = 0, where V (ν1 , ..., νd ) is the
Vandermonde matrix, and r ∈ Rd is a vector with its gth entry being rg = |Dg | − |Cg |. When
ming6=h |νg − νh | > 0 holds, V (ν1 , ..., νd ) has full rank, which leads to |Dg | = |Cg | for all
g = 1, ..., d. Finally, we can conclude that ℓ(θ, µ) = 0. The other direction is obvious.
The above proof actually shows that the function fd is not needed when d ≤ k − 1.
The equation with h = d in (16) is redundant for identifiability. The second conclusion of
9

Proposition 4.1 would still hold without it. However, we still keep it for the convenience of
analyzing the proposed test.
We propose two testing statistics. Define
2

d
k
k
X
X
X
1 
Tf = n
fh (µj ) ,
fh (Xj ) −
|Ch |

and

Tg = n

(18)

j=1

j=1

h=1

k
X

g(Xj ).

(19)

j=1

We present asymptotic distributions of Tf and Tg . Since the case d = 1 is trivial, we only
present results for d ≥ 2.
Condition B. Assume µ1 , ..., µk are k numbers that do not vary with n. Moreover, µj = νh
for all j ∈ Ch , h ∈ [d].
Theorem 4.1. Under Condition B, Tf
under the null hypothesis.

χ2d , Tg

χ2k and Tg − Tf

χ2k−d as n → ∞

Interestingly, Theorem 4.1 exhibits an analysis-of-variance type of result. The statistic
Tg dominates Tf in probability under the null hypothesis. An analogous analysis-of-variance
type of result continuous to hold under a local alternative (see Theorem 9.2). We define the
testing function as
φα = I{Tf > χ2k (α)} ∨ I{Tg > χ2k (α)},
where we use the notation a ∨ b for max(a, b). Since under the null hypothesis, Tg ≥ Tf in
probability, the asymptotic Type-1 error is just the probability of the event {Tg > χ2k (α)},
which tends to α as n → ∞. In fact, as we will show later in Section 6, the behavior of the
testing function mainly depends on the statistic Tg in the contiguous neighborhood of the null
hypothesis. The statistic Tf helps to ensure that the testing function has asymptotic power 1
√
as soon as nℓ(θ, µ) → ∞. Without Tf , the identifiability property of the test established in
Proposition 4.1 would break down, and the test would lose power outside of the contiguous
neighborhood of the null hypothesis. The next theorem rigorously establishes this fact.
Theorem 4.2. Under Condition B, the following two statements are equivalent
√
1. limn→∞ nℓ(θ, µ) = ∞;

2. limn→∞ Pθ Tf > χ2k (α) or Tg > χ2k (α) = 1, for any constant α ∈ (0, 1),

where the probability Pθ denotes N (θ, n−1 Ik ).

10

5

The Case of Categorical Distribution

Now we are ready to transfer our wisdom from Gaussian distribution to categorical distribution. Consider i.i.d. observations X1 , ..., Xn from a categorical distribution (p1 , ..., pk ). To
be specific, for each i ∈ [n] and j ∈ [k], P(Xi = j) = pj . Throughout this section, we use
Pp to denote the probability distribution of X1 , ..., Xn . We would like to test whether the k
numbers p1 , ..., pk are identical to q1 , ...qk after a permutation of labels. Introduce a distance
between the two vectors p and q,
v
u k
uX √
p
ℓ(p, q) = min 2t ( pj − qπ(j))2 .
(20)
π∈Sk

j=1

The hypothesis testing problem is

H0 : ℓ(p, q) = 0,
For each j ∈ [k], define

H1 : ℓ(p, q) > 0.

n

p̂j =

1X
I{Xi = j}.
n
i=1

P
(p̂ −q )2
Pearson’s chi-squared test [12] is defined as χ2 = n kj=1 j qj j , which is asymptotically
distributed as χ2k−1 when p = q. However, this test only works when the null hypothesis is
simple. Here, our null hypothesis is composite, and there is uncertainty from the underlying
permutation of the labels.
Our idea is to borrow the solution for the Gaussian case in Section 3. Intuitively, the vector
(p̂1 , ..., p̂k ) is asymptotically Gaussian after some normalization. However, the normalization
step brings extra difficulty for this problem. In the definition of Pearson’s chi-squared test,
√
each p̂j is normalized by qj because of the heteroskedasticity and dependence structure of
the vector (p̂1 , ..., p̂k ). This normalization does not work in our setting because the underlying
√
label is not given, and we do not know which qj to use. To overcome this issue, we adopt
p
the technique of variance-stabilizing transformation [3], and directly work with p̂j .
This leads to a modification of the definition of the function fl (·), and the new definition
is given by
√
RQ
√
j∈[k]\{l} ( t − qj )
fl (t) = Q
, l = 1, ..., k.
(21)
√
√
j∈[k]\{l} ( ql − qj )
The testing statistic is

T = 4n

k
X
l=1

2

k
k
X
X

fl (qj ) .
fl (p̂j ) −

(22)

j=1

j=1

Similar to the discussion in Section 3, when the value of T is large, the equations (9) are
unlikely to hold. Thus, the null hypothesis will be rejected when T exceeds some threshold.
The asymptotic distribution of T can be derived under the null hypothesis.
11

Condition C. Assume q1 , ..., qk are k different numbers in (0, 1) that do not vary with n.
Some possible extensions beyond Condition C will be discussed in Section 6.
Theorem 5.1. Under Condition C, T

χ2k−1 as n → ∞ under the null hypothesis.

For a chi-squared random variable χ2k−1 , define a number χ2k−1 (α) such that

Then, a testing function is


P χ2k−1 ≤ χ2k−1 (α) = 1 − α.

φα = I T > χ2k−1 (α) .

By Theorem 5.1, its asymptotic Type-1 error is α. The next result characterizes the regime
where the asymptotic power of the test tends to 1. It is a consequence of the fact that the
functions f1 , ..., fk satisfy the identifiability condition, though with slightly different definitions.
Theorem 5.2. Under Condition C, the following two statements are equivalent
√
1. limn→∞ nℓ(p, q) = ∞;

2. limn→∞ Pp T > χ2k−1 (α) = 1, for any constant α ∈ (0, 1),

where the probability Pp is defined in the beginning of this section.

Next, we study the degenerate case where the k numbers q1 , ..., qk only take d values.
There is a partition [k] = ∪dh=1 Ch such that for any g 6= h, Cg ∩ Ch = ∅. We assume the
following condition.
Condition D. Asume q1 , ..., qk are k numbers in (0, 1) that do not vary with n. Moreover,
qj = rh for all j ∈ Ch , h ∈ [d].
The approach we take is similar to that in Section 4, assisted with the technique of
variance-stabilizing transformation. Define
√
RQ
√
g∈[d]\{h} ( t − rg )
fh (t) = Q
, h = 1, ..., d,
(23)
√
√
g∈[d]\{h} ( rh − rg )
and

√

√ 2
rg )
g(t) = Pd Q
√
√ 2.
g=1
h∈[d]\{g} ( t − rh )
Qd

g=1 (

t−

(24)

Then, define the testing statistics

2

d
k
k
X
X
1 X
Tf = 4n
fh (qj ) ,
fh (p̂j ) −
|Ch |
h=1

j=1

12

j=1

(25)

and
Tg = 4n

k
X

g(p̂j ).

(26)

j=1

The properties of Tf and Tg are given by the following theorem. Again, the case d = 1 is
trivial, and we only present results for d ≥ 2.
Theorem 5.3. Under Condition D, Tg
under the null hypothesis.

χ2k−1 , Tf

χ2d−1 and Tg − Tf

χ2k−d as n → ∞

We define the testing function
φα = I{Tf > χ2k−1 (α)} ∨ I{Tg > χ2k−1 (α)}.
By Theorem 5.3, the Type-1 error of this test converges to α. Though Tf is dominated
by Tg under the null hypothesis, both are needed to ensure the power goes to 1 under the
alternative.
Theorem 5.4. Under Condition D, the following two statements are equivalent
√
1. limn→∞ nℓ(p, q) = ∞;

2. limn→∞ Pp Tf > χ2k−1 (α) or Tg > χ2k−1 (α) = 1, for any constant α ∈ (0, 1),

where the probability Pp is defined in the beginning of this section.

6

Optimality of the Test

In this section, we study the optimality issue of the testing problem from a decision-theoretic
perspective. The goal is to understand the fundamental limit of the problem and establish
optimality results of the proposed testing procedures. We propose to study the setting
where a null hypothesis is tested against a local alternative. This leads to a nontrivial
power function and a precise asymptotic characterization of the minimax risk of the test.
Depending on whether the data generating process is Gaussian or categorical, and whether
the null hypothesis is degenerate or not, the optimality of the test will be studied in four
different cases.

6.1

Gaussian Distribution: Non-Degenerate Case

We first consider the non-degenerate situation. That is, we assume that µ1 , ..., µk are k
different numbers. In Section 3, we impose the assumption that the k numbers µ1 , ..., µk do
not depend on n. This assumption can be made significantly weaker. For two indices j and
l that are not equal, define
Y
1
µl − µh
ηjl =
.
µj − µl
µj − µh
h∈[k]\{j,l}

It characterizes the relative difference between µj and µl in the background of the set
{µ1 , ..., µk }.
13

Condition M1. Assume limn→∞ maxj6=l

|ηjl |
√
n

= 0.

To understand Condition M1, we can interpret |ηjl | + |ηlj | as approximately the inverse
distance between µj and µl . Therefore, we allow the possibility that |µj − µl | converges to 0,
but not as fast as n−1/2 . Otherwise, the data cannot tell the difference between µj 6= µl and
µj = µl , which is equivalent to the degenerate case. Recall that the number k is assumed to
be a constant that does not vary with n throughout the paper.
Consider the testing problem


δ
H0 : θ ∈ Θ0 = {θ : ℓ(θ, µ) = 0} , H1 : θ ∈ Θδ = θ : ℓ(θ, µ) = √
.
(27)
n
That is, we test the null hypothesis against its contiguous alternative. The choice of H1
ensures a non-trivial asymptotic power. We measure the testing error via the minimax risk
function
)
(
Rn (k, δ) = inf

0≤φ≤1

sup Pθ φ + sup Pθ (1 − φ) .
θ∈Θδ

θ∈Θ0

The probability symbol Pθ stands for N (θ, n−1 Ik ). Throughout the paper, we assume k and
δ are fixed constants independent of n.
We first present the lower bound.
Theorem 6.1. Under Condition M1, for sufficiently large n, we have



Rn (k, δ) ≥ inf P χ2k > t + P(χ2k,δ2 ≤ t) .
t>0

Theorem 6.1 gives the benchmark of the problem. Using the proposed testing statistic T
defined in (12), we can achieve this benchmark.
Theorem 6.2. Consider the testing procedure φ = I{T > t∗ }, where T is defined in (12),
and



t∗ = argmin P χ2k > t + P(χ2k,δ2 ≤ t) .
t>0

Under Condition M1, we have




sup Pθ φ + sup Pθ (1 − φ) ≤ (1 + o(1)) inf P χ2k > t + P(χ2k,δ2 ≤ t) ,

θ∈Θ0

as n → ∞.

t>0

θ∈Θδ

Theorem 6.2 characterizes both Type-1 and Type-2 error of the test φ = I{T > t∗ }.
The conclusion holds for any local alternative with δ ∈ (0, ∞). It complements the result
of Theorem 3.2. Combining Theorem 6.1 and Theorem 6.2, we conclude that the minimax
testing error has the following asymptotic formula



2
2
Rn (k, δ) = (1 + o(1)) inf P χk > t + P(χk,δ2 ≤ t) ,
t>0

and this error can be achieved by the test φ = I{T > t∗ } with some carefully chosen t∗ only
depending on k and δ.
14

6.2

Gaussian Distribution: Degenerate Case

Now we consider situations of degeneracy. In Section 4, it is assumed that µ1 , ..., µk only take
d different values. This assumption can be relaxed. Here, we assume the k numbers µ1 , ..., µk
can be approximately clustered into d groups. Given d different numbers ν1 , ..., νd , for any
pair g 6= h, define
Y
1
νh − νl
η̄gh =
.
(28)
νg − νh
νg − νl
l∈[k]\{g,h}

|η̄

|

Condition M2. Assume limn→∞ maxg6=h √ghn = 0 and there is a partition C1 , ..., Cd of [k],
√
such that lim supn→∞ max1≤g≤d maxj∈Cg n|µj − νg | = 0.
This condition says that µ1 , ..., µk can be approximately clustered into d groups. The
within-group distance is of a smaller order than n−1/2 , and the between-group distance is of
a larger order than n−1/2 .
Consider the same local testing problem (27). The lower bound of the degenerate setting
is given by the following theorem.
Theorem 6.3. Under Condition M2, n → ∞, we have



Rn (k, δ) ≥ (1 + o(1)) inf P χ2k > t + P(χ2k,δ2 ≤ t) .
t>0

This lower bound can be achieved asymptotically using the testing statistics Tf and Tg
defined in (18) and (19).

Theorem 6.4. Consider the testing procedure φ = I{Tf > t∗ } ∨ I{Tg > t∗ }, where Tf and
Tg are defined in (18) and (19), and



t∗ = argmin P χ2k > t + P(χ2k,δ2 ≤ t) .
t>0

Under Condition M2 , we have




sup Pθ φ + sup Pθ (1 − φ) ≤ (1 + o(1)) inf P χ2k > t + P(χ2k,δ2 ≤ t) ,

θ∈Θ0

as n → ∞.

t>0

θ∈Θδ

Theorem 6.4 shows that the test φ = I{Tf > t∗ } ∨ I{Tg > t∗ } achieves the optimal
error asymptotically under a local alternative. As we will show in Theorem 9.2, Tg ≥ Tf
√
in probability under a local alternative that nℓ(θ, µ) = δ ∈ (0, ∞). Therefore, the test
φ = I{Tf > t∗ } ∨ I{Tg > t∗ } is asymptotically equivalent to I{Tg > t∗ }, and the latter only
uses Tg . Though the role of the statistic Tf is negligible for a local alternative, we have
√
already shown in Theorem 4.2 that as soon as nℓ(θ, µ) → ∞, the effect of using Tf starts
to kick in and it is necessary to use both Tf and Tg for the asymptotic power to approach
one.

15

6.3

Categorical Distribution: Non-Degenerate Case

We study the fundamental limit of testing for the categorical distribution. In Section 5, we
assume q1 , ..., qk are k different numbers that do not depend on n. In this section, we consider
a condition that is significantly weaker. Define
√
√
Y
ql − qh
1
ζjl = √
√
√ .
√
qj − ql
qj − qh
h∈[k]\{j,l}

Similar to the definition of ηjl , ζjl characterizes the relative difference between
√
√
in the background of the set { q1 , ..., qk }.
|ζjl |
√
n

Condition M3. Assume limn→∞ maxj6=l

√

qj and

√
ql

= 0 and min1≤j≤k nqj (1 − qj ) → ∞.

Compared with Condition M1, the extra requirement min1≤j≤k nqj (1 − qj ) → ∞ in Condition M3 ensures that each qj is bounded away from 0 and 1 with a gap at least of order
n−1 . If this extra requirement does not hold, qj would be asymptotically equivalent to 0 or
1, which results in a degenerate variance.
Consider the testing problem


δ
.
(29)
H0 : p ∈ P0 = {p : ℓ(p, q) = 0}, H1 : p ∈ Pδ = p : ℓ(p, q) = √
n
Recall that the distance ℓ(·, ·) is defined in (20).
We present the lower bound.
Theorem 6.5. Under Condition M3, as n → ∞, we have
Rn (k, δ) ≥ (1 + o(1)) inf

t>0

P

χ2k−1



>t +

inf

{δ1 ,δ2 :δ12 +δ22 =δ2 }

P(χ2k−1,δ2
1

+

δ22

!

≤ t) .

Theorem 6.5 gives the benchmark of the problem. Using the testing statistic T defined
in (22), we can achieve this benchmark.
Theorem 6.6. Consider the testing procedure φ = I{T > t∗ }, where T is defined in (22),
and
!

t∗ = argmin P χ2k−1 > t +
sup
P(χ2k−1,δ2 + δ22 ≤ t) .
t>0

1

{δ1 ,δ2 :δ12 +δ22 =δ2 }

Under Condition M3, we have

sup Pθ φ+ sup Pθ (1−φ) ≤ (1+o(1)) inf

θ∈P0

t>0

θ∈Pδ

P

χ2k−1

as n → ∞.



>t +

sup
{δ1 ,δ2 :δ12 +δ22 =δ2 }

P(χ2k−1,δ2
1

+

δ22

!

≤ t) ,

The upper bound given by Theorem 6.6 does not exactly match the lower bound given
by Theorem 6.5. The difference lies in the Type-2 error. For the lower bound, we get
inf {δ1 ,δ2 :δ12 +δ22 =δ2 } P(χ2k−1,δ2 +δ22 ≤ t), while for the upper bound, it is sup{δ1 ,δ2 :δ12 +δ22 =δ2 } P(χ2k−1,δ2 +
1

δ22 ≤ t). These two quantities are close, because for any δ1 and δ2 that satisfy δ12 + δ22 = δ2 ,
the expectation of χ2k−1,δ2 + δ22 is always k − 1 + δ2 . Therefore, the test using the statistic T
1
is nearly optimal.
16

1

6.4

Categorical Distribution: Degenerate Case

Finally, we study the categorical distribution with the presence of degeneracy. In Section 5,
we consider the situation where q1 , ..., qk take d different values. Here, we propose a much
weaker condition. Given d different numbers r1 , ..., rd ∈ (0, 1), for any pair g 6= h, define
√
√
Y
rh − rl
1
.
ζ̄gh = √
√
√
√
rg − rh
rg − rl
l∈[k]\{g,h}

|ζ̄ |

Condition M4. Assume limn→∞ maxj6=l √jln = 0, min1≤j≤k nqj (1 − qj ) → ∞, and there is
√ √
√
a partition C1 , ..., Cd of [k], such that lim supn→∞ max1≤g≤d maxj∈Cg n| qj − rg | = 0.
Condition M4 has the same interpretation as Condition M2. The extra requirement
min1≤j≤k nqj (1 − qj ) → ∞ is also needed in Condition M3 to prevent the variance from being
degenerate.
The lower bound of the local testing problem (29) is given by the next theorem.
Theorem 6.7. Under Condition M4, as n → ∞, we have
Rn (k, δ) ≥ (1 + o(1)) inf

t>0

P χ2k−1 > t +


inf

{δ1 ,δ2 :δ12 +δ22 =δ2 }

!

P(χ2k−1,δ2 + δ22 ≤ t) .
1

For the matching upper bound, we can use the proposed testing statistics Tf and Tg
defined in (25) and (26).
Theorem 6.8. Consider the testing procedure φ = I{Tf > t∗ } ∨ I{Tg > t∗ }, where Tf and
Tg are defined in (25) and (26), and
!

2
2
∗
2
sup
P(χk−1,δ2 + δ2 ≤ t) .
t = argmin P χk−1 > t +
t>0

1

{δ1 ,δ2 :δ12 +δ22 =δ2 }

Under Condition M4, we have
sup Pθ φ+ sup Pθ (1−φ) ≤ (1+o(1)) inf

θ∈P0

θ∈Pδ

t>0

P χ2k−1 > t +


as n → ∞.

7

sup
{δ1 ,δ2 :δ12 +δ22 =δ2 }

!

P(χ2k−1,δ2 + δ22 ≤ t) ,
1

Two-Sample Test

Consider two categorical distributions (p1 , ..., pk ) and (q1 , ..., qk ). Suppose we observe i.i.d.
observations X1 , ..., Xn from (p1 , ..., pk ) and i.i.d. observations Y1 , ..., Ym from (q1 , ..., qk ). We
assume that X1 , ..., Xn are independent of Y1 , ..., Ym . The hypothesis testing problem we
study in this section is
H0 : ℓ(p, q) = 0, H1 : ℓ(p, q) > 0,
17

where the distance ℓ(·, ·) is defined in (20). The two-sample testing problem is harder than
the one-sample version that we have just studied. The major difficulty is that the definitions
of the functions (23) and (24) all depend on the values of (p1 , ..., pk ) and (q1 , ..., qk ) under the
null hypothesis, which is not available anymore in the two-sample scenario.
Our idea is to estimate the unknown (p1 , ..., pk ) and (q1 , ..., qk ) from the data, and then
construct data-driven versions of (23) and (24).
P
For each j ∈ [k], define p̂j = n1 ni=1 I{Xi = j}. Next, we will apply a variable clustering
procedure to (p̂1 , ..., p̂k ). There exists a permutation σ ∈ Sk , such that we can rank the
empirical frequencies as p̂σ(1) ≤ p̂σ(2) ≤ ... ≤ p̂σ(k) . Let ĵ1 be the largest j such that
p
√ p
n| p̂σ(j) − p̂σ(1) | ≤ λn , where λn is some threshold to be specified later. Then, the first
n
o
cluster is defined as C 1 = σ(1), σ(2), ..., σ(ĵ1 ) . Similarly, we can define the second cluster
q
√ p
as C 2 = {σ(ĵ1 + 1), ..., σ(ĵ2 )}, where ĵ2 is the largest j such that n| p̂σ(j) − p̂σ(ĵ1 ) | ≤ λn .
We continue this operation until we obtain a partition C 1 , ..., C d of [k]. Here, d is the number
of clusters estimated from the data. Now, for each g ∈ [d], we find the center of the cluster
p
P
√
by r g = |C1 | j∈C
p̂j . With the numbers r 1 , ..., r d , we define
g

g

√

√
rg )
,
f h (t) = Q
√
√
g∈[d]\{h} ( r h − r g )
RQ

g∈[d]\{h} (

and

t−
√

h = 1, ..., d,

√ 2
rg )
g(t) = Pd Q
√
√ 2.
g=1
h∈[d]\{g} ( t − r h )
Qd

g=1 (

t−

We repeat the above procedure on the observations Y1 , ..., Ym . For each j ∈ [k], define
1 Pm
q̂j = m
on (q̂1 , ..., q̂k ),
i=1 I{Yi = j}. Then, apply the same variable clustering procedure
p
p
1 P
and we obtain a partition C 1 , ..., C d of [k]. For each g ∈ [d], define r g = |C | j∈Cg q̂j .
g
Analogous definitions of f h ’s and g are given by
RQ

f h (t) = Q

and

√

g∈[d]\{h} (

p

rg )
p
√
,
rg )
g∈[d]\{h} ( r h −
Qd

t−

√

h = 1, ..., d,

rg )2
√
Q
√ 2.
(
t
−
rh)
g=1
h∈[d]\{g}

g(t) = P
d

g=1 (

t−

p

Now we can define testing statistics for this problem:

Tf

2

d
k
k
X
2nm X 1 X
=
f h (q̂j )
f h (p̂j ) −
n+m
|C h |
j=1
j=1
h=1

2
k
k
d
X
2nm X 1 X
f h (p̂j ) −
f h (q̂j ) ,
+
n+m
|C
|
h
j=1
j=1
h=1
18

(30)

and



k
k
X
X
2nm 
g(q̂j ) +
Tg =
g(p̂j ) .
n+m
j=1

(31)

j=1

The asymptotic distributions of the testing statistics under the null distribution are given
below.
Condition E. Asume q1 , ..., qk are k numbers in (0, 1) that do not vary with n. Moreover,
there exists a d ≥ 2 and a partition [k] = ∪dh=1 Ch , such that qj = rh for all j ∈ Ch , h ∈ [d].
√
Theorem 7.1. Assume λn is a diverging sequence that satisfies λn = o( n) and we also
m
→ β ∈ (0, 1). Under Condition E, we have
assume n+m
Tg
Tf
Tg − Tf

1
βX1 +
2
X3 ,
1
βX1 +
2

1
(1 − β)X2 + X3 ,
2
1
(1 − β)X2 ,
2

as n → ∞ under the null hypothesis, where X1 , X2 and X3 are independent random variables
distributed as χ2k−d , χ2k−d and χ2d−1 , respectively.

Let X (α) be the number that satisfies P 21 βX1 + 12 (1 − β)X2 + X3 > X (α) = α. We
define the testing function as
φα = I{Tf > X (α)} ∨ I{Tg > X (α)}.
Theorem 7.1 implies that this test has asymptotic Type-1 error α. The next result characterizes the power behavior of the test.
√
Theorem 7.2. Assume λn is a diverging sequence that satisfies λn = o( n) and we also
m
assume n+m
→ β ∈ (0, 1). Under Condition E, the following two statements are equivalent
√
1. limn→∞ nℓ(p, q) = ∞;
2. limn→∞ Pp,q (Tf > X (α) or Tg > X (α)) = 1, for any constant α ∈ (0, 1),
where the probability Pp,q stands for the joint distribution of X1 , ..., Xn , Y1 , ..., Ym .
Theorem 7.2 assumes Condition E. That is, q1 , ..., qk are fixed numbers do that depend
on n, and p1 , ..., pk are allowed to vary with n. One can also assume an analogous condition
for p1 , ..., pk as fixed numbers that satisfy Condition E, and allow q1 , ..., qk to vary with n.

8

Discussion

The testing procedures that we propose and analyze in this paper critically depend on the
structure of null hypothesis. In Section 3, the mean vector (µ1 , ..., µk )T is assumed to consist
19

of k distinct numbers, and the testing statistic is constructed based on the functions f1 , ..., fk
defined in (10). In Section 4, we assume (µ1 , ..., µk )T consists of k numbers that take values
in {ν1 , ..., νd } for some d ≤ k. For this degenerate setting, we use the functions f1 , ..., fd and
g defined in (14) and (15) to construct the testing statistics.
Much weaker assumptions are considered in Section 6. In Section 6.1, we allow |µj − µl |
to converge to 0, but require the difference should be of a larger order than n−1/2 for every
j 6= l. This extends the assumption in Section 3 that µ1 , ..., µk are k distinct numbers that
do not vary with n. In Section 6.2, we consider the setting where |νg − νh | is of a larger order
than n−1/2 for every g 6= h, and |µj − νh | is of a smaller order than n−1/2 for every j ∈ Ch .
This setting extends the assumption used in Section 4. It turns out that the asymptotic
distributions of the proposed testing statistics (Theorem 3.1 and Theorem 4.1) are still valid
under these more general conditions (see Theorem 9.1 and Theorem 9.2 in Section 9.1).
However, the conditions in Section 6.1 and Section 6.2 still do not cover all situations. By
requiring the within-cluster distance to be of a smaller order than n−1/2 and the betweencluster distance to be of a larger order than n−1/2 , the numbers µ1 , ..., µk enjoy an approxi√
mately exact clustering structure, because for each j 6= l, we either have n|µj − µl | → 0 or
√
n|µj − µl | → ∞, depending on whether j and l are in the same cluster or not. A possible
√
situation n|µj − µl | ≍ 1 is excluded.
In this section, we discuss a situation where the clustering structure of the numbers
P
µ1 , ..., µk is ambiguous. Consider a partition C1 , ..., Cd of [k]. Define νh = |C1h | j∈Cg µj .
Instead of assuming the within-cluster distance is of a smaller order than n−1/2 , we consider
P
P
the situation where n dh=1 j∈Ch (µj − νh )2 is of a constant order. Moreover, we also assume
the between-cluster distance |νg − νh | is of a larger order than n−1/2 for every g 6= h. This
is without loss of generality, because if there is some g 6= h, such that |νg − νh | = O(n−1/2 ),
then Cg and Ch can be combined into a single cluster. Recall the definition of η̄gh in (28), we
formalize this ambiguous clustering structure into the following condition.
Condition M2’. For the partition C1 , ..., Cd and clustering centers ν1 , ..., νd defined above,
P
P
|η̄ |
assume limn→∞ maxg6=h √ghn = 0, and τ 2 = limn→∞ n dh=1 j∈Ch (µj − νh )2 ∈ [0, ∞).

Note that Condition M2 is a special case of Condition M2’ when τ 2 = 0. The next
theorem gives the asymptotic distribution of the testing statistics Tf and Tg defined in (18)
and (19) under the null hypothesis.
Theorem 8.1. Assume Condition M2’ holds. Then we have Tg
χ2k,τ 2 , Tf
Tg − Tf
χ2k−d,τ 2 as n → ∞ under the null hypothesis X ∼ N (µ, n−1 Ik ).

χ2d and

It is interesting to see that the asymptotic distribution of Tg is a noncentral chi-squared
distribution even under the null hypothesis. The noncentrality parameter τ 2 characterizes
the within-cluster distance of µ1 , ..., µk with respect to the partition C1 , ..., Cd . Theorem 8.1
is reduced to Theorem 4.1 when τ 2 = 0.
Define a number χ2k,τ 2 (α) that satisfies P(χ2k,τ 2 ≤ χ2k,τ 2 (α)) = 1 − α. Then, an α-level
testing function is φα = I{Tg > χ2k,τ 2 (α)} ∨ I{Tf > χ2k,τ 2 (α)}. Compared with the null
20

hypothesis where τ 2 = 0, a nonzero τ 2 requires a higher rejection level. This means the
test will have less power under a contiguous alternative, compared with the situation where
P
P
τ 2 = 0. Suppose τ̃ 2 = limn→∞ n dh=1 j∈Ch (θj − νh )2 ∈ (0, ∞). Then, one can also show
that Tg
χ2k,τ̃ 2 under the alternative X ∼ N (θ, n−1 Ik ). Therefore, the test φα starts to have
power when τ̃ 2 exceeds τ 2 . When τ̃ 2 is close to or even smaller then τ 2 , this test will not
have any power under the alternative. On the other hand, outside of the contiguous regime
√
where nℓ(θ, µ) → ∞, we must have τ̃ 2 = ∞, and then the test will have asymptotic power
1.
From what we have just discussed, we can see that the structure of µ1 , ..., µk plays a critical role on the solution of the problem. The discussion also applies to the case of categorical
distributions and we can obtain similar conclusions there. Theorem 8.1 characterizes the
asymptotic distribution of the testing statistics when µ1 , ..., µk exhibit an ambiguous clustering structure, right on the edge of degeneracy. This results in a non-trivial behavior of
the power function. Exact characterization of optimality of the testing problem (as what we
have done in Section 6) on the edge of degeneracy remains open, and we shall consider this
problem as a future project.

9

Proofs

In this section, we present the proofs of all results in the paper. In Section 9.1, we derive the
asymptotic distributions of the proposed testing statistics in various settings. These results
are used to derive Theorem 3.1, Theorem 4.1, Theorem 5.1, Theorem 5.3, Theorem 7.1 and
Theorem 8.1. Then, in Section 9.2, we analyze the powers of the proposed tests, which
include the proofs of Theorem 3.2, Theorem 4.2, Theorem 5.2, Theorem 5.4 and Theorem
7.2. Finally, in Section 9.3, we give proofs of all results in Section 6.

9.1

Asymptotic Distribution of the Testing Statistics

We first present and prove four theorems of the proposed testing statistics in various settings.
Theorem 9.1. In addition to Condition M1, assume
√
lim nℓ(θ, µ) = δ ∈ [0, ∞).
n→∞

Then, as n tends to infinity, T

χ2k,δ2 .

Proof. We first calculate the derivatives of fl (t). The first derivative is
Q
j∈[k]\{l} (t − µj )
′
.
fl (t) = Q
j∈[k]\{l} (µl − µj )

Therefore, fl′ (µl ) = 1. For any j 6= l, we give a bound for sup|t−µj |≤n−1/2 ǫ |fl′ (t)|. The
following inequality is useful.


Y
Y
1
µ
−
µ
2
µ
−
µ
j 
j
h
l

|ηlh | + |ηhl | =
+
≥
.
(32)
|µl − µh |
µh − µj
µl − µj
|µl − µh |
j∈[k]\{l,h}

j∈[k]\{l,h}

21

Note that
|fl′ (t)| =

|t − µj |
|µl − µj |

Y

h∈[k]\{l,j}

t − µh
µl − µh

=

|t − µj |
|µl − µj |

Y



h∈[k]\{l,j}



t − µj
µj − µh
+
µl − µh
µl − µh












t − µj
µj − µh 
|t − µj | k−2 
2
+
|µl − µj |
µl − µh
µl − µh
h∈[k]\{l,j}
h∈[k]\{l,j}
 Y 


|ηlh | + |ηhl |
k−2
k−1 |ηlj | + |ηjl |
+ 2k−2 |t − µj ||ηlj |.
≤ 2 |t − µj |
2
2
≤

Y

Y

h∈[k]\{l,j}

Therefore, we have the bound
κ1 (ǫ) = max

sup

j6=l |t−µ |≤n−1/2 ǫ
j

"

|fl′ (t)| ≤ 2k−2 max
j6=l



ǫ|ηjl |
√
n

k−2

+ max
j6=l



ǫ|ηjl |
√
n

#

The above bound is useful for k ≥ 3. For k = 2, it is easy to see


ǫ|ηjl |
′
√
.
κ1 (ǫ) = max
sup
|fl (t)| ≤ max
j6=l |t−µ |≤n−1/2 ǫ
j6=l
n
j

.

(33)

(34)

The second derivative of fl (t) is
X

fl′′ (t) =

j∈[k]\{l}

1
(µl − µj )

Y

h∈[k]\{l,j}

t − µh
.
µl − µh

We give a bound for sup|t−µl |≤n−1/2 ǫ |fl′′ (t)|. Similar calculation gives
κ2 (ǫ) = max

sup

1≤l≤k |t−µ |≤n−1/2 ǫ
l

|fl′′ (t)|



ǫ|ηjl |
≤ k max |ηjl | max 1 + √
j6=l
j6=l
n

k−2

.

(35)

Now we are ready to derive the asymptotic distribution of T . We write the observation as
√
Xj = θj + n−1/2 Zj , with Zj ∼ N (0, 1) independently. The condition limn→∞ nℓ(θ, µ) = δ
implies that there is some n0 , such that for any n > n0 , we have
nℓ2 (θ, µ) ≤ Cn δ2 ,
where Cn is an sequence that tends to infinity arbitrarily slowly. In particular, we require
3/2

Cn

that Cn satisfies Cn → ∞ and
is guaranteed by the assumption
depending on n, such that

maxj6=l |ηjl |
√
n
maxj6=l |ηjl |
√
→
n

→ 0. The existence of such sequence Cn
0. Thus, there exists a π ∈ Sk , possibly

max (θj − µπ(j) )2 ≤

1≤j≤k

22

Cn δ 2
.
n

Since k does not depend on n, max1≤j≤k Zj2 ≤ Cn with probability that goes to 1. By triangle
inequality,
√
√
Cn (1 + δ2 )
√
,
(36)
max |Xj − µπ(j) | ≤
1≤j≤k
n
with probability that goes to 1. We use Taylor expansion. For j such that π(j) = l, we have
1
fl (Xj ) − fl (µπ(j) ) = (Xj − µπ(j) ) + fl′′ (ξjl )(Xj − µπ(j) )2 ,
2
where we have used the fact that fl′ (µl ) = 1. For j such that π(j) 6= l, we have
fl (Xj ) − fl (µπ(j) ) = fl′ (ξjl )(Xj − µπ(j) ).
Therefore,
k
X
j=1

≤

fl (Xj ) −

k
X
j=1

fl (µj ) − (Xπ−1 (l) − µl )

1 ′′
|f (ξ −1 )|(Xπ−1 (l) − µl )2 +
2 l π (l)l

X

j6=π −1 (l)

|fl′ (ξjl )||Xj − µπ(j) |.

The number ξjl is between Xj and µπ(j) , which implies
√
√
Cn (1 + δ2 )
√
.
max |ξjl − µπ(j) | ≤ max |Xj − µπ(j) | ≤
j,l
1≤j≤k
n

(37)

Using the bounds (33), (34), (35), (36) and (37), we have
k
X
j=1

fl (Xj ) −

k
X
j=1

fl (µj ) − (Xπ−1 (l) − µl )

√
√ 
1 Cn (1 + δ2 )2 p
≤
κ2
Cn (1 + δ2 )
2
n
√
√
p
√  Cn (1 + δ2 )
2
√
.
+(k − 1)κ1
Cn (1 + δ )
n

23

(38)

Therefore,
T −n
≤ n



l=1

k
X
l=1

+n

l=1



k
X

≤ 2n

k
X
(Xπ−1 (l) − µl )2
k
X
j=1

fl (Xj ) −

|Xπ−1 (l) − µl |

k
k X
X
l=1 j=1

fl (Xj ) −

k
X
j=1

2

fl (µj ) − (Xπ−1 (l) − µl )2
k
X

k
X

fl (Xj ) −

k
X

fl (µj ) − (Xπ−1 (l) − µl )

j=1

j=1

j=1

fl (µj ) − (Xπ−1 (l) − µl )
2

k
k
X
X
√
√ p
≤ 2k n Cn (1 + δ2 )
fl (µj ) − (Xπ−1 (l) − µl )
fl (Xj ) −
j=1

j=1

+kn

k
X
j=1

fl (Xj ) −

By (38), the bound for T − n
it is easy to see that

k
X
j=1

Pk

2

fl (µj ) − (Xπ−1 (l) − µl ) .

l=1 (Xπ −1 (l)

− µl )2 is of order

3/2

Cn

maxj6=l |ηjl |
√
n

→ 0. Finally,

k
X
n
(Xπ−1 (l) − µl )2 ∼ χ2k,δn2 ,
l=1

where δn2 = nkθ − µπ k2 → δ2 . Therefore, T converges to χ2k,δ2 in distribution.
Theorem 9.2. In addition to Condition M2, assume
lim

n→∞

√
nℓ(θ, µ) = δ ∈ [0, ∞).

Then, as n tends to infinity, Tg
χ2k,δ2 , and Tg ≥ Tf in probability. Moreover, if δ2 = 0, we
χ2k−d .
χ2d and Tg − Tf
have Tg
χ2k , Tf
Proof. The case d = 1 is obvious. We only prove the case d ≥ 2. Similar to the inequality
2
(32), we have |η̄gh | + |η̄hg | ≥ |νg −ν
. By Condition M2, we have
h|
max1≤g≤d maxj∈Cg |µj − νg |
= o(1).
ming6=h |νg − νh |
The observation is Xj = θj + n−1/2 Zj with Zj ∼ N (0, 1) independently. Use the notation
√
L = max1≤g≤d maxj∈Cg n|µj − νg | = o(1). Under the assumption of the theorem, there

exists a sequence Cn that satisfies Cn → ∞, Cn2 L → 0 and
24

3/2

Cn

maxg6=h |η̄gh |
√
n

→ 0, such that

max1≤j≤k Zj2 ≤ Cn with probability tending to 1. Similar to the bound (36), the assumption
√
limn→∞ nℓ(θ, µ) = δ < ∞ implies the existence of π ∈ Sk such that
√
√
Cn (1 + δ2 )
√
.
max |Xj − µπ(j) | ≤
1≤j≤k
n
We first study the asymptotic distribution of Tg . Note that
max max |Xπ−1 (j) − νg | ≤

√

1≤g≤d j∈Cg

√
Cn (1 + δ2 ) + L
√
.
n

(39)

Together with Condition M2 and the choice of Cn , we can immediately deduce
√
√
max1≤g≤d maxj∈Cg |Xπ−1 (j) − νg |
Cn (1 + δ2 ) + L
√
≤ max |η̄gh |
= o(1).
g6=h
ming6=h |νg − νh |
n
The function g(t) can be written as
d

X
1
1
=
.
g(t)
(t − νg )2
g=1

For each j ∈ Cg , we have
(Xπ−1 (j) − νg )2
=1+
g(Xπ−1 (j) )

X

h∈[d]\{g}

(Xπ−1 (j) − νg )2
.
(Xπ−1 (j) − νh )2

Thus,
P

(Xπ−1 (j) −νg )2
h∈[d]\{g} (Xπ−1 (j) −νh )2

g(Xπ−1 (j) )
−1 ≤
P
(Xπ−1 (j) − νg )2
1 + h∈[d]\{g}

)2

(Xπ−1 (j) −νg
(Xπ−1 (j) −νh )2

≤

X

h∈[d]\{g}

(Xπ−1 (j) − νg )2
,
(Xπ−1 (j) − νh )2

where the bound on the right hand side above can be bounded by
√
√
X
2(Xπ−1 (j) − νg )2
Cn (1 + δ2 ) + L
√
≤ 4d max |η̄gh |
.
g6=h
(νg − νh )2 − 2(Xπ−1 (j) − νh )2
n
h∈[d]\{g}

Together with (39), we have
|g(Xπ−1 (j) ) − (Xπ−1 (j) − νg )2 |
g(Xπ−1 (j) )
−1
(Xπ−1 (j) − νg )2
!3
√
√
Cn (1 + δ2 ) + L
√
.
n

= (Xπ−1 (j) − νg )2
≤ 4d max |η̄gh |
g6=h

25

(40)

Therefore
Tg − n
≤ n

d
X

d X
X

h=1 j∈Ch

X

h=1 j∈Ch

(Xπ−1 (j) − νh )2

g(Xπ−1 (j) ) − (Xπ−1 (j) − νg )2

≤ 4kd max |η̄gh |
g6=h

√

3
√
Cn (1 + δ2 ) + L
√
= o(1).
n

(41)

For each j ∈ Ch ,
n|(Xπ−1 (j) − νh )2 − (Xπ−1 (j) − µj )2 |

≤ n|νh − µj ||Xπ−1 (j) − νh + Xπ−1 (j) − µj |
 p

√
≤ L 2 Cn (1 + δ2 ) + L = o(1).

Thus,

Tg − n

d X
X

h=1 j∈Ch

(Xπ−1 (j) − µj )2

(42)

has a bound that tends to 0. Observe that
n

d X
X

h=1 j∈Ch

where
δn2

(Xπ−1 (j) − µj )2 ∼ χ2k,δn2 ,

k
X
(θj − µπ(j) )2
=n

δ2 .

j=1

Thus, Tg
χ2k,δ2 .
Next we derive the asymptotic distribution of Tf . Similar to (33), (34) and (35), we also
have
"


d−2
#
ǫ|η̄
|
ǫ|η̄
|
gh
gh
κ1 (ǫ) = max
sup
|fh′ (t)| ≤ 2d−2 max √
+ max √
,
(43)
g6=h |t−ν |≤n−1/2 ǫ
g6=h
g6=h
n
n
g
for d ≥ 3,
κ1 (ǫ) = max

sup

g6=h |t−ν |≤n−1/2 ǫ
g

|fh′ (t)|

≤ max
g6=h



ǫ|η̄gh |
√
n



,

(44)

for d = 2, and
κ2 (ǫ) = max

sup

1≤h≤d |t−ν |≤n−1/2 ǫ
h

|fh′′ (t)|



ǫ|η̄gh |
≤ d max |η̄gh | max 1 + √
g6=h
g6=h
n
26

d−2

.

(45)

For any j ∈ Cg ,
fg (Xπ−1 (j) ) − fg (µj )

= fg (Xπ−1 (j) ) − fg (νg ) + fg (νg ) − fg (µj )
1
1
= fg′ (νg )(Xπ−1 (j) − µj ) + fg′′ (ξjg )(Xπ−1 (j) − νg )2 − fg′′ (ξ̄jg )(µj − νg )2 .
2
2
For any j ∈ Ch with any h 6= g,
fg (Xπ−1 (j) ) − fg (µj ) = fg′ (ξ̃jg )(Xπ−1 (j) − µj ).
By the fact that fg′ (νg ) = 1, we have
k
X
j=1

≤

fg (Xj ) −

k
X
j=1

fg (µj ) −

X

j∈Cg

(Xπ−1 (j) − µj )

1 X ′′
1 X ′′
|fg (ξjg )|(Xπ−1 (j) − νg )2 +
|fg (ξ̄jg )|(µj − νg )2
2
2
j∈Cg
j∈Cg
X X
′
|fg (ξ̃jg )||Xπ−1 (j) − µj |.

h∈[d]\{g} j∈Ch

The number ξjg is between Xπ−1 (j) and νg , the number ξ̄jg is between µj and νg , and the
number ξ̃jg is between Xπ−1 (j) and µj . Thus,
√
√
Cn (1 + δ2 ) + L
√
|ξjg − νg | ≤ |Xπ−1 (j) − νg | ≤
,
n
L
|ξ̄jg − νg | ≤ |µj − νg | ≤ √ ,
n
and

√
√
Cn (1 + δ2 )
√
|ξ̃jg − µj | ≤ |Xπ−1 (j) − µj | ≤
.
n

Using the bounds (43), (44) and (45), we can deduce
k
X
j=1

fg (Xj ) −

k
X
j=1

fg (µj ) −

X

j∈Cg

(Xπ−1 (j) − µj )

√
√

√
( Cn (1 + δ2 ) + L)2 p
Cn (1 + δ2 ) + L
≤ k
κ2
n
√
√
p
√  Cn (1 + δ2 )
√
Cn (1 + δ2 )
+kκ1
.
n

Similar to the proof of Theorem (32), we can show that
2

d
X
1 X
(Xπ−1 (j) − µj )
Tf − n
|Ch |
h=1

j∈Ch

27

(46)

3/2

has a bound of order

Cn

maxj6=l |ηjl |
√
n

→ 0. Note that when δ2 = 0,


2
d
X
X
1 
n
(Xπ−1 (j) − µj ) ∼ χ2d .
|Ch |
j∈Ch

h=1

Thus, Tf
χ2d .
Finally, we derive the asymptotic distribution for Tg − Tf . The bounds for (42) and (46)
imply that

Tg − Tf − n

d X
X

h=1 j∈Ch

2

d
X
X
1 
(Xπ−1 (j) − µj )
(Xπ−1 (j) − µj )2 + n
|Ch |
h=1

j∈Ch

has a bound that tends to zero. Thus, the asymptotic distribution of Tg − Tf is the same as
that of
2

d
d X
X
X
X
1 
(Xπ−1 (j) − µj )2 − n
n
(Xπ−1 (j) − µj )
|Ch |
h=1
h=1 j∈Ch
j∈Ch


2
d X
X
X
X
1
1
Xπ−1 (j) −
= n
Xπ−1 (j) − µj −
µj   ,
|Ch |
|Ch |
h=1 j∈Ch

j∈Ch

which is χ2k−d when δ2 = 0. Therefore, Tg − Tf
can still claim Tg ≥ Tf in probability.

j∈Ch

χ2k−d . Without the condition δ2 = 0, we

√
√
Theorem 9.3. For π = argminπ∈Sk k p − qπ k, define
δ12 = 4n

k
2
√
X
p
pl − qπ(l) ,
(1 − pl )

(47)

l=1

and
δ22 = 4n

k
X
l=1

lim supn→∞ (δ12 + δ22 )

Assume
to infinity.

pl

√
2
p
pl − qπ(l) .

< ∞. Then, under Condition M3, T − δ22

(48)
χ2k−1,δ2 , as n tends
1

Proof. The proof is almost the same as that of Theorem 9.1, and therefore we will omit some
√ √ √ p
overlapping details. Largely speaking, we can replace the t, µj , θj , Xj by t, qj , pj , p̂j ,
and most parts in the proof of Theorem 9.1 will go through. Here are a few different details.
p
√ p
√
√
We write p̂j = pj + n−1/2 Zj /2, with Zj = 2 n( p̂j − pj ). Condition M3 implies that
max1≤j≤k Zj2 = OP (1). Thus, the inequality (36) in the proof of Theorem 9.1 can be replaced

28

p
√
by max1≤j≤k | p̂j − qπ(j) | ≤
of Theorem 9.1, we have

√

√
Cn (1+ δ2 )
√
.
n

Then, following the same argument in the proof

k p
X
p
( p̂l − qπ(l) )2 = oP (1),
T − 4n
l=1

P
√
√
and it is sufficient to study the asymptotic distribution of 4n kl=1 ( p̂l − qπ(l) )2 . Let ∆ be a
√
P
√ √
√
√
vector with the lth entry being 2 n( p̂l − qπ(l) ). Then, we have 4n kl=1 ( p̂l − qπ(l) )2 =
√
√
kZ +∆k2 . Under Condition M3, Z
N (0, Ik − p pT ) by Lindeberg’s central limit theorem
together with an argument of delta’s method. Therefore, there exists a random vector W
√ √
that satisfies W
N (0, Ik ) and Z = (Ik − p pT )W . This gives
√ √ T
√ √
√ √
p p )W + (Ik − p pT )∆ + p pT ∆k2
√ √
√ √
√ √
= k(Ik − p pT )W + (Ik − p pT )∆k2 + k p pT ∆k2 ,

kZ + ∆k2 = k(Ik −
where k(Ik −

√ √ T
√ √
p p )W + (Ik − p pT )∆k2

√ √
χ2k−1,δ2 and k p pT ∆k2 = δ22 .
1

√
√
Theorem 9.4. For π = argminπ∈Sk k p − qπ k, define
δ12 = 4n

k
√
2
X
p
(1 − pl )
pl − qπ(l) ,
l=1

and
δ22

= 4n

k
X
l=1

Assume

lim supn→∞ (δ12 +δ22 )

pl

2
√
p
pl − qπ(l) .

< ∞. Then, under Condition M4, Tg −δ22

χ2k−1,δ2 , as n tends
1

to infinity. Moreover, Tg ≥ Tf in probability. Furthermore, when δ12 + δ22 = 0, Tg
χ2k−d .
Tf
χ2d−1 and Tg − Tf

χ2k−1 ,

Proof. The proof is largely the same as that of Theorem 9.3. We only need to replace the
√ √ √ √ p
t, µj , θj , νh , Xj in the proof of Theorem 9.3 by t, qj , pj , rh , p̂j . Then, by the same
argument, we have
d X q
X
√
( p̂π−1 (j) − qj )2 = oP (1),
Tg − 4n
h=1 j∈Ch

and
2

d
d X q
q
X
X
X
1
√
√

( p̂π−1 (j) − qj )2 + 4n
Tg − Tf − 4n
( p̂π−1 (j) − qj ) = oP (1).
|Ch |
h=1 j∈Ch

h=1

29

j∈Ch

The same argument in the proof of Theorem 9.3 implies that Tg − δ22
conclusion Tg ≥ Tf in probability can be deduced by

χ2k−1,δ2 . The
1


2
d X q
d
q
X
X
X
1 
√
√
( p̂π−1 (j) − qj )
( p̂π−1 (j) − qj )2 − 4n
4n
|Ch |
j∈Ch
h=1 j∈Ch
h=1
2

d X
q
q
X
X
√
 p̂π−1 (j) − √qj − 1
( p̂π−1 (j) − qj ) ≥ 0.
= 4n
|Ch |
j∈Ch

h=1 j∈Ch

Now we derive the results under the null distribution. Recall the definition of Zj in the
proof of Theorem 9.3. The asymptotic distributions of Tg , Tf and Tg − Tf are the same of
those of
2
2


d
k
d
k
X
X
X
X
X
X
1 
1 
Zj2 ,
Zj  ,
Zj  ,
Zj2 −
|Ch |
|Ch |
j=1

h=1

j=1

j∈Ch

h=1

j∈Ch

respectively under the null hypothesis. According to the argument in the proof of Theorem
P
√ √
9.3, Z = (Ik − q q T )W with W
N (0, Ik ). Therefore, kj=1 Zj2
χ2k−1 .
Define a k × d matrix Q with Qjh = √1 if j ∈ Ch and Qjh = 0 if j ∈
/ Ch . It is easy to
|Ch |

see that QQT is a projection matrix and QT Q = Id . Define a vector γ ∈ Rd whose hth entry
p
√
is γh = |Ch |rh . It is easy to see that γ is a unit vector. Moreover, we have q = Qγ. With
the new notation, we get

2
d
X
X
1 
Zj  = kQT Zk2 .
|Ch |
h=1

The covariance of QT Z is

QT (Ik −
Therefore, kQT Zk2
k
X
j=1

j∈Ch

√ √ T
q q )Q = Id − γγ T .

χ2d−1 . Finally,


2
d
X
X
1

Zj  = kZk2 − kQT Zk2 = Z T (Ik − QQT )Z = W T (Ik − QQT )W.
Zj2 −
|Ch |
h=1

j∈Ch

Therefore, its asymptotic distribution is χ2k−d .

The results of Theorem 3.1, Theorem 4.1, Theorem 5.1 and Theorem 5.3 are special
cases of Theorem 9.1, Theorem 9.2, Theorem 9.3 and Theorem 9.4. Next, we give proofs of
Theorem 7.1 and Theorem 8.1.
Proof of Theorem 7.1. Without loss of generality, we can assume that p1 = q1 ≤ p2 = q2 ≤
... ≤ pk = qk . This is just to simplify the notation. In general, such a rearrangement can
always be done with extra notation of permutations. Then, Cg = {jg +1, jg +2, ..., jg+1 } for g ∈
√ √
√
[d]. According to the assumption, ming6=h minj∈Cg minl∈Ch n| pj − pl | = o(1). Moreover,
30

√ p
√ p
√
√
n| p̂j − pj | = OP (1) and maxj∈[k] m| q̂j − qj | = OP (1).

it is easy to see that maxj∈[k]
This leads to the conclusion


P C g = C g = Cg for all g ∈ [d] and d = d = d → 1,

under Condition E.
From now on, the analysis is on the event {C g = C g = Cg for all g ∈ [d] and d = d = d}.
√ p
√ p
√
√
Define Z j = 2 n( p̂j − pj ) and Z j = 2 m( q̂j − qj ) for j ∈ [k]. The definition implies
that maxj∈[k] |Z j | = OP (1) and maxj∈[k] |Z j | = OP (1). The definitions of r g and r g give
√ p
√ p
1 X
1 X
√
√
2 n( rg − rg ) =
Zj.
Z j and 2 m( r g − rg ) =
|Cg |
|Cg |
j∈Cg

j∈Cg

p
√ p
√ p
√
Given that pj = qj = rg for all j ∈ Cg , we have n| q̂j − rg | = OP (1) and n| p̂j − r g | =
p
p
√
√
OP (1) for all j ∈ Cg . We also have | q̂j − r h |−1 = OP (1) and | p̂j − r h |−1 = OP (1) for
all j ∈ Cg and h 6= g.
We first analyze g(t). By its definition,
d

X
1
1
√
=
.
√
g(t)
( t − r h )2
h=1

Thus, for any j ∈ Cg ,

p
√
( q̂j − rg )2
g(q̂j )

p
√
( q̂j − rg )2
p
=1+
√ 2.
(
q̂
−
rh )
j
h∈[d]\{g}
X

Similar to the argument in (40), we get

p
X ( q̂j − √r g )2
g(q̂j )
−1
p
p
√ 2 = OP (n ).
√ 2 −1 ≤
( q̂j − r g )
( q̂j − r h )
h∈[d]\{g}

With some rearragangements, we get

d
2nm X X p
p
2nm X
g(q̂j ) −
( q̂j − r g )2 = oP (1).
n+m
n+m
g=1 j∈Cg

j∈[k]

A similar argument also gives

d
p
2nm X X p
2nm X
g(p̂j ) −
( p̂j − r g )2 = oP (1).
n+m
n + m g=1
j∈Cg

j∈[k]

Therefore, we obtain the following approximation

2
d X
X
X
1
1
2nm
1
 √
Tg −
Zj − √
Zj
m+n
|Cg |
2
n
2
m
g=1 j∈Cg
j∈Cg
2

d
1 1 X 
2nm X X  1
√ Zj − √
Zj
= oP (1).
−
m+n
2 m
2 n |Cg |
g=1
j∈Cg

j∈Cg

31

Since
2
X
1
1
1
 √
Zj 
Zj − √
2 n
2 m |Cg |
j∈Cg
j∈Cg

2
2

X
X
X
X
1
1
1
1
1
1
1
 √ Zj − √
=
Zj ,
Z j  + |Cg |  √
Zj − √
2 n
2 n |Cg |
2 n |Cg |
2 m |Cg |


X

j∈Cg

j∈Cg

j∈Cg

j∈Cg

and

2
X
1
1
1
 √ Zj − √
Zj
2 m
2 n |Cg |
j∈Cg
j∈Cg

2

2
X
X
X
X
1 1
1
1
1
 √1 Z j − √1
=
Z j  + |Cg |  √
Zj ,
Zj − √
2 m
2 m |Cg |
2 n |Cg |
2 m |Cg |
X



j∈Cg

j∈Cg

j∈Cg

j∈Cg

we have

2
2

d X
X
X
X
n
m
Z j − 1
Z j − 1
Zj
Zj −
Tg −
2(n + m)
|Cg |
2(n + m)
|Cg |
g=1 j∈Cg
g=1 j∈Cg
j∈Cg
j∈Cg

2
r
r

d
X
m
n
1 X

Z −
|Cg |
−
Z j  = oP (1).
(49)
|Cg |
m+n j
m+n
d X
X

g=1



j∈Cg

Next, we analyze f h (t). By its definition,

√
Q
√
df h (t)
g∈[d]\{h} ( t − r g )
√ =Q
√
√ .
d t
g∈[d]\{h} ( r h − r g )

Therefore, we have
max √
g∈[d]

sup
√

√
n| t− rg |≤λn

df g (t)
√ − 1 = oP (1)
d t

and

max

sup
√

g∈[d]\{h} √n| t−√r |≤λ
g
n

df h (t)
√
= oP (1).
d t

Using Taylor expansion, we get
k
X
j=1

f h (p̂j ) −

k
X
j=1

k
X
X p
p
p
p
f h (q̂j ) =
| p̂j − q̂j |.
( p̂j − q̂j ) + oP (1)
j=1

j∈Ch

Then, we have

2

2
d
k
k
d
X
X
X p
p
1
2nm
2nm X 1 X

f h (p̂j ) −
f h (q̂j ) −
( p̂j − q̂j ) = oP (1).
n+m
|Ch |
n+m
|Ch |
h=1

j=1

j=1

h=1

32

j∈Ch

The same argument also leads to


2
2
d
k
d
k
X
X
X
X
X
p
p
1 
1 
2nm
2nm
( p̂j − q̂j ) = oP (1).
f h (p̂j ) −
f h (q̂j ) −
n+m
|Ch |
n+m
|Ch |
j=1

h=1

j=1

h=1

j∈Ch

Hence, we have the following approximation,


r
r
 2
d
X
X
m
n
1
Zj −
|Cg | 
Z j  = oP (1).
Tf −
|C
|
m
+
n
m
+
n
g
g=1

(50)

j∈Cg

√ √
According to the argument in the proof of Theorem 9.3, Z = (Ik − p pT )W with
√ √
W
N (0, Ik ). Similarly, we also have Z = (Ik − q q T )W with W
N (0, Ik ). Note that
W is independent of W . Recall the definition of the matrix Q and the vector γ in the proof
of Theorem 9.4. Then,

2
d X
X
X
1
Z j −
Z j  = Z T (Ik − QQT )Z,
|C
|
g
g=1 j∈Cg
j∈Cg

2
d X
X
X
T
Z j − 1
Z j  = Z (Ik − QQT )Z,
|C
|
g
g=1 j∈Cg
j∈Cg


r
r
 2
 2
r
r
d
X
X
m
n
m
n
1
T


Zj
Z
.
= Q
Z −
Z−
|Cg |
|Cg |
m+n j
m+n
m+n
m+n
g=1
j∈Cg

Furthermore, we have

Z T (Ik − QQT )Z = W T (Ik − QQT )W ,
T

T

Z (Ik − QQT )Z = W (Ik − QQT )W ,
r
r
 2

r
r
m
n
m
n
T
T
T
Z
W
= (Ik − γγ )Q
Q
Z−
W−
m+n
m+n
m+n
m+n

2

.

Therefore, the three terms above are asymptotically independent, and their asymptotic distributions are χ2k−d , χ2k−d and χ2d−1 under the null, respectively.
Proof of Theorem 8.1. We will borrow notation and arguments used in the proof of Theorem
√
9.2. For example, we keep using the notation L = max1≤g≤d maxj∈Cg n|µj − νg |. However,
under Condition M2’, we have L = O(1) instead of L = o(1). Let Cn be a diverging sequence
C

3/2

max

|η̄

|

√g6=h gh → 0. Then, we can use the same analysis in the
that satisfies Cn → ∞ and n
n
proof of Theorem 9.2 that leads to (41) and (46). Note that the only difference is L = O(1),
and it will not affect the conclusions of (41) and (46). We still have

Tg − n

d X
X

h=1 j∈Ch

(Xπ−1 (j) − νh )2 = oP (1),
33

and


2
d
X
1 X
(Xπ−1 (j) − µj ) = oP (1).
Tf − n
|Ch |
j∈Ch

h=1

By the fact that

2

d
X
X
1 
(Xπ−1 (j) − νh )2 − n
(Xπ−1 (j) − µj )
n
|Ch |
h=1
h=1 j∈Ch
j∈Ch

2
d
d X
X
X
X
1
|Ch | 
(Xπ−1 (j) − νh )2 − n
= n
(Xπ−1 (j) − νh )
|Ch |
h=1
h=1 j∈Ch
j∈Ch
2

d X
X
X
Xπ−1 (j) − 1
Xπ−1 (j)  ,
= n
|Ch |
d X
X

j∈Ch

h=1 j∈Ch

we also have

Tg − Tf − n

d X
X

h=1 j∈Ch

2
X
Xπ−1 (j) − 1
Xπ−1 (j)  = oP (1).
|Ch |


j∈Ch

Therefore, under the null hypothesis X ∼ N (µ, n−1 Ik ), we have Tg
Tg − Tf
χ2k−d,τ 2 .

9.2

χ2k,τ 2 , Tf

χ2d and

Power Analysis

In this section, we give proofs of Theorem 3.2, Theorem 4.2, Theorem 5.2, Theorem 5.4 and
Theorem 7.2.
Proof of Theorem 3.2. We first assume nℓ(θ, µ)2 → ∞ and derive T → ∞ in probability.
Note that for each π ∈ Sk ,
n

k
k
k
X
X
X
(Xj − µπ(j) )2 .
(Xj − θj )2 + 2n
(θj − µπ(j) )2 ≤ 2n
j=1

j=1

j=1

Therefore,
2

nℓ(θ, µ) ≤ 2

k
X

Zj2 + 2nℓ(X, µ)2 ,

j=1

Pk

where Zj ∼ N (0, 1). The fact that 2 j=1 Zj2 = OP (1) and the assumption nℓ(θ, µ)2 →
∞ implies that nℓ(X, µ)2 → ∞ in probability. Suppose we can show T = OP (1) implies
nℓ(X, µ)2 = OP (1), then nℓ(X, µ)2 → ∞ in probability must implies T → ∞ in probability.
Now we suppose a bound T ≤ B = O(1), and it is sufficient to derive a bound for
nℓ(X, µ)2 . For each j = 1, ..., k, we shorthand the power sums pj (X1 , ..., Xk ) and pj (µ1 , ..., µk )
34

by pj (X) and pj (µ). Similarly, the elementary symmetric polynomials ej (X1 , ..., Xk ) and
ej (µ1 , ..., µk ) are shorthanded by ej (X) and ej (µ). Define a vector ∆ ∈ Rk with the jth entry
P
P
being ∆j = 1j kh=1 Xhj − 1j kh=1 µjh . Recall the definition of the matrix E(µ1 , ..., µk ). Then,
T = nkE(µ1 , ..., µk )∆k2 .

We use λmax (·) and λmin (·) to denote the largest and the smallest eigenvalues. By the fact
that V (µ1 , ..., µk )E(µ1 , ..., µk ) = Ik , we have
T ≥ nλmin (E(µ1 , ..., µk )T E(µ1 , ..., µk ))k∆k2 ≥

nk∆k2
.
λmax (V (µ1 , ..., µk )T V (µ1 , ..., µk ))

The bound T ≤ B then leads to
λmax (V (µ1 , ..., µk )T V (µ1 , ..., µk ))B
=O
k∆k ≤
n
2



B
n



.

(51)

Therefore, |pj (X) − pj (µ)|2 = O (B/n) for each j ∈ [k]. By Newton’s identities, we can
deduce |ej (X) − ej (µ)|2 = O (B/n) for each j ∈ [k]. Define
f (t) =

k
Y

fˆ(t) =

(t − µj ),

k
Y

(t − Xj ).

j=1

j=1

The relation between the two polynomials and the elementary symmetric polynomials is given
in (3). Using (3), we give a bound for |f (Xl )|.
|f (Xl )| = |f (Xl ) − fˆ(Xl )| ≤

k
X
j=0

|ek−j (X) − ek−j (µ)||Xl |j .

Since |Xl |2 ≤ p2 (X) ≤ p2 (µ) + |p2 (X) − p2 (µ)| = O(1), we have |f (Xl )|2 = O(B/n). The
following proposition is useful and will be proved in the end.
Proposition 9.1. For any µ1 , ..., µk , we have
|f (t)| ≥ min |t − µj |
1≤j≤k

Y

1≤j<l≤k

µj − µl
.
2

By this inequality, we have
2

max min (Xl − µj ) = O

1≤l≤k 1≤j≤k



B
n



Therefore, there exists a sequence σ(1), ..., σ(k) such that
 
B
2
max (Xj − µσ(j) ) = O
.
1≤j≤k
n

35

.

(52)

Since
k
Y

j=1

|t − µσ(j) | ≤ 2k

k
Y

j=1

|t − Xj | + 2k

and
|fˆ(µl )| = |fˆ(µl ) − f (µl )| ≤
we have

k
Y

j=1

k
X
j=0

k
Y

j=1



|Xj − µσ(j) | = 2k |fˆ(t)| + O

r

|ek−j (X) − ek−j (µ)||µl |j = O

|µl − µσ(j) | = O

r

B
n

!

B
n

B
n

k/2 !

!

,

,

,

which holds for every l = 1, ..., k. The fact that µ1 , ..., µk are k different fixed number implies
σ must be an element of Sk . Hence, the bound (52) implies nℓ(X, µ)2 = O(B), and the proof
of one direction is complete.
For the other direction, it is sufficient to show that nℓ(θ, µ) = O(1) implies T = OP (1).
This can be shown using the same argument in the proof of Theorem 9.1.
Proof of Proposition 9.1. We first consider the case k = 2, where f (t) = (t − µ1 )(t − µ2 ).
2|
2|
. Thus, |f (t)| ≥ |µ1 −µ
min{|t−µ1 |, |t−µ2 |}.
Suppose |t−µ1 | ≤ |t−µ2 |, then |t−µ2 | ≥ |µ1 −µ
2
2
The same argument also works when |t − µ1 | > |t − µ2 |. When k = 3,
|µ1 − µ2 |
min{|t − µ1 |, |t − µ2 |}
2
|µ1 − µ2 |
min {|t − µ1 ||t − µ3 |, |t − µ2 ||t − µ3 |} .
2

|f (t)| ≥ |t − µ3 |
=

The inequality for k = 2 can be used to lower bound both |t − µ1 ||t − µ3 | and |t − µ2 ||t − µ3 |.
This gives the desired result for k = 3. A standard mathematical induction argument leads
to inequality for all k.
Proof of Theorem 4.2. According to the argument that we have used in the proof of Theorem
3.2, we need to show Tf = OP (1) and Tg = OP (1) imply nℓ(X, µ)2 = OP (1) for the proof of
the first direction.
Suppose Tf ≤ B1 = O(1) and Tg ≤ B2 = O(1). It is sufficient to derive a bound for
nℓ(X, µ)2 . We first derive an inequality for g(t). Since
max

1≤g≤d

Y

2

(t − νh ) ≤

h∈[d]\{g}

d
X

Y

(t − νh )2 ≤ d max

g=1 h∈[d]\{g}

we have

1≤g≤d

Y

(t − νh )2 ,

h∈[d]\{g}

1
min (t − νg )2 ≤ g(t) ≤ min (t − νg )2 .
(53)
1≤g≤d
d 1≤g≤d
P
2
Therefore, Tg ≤ B2 implies that kj=1 min1≤g≤d (Xj − νg )2 ≤ dB
n . This implies the existence
2
of a sequence σ(1), ..., σ(k) such that max1≤j≤k (Xj − νσ(j) )2 ≤ dB
n = O(B2 /n). It further
36

p
h | = O( B /n). Define Cˆ = {j ∈ [k] : σ(j) = g} for
implies max1≤h≤d max1≤j≤k |Xjh − νσ(j)
2
g
each g ∈ [d]. Then
2

 
d
d−1 X
k
X
X
B2
h
h
ˆ

|Cg |νg
Xj −
=O
.
n
g=1
j=1

h=1

Using the same argument in deriving (51), we can also get the bound
d−1
X

h=1

2

 
d
k
X
X
B1

|Cg |νgh  = O
Xjh −
.
n
j=1

g=1

P
P
The inequalities in the last two displays, together with the equality dg=1 |Cˆg | = dg=1 |Cg |,
give
2



d
d−1 X
d
X
X
B1 + B2
h
h
ˆ

.
|Cg |νg
=O
|Cg |νg −
n
h=0

g=1

g=1

Define a vector r ∈ Rd , with its gth entry being |Cˆg | − |Cg |. Then,
d−1
X
h=0

2

d
d
X
X

|Cg |νgh  = kV (ν1 , ..., νd )rk2 ≥ λmin (V (ν1 , ..., νd )T V (ν1 , ..., νd ))krk2 .
|Cˆg |νgh −
g=1

g=1

When ν1 , ..., νd are d different numbers, we have λmin (V (ν1 , ..., νd )T V (ν1 , ..., νd )) > 0, and

2
. Since krk2 is an integer, we must have krk2 = 0, which gives
thus krk2 = O B1 +B
n
|Cˆg | = |Cg | for any g ∈ [d]. From this we can deduce that nℓ(X, µ)2 = O(B2 ).
For the other direction, it is sufficient to show that nℓ(θ, µ)2 = O(1) implies Tf = OP (1)
and Tg = OP (1). This can be shown using the same argument in the proof of Theorem
9.2.
Proofs of Theorem 5.2 and Theorem 5.4. The proofs are the same as those of Theorem 3.2
and Theorem 4.2.
√ p
√
Proof of Theorem 7.2. First of all, we have maxj∈[k] n| q̂j − qj | = OP (1). This gives
that P(C g = Cg for all g ∈ [d] and d = d) → 1. From now on, the analysis is on the event
√ p
√
{C g = Cg for all g ∈ [d] and d = d}. Since we also have maxj∈[k] n| p̂j − pj | = OP (1),
the statement nℓ(p, q)2 → ∞ is equivalent to nℓ(p̂, q)2 → ∞ in probability. Therefore, we
only need to establish the equivalence between nℓ(p̂, q)2 → ∞ in probability and the power
of the test goes to one.
In the first direction of the proof, we suppose that Tf ≤ B1 = OP (1) and Tg ≤ B2 =
OP (1), and we will show nℓ(p̂, q)2 = OP (1). The bound Tg ≤ B2 = OP (1) implies that
k

2nm X
g(p̂j ) ≤ B2 .
n+m
j=1

37

√
p
By the definition of g(·), we have g(t) ≥ d−1 ming∈[d] ( t − rg )2 . This implies the bound
k
X
j=1

Since maxg∈[d]

min

g∈[d]

p

p̂j −

k
X

min

p 2 dB2 (n + m)
rg ≤
= OP (n−1 ).
nm

√ p
√
n| rg − rg | = OP (1), we deduce
j=1

g∈[d]

p

p̂j −

√ 2
rg = OP (n−1 ).

p
√
Then, there must exist σ(1), ..., σ(k) such that maxj∈[k] | p̂j − rσ(j) |2 = OP (n−1 ). It
p h
√
further implies that maxh∈[d] maxj∈[k] |( p̂j ) − ( rσ(j) )h | = OP (n−1/2 ). Define Cˆg = {j ∈
[k] : σ(j) = g} for each g ∈ [d]. Then, we have
d−1
X
h=1

Note that
Tf

2
k
d
X
p h X
√
 ( p̂j ) −
|Cˆg |( rg )h  = OP (n−1 ).


≥
≥
=

j=1

(54)

g=1


2
d
k
k
X
2nm X 1 X
f h (p̂j ) −
f h (q̂j )
n+m
|Ch |
j=1
j=1
h=1
2

k
d
k
X
X
X
2nm

f h (p̂j ) −
f h (q̂j )
d(n + m)
h=1

2nm
d(n + m)

j=1

j=1

√
√
kE( r 1 , ..., r d )∆k2 ,

where ∆ is a d-dimensional vector with ∆h =
bound Tf ≤ B1 = OP (1) implies that

1
h

Pk

p

j=1 (

p̂j )h −

√
√
kE( r1 , ..., r d )∆k2 = OP (n−1 ).

1
h

Pk

p

j=1 (

q̂j )h . Thus, the

√
√
√
√
Since λmin (E( r1 , ..., rd )T E( r1 , ..., rd )) is a positive constant that is bounded away from
0, and
√
√
√
√
√
√
√
√
|λmin (E( r1 , ..., rd )T E( r1 , ..., r d )) − λmin (E( r1 , ..., rd )T E( r1 , ..., rd ))| = oP (1),
we have k∆k2 = OP (n−1 ), which further leads to
d−1
X
h=1

2
k
d
X
p h X
√
 ( p̂j ) −
|Cg |( rg )h  = OP (n−1 ),


j=1

g=1

38

(55)

√ p
√
by using the fact that maxj∈[k] n| q̂j − qj | = OP (1) and Condition E. The two inequalities
P
P
(54) and (55), together with the fact that dg=1 |Cˆg | = dg=1 |Cg |, imply

2
d
d
d−1 X
X
X
√
√

|Cg |( rg )h  = OP (n−1 ).
|Cˆg |( rg )h −
h=0

g=1

g=1

The same argument used in the proof of Theorem 4.2 implies that |Cˆg | = |Cg | for all g ∈ [d].
p
√
Therefore, together with maxj∈[k] | p̂j − rσ(j) |2 = OP (n−1 ), we obtain the conclusion
nℓ(p̂, q) = OP (1).
For the other direction, when nℓ(p, q)2 = O(1), the approximations (49) and (50) in the
proofs of Theorem 7.1 hold with bounds at the order of OP (1). This leads to Tf = OP (1)
and Tg = OP (1).

9.3

Minimax Upper and Lower Bounds

In this section, we prove all results in Section 6. We first give proofs for the lower bounds,
and then for the upper bounds.
2
Proof of Theorem 6.1. We first observe an inequality |ηjl | + |ηlj | ≥ |µl −µ
, which has been
j|
√
derived in the proof of Theorem 9.1. Thus, Condition M1 implies n|µj − µl | → ∞ for any
j 6= l. Consider the set


δ
Θ̄δ = θ : kθ − µk = √
.
n
2

For each θ ∈ Θ̄δ , |θj − µj |2 ≤ δn , which implies µj is the closest element to θj in the set
√
{µ1 , ..., µk }. Therefore, ℓ(θ, µ) = kθ − µk = δ/ n, which implies Θ̄δ ⊂ Θδ . This gives the
lower bound
(
)
Rn (k, δ) ≥ inf

0≤φ≤1

Pµ φ + sup Pθ (1 − φ) .
θ∈Θ̄δ

Consider the uniform distribution Π on Θ̄δ . Then,


Z
Rn (k, δ) ≥ inf
Pµ φ + Pθ (1 − φ)dΠ(θ) .
0≤φ≤1

By Neyman-Pearson lemma, the optimal testing function φ is given by
 R

d Pθ dΠ(θ)
φ=
>1 .
dPµ
Using the property of Π, we have
R
Z
d Pθ dΠ(θ)
dPθ
=
dΠ(θ)
dPµ
dPµ
Z
 n

=
exp − kθ − µk2 + n hX − µ, θ − µi dΠ(θ)
2
Z
2
= e−δ /2 exp (n hX − µ, θ − µi) dΠ(θ).
39

Let Π̄ be the uniform distribution on the unit sphere {θ : kθk = 1}, and then we have
Z
Z

√
exp (n hX − µ, θ − µi) dΠ(θ) = exp δ n hX − µ, θi dΠ̄(θ).

Let f be the marginal density of the first coordinate of θ ∼ Π̄. Then, f (t) ∝ (1 − t2 )
uniformity of Π̄ implies that
Z

√


exp δ n hX − µ, θi dΠ̄(θ) =

R1

−1 exp (δ

√

nkX − µkt) (1 − t2 )

R1

−1 (1

− t2 )

k−3
2

k−3
2

dt

dt

k−3
2

.

. The

(56)

√
Therefore, we can write the quantity in the above display as F ( nkX − µk). Since
′

F (x) =

the testing statistic

d

R

R1
0

Pθ dΠ(θ)
dPµ

(eδxt − e−δxt )δt(1 − t2 )
R1
k−3
2 2 dt
−1 (1 − t )

k−3
2

dt

> 0, for x > 0,

is an increasing function of kX − µk2 . This implies

φ = nkX − µk2 ≥ t ,

for some t > 0. Note that nkX − µk2 ∼ χ2k under Pµ , and nkX − µk2 ∼ χ2k,δ2 under any Pθ
with θ ∈ Θ̄δ . Hence,
n
o
Rn (k, δ) ≥ inf P(χ2k ≥ t) + P(χ2k,δ2 < t) .
t>0

This completes the proof.

Proof of Theorem 6.3. Since |η̄gh |+|η̄hg | ≥

2
|νg −νh | ,

it is implied by Condition M2 that
o(n−1/2 ).

√

n|νg −

νh | → ∞ for any g 6= h. Moreover, for any j ∈ Ch , |µj − νh | =
Under these
δ
assumptions, for any θ such that kθ − µk = √n , there exists a π ∈ Sk that depends on θ and
kθπ − µk = ℓ(θ, µ) =

kθ − µk =

√δ .
n

Define

√δ (1
n

+ ǫθ ). Moreover, |ǫθ | = o(1) uniformly over all θ that satisfies
θ′ = µ +

1
(θ − µ).
1 + ǫθ

(57)

δ
Then, kθ ′ − µk = √δθn and ℓ(θ ′ , µ) = √δn , where δθ = 1+ǫ
. We use the notation R to denote
θ
the operator R : θ 7→ R(θ) = θ ′ defined by (57). By the definition, a useful property is
R(θ)−µ
θ−µ
kR(θ)−µk = kθ−µk . Consider the set



δ
.
Θ̄δ = R(θ) : kθ − µk = √
n
This definition immediately implies Θ̄δ ⊂ Θδ . Note that each element in Θ̄δ can be represented as
δθ θ − µ
R(θ) = µ + √
.
n kθ − µk
40

Since there is a one-to-one relation between
δv
√
v.
n

θ−µ
kθ−µk

and a unit vector v, we can also write

Consider a uniform probability measure Π̄ on {v : kvk = 1}.
each element in Θ̄δ as µ +
Then, by the same argument in the proof of Theorem 6.1,


Z
Rn (k, δ) ≥ inf
Pµ φ + Pµ+ √δv v (1 − φ)dΠ̄(v) ,
0≤φ≤1

n

and the likelihood ratio is
L=

Z dP √δv
µ+

n

dPµ

v

dΠ̄(v) =

Z


√
exp −δv2 /2 + δv n hX − µ, vi dΠ̄(v).

Under the assumption, there exist δ− and δ+ such that δ− ≤ δv ≤ δ+ for all v and δ− /δ =
1 + o(1) and δ+ /δ = 1 + o(1). We introduce the upper and lower brackets of L as
Z

√
2
exp −δ+
/2 + δ− n hX − µ, vi dΠ̄(v),
L− = min

Z

√
2
exp −δ+
/2 + δ+ n hX − µ, vi dΠ̄(v) ,
Z

√
2
exp −δ−
/2 + δ− n hX − µ, vi dΠ̄(v),
L+ = min

Z

√
2
exp −δ− /2 + δ+ n hX − µ, vi dΠ̄(v) .
The definitions imply L− ≤ L ≤ L+ . Define the function
Fδ (x) =
By (56), we have

2 k−3
2 dt
−1 exp (δxt) (1 − t )
.
R1
k−3
2 2 dt
−1 (1 − t )

R1

(58)

√
√
2
L− = e−δ+ /2 min{Fδ− ( nkX − µk), Fδ+ ( nkX − µk)},
√
√
2
L+ = e−δ− /2 max{Fδ− ( nkX − µk), Fδ+ ( nkX − µk)}.
Define φ = I{L > 1}, φ− = I{L− > 1} and φ+ = I{L+ > 1}. We have the inequality
√
φ− ≤ φ ≤ φ+ . For θ = EX = µ, k n(X − µ)k2 ∼ χ2k . Thus, let Z ∼ N (0, Ik ), and then we
have
Pµ φ

≥

Pµ (L− > 1)
 2

= P e−δ+ /2 min{Fδ− (kZk), Fδ+ (kZk)} > 1
 2

→ P e−δ /2 Fδ (kZk) > 1 .

41

For the alternative θ = µ +
Pµ+ √δv v (1 − φ)
n

δv
√
v
n

√
∈ Θ̄δ , k n(X − µ)k2 ∼ χk2 ,δv2 , where δv2 ∈ [δ− , δ+ ]. Then,

Pµ+ √δv v (L+ ≤ 1)
n
 2

−δ− /2
= P e
max{Fδ− (kZ + δv vk), Fδ+ (kZ + δv vk)} ≤ 1
 2

−δ− /2
≥ P e
max{Fδ− (kZ + δ+ vk), Fδ+ (kZ + δ+ vk)} ≤ 1
 2

→ P e−δ /2 Fδ (kZ + δvk) ≤ 1
≥

 2

Note that P e−δ /2 Fδ (kZ + δvk) ≤ 1 is independent of v. Therefore, by the fact that Fδ (x)
is increasing on x > 0, we have
Rn (k, n) ≥ Pµ (L− > 1) + inf Pµ+ √δv v (L+ ≤ 1)
n
kvk=1
 

 2

−δ2 /2
−δ /2
≥ (1 + o(1)) P e
Fδ (kZk) > 1 + inf P e
Fδ (kZ + δvk) ≤ 1
kvk=1
n
o
≥ (1 + o(1)) inf P(χ2k ≥ t) + P(χ2k,δ2 < t) .
t>0

The proof is complete.

√ √
√
Proof of Theorem 6.5. Note that Condition M3 implies n| qj − ql | → ∞ for any j 6= l.
Consider the set


δ
√
√
P̄δ = p : k p − qk = √
.
n
2
√
√
√
√
For each p ∈ P̄δ , | pj − qj |2 ≤ δn , which implies qj is the closest element to pj in the
√
√
√
√
√
set { q1 , ..., qk }. Therefore, ℓ(p, q) = k p − qk = δ/ n, which implies P̄δ ⊂ Pδ . This
gives the lower bound
(
)
Rn (k, δ) ≥ inf

0≤φ≤1

Pq φ + sup Pp (1 − φ) .
p∈P̄δ

√
√
Let Π be the uniform distribution on the sphere {v : kv − qk = δ/ n}. Then,


Z
√
Rn (k, δ) ≥ inf
Pq φ + Pp (1 − φ)dΠ( p) .
0≤φ≤1

By Neyman-Pearson lemma, the optimal testing function φ is given by
 R

√
d Pp dΠ( p)
φ=
>1 .
dPq
By the definition, we have


R
Z
√
k
k
X
X
d Pp dΠ( p)
p
p
√
j
j
qj log
(p̂j − qj ) log  dΠ( p),
= exp n
+n
L=
dPq
qj
qj
j=1

j=1

42

1 Pn
i=1 I{Xi = j}. Note that
n
√
√
pj − qj
√
max1≤j≤k
= o(1). Therefore,
qj

where p̂j =

log
max

1≤j≤k

and
log
max

1≤j≤k

Since

k
X
j=1

qj

"√

q

pj
qj

−

log

q

pj
qj


= log 1 +

√
√
pj − qj
pj
√
qj −
qj
√
√
pj − qj 2
√
qj

q

√

√
pj − qj
√
qj
√

+

1
2

√
pj − qj 3
√
qj

√

√

√ 
pj − qj
√
.
qj

By Condition M3,

= O(1),

√ 
pj − qj 2
√
qj

(59)

= O(1).

(60)

√
√
√  #
pj − q j
pj − q j 2
1
√
√
−
= −k p − qk2 .
√
√
qj
2
qj

By (60), we have
k
X
j=1

qj log

pj
√
√
= −(1 + o(1))2k p − qk2 .
qj

Under Condition M3, p̂j /pj = 1 + oP (1), and this implies p̂j /qj = 1 + oP (1). Therefore,
√
√
k
k
X
X
p
pj − q j
√
√
√
( p̂j − qj )( pj − qj ).
= 2(1 + oP (1))
(p̂j − qj )
√
qj

(61)

j=1

j=1

By (59), we have
k
k
X
X
p
pj
√
√
√
( p̂j − qj )( pj − qj ).
= 4(1 + oP (1))
(p̂j − qj ) log
qj

(62)

j=1

j=1

The approximations (61) and (62) imply the existence of δ− and δ+ that satisfies δ− =
(1 + o(1))δ, δ+ = (1 + o(1))δ. Moreover, on an event E with probability 1 − o(1) under both
null and alternative, the following inequalities hold:
2
−2δ+

≤n

k
X

qj log

j=1

pj
2
≤ −2δ−
,
qj




√
√
√ 
√ 
k
X
p− q
p− q
pj
√
√
4δ− p
4δ+ p
p̂ − q, √
p̂ − q, √
(p̂j − qj ) log
≤ max √
,√
,
√
√
qj
n
k p − qk
n
k p − qk
j=1

and



√
√
√ 
√ 
k
X
p− q
p− q
4δ− p
4δ+ p
pj
√
√
≥ min √
p̂ − q, √
,√
p̂ − q, √
.
(p̂j − qj ) log
√
√
qj
n
k p − qk
n
k p − qk
j=1

43

We introduce the upper and lower brackets of the L as
Z

√ Dp
√ E
2
p̂ − q, v dΠ̄(v),
L− = min
exp −2δ+
+ 4δ− n

Z

√ Dp
√ E
2
exp −2δ+ + 4δ+ n
p̂ − q, v dΠ̄(v) ,
Z

√ Dp
√ E
2
p̂ − q, v dΠ̄(v),
exp −2δ−
+ 4δ− n
L+ = max

Z

√ Dp
√ E
2
p̂ − q, v dΠ̄(v) ,
exp −2δ− + 4δ+ n

(63)

(64)

where Π̄ is the uniform distribution on the unit sphere {v : kvk = 1}. By (56), we have
√ p
√ p
2
√
√
L− = e−2δ+ min{F2δ− (2 nk p̂ − qk), F2δ+ (2 nk p̂ − qk)},
√ p
√ p
√
√
2
L+ = e−2δ− max{F2δ− (2 nk p̂ − qk), F2δ+ (2 nk p̂ − qk)}.

√
√
√
where Fδ (x) is defined in (58). Note that 4nk p̂ − qk2
χ2k−1 under the null and 4nk p̂ −
√ 2
qk − δ22
χ2k−1,δ2 , with δ12 = δ1 (p)2 and δ22 = δ2 (p)2 defined in (47) and (48), under the
1
alternative. Define φ = I{L > 1}, φ− = I{L− > 1}, φ+ = I{L+ > 1} and φ∗ = I{L∗ > 1}.
Then, we have the inequality φ− IE ≤ φIE ≤ φ+ IE . For q = p, we have
Pq φ

=

Pq φIE + Pq φIE c

≥

Pq φ− IE

Pq (L− > 1) − Pq (E c )


√ p
√ p
2
√
√
= Pq e−2δ+ min{F2δ− (2 nk p̂ − qk), F2δ+ (2 nk p̂ − qk)} > 1 − Pq (E c )

q


2
→ P e−2δ F2δ
χ2k−1 > 1 .
≥

For the alternative, we have
Pp (1 − φ)

=
≤

Pp (1 − φ)IE + Pp (1 − φ)IE c
Pp (1 − φ+ )IE + Pp (E c )

Pp (1 − φ+ ) + Pp (E c )


√ p
√ p
√
√
2
= Pp e−2δ− max{F2δ− (2 nk p̂ − qk), F2δ+ (2 nk p̂ − qk)} ≤ 1 + Pp (E c )


q

2
→ P e−2δ F2δ
χ2k−1,δ1 (p)2 + δ2 (p)2 ≤ 1

q


2
≥
inf
P e−2δ F2δ
χ2k−1,δ2 + δ22 ≤ 1 .
≤

{δ1 ,δ2 :δ12 +δ22 =δ2 }

1

44

By the fact that Fδ (x) is increasing on x > 0, we have
q
n 


−2δ2
F2δ
Rn (k, δ) ≥ (1 + o(1)) P e
χ2k−1 > 1 +
inf

{δ1 ,δ2 :δ12 +δ22 =δ2 }




q
2
χ2k−1,δ2 + δ22 ≤ 1
P e−2δ F2δ
1

≥ (1 + o(1)) inf

P

t>0

χ2k−1



>t +

inf

{δ1 ,δ2 :δ12 +δ22 =δ2 }

)

P(χ2k−1,δ2
1

+

δ22

!

≤ t) .

The proof is complete.
√ √
√
Proof of Theorem 6.7. It is implied by Condition M4 that n| rg − rh | → ∞ for any g 6= h.
√
√
Moreover, for any j ∈ Ch , | qj − rh | = o(n−1/2 ). Under these assumptions, for any p such
√
√
√
√
that k p − qk = √δn , there exists a π ∈ Sk that depends on p and k pπ − qk = ℓ(p, q) =
√
√
√δ (1 + ǫθ ). Moreover, |ǫθ | = o(1) uniformly over all p that satisfies k p − qk = √δ . Define
n
n
′

p =



√

2
√
1
√
q+
( p − q) .
1 + ǫθ

(65)

√
√
δ
. We use the notation R to
Then, k p − qk = √δθn and ℓ(p′ , q) = √δn , where δθ = 1+ǫ
θ
By
the
definition,
a useful property is
denote
the
operator
R
:
p
→
7
R(p)
defined
by
(65).
√
√

√R(p)−√q =

k

R(p)− qk

√ √
p− q
√ √
k p− qk .

Consider the set



δ
√
√
P̄δ = R(p) : k p − qk = √
.
n
This definition immediately implies P̄δ ⊂ Pδ . Note that each element in P̄δ can be represented
as

√
√ 
p− q 2
δθ
√
q+√ √
R(p) =
.
√
n k p − qk
√

√
p− q

Since there is a one-to-one relation between k√p−√qk and a unit vector v, we can also write
√
2
each element in P̄δ as
q + √δvn v . Consider a uniform probability measure Π̄ on {v : kvk =
1}. Then, by the same argument in the proof of Theorem 6.1,
)
(
Z
Rn (k, δ) ≥ inf

0≤φ≤1

and the likelihood ratio is
L=

Pq φ +

P√

Z dP√

δv
v
q+ √
n

δv
q+ √
v
n

dPq

2

2 (1

− φ)dΠ̄(v) ,

dΠ̄(v).

Using the same arguments in the proofs of Theorem 6.3 and Theorem 6.5, there exist δ− and
δ+ , with which we can define L− and L+ as in (63) and (64) with the desired properties.
Then, the same argument in the proof of Theorem 6.5 leads to the desired result.
45

Proof of Theorem 6.2. By studying the proof of Theorem 9.1, the only probabilistic argument
in approximation is that max1≤j≤k Zj2 ≤ Cn in probability. Since this event is independent
of θ, the in-probability argument can be made uniformly over θ ∈ Θδ and θ ∈ Θ0 .
Proof of Theorem 6.4. By Theorem 9.2, Tg ≥ Tf in probability. This implies that Pθ φ =
Pθ (Tg > t∗ ) and Pθ (1 − φ) = Pθ (Tg ≤ t∗ ) under both null and alternative distributions. Then,
by the same argument in the proof of Theorem 6.2, we obtain the desired conclusion.
Proofs of Theorem 6.6 and Theorem 6.8. Similar to the argument used in the proof of Theorem 6.2, the results directly follow the conclusions of Theorem 9.3 and Theorem 9.4.

References
[1] Animashree Anandkumar, Daniel Hsu, and Sham M Kakade. A method of moments for
mixture models and hidden markov models. In Conference on Learning Theory, pages
33–1, 2012.
[2] Animashree Anandkumar, Rong Ge, Daniel Hsu, and Sham Kakade. A tensor spectral
approach to learning mixed membership community models. In Conference on Learning
Theory, pages 867–881, 2013.
[3] Francis J Anscombe. The transformation of poisson, binomial and negative-binomial
data. Biometrika, 35(3/4):246–254, 1948.
[4] Sanjeev Arora, Rong Ge, and Ankur Moitra. New algorithms for learning incoherent
and overcomplete dictionaries. In Conference on Learning Theory, pages 779–806, 2014.
[5] Debapratim Banerjee and Zongming Ma. Optimal hypothesis testing for stochastic block
models with growing degrees. arXiv preprint arXiv:1705.05305, 2017.
[6] Harry Crane. The ubiquitous ewens sampling formula. Statistical Science, 31(1):1–19,
2016.
[7] Warren J Ewens. The sampling theory of selectively neutral alleles. Theoretical population biology, 3(1):87–112, 1972.
[8] Chao Gao and John Lafferty. Testing network structure using relations between small
subgraph probabilities. arXiv preprint arXiv:1704.06742, 2017.
[9] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press,
2012.
[10] Daniel Hsu and Sham M Kakade. Learning mixtures of spherical gaussians: moment
methods and spectral decompositions. In Proceedings of the 4th conference on Innovations in Theoretical Computer Science, pages 11–20. ACM, 2013.

46

[11] Peter Müller, Abel Rodriguez, et al. Random partition models. In Nonparametric
Bayesian Inference, pages 87–92. IMS and ASA, 2013.
[12] Karl Pearson. On the criterion that a given system of deviations from the probable in
the case of a correlated system of variables is such that it can be reasonably supposed to
have arisen from random sampling. The London, Edinburgh, and Dublin Philosophical
Magazine and Journal of Science, 50(302):157–175, 1900.
[13] Amelia Perry, Jonathan Weed, Afonso Bandeira, Philippe Rigollet, and Amit Singer.
The sample complexity of multi-reference alignment. arXiv preprint arXiv:1707.00943,
2017.
[14] Jim Pitman. Exchangeable and partially exchangeable random partitions. Probability
theory and related fields, 102(2):145–158, 1995.

47

