[#1]

# Testing with Non-identically Distributed Samples

Shivam Garg
Harvard University
<EMAIL_ADDRESS>
&Chirag Pabbaraju
Stanford Univesity
<EMAIL_ADDRESS>
&Kirankumar Shiragur
Broad Institute of MIT & Harvard
<EMAIL_ADDRESS>
&Gregory Valiant
Stanford University
<EMAIL_ADDRESS>

###### Abstract

We examine the extent to which sublinear-sample property testing and
estimation applies to settings where samples are independently but not
identically distributed. Specifically, we consider the following
distributional property testing framework: Suppose there is a set of
distributions over a discrete support of size $k$,
$\textbf{p}_{1},\textbf{p}_{2},\ldots,\textbf{p}_{T}$, and we obtain $c$
independent draws from each distribution. Suppose the goal is to learn or test
a property of the average distribution, $\textbf{p}_{\mathrm{avg}}$. This
setup models a number of important practical settings where the individual
distributions correspond to heterogeneous entities — either individuals,
chronologically distinct time periods, spatially separated data sources, etc.
From a learning standpoint, even with $c=1$ samples from each distribution,
$\Theta(k/\varepsilon^{2})$ samples are necessary and sufficient to learn
$\textbf{p}_{\mathrm{avg}}$ to within error $\varepsilon$ in TV distance. To
test uniformity or identity — distinguishing the case that
$\textbf{p}_{\mathrm{avg}}$ is equal to some reference distribution, versus
has $\ell_{1}$ distance at least $\varepsilon$ from the reference
distribution, we show that a linear number of samples in $k$ is necessary
given $c=1$ samples from each distribution. In contrast, for $c\geq 2$, we
recover the usual sublinear sample testing of the i.i.d. setting: we show that
$O(\sqrt{k}/\varepsilon^{2}+1/\varepsilon^{4})$ samples are sufficient,
matching the optimal sample complexity in the i.i.d. case in the regime where
$\varepsilon\geq k^{-1/4}$. Additionally, we show that in the $c=2$ case,
there is a constant $\rho>0$ such that even in the linear regime with $\rho k$
samples, no tester that considers the multiset of samples (ignoring which
samples were drawn from the same $\textbf{p}_{i}$) can perform uniformity
testing.

_K_ eywords Property testing, Identity testing, Non-i.i.d samples

##  1 Introduction

The problem of estimating statistics of an unknown distribution, or
determining whether the distribution in question possesses a property of
interest has been studied by the Statistics community for well over a century.
Interest in these problems from the TCS community was sparked by the seminal
paper of Goldreich [GR00], demonstrating the surprising result that such tasks
might be accomplished given a sample size that scales _sublinearly_ with the
support of the underlying distribution. Over the subsequent 20+ years, the lay
of the land of sublinear sample property testing and estimation has largely
been worked out: for a number of natural properties of distributions (or pairs
of distributions), testing or estimation can be accomplished with a sample
size that is sublinear in the support size of the distributions in question,
and in most settings, the optimal sample complexities are now known to
constant or subconstant factors.

More recently, these questions have been revisited with an eye towards
relaxing the assumption that samples are drawn i.i.d. from the distribution in
question. The majority of such departures focused on relaxing the independence
assumption; this includes work from the robust statistics perspective where
some portion of samples may be adversarially corrupted, as well as other
models of dependent sampling.

In this work, we consider the implications of relaxing the more innocuous
seeming assumption of identical samples. Given samples drawn independently
from a collection of distributions, $\textbf{p}_{1},\ldots,\textbf{p}_{T}$,
there are a number of different questions one can ask, including estimating
properties of how the various distribution are related. Here, however, we
focus on the practically motivated question of testing or estimating
properties of the _average_ distribution
$\textbf{p}_{\mathrm{avg}}=\frac{1}{T}\sum\textbf{p}_{i}.$ To what extent is
sublinear sample testing or estimation still possible in this setting, and do
existing estimators suffice? Below, we describe several concrete practical
settings that motivate these questions.

######  Example 1.

The “Federated” Setting: Consider the setting where there are a number of
users/individuals, each with a corresponding distribution (over online
purchases, language, biometrics, etc.) and the goal is to test whether the
average distribution is close to some reference. There might be significant
heterogeneity between users, and the number of samples (i.e. amount of data)
collected from each user might be very modest, due to privacy, bandwidth, or
power considerations.

######  Example 2.

Chronological Heterogeneity: Consider a setting where samples are collected
chronologically, and the underlying distribution varies over time. Consider a
wearable technology that periodically samples biometric statistics, or
language spoken. The goal may be to test whether the average distribution is
close to some reference (with the goal of providing an early warning of
illness in the case of biometrics, or for early detection of dementia in the
case of sampling words spoken). Ideally, this test can be successfully
accomplished with far less data than would be required to _learn_. There is
significant heterogeneity across time but samples collected close together can
be regarded as being sampled from the same distribution, $\textbf{p}_{i}.$

######  Example 3.

Spatially Segregated Sampling: Consider a setting where the goal is to sample
species (of animals, bacteria, etc.) and test whether the overall distribution
is close to a reference distribution. In many such settings, the distribution
of species has significant spatial variation — the distribution of soil
bacteria in a grassy spot is quite different from the distribution in dense
forest, similarly, the distribution of wildlife observed by trail-cameras in
national parks varies according to the location of the cameras. Again, the
goal is to accomplish this statistical test with less data than would be
required to learn the underlying average distribution.

In some of these motivating settings, one may assume some structure in the
various distributions—for example in chronological settings, for most indices,
$i$, $\textbf{p}_{i}$ is similar to $\textbf{p}_{i-1}.$ Nevertheless, it is
still worth understanding whether such assumptions _must_ be leveraged.
Indeed, for _learning_ the average distribution, $\textbf{p}_{\mathrm{avg}}$,
to within total variation distance $\varepsilon$, the sample complexity is the
same as in the i.i.d. case, $O(k/\varepsilon^{2})$ where $k$ is the support
size, without any assumptions on the $\textbf{p}_{i}$s. At the highest level,
our results demonstrate that as soon as one draws at least $c=2$ samples from
each distribution, this non-identically distributed setting recovers much of
the power of sublinear-sample property testing. The caveat is that one must
design new algorithms for this setting that are cognizant of which
distribution each sample was drawn from; as we show, testers that return a
function of the multiset of examples do not suffice.

Beyond the specific problems addressed in this work, there are many obvious
directions for future work, including mapping the sample complexities for
other natural property testing and estimation problems within the framework of
non-identically distributed samples. This includes considering properties of
pairs of distributions, such as “closeness” testing, and estimating distance
metrics between distributions. Also, while studying properties of the average
distribution is a natural starting point, other summary statistics of a
collection of distributions are also worth considering. For example, in
chronological settings, one might be interested in how certain properties
change over time and properties of recently seen distributions. More broadly,
probing the robustness of sublinear sample testing from other perspectives may
yield further surprises with practical implications.

###  1.1 Summary of Results

First, we establish that in the case that we draw $c=1$ samples from each
distribution $\textbf{p}_{1},\ldots,\textbf{p}_{T}$, one _can_ learn the
average distribution with the same sample complexity as in the i.i.d. setting.
Despite this, with $c=1$ sample from each distribution, sublinear-sample
uniformity or identity testing is impossible:

######  Claim 1.1 (Learning the distribution, proof in Appendix A).

Given access to $T$ distributions, $\textbf{p}_{1},\ldots,\textbf{p}_{T}$,
each supported on a common domain of size $\leq k$, for any $\varepsilon>0,$
given $c=1$ samples drawn from each $\textbf{p}_{i}$, one can output a
distribution $\tilde{\textbf{p}}_{\mathrm{avg}}$ such that with probability at
least $2/3$,
$\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\tilde{\textbf{p}}_{\mathrm{avg}})\leq\varepsilon$,
provided $T=O(k/\varepsilon^{2})$. Furthermore, $\Omega(k/\varepsilon^{2})$
samples are necessary, even if
$\textbf{p}_{1}=\ldots=\textbf{p}_{T}=\textbf{p}_{avg}$ for such a guarantee.

######  Claim 1.2 (Impossibility result with $c=1$, proof in Appendix B).

Given access to $T\leq k/2$ distributions,
$\textbf{p}_{1},\ldots,\textbf{p}_{T}$, and $c=1$ sample drawn from each
distribution, no tester can distinguish the case that the average
distribution, $\textbf{p}_{\mathrm{avg}}$, is the uniform distribution of
support $k$, versus has total variation distance at least $1/4$ from
$\mathrm{Unif}(k)$, with probability of success greater than $2/3.$

The above impossibility of sublinear-sample testing in the case of $c=1$
sample from each distribution follows from the following simple construction,
which also provides intuition behind the positive results for $c\geq 2:$
Consider the instance where $T=k/2$, and each $\textbf{p}_{i}$ is a point mass
on a distinct element, versus the instance where each $\textbf{p}_{i}$ is a
uniform distribution over two distinct domain elements that are disjoint from
the supports of $\textbf{p}_{j}$ for $j\neq i$. In both instances, given $c=1$
sample from each distribution, one will observe $T=k/2$ distinct elements each
observed exactly once. Despite this in the second instance, $\textbf{p}_{avg}$
is uniform over support $k$, whereas in the former the average distribution
has total variation distance $1/4$ from $\mathrm{Unif}(k).$

Our main result is that with just $c=2$ samples from each distribution, we
recover the full strength of sublinear sample uniformity (and identity)
testing. The key intuition is that with two samples from each distribution, we
can count both the collision statistics within distributions, as well as the
collisions across distributions, and build an unbiased estimator for
$\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}$. We then leverage techniques from
[DGPP16] and adapt them to this setting of non-identical samples to bound the
variance of our estimator to get the following sublinear sample complexity for
uniformity testing.

######  Theorem 1.3 (Uniformity testing, proof in Section 3).

There is an absolute constant, $\alpha$, such that given access to $T$
distributions, $\textbf{p}_{1},\ldots,\textbf{p}_{T}$, each supported on a
common domain of size $\leq k$, for any $\varepsilon>0,$ provided
$T\geq\alpha(\sqrt{k}/\varepsilon^{2}+1/\varepsilon^{4})$ given $c=2$ samples
drawn from each $\textbf{p}_{i}$, there exists a testing algorithm that
succeeds with probability $2/3$ and distinguishes whether,

$\textbf{p}_{\mathrm{avg}}=\mathrm{Unif}(k)\quad\text{ versus
}\quad\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\mathrm{Unif}(k))\geq\varepsilon~{}.$

Note that when $\varepsilon\geq k^{-1/4}$, our sample complexity for
uniformity testing simplifies to $O(\sqrt{k}/\varepsilon^{2})$, which matches
the optimal sample complexity for testing uniformity in the i.i.d setting.
Since the setting of non-identical samples is a generalization of the i.i.d
setting, the lower bound of $\Omega(\sqrt{k}/\varepsilon^{2})$ for testing
uniformity in the i.i.d setting also holds in our setting, hence we get
optimal sample complexity in the regime where $\varepsilon\geq k^{-1/4}$.

Our results also hold for identity testing, through standard reduction
techniques. In particular, we can adapt the reduction from identity testing to
uniformity testing of [Gol16] to our setting with non-identical distributions,
yielding the following result on the reduction from an instance of identity
testing to an instance of uniformity testing.

######  Lemma 1.4 (Identity to uniformity testing, proof in Section 4).

Given an arbitrary reference distribution q supported on $\leq k$ elements,
there exists a pair $(\Phi_{\textbf{q}},\Psi_{\textbf{q}})$ that maps
distributions and samples over $[k]$ to distributions and samples over $[4k]$,
and satisfies the following,

  * •

For a sequence of distributions $\textbf{q}_{1},\dots,\textbf{q}_{T}$ such
that $\mathrm{avg}(\textbf{q}_{1},\dots,\textbf{q}_{T})=\textbf{q}$, the map
$\Phi_{\textbf{q}}$ satisfies,

$\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}_{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))=\textbf{u}_{4k}~{}.$

  * •

For two sequences of distributions
$\textbf{p}^{1}_{1},\dots,\textbf{p}^{1}_{T}$ and
$\textbf{p}^{2}_{1},\dots,\textbf{p}^{2}_{T}$, the map $\Phi_{\textbf{q}}$
satisfies,

$\mathrm{d_{TV}}(\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{p}_{1}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{p}^{1}_{T})),\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{p}_{1}^{2}),\dots,\Phi_{\textbf{q}}(\textbf{p}^{2}_{T})))\geq\frac{1}{4}\cdot\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}^{1},\dots,\textbf{p}^{1}_{T}),\mathrm{avg}(\textbf{p}^{2},\dots,\textbf{p}^{2}_{T}))~{}.$

The above result combined with the result for uniformity testing, immediately
yields the following result for identity testing. Our bounds for identity
testing are optimal in the worst case for large values of $\varepsilon\geq
k^{-1/4}$.

######  Corollary 1.5 (Identity testing).

There is an absolute constant, $\alpha$, such that given a reference
distribution q supported on $\leq k$ elements and $c=2$ samples from each of
$T$ distributions, $\textbf{p}_{1},\ldots,\textbf{p}_{T}$, there exists a
testing algorithm that succeeds with probability $2/3$ and distinguishes
whether,

$\textbf{p}_{\mathrm{avg}}=\textbf{q}\quad\text{ versus
}\quad\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\textbf{q})\geq\varepsilon~{},$

provided $T\geq\alpha(\sqrt{k}/\varepsilon^{2}+1/\varepsilon^{4}).$

We note that our sublinear sample testing algorithms leverage the knowledge of
which distribution each sample was drawn from. As the following theorem
asserts, this is necessary — there is a constant $\rho>0$ such that even in
the linear regime with $\rho k$ samples, there is no testing algorithm that
simply returns a function of the multiset of samples, throwing away the
information about which samples were drawn from the same distributions.

######  Theorem 1.6 (Lower bound for “pooled” estimators, proof in Section 5).

There is an absolute constant, $\rho>0$, such that given access to
distributions $\textbf{p}_{1},\ldots,\textbf{p}_{\rho k}$ supported on a
domain of size $k$, given $c=2$ samples from each of
$\textbf{p}_{1},\ldots,\textbf{p}_{\rho k}$, no tester that returns a function
of the multiset of samples (i.e. ignoring the information about which samples
were drawn from the same distributions) can distinguish the case that
$\textbf{p}_{\mathrm{avg}}=\mathrm{Unif}(k)\quad\text{ versus
}\quad\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\mathrm{Unif}(k))\geq 0.01~{}$
with success probability at least $2/3$.

Finally, we note that this interesting phase shift for different values of $c$
holds only in the non-Poisson setting. Results in the Poisson setting remain
the same as that of the i.i.d setting. In particular, if instead of $c$
samples, we are given $Poi(c)$ samples from each distribution, then even in
the case of $c=1$, we recover all testing results known in the i.i.d setting.
This follows from the following basic fact: receiving $Poi(c)$ samples from
every distribution is equivalent to receiving $Poi(cT)$ samples from the
average distribution. A more formal version of this result is stated in
Appendix C for identity testing, but such a result also holds for testing
other properties.

The techniques used to prove our upper bounds mostly involve adapting the
techniques from the i.i.d. case to our setting. Establishing the lower bound
for pooled samples is more complex, involving a new construction that might be
of independent interest. Nonetheless, more than the techniques, our main
contribution is the problem definition and the high-level takeaways. Commonly,
when collecting samples, heterogeneity invariably arises, particularly when
these samples are gathered over various time points, geographical locations,
or from different users, as highlighted in the examples discussed above. Given
this, it is natural to ask if it is okay to apply standard testers which
assume identically distributed samples. We demonstrate that while standard
testers are not directly applicable (as evidenced by our lower bound for
pooled samples), they can be effectively adapted. For example, for identity
testing, a standard estimator involves counting the number of collisions. In
contrast, our modified estimator employs a weighted collision count, assigning
different weights to collisions depending on whether they occur within samples
from identical or non-identical distributions.

##  2 Related Work

Interest from the theoretical computer science community on distribution
testing, given i.i.d sample access, was sparked by the problem of
distinguishing whether an unknown probability distribution was the uniform
distribution over support $k$, versus has total variation distance at least
$\epsilon$ from this uniform distribution. The early work [GR00] proposed a
collision-based estimator, demonstrating that testing this property could be
accomplished given significantly fewer samples than would be required to learn
the distribution in question. It was used for testing whether a bounded degree
graph is an expander. Since then, a line of work eventually pinned down the
exact sample complexity of $\Theta(\sqrt{k}/\varepsilon^{2})$ — optimal to
constant factors including the dependence on the probability of the tester
failing [Pan08, VV17, DKN14, DGPP16, DGPP17]. For a comprehensive exposition
of this line of work, we refer the reader to Chapters 2 and 3 in [Can22].

A closely related problem to uniformity testing is that of identity testing,
where the task is to determine if an unknown probability distribution, p, is
equal to versus far from a fixed reference distribution, q, given i.i.d sample
access [BFF+01]. While “instance-optimal” estimators — estimators that are
optimal for _every_ q — are known [VV17], among reference distributions
supported on $\leq k$ elements, the uniform distribution is the most difficult
to test. Beyond this, building off [DK16], [Gol16] gave a reduction from
identity testing to uniformity testing, showing that any uniformity testing
algorithm can be leveraged in a black-box fashion for identity testing. We
leverage both the high-level design of the optimal uniformity testing
algorithms, and this reduction from identity testing to uniformity testing.

Beyond uniformity testing and identity testing, there is an enormous body of
work on testing or estimating other distribution properties, including
properties of pairs of distributions, such as total variation distance and
other distance metrics. Broadly speaking, the optimal sample complexities for
these tasks are now pinned down, at least to constant factors, in this setting
where one obtains samples drawn i.i.d. from the distribution in question.

#### Beyond i.i.d samples:

