On Identifying a Massive Number of Distributions
Sara Shahi, Daniela Tuninetti and Natasha Devroye
University of Illinois at Chicago, Chicago IL 60607, USA.
Email: sshahi7, danielat, devroye @uic.edu

Abstract—THIS PAPER IS ELIGIBLE FOR THE STUDENT
PAPER AWARD. Finding the underlying probability distributions of a set of observed sequences under the constraint that
each sequence is generated i.i.d by a distinct distribution is
considered. The number of distributions, and hence the number
of observed sequences, are let to grow with the observation
blocklength n. Asymptotically matching upper and lower bounds
on the probability of error are derived.

arXiv:1801.04593v1 [cs.IT] 14 Jan 2018

I. I NTRODUCTION
Hypothesis testing is a classical problem in statistics where
one is given a random observation vector and one seeks to
identify the distribution from a given set of distributions that
generated it. Pioneering work in classical hypothesis testing
include the proof of the optimality of likelihood ratio tests
under certain criteria in the Neyman-Pearon Theorem [1].
Derivation of error exponents of different error types and
their trade-offs for binary and M-ary hypothesis testing in [2]
and [3] and the analysis of sequential hypothesis testing in [4].
The classical identification problem, which includes hypothesis testing as a special case, is consist of a finite number of
distinct sources, each generating a sequence of i.i.d samples.
The problem is to find the underlying distribution of each
sample sequence, given the constraint that each sequence
is generated by a distinct distribution. With this constraint
the number of hypothesis is exponential in the number of
distributions. If one neglects the fact that the sequences are
generated by distinct distributions, the problem boils down to
multiple M-ary hypothesis testing problems. This approach is
suboptimal as it fails to exploit some of the (possibly useful)
constraints.
In [5], the authors study the the Logarithmically Asymptotically Optimal (LAO) Testing of identification problem for
a finite number of distributions. In particular, they study the
identification of only two different objects in detail and find
the reliability matrix, which consist of the error exponents
of all error types. Their optimality criterion is to find the
largest error exponent for a set of error types for given
values of the other error types error exponent. The same
problem with a different optimality criterion was also studied
in [6], where multiple, finite, sequences were matched to the
source distributions. More specifically, they proposed a test
for a generalized Neyman-Pearson-like optimality criterion to
minimize the rejection probability given that all other error
probabilities decay exponentially with a pre-specified slope.
In here, we assume A sequences of length n are generated
i.i.d according to A distinct distributions; in particular random
i.i.d
vectors Xin ∼ Pσi , i ∈ [1 : A], for some unknown

permutation σ of the distributions. The goal is to reliably
identify the permutation σ with vanishing error probability as
n
n → ∞ from an observation of [X1n , . . . , XA
]. This problem
has close ties with de-anonymization of anonymized data [6].
A different motivation is the identification of users using only
channel output sequences, without the use of pilot / explicit
identification signals [7]. In both scenarios, the problem’s
difficulty increases with the number of users. In addition,
in modeling the systems with a massive number of users
(such as the Internet of Things), it may be reasonable to
assume that the number of users grow with the transmission
blocklength [7], [8], and that the user’s identities must be
distinguished from the received data. As the result, it is useful
to understand exactly how the number of distributions affects
the system performance, in particular for the case that the
cardinality of the distributions grows with the blocklength.
Notice that in this scenario, the number of hypothesis, would
be doubly exponential in blocklength and the analysis of the
optimal decoder becomes much harder than the classical (with
constant number of distributions) identification problems.
Contributions. In this paper, we consider the identification
problem for the case that the number of distributions grow with
the observation blocklength n as motivated by the massive
user identification problem in the Internet of Things paradigm.
The key novel element in this work consist of analyzing and
reducing the complexity of the optimal maximum likelihood
decoder, with double exponential number of hypothesis, using
a graph theoretic result. In particular, we find
1) Find matching upper and lower bounds on the probability of error. This result specifies the relation between
the growth rate of the number of distributions and
the pairwise distance of the distributions for reliable
identification.
2) We show that the probability that more than two distributions are incorrectly identified is dominated by the
probability of the event that only two distributions are
incorrectly identified.
3) We show that the arithmetic mean of the cycles gains
(where we define the cycle gain as the product of the
edge weights within the cycle) in a graph can be upper
bounded by a function of the sum of the squares of the
edge weights. This may be of independent interest.
II. N OTATION
Capital letters represent random variables that take on lower
case letter values in calligraphic letter alphabets. For a set of
finite alphabet X , we use PX to denote the set of all possible