The questions of learning, property testing and estimation have also been
considered in various settings that deviate from the idealized setting of
samples drawn i.i.d. from a fixed distribution. These include work from the
perspective of robust statistics, where some portion of the samples may be
adversarially corrupted (see e.g. [DKK+19, DK19, CSV17], as well as the broad
area of time-series analysis where observations are drawn from time-varying
distributions (e.g. [CZ64, KSAX10, Lam15]).

Most similar to the present paper are works that explore learning and testing
questions in various settings where there are a number of data sources, each
providing a batch of samples. In [QV18] and the followup papers [JO20, CLM20],
it is assumed that an unknown $1-\epsilon$ fraction of data sources correspond
to identical distributions, each providing a batch of $c$ i.i.d. samples, and
no assumptions are made about the samples in the remaining batches. The main
results here are are that as $c$ increases, the batches can be leveraged for
learning: specifically, the distribution of the $1-\epsilon$ fraction can be
learned to accuracy $O(\varepsilon/\sqrt{c})$. The papers [TKV17, VKVK19]
explore the setting where batches of size $c$ are drawn i.i.d. from a
collection of heterogeneous distributions, and the goal is to learn the
multiset of distributions. The punchline here is that the multiset of
distributions can be learned given asymptotically fewer draws from each
distribution than would be necessary to learn them in isolation. While the
focus in these works is on the setting where the distributions have support
size 2 (i.e. the setting corresponds to flipping coins with heterogeneous
probabilities), the results apply more broadly. The paper of Levi, Ron, and
Rubinfeld [LRR13] considered the setting of a collection of $T$ distributions
over large support size, and explored the question of testing whether all
distributions in the collection are the same, versus have significant
variation. They considered two sampling models — a “query” model where one can
adaptively choose which distribution to draw a sample from, and a weaker model
where each sample is drawn from a distribution selected uniformly at random
from the $T$ distributions. We note that in this latter model, testing
properties of the average distribution trivially reduces to the i.i.d.
setting. Later works [DK16, ABR16] improve the results obtained by [LRR13].
Finally, the paper of Aliakbarpour and Silwal [AS19] considers the setting
with a collection of distributions, and given one sample (in expectation) from
each distribution, the task is to distinguish whether all the distributions
are equal to a reference distribution, or all distributions are far from it.
In contrast, our focus is on distinguishing whether the average distribution
is equal to or far from a reference distribution. They also consider the case
where we only have sample access to the reference distribution. General non-
vacuous results are not possible in their setting given a single sample from
each distribution. To bypass this, they impose a structural condition on the
collection of distributions. We also face a similar issue and show that it can
be bypassed in our setting by drawing multiple samples from each distribution.

##  3 Uniformity testing from non-identical samples

In this section, we prove our sample complexity results for uniformity testing
in the setting of non-identical samples. Our tester for uniformity is based on
collisions and constructs an unbiased estimator for
$\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}$. As
$\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}$ equals $\frac{1}{k}$ when
$\textbf{p}_{\mathrm{avg}}$ is uniform and is larger than
$(1+\varepsilon^{2})\frac{1}{k}$ when $\textbf{p}_{\mathrm{avg}}$ is
$\varepsilon$-far from uniform, we use this separation to solve the testing
problem. The main part of the proof constitutes bounding the variance of the
estimator that we construct in order to show that it concentrates around its
mean. We adapt the proof from [DGPP16] to the setting of non-identical samples
to bound the variance of our estimator. In the remainder of this section, we
restate 1.3 and provide its complete proof.

See 1.3

###### Proof.

To test uniformity, we build an unbiased estimator for
$\|\textbf{p}_{\mathrm{avg}}\|^{2}_{2}$. In the following, we provide a
description of this estimator. For each $t\in[T]$, let $(X_{t}(1),X_{t}(2))$
denote the 2 i.i.d samples drawn from the distribution $\textbf{p}_{t}$. For
each $t\in[T]$, we define,

$\displaystyle Y_{t}=\mathds{1}[X_{t}(1)=X_{t}(2)]\text{ and
}Y_{st}=\mathds{1}[X_{t}(1)=X_{s}(1)]~{}.$

Note that $\mathbb{E}[Y_{t}]=\|\textbf{p}_{t}\|^{2}_{2}$ and
$\mathbb{E}[Y_{st}]=\langle\textbf{p}_{t},\textbf{p}_{s}\rangle$ for all
$s,t\in[T]$. Using these random variables, we define an estimator $Z$ as
follows,

$\displaystyle
Z=\frac{1}{T^{2}}\Big{(}\sum_{t\in[T]}Y_{t}+2\sum_{s<t}Y_{st}\Big{)}.$

Note that, the expectation of the random variable $Z$ is given by,

$\mathbb{E}[Z]=\frac{1}{T^{2}}\Big{(}\sum_{t\in[T]}\|\textbf{p}_{t}\|^{2}_{2}+2\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle\Big{)}=\|\textbf{p}_{\mathrm{avg}}\|^{2}_{2}~{}.$

Therefore $Z$ is an unbiased estimator for
$\|\textbf{p}_{\mathrm{avg}}\|^{2}_{2}$. In the remainder of the proof, we
bound the variance of this estimator $Z$ and use it to solve the uniformity
testing problem. Towards this, we first bound the variance.

$\displaystyle\operatorname{{Var}}[Z]$
$\displaystyle=\mathbb{E}\Big{[}\Big{(}Z-\mathbb{E}[Z]\Big{)}^{2}\Big{]}=\frac{1}{T^{4}}\mathbb{E}\Big{[}\Big{(}\sum_{t\in[T]}(Y_{t}-\mathbb{E}[Y_{t}])+2\sum_{s<t}(Y_{st}-\mathbb{E}[Y_{st}])\Big{)}^{2}\Big{]}.$

Define

$\displaystyle\hat{Y}_{t}=Y_{t}-\mathbb{E}[Y_{t}]\text{ and
}\hat{Y}_{st}=Y_{st}-\mathbb{E}[Y_{st}],$

and note that $\mathbb{E}[\hat{Y}_{t}]=0$ and $\mathbb{E}[\hat{Y}_{st}]=0$.
Rewriting the variance of $Z$ in terms of these new random variables we get
the following,

$\displaystyle\operatorname{{Var}}[Z]$
$\displaystyle=\frac{1}{T^{4}}\mathbb{E}\Big{[}\Big{(}\sum_{t\in[T]}\hat{Y}_{t}+2\sum_{s<t}\hat{Y}_{st}\Big{)}^{2}\Big{]}\leq\frac{2}{T^{4}}\mathbb{E}\Big{[}\Big{(}\sum_{t\in[T]}\hat{Y}_{t}\Big{)}^{2}+4\Big{(}\sum_{s<t}\hat{Y}_{st}\Big{)}^{2}\Big{]}$
$\displaystyle=\frac{2}{T^{4}}\Big{(}\mathbb{E}\Big{[}\Big{(}\sum_{t\in[T]}\hat{Y}_{t}\Big{)}^{2}\Big{]}+4\cdot\mathbb{E}\Big{[}\Big{(}\sum_{s<t}\hat{Y}_{st}\Big{)}^{2}\Big{]}\Big{)}$
(1)

In the second inequality, we used $(a+b)^{2}\leq 2(a^{2}+b^{2})$. In the final
inequality, we used the linearity of expectation. To bound the variance of
$Z$, we bound the terms in the final expression separately. We start with the
first term.

$\displaystyle\mathbb{E}\Big{[}\Big{(}\sum_{t\in[T]}\hat{Y}_{t}\Big{)}^{2}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{t\in[T]}\hat{Y}_{t}^{2}+2\sum_{s<t}\hat{Y}_{t}\hat{Y}_{s}\Big{]}=\sum_{t\in[T]}\mathbb{E}[\hat{Y}_{t}^{2}]+2\sum_{s<t}\mathbb{E}[\hat{Y}_{t}]\mathbb{E}[\hat{Y}_{s}]=\sum_{t\in[T]}\mathbb{E}[\hat{Y}_{t}^{2}]$
$\displaystyle=\sum_{t\in[T]}(\mathbb{E}[{Y}_{t}^{2}]-\mathbb{E}[{Y}_{t}]^{2})\leq\sum_{t\in[T]}\mathbb{E}[Y^{2}_{i}]=\sum_{t\in[T]}\mathbb{E}[Y_{t}]=\sum_{t\in[T]}\|\textbf{p}_{t}\|^{2}_{2}.$
(2)

In the first equality, we expanded the expression. In the second equality, we
used the fact that the random variables $Y_{s}$, $Y_{t}$ are independent for
all $s,t\in[T]$ and $s\neq t$. In the third equality, we used
$\mathbb{E}[\hat{Y}_{t}]=0$ for all $t\in[T]$. The fourth and fifth
inequalities are immediate. The sixth equality follows because $Y_{t}$ is an
indicator random variable. In the seventh inequality, we substituted the value
of $\mathbb{E}[Y_{t}]=\|\textbf{p}_{t}\|^{2}_{2}$. Similar to the above, we
now bound the second term of Section 3.

$\displaystyle\mathbb{E}\Big{[}\Big{(}\sum_{s<t}\hat{Y}_{st}\Big{)}^{2}\Big{]}$
$\displaystyle=\mathbb{E}\Big{[}\sum_{s<t}\sum_{a<b}\hat{Y}_{st}\hat{Y}_{ab}\Big{]}=\sum_{s<t}\mathbb{E}[\hat{Y}_{st}^{2}]+\sum_{\begin{subarray}{c}s<t\\\
a<b\\\
|\\{s,t,a,b\\}|=3\end{subarray}}\mathbb{E}[\hat{Y}_{st}\hat{Y}_{ab}]+\sum_{\begin{subarray}{c}s<t\\\
a<b\\\ |\\{s,t,a,b\\}|=4\end{subarray}}\mathbb{E}[\hat{Y}_{st}\hat{Y}_{ab}].$
(3)

In the first and second equality, we expanded and simplified the expression.
In the following, we bound each of the three terms in the above expression
separately. Consider the first term,

$\displaystyle\sum_{s<t}\mathbb{E}[\hat{Y}_{st}^{2}]$
$\displaystyle\leq\sum_{s<t}\mathbb{E}[Y_{st}^{2}]=\sum_{s<t}\mathbb{E}[Y_{st}]=\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle$
(4)

As discussed before, the first inequality follows because
$\mathbb{E}[\hat{Y}_{st}^{2}]=\mathbb{E}[{Y}_{t}^{2}]-\mathbb{E}[{Y}_{t}]^{2}\leq\mathbb{E}[{Y}_{t}^{2}]$
as $\mathbb{E}[{Y}_{t}]^{2}\geq 0$. The second equality follows because
$Y_{st}$ is an indicator random variable. Finally, in the last expression we
substituted the value of
$\mathbb{E}[Y_{st}]=\langle\textbf{p}_{t},\textbf{p}_{s}\rangle$.

For the third term in the final expression of Equation 3, observe that if the
indices $s,t,a,b$ are all distinct, the random variables $\hat{Y}_{st}$ and
$\hat{Y}_{ab}$ are independent, and hence
$\mathbb{E}[\hat{Y}_{st}\hat{Y}_{ab}]=\mathbb{E}[\hat{Y}_{st}]\mathbb{E}[\hat{Y}_{ab}]=0$
as $\mathbb{E}[\hat{Y}_{st}]=0$. Therefore all that remains is to only bound
the second term. Observe that for any 3 fixed distinct values, there are 6
possible orderings of the indices $s<t$ and $a<b$ such that the multiset
$\\{s,t,a,b\\}|$ has exactly these distinct values. Further, for each of these
orderings, the random variable $\hat{Y}_{st}\hat{Y}_{ab}$ is non-zero if and
only if the first sample at the three distinct indices is the same. Thus, we
have that,

$\displaystyle\sum_{\begin{subarray}{c}s<t\\\ a<b\\\
|\\{s,t,a,b\\}|=3\end{subarray}}\mathbb{E}[\hat{Y}_{st}\hat{Y}_{ab}]$
$\displaystyle=6\sum_{a<b<c}\sum_{l=1}^{k}p^{l}_{a}p^{l}_{b}p^{l}_{c}=6\sum_{l=1}^{k}\sum_{a<b<c}p^{l}_{a}p^{l}_{b}p^{l}_{c}\leq
6\sum_{l=1}^{k}\Big{(}\sum_{a}p^{l}_{a}\Big{)}^{3}=6\Big{\|}\sum_{a}p_{a}\Big{\|}^{3}_{3}~{}.$
(5)

Putting it all together, that is substituting Equation 4 and Equation 5 in
Equation 3 we get,

$\displaystyle\mathbb{E}\Big{[}\Big{(}\sum_{s<t}\hat{Y}_{st}\Big{)}^{2}\Big{]}$
$\displaystyle\leq\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle+6\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{3}_{3}.$

Substituting the above inequality, combined with Section 3 into Section 3, we
get the following bound for the variance of $Z$,

$\displaystyle\operatorname{{Var}}[Z]$
$\displaystyle\leq\frac{2}{T^{4}}\Big{(}\sum_{t\in[T]}\|\textbf{p}_{t}\|^{2}_{2}+4\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle+24\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{3}_{3}\Big{)}$
$\displaystyle\leq\frac{2}{T^{4}}\Big{(}2\sum_{t\in[T]}\|\textbf{p}_{t}\|^{2}_{2}+4\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle+24\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{3}_{3}\Big{)}$
$\displaystyle=\frac{4}{T^{4}}\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{2}_{2}+\frac{48}{T^{4}}\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{3}_{3}=\frac{4}{T^{2}}\Big{\|}\textbf{p}_{\mathrm{avg}}\Big{\|}^{2}_{2}+\frac{48}{T}\Big{\|}\textbf{p}_{\mathrm{avg}}\Big{\|}^{3}_{3}.$
(6)

In the third equality, we used
$2\sum_{t\in[T]}\|\textbf{p}_{t}\|^{2}_{2}+4\sum_{s<t}\langle\textbf{p}_{t},\textbf{p}_{s}\rangle=2\Big{\|}\sum_{t\in[T]}\textbf{p}_{t}\Big{\|}^{2}_{2}$.
In the final equality, we used the definition of $\textbf{p}_{\mathrm{avg}}$.
In the remainder of the proof, we use the variance bound obtained above to
solve the uniformity testing problem. We divide our remaining proof into two
cases.

#### Uniform case:

In this case, we are promised that the
$\textbf{p}_{\mathrm{avg}}=\textbf{u}_{k}$. Therefore, it is immediate that
$\mathbb{E}[Z]=\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}=\frac{1}{k}$ and
$\|\textbf{p}_{\mathrm{avg}}\|_{3}^{3}=\frac{1}{k^{2}}$, which further gives
us that,

$\displaystyle\Pr\Big{[}Z\geq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\frac{1}{k}\Big{]}$
$\displaystyle=\Pr\Big{[}Z\geq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\mathbb{E}[Z]\Big{]}\leq\frac{9}{\varepsilon^{4}\mathbb{E}[Z]^{2}}\cdot\operatorname{{Var}}[Z]=\frac{9k^{2}}{\varepsilon^{4}}\cdot\operatorname{{Var}}[Z]~{},$
$\displaystyle\leq\frac{9k^{2}}{\varepsilon^{4}}\Big{(}\frac{4}{T^{2}k}+\frac{48}{Tk^{2}}\Big{)}=\frac{36k}{\varepsilon^{4}T^{2}}+\frac{432}{T\varepsilon^{4}}~{}.$

In the first inequality, we used that $\mathbb{E}[Z]=1/k$. In the second
inequality, we used the Chebyshev’s inequality. In the third and fourth
inequality, we substituted the values of $\mathbb{E}[Z]$ and
$\operatorname{{Var}}[Z]$ respectively; to upper bound the variance we used
bounds from Section 3. In the final inequality, we simplified the expression.
Note that when $T\geq\frac{2600}{\varepsilon^{4}}$, the second term above is
smaller than $1/6$, and for $T\geq\frac{216\sqrt{k}}{\varepsilon^{2}}$, the
first term is smaller than $1/6$. Therefore, we have that, for
$T=\max\Big{(}\frac{2600}{\varepsilon^{4}},\frac{216\sqrt{k}}{\varepsilon^{2}}\Big{)}=O\Big{(}\max\Big{(}\frac{\sqrt{k}}{\varepsilon^{2}},\frac{1}{\varepsilon^{4}}\Big{)}\Big{)}$,

$\displaystyle\Pr\Big{[}Z\geq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\frac{1}{k}\Big{]}\leq
1/3~{}.$

Therefore, $Z$ is smaller than $(1+\varepsilon^{2}/3)\frac{1}{k}$ with
probability at least $2/3$ in the uniform case, that is, when
$\textbf{p}_{\mathrm{avg}}=\textbf{u}_{k}$.

#### Far from uniform case:

In this case, we are promised that,
$\|\textbf{p}_{\mathrm{avg}}-\textbf{u}_{k}\|_{1}\geq\varepsilon$, which
further implies
$\mathbb{E}[Z]=\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}=\frac{1+\alpha^{2}}{k}\geq\frac{1}{k}(1+\varepsilon^{2})$,
where
$\alpha^{2}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}k\|\textbf{p}_{\mathrm{avg}}-u\|_{2}^{2}\geq\varepsilon^{2}$.
In the following, we upper bound the probability that $Z$ takes a value
smaller than greater than $(1+\varepsilon^{2}/3)\frac{1}{k}$.

$\displaystyle\Pr\Big{[}Z\leq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\frac{1}{k}\Big{]}$
$\displaystyle=\Pr\Big{[}Z\leq\Big{(}\frac{1+\frac{\varepsilon^{2}}{3}}{1+\alpha^{2}}\Big{)}\Big{(}\frac{1+\alpha^{2}}{k}\Big{)}\Big{]}=\Pr\Big{[}Z\leq\Big{(}\frac{1+\frac{\varepsilon^{2}}{3}}{1+\alpha^{2}}\Big{)}\mathbb{E}[Z]\Big{]}$
$\displaystyle=\Pr\Big{[}Z\leq\Big{(}1-\frac{\alpha^{2}-\frac{\varepsilon^{2}}{3}}{1+\alpha^{2}}\Big{)}\mathbb{E}[Z]\Big{]}\leq\Pr\Big{[}Z\leq\Big{(}1-\frac{\alpha^{2}-\frac{\alpha^{2}}{3}}{1+\alpha^{2}}\Big{)}\mathbb{E}[Z]\Big{]}$
$\displaystyle=\Pr\Big{[}Z\leq\Big{(}1-\frac{2\alpha^{2}}{3(1+\alpha^{2})}\Big{)}\mathbb{E}[Z]\Big{]}\leq\frac{9(1+\alpha^{2})^{2}}{4\alpha^{4}\mathbb{E}[Z]^{2}}\cdot\operatorname{{Var}}[Z]=\frac{9(1+\alpha^{2})^{2}}{4\alpha^{4}\|\textbf{p}_{\mathrm{avg}}\|_{2}^{4}}\cdot\operatorname{{Var}}[Z]$
$\displaystyle\leq\frac{9(1+\alpha^{2})^{2}}{T^{2}\alpha^{4}\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}}+\frac{108(1+\alpha^{2})^{2}}{T\alpha^{4}}\cdot\frac{\Big{\|}\textbf{p}_{\mathrm{avg}}\Big{\|}^{3}_{3}}{\|\textbf{p}_{\mathrm{avg}}\|^{4}_{2}}=\frac{9k(1+\alpha^{2})}{T^{2}\alpha^{4}}+\frac{108k^{2}}{T\alpha^{4}}\cdot\Big{\|}\textbf{p}_{\mathrm{avg}}\Big{\|}^{3}_{3}.$
(7)

In the first equality, we multiplied and divided by the term $(1+\alpha^{2})$.
In the second equality, we used the definition of $\alpha$. In the third
equality, we used
$\frac{1+\frac{\varepsilon^{2}}{3}}{1+\alpha^{2}}=1-\frac{\alpha^{2}-\frac{\varepsilon^{2}}{3}}{1+\alpha^{2}}$.
In the fourth inequality, we used $\alpha^{2}\geq\varepsilon^{2}$ and in the
fifth equality, we simplified the expression. In the sixth inequality, we used
Chebyshev’s inequality. In the seventh and eighth inequality, we used
$\mathbb{E}[Z]=\|\textbf{p}_{\mathrm{avg}}\|_{2}^{2}$ and substituted the
bound on the variance of $Z$ from Section 3. In the final expression, we used
the definition of $\alpha$. To upper bound the above probability term, we next
bound each of the terms in the final expression separately. The first term
above is bounded by,

$\displaystyle\frac{9k(1+\alpha^{2})}{T^{2}\alpha^{4}}$
$\displaystyle\leq\frac{9k(1+\varepsilon^{2})}{T^{2}\varepsilon^{4}}\leq\frac{18k}{T^{2}\varepsilon^{4}}~{}.$
(8)

In the first inequality, we used the fact that for $x>0$, the function
$\frac{1+x}{x^{2}}$ is decreasing in $x$ and also
$\alpha^{2}\geq\varepsilon^{2}$. The final inequality follows because
$\varepsilon\leq 1$. To upper bound the second term in Section 3, we first
note that,

$\displaystyle\|\textbf{p}_{\mathrm{avg}}\|_{3}^{3}$
$\displaystyle=\|\textbf{p}_{\mathrm{avg}}-u+u\|_{3}^{3}=\sum_{i=1}^{k}((\textbf{p}_{\mathrm{avg}}(i)-u(i))+u(i))^{3}$
$\displaystyle=\sum_{i=1}^{k}\Big{[}(\textbf{p}_{\mathrm{avg}}(i)-u(i))^{3}+u(i)^{3}+3(\textbf{p}_{\mathrm{avg}}(i)-u(i))u(i)\textbf{p}_{\mathrm{avg}}(i)\Big{]}$
$\displaystyle=\|\textbf{p}_{\mathrm{avg}}-u\|_{3}^{3}+\frac{1}{k^{2}}+\frac{3}{k}\Big{(}\sum_{i=1}^{k}\textbf{p}_{\mathrm{avg}}(i)^{2}-\frac{1}{k}\Big{)}=\|\textbf{p}_{\mathrm{avg}}-u\|_{3}^{3}+\frac{1}{k^{2}}+\frac{3}{k}\|\textbf{p}_{\mathrm{avg}}-u\|_{2}^{2}$
$\displaystyle\leq\|\textbf{p}_{\mathrm{avg}}-u\|_{2}^{3}+\frac{3}{k}\|\textbf{p}_{\mathrm{avg}}-u\|_{2}^{2}+\frac{1}{k^{2}}=\frac{\alpha^{3}}{k^{3/2}}+\frac{3\alpha^{2}}{k^{2}}+\frac{1}{k^{2}}.$

The first five equalities follow from simple algebraic manipulation. The sixth
inequality holds because $\|\cdot\|_{3}\leq\|\cdot\|_{2}$. In the final
equality, we used the definition of $\alpha$. Thus, the second term is bounded
as,

$\displaystyle\frac{108k^{2}}{T\alpha^{4}}\cdot\Big{\|}\textbf{p}_{\mathrm{avg}}\Big{\|}^{3}_{3}$
$\displaystyle\leq\frac{108k^{2}}{T\alpha^{4}}\cdot\Big{(}\frac{\alpha^{3}}{k^{3/2}}+\frac{3\alpha^{2}}{k^{2}}+\frac{1}{k^{2}}\Big{)}=\frac{108\sqrt{k}}{T\alpha}+\frac{324}{T\alpha^{2}}+\frac{108}{T\alpha^{4}}$
$\displaystyle\leq\frac{108\sqrt{k}}{T\varepsilon}+\frac{324}{T\varepsilon^{2}}+\frac{108}{T\varepsilon^{4}},$
(9)

In the final inequality, we used $\alpha\geq\varepsilon$. Substituting
Equation 8 and Section 3 in Section 3, we get the following bound on the
probability,

$\displaystyle\Pr\Big{[}Z\leq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\frac{1}{k}\Big{]}$
$\displaystyle\leq\frac{18k}{T^{2}\varepsilon^{4}}+\frac{108\sqrt{k}}{T\varepsilon}+\frac{324}{T\varepsilon^{2}}+\frac{108}{T\varepsilon^{4}}\leq\frac{18k}{T^{2}\varepsilon^{4}}+\frac{432\sqrt{k}}{T\varepsilon^{2}}++\frac{108}{T\varepsilon^{4}}.$

Note that for $T\geq\frac{2600\sqrt{k}}{\varepsilon^{2}}$, the sum of the
first two terms is smaller than $1/6$, and for
$T\geq\frac{648}{\varepsilon^{4}}$, the last term is smaller than $1/6$. Thus,
we have that for
$T=\max\Big{(}\frac{2600\sqrt{k}}{\varepsilon^{2}},\frac{648}{\varepsilon^{4}}\Big{)}=O\Big{(}\max\Big{(}\frac{\sqrt{k}}{\varepsilon^{2}},\frac{1}{\varepsilon^{4}}\Big{)}\Big{)}$,

$\displaystyle\Pr\Big{[}Z\leq\Big{(}1+\frac{\varepsilon^{2}}{3}\Big{)}\frac{1}{k}\Big{]}\leq
1/3.$

Therefore, $Z$ is larger than $(1+\varepsilon^{2}/3)\frac{1}{k}$ with
probability at least $2/3$ in the far from uniform case, that is when
$\|\textbf{p}_{\mathrm{avg}}-\textbf{u}_{k}\|_{1}\geq\varepsilon$. In
conclusion, for
$T=O\Big{(}\frac{\sqrt{k}}{\varepsilon^{2}}+\frac{1}{\varepsilon^{4}}\Big{)}$,
we can test uniformity, that is we can separate
$\textbf{p}_{\mathrm{avg}}=\textbf{u}_{k}$ from
$\|\textbf{p}_{\mathrm{avg}}-\textbf{u}_{k}\|_{1}\geq\varepsilon$, for any
$\varepsilon>0$. We conclude the proof. ∎

##  4 Identity testing from non-identical samples

We now prove our result which reduces the problem of identity testing to
uniformity testing. Such a reduction for the i.i.d setting is already known
[Can22, Section 2.2.3], and we adapt the same reduction for the setting of
non-identical samples. In particular, we use the same reduction functions from
that of the i.i.d case and show that they work even in the case of a sequence
of changing distributions. A more formal statement of this reduction, along
with its proof for a sequence of distributions is provided below. See 1.4

###### Proof.

We divide the definition of ours maps $(\Phi_{\textbf{q}},\Psi_{\textbf{p}})$
into three parts:

$\Phi_{\textbf{q}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Phi_{\textbf{q}}^{1}\circ\Phi_{\textbf{q}}^{2}\circ\Phi_{\textbf{q}}^{3}~{}.$
$\Psi_{\textbf{q}}\stackrel{{\scriptstyle\mathrm{def}}}{{=}}\Psi_{\textbf{q}}^{1}\circ\Psi_{\textbf{q}}^{2}\circ\Psi_{\textbf{q}}^{3}~{}.$

We first define the map $\Phi_{\textbf{q}}$, which we divide into three parts
$\Phi_{\textbf{q}}^{3},\Phi_{\textbf{q}}^{2}$ and $\Phi_{\textbf{q}}^{1}$. The
map $\Phi_{\textbf{q}}^{3}:\Delta_{k}\rightarrow\Delta_{k}$ is defined as
follows,

$\Phi_{\textbf{q}}^{3}(\textbf{p})=\frac{1}{2}\textbf{p}+\frac{1}{2}\mathrm{Unif}(k)~{}.$

Let $k^{\prime}=4k$ and
$r=\Phi_{\textbf{q}}^{3}(\textbf{q})=\frac{1}{2}\textbf{q}+\frac{1}{2}\mathrm{Unif}(k)$.
The map $\Phi_{\textbf{q}}^{2}:\Delta_{k}\rightarrow\Delta_{k+1}$ is defined
as follows,

$\Phi_{\textbf{q}}^{2}(\textbf{p})(i)=\begin{cases}\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\cdot\textbf{p}(i)&\text{ for all
}i\in[k]\\\ 1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot\textbf{p}(j)&\text{ for
}i=k+1~{}.\end{cases}$ (10)

Let $s=\Phi^{2}(r)=\Phi^{2}(\Phi^{3}(\textbf{q}))$ and define
$k_{i}=k^{\prime}\cdot s(i)$ for $i\in[k+1]$. Let $S_{1},\dots,S_{k+1}$ be any
partition of $[k^{\prime}]$ such that $|S_{i}|=k_{i}$ for all $i\in[k+1]$.
Then the map $\Phi_{\textbf{q}}^{1}:\Delta_{k+1}\rightarrow\Delta_{4k}$ is
defined as follows,

$\Phi_{\textbf{q}}^{1}(\textbf{p})(i)=\frac{1}{k^{\prime}}\sum_{j\in[k+1]}\frac{\textbf{p}(j)}{s(j)}\textbf{1}(i\in
S_{j})~{}.$

Using these definitions, we now prove the two claims stated in the theorem.

#### Claim 1:

For any $t\in[T]$, let,

$x_{t}=\Phi_{\textbf{q}}^{3}(\textbf{q}_{t}),~{}y_{t}=\Phi_{\textbf{q}}^{2}(x_{t})\text{
and }z_{t}=\Phi_{\textbf{q}}^{1}(y_{t})~{}.$

In the following, we show that,

$\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))(i)=\mathrm{avg}(z_{1},\dots,z_{t})=\textbf{u}_{4k}~{}.$

We prove the above statement entry-wise, and we consider $i$th entry of the
average distribution. We divide the proof into two cases. Let $i$ be such that
$i\in S_{j}$ for some $j\in[k]$, then note that,

$\displaystyle\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))(i)$
$\displaystyle=\frac{1}{T}\sum_{t\in[T]}z_{t}(i)=\frac{1}{T}\sum_{t\in[T]}\frac{1}{k^{\prime}}\sum_{j^{\prime}\in[k+1]}\frac{y_{t}(j^{\prime})}{s(j^{\prime})}\textbf{1}(i\in
S_{j^{\prime}}),$ (11)
$\displaystyle=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{y_{t}(j)}{s(j)}=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot x_{t}(j)}{s(j)},$ (12)
$\displaystyle=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot x_{t}(j)}{\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}}}=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{x_{t}(j)}{r(j)},$
(13)
$\displaystyle=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{\frac{1}{2}\textbf{q}_{t}(j)+\frac{1}{2}\mathrm{Unif}(k)(j)}{r(j)}=\frac{1}{Tk^{\prime}}T\cdot\frac{\frac{1}{2}\textbf{q}(j)+\frac{1}{2}\mathrm{Unif}(k)(j)}{r(j)}=\frac{1}{k^{\prime}}$
(14)

In the second equality, we substituted the value
$z_{t}=\Phi_{\textbf{q}}^{1}(y_{t})$. In the third equality, we used the
assumption that $i\in S_{j}$. In the fourth and fifth inequality, we
substituted the values of $y_{t}$ and $s$ respectively. We simplified the
expression in the sixth equality and substituted the value of $x_{t}$ in the
seventh equality. In the eighth equality, we used the definition of
$\textbf{q}=\mathrm{avg}(\textbf{q}_{1},\dots,\textbf{q}_{T})$. In the final
equality, we used the definition of $r$.

Let $i\in S_{k+1}$, then note that,

$\displaystyle\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))(i)$
$\displaystyle=\frac{1}{T}\sum_{t\in[T]}z_{t}(i)=\frac{1}{T}\sum_{t\in[T]}\frac{1}{k^{\prime}}\sum_{j^{\prime}\in[k+1]}\frac{y_{t}(j^{\prime})}{s(j^{\prime})}\textbf{1}(i\in
S_{j^{\prime}}),$ (15)
$\displaystyle=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{y_{t}(k+1)}{s(k+1)}=\frac{1}{Tk^{\prime}}\sum_{t\in[T]}\frac{1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot x_{t}(j)}{s(k+1)},$ (16)
$\displaystyle=\frac{1}{Tk^{\prime}}\frac{1}{s(k+1)}\sum_{t\in[T]}\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot x_{t}(j)\right),$ (17)
$\displaystyle=\frac{1}{Tk^{\prime}}\frac{1}{s(k+1)}\cdot
T\cdot\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot\sum_{t\in[T]}\frac{x_{t}(j)}{T}\right),$
(18)
$\displaystyle=\frac{1}{k^{\prime}}\frac{1}{s(k+1)}\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot(\frac{1}{2}\textbf{q}(j)+\frac{1}{2}\mathrm{Unif}(k)(j))\right),$
(19)
$\displaystyle=\frac{1}{k^{\prime}}\frac{1}{s(k+1)}\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}}\right)=\frac{1}{k^{\prime}}\frac{1}{s(k+1)}\cdot
s(k+1)=\frac{1}{k^{\prime}}~{}.$ (20)

In the second equality, we substituted the value
$z_{t}=\Phi_{\textbf{q}}^{1}(y_{t})$. In the third equality, we used the
assumption that $i\in S_{k+1}$. In the fourth equality, we substituted the
values of $y_{t}$ and simplified the expression in the fifth and sixth
equality. In the seventh equality, substituted the value of $x_{t}$ and used
the definition of
$\textbf{q}=\mathrm{avg}(\textbf{q}_{1},\dots,\textbf{q}_{T})$. In the eighth
and ninth equality, we used the definition of $r$ and $s$ respectively.

Combining the above two derivations, we have that, for all $i\in[k+1]$,

$\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))(i)=\frac{1}{k^{\prime}}=\frac{1}{4k}~{}.$

Therefore,

$\mathrm{avg}(\Phi_{\textbf{q}}(\textbf{q}^{1}),\dots,\Phi_{\textbf{q}}(\textbf{q}_{T}))=\textbf{u}_{4k}~{}.$

#### Claim 2:

For any $t\in[T]$, let,

$x^{a}_{t}=\Phi_{\textbf{q}}^{3}(\textbf{p}^{a}_{t}),y^{a}_{t}=\Phi_{\textbf{q}}^{2}(x^{a}_{t})\text{
and }z^{a}_{t}=\Phi_{\textbf{q}}^{1}(y^{a}_{t})\text{ for }a\in\\{1,2\\}~{}.$

In the remainder of the proof, we show that

$\displaystyle\mathrm{d_{TV}}(\mathrm{avg}(z_{1}^{1},\dots,z_{T}^{1}),\mathrm{avg}(z_{1}^{2},\dots,z_{T}^{2})$
$\displaystyle=\mathrm{d_{TV}}(\mathrm{avg}(\Phi(\textbf{p}^{1}_{1}),\dots,\Phi(\textbf{p}^{1}_{T})),\mathrm{avg}(\Phi(\textbf{p}^{2}_{1}),\dots,\Phi(\textbf{p}^{1}_{T}))$
$\displaystyle\geq\frac{1}{4}\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}^{1}_{1},\dots,\textbf{p}^{1}_{T}),\mathrm{avg}(\textbf{p}^{2}_{1},\dots,\textbf{p}^{2}_{T})~{}.$

It is immediate that,

$\mathrm{d_{TV}}(\mathrm{avg}(z_{1}^{1},\dots,z_{T}^{1}),\mathrm{avg}(z_{1}^{2},\dots,z_{T}^{2})=\mathrm{d_{TV}}(\mathrm{avg}(y_{1}^{1},\dots,y_{T}^{1}),\mathrm{avg}(y_{1}^{2},\dots,y_{T}^{2}))~{}.$

Furthermore, note that for $i\in[k]$,

$\displaystyle\mathrm{avg}(y_{1}^{a},\dots,y_{T}^{a})(i)=\frac{1}{T}\sum_{t}\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\cdot x^{a}_{t}(i)=\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\cdot(\frac{1}{2}\textbf{p}^{a}_{\mathrm{avg}}(i)+\frac{1}{2}\mathrm{Unif}(k)(i))$

and,

$\displaystyle\mathrm{avg}(y_{1}^{a},\dots,y_{T}^{a})(k+1)=\frac{1}{T}\sum_{t}\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot
x^{a}_{t}(j)\right)=1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot(\frac{1}{2}\textbf{p}^{a}_{\mathrm{avg}}(j)+\frac{1}{2}\mathrm{Unif}(k)(j))~{}.$