distributions on X . A vector of length n is defined by xn =
[x1 , . . . , xn ]. When all elements of the random vector X n are
generated i.i.d according to distribution P , we denote it as
i.i.d
X n ∼ P . We use Sn , where |Sn | = n!, to denote the set of all
possible permutations of a set of n elements. For a permutation
σ ∈ Sn , σi denotes the i-th element of the permutation. bxcr is
used to denote the remainder of x divided by r. The indicator
function of event A is denoted by 1{A} . We use the notation
.
log an
= b.
an = enb when limn→∞
n

Kk a1 , . . . , a(k) is the complete graph with k nodes with
2


edge index i ∈ [1 : k2 ] and edge weights ai , i ∈ [1 : k2 ].
We may drop the edge argument and simply write Kk when
the edge specification is not needed. A cycle c of length r in
Kk may be interchangeably defined by a vector of vertices as
c(v) = [v1 , . . . , vr ] or by a set of edges c(e) = {a1 , . . . , ar }
where ai is the edge between (vi , vi+1 ), ∀i ∈ [1 : r − 1] and
ar is that between (vr , v1 ). With this notation, c(v) (i) is then
(r)
used to indicate the i-th vertex of the cycle c. Ck is used to
denote
 the set of all cycles of length r in the complete graph
Kk a1 , . . . , a(k) . The cycle gain, denoted by G(c), for cycle
2

(r)