In the following we bound
$\mathrm{d_{TV}}(\mathrm{avg}(y_{1}^{1},\dots,y_{T}^{1}),\mathrm{avg}(y_{1}^{2},\dots,y_{T}^{2}))$,
which in turn bounds the quantity
$\mathrm{d_{TV}}(\mathrm{avg}(z_{1}^{1},\dots,z_{T}^{1}),\mathrm{avg}(z_{1}^{2},\dots,z_{T}^{2})$.

$\displaystyle\mathrm{d_{TV}}(\mathrm{avg}(y_{1}^{1},\dots,y_{T}^{1}),$
$\displaystyle\mathrm{avg}(y_{1}^{2},\dots,y_{T}^{2}))$
$\displaystyle=\sum_{i\in[k]}\left|\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\cdot(\frac{1}{2}\textbf{p}^{1}_{\mathrm{avg}}(i)+\frac{1}{2}\mathrm{Unif}(k)(i))-\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\cdot(\frac{1}{2}\textbf{p}^{2}_{\mathrm{avg}}(i)+\frac{1}{2}\mathrm{Unif}(k)(i))\right|,$
$\displaystyle+\left|1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot(\frac{1}{2}\textbf{p}^{1}_{\mathrm{avg}}(j)+\frac{1}{2}\mathrm{Unif}(k)(j))-\left(1-\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\cdot(\frac{1}{2}\textbf{p}^{2}_{\mathrm{avg}}(j)+\frac{1}{2}\mathrm{Unif}(k)(j))\right)\right|,$
$\displaystyle=\sum_{i\in[k]}\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\frac{1}{2}\left|\textbf{p}^{1}_{\mathrm{avg}}(i)-\textbf{p}^{2}_{\mathrm{avg}}(i)\right|+\sum_{j\in[k]}\frac{\lfloor
k^{\prime}r(j)\rfloor}{k^{\prime}r(j)}\frac{1}{2}\left|\textbf{p}^{1}_{\mathrm{avg}}(j)-\textbf{p}^{2}_{\mathrm{avg}}(j)\right|,$
$\displaystyle=\sum_{i\in[k]}\frac{\lfloor
k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}\left|\textbf{p}^{1}_{\mathrm{avg}}(i)-\textbf{p}^{2}_{\mathrm{avg}}(i)\right|\geq\frac{1}{2}\sum_{i\in[k]}\left|\textbf{p}^{1}_{\mathrm{avg}}(i)-\textbf{p}^{2}_{\mathrm{avg}}(i)\right|~{}.$

In the first equality, we substituted the values of
$\mathrm{avg}(y_{1}^{a},\dots,y_{T}^{a})$ for $a\in\\{1,2\\}$ that were
computed earlier. In the second and third equality, we simplified the
expression. The last inequality follows because $r(i)\geq\frac{1}{2k}$,
$k^{\prime}r(i)\geq 2$ and $\lfloor k^{\prime}r(i)\rfloor\geq
k^{\prime}r(i)-1$. Putting it all together, we have that,

$\mathrm{d_{TV}}(\mathrm{avg}(\Phi(\textbf{p}^{1}_{1}),\dots,\Phi(\textbf{p}^{1}_{T})),\mathrm{avg}(\Phi(\textbf{p}^{2}_{1}),\dots,\Phi(\textbf{p}^{1}_{T}))\\\
\geq\frac{1}{4}\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}^{1}_{1},\dots,\textbf{p}^{1}_{T}),\mathrm{avg}(\textbf{p}^{2}_{1},\dots,\textbf{p}^{2}_{T})~{},$

and we conclude the proof for this case.

#### Sampling:

In the remainder of the proof, we state the maps $\Psi^{3},\Psi^{2},\Psi^{1}$
which help us generate the samples from the mapped distributions. The
definitions of these sampling maps are pretty straightforward and we state
them below to conclude the proof.

$\Psi^{3}_{\textbf{q}}:$ Given $i\in[k]$, return $i$ with probability 1/2 and
a uniformly random element of $[k]$ otherwise.

$\Psi^{2}_{\textbf{q}}:$ Given $i\in[k]$, return $i$ with probability
$\frac{\lfloor k^{\prime}r(i)\rfloor}{k^{\prime}r(i)}$ and $k+1$ otherwise.

$\Psi^{1}_{\textbf{q}}:$ Given $i\in[k+1]$, return a uniformity random element
from $S_{i}$. ∎

##  5 Lower bound for pooling-based estimators

In this section, we prove the indistinguishability result for pooling-based
estimators given in 1.6. First, observe that uniformity of the average
distribution is a symmetric property, and thus, labels of the samples do not
matter for a testing algorithm. Thus, without loss of generality, we can
assume that the testing algorithm takes as input the pooled multiset of
samples and operates only on the fingerprint of the pooled multiset (refer to
Appendix E for a formal discussion on this). Here, the fingerprint is the
count of elements that occur exactly zero times, once, twice etc. In what
follows, we will construct two sequences of distributions: one whose average
is the uniform distribution and another whose average is far from uniform.
However, we show that the total variation distance between the distributions
of their corresponding fingerprints is small, implying impossibility of
uniformity testing with pooled samples. Below, we describe the steps involved
in the proof.

#### Step 1:

We construct two sequences of distributions a and b (Definition 5.2) such that
$\mathrm{avg}(\textbf{a})$ is uniform and $\mathrm{avg}(\textbf{b})$ is far
from uniform (Claim 5.3). Moreover, these sequences are chosen in such a way
that when we draw $2$ samples from each distribution in the sequence, with
good probability no element will be observed more than $4$ times in the pooled
multiset. The building blocks needed for defining these sequences of
distributions are introduced in Lemma 5.1.

#### Step 2:

Next, we show that when we draw 2 samples from each distribution in the
sequences, the fingerprints of the pooled multisets have the same mean (Claim
5.4), and similar covariances (Claim 5.5). A minor detail here is that we show
this for the collision counts rather than fingerprints, but this is not an
issue, as one can use an invertible linear transform to convert one to the
other.

#### Step 3:

We want to eventually show that the distributions of fingerprints are close,
and hence can not be distinguished. For this, we will first show that the
distributions of these fingerprints are close, in total variation distance, to
the multivariate Gaussian distributions $G_{\textbf{a}}$ and $G_{\textbf{b}}$
of corresponding mean and covariance, that have been discretized by rounding
all probability mass to the nearest point in the integer lattice (Lemma 5.7).
We show this via a CLT (Lemma 5.6). One slight complication in proving this
CLT is that in our setting, the fingerprints no longer correspond to a
generalized multinomial distribution, and hence we cannot directly leverage
the multivariate CLT for such distributions in [VV11]. Instead, we will show
that the distribution of fingerprints is represented as a sum of independent
samples, supported on the all-zero vector, the basis vectors, and the vector
$[2,0,0,\ldots].$ Our proof essentially “splits” each distribution into the
component supported on the zero vector and the basis vectors, and a component
supported on the zero vector and the $[2,0,0,\ldots]$ vector. The portion
supported on the basis vectors _is_ a generalized multinomial, and hence is
close to the corresponding discretized Gaussian by the CLT in [VV11], and the
remaining portion is simply a binomial, scaled by a factor of $2$. We then
argue that the convolution of these distributions is close to a discretized
Gaussian.

#### Step 4:

Having shown that the distributions of fingerprints are close to corresponding
discretized multivariate Gaussian distributions, we are left with the
tractable task of showing that the TV distance between these two (discretized)
Gaussians is small. This is shown in Lemma 5.8 and relies on certain technical
results proved in Lemma 5.10 and Lemma 5.11. Here, we use the fact that the
two collision-count distributions have the same mean and similar covariances
as discussed in Step 2 above. Finally, a triangle inequality yields the
desired result (Lemma 5.9).

We start with defining some distributions which are the building blocks for
our hard instance. We will tile up these distributions over disjoint supports
to form the overall hard instance as defined in Definition 5.2.

######  Lemma 5.1 (Building block).

There exist distributions
$\textbf{p}_{1},\textbf{p}_{2},\textbf{q}_{1},\textbf{q}_{2},\textbf{r}_{1},\textbf{r}_{2},\textbf{s}_{1},\textbf{s}_{2}$,
each supported on $m$ elements, satisfying the following:

  * •

$\mathrm{avg}(\textbf{p}_{1},\textbf{p}_{2})=\mathrm{avg}(\textbf{r}_{1},\textbf{r}_{2})=\mathrm{Unif}(m)$.

  * •

$\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}_{1},\textbf{p}_{2}),\mathrm{avg}(\textbf{q}_{1},\textbf{q}_{2}))\geq\frac{1}{16\sqrt{2}}\text{
and
}\mathrm{d_{TV}}(\mathrm{avg}(\textbf{r}_{1},\textbf{r}_{2}),\mathrm{avg}(\textbf{s}_{1},\textbf{s}_{2}))\geq\frac{1}{16\sqrt{2}}~{}.$

  * •

Let
$FP(\textbf{p})=[FP(\textbf{p})_{2},FP(\textbf{p})_{3},FP(\textbf{p})_{4}]$ be
the random variable representing the tuple of counts of elements observed
exactly 2 times, 3 times and 4 times respectively, when we draw $c=2$ samples
i.i.d each from $\textbf{p}_{1}$ and $\textbf{p}_{2}$ (i.e. we obtain a total
4 samples). Note that $FP(\textbf{p})$ is supported on
$[0,0,0],[1,0,0],[0,1,0],[0,0,1],[2,0,0]$. Similarly, define
$FP(\textbf{q}),FP(\textbf{r}),FP(\textbf{s})$. Furthermore, let
$C_{\textbf{p}}=[c^{\textbf{p}}_{2},c^{\textbf{p}}_{3},c^{\textbf{p}}_{4}]$ be
the 3-dimensional vector of 2-way, 3-way and 4-way collisions observed when we
draw $c=2$ samples i.i.d each from $\textbf{p}_{1}$ and
$\textbf{p}_{2}$111$m$-way collisions also formally defined in Appendix D..
Similarly define $C_{\textbf{q}},C_{\textbf{r}},C_{\textbf{s}}$. There exists
an $\alpha\in(0,1)$ such that,

$\displaystyle\mathbb{E}(\alpha
C_{\textbf{p}}+(1-\alpha)C_{\textbf{r}})=\mathbb{E}(\alpha
C_{\textbf{q}}+(1-\alpha)C_{\textbf{s}}).$ $\displaystyle\mathbb{E}(\alpha
FP(\textbf{p})+(1-\alpha)FP(\textbf{r}))=\mathbb{E}(\alpha
FP(\textbf{q})+(1-\alpha)FP(\textbf{s}))~{}.$

###### Proof.

First, we describe the distributions
$\textbf{p}_{1},\textbf{p}_{2},\textbf{r}_{1},\textbf{r}_{2}$. Let
$\textbf{p}_{1}=\textbf{p}_{2}\in\Delta_{m}$ be the uniform distribution on
$m$ elements. Let $\textbf{r}_{1}\in\Delta_{m}$ be such that it assigns mass
$\frac{2}{m}$ each on the first $\frac{m}{2}$ elements of $[m]$. Let
$\textbf{r}_{2}\in\Delta_{m}$ be such that it assigns mass $\frac{2}{m}$ each
on the last $\frac{m}{2}$ elements of $[m]$. This is illustrated more clearly
in Figure 1(a). It is clear that
$\mathrm{avg}(\textbf{p}_{1},\textbf{p}_{2})=\mathrm{avg}(\textbf{r}_{1},\textbf{r}_{2})=\mathrm{Unif}(m)$,
and hence the first part of the lemma holds.

Next, we describe the distributions
$\textbf{q}_{1},\textbf{q}_{2},\textbf{s}_{1},\textbf{s}_{2}$. Set
$\varepsilon=\frac{1}{\sqrt{2}}$. Let $\textbf{q}_{1}\in\Delta_{m}$ be such
that $\textbf{q}_{1}$ has a mass $\frac{1+\varepsilon}{m}$ each on the first
$\frac{m}{2}$ elements, and a mass $\frac{1-\varepsilon}{m}$ each on the
remaining $\frac{m}{2}$ elements. Next, consider $\textbf{q}_{2}\in\Delta_{m}$
defined as follows: Of the first $\frac{m}{2}$ elements, $\textbf{q}_{2}$ has
mass $\frac{1-\varepsilon}{m}$ each on the first $\frac{7}{8}^{\text{th}}$
fraction, and a mass $\frac{1+\varepsilon}{m}$ each on the remaining
$\frac{1}{8}^{\text{th}}$ fraction. Similarly, of the latter $\frac{m}{2}$
elements, $\textbf{q}_{2}$ has a mass $\frac{1+\varepsilon}{m}$ each on the
first $\frac{7}{8}^{\text{th}}$ fraction, and a mass $\frac{1-\varepsilon}{m}$
each on the remaining $\frac{1}{8}^{\text{th}}$ fraction. Further, we set
$\textbf{s}_{1}=\textbf{q}_{1}$ and $\textbf{s}_{2}=\textbf{q}_{2}$. This is
illustrated more clearly in Figure 1(b).

(a) Average is uniform

(b) Average far from uniform

Figure 1: Building block for the hard instance defined in Definition 5.2.

We can readily see that
$\|\mathrm{avg}(\textbf{p}_{1},\textbf{p}_{2})-\mathrm{avg}(\textbf{q}_{1},\textbf{q}_{2})\|_{1}=\|\mathrm{avg}(\textbf{r}_{1},\textbf{r}_{2})-\mathrm{avg}(\textbf{s}_{1},\textbf{s}_{2})\|_{1}=\frac{\varepsilon}{8}$.
Recalling the definition of $\mathrm{d_{TV}}$ and that
$\varepsilon=\frac{1}{\sqrt{2}}$, the second part of the lemma holds.

Now, we prove the last part. Fix $\beta=\frac{7}{8}$. Let
$c_{2}^{\textbf{q}}$, $c_{3}^{\textbf{q}}$, $c_{4}^{\textbf{q}}$ denote the
number of $2$-way, 3-way and 4-way collisions respectively when we draw 2
samples from $\textbf{q}_{1}$ and 2 samples from $\textbf{q}_{2}$.

$\displaystyle\mathbb{E}[c_{2}^{\textbf{q}}]$
$\displaystyle=2\left[\frac{m}{2}\cdot\left(\frac{1+\varepsilon}{m}\right)^{2}+\frac{m}{2}\cdot\left(\frac{1-\varepsilon}{m}\right)^{2}\right]+$
$\displaystyle\qquad\qquad 4\left[\beta
m\cdot\left(\frac{1+\varepsilon}{m}\right)\left(\frac{1-\varepsilon}{m}\right)+\frac{(1-\beta)m}{2}\cdot\left(\left(\frac{1+\varepsilon}{m}\right)^{2}+\left(\frac{1-\varepsilon}{m}\right)^{2}\right)\right]$
$\displaystyle=\frac{1}{m}\left[(1+\varepsilon)^{2}+(1-\varepsilon)^{2}\right]+\frac{4}{m}[\beta(1-\varepsilon^{2})+(1-\beta)(1+\varepsilon^{2})]$
$\displaystyle=\frac{2}{m}\left[1+\varepsilon^{2}+2\beta-2\beta\varepsilon^{2}+2+2\varepsilon^{2}-2\beta-2\beta\varepsilon^{2}\right]=\frac{2}{m}(3\varepsilon^{2}-4\beta\varepsilon^{2}+3)=\frac{11}{2m}.$
$\displaystyle\mathbb{E}[c_{3}^{\textbf{q}}]$
$\displaystyle=4\left[\frac{(1-\beta)m}{2}\cdot\left(\left(\frac{1+\varepsilon}{m}\right)^{3}+\left(\frac{1-\varepsilon}{m}\right)^{3}\right)+\right.$
$\displaystyle\qquad\qquad\left.\frac{\beta
m}{2}\left(\left(\frac{1+\varepsilon}{m}\right)^{2}\left(\frac{1-\varepsilon}{m}\right)+\left(\frac{1+\varepsilon}{m}\right)\left(\frac{1-\varepsilon}{m}\right)^{2}\right)\right]$
$\displaystyle=\frac{4}{m^{2}}\left[(1-\beta)(1+3\varepsilon^{2})+\beta(1-\varepsilon^{2})\right]=\frac{4}{m^{2}}\left[1+3\varepsilon^{2}-\beta-3\beta\varepsilon^{2}+\beta-\beta\varepsilon^{2}\right]$
$\displaystyle=\frac{4}{m^{2}}[3\varepsilon^{2}-4\beta\varepsilon^{2}+1]=\frac{3}{m^{2}}.$
$\displaystyle\mathbb{E}[c_{4}^{\textbf{q}}]$
$\displaystyle=\frac{(1-\beta)m}{2}\left[\left(\frac{1+\varepsilon}{m}\right)^{4}+\left(\frac{1-\varepsilon}{m}\right)^{4}\right]+\beta
m\left[\left(\frac{1+\varepsilon}{m}\right)^{2}\left(\frac{1-\varepsilon}{m}\right)^{2}\right]$
$\displaystyle=\frac{1}{m^{3}}\left[(1-\beta)(1+6\varepsilon^{2}+\varepsilon^{4})+\beta(1-2\varepsilon^{2}+\varepsilon^{4})\right]$
$\displaystyle=\frac{1}{m^{3}}[1+6\varepsilon^{2}+\varepsilon^{4}-\beta-6\beta\varepsilon^{2}-\beta\varepsilon^{4}+\beta-2\beta\varepsilon^{2}+\beta\varepsilon^{4}]$
$\displaystyle=\frac{1}{m^{3}}[\varepsilon^{4}-8\beta\varepsilon^{2}+6\varepsilon^{2}+1]=\frac{3}{4m^{3}}.$

Since $\textbf{q}_{1}=\textbf{s}_{1}$ and $\textbf{q}_{2}=\textbf{s}_{2}$, for
any $\alpha\in(0,1)$,

$\mathbb{E}\begin{bmatrix}c_{2}^{\textbf{q}}\\\ c_{3}^{\textbf{q}}\\\
c_{4}^{\textbf{q}}\end{bmatrix}=\mathbb{E}\begin{bmatrix}c_{2}^{\textbf{s}}\\\
c_{3}^{\textbf{s}}\\\
c_{4}^{\textbf{s}}\end{bmatrix}=\mathbb{E}\begin{bmatrix}\alpha
c_{2}^{\textbf{q}}+(1-\alpha)c_{2}^{\textbf{s}}\\\ \alpha
c_{3}^{\textbf{q}}+(1-\alpha)c_{3}^{\textbf{s}}\\\ \alpha
c_{4}^{\textbf{q}}+(1-\alpha)c_{4}^{\textbf{s}}\end{bmatrix}=\begin{bmatrix}11/2m\\\
3/m^{2}\\\ 3/4m^{3}\end{bmatrix}.$

Now, set $\alpha=\frac{3}{4}$. Say we toss a coin with bias $\alpha$. If we
observe heads, we will draw two samples each from $\textbf{p}_{1}$ and
$\textbf{p}_{2}$. If we observe tails, we will draw two samples each from
$\textbf{r}_{1}$ and $\textbf{r}_{2}$. We can calculate the expected number of
$2$-way, 3-way and 4-way collisions in the 4 samples obtained via this random
process.

$\displaystyle\mathbb{E}[\alpha
c_{2}^{\textbf{p}}+(1-\alpha)c_{2}^{\textbf{r}}]$
$\displaystyle=\alpha\cdot\binom{4}{2}\cdot\frac{1}{m}+(1-\alpha)\cdot\left(\frac{2}{m}+\frac{2}{m}\right)=\frac{2\alpha+4}{m}=\frac{11}{2m}.$
$\displaystyle\mathbb{E}[\alpha
c_{3}^{\textbf{p}}+(1-\alpha)c_{3}^{\textbf{r}}]$
$\displaystyle=\frac{4\alpha}{m^{2}}=\frac{3}{m^{2}}.$
$\displaystyle\mathbb{E}[\alpha
c_{4}^{\textbf{p}}+(1-\alpha)c_{4}^{\textbf{r}}]$
$\displaystyle=\frac{\alpha}{m^{3}}=\frac{3}{4m^{3}}.$

These are precisely the expressions for the expectations above. Thus, we have
just shown that

$\displaystyle\mathbb{E}\begin{bmatrix}\alpha
c_{2}^{\textbf{q}}+(1-\alpha)c_{2}^{\textbf{s}}\\\ \alpha
c_{3}^{\textbf{q}}+(1-\alpha)c_{3}^{\textbf{s}}\\\ \alpha
c_{4}^{\textbf{q}}+(1-\alpha)c_{4}^{\textbf{s}}\end{bmatrix}=\mathbb{E}\begin{bmatrix}\alpha
c_{2}^{\textbf{p}}+(1-\alpha)c_{2}^{\textbf{r}}\\\ \alpha
c_{3}^{\textbf{p}}+(1-\alpha)c_{3}^{\textbf{r}}\\\ \alpha
c_{4}^{\textbf{p}}+(1-\alpha)c_{4}^{\textbf{r}}\end{bmatrix}.$

Recalling the linear relation between the collision counts and the fingerprint
from Lemma D.1, and by linearity of expectation, we obtain the third part of
the lemma. ∎

######  Remark 1.

Note that as we draw only 4 samples from the building block given above, the
number of elements that occur exactly zero times and exactly once are a
deterministic function of the number of elements that occur exactly 2,3 and 4
times. Furthermore, since we will tile up the above instance over disjoint
supports of $m$ elements, no element will ever occur more than 4 times. Thus,
we restrict our attention only to the fingerprint of elements appearing
exactly 2,3 and 4 times, and the number of unseen and unique elements is fixed
as a deterministic function of these.

Now, using this building block, we propose two sequences of distributions
$\textbf{a}=(\textbf{a}_{1},\cdots,\textbf{a}_{T})$ and
$\textbf{b}=(\textbf{b}_{1},\cdots,\textbf{b}_{T})$ such that
$\mathrm{avg}(\textbf{a})$ is uniform and $\mathrm{avg}(\textbf{b})$ is far
from uniform. Let $FP(\textbf{a})$ and $FP(\textbf{b})$ denote the random
variables distributed according to the corresponding fingerprint distributions
over the entire sequence of samples.

######  Definition 5.2.

Let us break up the support $[k]$ into $n$ disjoint blocks, each of size $m$.
Thus, $k=mn$. Each block will correspond to the support of $2$ distributions
in a sequence, so that the total number of distributions $T=2n$.

First, we specify each block in the first $\alpha n$ many blocks (where
$\alpha=\frac{3}{4}$ and $n$ will be some multiple of 4) — fix the
$i^{\text{th}}$ such block of size $m$, where $1\leq i\leq\alpha n$. Let
$\textbf{p}_{1}^{i},\textbf{p}_{2}^{i},\textbf{q}_{1}^{i},\textbf{q}_{2}^{i}$
correspond to distributions
$\textbf{p}_{1},\textbf{p}_{2},\textbf{q}_{1},\textbf{q}_{2}$ respectively (as
defined in Lemma 5.1), supported on this block. For the first distribution
supported on this block, that is for $t=2i-1$, we will set
$\textbf{a}_{2i-1}=\textbf{p}_{1}^{i},\textbf{b}_{2i-1}=\textbf{q}_{1}^{i}$.
For the second distribution supported on this block, that is for $t=2i$, we
will set
$\textbf{a}_{2i}=\textbf{p}_{2}^{i},\textbf{b}_{2i}=\textbf{q}_{2}^{i}$.

Now, we specify each block in the remaining $(1-\alpha)n$ many blocks — fix
the $i^{\text{th}}$ such block of size $m$, where $\alpha n+1\leq i\leq n$.
Let
$\textbf{r}_{1}^{i},\textbf{r}_{2}^{i},\textbf{s}_{1}^{i},\textbf{s}_{2}^{i}$
correspond to distributions
$\textbf{r}_{1},\textbf{r}_{2},\textbf{s}_{1},\textbf{s}_{2}$ respectively (as
defined in Lemma 5.1), supported on this block. For the first distribution
supported on this block, that is for $t=2i-1$, we will set
$\textbf{a}_{2i-1}=\textbf{r}_{1}^{i},\textbf{b}_{2i-1}=\textbf{s}_{1}^{i}$.
For the second distribution supported on this block, that is for $t=2i$, we
will set
$\textbf{a}_{2i}=\textbf{r}_{2}^{i},\textbf{b}_{2i}=\textbf{s}_{2}^{i}$.

In the proof below, we will assume that $k$ is large enough and $m$ is a large
constant independent of $k$. $k$ being large enough and $m$ being a constant
ensures that $T=2n=\Theta(k)$ is also large enough.

######  Claim 5.3.

$\mathrm{avg}(\textbf{a})$ is uniform on $[k]=[mn]$ and
$\mathrm{avg}(\textbf{b})$ is far from uniform, with
$\mathrm{d_{TV}}(\mathrm{Unif}(k),\mathrm{avg}(\textbf{b}))=\frac{1}{16\sqrt{2}}$.

###### Proof.

Observe that from Lemma 5.1, in every block $1\leq i\leq n$,
$\mathrm{avg}(\textbf{a}_{2i-1},\textbf{a}_{2i})=\mathrm{Unif}(m)$.
Furthermore, since all blocks have disjoint supports of size $m$, we conclude
that
$\mathrm{avg}(\textbf{a})=\mathrm{avg}(\textbf{a}_{1},\dots,\textbf{a}_{2n})=\textbf{u}_{mn}=\mathrm{Unif}(k)$.

Also, from Lemma 5.1, in every block $1\leq i\leq n$,
$\|\mathrm{avg}(\textbf{a}_{2i-1},\textbf{a}_{2i})-\mathrm{avg}(\textbf{b}_{2i-1},\textbf{b}_{2i})\|_{1}=\frac{1}{8\sqrt{2}}$.
This immediately gives us
$\|\mathrm{avg}(\textbf{a}_{1},\textbf{a}_{2n})-\mathrm{avg}(\textbf{b}_{1},\textbf{b}_{2n})\|_{1}=\frac{1}{8\sqrt{2}}$.
Thus,
$\mathrm{d_{TV}}(\mathrm{avg}(\textbf{a}),\mathrm{avg}(\textbf{b}))=\mathrm{d_{TV}}(\mathrm{Unif}(k),\mathrm{avg}(\textbf{b}))=\frac{1}{16\sqrt{2}}$.
∎

######  Claim 5.4 (Means match).

Let $C_{\textbf{a}}$ and $C_{\textbf{b}}$ be the 3-dimensional vectors of
2-way, 3-way and 4-way collisions observed for the sequences a and b
respectively over all the $n$ blocks. Then,

$\mathbb{E}\left[C_{\textbf{a}}\right]=\mathbb{E}\left[C_{\textbf{b}}\right].$

###### Proof.

Let $C_{\textbf{a}_{i}}$ be the 3-dimensional vector of 2-way, 3-way and 4-way
collisions observed for a in the $i^{\text{th}}$ block (i.e. 2 samples each
from $\textbf{a}_{2i-1}$ and $\textbf{a}_{2i}$). Similarly, define
$C_{\textbf{b}_{i}}$. Then, the total number of 2-way, 3-way and 4-way
collision across all $n$ blocks will be $\sum_{i\in[n]}C_{\textbf{a}_{i}}$ and
$\sum_{i\in[n]}C_{\textbf{b}_{i}}$. Now, recall that exactly $\alpha n$ many
blocks are of one kind, where each $C_{\textbf{a}_{i}}=C_{\textbf{p}}$
(respectively, $C_{\textbf{b}_{i}}=C_{\textbf{q}}$) independently, and the
remaining $(1-\alpha)n$ many blocks are of the second kind, where each
$C_{\textbf{a}_{i}}=C_{\textbf{r}}$ (respectively,
$C_{\textbf{b}_{i}}=C_{\textbf{s}}$) independently. Thus we have that

$\displaystyle\mathbb{E}\left[\sum_{i\in[n]}C_{\textbf{a}_{i}}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{\alpha
n}C_{\textbf{a}_{i}}+\sum_{i=\alpha
n+1}^{n}C_{\textbf{a}_{i}}\right]=n(\mathbb{E}[\alpha
C_{\textbf{p}}+(1-\alpha)C_{\textbf{r}}])$ $\displaystyle=n(\mathbb{E}[\alpha
C_{\textbf{q}}+(1-\alpha)C_{\textbf{s}}])\qquad\text{(from
\lx@cref{creftypecap~refnum}{lem:lb_builder})}$
$\displaystyle=\mathbb{E}\left[\sum_{i=1}^{\alpha
n}C_{\textbf{b}_{i}}+\sum_{i=\alpha
n+1}^{n}C_{\textbf{b}_{i}}\right]=\mathbb{E}\left[\sum_{i\in[n]}C_{\textbf{b}_{i}}\right].$

∎

######  Claim 5.5 (Covariances match approximately).

Let $C_{\textbf{a}}$ and $C_{\textbf{b}}$ be the 3-dimensional vectors of
2-way, 3-way and 4-way collisions observed for the sequences a and b
respectively over all the $n$ blocks. Then the covariance matrices are as
follows:

$\Sigma\left[C_{\textbf{a}}\right]=n\begin{bmatrix}\gamma_{11}/m&\gamma_{12}/m^{2}&\gamma_{13}/m^{3}\\\
\gamma_{12}/m^{2}&\gamma_{22}/m^{2}&\gamma_{23}/m^{3}\\\
\gamma_{13}/m^{3}&\gamma_{23}/m^{3}&\gamma_{33}/m^{3}\end{bmatrix}+n\begin{bmatrix}\alpha_{11}/m^{2}&\alpha_{12}/m^{3}&\alpha_{13}/m^{4}\\\
\alpha_{12}/m^{3}&\alpha_{22}/m^{3}&\alpha_{23}/m^{4}\\\
\alpha_{13}/m^{4}&\alpha_{23}/m^{4}&\alpha_{33}/m^{4}\end{bmatrix},$
$\Sigma\left[C_{\textbf{b}}\right]=n\begin{bmatrix}\gamma_{11}/m&\gamma_{12}/m^{2}&\gamma_{13}/m^{3}\\\
\gamma_{12}/m^{2}&\gamma_{22}/m^{2}&\gamma_{23}/m^{3}\\\
\gamma_{13}/m^{3}&\gamma_{23}/m^{3}&\gamma_{33}/m^{3}\end{bmatrix}+n\begin{bmatrix}\alpha^{\prime}_{11}/m^{2}&\alpha^{\prime}_{12}/m^{3}&\alpha^{\prime}_{13}/m^{4}\\\
\alpha^{\prime}_{12}/m^{3}&\alpha^{\prime}_{22}/m^{3}&\alpha^{\prime}_{23}/m^{4}\\\
\alpha^{\prime}_{13}/m^{4}&\alpha^{\prime}_{23}/m^{4}&\alpha^{\prime}_{33}/m^{4}\end{bmatrix},$

with $|\alpha_{ij}|,|\alpha^{\prime}_{ij}|,|\gamma_{ij}|$ bounded by constants
independent of $m$ (for $m$ large enough).

###### Proof.

As above, we have that $C_{\textbf{a}}=\sum_{i\in[n]}C_{\textbf{a}_{i}}$ and
$C_{\textbf{b}}=\sum_{i\in[n]}C_{\textbf{b}_{i}}$, where $C_{\textbf{a}_{i}}$
is either $C_{\textbf{p}}$ or $C_{\textbf{r}}$, and $C_{\textbf{b}_{i}}$ is
either $C_{\textbf{q}}$ or $C_{\textbf{s}}$. Further, since the samples in
each block are independent, the covariances add up. Thus, we only need to
compute the covariance in one block, which we recall supports two
distributions and contributes 4 samples. Suppressing subscripts for now, we
have that

$\displaystyle\Sigma[C]$
$\displaystyle=\begin{bmatrix}\mathbb{E}[c_{2}^{2}]-\mathbb{E}[c_{2}]^{2}&\mathbb{E}[c_{2}c_{3}]-\mathbb{E}[c_{2}]\mathbb{E}[c_{3}]&\mathbb{E}[c_{2}c_{4}]-\mathbb{E}[c_{2}]\mathbb{E}[c_{4}]\\\
\mathbb{E}[c_{2}c_{3}]-\mathbb{E}[c_{2}]\mathbb{E}[c_{3}]&\mathbb{E}[c_{3}^{2}]-\mathbb{E}[c_{3}]^{2}&\mathbb{E}[c_{3}c_{4}]-\mathbb{E}[c_{3}]\mathbb{E}[c_{4}]\\\
\mathbb{E}[c_{2}c_{4}]-\mathbb{E}[c_{2}]\mathbb{E}[c_{4}]&\mathbb{E}[c_{3}c_{4}]-\mathbb{E}[c_{3}]\mathbb{E}[c_{4}]&\mathbb{E}[c_{4}^{2}]-\mathbb{E}[c_{4}]^{2}\end{bmatrix}.$

Let $Y_{ab}$ be the indicator that the elements at indices $a$ and $b$
collide. Note that $1\leq a,b\leq 4$, since we have 4 samples in each block.
Then,