c = {a1 , . . . , ar } ∈ Ck is theQ
product of the edge weights
r
within the cycle c, i.e., G(c) = i=1 ai , ∀ai ∈ c.
III. P ROBLEM FORMULATION
Let P := {P1 , . . . , PA } ⊂ PX consist of A distinct
distributions and also let Σ be uniformly distributed over SA ,
the set of permutations of A elements. In addition, assume that
n
we have A independent random vectors {X1n , X2n , . . . , XA
} of
length n each. For σ, a realization of Σ, assign the distribution
Pσni to the random vector Xin , ∀i ∈ [1 : A]. After observing
a sample xnA = [xn1 , . . . , xnA ] of the random vector X nA =
n
], we would like to identify Pσi , ∀i ∈ [1 : A].
[X1n , . . . , XA
More specifically, we are interested in finding a permutation
i.i.d
σ̂ : X nA → SA to indicate that Xin ∼ Pσ̂i , ∀i ∈ [1 : A]. Let
nA
Σ̂ = σ̂(X ).
The average probability of error for the set of distributions
P is given by
h
i
Pe(n) = P Σ̂ 6= Σ
i
1 X h
i.i.d
=
P Σ̂ 6= σ|Xin ∼ Pσi , ∀i ∈ [1 : A]
(A)!
σ∈SA
h
i
= P Σ̂ 6= [1 : A] H(1,...,A) .
(1)
i.i.d

where H(1,...,A) := {Xin ∼ Pi , ∀i ∈ [1 : A]}.
We say that a set of distributions P are identifiable if
(n)
limn→∞ Pe → 0.
Theorem 1. A sequence of distributions P = {P1 , . . . , PAn }
are identifiable iff
X
lim
e−2nB(Pi ,Pj ) = 0,
n→∞

1≤i<j≤An

where B(P, Q) = B(Q, P ) = − log PP

  
1/2
Q
P

is the

Bhattacharya distance between the distributions P and Q.

Proof. As it is obvious from the result of Theorem 1, for the
case that An = A is a constant or the case that An = O(n),
the sequence of distributions in P are always identifiable and
the probability of error in the identification problem decays
to zero as the blocklength n goes to infinity. The interesting
aspect of Theorem 1 is in fact in the regime that An increases
exponentially with the blocklength.
To prove Theorem 1, we provide upper and lower bounds
on the probability of error in the following subsections.
A. Upper bound on the probability of error
We use the optimal Maximum Likelihood (ML) decoder
which minimizes the average probability of error, given by
σ̂(xn1 , . . . , xnAn ) := arg max

σ∈SAn

An
X

log (Pσi (xni )) ,

(2)

i=1

Qn
where Pσi (xni ) = t=1 Pσi (xi,t ). The average probability of
error associated with the ML decoder can also be written as
i
h
Pe(n) = P Σ̂ 6= [1 : An ] H(1,...,An )


[
= P
Σ̂ = σ̂ H(1,...,An ) 
σ̂6=[1:An ]




An
[

= P
r=2

"
=P



Σ̂ = σ̂ H(1,...,An ) 

PAn σ̂:
1
=r
{ i=1 {σ̂i 6=i} }
[

An
[

An
X

[

r=2 P
An

{

i=1

σ̂:

1{σ̂i 6=i} =r}

(3)

Pσ̂
log i (Xin ) ≥ 0 H(1,...,An )
Pi
i=1

#

(4)
Pi (Xt )
where log PPji (X n ) :=
t=1 log Pj (Xt ) and where (3) is
due to the requirement that each sequence is distributed
according to a distinct distribution and hence the number of
incorrect distributions ranges from [2 : An ]. Equation (4)
is also the consequence of the ML decoder defined in (2).
In order to avoid considering the same set of error events
multiple
a graph theoretic interpretation
nP times, we incorporate
o
An
of
in (4). Consider the two sequences
i=1 1{Σ̂i 6=i} = r
[i1 , . . . , ir ] and [σ̂i1 , . . . , σ̂ir ] for which we have


An
r
X

X
1{σ̂i 6=i} =
1{σ̂ij 6=ij } = r .



Pn

i=1

j=1

These two sequences in (4) in fact indicate the event that
i.i.d
we have (incorrectly) identified Xinj ∼ Pσ̂ij instead of the
i.i.d

(true) distribution Xinj ∼ Pij , ∀j ∈ [1 : r]. For a complete
graph KAn , the set of edges between ((i1 , σ̂i1 ), . . . , (ir , σ̂ir ))
in KAn would produce a single cycle of length r or a set of
disjoint cycles with total length r. However, we should note
that in the latter case where the sequence of edges construct a
set of (lets say of size L) disjoint cycles (each with some length

PL
r̃l for r̃l < r such that l=1 r̃l = r), then those cycles and
their corresponding sequences are already taken into account
in the (union of) set of r̃l error events.
As an example, assume An = 4 and consider the error event
P2 n
P1 n
P4 n
P3 n
(X ) + log
(X ) + log
(X ) + log
(X ) ≥ 0,
P1 1
P2 2
P3 3
P4 4
which corresponds to the (error) event of choosing
[σ̂1 , σ̂2 , σ̂3 , σ̂4 ] = [2, 1, 4, 3] over [1, 2, 3, 4] with r = 4 errors.
In the graph representation, this gives two cycles of length 2
each, which correspond to
log

P2 n
P1 n
(X ) + log
(X ) ≥ 0 ∩
P1 1
P2 2
P4 n
P3 n
log
(X3 ) + log
(X ) ≥ 0,
P3
P4 4
and are already accounted for in the events
{[σ̂1 , σ̂2 , σ̂3 , σ̂4 ] = [2, 1, 3, 4]}∪{[σ̂1 , σ̂2 , σ̂3 , σ̂4 ] = [1, 2, 4, 3]}
with r = 2.
As the result, in order to avoid double counting, in calculating the value of (4) for each r we should only consider the
sets of sequences which produce a single cycle of length r.
Hence, we can upper bound the probability of error in (4) as
(where we drop the conditioning for ease of notation)
#
" r
An X

X
X
Pbc(v) (i+1)cr  n
(n)
Xc(v) (i) ≥ 0
Pe ≤
P
log
Pc(v) (i)
(r)
r=2
i=1
log

c∈CAn

≤

An
X

X

error events are dominated by the set 2 incorrect distributions.
i.i.d
i.i.d
This can be seen as follows for X1n ∼ P1 , X2n ∼ P2


P1 n
P2 n
P log
(X2 ) + log
(X1 ) ≥ 0
P2
P1
n



o
X
=
exp −nD P̂1 k P1 − nD P̂2 k P2
P

x∈X

P̂1 ,Pˆ2 :
P̂1 (x) log

Pˆ2 (y) log

P2 (x)
+
P1 (x)
P1 (x)
≥0
P2 (x)

.
= e−nD(P̃ kP1 )−nD(P̃ kP2 ) = e−2nB(P1 ,P2 ) ,

where P̃ in the first equality in (8), by using the Lagrangian
method, can be shown to be equal to P̃ (x) =
√
P1 (x)P2 (x)
and subsequently the second inequality
P √
0
0
x0

P1 (x )P2 (x )

in (8) is proved.
In order to further simplify the expression in (6), we use
the following graph theoretic Lemma, the proof of which is
given in the Appendix.
Lemma 1. In a complete graph Kk (a1 , . . . , ank ) and for the
(r)
set of cycles of length r, Ck = {c1 , . . . cNr,k } we have
r
 2

a1 + . . . + a2nk 2
1
G(c1 ) + . . . G(cNr,k ) ≤
Nr,k
nk
where Nr,k , nk are the number of cycles of length r and the
number of edges in the complete graph Kk , respectively.
By Lemma 1 and (6) we can write

−n

e

Pr

i=1

B(Pc(v) (i) ,Pc(v) (bi+1c

r)

)

(5)

r=2 c∈C (r)

Pe(n) ≤

An

=

An X
X

(8)

An X
X

G(c)

r=2 c∈C (r)

An

G(c),

(6)

r=2 c∈C (r)

≤

An

An
X
Nr,An 
r=2

where r enumerates the number of incorrect matchings and
where c(i) is the i-th vertex in the cycle c. The inequality
in (5) is by
" r
#

X
Pbc(v) (i+1)cr  n
P
log
Xc(v) (i) ≥ 0
Pc(v) (i)
i=1


!t 
r


Y
Pc(v) (bi+1cr )  n 

Xc(i)
≤ exp n inf log E 
 t

Pc(v) (i)
i=1




!1/2
r
 X

Pc(v) (bi+1cr )  n 

≤ exp n
log E 
Xc(i)
(7)


Pc(v) (i)
i=1
(
)
r
X
= exp −n
B(Pc(v) (i) , Pc(v) (bi+1cr ) ) .

≤

An
X

−nB(Pi ,Pj )

In (6), we have also defined e
to be the edge weight
between vertices
(i,
j)
in
the
complete
graph KAn . Hence
P
−n ri=1 B(Pc(v) (i) ,Pc(v) (bi+1c ) )
r
G(c) = e
is the gain of cycle c.
The fact that we used t = 1/2 in (7) instead of finding the
exact optimizing t, comes from the fact that t = 1/2 is the
optimal choice for r = 2 and as we will see later, the rest of the

4r 

16
≤

a21 + . . . + a2nAn

r/2
r/2

X

e−2nB(Pi ,Pj ) 

(9)

1≤i<j≤An

r=2

P

1≤i<j≤An

e−2nB(Pi ,Pj )



qP
,
−2nB(Pi ,Pj )
1−4
e
1≤i<j≤An

(10)

where (9) is by Fact 1 (see Appendix) and

An
Nr,An
r
r (r − 1)!/2
= 
r/2 ≤ 4 .
r/2

A
(n )
n
An

2

The upper bound on the probability of error in (10) goes to
zero if
X
lim
e−2nB(Pi ,Pj ) = 0.
n→∞

i=1

(nAn )


r
2

1≤i<j≤An

As a result of Lemma 1, it can be seen from (9) that the
sum of probabilities that r ≥ 3 distributions are incorrectly
identified is dominated by the probability that only r = 2
distributions are incorrectly identified. This shows that the
most probable error event is indeed the error events with two
wrong distributions.

B. Lower bound on the probability of error
For our converse, we use the optimal ML decoder, and as a
lower bound to the probability of error in (4), we only consider
the set of error events with only two incorrect distributions,
i.e. the set of events with r = 2. In this case we have


[
Pi
Pj
Pe(n) ≥ P 
log (Xjn ) + log (Xin ) ≥ 0
Pj
Pi
1≤i<j≤An
P
2
1≤i<j≤An P [ξi,j ]
(11)
≥ P
(i,j),(j,k) P[ξi,j , ξk,l ]

error is bounded P
away from zero. As the result, we have
to have limn→∞ 1≤i<j≤An e−2nB(Pi ,Pj ) = 0, which also
matches our upper bound on probability of error in (10).
IV. C ONCLUSION
In this paper, we generalized the identification problem
to the case that the number of distributions grows with the
blocklength n. We found matching upper and lower bounds on
the probability of identification error. This result characterizes
the relation between the number of distributions and the
pairwise distance of the distributions for reliable identification.

(i,j)6=(l,k)
i6=j,l6=k

A PPENDIX

where (11) is by [9] and where


Pi
Pj
n
n
ξi,j := log (Xj ) + log (Xi ) ≥ 0 .
Pj
Pi

(12)

We first consider the case that r is an even number and then
prove
r

r(nk ) 2

We upper bound the denominator of (11) by

Pi
Pj
P[ξi,j , ξi,k ] = P log (Xjn ) + log (Xin ) ≥ 0
Pj
Pi

Pi
P
k
n
n
∩ log
(X ) + log
(X ) ≥ 0
Pk k
Pi i

Pj
Pi
≤ P log (Xjn ) + log (Xin )
Pj
Pi

Pk n
Pi
(Xkn ) + log
(Xi ) ≥ 0
+ log
Pk
Pi
(
≤ exp n inf
t

"
t #! )
Pi
Pj
Pi
Pk n
n
n
n
log E
(X ) ·
(X ) ·
(X ) ·
(X )
Pj j
Pi i
Pk k
Pi i
(
"
 12#)
Pi
n Pj
n Pi
n Pk
n
≤ exp n log E
(X )· (X )· (X )· (X )
Pj j Pi i Pk k Pi i

−1

 Nr,k r 2
r
a1 + . . . + ank 2 2 .
G(c1 ) + . . . G(cNr,k ) ≤
nk
(16)

We may drop the subscripts and use N := Nr,k and n := nk
in the following for notational ease. Our goal is to expand
the right hand side (RHS) of (16) such that all elements have
coefficient 1. Then, we parse these elements into N different
groups (details will be provided later) such that using the AM1
Pn
Qn
GM inequality (i.e., n ( i=1 ai ) n ≤ i=1 ai ) on each group,
we get one of the N terms on the LHS of (16). Before stating
the rigorous proof, we provide an example of this strategy for
the graph with k = 4 vertices shown in Fig. 1. In this example,
we consider the Lemma for r = 4 cycles (for which we have
N = 3).

a1
a5

a6

a4

a2

= exp {−nB(Pi , Pj ) − nB(Pj , Pk ) − nB(Pi , Pk )} . (13)
An upper bound for P [ξi,j , ξk,l ] can be derived accordingly.
By substituting (8) and (13) in (11) we have
Pe(n)

≥
P

1≤i<j≤An

P

i,j,k

e

−2nB(Pi ,Pj )

e−nB(Pi ,Pj )−nB(Pi ,Pk )−nB(Pk ,Pj ) +

Fig. 1: A complete graph with 4 vertices

2

P

i,j

2

e−2nB(Pi ,Pj )

2

P

e−2nB(Pi ,Pj )
!3/2
P
−2nB(P
,P
)
i
j
e
+
i,j

≥
P

8

1≤i<j≤An

qP

1≤i<j≤An

=
8+

qP

+ a21 a22 + a21 a22 + a21 a22 + a21 a22 + a21 a24 + a21 a24 + a21 a24 + a21 a24

(14)

+ a22 a23 + a22 a23 + a22 a23 + a22 a23 + a23 a24 + a23 a24 + a23 a24 + a23 a24

Θ2 = a41 + a46 + a43 + a45 + a25 a26 + a25 a26 + a21 a23 + a21 a23

e−2nB(Pi ,Pj )

e−2nB(Pi ,Pj )

1≤i<j≤An

e−2nB(Pi ,Pj )

We may expand the RHS in (16) as
2
2 a21 + . . . + a26 = Θ1 + Θ2 + Θ3 ,

Θ1 = a41 + a42 + a43 + a44 + a21 a23 + a21 a23 + a22 a24 + a22 a24

!2

1≤i<j≤An

,

a3

(15)

where (14) P
is by Lemma 1. As it can be seen from (15),
if limn→∞ 1≤i<j≤An e−2nB(Pi ,Pj ) 6= 0, the probability of

+ a21 a26 + a21 a26 + a21 a26 + a21 a26 + a21 a25 + a21 a25 + a21 a25 + a21 a25
+ a23 a26 + a23 a26 + a23 a26 + a23 a26 + a23 a25 + a23 a25 + a23 a25 + a23 a25

Θ3 = a44 + a45 + a42 + a46 + a25 a26 + a25 a26 + a22 a24 + a22 a24
+ a24 a25 + a24 a25 + a24 a25 + a24 a25 + a24 a26 + a24 a26 + a24 a26 + a24 a26
+ a22 a25 + a22 a25 + a22 a25 + a22 a25 + a22 a26 + a22 a26 + a22 a26 + a22 a26 .

It can be easily seen that if we use the AM-GM inequality
on Θ1 , Θ2 and Θ3 , we can get the lower bound equal to
24(a1 a2 a3 a4 ), 24(a1 a6 a3 a5 ) and 24(a4 a5 a2 a6 ), respectively
r
where rn 2 −1 = 24 and hence (16) holds in this example.
We proceed to prove Lemma 1 for arbitrary k and (even)
r ≥ 2. We propose the following scheme to group the elements
on the RHS of (16) and then we prove that this grouping
indeed leads to the claimed inequality in the Lemma.
Grouping scheme: For each cycle ci = {ai1 . . . , air },
we need a group of elements, Θi , from the RHS
of (16). In this regard, we consider all possible subsets
r
of
 the edges of cycle ci with 1 : 2 elements (e.g.
{ai1 }, . . . {ai1 , ai2 }, . . . {ai1 . . . , air/2 }, . . . ). For each one
of these subsets, we find the respective elements from the RHS
of (16) that is the multiplication of the elements in that subset.
For example, for the subset {ai1 , ai2 , ai3 }, we consider the
n
n
n
elements like ai1i1 ai2i2 ai3i3 for all possible ni1 , ni2 , ni3 > 0
from the RHS of (16). However, note that we do not assign
all such elements to cycle ci only. If there are l cycles of
length r that all contain {ai1 , ai2 , ai3 }, we should assign 1l of
n
n
n
the elements like ai1i1 ai2i2 ai3i3 , ni1 , ni2 , ni3 > 0 to cycle ci
(so that we can assign the same amount of elements to other
cycles with similar edges).
We state some facts, which can be easily verified:
Fact 1. In a complete graph Kk , there are N = Nr,k =
k (r−1)!
cycles of length r.
r
2
Fact 2. By expanding the RHS of (16) such that all elements
r
have coefficient 1, we end up with Nnr n 2 elements.
Fact 3. Expanding the RHS of (16) such that all elements
have coefficient 1, and finding their product yields
r

Nr
rn 2 −1
(a1 × . . . × an )( n )
.

Fact 4. In above grouping scheme each element on the RHS
of (16) is summed in exactly one group. Hence, by symmetry
r
and Fact 2, each group is the sum of rn 2 −1 elements.
(e)
(e)
Now, consider any two cycles ci = {ai1 , . . . , air }, cj =
{aj1 , . . . , ajr }. Assume that using the above grouping scheme,
we get the group of elements Θi , Θj (where by fact 3 each
r
one is the sum of rn 2 −1 elements). If we apply the AM-GM
inequality on each one of the two groups, we get


Θi ≥ rn

r
2 −1

n
ai1i1

× ... ×

n 
air1r


1
r −1
rn 2
1
r −1
rn 2



,


r
n
n 
Θj ≥ rn 2 −1 aj1j1 × . . . × ajrjr
,
Qr
nit
where t=1 ait is the product of the elements in Θi . By
symmetry of the grouping scheme for different cycles, it is
obvious that ∀t ∈ [1 : r], nit = njt . Hence nit = njt =
pt , ∀i, j ∈ [1 : N ]. i.e., we have



Θi ≥ rn

r
2 −1

api11


× . . . × apirr

1
r −1
rn 2



.

(17)

By symmetry of the grouping scheme over the elements of
each cycle, we also get that nik = nil = qi , ∀k, l ∈ [1 : r]. i.e.


Θi ≥ rn

r
2 −1

aqi1i

× ... ×


aqiri

1
r −1
rn 2



.

(18)

It can be seen from (17) and (18) that all the elements of all
groups have the same power nit = p, ∀i ∈ [1 : N ], t ∈ [1 : r].
i.e.,


Θi ≥ rn

r
2 −1

api1

× ... ×


apir

1
r −1
rn 2



.

Since each element on theQRHS of (16)Q
is assigned to one and
n
r
r
only one group and since t=1 aitit = t=1 apit is the product
of the elements of each group Θi , the product of all elements
in Θ1 +. . .+ΘN (which is equal to product ofQthe elements
in
N Qr
the expanded version of the RHS of (16)) is i=1 t=1 apit .
In addition, since each ai appears in exactly Nnr of the
cycles, by Fact 3 and a double counting argument, we have


r
Nr
Nr
p×
=
rn 2 −1 ,
n
n
r

and hence p = rn 2 −1 . Hence, the lower bound of the AM-GM
inequality on the Θ1 + . . . + ΘN , will result in
r

r

rn 2 −1 G(c1 ) + . . . + rn 2 −1 G(cNr ),
and the Lemma is proved for even r.
For odd values of r, the problem that may arise by using
the grouping strategy in its current form, is when r < k2 . In
this case, some of the terms on the RHS of (16) may contain
multiplication of ai ’s that are not present in any of the G(ci )’s.
To overcome this, take both sides to the power of 2m for the
smallest m such that rm > k2 . Then the RHS of (16) is at
most the multiplication of rm different ai ’s and on the LHS
of (16), there are 2m cycles of length r multiplied together.
By our choice of 2m, now, all possible combinations of ai ’s
on the RHS are present in at least one cycle multiplication
in the LHS. Hence, we can now continue the proof with the
same strategy as even values of r for the odd values of r.
R EFERENCES
[1] J. Neyman and E. S. Pearson, “On the problem of the most efficient tests
of statistical hypotheses,” Philosophical Transactions of the Royal Society
of London. Series A, Containing Papers of a Mathematical or Physical
Character, vol. 231, pp. 289–337, 1933.
[2] R. Blahut, “Hypothesis testing and information theory,” IEEE Transactions on Information Theory, vol. 20, no. 4, pp. 405–417, 1974.
[3] E. Tuncel, “Extensions of error exponent analysis in hypothesis testing,”
in IEEE International Symposium on Information Theory (ISIT), 2005.
[4] A. Wald, “Sequential tests of statistical hypotheses,” The Annals of
Mathematical Statistics, vol. 16, no. 2, pp. 117–186, 1945.
[5] R. Ahlswede and E. Haroutunian, “On logarithmically asymptotically
optimal testing of hypotheses and identification,” in General Theory of
Information Transfer and Combinatorics. Springer, 2006, pp. 553–571.
[6] J. Unnikrishnan, “Asymptotically optimal matching of multiple sequences
to source distributions and training sequences,” IEEE Transactions on
Information Theory, vol. 61, no. 1, pp. 452–468, 2015.
[7] S. Shahi, D. Tuninetti, and N. Devroye, “On the capacity of strong
asynchronous multiple access channels with a large number of users,” in
IEEE International Symposium on Information Theory (ISIT), July 2016,
pp. 1486–1490.
[8] X. Chen, T.-Y. Chen, and D. Guo, “Capacity of gaussian many-access
channels,” IEEE Transactions on Information Theory, vol. 63, no. 6, pp.
3516–3539, 2017.
[9] K. L. Chung and P. Erdos, “On the application of the borel-cantelli
lemma,” Transactions of the American Mathematical Society, vol. 72,
no. 1, pp. 179–186, 1952.