$\displaystyle\mathbb{E}[c^{2}_{2}]$
$\displaystyle=\mathbb{E}\left[\left(\sum_{a<b}Y_{ab}\right)\left(\sum_{i<j}Y_{ij}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{a<b}Y_{ab}^{2}+6\sum_{a<b<c}Y_{abc}+6\sum_{a<b<c<d}Y_{ab}Y_{cd}\right]$
$\displaystyle=\mathbb{E}\left[\sum_{a<b}Y_{ab}\right]+6\cdot\mathbb{E}\left[\sum_{a<b<c}Y_{abc}\right]+6\cdot\mathbb{E}[Y_{12}]\cdot\mathbb{E}[Y_{34}]$
$\displaystyle=\mathbb{E}[c_{2}]+6\cdot\mathbb{E}[c_{3}]+6\cdot\Pr[\text{first
two samples collide}]\cdot\Pr[\text{second two samples collide}].$

In a similar manner, we can obtain the following expressions for the remaining
terms:

$\displaystyle\mathbb{E}[c^{3}_{2}]=\mathbb{E}[c_{3}]+12\cdot\mathbb{E}[c_{4}]$
$\displaystyle\mathbb{E}[c_{4}^{2}]=\mathbb{E}[c_{4}]$
$\displaystyle\mathbb{E}[c_{2}c_{3}]=3\cdot\mathbb{E}[c_{3}]+12\cdot\mathbb{E}[c_{4}]$
$\displaystyle\mathbb{E}[c_{2}c_{4}]=6\cdot\mathbb{E}[c_{4}]$
$\displaystyle\mathbb{E}[c_{3}c_{4}]=4\cdot\mathbb{E}[c_{4}].$

Thus, we have expressed all the entries in the covariance matrices in terms of
just the expected number of 2-way, 3-way and 4-way collisions. We have already
computed explicit expressions for these for each of p, q, r and s in the proof
of Lemma 5.1. Plugging these in, we obtain

$\displaystyle\Sigma[C_{\textbf{p}}]$
$\displaystyle=\begin{bmatrix}\frac{6}{m}&\frac{12}{m^{2}}&\frac{6}{m^{3}}\\\
\frac{12}{m^{2}}&\frac{4}{m^{2}}&\frac{4}{m^{3}}\\\
\frac{6}{m^{3}}&\frac{4}{m^{3}}&\frac{1}{m^{3}}\end{bmatrix}+\begin{bmatrix}-\frac{6}{m^{2}}&-\frac{12}{m^{3}}&-\frac{6}{m^{4}}\\\
-\frac{12}{m^{3}}&\frac{12}{m^{3}}-\frac{16}{m^{4}}&-\frac{4}{m^{5}}\\\
-\frac{6}{m^{4}}&-\frac{4}{m^{5}}&-\frac{1}{m^{6}}\end{bmatrix}$
$\displaystyle\Sigma[C_{\textbf{r}}]$
$\displaystyle=\begin{bmatrix}\frac{4}{m}&0&0\\\ 0&0&0\\\
0&0&0\end{bmatrix}+\begin{bmatrix}\frac{8}{m^{2}}&0&0\\\ 0&0&0\\\
0&0&0\end{bmatrix}$
$\displaystyle\Sigma[C_{\textbf{q}}]=\Sigma[C_{\textbf{s}}]$
$\displaystyle=\begin{bmatrix}\frac{11}{2m}&\frac{9}{m^{2}}&\frac{9}{2m^{3}}\\\
\frac{9}{m^{2}}&\frac{3}{m^{2}}&\frac{3}{m^{3}}\\\
\frac{9}{2m^{3}}&\frac{3}{m^{3}}&\frac{3}{4m^{3}}\end{bmatrix}+\begin{bmatrix}\frac{5}{4m^{2}}&-\frac{15}{2m^{3}}&-\frac{33}{8m^{4}}\\\
-\frac{15}{2m^{3}}&\frac{9}{m^{3}}-\frac{9}{m^{4}}&-\frac{9}{4m^{5}}\\\
-\frac{33}{8m^{4}}&-\frac{9}{4m^{5}}&-\frac{9}{16m^{6}}\end{bmatrix}.$

Finally, recall that

$\displaystyle\Sigma[C_{\textbf{a}}]=\Sigma\left[\sum_{i=1}^{\alpha
n}C_{\textbf{a}_{i}}\right]+\Sigma\left[\sum_{i=\alpha
n+1}^{n}C_{\textbf{a}_{i}}\right]=\alpha
n\Sigma[C_{\textbf{p}}]+(1-\alpha)n\Sigma[C_{\textbf{r}}]$
$\displaystyle\Sigma[C_{\textbf{b}}]=\Sigma\left[\sum_{i=1}^{\alpha
n}C_{\textbf{b}_{i}}\right]+\Sigma\left[\sum_{i=\alpha
n+1}^{n}C_{\textbf{b}_{i}}\right]=\alpha
n\Sigma[C_{\textbf{q}}]+(1-\alpha)n\Sigma[C_{\textbf{s}}]$

for $\alpha=\frac{3}{4}$, and hence, substituting the values above, we get

$\displaystyle\Sigma[C_{\textbf{a}}]$
$\displaystyle=n\begin{bmatrix}\frac{11}{2m}&\frac{9}{m^{2}}&\frac{9}{2m^{3}}\\\
\frac{9}{m^{2}}&\frac{3}{m^{2}}&\frac{3}{m^{3}}\\\
\frac{9}{2m^{3}}&\frac{3}{m^{3}}&\frac{3}{4m^{3}}\end{bmatrix}+n\begin{bmatrix}-\frac{5}{2m^{2}}&-\frac{9}{m^{3}}&-\frac{9}{2m^{4}}\\\
-\frac{9}{m^{3}}&\frac{9}{m^{3}}-\frac{12}{m^{4}}&-\frac{3}{m^{5}}\\\
-\frac{9}{2m^{4}}&-\frac{3}{m^{5}}&-\frac{3}{4m^{6}}\end{bmatrix}$
$\displaystyle\Sigma[C_{\textbf{b}}]$
$\displaystyle=n\begin{bmatrix}\frac{11}{2m}&\frac{9}{m^{2}}&\frac{9}{2m^{3}}\\\
\frac{9}{m^{2}}&\frac{3}{m^{2}}&\frac{3}{m^{3}}\\\
\frac{9}{2m^{3}}&\frac{3}{m^{3}}&\frac{3}{4m^{3}}\end{bmatrix}+n\begin{bmatrix}\frac{5}{4m^{2}}&-\frac{15}{2m^{3}}&-\frac{33}{8m^{4}}\\\
-\frac{15}{2m^{3}}&\frac{9}{m^{3}}-\frac{9}{m^{4}}&-\frac{9}{4m^{5}}\\\
-\frac{33}{8m^{4}}&-\frac{9}{4m^{5}}&-\frac{9}{16m^{6}}\end{bmatrix}.$

For the terms $9/m^{3}-12/m^{4}$ and $9/m^{3}-9/m^{4}$, we can write them as
$\frac{(9-12/m)}{m^{3}}$ and $\frac{9-9/m}{m^{3}}$ respectively. Thus for $m$
large enough, we can write all the terms in the matrices in the form specified
in the claim, completing the proof. ∎

We now prove a CLT which helps us approximate the distributions of the
fingerprints by multivariate Gaussians having the same mean and covariance.

######  Lemma 5.6 (CLT).

Consider two distributions supported on $[0,0,0]$, the basis vectors, and
$[2,0,0]$, such that the probability of $[0,0,0]$ is at least $0.9999$. Then
for constant $\alpha$, and $n$ large enough, the distribution of the sum of
$\alpha n$ i.i.d samples from the first distribution and $(1-\alpha)n$ i.i.d
samples from the second distribution has total variation distance at most
$0.01$ from a Gaussian, where the mass has been discretized to the nearest
point in the integer lattice.

###### Proof.

We begin by showing that the distribution of the sum of $\ell$ i.i.d. samples
from each distribution is close, in total variation distance to the
multivariate Gaussian of corresponding mean and covariance, discretized to the
integer lattice. Consider one of the distributions, and let
$u_{0}=\Pr([0,0,0]),$ and
$u_{1}=\Pr([1,0,0]),u_{2}=\Pr([0,1,0]),u_{3}=\Pr([0,0,1]),$ and
$v=\Pr([2,0,0])$. We draw a sample from this distribution as follows: first
flip a fair coin, and if the coin lands heads, sample from the distribution
over $[0,0,0],[1,0,0],[0,1,0],[0,0,1],$ given by respective probabilities
$1-2(u_{1}+u_{2}+u_{3}),2u_{1},2u_{2},2u_{3}.$ If the coin lands tails, we
sample from the distribution over $[0,0,0],[2,0,0]$ with respective
probability $1-2v,2v.$ Note that this sampling procedure yields a sample from
the original distribution.

Given $\ell$ independent samples from this distribution sampled in this way,
let us consider the distribution of the sum of the samples, conditioned on
exactly $t$ of the $\ell$ fair coins having landed heads. Going forward, we
will assume that $t$ and $\ell-t$ are at least $\ell/4$ — by the Chernoff
bound, each of these events individually happen with probability at least
$1-\exp(-\Omega(l))$, and so by having $l$ be large enough and applying a
union bound, we lose at most a probability mass of $0.0001$ in our total
variation distance bound. Conditioned on a value of $t$, the distribution
corresponds to the convolution of $t$ independent draws from the multinomial
distribution given by the distribution corresponding to the coin landing
heads, and the distribution corresponding to the $\ell-t$ samples from the
distribution supported on $[0,0,0]$ and $[2,0,0]$, which is a binomial random
variable in the first coordinate, scaled by a factor of 2.

Leveraging a multivariate CLT (e.g. the multivariate CLT for generalized
multinomial distributions in [VV11, Theorem 4]), the distribution of the sum
of the $t$ draws from the multinomial will have total variation distance at
most $O\left(\frac{\log t}{\sigma^{1/3}}\right)$ from the multivariate
Gaussian of corresponding mean and covariance, discretized to the nearest
point in the integer lattice. Here, $\sigma^{2}$ denotes the smallest
eigenvalue of the covariance of the sum vector of the $t$ draws. Since each of
the $t$ independent draws has covariance matrix with smallest eigenvalue
bounded below by a constant, $\sigma=\Theta(\sqrt{t})$ and this distance goes
to zero as $t$ gets large.

Since the binomial is supported on lattice points, the convolution of a
binomial with a discretized Gaussian is identical to discretizing the
convolution of the binomial and (non-discretized) Gaussian. Since we have
assumed that both $t$ and $\ell-t$ are $\Theta(n)$, the convolution of the
binomial and (non-discretized) Gaussian is itself total variation distance
$o(1)$ from the distribution of the Gaussian of corresponding mean and
covariance.

Note that for large $\ell$, with probability at least $0.999$,
$t\in[\ell/2-4\sqrt{\ell},\ell/2+4\sqrt{\ell}].$ We now claim that for any $t$
in this range, the Gaussian distributions of mean and covariance corresponding
to the mean and covariance of $\ell$ samples from our distribution
_conditioned on this value of $t$_, have total variation distance at most
$0.005$ from each other. This follows from elementary bounds on the distance
between shifted multivariate Gaussians, and the assumption that the
probability of sampling $[0,0,0]$ is at least $u_{0}>0.9999$. Indeed, for each
of the coordinates, the mean shifts by at most $p\cdot 8\sqrt{\ell}$ where
$p=1-u_{0}<0.0001$ denotes the expectation of that coordinate, whereas the
standard deviation in this direction is $\approx\sqrt{p}\sqrt{\ell}$, which is
significantly greater as long as $\sqrt{p}\gg p$.

Since we have shown that the distribution of the sum from each distribution is
close to a discretized Gaussian, all that remains, is to prove that the
convolution of two discretized Gaussians is close, in total variation
distance, to the discretization of the convolution of the two Gaussians. This
is trivially true for any Gaussians in constant dimension with minimum
eigenvalue of the covariance super-constant.

∎

Let $FP(\textbf{a})$ and $FP(\textbf{b})$ be 3 dimensional random variables
containing the number of elements observed exactly 2, 3 and 4 times, for
samples drawn from a and b respectively. Let $G_{\textbf{a}}$ be a random
variable corresponding to picking a sample from gaussian with same mean and
covariance as $FP(\textbf{a})$ and rounding each coordinate to the nearest
integer. Similarly, $G_{\textbf{b}}$ corresponds to $FP(\textbf{b})$.

######  Lemma 5.7 (Fingerprints close to discretized Gaussians).

$\mathrm{d_{TV}}(FP(\textbf{a}),G_{\textbf{a}})\leq 0.01$ and
$\mathrm{d_{TV}}(FP(\textbf{b}),G_{\textbf{b}})\leq 0.01$.

###### Proof.

Recall that $FP(\textbf{a})$ and $FP(\textbf{b})$ are $3-$dimensional random
variables containing number of elements appearing exactly $2$, $3$ and $4$
times in samples drawn according to a and b respectively. Due to the structure
of a and b (see Definition 5.2), we can decompose $FP(\textbf{a})$ and
$FP(\textbf{b})$ as

$\displaystyle FP(\textbf{a})=\sum_{i=1}^{\alpha
n}FP(\textbf{p}^{i})+\sum_{i=\alpha n+1}^{n}FP(\textbf{r}^{i}),$
$\displaystyle FP(\textbf{b})=\sum_{i=1}^{\alpha
n}FP(\textbf{q}^{i})+\sum_{i=\alpha n+1}^{n}FP(\textbf{s}^{i}).$

Here, $FP(\textbf{p}^{i})$ denotes the fingerprint vector when we obtain 2
samples from $\textbf{p}_{1}^{i}$ and 2 samples from $\textbf{p}_{2}^{i}$.
Note that as we vary $i$, $FP(\textbf{p}^{i})$ corresponds to independent
samples from the same distribution. $FP(\textbf{q}^{i})$, $FP(\textbf{r}^{i})$
and $FP(\textbf{s}^{i})$ are defined analogously. Note that each of
$FP(\textbf{p}^{i})$, $FP(\textbf{q}^{i})$, $FP(\textbf{r}^{i})$ and
$FP(\textbf{s}^{i})$ are supported on $[0,0,0]$, the basis vectors and
$[2,0,0]$.

Also, note that $FP(\textbf{p}^{i})=[0,0,0]$ corresponds to the event that
when we draw $2$ samples each from $p_{1}^{i}$ and $p_{2}^{i}$, the $4$
samples so obtained are distinct. The probability of this event is equal to
$(1-1/m)(1-2/m)(1-3/m)$ which is at least $0.9999$ if we choose $m$ to be
large enough. Similarly, one can verify that for $m$ large enough constant,
for each of $FP(\textbf{q}^{i})$, $FP(\textbf{r}^{i})$ and
$FP(\textbf{s}^{i})$, the probability of these random variables being
$[0,0,0]$ is at least $0.999$.

By applying Lemma 5.6, we get
$\mathrm{d_{TV}}(FP(\textbf{a}),G_{\textbf{a}})\leq 0.01$ and
$\mathrm{d_{TV}}(FP(\textbf{b}),G_{\textbf{b}})\leq 0.01$, which completes the
proof. ∎

######  Lemma 5.8 (Discretized Gaussians are close).

$\mathrm{d_{TV}}(G_{\textbf{a}},G_{\textbf{b}})\leq 0.02$.

###### Proof.

Let $G^{\prime}_{\textbf{a}}$ be a random variable corresponding to picking a
sample from gaussian with same mean and covariance as $FP(\textbf{a})$
(without any rounding). Similarly, $G^{\prime}_{\textbf{b}}$ corresponds to
$FP(\textbf{b})$. By data processing inequality, rounding each coordinate can
only decrease the total variation distance,
$\mathrm{d_{TV}}(G_{\textbf{a}},G_{\textbf{b}})\leq\mathrm{d_{TV}}(G^{\prime}_{\textbf{a}},G^{\prime}_{\textbf{b}})$.

By Lemma D.1, given 4 samples from a finite support, there exists an
invertible linear map, say $A$, such that we can go from a vector of
fingerprints to vector of collisions by applying $A$ to the vector of
fingerprints. Since we can decompose a and b into disjoint supports from each
of which we are getting 4 samples, applying $A$ also lets us go from vector of
fingerprints to vector of collisions for samples obtained from a and b.

We apply $A$ to random variables $G^{\prime}_{\textbf{a}}$ and
$G^{\prime}_{\textbf{b}}$. Since $A$ is invertible,
$\mathrm{d_{TV}}(AG^{\prime}_{\textbf{a}},AG^{\prime}_{\textbf{b}})=\mathrm{d_{TV}}(G^{\prime}_{\textbf{a}},G^{\prime}_{\textbf{b}})$.
Here $AG^{\prime}_{\textbf{a}}$ is a 3 dimensional Gaussian random variable
with mean and covariance same as the mean and covariance of the vector
containing number of 2-way, 3-way and 4-way collisions in the samples produced
by a. $AG^{\prime}_{\textbf{b}}$ is related to b in the same fashion.

From Claim 5.4, we know that expectations of $AG^{\prime}_{\textbf{a}}$ and
$AG^{\prime}_{\textbf{b}}$ match. Let us denote the expectation by $\mu$. From
Claim 5.5, we know that covariances of $AG^{\prime}_{\textbf{b}}$ and
$AG^{\prime}_{\textbf{b}}$ are as follows:

$\Sigma(AG^{\prime}_{\textbf{a}})=\Sigma_{1}+n\begin{bmatrix}\alpha_{11}/m^{2}&\alpha_{12}/m^{3}&\alpha_{13}/m^{4}\\\
\alpha_{12}/m^{3}&\alpha_{22}/m^{3}&\alpha_{23}/m^{4}\\\
\alpha_{13}/m^{4}&\alpha_{23}/m^{4}&\alpha_{33}/m^{4}\end{bmatrix},~{}~{}~{}~{}\Sigma(AG^{\prime}_{\textbf{b}})=\Sigma_{1}+n\begin{bmatrix}\alpha^{\prime}_{11}/m^{2}&\alpha^{\prime}_{12}/m^{3}&\alpha^{\prime}_{13}/m^{4}\\\
\alpha^{\prime}_{12}/m^{3}&\alpha^{\prime}_{22}/m^{3}&\alpha^{\prime}_{23}/m^{4}\\\
\alpha^{\prime}_{13}/m^{4}&\alpha^{\prime}_{23}/m^{4}&\alpha^{\prime}_{33}/m^{4}\end{bmatrix},$

where

$\Sigma_{1}=n\begin{bmatrix}\gamma_{11}/m&\gamma_{12}/m^{2}&\gamma_{13}/m^{3}\\\
\gamma_{12}/m^{2}&\gamma_{22}/m^{2}&\gamma_{23}/m^{3}\\\
\gamma_{13}/m^{3}&\gamma_{23}/m^{3}&\gamma_{33}/m^{3}\end{bmatrix}.$

Let $G_{1}$ be a random variable distributed as a Gaussian with mean $\mu$ and
covariance $\Sigma_{1}$. From Lemma 5.11, which is a technical lemma that
bounds the TV distance between Gaussians having the same mean and similar
covariances, and is proved at the end of this section, we know
$\mathrm{d_{TV}}(G_{1},AG^{\prime}_{\textbf{a}})\leq 0.01$ and
$\mathrm{d_{TV}}(G_{1},AG^{\prime}_{\textbf{b}})\leq 0.01$ (compared to the
lemma statement there, covariances here have an additional factor of $n$ but
that does not change the TV distance). Using triangle inequality, we get
$\mathrm{d_{TV}}(AG^{\prime}_{\textbf{a}},AG^{\prime}_{\textbf{b}})\leq 0.02$.
Since
$\mathrm{d_{TV}}(G_{\textbf{a}},G_{\textbf{b}})\leq\mathrm{d_{TV}}(G^{\prime}_{\textbf{a}},G^{\prime}_{\textbf{b}})=\mathrm{d_{TV}}(AG^{\prime}_{\textbf{a}},AG^{\prime}_{\textbf{b}})$,
this completes the proof. ∎

######  Lemma 5.9 (Fingerprints are close).

$\mathrm{d_{TV}}(FP(\textbf{a}),FP(\textbf{b}))\leq 0.04$.

###### Proof.

$\mathrm{d_{TV}}(FP(\textbf{a}),FP(\textbf{b}))\leq\mathrm{d_{TV}}(FP(\textbf{a}),G_{a})+\mathrm{d_{TV}}(FP(\textbf{b}),G_{b})+\mathrm{d_{TV}}(G_{a},G_{b})$
by triangle inequality which is at most $0.04$ due to Lemma 5.7 and Lemma 5.8.
∎

With this, we have shown that the TV distance between the distribution of
fingerprints of the two sequences is small, even when the total variation
distance between the corresponding average distributions is at least some
constant. We can then invoke the Neyman-Pearson lemma [NP33], [Can22, Lemma
1.4] to say that no testing algorithm can distinguish between these two cases
with high probability. This concludes the proof of Theorem 1.6.

Finally, we prove the promised technical lemma that bounds the TV distance
between Gaussians having the same mean and similar covariances.

######  Lemma 5.10.

Let $A$ and $D$ be defined as follows:

$A=\begin{bmatrix}\alpha_{11}/m^{2}&\alpha_{12}/m^{3}&\alpha_{13}/m^{4}\\\
\alpha_{12}/m^{3}&\alpha_{22}/m^{3}&\alpha_{23}/m^{4}\\\
\alpha_{13}/m^{4}&\alpha_{23}/m^{4}&\alpha_{33}/m^{4}\end{bmatrix}\text{ and
matrix }D=\begin{bmatrix}1/m^{2}&0&0\\\ 0&1/m^{3}&0\\\
0&0&1/m^{4}\end{bmatrix},$

where $\alpha_{ij}$ are bounded by constants independent of $m$. For large
enough $m$, there exists a positive constant $\alpha$ such that,

$-\alpha D\preceq A\preceq\alpha D.$

###### Proof.

Let $v_{1}=[1,1,0]$, $v_{2}=[1,0,1]$ and $v_{3}=[0,1,1]$. Note that,

$A=\frac{\alpha_{12}}{m^{3}}v_{1}v_{1}^{T}+\frac{\alpha_{13}}{m^{4}}v_{2}v_{2}^{T}+\frac{\alpha_{23}}{m^{4}}v_{3}v_{3}^{T}+D^{\prime},$

where $D^{\prime}$ is a diagonal matrix, whose entries are as follows:

$D^{\prime}=\begin{bmatrix}\frac{\alpha_{11}}{m^{2}}-\frac{\alpha_{12}}{m^{3}}-\frac{\alpha_{13}}{m^{4}}&0&0\\\
0&\frac{\alpha_{22}}{m^{3}}-\frac{\alpha_{12}}{m^{3}}-\frac{\alpha_{23}}{m^{4}}&0\\\
0&0&\frac{\alpha_{33}}{m^{4}}-\frac{\alpha_{13}}{m^{4}}-\frac{\alpha_{23}}{m^{4}}\end{bmatrix}$
(21)

Note that, it is immediate that, $v_{1}v_{1}^{T}\preceq 2D_{1}$,
$v_{2}v_{2}^{T}\preceq 2D_{2}$ and $v_{3}v_{3}^{T}\preceq 2D_{3}$, where
matrices $D_{1},D_{2}$ and $D_{3}$ are defined as follows,

$D_{1}=\begin{bmatrix}1&0&0\\\ 0&1&0\\\
0&0&0\end{bmatrix},~{}~{}D_{2}=\begin{bmatrix}1&0&0\\\ 0&0&0\\\
0&0&1\end{bmatrix}\text{ and }D_{3}=\begin{bmatrix}0&0&0\\\ 0&1&0\\\
0&0&1\end{bmatrix}.$

Furthermore, as all $\alpha_{ij}$s are bounded by constants, we have that the
matrix $D^{\prime}$ satisfies, $D^{\prime}\preceq c\cdot D$ for some positive
constant $c$.

Combining all the above inequalities we get that,

$A=\frac{\alpha_{12}}{m^{3}}v_{1}v_{1}^{T}+\frac{\alpha_{13}}{m^{4}}v_{2}v_{2}^{T}+\frac{\alpha_{23}}{m^{4}}v_{3}v_{3}^{T}+D^{\prime}\preceq\frac{2|\alpha_{12}|}{m^{3}}D_{1}+\frac{2|\alpha_{13}|}{m^{4}}D_{2}+\frac{2|\alpha_{23}|}{m^{4}}D_{3}+c\cdot
D~{}.$

The matrix in the final expression simplifies to,

$\begin{bmatrix}\frac{c}{m^{2}}+\frac{2|\alpha_{12}|}{m^{3}}+\frac{2|\alpha_{13}|}{m^{4}}&0&0\\\
0&\frac{c}{m^{3}}+\frac{2|\alpha_{12}|}{m^{3}}+\frac{|\alpha_{23}|}{m^{4}}&0\\\
0&0&\frac{c}{m^{4}}+\frac{|\alpha_{13}|}{m^{4}}+\frac{|\alpha_{23}|}{m^{4}}\end{bmatrix}$

As all $\alpha_{ij}$s are bounded by constants, we have that the above matrix
is upper bounded by $\alpha\cdot D$ for some large constant $\alpha>0$.
Therefore $A\preceq\alpha\cdot D$.

The proof for the other side, that is $-\alpha\cdot D\preceq A$ follows
exactly the same argument when applied to $-A$ and we conclude the proof. ∎

######  Lemma 5.11.

Let $G_{1}$ be distributed as $N(\mu,\Sigma_{1})$ and $G_{2}$ be distributed
as $N(\mu,\Sigma_{2})$ where

$\Sigma_{1}=\begin{bmatrix}\gamma_{11}/m&\gamma_{12}/m^{2}&\gamma_{13}/m^{3}\\\
\gamma_{12}/m^{2}&\gamma_{22}/m^{2}&\gamma_{23}/m^{3}\\\
\gamma_{13}/m^{3}&\gamma_{23}/m^{3}&\gamma_{33}/m^{3}\end{bmatrix}\text{ and
}\Sigma_{2}=\Sigma_{1}+\begin{bmatrix}\alpha_{11}/m^{2}&\alpha_{12}/m^{3}&\alpha_{13}/m^{4}\\\
\alpha_{12}/m^{3}&\alpha_{22}/m^{3}&\alpha_{23}/m^{4}\\\
\alpha_{13}/m^{4}&\alpha_{23}/m^{4}&\alpha_{33}/m^{4}\end{bmatrix},$

for $\gamma_{ij}$ and $\alpha_{ij}$ such that $|\gamma_{ij}|$ and
$|\alpha_{ij}|$ are bounded by constants independent of $m$. Then
$\mathrm{d_{TV}}(G_{1},G_{2})\leq 0.01$, for $m$ large enough.

###### Proof.

In our proof, we show that, for a sufficiently large enough $m$, the
covariance matrices $\Sigma_{1}$ and $\Sigma_{2}$ satisfy:
$(1-\alpha/m)\Sigma_{1}\preceq\Sigma_{2}\preceq(1+\alpha/m)\Sigma_{1}$ for
some constant $\alpha>0$. Equivalently, all the eigenvalues of the matrix
$L^{-1}\Sigma_{2}(L^{T})^{-1}$ lie in the range $[1-\alpha/m,1+\alpha/m]$,
where $\Sigma_{1}=LL^{T}$ is the Cholesky decomposition of matrix
$\Sigma_{1}$. Note that, by Fact 31 in [VV10] this result immediately implies
the following upper bound on $\mathrm{d_{TV}}(G_{1},G_{2})$ between the two
Gaussian distributions,

$\displaystyle\mathrm{d_{TV}}(G_{1},G_{2})\leq\sum_{i=1}^{3}\frac{\max(\lambda_{i},\lambda^{-1}_{i})-1}{\sqrt{2\pi
e}}\leq\sum_{i=1}^{3}\frac{O(1/m)}{\sqrt{2\pi e}}\leq O(1/m)~{}.$

The above inequality holds because both the distributions $G_{1}$ and $G_{2}$
have the same mean. Now note that, for a sufficiently large $m$, we get the
desired upper bound on the $\mathrm{d_{TV}}(G_{1},G_{2})$.

Therefore to prove our lemma, all that remains is to show that,
$(1-\alpha/m)\Sigma_{1}\preceq\Sigma_{2}\preceq(1+\alpha/m)\Sigma_{1}$ for
some constant $\alpha>0$. In the remainder of the proof, we prove this claim.
First we show invertibility of $\Sigma_{1}$ and we do this by lower bounding
the absolute value of the determinant. Note that, the permutation
corresponding to the diagonal entries contributes absolute value of
$\Omega(1/m^{6})$ to the determinant, while all other permutations have
absolute value that is bounded by $O(1/m^{7})$, therefore for large enough
$m$, we have that, the absolute value of the determinant is lower bounded by
$\Omega(1/m^{6})$ and matrix $\Sigma_{1}$ is invertible. Let,

$E=\begin{bmatrix}\alpha_{11}/m^{2}&\alpha_{12}/m^{3}&\alpha_{13}/m^{4}\\\
\alpha_{12}/m^{3}&\alpha_{22}/m^{3}&\alpha_{23}/m^{4}\\\
\alpha_{13}/m^{4}&\alpha_{23}/m^{4}&\alpha_{33}/m^{4}\end{bmatrix}$ (22)

To prove the claim, we in turn show that, $-\frac{\alpha}{m}\Sigma_{1}\preceq
E\preceq\frac{\alpha}{m}\Sigma_{1}$.

By Lemma 5.10, we know that there exist constants $\alpha_{1}$ and
$\alpha_{2}$ such that, $-\alpha_{1}D\preceq E\preceq\alpha_{1}D$ and
$0\preceq\Sigma_{1}\preceq\alpha_{2}mD$, where

$D=\begin{bmatrix}1/m^{2}&0&0\\\ 0&1/m^{3}&0\\\ 0&0&1/m^{4}\end{bmatrix}$

In the following, we prove $E\preceq\frac{\alpha}{m}\Sigma_{1}$ for some
constant $\alpha>0$. We first show that $D\preceq\frac{\gamma}{m}\Sigma_{1}$
for some constant $\gamma$, as $E\preceq\alpha_{1}D$, we conclude that
$E\preceq\frac{\alpha}{m}\Sigma_{1}$. Towards this end, we now prove that
$D\preceq\frac{\gamma}{m}\Sigma_{1}$ for some constant $\gamma$. Equivalently,
we wish to show that the smallest eigenvalue of the matrix
$F=D^{-1/2}\frac{1}{m}\Sigma_{1}D^{-1/2}$ is lower bounded by some constant.
Note that $F$ is equal to,

$F=\begin{bmatrix}\gamma_{11}&\gamma_{12}/m^{1/2}&\gamma_{13}/m\\\
\gamma_{12}/m^{1/2}&\gamma_{22}&\gamma_{23}/m^{1/2}\\\
\gamma_{13}/m&\gamma_{23}/m^{1/2}&\gamma_{33}\end{bmatrix}~{}.$

Note that $F$ is a PSD matrix as $\Sigma_{1}$ is a PSD matrix. The trace of
matrix $F$ is given by,
$\mathrm{Tr}(F)=\gamma_{11}+\gamma_{22}+\gamma_{33}\in\Omega(1)$. Also, note
that for large enough $m$, the determinant of $F$ is lower bounded by
$\gamma_{11}\gamma_{22}\gamma_{33}/2\in\Omega(1)$ because the permutation
correpsonding to the diagonal entries contributes
$\gamma_{11}\gamma_{22}\gamma_{33}$ and for a large enough $m$ all the other
permutations contribute at most $\gamma_{11}\gamma_{22}\gamma_{33}/2$ in
absolute value.

Recall that trace is the sum of eigenvalues and determinant is the product of
eigenvalues, and we have just shown that both the trace and determinant are
lower bounded by positive constants. Consequently, as all the eigenvalues of
$F$ are non-negative, we immediately conclude that all the eigenvalues are
additionally lower bounded by a positive constant and we conclude that
$E\preceq\frac{\alpha}{m}\Sigma_{1}$.

The proof for the other side, that is $-\frac{\alpha}{m}\cdot\Sigma_{1}\preceq
E$ follows exactly the same argument when applied to $-E$ and we conclude the
proof.

## Acknowledgements

S.G. did part of this work at Stanford where he was supported by a Stanford
Interdisciplinary Graduate Fellowship. He is currently supported by a
postdoctoral fellowship from Harvard’s Digital Data Design Institute. C.P. is
supported by Moses Charikar and Gregory Valiant’s Simons Investigator Awards.
K.S. was supported, in part, by funding from the Eric and Wendy Schmidt Center
at the Broad Institute of MIT and Harvard. G.V. is supported, in part, by a
Simons Investigator Award.

∎

## References

  * [ABR16] Maryam Aliakbarpour, Eric Blais, and Ronitt Rubinfeld.  Learning and testing junta distributions.  In Conference on Learning Theory, pages 19–46. PMLR, 2016.
  * [AS19] Maryam Aliakbarpour and Sandeep Silwal.  Testing properties of multiple distributions with few samples.  arXiv preprint arXiv:1911.07324, 2019.
  * [BFF+01] Tugkan Batu, Eldar Fischer, Lance Fortnow, Ravi Kumar, Ronitt Rubinfeld, and Patrick White.  Testing random variables for independence and identity.  In Proceedings 42nd IEEE Symposium on Foundations of Computer Science, pages 442–451. IEEE, 2001.
  * [Can20] Clément L Canonne.  A short note on learning discrete distributions.  arXiv preprint arXiv:2002.11457, 2020.
  * [Can22] Clément L. Canonne.  Topics and techniques in distribution testing: A biased but representative sample.  Foundations and Trends® in Communications and Information Theory, 19(6):1032–1198, 2022.
  * [CLM20] Sitan Chen, Jerry Li, and Ankur Moitra.  Learning structured distributions from untrusted batches: Faster and simpler.  Advances in Neural Information Processing Systems, 33:4512–4523, 2020.
  * [CSV17] Moses Charikar, Jacob Steinhardt, and Gregory Valiant.  Learning from untrusted data.  In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pages 47–60, 2017.
  * [CZ64] Herman Chernoff and Shelemyahu Zacks.  Estimating the current mean of a normal distribution which is subjected to changes in time.  The Annals of Mathematical Statistics, 35(3):999–1018, 1964.
  * [DGPP16] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Collision-based testers are optimal for uniformity and closeness.  arXiv preprint arXiv:1611.03579, 2016.
  * [DGPP17] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Optimal identity testing with high probability.  arXiv preprint arXiv:1708.02728, 2017.
  * [DK16] Ilias Diakonikolas and Daniel M Kane.  A new approach for testing properties of discrete distributions.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 685–694. IEEE, 2016.
  * [DK19] Ilias Diakonikolas and Daniel M Kane.  Recent advances in algorithmic high-dimensional robust statistics.  arXiv preprint arXiv:1911.05911, 2019.
  * [DKK+19] Ilias Diakonikolas, Gautam Kamath, Daniel Kane, Jerry Li, Ankur Moitra, and Alistair Stewart.  Robust estimators in high-dimensions without the computational intractability.  SIAM Journal on Computing, 48(2):742–864, 2019.
  * [DKN14] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin.  Testing identity of structured distributions.  In Proceedings of the twenty-sixth annual ACM-SIAM symposium on Discrete algorithms, pages 1841–1854. SIAM, 2014.
  * [Gol16] Oded Goldreich.  The uniform distribution is complete with respect to testing identity to a fixed distribution.  In Electron. Colloquium Comput. Complex., volume 23, page 15, 2016\.
  * [GR00] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  2000\.
  * [JO20] Ayush Jain and Alon Orlitsky.  Optimal robust learning of discrete distributions from batches.  In International Conference on Machine Learning, pages 4651–4660. PMLR, 2020.
  * [KSAX10] Mladen Kolar, Le Song, Amr Ahmed, and Eric P Xing.  Estimating time-varying networks.  The Annals of Applied Statistics, pages 94–123, 2010.
  * [Lam15] Christoph H Lampert.  Predicting the future behavior of a time-varying probability distribution.  In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 942–950, 2015.
  * [LRR13] Reut Levi, Dana Ron, and Ronitt Rubinfeld.  Testing properties of collections of distributions.  Theory of Computing, 9(8):295–347, 2013.
  * [NP33] Jerzy Neyman and Egon Sharpe Pearson.  Ix. 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, 231(694-706):289–337, 1933.
  * [Pan08] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 54(10):4750–4755, 2008\.
  * [QV18] Mingda Qiao and Gregory Valiant.  Learning discrete distributions from untrusted batches.  In Anna R. Karlin, editor, 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11-14, 2018, Cambridge, MA, USA, volume 94 of LIPIcs, pages 47:1–47:20. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018.
  * [TKV17] Kevin Tian, Weihao Kong, and Gregory Valiant.  Learning populations of parameters.  Advances in neural information processing systems, 30, 2017.
  * [VKVK19] Ramya Korlakai Vinayak, Weihao Kong, Gregory Valiant, and Sham Kakade.  Maximum likelihood estimation for learning populations of parameters.  In International Conference on Machine Learning, pages 6448–6457. PMLR, 2019.
  * [VV10] Gregory Valiant and Paul Valiant.  A clt and tight lower bounds for estimating entropy.  In Electron. Colloquium Comput. Complex., volume 17, page 179, 2010\.
  * [VV11] Gregory Valiant and Paul Valiant.  Estimating the unseen: an n/log (n)-sample estimator for entropy and support size, shown optimal via new clts.  In Proceedings of the forty-third annual ACM symposium on Theory of computing, pages 685–694, 2011.
  * [VV17] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing, 46(1):429–455, 2017.

##  Appendix A Learning the average distribution

In this section, we show that the sample complexity of learning the average
distribution in the setting of non-identical samples is asymptotically equal
to that of the i.i.d. See 1.1

###### Proof.

The lower bound for the setting of non-identical samples follows directly from
the lower bound of the standard i.i.d setting, that is if we let
$\textbf{p}_{t}=\textbf{p},\forall t\in[T]$. For the upper bound, we follow
the proof in [Can20, Theorem 1]. Consider the empirical estimator given by,

$\displaystyle\tilde{\textbf{p}}_{\mathrm{avg}}(i)=\frac{1}{T}\sum_{t\in[T]}1[X_{t}=i].$

Observe that by definition,
$\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\tilde{\textbf{p}}_{\mathrm{avg}})>\varepsilon$
implies that there exists some $S\subseteq[k]$ such that
$\tilde{\textbf{p}}_{\mathrm{avg}}(S)>\textbf{p}_{\mathrm{avg}}(S)+\varepsilon$.
Fix any $S\subseteq[k]$ and we have,

$\displaystyle\tilde{\textbf{p}}_{\mathrm{avg}}(S)=\frac{1}{T}\sum_{i\in
S}\sum_{t\in T}1[X_{t}=i].$

Define $Y_{t}=\sum_{i\in S}1[X_{t}=i]$ so that
$\tilde{\textbf{p}}_{\mathrm{avg}}(S)=\frac{1}{T}\sum_{t\in[T]}Y_{t}$. Note
that, each $Y_{t}$ is a Bernoulli random variable with parameter
$\mathbb{E}[Y_{t}]=\textbf{p}_{t}(S)$. Furthermore, since samples from
different distributions are independent, all the $Y_{t}$’s are independent and
we have that,

$\displaystyle\Pr\left[\frac{1}{T}\sum_{t\in[T]}Y_{t}>\mathbb{E}\left[\frac{1}{T}\sum_{t\in[T]}Y_{t}\right]+\varepsilon\right]$
$\displaystyle=\Pr\left[\tilde{\textbf{p}}_{\mathrm{avg}}(S)>\frac{1}{T}\sum_{t\in
T}\textbf{p}_{t}(S)+\varepsilon\right]=\Pr[\tilde{\textbf{p}}_{\mathrm{avg}}(S)>\textbf{p}_{\mathrm{avg}}(S)+\varepsilon],$

and hence, letting $\mu=\mathbb{E}\left[\sum_{t\in[T]}Y_{t}\right]$, we get

$\displaystyle\Pr[\tilde{\textbf{p}}_{\mathrm{avg}}(S)>\textbf{p}_{\mathrm{avg}}(S)+\varepsilon]$
$\displaystyle=\Pr\left[\frac{1}{T}\sum_{t\in[T]}Y_{t}>\mathbb{E}\left[\frac{1}{T}\sum_{t\in[T]}Y_{t}\right]+\varepsilon\right]=\Pr\left[\sum_{t\in[T]}Y_{t}>\left(1+\frac{T\varepsilon}{\mu}\right)\mu\right]$
$\displaystyle\leq\exp\left(-\frac{T^{2}\varepsilon^{2}}{\mu(2+T\varepsilon/\mu)}\right)=\exp\left(-\frac{T^{2}\varepsilon^{2}}{2\mu+T\varepsilon}\right)\leq\exp\left(-\frac{T\varepsilon^{2}}{3}\right),$

where in the first inequality, we used the Chernoff bound, and in the last
inequality, we used the facts that $\varepsilon\leq 1,\mu\leq T$. Setting this
failure probability to $\frac{1}{3\cdot 2^{k}}$ along with the union bound
over $2^{k}$ possible values of $S$ would give us the required result, namely

$\displaystyle\Pr[\exists S\in[k]\text{ s.t.
}\tilde{\textbf{p}}_{\mathrm{avg}}(S)>\textbf{p}_{\mathrm{avg}}+\varepsilon]\leq\frac{1}{3}.$

Correspondingly,

$\displaystyle\exp\left(-\frac{T\varepsilon^{2}}{3}\right)=\frac{1}{3\cdot
2^{k}}\implies T=O(k/\varepsilon^{2}).$

We conclude the proof. ∎

##  Appendix B Impossibility Result with $c=1$

See 1.2

We prove the following equivalent claim.

######  Claim B.1.

For all $c_{1}>0$, there is a $k\geq c_{1}$ such that for any $T\leq k/2$,
given $c=1$ sample drawn from each of $\textbf{p}_{1},\dots,\textbf{p}_{T}$,
there exists no testing algorithm that succeeds with probability greater than
$1/2$ and tests whether

$\textbf{p}_{\mathrm{avg}}=\mathrm{Unif}(k)\quad\text{ versus
}\quad\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\mathrm{Unif}(k))\geq 1/4~{}.$

###### Proof.

All the logarithms in the proof below are base 2. Let $k$ be the smallest
power of $2$ greater than or equal to $c_{1}$,

$k=2^{\lceil\log c_{1}\rceil}.$

For $T\leq k/2$, let $r=k/T$, so that $r\geq 2$. We set $r^{\prime}$ to be the
smallest power of $2$ greater than or equal to $r$,

$r^{\prime}=2^{\lceil\log r\rceil}.$

Let $T^{\prime}=k/r^{\prime}$. By construction $T^{\prime}\leq T\leq k/2$, $\
T^{\prime}$ is integral, and $T^{\prime}/T\geq 1/2$.

We now consider two distributions $D_{1}$ and $D_{2}$ over sequences of
distributions $(\textbf{p}_{1}\dots\textbf{p}_{T})$ such that for all
sequences $(\textbf{p}_{1}\dots\textbf{p}_{T})$ in the support of $D_{1}$,
$\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T})=\mathrm{Unif}(k)$ and for all
sequences in the support of $D_{2}$,
$\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T}),\mathrm{Unif}(k))\geq
1/4$. Further, we will show that the samples drawn from distribution sequences
drawn from $D_{1}$ are indistinguishable from samples drawn from distribution
sequences drawn from $D_{2}$ (that is, corresponding distributions have total
variation distance $0$). This implies that there exists no testing algorithm
that succeeds with probability greater than $1/2$ and tests whether average
distribution is the uniform distribution versus average distribution has total
variation distance at least $1/4$ from the uniform distribution.

Here is the procedure to draw a sequence of distribution
$(\textbf{p}_{1}\dots\textbf{p}_{T})$ from $D_{1}$:

  1. 1.

Draw a permutation $\pi:[k]\rightarrow[k]$ uniformly at random.

  2. 2.

Use the permutation $\pi$ to partition the domain into $T^{\prime}$ sets of
size $r^{\prime}$ each where for $i\leq T^{\prime}$, each $\textbf{p}_{i}$
corresponds to a uniform distribution over a distinct set. That is, for $1\leq
i\leq T^{\prime}$, $\textbf{p}_{i}$ corresponds to a uniform distribution over
$\\{\pi\left((i-1)*r^{\prime}+1\right),\pi\left((i-1)*r^{\prime}+2\right),\cdots,\pi(i*r^{\prime})\\}$.

  3. 3.

For $T^{\prime}+1\leq i\leq T$, $\textbf{p}_{i}$ corresponds to a uniform
distribution over the whole support $[k]$, that is
$\textbf{p}_{i}=\mathrm{Unif}(k)$.

Here is the procedure to draw a sequence of distributions
$(\textbf{p}_{1}\dots\textbf{p}_{T})$ from $D_{2}$:

  1. 1.

Draw a permutation $\pi:[k]\rightarrow[k]$ uniformly at random.

  2. 2.

Use the permutation $\pi$ to partition the domain into $T^{\prime}$ sets of
size $r^{\prime}$ each where for $i\leq T^{\prime}$, each $\textbf{p}_{i}$
corresponds to a point-mass distribution supported over an element of a
distinct set: For $1\leq i\leq T^{\prime}$, $\textbf{p}_{i}$ corresponds to a
point-mass distribution with probability mass $1$ on element
$\pi\left((i-1)*r^{\prime}+1\right)$.

  3. 3.

For $T^{\prime}+1\leq i\leq T$, $\textbf{p}_{i}$ corresponds to a uniform
distribution over the whole support $[k]$, that is
$\textbf{p}_{i}=\mathrm{Unif}(k)$.

Note that all the distributions sequences in the support of $D_{1}$ satisfy
$\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T})=u_{k}$. Next, we show that
all the distribution sequences in the support of $D_{2}$ satisfy
$\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T}),\mathrm{Unif}(k))\geq
1/4$. For such distribution sequences,
$\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T}^{\prime})$ has mass
$\frac{1}{k}-\frac{T^{\prime}}{Tk}+\frac{1}{T}$ on $T^{\prime}$ domain
elements and mass $\frac{1}{k}-\frac{T^{\prime}}{Tk}$ on $k-T^{\prime}$ domain
elements. From this, we get

$\displaystyle\mathrm{d_{TV}}(\mathrm{avg}(\textbf{p}_{1}\dots\textbf{p}_{T}),\mathrm{Unif}(k))$
$\displaystyle=\frac{(k-T^{\prime})T^{\prime}}{Tk}$
$\displaystyle\geq\frac{1}{4}$

where for the last inequality, we used $T^{\prime}\leq T\leq k/2$ and
$T^{\prime}/T\geq 1/2$.

Now, we will show that the samples drawn from distribution sequences drawn
from $D_{1}$ are indistinguishable from samples drawn from distribution
sequences drawn from $D_{2}$ which will complete the proof. Let $D_{1}^{X}$ be
the distribution corresponding to $c=1$ sample drawn from each of
$\textbf{p}_{1},\dots,\textbf{p}_{T}$, where
$(\textbf{p}_{1}\dots\textbf{p}_{T})$ is drawn from $D_{1}$ (with $c=1$). We
define $D_{2}^{X}$ analogously. We want to show that
$\mathrm{d_{TV}}(D_{1}^{X},D_{2}^{X})=0$. Note that in both $D_{1}^{X}$ and
$D_{2}^{X}$, each of last $(T-T^{\prime})$ samples
$\\{X_{t}\\}_{t\in[T-T^{\prime}]}$ are drawn from $\mathrm{Unif}(k)$
independent of the first $T^{\prime}$ samples
$\\{X_{t}\\}_{t\in[T^{\prime}]}$. And the first $T^{\prime}$ samples
$\\{X_{t}\\}_{t\in[T^{\prime}]}$ correspond to choosing $T^{\prime}$ distinct
domain elements uniformly at random. Thus $D_{1}^{X}$ and $D_{2}^{X}$ are the
same distributions.

∎

##  Appendix C Poissonized setting

In this section, we state and prove some results for the non-i.i.d setting,
where we are also allowed to use Poissonization. We will use the following
standard facts about Poisson distributions.

Let $\mathrm{Poi}(\lambda)$ denote a Poisson random variable with mean
parameter $\lambda\geq 0$.

######  Fact C.1.

For any $\lambda_{1},\lambda_{2}\geq 0$, if $X_{1}$ and $X_{2}$ are
independent random variables distributed as
$X_{1}\sim\mathrm{Poi}(\lambda_{1})$ and $X_{2}\sim\mathrm{Poi}(\lambda_{2})$,
then $X_{1}+X_{2}\sim\mathrm{Poi}(\lambda_{1}+\lambda_{2})~{}.$

######  Fact C.2.

Given $\mathrm{Poi}(c)$ samples from a distribution $\textbf{p}\in\Delta_{k}$,
the frequency of any element $j\in[k]$ follows the distribution
$\mathrm{Poi}(c\cdot\textbf{p}(j))$.

We are now ready to prove the following theorem.

######  Claim C.3 (Poisson identity testing).

For any $\varepsilon>0$ and reference distribution $\textbf{q}\in\Delta_{k}$,
with $\mathrm{Poi}(c)$ samples from each of
$\textbf{p}_{1},\dots,\textbf{p}_{T}$ and $T=O(\sqrt{k}/\varepsilon^{2})$,
there exists a testing algorithm that succeeds with probability at least $2/3$
and tests whether,

$\textbf{p}_{\mathrm{avg}}=\textbf{q}\quad\text{ versus
}\quad\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\textbf{q})\geq\varepsilon~{},$

for any $c\geq 1$.

###### Proof.

Note that we are given $\mathrm{Poi}(c)$ samples from each distribution
$\textbf{p}_{t}$ for all $t\in[T]$. For each $t\in[T]$, let $N_{t}$ denote the
number of samples drawn from $\textbf{p}_{t}$. Note that
$N_{t}\sim\mathrm{Poi}(c)$. For $i\in[k]$, let $N_{t}(i)$ be the random
variable that denotes the frequency of element $i$ in samples $X_{t}$, that
is, $N_{t}(i)=|\\{j\in[N_{t}]~{}:~{}X_{t}(j)=i\\}|$. By C.2, we know that

$N_{t}(i)\sim\mathrm{Poi}(c\cdot\textbf{p}_{t}(i))~{}.$

Furthermore, if we let $N(i)=\sum_{t\in[T]}N_{t}(i)$, then by C.1, we get
that,

$N(i)\sim\mathrm{Poi}\Big{(}c\cdot\sum_{t\in[T]}\textbf{p}_{t}(i)\Big{)}=\mathrm{Poi}(cT\cdot\textbf{p}_{\mathrm{avg}}(i))~{}.$

Therefore, $N(i)$ has the same distribution as the frequency of element $i$
when we are given $\mathrm{Poi}(cT)$ i.i.d samples from distribution
$\textbf{p}_{\mathrm{avg}}$. As $cT\in O(\sqrt{k}/\varepsilon^{2})$, and since
we just argued that we are under the setting of having drawn
$\mathrm{Poi}(cT)$ samples from $\textbf{p}_{\mathrm{avg}}$, we can invoke
existing identity testing algorithms that use Poissonization for the i.i.d
setting to solve the problem with success probability $2/3$, even with $c=1$.
∎

##  Appendix D Collisions and Fingerprints

We relate the collision statistics and the fingerprint of a sample by an
invertible linear map. To recall, the number of $m$-way collisions in a sample
$S=\\{X_{1},\dots,X_{n}\\}$ is equal to
$\sum_{i_{1}<\dots<i_{m}}^{n}1[X_{i_{1}}=\dots=X_{i_{m}]}]$. The fingerprint
of the sample is a count array, where for each $i$, we list the count of the
number of support elements that appeared exactly $i$ times in $S$.

######  Lemma D.1 (Collisions to fingerprint).

Let $x_{1},x_{2},x_{3},x_{4}\in[m]^{4}$ for $m>4$. Let $c_{2},c_{3},c_{4}$
denote the number of $2$-way, 3-way and $4$-way collisions amongst
$x_{1},x_{2},x_{3},x_{4}$. Further, let $n_{2},n_{3},n_{4}$ denote the number
of elements in $[m]$ occurring exactly 2 times, 3 times and 4 times
respectively in $x_{1},x_{2},x_{3},x_{4}$. Then, the vectors
$\begin{bmatrix}c_{2}\\\ c_{3}\\\ c_{4}\end{bmatrix}$ and
$\begin{bmatrix}n_{2}\\\ n_{3}\\\ n_{4}\end{bmatrix}$ are related by an
invertible linear map. In particular,

$\displaystyle\begin{bmatrix}n_{2}\\\ n_{3}\\\
n_{4}\end{bmatrix}=\begin{bmatrix}1&-3&6\\\ 0&1&-4\\\
0&0&1\end{bmatrix}\begin{bmatrix}c_{2}\\\ c_{3}\\\ c_{4}\end{bmatrix}.$

###### Proof.

Observe that

$\displaystyle n_{4}=c_{4},~{}~{}n_{3}=c_{3}-\binom{4}{3}n_{4}=c_{3}-4c_{4}$
$\displaystyle
n_{2}=c_{2}-\binom{3}{2}n_{3}-\binom{4}{2}n_{4}=c_{2}-3(c_{3}-4c_{4})-6c_{4}=c_{2}-3c_{3}+6c_{4}.$

The matrix associated with the linear map has determinant $1$, therefore the
map is invertible. ∎

##  Appendix E Sufficiency of fingerprint for pooling-based testing algorithms

We first formally state the definition of a pooling-based testing algorithm.

######  Definition E.1 (Pooling-based testing algorithm).

Fix $c$ and let $\pi\sim\textrm{Perm}(cT)$ denote drawing a uniformly random
permutation $\pi$ over $cT$ elements. A pooling-based testing algorithm
$\mathcal{A}$ for property $\mathcal{P}\subseteq\Delta_{k}$ with sample
complexity $cT$ is a (possibly randomized) algorithm which, when given a
randomly shuffled pooled multiset $S$ of $c$ samples drawn independently from
each of $\textbf{p}_{1},\dots,\textbf{p}_{T}$, i.e.,
$S=\bigcup_{t=1}^{T}\\{X^{(t)}_{1},\dots,X^{(t)}_{c}\sim\textbf{p}_{t}\\}$,
$\pi\sim\textrm{Perm}(cT)$, $S\leftarrow\pi(S)$, produces output
$\mathcal{A}(S)\in\\{0,1\\}$ satisfying the following

  * •

If $\textbf{p}_{\mathrm{avg}}\in\mathcal{P}$, then
$\Pr_{S,\pi,\mathcal{A}}[\mathcal{A}[S]=1]\geq 2/3$.

  * •

If $\mathrm{d_{TV}}(\textbf{p}_{\mathrm{avg}},\mathcal{P})\geq\varepsilon$,
then $\Pr_{S,\pi,\mathcal{A}}[\mathcal{A}[S]=0]\geq 2/3$.

The following lemma states that the fingerprint of the combined sample
captures all the information required for a pooling-based testing algorithm to
test a symmetric property of the average distribution.

######  Lemma E.2.

Let $\mathcal{A}$ be a pooling-based testing algorithm having sample
complexity $cT$ that tests a symmetric property
$\mathcal{P}\subseteq\Delta_{k}$ of the average distribution
$\textbf{p}_{\mathrm{avg}}=\mathrm{avg}(\textbf{p}_{1},\dots,\textbf{p}_{T})$.
Then, there exists a pooling-based algorithm $\mathcal{A}^{\prime}$ for the
same task having the same sample complexity which takes as input only the
fingerprint of the combined sample.

###### Proof.

Let the fingerprint of the combined sample $S$ be denoted by
$f=[f_{0},f_{1},\dots,f_{cT}]$. Here, $f_{i}$ is the number of elements in
$[k]$ that occur exactly $i$ times in the combined sample. Given as input $f$,
the algorithm $\mathcal{A}^{\prime}$ constructs a sequence $S$ in the
following way:

  1. 1.

Initially, $S=\phi$, $e=1$.

  2. 2.

For $i=0,\dots,cT:$

$\displaystyle\qquad\text{While }f_{i}>0:$
$\displaystyle\qquad\qquad\text{Append }i\text{ copies of }e\text{ to }S.$
$\displaystyle\qquad\qquad e\leftarrow e+1,\;f_{i}\leftarrow f_{i}-1.$

  3. 3.

Draw $\pi_{k}\sim\textrm{Perm}(k)$.

  4. 4.

For every $s\in S$:

$\displaystyle\qquad\text{Set }s\leftarrow\pi_{k}(s).$

  5. 5.

Draw $\pi_{S}\sim\textrm{Perm}(cT)$.

  6. 6.

Set $S\leftarrow\pi_{S}(S)$.

The algorithm $\mathcal{A}^{\prime}$ then feeds $S$ constructed as above to
$\mathcal{A}$, and returns $\mathcal{A}$’s output.

Observe that the distribution of $S$ constructed as above is identical to the
distribution of $S$ obtained in the following way:

  1. 1.

Draw $\pi_{k}\sim\textrm{Perm}(k)$.

  2. 2.

Draw
$S=\bigcup_{t=1}^{T}\\{X^{(t)}_{1},\dots,X^{(t)}_{c}\sim\pi_{k}(\textbf{p}_{t})\\}$.

  3. 3.

Draw $\pi_{S}\sim\textrm{Perm}(cT)$.

  4. 4.

Set $S\leftarrow\pi_{S}(S)$.

Here, $\pi(\textbf{p})$ denotes permuting the probability distribution p
according to $\pi$ i.e. $\pi(\textbf{p})_{i}=\textbf{p}_{\pi(i)}$. Now, for a
fixed permutation $\pi_{k}$, observe that
$\mathrm{avg}(\pi_{k}(\textbf{p}_{1}),\dots,\pi_{k}(\textbf{p}_{T}))=\pi_{k}(\mathrm{avg}(\textbf{p}_{1},\dots,\textbf{p}_{T}))=\pi_{k}(\textbf{p}_{\mathrm{avg}})$.
Further, recall that the property $\mathcal{P}$ we are thinking about is
symmetric. Thus, if $\textbf{p}_{\mathrm{avg}}\in\mathcal{P}$, then
$\pi_{k}(\textbf{p}_{\mathrm{avg}})\in\mathcal{P}$ for any
$\pi_{k}\in\textrm{Perm}(k)$. Similarly, if
$\textbf{p}_{\mathrm{avg}}\notin\mathcal{P}$, then
$\pi_{k}(\textbf{p}_{\mathrm{avg}})\notin\mathcal{P}$ for any
$\pi_{k}\in\textrm{Perm}(k)$. Thus, for any fixed $\pi_{k}$, $\mathcal{A}$
correctly tests if
$\mathrm{avg}(\pi_{k}(\textbf{p}_{1}),\dots,\pi_{k}(\textbf{p}_{T}))$ has the
property $\mathcal{P}$
($\iff\mathrm{avg}(\textbf{p}_{1},\dots,\textbf{p}_{T})$ has the property
$\mathcal{P}$). Consequently, $\mathcal{A}$ (and hence $\mathcal{A}^{\prime}$)
correctly tests for a randomly chosen $\pi_{k}$ as well.

∎