# Testing Product Distributions: A Closer Look

Arnab Bhattacharyya
<EMAIL_ADDRESS>
National University of Singapore Supported in part by NRF-AI Fellowship
R-252-100-B13-281 and an Amazon Research Award. Sutanu Gayen
<EMAIL_ADDRESS>
National University of Singapore Supported in part by NRF-AI Fellowship
R-252-100-B13-281. Saravanan Kandasamy
<EMAIL_ADDRESS>
Cornell University  N. V. Vinodchandran
<EMAIL_ADDRESS>
University of Nebraska-Lincoln Supported in part by the US National Science
Foundation under grants NSF CCF-184908 and NSF HDR:TRIPODS-1934884.

###### Abstract

We study the problems of identity and closeness testing of $n$-dimensional
product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart
(COLT ‘17) and Daskalakis and Pan (COLT ‘17) have established tight sample
complexity bounds for non-tolerant testing over a binary alphabet: given two
product distributions $P$ and $Q$ over a binary alphabet, distinguish between
the cases $P=Q$ and $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$. We build on
this prior work to give a more comprehensive map of the complexity of testing
of product distributions by investigating tolerant testing with respect to
several natural distance measures and over an arbitrary alphabet. Our study
gives a fine-grained understanding of how the sample complexity of tolerant
testing varies with the distance measures for product distributions. In
addition, we also extend one of our upper bounds on product distributions to
bounded-degree Bayes nets.

##  1 Introduction

The main goal of this work is to give a comprehensive investigation to the
sample complexity of several distribution testing problems over high-
dimensional product distributions. Testing properties of distributions from
samples has been actively investigated for several decades from the
perspectives of classical statistics and, more recently, from a property
testing viewpoint in theoretical computer science. Hypothesis testing is a
classical problem investigated in statistics with significant practical
applications. From the property testing viewpoint, the two most well studied
distribution testing problems are identity testing and closeness
testing.111Identity testing is also known as goodness-of-fit testing or one-
sample testing in the literature. Similarly, closeness testing is also known
as two-sample testing.

In the identity testing problem, we are given a known reference distribution
$Q$ and sample access to an unknown distribution $P$ over the same sample
space as that of $Q$, and the goal is to distinguish between the cases $P=Q$
or $P$ is $\epsilon$-far from $Q$ with respect to a given distance measure. It
is known that $\Theta(\sqrt{m}/\epsilon^{2})$ samples are necessary and
sufficient to solve the identity testing problem with respect to the total
variation distance, where $m$ is the size of the sample space [Valiant and
Valiant, 2014, Paninski, 2008]. In the closeness testing problem, we have
sample access to a pair of unknown distributions $P$ and $Q$ on a common
sample space, and the goal is to distinguish between the cases $P=Q$ or $P$ is
$\epsilon$-far from $Q$ with respect to a certain distance measure. It is
known that $\Theta(\max(m^{2/3}\epsilon^{-4/3},\sqrt{m}\epsilon^{-2}))$
samples are necessary and sufficient to solve the closeness testing problem
with respect to the total variation distance, where $m$ is the size of the
sample space [Chan, Diakonikolas, Valiant, and Valiant, 2014]. See the surveys
Rubinfeld [2012], Canonne [2020] and the references therein for pointers to
the extensive research on identity and closeness testing as well as related
problems.

One of the main bottlenecks resulting from the above-mentioned complexity
bounds is that these testing problems are (provably) hard for arbitrary
distributions over large sample spaces. For example, for distributions over an
$n$-dimensional Boolean hypercube $m=2^{n}$ and hence $\Theta(2^{n\over 2})$
samples are necessary and sufficient for identity testing (for a constant
$\epsilon$). To overcome this bottleneck, very recently researchers have
started investigating testing problems over high-dimensional sample spaces by
imposing natural structural assumptions over distributions. Such assumptions
restrict the class of distributions and open up the possibility of designing
testers with substantially smaller sample complexity than required for the the
general case. Among them product distributions over a finite alphabet are a
natural class that is both practically relevant and simple enough to serve as
a test ground for algorithm design. Indeed, prior works of Canonne,
Diakonikolas, Kane, and Stewart [2017] and Daskalakis and Pan [2017] have
established tight sample complexity bounds for identity and closeness testing
of product distributions over a binary alphabet.

A drawback of the testing problems as stated is their one-sided or non-
tolerant aspect: on the one side of the decision, we only need to distinguish
from the case where two distributions are exactly equal. This is a significant
restriction specially for high-dimensional distributions which require a large
number of parameters to be specified. For example, in the case of identity
testing, it is unlikely that we can ever hypothesize a reference distribution
$Q$ such that it exactly equals the data distribution $P$. Similarly, for
closeness testing, two data distributions $P$ and $Q$ are most likely not
exactly equal. The tolerant version of testing problems addresses this issue
as it seeks to design testers for identity and closeness that tolerate errors
on both decision cases. That is, in the tolerant version we would like to
distinguish between the cases
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\epsilon_{1}$ and
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon_{2}$, where
$\epsilon_{1}<\epsilon_{2}$ are user-supplied error parameters. The tolerance
requirement makes the testing problems more expensive. For arbitrary
distributions on a set of size $m$ it is known [Valiant and Valiant, 2010]
that tolerant identity and closeness testing of arbitrary distributions
supported on a set of size $m$ require $\Omega(m/\log m)$ samples for
constants $\epsilon_{1}<\epsilon_{2}$, if the distance measure used is the
total variation distance.

The main focus of this paper is to take a closer look at the complexity of
testing of product distributions by investigating tolerant testing with
respect to several natural distance measures and over an arbitrary alphabet.
Such an investigation is important because a complete picture on the
complexity of testing product distribution will shed light on possibilities
and challenges in algorithm design for testing high dimensional structured
distributions.

###  1.1 Our Contributions

We investigate tolerant testing of product distributions with respect to the
following distance measures: total variation distance (${d}_{\mathrm{TV}}$),
Hellinger distance ($d_{\mathrm{H}}$), Kullback-Leibler divergence
($d_{\mathrm{KL}}$), and Chi-squared distance
($d_{\mathrm{\chi}^{2}}$)222Refer to Section 2 for the notations and
definitions.. The following relationship is well-known among them:

$\displaystyle\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)\leq\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\sqrt{\mbox{$d_{\mathrm{KL}}$}(P,Q)}\leq\sqrt{\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)}$
(1)

We fix a pair of distance functions $d_{1}\leq d_{2}$ from the above equation
and investigate the problem of deciding $d_{1}(P,Q)\leq\epsilon/3$ versus
$d_{2}(P,Q)>\epsilon$ with 2/3 probability, which we call
$d_{1}$-versus-$d_{2}$ testing. When both $P$ and $Q$ are only accessed by
samples, this problem is called $d_{1}$-versus-$d_{2}$ closeness testing. When
$Q$ is a reference distribution given to us and $P$ is accessed by samples,
the problem is called $d_{1}$-versus-$d_{2}$ identity testing. The problem of
distinguishing $P=Q$ versus $d_{2}(P,Q)>\epsilon$ is called non-tolerant
testing w.r.t. $d_{2}$. Clearly, tolerant testing is at least as hard as non-
tolerant testing.

Our contributions regarding $d_{1}$-versus-$d_{2}$ identity and closing
testing problems over product distributions are summarized in Table 1 and
Table 2. Each cell of the tables represents the sample complexity of testing
whether the two product distributions are close or far in terms of the
distance corresponding to that row and column respectively. The problems
become harder as we traverse the table down or to the right due to Equation 1.
Daskalakis, Kamath, and Wright [2018] have shown that non-tolerant testing
w.r.t. $d_{\mathrm{KL}}$ is not testable in a finite set of samples. Hence,
only ${d}_{\mathrm{TV}}$ and $d_{\mathrm{H}}$ are meaningful for $d_{2}$.

Table 1: Sample complexity upper and lower bounds for $d_{1}$-vs-$d_{2}$
identity testing of product distributions for various distance measures. First
column (row) lists $d_{1}(P,Q)\leq\epsilon_{1}$ (respectively,
$d_{2}(P,Q)>\epsilon_{2}$). The problem becomes computationally more
difficult, and hence the sample complexity is non-decreasing, as we traverse
the table down or to the right. [†], [*] and [‡] are from Daskalakis and Pan
[2017], Canonne, Diakonikolas, Kane, and Stewart [2017] and Bhattacharyya,
Gayen, Meel, and Vinodchandran [2020], respectively. Note that for some of the
cells, to get to the bound we need to follow a chain of directions.

| $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$ | $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$
---|---|---
$P=Q$ |  UB : $O(\sqrt{n}/\epsilon^{2})$ (for $|\Sigma|=2$) [†,*] |  UB : Below
|  LB : $\Omega(\sqrt{n}/\epsilon^{2})$ (for $|\Sigma|=2$) [†,*] |  LB : Left
|  LB : $\Omega(\sqrt{n\lvert\Sigma\rvert}/\epsilon^{2})$ (for $|\Sigma|>2$) 2.5 |
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ |  UB : Right |  UB : $O(\sqrt{n\lvert\Sigma\rvert}/\epsilon^{2})$ 2.3
|  LB : Above |  LB : Left
$\mbox{$d_{\mathrm{KL}}$}(P,Q)\leq\epsilon^{2}/9$ |  UB : Below |  UB : Below
|  LB : $\Omega(n/\log n)$ 2.6 |  LB : Left
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/3$ |  UB : Right |  UB : $O(n|\Sigma|/\epsilon^{2})$ 2.4
|  LB : Above |  LB : Left
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\epsilon/3$ |  UB : $O(n|\Sigma|/\epsilon^{2})$ [‡] | Not Well Defined
|  LB : $\Omega(n/\log n)$[*] |

Table 2: Sample complexity bounds for of $d_{1}$-vs-$d_{2}$ closeness testing
of product distributions. As in the case of identity testing, sample
complexity is non-decreasing as we traverse the table down or to the right.
[*] and [‡] are from Canonne, Diakonikolas, Kane, and Stewart [2017] and
Bhattacharyya, Gayen, Meel, and Vinodchandran [2020], respectively.

| $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$ | $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$
---|---|---
$P=Q~{}(\Sigma=2)$ |  UB : $O(\max(\sqrt{n}/\epsilon^{2},n^{3/4}/\epsilon))$ [*] |  UB : $O(n^{3/4}/\epsilon^{2})$, 2.8
|  LB : $\Omega(\max(\sqrt{n}/\epsilon^{2},n^{3/4}/\epsilon))$ [*] |  LB : Left
(Any $\Sigma)$ |  UB : $O\\!\left(\max\left\\{\sqrt{n\lvert\Sigma\rvert}/\epsilon^{2},(n\lvert\Sigma\rvert)^{3/4}/\epsilon\right\\}\right)$ 2.9 |  UB : $O((n|\Sigma|)^{3/4}/\epsilon^{2})$, 2.8
|  LB : Above |  LB : Above
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ |  UB : Below |  UB : Below
|  LB : $\Omega(n/\log n)$ 2.7 |  LB : Left
$\mbox{$d_{\mathrm{KL}}$}(P,Q)\leq\epsilon^{2}/9$ |  UB : Below |  UB : Below
|  LB : Above |  LB : Left
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/3$ |  UB : Right |  UB : $O(n|\Sigma|/\epsilon^{2})$ 2.4
|  LB : Above |  LB : Left
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\epsilon/3$ |  UB : $O(n|\Sigma|/\epsilon^{2})$ [‡] | Not Well-defined
|  LB : $\Omega(n/\log n)$[*] |

We informally present our main results below. We would like to note that the
only algorithmic results known regarding the complexity of testing product
distributions prior to our work are:

  1. (1)

$\Theta(\sqrt{n}/\epsilon^{2})$ sample complexity bound for the non-tolerant
identity testing over the binary alphabet [Daskalakis and Pan, 2017, Canonne,
Diakonikolas, Kane, and Stewart, 2017],

  2. (2)

$\Theta(\max(\sqrt{n}/\epsilon^{2},n^{3/4}/\epsilon))$ sample complexity bound
for non-tolerant closeness testing problem over the binary alphabet [Canonne,
Diakonikolas, Kane, and Stewart, 2017], and

  3. (3)

$O(n|\Sigma|/\epsilon^{2})$ upper bound for
${d}_{\mathrm{TV}}$-vs-${d}_{\mathrm{TV}}$ tolerant identity and closeness
testing [Bhattacharyya, Gayen, Meel, and Vinodchandran, 2020].

#### Identity testing: $P$ unknown and $Q$ given

  * -

We present a tolerant identity testing algorithm that distinguishes
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ versus
$\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ with
$O(\sqrt{n\lvert\Sigma\rvert}/\epsilon^{2})$ sample complexity. Since the
condition for the tester rejecting $\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ is
stronger than $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$ due to Equation 1, we
get the same bound when the second distance is ${d}_{\mathrm{TV}}$. Our
algorithm applies for an arbitrary $\Sigma$ and has optimal dependence on
$n,\lvert\Sigma\rvert$ and $\epsilon$.

  * -

We present an algorithm for $d_{\mathrm{H}}$-vs-$d_{\mathrm{H}}$ identity
testing with sample complexity $O(n|\Sigma|/\epsilon^{2})$.

  * -

Our third result is a lower bound: we establish the optimality of the sample
complexity of our non-tolerant identity tester w.r.t. ${d}_{\mathrm{TV}}$in
terms of $n,\lvert\Sigma\rvert$ and $\epsilon$. Such a lower bound was
previously known only for $\lvert\Sigma\rvert=2$.

  * -

Our next result is another lower bound: we show that the identity testing
problem of distinguishing $\mbox{$d_{\mathrm{KL}}$}(P,Q)\leq\epsilon^{2}/9$
versus $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$ requires at least
$\Omega(n/\log n)$ samples. This shows a jump in sample complexity when we
move to $d_{\mathrm{KL}}$ from $\chi^{2}$ distance. Previously, Canonne,
Diakonikolas, Kane, and Stewart [2017] had shown the $\Omega(n/\log n)$ lower
bound for ${d}_{\mathrm{TV}}$-vs-${d}_{\mathrm{TV}}$ testing; we strengthen it
to $d_{\mathrm{KL}}$-vs-${d}_{\mathrm{TV}}$ testing.

#### Closeness testing: $P$ and $Q$ unknown

  * -

We design an efficient algorithm that distinguishes
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/3$ versus
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ with
$O(n\lvert\Sigma\rvert/\epsilon^{2})$ sample complexity. (Note that this
result appears in both Table 1 and Table 2). Our upper bound works for
distributions over arbitrary alphabet.

  * -

We complement the above upper bound with a new lower bound. We show that given
sample access to two unknown distributions $P$ and $Q$, distinguishing
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ from
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$ requires $\Omega(n/\log n)$
samples, even for $|\Sigma|=2$ and constant $\epsilon$. Note that this is in
contrast to identity testing, where Table 1 shows that the same problem can be
solved using $O(\sqrt{n\lvert\Sigma\rvert}/\epsilon^{2})$ samples. This also
strengthens the ${d}_{\mathrm{TV}}$-vs-${d}_{\mathrm{TV}}$ lower bound of
Canonne, Diakonikolas, Kane, and Stewart [2017].

We also establish new upper bounds for non-tolerant closeness testing over
arbitrary alphabet. Prior work considered only the binary alphabet and the
extension to arbitrary alphabet is not completely straightforward.

#### Tolerant Testing for Bayes Nets

A more general class of probability distributions, containing product
distributions as a special case, is bounded-degree Bayesian networks (or Bayes
nets in short). Formally, a probability distribution $P$ over $n$ variables
$X_{1},\dots,X_{n}\in\Sigma$ is said to be a Bayesian network on a directed
acyclic graph $G$ with $n$ nodes if333We use the notation $X_{S}$ to denote
$\\{X_{i}:i\in S\\}$ for a set $S\subseteq[n]$. for every $i\in[n]$, $X_{i}$
is conditionally independent of $X_{\text{non-descendants}(i)}$ given
$X_{\text{parents}(i)}$. Equivalently, $P$ admits the factorization:

$\Pr_{X\sim P}[X=x]=\prod_{i=1}^{n}\Pr_{X\sim P}[X_{i}=x_{i}\mid\forall
j\in{\rm parents}(i),X_{j}=x_{j}]\qquad\text{for all }x\in\Sigma^{n}$ (2)

For example, product distributions are Bayes nets on the empty graph. A
degree-$d$ Bayes net is a Bayes net on a graph with in-degree bounded by $d$.

We consider tolerant closeness testing of degree-$d$ Bayes nets on known
directed acyclic graphs. Bhattacharyya, Gayen, Meel, and Vinodchandran [2020]
designed an algorithm for tolerant ${d}_{\mathrm{TV}}$-vs-${d}_{\mathrm{TV}}$
closeness testing with $\tilde{O}(|\Sigma|^{d+1}n\epsilon^{-2})$ sample
complexity. Our main result for Bayes nets extends this same bound to
$d_{\mathrm{H}}$-vs-$d_{\mathrm{H}}$ testing, which is the hardest variant of
the tolerant testing problems considered above. Moreover, our test is
computationally efficient (in terms of time complexity). Note that a
computationally inefficient test readily follows from available learning
algorithms for fixed-structure Bayes nets with respect to KL divergence
[Dasgupta, 1997, Bhattacharyya, Gayen, Meel, and Vinodchandran, 2020]. Indeed,
the main technical component in our result is a novel efficient estimator for
Hellinger distance between two distributions when given access to samples
generated from them as well as their probability mass functions. This
estimator may be of independent interest.

###  1.2 Related Work

The history of identity tests goes back to Pearson’s chi-squared test in 1900.
The traditional spirit of analyzing such tests is to consider a fixed
distribution $P$ and to let the number of samples go to infinity. Work on
understanding the performance of hypothesis tests with a finite number of
samples mostly started only quite recently. Goldreich and Ron [2011] studied
the problem of distinguishing whether an input distribution $P$ is uniform
over its support or $\epsilon$-far from uniform in total variation distance
(in fact, they showed a tolerant tester with respect to the $\ell_{2}$-norm).
Paninski showed that $\Theta(\sqrt{m}/\epsilon^{2})$ samples are necessary for
uniformity testing, and gave an optimal tester when $\epsilon>m^{-1/4}$ (where
$m$ is the size of the support). For the more general problem of testing
identity to an arbitrary given distribution, Batu, Fortnow, Rubinfeld, Smith,
and White [2013] showed an upper bound of $\tilde{O}(\sqrt{m}/\epsilon^{6})$.
This was then refined by Valiant and Valiant [2014] to the tight bound of
$\Theta(\sqrt{m}/\epsilon^{2})$. Batu, Fortnow, Rubinfeld, Smith, and White
[2013] also studied the problem of testing closeness between two input
distributions and showed an upper bound of
$\tilde{O}(m^{2/3}\textrm{poly}(1/\epsilon))$ on the sample complexity. The
tight bound of $\Theta(\max(m^{2/3}\epsilon^{-4/3},\sqrt{m}\epsilon^{-2}))$
was achieved by Chan, Diakonikolas, Valiant, and Valiant [2014]. Tolerant
versions of uniformity, identity, and closeness testing with respect to the
total variation distance require $\Omega(m/\log m)$ samples Valiant and
Valiant [2011], which is also tight Valiant and Valiant [2010]. To circumvent
this lower bound, tolerant identity testing with respect to chi-squared
distance was initiated by Acharya, Daskalakis, and Kamath [2015] and was
thoroughly studied in Daskalakis, Kamath, and Wright [2018] for a number of
pairs of distances.

The study of testing distributions over high-dimensional domains was initiated
recently independently and concurrently in Daskalakis, Dikkala, and Kamath
[2019], Canonne, Diakonikolas, Kane, and Stewart [2017], Daskalakis and Pan
[2017], who recognized that since testing arbitrary distributions over
$\Sigma^{n}$ would require an exponential number of samples, it is important
to make structural assumptions on the distribution. In particular, in
Daskalakis, Dikkala, and Kamath [2019], they make the assumption that the
input distributions are drawn from an Ising model. In Canonne, Diakonikolas,
Kane, and Stewart [2017] and Daskalakis and Pan [2017], the authors considered
identity testing and closeness testing for distributions given by Bayes
networks of bounded in-degree. These works also considered the special case of
product distributions (equivalently, distributions over a Bayes network
consisting of isolated nodes). It’s shown that $\Theta(\sqrt{n}/\epsilon^{2})$
and $\Theta(\max(\sqrt{n}/\epsilon^{2},n^{3/4}/\epsilon))$ samples are
necessary and sufficient for identity testing and closeness testing
respectively of pairs of product distributions when $|\Sigma|=2$. The identity
tester of Canonne, Diakonikolas, Kane, and Stewart [2017] is claimed to have
certain weaker ($O(\epsilon^{2})$ in ${d}_{\mathrm{TV}}$, see Remark 8)
tolerance. A reduction from testing problems for product distributions over
alphabet $\Sigma$, to that for the Bayes nets of degree
$\lfloor\log_{2}|\Sigma|\rfloor-1$, was given in Canonne, Diakonikolas, Kane,
and Stewart [2017] (Remark 55 of their paper). Canonne, Diakonikolas, Kane,
and Stewart [2017] also show that for product distributions, $\Omega(n/\log
n)$ samples are necessary for tolerant identity and closeness testing with
respect to the total variation distance. Very recently, Bhattacharyya, Gayen,
Meel, and Vinodchandran [2020] designed tolerant testers for certain classes
of high-dimensional distributions (including product distributions) with
respect to ${d}_{\mathrm{TV}}$.

##  2 Preliminaries and Formal Statements of Results

We use $\mathrm{Bern}(\delta)$ to denote the Bernoulli distribution with
$\mathrm{Pr}[1]=\delta$. We define various distance measures between
distributions that we use in this paper.

######  Definition 2.1.

Let $P=(p_{1},p_{2},\ldots,p_{m})$ and $Q=(q_{1},q_{2},\ldots,q_{m})$ be two
distributions over sample space $[m]$. Then the distance measures, total
variational distance, chi-squared distance, Hellinger distance, and KL
distance, respectively are defined as follows.

$\mbox{${d}_{\mathrm{TV}}$}(P,Q)=\frac{1}{2}\sum_{i}|p_{i}-q_{i}|;\qquad\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)=\sum_{i}(p_{i}-q_{i})^{2}/q_{i}=\sum_{i}p_{i}^{2}/q_{i}-1;$
$\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)={1\over
2}\sum_{i}(\sqrt{p_{i}}-\sqrt{q_{i}})^{2}=1-\sum_{i}\sqrt{p_{i}q_{i}};\qquad\mbox{$d_{\mathrm{KL}}$}(P,Q)=\sum_{i}p_{i}\ln{p_{i}\over
q_{i}}$

######  Lemma 2.2.

(folklore, see Daskalakis, Kamath, and Wright [2018] for a proof) For two
distributions $P$ and $Q$, the following relation holds.

$\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)\leq\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\sqrt{\mbox{$d_{\mathrm{KL}}$}(P,Q)}\leq\sqrt{\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)}$

###  2.1 Formal Statements of Main Results

Here we list the formal statements of the main theorems we prove in the paper.
First we state the two main upper bounds.

######  Theorem 2.3.

($d_{\mathrm{\chi}^{2}}$-versus-$d_{\mathrm{H}}$ identity tester) There is an
algorithm with sample access to an unknown product distribution
$P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and input a known product distribution
$Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$, both over the common sample space
$\Sigma^{n}$, that decides between cases
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ versus
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$. The algorithm takes
$O(\sqrt{n|\Sigma|}/\epsilon^{2})$ samples from $P$ and runs in time
$O(n\ell+n^{3/2}\sqrt{\ell}/\epsilon^{2})$. The algorithm has a success
probability at least $2/3$.

######  Theorem 2.4.

($d_{\mathrm{H}}$-versus-$d_{\mathrm{H}}$ closeness tester) There is an
algorithm with sample access to two unknown product distribution
$P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$, both
over the common sample space $\Sigma^{n}$, that decides between cases
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/3$ versus
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$. The algorithm takes
$O(n(|\Sigma|+\log n)/\epsilon^{2})$ samples from $P$ and $Q$ and runs in time
$O(n^{2}(|\Sigma|+\log n)/\epsilon^{2})$. The algorithm has a success
probability at least $2/3$.

We complement the above upper bounds on sample complexity with the following
lower bounds.

######  Theorem 2.5.

Uniformity testing with w.r.t. ${d}_{\mathrm{TV}}$ distance for product
distributions over $[\ell]^{n}$ needs $\Omega(\sqrt{n\ell}/\epsilon^{2})$
samples.

######  Theorem 2.6.

($d_{\mathrm{KL}}$-versus-${d}_{\mathrm{TV}}$ identity testing lower bound)
There exists a constant $0<\epsilon<1$ and three product distributions
$F^{yes},F^{no}$ and $F$, each over the sample space $\\{0,1\\}^{n}$ such that
$\mbox{$d_{\mathrm{KL}}$}(F^{yes},F)\leq\epsilon^{2}/9$, whereas
$\mbox{${d}_{\mathrm{TV}}$}(F^{no},F)>\epsilon$, and given only sample
accesses to $F^{yes},F^{no}$, and complete knowledge about $F$, distinguishing
$F^{yes}$ versus $F^{no}$ with probability $>2/3$, requires $\Omega(n/\log n)$
samples.

######  Theorem 2.7.

($d_{\mathrm{\chi}^{2}}$-versus-${d}_{\mathrm{TV}}$ closeness testing lower
bound) There exists a constant $0<\epsilon<1$ and three product distributions
$F^{yes},F^{no}$ and $F$, each over the sample space $\\{0,1\\}^{n}$ such that
$\mbox{$d_{\mathrm{\chi}^{2}}$}(F^{yes},F)\leq\epsilon^{2}/9$, whereas
$\mbox{${d}_{\mathrm{TV}}$}(F^{no},F)>\epsilon$, and given only sample
accesses to $F^{yes},F^{no}$ and $F$, distinguishing $F^{yes}$ versus $F^{no}$
with probability $>2/3$, requires $\Omega(n/\log n)$ samples.

Earlier work has designed non-tolerant closeness tester for product
distribution over a binary alphabet. Here we extend it to arbitrary alphabets.

######  Theorem 2.8.

(Exact-versus-$d_{\mathrm{H}}$ closeness tester) There is an algorithm with
sample access to two unknown product distribution
$P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$, both
over the common sample space $\Sigma^{n}$, that decides between cases $P=Q$
versus $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$. The algorithm takes
$m=O((n|\Sigma|)^{3/4}/\epsilon^{2})$ samples from $P$ and $Q$ and runs in
time $O(mn)$. The algorithm has a success probability at least $2/3$.

######  Theorem 2.9.

(Exact-versus-${d}_{\mathrm{TV}}$ closeness tester) There is an algorithm with
sample access to two unknown product distribution
$P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$, both
over the common sample space $\Sigma^{n}$, that decides between cases $P=Q$
versus $\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$. The algorithm takes
$m=O(\max\\{\sqrt{n|\Sigma|}/\epsilon^{2},(n|\Sigma|)^{3/4}/\epsilon\\})$
samples and runs in time $O(mn)$. The algorithm has a success probability at
least $2/3$.

Finally, we state our result for $d_{\mathrm{H}}$-vs-$d_{\mathrm{H}}$
closeness testing of fixed-structure Bayes nets.

######  Theorem 2.10.

($d_{\mathrm{H}}$-vs-$d_{\mathrm{H}}$ closeness tester for Bayes nets) Given
samples from two unknown Bayesian networks $P$ and $Q$ over $\Sigma^{n}$ on
potentially different but known pair of graphs of indegree at most $d$, we can
distinguish the cases $\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/2$ versus
$\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ with 2/3 probability using
$m=O(|\Sigma|^{d+1}n\log(|\Sigma|^{d+1}n)\epsilon^{-2})$ samples and
$O(|\Sigma|^{d+1}mn+n\epsilon^{-4})$ time.

##  3 Efficient Tolerant Testers

###  3.1 $d_{\mathrm{\chi}^{2}}$-vs-$d_{\mathrm{H}}$ Tolerant Identity Tester

In this section, we generalize the testers of Daskalakis and Pan [2017],
Canonne, Diakonikolas, Kane, and Stewart [2017] that distinguishes $P=Q$ (‘yes
class’) versus $\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq\epsilon$ (‘no class’)
using $O(\sqrt{n}/\epsilon^{2})$ samples, where $P$ and $Q$ are product
distributions over $\\{0,1\\}^{n}$. Our first contribution is to generalize
their tester in the following three ways. Firstly, our ‘no class’ is defined
as $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$, which is more general
than $\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq\epsilon$. Secondly, our tester works
for any general alphabet size $|\Sigma|\geq 2$. Finally, we give a
$d_{\mathrm{\chi}^{2}}$ tolerant tester i.e. our ‘yes class’ is defined as
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)<\epsilon^{2}/9$.

Our tester relies on certain factorizations of $d_{\mathrm{\chi}^{2}}$ and
$d^{2}_{\mathrm{H}}$ for product distributions. We shall proceed to discuss
those relations.

######  Lemma 3.1.

(folklore, see Acharya, Daskalakis, and Kamath [2015] for a proof) Let
$P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$ be two
distributions, both over the common sample space $\Sigma^{n}$. Then
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)=\prod_{i=1}^{n}(1+\mbox{$d_{\mathrm{\chi}^{2}}$}(P_{i},Q_{i}))-1$.
In particular,
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\geq\sum_{i}\mbox{$d_{\mathrm{\chi}^{2}}$}(P_{i},Q_{i})$

######  Fact 3.2.

(folklore) Let $P=\prod_{i=1}^{n}P_{i}$ and $Q=\prod_{i=1}^{n}Q_{i}$ be two
distributions over $\Sigma^{n}$. It holds that
$1-\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)=\Pi_{i=1}^{n}(1-\mbox{$d^{2}_{\mathrm{H}}$}(P_{i},Q_{i}))$.
In particular,
$\mbox{$d_{\mathrm{H}}$}^{2}(P,Q)\leq\sum_{i}\mbox{$d_{\mathrm{H}}$}^{2}(P_{i},Q_{i})$.

We get the following useful corollary from 2.2 and 3.2.

######  Corollary 3.3.

Let $P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$ be
two distributions, both over the common sample space $\Sigma^{n}$. Then
$\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)\leq\sum_{i}\mbox{$d_{\mathrm{\chi}^{2}}$}(P_{i},Q_{i})/2$.

To avoid low probabilities in the denominator of the test statistic, we need
to ensure that for each distribution $Q_{i}$, each element in the sample space
$\Sigma$ gets at least a sufficiently large probability
$\Omega(\epsilon^{2}/|\Sigma|n)$. We do this by slightly randomizing $Q$ to
get a new distribution $S$. The randomization process to get $S$ from $Q$ is
given below. This is similar to the reduction given in Daskalakis and Pan
[2017] and Canonne, Diakonikolas, Kane, and Stewart [2017] for the case
$\Sigma=\\{0,1\\}$ and for the case when the ‘no’ class is defined with
respect to ${d}_{\mathrm{TV}}$. Let $\mathrm{Bern}(\delta)^{n}$ be the product
distribution of $n$ copies of $\mathrm{Bern}(\delta)$.

######  Lemma 3.4.

For a product distribution $P=\prod_{i=1}^{n}P_{i}$, where the
$P_{i}^{\prime}s$ are over a sample space $\Sigma$, and $0<\delta<1$, let
$P^{\delta}$ be the distribution over $\Sigma^{n}$ defined by the following
sampling process. In order to produce a sample $(X_{1},X_{2},\ldots,X_{n})$ of
$P^{\delta}$,

  1. -

Sample $(r_{1},r_{2},\dots,r_{n})\sim\mathrm{Bern}(\delta)^{n}$ and sample
$(Y_{1},Y_{2},\dots,Y_{n})\sim P$

  2. -

For every $i$, if $r_{i}=1$, $X_{i}\leftarrow$ uniform sample from $\Sigma$,
if $r_{i}=0$, $X_{i}\leftarrow Y_{i}$.

Then, the following is true.

  1. -

$P^{\delta}$ is a product distribution $\prod_{i}P_{i}^{\delta}$ and each
sample from $P^{\delta}$ can be simulated by 1 sample from $P$.

  2. -

For every $i:1\leq i\leq n$ and $j\in\Sigma$,
$P_{i}^{\delta}(j)\geq\delta/|\Sigma|$.

  3. -

$\mbox{$d^{2}_{\mathrm{H}}$}(P,P^{\delta})\leq 2n\delta$

###### Proof.

The first part is obvious from the sampling process. For the second part,
$P_{i}^{\delta}(j)=(1-\delta)P_{i}(j)+\delta/|\Sigma|\geq\delta/|\Sigma|$ for
every $i,j$.

The proof of the third part can be obtained by generalizing the proof of
Daskalakis, Kamath, and Wright [2018]. Consider the $i$-th component of $P$
and $P^{\delta}$, denoted $P_{i}$ and $Q_{i}$ respectively for convenience.
Let $E_{i}$ be the event that $r_{i}=0$. Also note that conditioned on the
event $E_{i}$, for any item $j\in\Sigma,$ the probability values satisfy
$Q_{i}(j\mid E_{i})=P_{i}(j)$.

$\displaystyle\mbox{$d^{2}_{\mathrm{H}}$}(P_{i},Q_{i})$
$\displaystyle=\sum_{j\in\Sigma}\left(\sqrt{Q_{i}(j)}-\sqrt{P_{i}(j)}\right)^{2}$
$\displaystyle=\sum_{j\in\Sigma}\left(\sqrt{Q_{i}(j\mid
E_{i})\mathrm{Pr}(E_{i})+Q_{i}(j\mid\bar{E}_{i})\mathrm{Pr}(\bar{E}_{i})}-\sqrt{P_{i}(j)}\right)^{2}$
$\displaystyle=\sum_{j}\left(\sqrt{P_{i}(j)\mathrm{Pr}(E_{i})}-\sqrt{P_{i}(j)}\right)^{2}+\sum_{j}Q_{i}(j\mid\bar{E}_{i})\mathrm{Pr}(\bar{E}_{i})$
(Using
$(\sqrt{a+b}-\sqrt{c+d})^{2}\leq(\sqrt{a}-\sqrt{c})^{2}+(\sqrt{b}-\sqrt{d})^{2}$
for non-negative $a,b,c,d$)
$\displaystyle=(1-\sqrt{\mathrm{Pr}(E_{i})})^{2}+\mathrm{Pr}(\bar{E}_{i})$
$\displaystyle=(1-\sqrt{1-\mathrm{Pr}(\bar{E}_{i})})^{2}+\mathrm{Pr}(\bar{E}_{i})$
$\displaystyle\leq 2\mathrm{Pr}(\bar{E}_{i})=2\delta$ (Using
$(1-\sqrt{1-x})^{2}\leq x$ for $0\leq x\leq 1$)

Then 3.2 gives us $\mbox{$d^{2}_{\mathrm{H}}$}(P,P^{\delta})\leq 2n\delta$ due
to sub-additivity. ∎

######  Lemma 3.5.

Let $P=\prod_{i=1}^{n}P_{i}$ and $Q=\prod_{i=1}^{n}Q_{i}$ be two
distributions, both over the common sample space $\Sigma^{n}$. Let
$\ell=|\Sigma|$, $R=P^{\delta}$, $S=Q^{\delta}$ with
$\delta=\epsilon^{2}/50n$. $R=\prod_{i=1}^{n}R_{i}$ and
$S=\prod_{i=1}^{n}S_{i}$, where $R_{i}=\langle
r_{i1},r_{i2},\dots,r_{i\ell}\rangle$ and $S_{i}=\langle
s_{i1},s_{i2},\dots,s_{i\ell}\rangle$ for every $i$. Then

  * (1)

If $\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ then
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}<0.12\epsilon^{2}$.

  * (2)

If $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$ then
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}>0.18\epsilon^{2}$.

###### Proof.

(Proof of (1)) We have that $r_{ij}=(1-\delta)p_{ij}+\delta/\ell$ and
$s_{ij}=(1-\delta)q_{ij}+\delta/\ell$. Then,
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over
s_{ij}}=\sum_{i,j}{(1-\delta)^{2}(p_{ij}-q_{ij})^{2}\over(1-\delta)q_{ij}+\delta/\ell}\leq\sum_{i,j}{(1-\delta)^{2}(p_{ij}-q_{ij})^{2}\over(1-\delta)q_{ij}}=(1-\delta)\sum_{i,j}{(p_{ij}-q_{ij})^{2}\over
q_{ij}}<\sum_{i}\sum_{j}\allowbreak{(p_{ij}-q_{ij})^{2}\over
q_{ij}}=\sum_{i}\mbox{$d_{\mathrm{\chi}^{2}}$}(P_{i},Q_{i})\leq\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)<0.12\epsilon^{2}$
. The second last step is due to 3.1.

(Proof of (2)). From 3.4, for $\delta=\epsilon^{2}/50n$, it follows that
$\mbox{$d^{2}_{\mathrm{H}}$}(P,R)\leq\epsilon^{2}/25$ and
$\mbox{$d^{2}_{\mathrm{H}}$}(Q,S)\leq\epsilon^{2}/25$. By triangle inequality
we get
$\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\mbox{$d_{\mathrm{H}}$}(R,S)+\mbox{$d_{\mathrm{H}}$}(P,R)+\mbox{$d_{\mathrm{H}}$}(Q,S)$.
It follows that if $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$ then
$\mbox{$d_{\mathrm{H}}$}(R,S)\geq\epsilon(1/\sqrt{2}-2/5)$. Then 3.3 gives
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over
s_{ij}}=\sum_{i}\mbox{$d_{\mathrm{\chi}^{2}}$}(R_{i},S_{i}))\geq
2\mbox{$d^{2}_{\mathrm{H}}$}(R,S)>0.18\epsilon^{2}$. ∎

At this point it remains to test $\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over
s_{ij}}>0.18\epsilon^{2}/10$ versus $<0.12\epsilon^{2}/10$, which we perform
using the tester of Acharya, Daskalakis, and Kamath [2015]. We state their
tester with necessary modifications and prove it in the Appendix.

######  Theorem 3.6.

(Modified from Acharya, Daskalakis, and Kamath [2015]) Let $m$ be an integer
and $0<\epsilon<1$ be an error parameter. Let $r_{1},r_{2},\ldots,r_{K}$ be
$K$ non-negative real numbers. Let $s_{1},s_{2},\ldots,s_{K}$ be non-negative
real numbers such that $s_{i}\geq\epsilon^{2}/50K$. For $1\leq i\leq K$, let
$N_{i}\sim{\rm Poi}(mr_{i})$ be independent samples from ${\rm Poi}(mr_{i})$.
Then there exists a test statistic $T,$ computable in time $O(K)$ from inputs
$N_{i}$s and $s_{i}$s, with the following guarantees.

  * -

$\mathrm{E}[T]=m\sum_{i}{(r_{i}-s_{i})^{2}\over s_{i}}$

  * -

$\mathrm{Var}[T]\leq 2K+7\sqrt{K}\mathrm{E}[T]+4K^{1/4}(\mathrm{E}[T])^{3/2}$,
for a constant $c$ and $m\geq c\sqrt{K}/\epsilon^{2}$.

##### Remark

The test $T$ of Acharya, Daskalakis, and Kamath [2015] is given by
$T=\Sigma_{i=1}^{n}{(N_{i}-ms_{i})^{2}-N_{i}\over ms_{i}}$. Their paper gives
the upper bound $\mathrm{Var}[T]\leq 4n+9\sqrt{n}\mathrm{E}[T]+{2\over
5}n^{1\over 4}\mathrm{E}[T]^{3/2}$ under the assumption
$s_{i}\geq\epsilon/50n$ for every $i$. In our application, $\ell$ is the
alphabet size and we will need the bound to depend on $\ell$. In addition, we
also need the bounds to work when $s_{i}\geq\epsilon^{2}/50n\ell$. Both these
can be achieved by modifying their proof.

It remains to sample numbers $N_{ij}\sim\mathrm{Poi}(mr_{ij})$ independently
for every $i,j$. We do this via poissonization followed by sampling from each
coordinate of the product distribution $R$ independently. We present Algorithm
1 with its correctness.

1 for  _$i=1$ to $n$_ do

2 Sample $N_{i}\sim\mathrm{Poi}(m)$ independently;

3

4 end for

5$N=\max_{i}N_{i}$;

6 $X\leftarrow$ Take $N$ samples from $R$;

7 for  _$i=1$ to $n$_ do

8 $X_{i}\leftarrow$ Sequence of symbols in the $i$-th coordinate of first
$N_{i}$ samples of $X$;

9 $\langle N_{i1},N_{i1},\dots,N_{i\ell}\rangle\leftarrow$ histogram of
symbols in $X_{i}$;

10

11 end for

12Compute statistic $T$ of 3.6 using $N_{ij}$ and $s_{ij}$ values for every
$i,j$;

13 if  _$T\leq 0.15m\epsilon^{2}$_ then

14 output ‘yes.’;

15else

16 output ‘no.’

17 end if

Algorithm 1 Given samples from an unknown distribution
$R=\prod_{i=1}^{n}R_{i}$ and a known distribution $S=\prod_{i=1}^{n}S_{i}$
over $\Sigma^{n}$, decide
$\mbox{$d_{\mathrm{\chi}^{2}}$}(R,S)\leq\epsilon^{2}/9$ (‘yes’) versus
$\sqrt{2}\mbox{$d_{\mathrm{H}}$}(R,S)>\epsilon$ (‘no’). Let $\ell=|\Sigma|$,
$R_{i}=\langle r_{i1},r_{i2},\dots,r_{i\ell}\rangle$, $S_{i}=\langle
s_{i1},s_{i2},\dots,s_{i\ell}\rangle$ with $s_{ij}\geq\epsilon^{2}/50n\ell$
for every $j$, for every $i$

###### Proof.

(of 2.3) Let $\ell=|\Sigma|$. First, we transform the distributions $P$ and
$Q$ into the distributions $R$ and $S$ respectively according to the
modification process mentioned in 3.5. This gives:

  1. -

Each sample from $R$ can be simulated by 1 sample from $P$.

  2. -

$R$ and $S$ are product distributions, $R=\prod_{i=1}^{n}R_{i}$ and
$S=\prod_{i=1}^{n}S_{i}$, where $R_{i}=\langle
r_{i1},r_{i2},\dots,r_{i\ell}\rangle$ and $S_{i}=\langle
s_{i1},s_{i2},\dots,s_{i\ell}\rangle$ for every $i$.

  3. -

For every $i,j$, $s_{ij}\geq\epsilon^{2}/50n\ell$.

  4. -

If $\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ then
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}<0.12\epsilon^{2}$.

  5. -

If $\sqrt{2}\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ then
$\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}>0.18\epsilon^{2}$.

Henceforth, we focus on distinguishing $\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over
s_{ij}}<0.12\epsilon^{2}$ versus $>0.18\epsilon^{2}$, under the assumption
$s_{ij}\geq\epsilon^{2}/50n\ell$ for every $i,j$, by sampling from $R$. We use
the tester $T$ of Acharya, Daskalakis, and Kamath [2015] stated in 3.6 with
$K=n\ell$, for this. Firstly, note that in Algorithm 1, the samples $S_{i}$ is
a set of $N_{i}\sim\mathrm{Poi}(m)$ samples from $R_{i}$, independently for
every $i$’s. This is because the set of samples are taken from the product
distribution $R=R_{1}\times R_{2}\times\dots\times R_{n}$ and the $N_{i}$
values are independent for different $i$’s. Due to Poissonization it follows
$N_{ij}\sim\mathrm{Poi}(r_{ij})$ independently for every $i,j$. The tester $T$
requires $m\geq c\sqrt{n\ell}/\epsilon^{2}$, for some constant $c$ and
satisfies $\mathrm{E}[T]=m\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}$,
$\mathrm{Var}[T]\leq
2n\ell+7\sqrt{n\ell}\mathrm{E}[T]+4(n\ell)^{1/4}(\mathrm{E}[T])^{3/2}$.

If $\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}<0.12\epsilon^{2}$ then we get
$\mathrm{E}[T]\leq 0.12m\epsilon^{2}$ and $\mathrm{Var}[T]\leq\left({2\over
c^{2}}+{0.84\over c}+{4(0.12)^{3}\over\sqrt{c}}\right)m^{2}\epsilon^{4}$,
using $m\geq c\sqrt{nl}/\epsilon^{2}$ and the upper bound for $\mathrm{E}[T]$.
By Chebyshev’s inequality $T<0.15m\epsilon^{2}$ with probability at least 4/5,
where $c=\Omega(1)$ is an appropriate constant.

If $\sum_{i,j}{(r_{ij}-s_{ij})^{2}\over s_{ij}}>0.18\epsilon^{2}$ then we get
$\mathrm{E}[T]>0.18m\epsilon^{2}\geq 0.18c\sqrt{nl}$ and
$\mathrm{Var}[T]\leq({2\over(0.18c)^{2}}+{7\over
0.18c}+{4\over\sqrt{0.18c}})\mathrm{E}^{2}[T]$. By Chebyshev’s inequality
$T>0.15m\epsilon^{2}$ with probability at least 4/5, for an appropriate
constant $c=\Omega(1)$.

Hence, for some constant $c^{\prime}$, $m\geq
c^{\prime}\sqrt{n\ell}/\epsilon^{2}$ suffices for the tester $T$ to
distinguish the above two cases. It also follows from the concentration of the
Poisson distribution that the number of samples required is $\max_{i}N_{i}\leq
2m$, except for probability at most $n\cdot\exp(-m)<1/10$ (using union bound).

The histograms can be computed by a single pass over the $n$-dimensional
sample set $S$. The statistic $T$ can be computed in time $O(n\ell)$. So the
time complexity is $O(n\ell+n^{3/2}\sqrt{\ell}/\epsilon^{2})$. ∎

###  3.2 $d_{\mathrm{H}}$-vs-$d_{\mathrm{H}}$ Tolerant Closeness Tester

In this section, we give a tester for distinguishing
$\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon$ versus
$\mbox{$d_{\mathrm{H}}$}(P,Q)>3\epsilon$ for two unknown product distributions
$P$ and $Q$ over support $\Sigma^{n}$. To get 2.4, we rescale $\epsilon$ down
to $\epsilon/\sqrt{2}$. We take a testing-by-learning approach: we first learn
$P$ and $Q$ in Hellinger distance $\epsilon/2$ using the following known
result. Then the Hellinger distance between the learnt distributions can be
computed exactly.

######  Theorem 3.7.

[Acharya, Daskalakis, and Kamath, 2015] Given samples from an unknown product
distribution $D$ over $\Sigma^{n}$, $\hat{D}$, the product of component-wise
empirical distributions on $m$ samples satisfy
$\mbox{$d_{\mathrm{H}}$}(D,\hat{D})\leq\epsilon$ with $9/10$ probability if
$m\geq\Theta(n|\Sigma|/\epsilon^{2})$.

###### Proof.

(of 2.4) We first learn $P$ and $Q$ as $\hat{P}$ and $\hat{Q}$ using 3.7 such
that $\mbox{$d_{\mathrm{H}}$}(P,\hat{P})\leq\epsilon/2$ and
$\mbox{$d_{\mathrm{H}}$}(Q,\hat{Q})\leq\epsilon/2$, together with 4/5
probability. Conditioned on this. we compute
$\mbox{$d_{\mathrm{H}}$}(\hat{P},\hat{Q})$ exactly using 3.2.

Due to triangle inequality, $\mbox{$d_{\mathrm{H}}$}(\hat{P},\hat{Q})\leq
2\epsilon$ or not would decide $\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon$ or
$>3\epsilon$. ∎

##  4 Lower Bounds

In this section, we give lower bounds for tolerant testing of product
distributions. Our lower bounds use a reduction from testing the class of
unstructured distributions over $n$ items to testing the class of product
distributions over $\\{0,1\\}^{n}$, given by Canonne, Diakonikolas, Kane, and
Stewart [2017] (Section 4.5 of their paper). However, in order to apply this
reduction, we need to establish certain new bounds relating the distances in
the unstructured setting to the setting of product distribution. We first
define how to construct a product distribution from the corresponding
unstructured distribution. In particular, for a $\delta<1$, this construction
produces a product distribution $F_{\delta}(P)$ over $\\{0,1\\}^{n}$ from a
given distribution $P$ over $n$ symbols.

######  Definition 4.1.

(Construction of $F_{\delta}(P)$) Let $P$ be a distribution over a sample
space of $n$ items and $0<\delta\leq 1$ be a constant. Let $S$ be a random set
of $\mathrm{Poi}(\delta)$ samples from $P$. For every item $i\in[n]$, let
$x_{i}$ be the indicator variable such that $x_{i}=1$ iff $i$ appears in $S$.
Let $F_{\delta}(P)$ be the joint distribution of $\langle
x_{1},x_{2},\dots,x_{n}\rangle$ over the sample space $\\{0,1\\}^{n}$.

The following property can be observed using the property of Poissonization.

######  Fact 4.2.

Let $P$ be a distribution over a sample space of $n$ items with probability
vector $\langle p_{1},p_{2},\dots,p_{n}\rangle$ and $0<\delta\leq 1$ be a
constant. Then $F_{\delta}(P)$ is a product distribution such that
$F_{\delta}(P)=\prod_{i=1}^{n}F_{\delta}(P_{i})$ where
$F_{\delta}(P_{i})\sim\mathrm{Bern}(1-e^{-\delta p_{i}})$.

We use the following crucial lemma.

######  Lemma 4.3.

For any $0<\delta\leq 1$ and distributions $P,Q$,
$\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P),F_{\delta}(Q))\geq\delta
e^{-\delta}\mbox{${d}_{\mathrm{TV}}$}(P,Q)$, with equality holding iff $P=Q$.

###### Proof.

Let $P=\langle p_{1},\dots,p_{i},\dots,p_{n}\rangle$ and $Q=\langle
q_{1},\dots,q_{i},\dots,q_{n}\rangle$ be the probability values of $P$ and
$Q$.

$\displaystyle\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P),F_{\delta}(Q))$
$\displaystyle=\sum_{x\in\\{0,1\\}^{n}}|F_{\delta}(P)(x)-F_{\delta}(Q)(x)|$
$\displaystyle\geq\sum_{i=1}^{n}|F_{\delta}(P)(e_{i})-F_{\delta}(Q)(e_{i})|$
(unit vector $e_{i}$ has $i$-th value 1)
$\displaystyle=\sum_{i=1}^{n}|(1-e^{-\delta p_{i}})\Pi_{j\neq i}e^{-\delta
p_{j}}-(1-e^{-\delta q_{i}})\Pi_{j\neq i}e^{-\delta q_{j}}|$
$\displaystyle=\sum_{i=1}^{n}e^{-\delta}|e^{\delta p_{i}}-e^{\delta q_{i}}|$
(Since $\Pi_{j}e^{-\delta p_{j}}=\Pi_{j}e^{-\delta q_{j}}=e^{-\delta}$)
$\displaystyle=e^{-\delta}\sum_{i=1}^{n}|\delta(p_{i}-q_{i})+\delta^{2}(p_{i}^{2}-q_{i}^{2})/2!+\dots+\delta^{j}(p_{i}^{j}-q_{i}^{j})/j!+\dots|.$

We analyze the expression under modulus under two cases: 1) if $p_{i}>q_{i}$,
it is more than $\delta(p_{i}-q_{i})$, 2) if $p_{i}<q_{i}$, it is more than
$\delta(q_{i}-p_{i})$.

$\displaystyle\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P),F_{\delta}(Q))$
$\displaystyle\geq e^{-\delta}\sum_{i=1}^{n}|\delta(p_{i}-q_{i})|$
$\displaystyle=\delta e^{-\delta}\mbox{${d}_{\mathrm{TV}}$}(P,Q).$

∎

###  4.1 Hardness of $d_{\mathrm{\chi}^{2}}$-vs-${d}_{\mathrm{TV}}$ Tolerant
Closeness Testing

Here we show that for two unknown product distribution $P,Q$ over
$\\{0,1\\}^{n}$, distinguishing
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P,Q)\leq\epsilon^{2}/9$ versus
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$, for a constant $\epsilon$, can not
be decided in general with a truly sublinear sample complexity. We use a
reduction to the following difficult problem, for hardness of
$\chi^{2}$-tolerance for closeness testing of unstructured distributions over
$n$ items, given in Daskalakis, Kamath, and Wright [2018]. We restate the
theorem with changes in the constants.

######  Theorem 4.4.

There exists a constant $0<\epsilon<1$ and three distributions
$P^{yes},P^{no}$ and $Q$, each over the sample space $[n]$ such that: (1)
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P^{yes},Q)\leq\epsilon^{2}/216$, whereas
$\mbox{${d}_{\mathrm{TV}}$}(P^{no},Q)\geq\epsilon$ and (2) given only sample
accesses to one of $P^{yes}$ or $P^{no}$, and $Q$, distinguishing $P^{yes}$
versus $P^{no}$ with probability $>4/5$, requires $\Omega(n/\log n)$ samples.

We use the following important property about the $\chi^{2}$-distance between
the reduced distributions.

######  Lemma 4.5.

$\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P),F_{\delta}(Q))\leq\exp(4\delta\cdot\chi^{2}(P,Q))-1$,
for any $0<\delta\leq 1$.

###### Proof.

From 4.2, both $F_{\delta}(P)$ and $F_{\delta}(Q)$ are product distributions,
the distribution of the $i$-th component being $F_{\delta}(P_{i})$ and
$F_{\delta}(Q_{i})$ respectively. Let $P=\langle
p_{1},p_{2},\dots,p_{n}\rangle$ and $Q=\langle
q_{1},q_{2},\dots,q_{n}\rangle$. Then
$F_{\delta}(P_{i})\sim\mathrm{Bern}(1-e^{-\delta p_{i}})$ and
$F_{\delta}(Q_{i})\sim\mathrm{Bern}(1-e^{-\delta q_{i}})$.

$\displaystyle\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P),F_{\delta}(Q))$
$\displaystyle=\prod_{i}(1+\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P_{i}),F_{\delta}(Q_{i})))-1$
(From 3.1)
$\displaystyle\leq\prod_{i}\exp(\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P_{i}),F_{\delta}(Q_{i})))-1$
(Since $e^{x}\geq(1+x)$ for $x\geq 0$)
$\displaystyle=\exp(\sum_{i}\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P_{i}),F_{\delta}(Q_{i})))-1$
$\displaystyle=\exp\left(\sum_{i}(e^{-\delta p_{i}}-e^{-\delta
q_{i}})^{2}\left({1\over e^{-\delta q_{i}}}+{1\over 1-e^{-\delta
q_{i}}}\right)\right)-1$ (Since
$F_{\delta}(P^{yes}_{i})\sim\mathrm{Bern}(1-e^{-\delta p_{i}})$ and
$F_{\delta}(Q_{i})\sim\mathrm{Bern}(1-e^{-\delta q_{i}})$)
$\displaystyle=\exp(\sum_{i}(e^{-\delta p_{i}}-e^{-\delta
q_{i}})^{2}/e^{-\delta q_{i}}(1-e^{-\delta q_{i}}))-1$
$\displaystyle=\exp(\sum_{i}(e^{\delta(q_{i}-p_{i})}-1)^{2}/(e^{\delta
q_{i}}-1))-1$
$\displaystyle=\exp(\sum_{i}(e^{\delta(q_{i}-p_{i})}-1)^{2}/(e^{\delta
q_{i}}-1))-1$ $\displaystyle\leq\exp(\sum_{i}(2\delta(p_{i}-q_{i}))^{2}/\delta
q_{i}))-1$ (Since $(e^{x}-1)\geq x$ and $(|e^{x}-1|\leq 2|x|$ for $0<|x|<1$)
$\displaystyle=\exp(4\delta\chi^{2}(P,Q))-1.$

∎

We are set to present the main lower bound result of this section.

See 2.7

###### Proof.

We start with the hard distributions $P^{yes},P^{no}$ and $Q$ from 4.4. Then
$\mbox{$d_{\mathrm{\chi}^{2}}$}(P^{yes},Q)\leq\epsilon^{2}/216$ and
$\mbox{${d}_{\mathrm{TV}}$}(P^{no},Q)\geq\epsilon$ for some constant
$0<\epsilon<1$. We apply the reduction of 4.1 with $\delta=1/3$ to these three
distributions. Then from 4.3 and 4.5 we get the following two inequalities:

  * •

$\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P^{yes}),F_{\delta}(Q))\leq\exp(4\chi^{2}(P^{yes},Q)/3)-1<\epsilon^{2}/160$.

  * •

$\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P^{no}),F_{\delta}(Q))>(1/3e^{1/3})\epsilon$.

It follows if we can distinguish
$\mbox{$d_{\mathrm{\chi}^{2}}$}(F_{\delta}(P^{yes}),F_{\delta}(Q))\leq\epsilon^{2}/160$
versus
$\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P^{no}),F_{\delta}(Q))>(1/3e^{1/3})\epsilon$,
then we are able to decide the hard instance of 4.4. Moreover, in order to
simulate each sample from the distribution $F_{1/2}(P)$, we need
$\mathrm{Poi}(1/2)$ samples from $P$. So, if we need $m$ samples in total,
from the additive property of the Poisson distribution, we need
$\mathrm{Poi}(m/2)=O(m)$ samples from $P$ in total, except for $\exp(-m)$
probability. It follows, if we can decide the problem given in the theorem
statement in $o(n/\log n)$ samples, we can decide the hard problem of 4.4 in
$o(n/\log n)$ samples as well. This leads to a contradiction. Replacing the
constant $\epsilon$ by $3e^{1/3}\epsilon_{1}$, we get 2.7. ∎

###  4.2 Hardness of $d_{\mathrm{KL}}$-vs-${d}_{\mathrm{TV}}$ Tolerant
Identity Testing

In this section we show that for an unknown product distribution $P$ and a
known product distribution $Q$ over $\\{0,1\\}^{n}$, distinguishing
$\mbox{$d_{\mathrm{KL}}$}(P,Q)\leq\epsilon^{2}/9$ versus
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)>\epsilon$, for a constant $\epsilon$, cannot
be decided in general with a truly sublinear sample complexity. We use a
reduction to the following hardness result, for identity testing of
unstructured distributions over $n$ items under $\mathrm{KL}$-tolerance, given
in Daskalakis, Kamath, and Wright [2018]. We restate the theorem with changes
in the constants. For a probability distribution $P=\langle
p_{1},p_{2},\dots,p_{n}\rangle$ over $n$ items,
$||P||_{2}^{2}=\sum_{i}p_{i}^{2}$.

######  Theorem 4.6.

There exists a constant $0<\epsilon<1$ and three distributions
$P^{yes},P^{no}$ and $Q$, each over the sample space $[n]$ such that: (1)
$\mbox{$d_{\mathrm{KL}}$}(P^{yes},Q)\leq\epsilon^{2}/216$, whereas
$\mbox{${d}_{\mathrm{TV}}$}(P^{no},Q)\geq\epsilon$, (2)
$||P^{yes}||_{2}^{2}=O(\log^{2}n/n)$, and (3) given only sample accesses to
one of $P^{yes}$ or $P^{no}$, and complete knowledge of $Q$, distinguishing
$P^{yes}$ versus $P^{no}$ with probability $>4/5$, requires $\Omega(n/\log n)$
samples.

###### Proof.

The proof of this Theorem appears in Daskalakis, Kamath, and Wright [2018] (in
Theorem 6.2 of this version), except the fact
$||P^{yes}||_{2}^{2}=O(\log^{2}n/n)$ is not explicitly claimed. We prove this
claim in the following, by observing from the original construction given in
the paper by Valiant and Valiant [2010].

The hard distribution $P^{yes}$ is the distribution $p^{-}_{\log k,\phi}$ as
defined in Definition 12 of Valiant and Valiant [2010]. We use the following
facts about this distribution $p^{-}_{\log k,\phi}$, given in Fact 11,
Definition 12 and (in the end of the second paragraph in the proof of) Lemma
13 in Valiant and Valiant [2010]:

  * •

$\phi$ is a small enough constant

  * •

The support size $n$ and the parameter $k$ are related as $n=32k\log k/\phi$

  * •

The ‘un-normalized’ mass at each point is $x/32k$, where $j=\log k$ and $x\leq
4j$

  * •

The ‘normalizing constant’ $c_{2}$ (which makes the probability values sum up
to 1) is at most $\phi/j$ where $j=\log k$

From these facts we conclude each probability mass is $c_{2}\cdot
x/32k\leq\phi/8k$, where $n=32k\log k/\phi$ for some constant $\phi$. Hence,
$||P^{yes}||_{2}^{2}\leq\phi^{2}/64k^{2}\cdot 32k\log k/\phi=\phi\log
k/2k=O(\log^{2}n/n)$. ∎

We use the reduction given in 4.1. We establish the following lemma, relating
KL distances between the original and the reduced distributions.

######  Lemma 4.7.

$\mbox{$d_{\mathrm{KL}}$}(F_{\delta}(P),F_{\delta}(Q))\leq\left(\delta+{\delta^{2}\over
2}\right)\mbox{$d_{\mathrm{KL}}$}(P,Q)+{3\delta^{2}\over 2}||P||_{2}^{2}$, for
any $0<\delta\leq 1$.

###### Proof.

We use the following fact about the $\mathrm{KL}$-distance between two product
distributions.

######  Fact 4.8.

For two distributions $P=\prod_{i=1}^{n}P_{i}$ and $Q=\prod_{i=1}^{n}Q_{i}$
over the same discrete sample space, it holds that
$\mbox{$d_{\mathrm{KL}}$}(P,Q)=\sum_{i=1}^{n}\mbox{$d_{\mathrm{KL}}$}(P_{i},Q_{i})$.

From 4.2, both $F_{\delta}(P)$ and $F_{\delta}(Q)$ are product distributions,
the distribution of the $i$-th component being $F_{\delta}(P_{i})$ and
$F_{\delta}(Q_{i})$ respectively. Let $P=\langle
p_{1},p_{2},\dots,p_{n}\rangle$ and $Q=\langle
q_{1},q_{2},\dots,q_{n}\rangle$. Then
$F_{\delta}(P_{i})\sim\mathrm{Bern}(1-e^{-\delta p_{i}})$ and
$F_{\delta}(Q_{i})\sim\mathrm{Bern}(1-e^{-\delta q_{i}})$.

$d_{\mathrm{KL}}$ $\displaystyle(F_{\delta}(P),F_{\delta}(Q))$
$\displaystyle=\sum_{i}\mbox{$d_{\mathrm{KL}}$}(F_{\delta}(P_{i}),F_{\delta}(Q_{i}))$
$\displaystyle=\sum_{i}\left[(1-e^{-\delta p_{i}})\ln\left({1-e^{-\delta
p_{i}}\over 1-e^{-\delta q_{i}}}\right)+e^{-\delta p_{i}}\ln{e^{-\delta
p_{i}}\over e^{-\delta q_{i}}}\right]$
$\displaystyle=\sum_{i}\ln\left({1-e^{-\delta p_{i}}\over 1-e^{-\delta
q_{i}}}\right)+\sum_{i}e^{-\delta p_{i}}\ln{e^{-\delta p_{i}}(1-e^{-\delta
q_{i}})\over e^{-\delta q_{i}}(1-e^{-\delta p_{i}})}$
$\displaystyle=\sum_{i}\ln{e^{\delta q_{i}}(e^{\delta p_{i}}-1)\over e^{\delta
p_{i}}(e^{\delta q_{i}}-1)}+\sum_{i}e^{-\delta p_{i}}\ln\left({e^{\delta
q_{i}}-1\over e^{\delta p_{i}}-1}\right)$ $\displaystyle=\sum_{i}\ln{e^{\delta
q_{i}}\over e^{\delta p_{i}}}+\sum_{i}\ln\left({e^{\delta p_{i}}-1\over
e^{\delta q_{i}}-1}\right)+\sum_{i}e^{-\delta p_{i}}\ln\left({e^{\delta
q_{i}}-1\over e^{\delta p_{i}}-1}\right)$
$\displaystyle=\sum_{i}(q_{i}-p_{i})+\sum_{i}(1-e^{-\delta
p_{i}})\ln\left({e^{\delta p_{i}}-1\over e^{\delta q_{i}}-1}\right)$
$\displaystyle=\sum_{i}(1-e^{-\delta p_{i}})\ln\left({e^{\delta p_{i}}-1\over
e^{\delta q_{i}}-1}\right)$ (Since $\sum_{i}p_{i}=\sum_{i}q_{i}=1$)
$\displaystyle=\sum_{p_{i}>q_{i}}(1-e^{-\delta p_{i}})\ln\left({e^{\delta
p_{i}}-1\over e^{\delta q_{i}}-1}\right)+\sum_{q_{i}>p_{i}}(1-e^{-\delta
p_{i}})\ln\left({e^{\delta p_{i}}-1\over e^{\delta q_{i}}-1}\right)$
$\displaystyle\leq\sum_{p_{i}>q_{i}}\delta p_{i}\ln\left({e^{\delta
p_{i}}-1\over e^{\delta q_{i}}-1}\right)+\sum_{q_{i}>p_{i}}\left(\delta
p_{i}-{1\over 2}\delta^{2}p_{i}^{2}\right)\ln\left({e^{\delta p_{i}}-1\over
e^{\delta q_{i}}-1}\right)$ $\displaystyle=\sum_{i}\delta
p_{i}\ln\left({e^{\delta p_{i}}-1\over e^{\delta
q_{i}}-1}\right)+\sum_{q_{i}>p_{i}}{\delta^{2}p_{i}^{2}\over
2}\ln\left({e^{\delta q_{i}}-1\over e^{\delta p_{i}}-1}\right)$
$\displaystyle\leq\sum_{i}\delta p_{i}\ln\left({\delta p_{i}(1+\delta
p_{i})\over\delta q_{i}}\right)+\sum_{q_{i}>p_{i}}{\delta^{2}p_{i}^{2}\over
2}\ln\left(\delta q_{i}(1+\delta q_{i})\over\delta p_{i}\right)$
$\displaystyle=\delta\left(\sum_{i}p_{i}\ln{p_{i}\over
q_{i}}+\sum_{i}p_{i}\ln(1+\delta p_{i})\right)+{\delta^{2}\over
2}\left(\sum_{q_{i}>p_{i}}p_{i}^{2}\ln{q_{i}\over
p_{i}}+\sum_{q_{i}>p_{i}}p_{i}^{2}\ln(1+\delta q_{i})\right)$
$\displaystyle\leq\left(\delta+{\delta^{2}\over
2}\right)\sum_{i}p_{i}\ln{q_{i}\over p_{i}}+{3\delta^{2}\over
2}\sum_{i}p_{i}^{2}$ $\displaystyle=\left(\delta+{\delta^{2}\over
2}\right)\mbox{$d_{\mathrm{KL}}$}(P,Q)+{3\delta^{2}\over 2}||P||_{2}^{2}.$

∎

Now we present the lower bound for closeness testing of product distributions.

See 2.6

###### Proof.

We start with the distributions $P^{yes},P^{no}$ and $Q$ from the hardness
result 4.6. Then $\mbox{$d_{\mathrm{KL}}$}(P^{yes},Q)\leq\epsilon^{2}/216$,
$||P^{yes}||_{2}^{2}=O(\log^{2}n/n)$ and
$\mbox{${d}_{\mathrm{TV}}$}(P^{no},Q)\geq\epsilon$ for some constant
$0<\epsilon<1$. We apply the reduction of 4.1, with $\delta=1/3$ to these
three distributions. Then from 4.3 and 4.7 we get the following two:

  * •

$\mbox{$d_{\mathrm{KL}}$}(F_{\delta}(P^{yes}),F_{\delta}(Q))\leq\epsilon^{2}/160$,
for any large enough $n$.

  * •

$\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P^{no}),F_{\delta}(Q))>(1/3e^{1/3})\epsilon$.

It follows if we can distinguish
$\mbox{$d_{\mathrm{KL}}$}(F_{\delta}(P^{yes}),F_{\delta}(Q))\leq\epsilon^{2}/160$
versus
$\mbox{${d}_{\mathrm{TV}}$}(F_{\delta}(P^{no}),F_{\delta}(Q))>(1/3e^{1/3})\epsilon$,
then we will be able to decide the hard instance of 4.4. Moreover, in order to
simulate each sample from the distribution $F_{1/2}(P)$, we need
$\mathrm{Poi}(1/2)$ samples from $P$. So, if we need $m$ samples in total,
from the additive property of the Poisson distribution, we need
$\mathrm{Poi}(m/2)=O(m)$ samples from $P$ in total, except for $\exp(-m)$
probability. It follows, if we can decide the problem given in the Theorem
statement in $o(n/\log n)$ samples, we can decide the hard problem of 4.6 in
$o(n/\log n)$ samples as well. This leads to a contradiction. Replacing the
constant $\epsilon$ by $3e^{1/3}\epsilon_{1}$, we get 2.6. ∎

Before moving on to the next section, we note that recently the question of
${d}_{\mathrm{TV}}$-versus-${d}_{\mathrm{TV}}$ tolerant testing problem for
uniformity testing of distributions over $[n]$ was settled to be
$\Theta({n\over\log n}{1\over\epsilon^{2}})$ by Jiao, Han, and Weissman
[2018]. In particular, this gives a stronger guarantee for 4.4 and 4.6 when
$\epsilon$ is not a constant. This directly strengthens our 2.7; also 2.6
whenever $||P_{yes}||_{2}^{2}=O(\epsilon^{2})$, giving us a
$\Omega({n\over\log n}{1\over\epsilon^{2}})$ lower bound for any $\epsilon$.

###  4.3 Hardness of non-tolerant ${d}_{\mathrm{TV}}$ Identity Testing for
General Alphabets

Daskalakis, Dikkala, and Kamath [2019] and Canonne, Diakonikolas, Kane, and
Stewart [2017] have given optimal lower bounds for non-tolerant testing w.r.t.
${d}_{\mathrm{TV}}$ distance when $\lvert\Sigma\rvert=2$. In this section, we
generalize their result for $\Sigma>2$ case and get an optimal lower bound in
regard to 2.3. We show the following theorem, generalizing the proof of
Daskalakis, Dikkala, and Kamath [2019] specifically. See 2.5

Our hard distributions are as follows:

$P=$ the uniform distribution over $[\ell]^{n}$.

$Q=$ a radom distribution from the mixture
$\left\\{\left\\{{1\over\ell}\left(1\pm{\epsilon\over\sqrt{n}}\right)\right\\}^{{\ell\over
2}}\right\\}^{n}$. Each distribution of the mixture is a product distribution,
whose $i$-th component is a distribution over $[\ell]$, which randomly assigns
probability values either
${1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right),{1\over\ell}\left(1-{\epsilon\over\sqrt{n}}\right)$
or
${1\over\ell}\left(1-{\epsilon\over\sqrt{n}}\right),{1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right)$,
based on a random vector from $\\{0,1\\}^{{\ell\over 2}}$, for every
consecutive sample space items from $[\ell]$.

First claim we show is that each member of the mixture is $\Theta(\epsilon)$
far from $P$ in ${d}_{\mathrm{TV}}$ distance.

######  Claim 4.9.

Let $Q^{*}$ be any member of $Q$. Then
$\mbox{${d}_{\mathrm{TV}}$}(P,Q^{*})\geq\Theta(\epsilon)$.

###### Proof.

Note that all members of the mixture $Q$ are permutations of each other. Since
$P$ is fixed to the uniform distribution, all of them have the same
${d}_{\mathrm{TV}}$ to $P$. We fix $Q^{*}$ to be the distribution from $Q$,
corresponding to $\\{0,1\\}^{\ell/2}$ at every component.

It is a known fact that applying a common function to the sample space items
can only reduce ${d}_{\mathrm{TV}}$. We apply the function which is parity of
$x\in[\ell]$ component wise. Resulting sample space becomes $\\{0,1\\}^{n}$,
$Q^{*}$ becomes $\mathrm{Bern}\left(1+{\epsilon\over\sqrt{n}}\right)^{n}$ and
$P$ becomes $\mathrm{Bern}\left({1\over 2}\right)^{n}$. It is a standard fact
that the ${d}_{\mathrm{TV}}$ of the later pair is at least $\Theta(\epsilon)$
(see eg. Canonne, Diakonikolas, Kane, and Stewart [2017]). ∎

Next we show that distingishing $k$ samples from $P$ and $Q$ is hard. Let
$P^{\otimes k},Q^{\otimes k}$ be their distributions. Noting that the
components of both the mixture and the uniform distribution are independent
and symmetric. We can upper bound them by $n$ copies of the first component’s
distribution, using Pinsker’s inequality and linearity of KL.

$\displaystyle\mbox{${d}_{\mathrm{TV}}^{2}$}(P^{\otimes k},Q^{\otimes
k})\lesssim\mbox{$d_{\mathrm{KL}}$}(Q^{\otimes k},P^{\otimes k})\leq
n\cdot\mbox{$d_{\mathrm{KL}}$}(Q_{1}^{\otimes k},P_{1}^{\otimes k})$ (3)

Computing $d^{2}_{\mathrm{H}}$ or $d_{\mathrm{KL}}$ are hard for the
multinomial unlike Daskalakis, Dikkala, and Kamath [2019] (cf. Lemma 17). So,
we use a reduction to simplify the calculations.

Recall $P_{1}^{\otimes k}$ is the distribution of the first $k$ samples when
$P$ is the uniform distribution over $[\ell]$ and $Q_{1}^{\otimes k}$ is the
same when we take a random distribution from the $2^{{\ell\over 2}}$ size
mixture.

We reduce $P_{1}$ to the distribution
$f(P)_{1}=\mathrm{Bern}({1\over\ell})^{l}$ and any distribution from the
mixture $Q^{*}_{1}=\langle q_{1},\dots,q_{\ell}\rangle$ to
$f(Q)^{*}_{1}=\mathrm{Bern}(q_{1})\times\dots\times\mathrm{Bern}(q_{\ell})$.
We claim that this reduction changes KL by a constant factor, for any
particular (randomly) chosen pair $P_{1},Q^{*}_{1}$ to start with.

######  Claim 4.10.

$\mbox{$d_{\mathrm{H}}$}(Q^{*}_{1},P_{1})\leq\mbox{$d_{\mathrm{KL}}$}(f(Q)^{*}_{1},f(P)_{1})$
and $\mbox{$d_{\mathrm{KL}}$}({Q_{1}}^{\otimes k},P_{1}^{\otimes k})\leq
6\mbox{$d_{\mathrm{KL}}$}({f(Q)_{1}}^{\otimes k},{f(P)_{1}}^{\otimes k})$.

###### Proof.

$\displaystyle\mbox{$d_{\mathrm{KL}}$}(Q_{1},P_{1})$
$\displaystyle=\sum_{j}Q_{ij}\log{Q_{1j}\over P_{1j}}$
$\displaystyle=\sum_{j:Q_{1j}>{1\over\ell}}{1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right)\log\left(1+{\epsilon\over\sqrt{n}}\right)+\sum_{j:Q_{1j}<{1\over\ell}}{1\over\ell}\left(1-{\epsilon\over\sqrt{n}}\right)\log\left(1-{\epsilon\over\sqrt{n}}\right)$
$\displaystyle\leq{1\over
2}\left(1+{\epsilon\over\sqrt{n}}\right){\epsilon\over\sqrt{n}}+{1\over
2}\left(1-{\epsilon\over\sqrt{n}}\right)\left(-{\epsilon\over\sqrt{n}}\right)$
$\displaystyle={\epsilon^{2}\over n}$

$\displaystyle\mbox{$d_{\mathrm{KL}}$}(f(Q)_{1},f(P)_{1})$
$\displaystyle={\ell\over
2}\mbox{$d_{\mathrm{KL}}$}\left(\mathrm{Bern}\left({1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right),\mathrm{Bern}\left({1\over\ell}\right)\right)\right)+$
$\displaystyle{\ell\over
2}\mbox{$d_{\mathrm{KL}}$}\left(\mathrm{Bern}\left({1\over\ell}\left(1-{\epsilon\over\sqrt{n}}\right)\right),\mathrm{Bern}\left({1\over\ell}\right)\right)$
$\displaystyle\mbox{$d_{\mathrm{KL}}$}\left(\mathrm{Bern}\left({1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right),\mathrm{Bern}\left({1\over\ell}\right)\right)\right)$
$\displaystyle={1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right)\log(1+{\epsilon\over\sqrt{n}})+\left(1-{1\over\ell}-{\epsilon\over\ell\sqrt{n}}\right)\log\left(1-{\epsilon\over(\ell-1)\sqrt{n}}\right)$
$\displaystyle\geq{1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right)\left({\epsilon\over\sqrt{n}}-{\epsilon^{2}\over
2n}\right)+\left(1-{1\over\ell}-{\epsilon\over\ell\sqrt{n}}\right)\left(-{\epsilon\over\sqrt{n}(\ell-1)}-{\epsilon^{2}\over
n(\ell-1)^{2}}\right)$ $\displaystyle\geq{\epsilon^{2}\over 3n\ell}$

Therefore,
$\mbox{$d_{\mathrm{KL}}$}(f(Q)_{1},f(P)_{1})\geq\mbox{$d_{\mathrm{KL}}$}(Q_{1},P_{1})/6$.
Using linearity of KL, we get $\mbox{$d_{\mathrm{H}}$}({Q_{1}^{*}}^{\otimes
k},P_{1}^{\otimes k})\leq 6\mbox{$d_{\mathrm{KL}}$}({f(Q)_{1}^{*}}^{\otimes
k},f(P)_{1}^{\otimes k})$. Since this holds for the reduction on any chosen
starting pair, we get that in general for the mixture,

$\mbox{$d_{\mathrm{KL}}$}({Q_{1}}^{\otimes k},P_{1}^{\otimes k})\leq
6\mbox{$d_{\mathrm{KL}}$}({f(Q)_{1}}^{\otimes k},{f(P)_{1}}^{\otimes k})$

∎

Henceforth we focus on upper bounding
$\mbox{$d_{\mathrm{KL}}$}(f(Q)_{1}^{\otimes k},f(P)_{1}^{\otimes k})$. The
reduction makes it a Boolean product distribution. Daskalakis, Dikkala, and
Kamath [2019] gave such upper bounds when every component is randomly mixed
and when the probabilities are close to $1/2$. Instead we need to mix every
pairs of components and need to make the probabilities close to $1/\ell$.

Let $p_{+}={1\over\ell}\left(1+{\epsilon\over\sqrt{n}}\right)$ and
$p_{-}={1\over\ell}\left(1-{\epsilon\over\sqrt{n}}\right)$.

###### Proof.

(of 2.5) We firstly note that it suffices to upper bound the joint
distribution of the count of 1’s in the samples $f(Q)_{1}^{\otimes k}$ and
$f(P)_{1}^{\otimes k}$ (Daskalakis, Dikkala, and Kamath [2019], Lemma 17). By
symmetry, we can focus on the mixture on the first two components $1,2$.
Recall these are actually the first two of the $\ell$ components of the
reduced distribution (where the reduction was performed on the first component
of the original distribution). Note that Daskalakis, Dikkala, and Kamath
[2019] could instead focus on a single component.

$\displaystyle\mbox{$d_{\mathrm{KL}}$}(Q_{1}^{\otimes k},P_{1}^{\otimes
k})\lesssim\mbox{$d_{\mathrm{KL}}$}(f(Q)_{1}^{\otimes k},f(P)_{1}^{\otimes
k})={\ell\over 2}\mbox{$d_{\mathrm{KL}}$}({f(Q)_{1}^{\otimes
k}}_{12},{f(P)_{1}^{\otimes k}}_{12})\leq{\ell\over
2}\mbox{$d_{\mathrm{\chi}^{2}}$}(R^{\otimes k}_{12},S^{\otimes k}_{12})$ (4)

We use $R=f(Q)_{1}$ and $S=f(P)_{1}$ for simplicity. Then, $R^{\otimes
k}_{12}$ and $S^{\otimes k}_{12}$ denote the joint distribution of the count
of 1s in $k$ samples at the first 2 components w.r.t the distributions
$\mathrm{Bern}\left({1\over\ell}\right)$ and the $2^{\ell/2}$-sized mixture
$\mathrm{Bern}\left({1\over\ell}\left(1\pm{\epsilon\over\sqrt{n}}\right)\right)$
(the former and the later are due to our reduction).

$\displaystyle 1+\mbox{$d_{\mathrm{\chi}^{2}}$}(R^{\otimes k}_{12},S^{\otimes
k}_{12})$ $\displaystyle=\sum_{i=0}^{k}\sum_{j=0}^{k}{\left[{1\over
2}{k\choose i}(p_{+})^{i}(1-p_{+})^{k-i}+{1\over 2}{k\choose
j}(p_{-})^{j}(1-p_{-})^{k-j}\right]^{2}\over{k\choose
i}\left({1\over\ell}\right)^{i}\left(1-{1\over\ell}\right)^{k-i}{k\choose
j}\left({1\over\ell}\right)^{j}\left(1-{1\over\ell}\right)^{k-j}}$
$\displaystyle={\ell^{2k}\over 4}\sum_{i=0}^{k}\sum_{j=0}^{k}{k\choose
i}{k\choose
j}[\left(p_{+}^{2}\right)^{i}\left({(1-p_{+})^{2}\over(\ell-1)}\right)^{k-i}\left(p_{-}^{2}\right)^{j}\left({(1-p_{-})^{2}\over(\ell-1)}\right)^{k-j}+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\left(p_{-}^{2}\right)^{i}\left({(1-p_{-})^{2}\over(\ell-1)}\right)^{k-i}\left(p_{+}^{2}\right)^{j}\left({(1-p_{+})^{2}\over(\ell-1)}\right)^{k-j}+$
$\displaystyle\qquad\qquad\qquad\qquad\qquad
2\left(p_{+}p_{-}\right)^{i}\left({(1-p_{+})(1-p_{)}\over(\ell-1)}\right)^{k-1}\left(p_{-}p_{+}\right)^{j}\left({(1-p_{)}(1-p_{+})\over(\ell-1)}\right)^{k-j}]$
$\displaystyle={\ell^{2k}\over
4}\left[2\left(p_{+}^{2}+{(1-p_{+})^{2}\over\ell-1}\right)^{k}\left(p_{-}^{2}+{(1-p_{-})^{2}\over\ell-1}\right)^{k}+2\left(p_{+}p_{-}+{(1-p_{+})(1-p_{-})\over(\ell-1)}\right)^{2k}\right]$

$\displaystyle p_{+}^{2}+{(1-p_{+})^{2}\over(\ell-1)}$
$\displaystyle={1\over\ell^{2}}\left(1+{\epsilon\over\sqrt{n}}\right)^{2}+{1\over(\ell-1)}\left(1-{1\over\ell-{\epsilon\over
l\sqrt{n}}}\right)^{2}$ $\displaystyle={1\over\ell}+{\epsilon^{2}\over
n\ell(\ell-1)}$ (upon simplification)

$\displaystyle p_{+}^{2}+{(1-p_{+})^{2}\over(\ell-1)}$
$\displaystyle={1\over\ell}+{\epsilon^{2}\over n\ell(\ell-1)}$ (upon
simplification)

$\displaystyle\left(p_{+}p_{-}+{(1-p_{+})(1-p_{)}\over(\ell-1)}\right)$
$\displaystyle={1\over\ell}-{\epsilon^{2}\over n\ell(\ell-1)}$ (upon
simplification)

Therefore,

$\displaystyle 1+\mbox{$d_{\mathrm{\chi}^{2}}$}(R^{\otimes k}_{12},S^{\otimes
k}_{12})$ $\displaystyle\leq{\ell^{2k}\over
2}\left[\left({1\over\ell}+{\epsilon^{2}\over
n\ell(\ell-1)}\right)^{2k}+\left({1\over\ell}-{\epsilon^{2}\over
n\ell(\ell-1)}\right)^{2k}\right]$ $\displaystyle\approx 1+{2k\choose
2}\left(\epsilon^{2}\over n(\ell-1)\right)^{2}+\dots$

We get that if $k=o(\sqrt{nl}\epsilon^{-2})$, then
$\mbox{$d_{\mathrm{\chi}^{2}}$}(R^{\otimes k}_{12},S^{\otimes
k}_{12})=o({1\over nl})$. Then we get from Equation 3 and Equation 4,
$\mbox{${d}_{\mathrm{TV}}$}(P^{\otimes k},Q^{\otimes k})=o(1)$, establishing
2.5. ∎

##  5 Tolerant Testing in $d_{\mathrm{H}}$ for High-Dimensional Distributions

In this section, we give an algorithm for tolerant testing of two high-
dimensional distributions w.r.t. the Hellinger distance. More specifically,
given samples from such a pair of unknown distributions $P$ and $Q$ our goal
would be to distinguish between the cases:
$\mbox{$d_{\mathrm{H}}$}(P,Q)\leq\epsilon/2$ versus
$\mbox{$d_{\mathrm{H}}$}(P,Q)>\epsilon$ with 2/3 probability, which can be
amplified to $1-\delta$ using the majority of $O(\log{1\over\delta})$
repetitions, for any $0<\delta,\epsilon<1$. This generalizes the work of
Bhattacharyya, Gayen, Meel, and Vinodchandran [2020], who gave such tolerant
testers w.r.t. ${d}_{\mathrm{TV}}$ using distance approximation.

We start with a result that additively estimates
$\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)$, when we have access to both the p.m.f.s
and also to independent samples from $P$.

######  Theorem 5.1.

Consider $P$ and $Q$ be two unknown distributions over $\Sigma^{n}$. Suppose
we have access to two circuits $\xi_{P}(x)$ and $\xi_{Q}(x)$ which on input
$x$, outputs $P(x)$ and $Q(x)$ respectively. Then we can output a number $e$
such that $|e-\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)|\leq\epsilon$ with 2/3
probability for any $0<\epsilon<1$, using $3\epsilon^{-2}$ independent samples
from $P$ and $3\epsilon^{-2}$ calls to each of $\xi_{P}(x)$ and $\xi_{Q}(x)$.

###### Proof.

$\displaystyle 1-\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)$
$\displaystyle=\sum_{x\in\Sigma^{n}}\sqrt{P(x)Q(x)}$
$\displaystyle=\sum_{x\in\Sigma^{n}}\sqrt{Q(x)\over P(x)}P(x)$
$\displaystyle=\mathrm{E}_{x\sim P}\left[\sqrt{Q(x)\over P(x)}\right]$ (since
$P(x)\neq 0$)

Let $f(x)=\sqrt{Q(x)\over P(x)}$. Therefore, it suffices to estimate
$\mathrm{E}_{x\sim P}\left[f(x)\right]$ additively. Note that,
$\mathrm{Var}_{x\sim P}[f(x)]\leq\mathrm{E}_{x\sim
P}\left[f^{2}(x)\right]\allowbreak=\sum_{x}Q(x)=1$. We define our estimator to
be $e$, the average of $(1-f(x))$ over $R$ samples from $P$. Then $e$
satisfies $\mathrm{E}[e]=\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)$ and
$\mathrm{Var}[e]\leq 1/R$. Chebyshev’s inequality gives us that for $R\geq
3\epsilon^{-2}$, $|e-\mbox{$d^{2}_{\mathrm{H}}$}(P,Q))|\leq\epsilon$ with at
least 2/3 probability. ∎

###  5.1 Application: Bayesian Networks

Bhattacharyya, Gayen, Meel, and Vinodchandran [2020] have given the following
Algorithm for learning an unknown Bayesian network on a known graph of
indegree at most $d$.

######  Theorem 5.2.

There is an algorithm that given a parameter $\epsilon>0$ and sample access to
an unknown Bayesian network distribution $P$ on a known directed acyclic graph
$G$ of in-degree at most $d$, returns a Bayesian network $\hat{P}$ on $G$ such
that $\mbox{$d_{\mathrm{H}}$}(P,\hat{P})\leq\epsilon$ with probability $\geq
9/10$. Letting $\Sigma$ denote the range of each variable $X_{i}$, the
algorithm takes $m=O(|\Sigma|^{d+1}n\log(|\Sigma|^{d+1}n)\epsilon^{-2})$
samples and runs in $O(mn)$ time.

We get the following result for tolerant resting of Bayesian networks in
Hellinger distance. See 2.10

###### Proof.

First we learn $P$ and $Q$ using 5.2 such that
$\mbox{$d_{\mathrm{H}}$}(P,\hat{P})\leq\epsilon/12$ and
$\mbox{$d_{\mathrm{H}}$}(Q,\hat{Q})\leq\epsilon/12$. This step costs
$m=O(|\Sigma|^{d+1}n\log(|\Sigma|^{d+1}n)\epsilon^{-2})$ samples, runs in
$O(mn)$ time, and succeeds with 4/5 probability. Note that $\hat{P}$ and
$\hat{Q}$, once learnt, can be sampled and evaluated correctly in $O(n)$ time.

Next we estimate $\mbox{$d^{2}_{\mathrm{H}}$}(\hat{P},\hat{Q})$ up to an
additive $\epsilon^{2}/9$ error using 5.1. This step costs $O(n\epsilon^{-4})$
time and no further samples and succeeds with 4/5 probability. Due to the
triangle inequality of $d_{\mathrm{H}}$, in the first case,
$\mbox{$d^{2}_{\mathrm{H}}$}(\hat{P},\hat{Q})\leq 20\epsilon^{2}/36$ and in
the second case
$\mbox{$d^{2}_{\mathrm{H}}$}(\hat{P},\hat{Q})>21\epsilon^{2}/36$, thus
separating the two cases. ∎

##  6 Non-tolerant Closeness Testers

###  6.1 $d_{\mathrm{H}}$-tester

A non-tolerant tester for 2-sample testing of product distributions was given
in Canonne, Diakonikolas, Kane, and Stewart [2017]. Their tester distinguishes
$P=Q$ from $\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq\epsilon$ with sample
complexity $O(\max\\{n^{3/4}/\epsilon,\allowbreak\sqrt{n}/\epsilon^{2}\\})$.
Using the relation,
$\mbox{${d}_{\mathrm{TV}}$}\geq\mbox{$d^{2}_{\mathrm{H}}$}$ from 2.2, we
immediately get a tester for distinguishing $P=Q$ from
$\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$, with sample complexity
$O(\max\\{n^{3/4}/\epsilon^{2},\sqrt{n}/\epsilon^{4}\\})$. Here, we show an
improved tester with $O(n^{3/4}/\epsilon^{2})$ sample complexity in Algorithm
2. We analyze its correctness and complexity below.

/* Approximately identify heavy and light partitions */

1 Take $m$ samples from $P$ and $Q$. Let $U^{\prime}\subseteq[n]\times[\ell]$
be the set of indices $(i,j)$, such that at least one sample from either $P$
or $Q$ has hit symbol $j\in\Sigma$ in the coordinate $i$;

2 Let $V^{\prime}=[n]\times[\ell]\setminus U^{\prime}$;

3

/* Poisson sampling */

4 For each $i\in[n]$, sample $M_{i}\sim\mathrm{Poi}(m)$ independently

5 For each $i\in[n]$, sample $M^{\prime}_{i}\sim\mathrm{Poi}(m)$ independently

6 Let $M=\max_{i}\\{M_{i}\\}$ and $M^{\prime}=\max_{i}\\{M^{\prime}_{i}\\}$

7 If $\max\\{M,M^{\prime}\\}\geq 2m$ output ‘no’

8 Take $M$ samples $X^{1},\dots,X^{M}$ from $P$

9 Take $M^{\prime}$ samples $Y^{1},\dots,Y^{M^{\prime}}$ from $Q$

10 For every $(i,j)$, let $W_{ij}$ be the number of occurrences of symbol
$j\in\Sigma$ in the $i$-th coordinate of the sample subset
$X^{1},\dots,X^{M_{i}}$

11 For every $(i,j)$, let $V_{ij}$ be the number of occurrences of symbol
$j\in\Sigma$ in the $i$-th coordinate of the sample
subset$Y^{1},\dots,Y^{M^{\prime}_{i}}$

12

13

/* Test the heavy partition */

14 $W_{heavy}=\sum_{(i,j)\in
U^{\prime}}{(W_{ij}-V_{ij})^{2}-(W_{ij}+V_{ij})\over(W_{ij}+V_{ij})}$

15 If $W_{heavy}>m\epsilon^{2}/120$ output ‘no’

16

17

/* Test the light partition */

18 $W_{light}=\sum_{(i,j)\in V^{\prime}}(W_{ij}-V_{ij})^{2}-(W_{ij}+V_{ij})$

19 If $W_{light}>m^{2}\epsilon^{4}/1000n\ell$ output ‘no’

20 Output ‘yes’

Algorithm 2 Given samples from two unknown distributions
$P=P_{1}\times\dots\times P_{n}$ and $Q=Q_{1}\times\dots\times Q_{n}$ over
$\Sigma^{n}$, decides $P=Q$ (‘yes’) versus
$\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$ (‘no’). Let $\ell=|\Sigma|$.

Let $P=\mbox{$\prod_{i=1}^{n}P_{i}$}$ and $Q=\mbox{$\prod_{i=1}^{n}Q_{i}$}$,
with $P_{i}=\langle p_{i1},\dots,p_{i\ell}\rangle$ and $Q_{i}=\langle
q_{i1},\dots,q_{i\ell}\rangle$ as probability vectors. We assume
$\min_{i,j}p_{ij}\geq\epsilon^{2}/50n\ell$ and
$\min_{i,j}q_{ij}\geq\epsilon^{2}/50n\ell$, without loss of generality using
the reduction of 3.4.

Analysis of Algorithm 2 can be divided into two cases: ‘heavy’ and ‘light’.
Let $V\subseteq[n]\times[\ell]$ be the ‘light’ set of indices $(i,j)$, such
that $\max\\{p_{ij},q_{ij}\\}<1/m$. The remaining indices in
$U=[n]\times[\ell]\setminus V$ are ‘heavy’. The following important lemma
shows that for each case, a certain sum must deviate from zero substantially,
for the ‘no’ class.

######  Lemma 6.1.

Suppose $\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$. Suppose
$\min_{i,j}p_{ij}\geq\epsilon^{2}/50n\ell$ and
$\min_{i,j}q_{ij}\geq\epsilon^{2}/50n\ell$. Then at least one of the following
two must hold:

  1. 1.

$\sum_{(i,j)\in V}(p_{ij}-q_{ij})^{2}\geq\epsilon^{4}/25n\ell$

  2. 2.

$\sum_{(i,j)\in U}{(p_{ij}-q_{ij})^{2}\over p_{ij}+q_{ij}}\geq\epsilon^{2}$.

###### Proof.

If $\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$, 3.2 gives us
$\sum_{i}\mbox{$d^{2}_{\mathrm{H}}$}(P_{i},Q_{i})\geq\epsilon^{2}$. We use the
following standard Fact to get
$\sum_{i=1}^{n}\sum_{j=1}^{\ell}{(p_{ij}-q_{ij})^{2}\over p_{ij}+q_{ij}}\geq
2\sum_{i}\mbox{$d^{2}_{\mathrm{H}}$}(P_{i},Q_{i})\geq 2\epsilon^{2}$.

######  Fact 6.2.

(see eg. Daskalakis, Kamath, and Wright [2018]) For two distributions
$P=\\{p_{1},\dots,p_{\ell}\\}$ and $Q=\\{q_{1},\dots,q_{\ell}\\}$,
$\sum_{j}{(p_{j}-q_{j})^{2}\over p_{j}+q_{j}}\geq
2\mbox{$d^{2}_{\mathrm{H}}$}(P,Q)$.

It follows that at least one of 1) $\sum_{(i,j)\in V}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}$ or 2) $\sum_{(i,j)\in U}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}$ is at least $\epsilon^{2}$.

In the first case,

$\displaystyle\sum_{(i,j)\in V}(p_{ij}-q_{ij})^{2}$
$\displaystyle=\sum_{(i,j)\in
V}(\sqrt{p_{ij}}-\sqrt{q_{ij}})^{2}(\sqrt{p_{ij}}+\sqrt{q_{ij}})^{2}$
$\displaystyle\geq(2\epsilon^{2}/25n\ell)\cdot\sum_{(i,j)\in
V}(\sqrt{p_{ij}}-\sqrt{q_{ij}})^{2}$ (as
$\min_{i,j}\min\\{p_{ij},q_{ij}\\}\geq\epsilon^{2}/50n\ell$)
$\displaystyle\geq(2\epsilon^{2}/25n\ell)\cdot\sum_{(i,j)\in
V}{(p_{ij}-q_{ij})^{2}\over(\sqrt{p_{ij}}+\sqrt{q_{ij}})^{2}}$
$\displaystyle\geq(\epsilon^{2}/25n\ell)\cdot\sum_{(i,j)\in
V}{(p_{ij}-q_{ij})^{2}\over p_{ij}+q_{ij}}$
$\displaystyle\geq\epsilon^{4}/25n\ell.$

∎

The following lemma shows $U^{\prime}$ ($V^{\prime}$), as obtained in Lines
1-2 of Algorithm 2, could be an acceptable proxy for $U$ ($V$).

######  Lemma 6.3.

Let $U^{\prime},V^{\prime}$ be as in Algorithm 2. Let
$m=\Omega(\sqrt{n\ell}/\epsilon^{2})$ for some sufficiently large constant.
Then with probability at least $0.63$ in each case, the following holds:

  1. 1.

$\sum_{(i,j)\in U}{(p_{ij}-q_{ij})^{2}\over p_{ij}+q_{ij}}\geq\epsilon^{2}$
implies $\sum_{(i,j)\in U\cap U^{\prime}}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}\geq\epsilon^{2}/20$

  2. 2.

$\sum_{(i,j)\in V}(p_{ij}-q_{ij})^{2}\geq\epsilon^{4}/25n\ell$ implies
$\sum_{(i,j)\in V^{\prime}}(p_{ij}-q_{ij})^{2}\geq\epsilon^{4}/500n\ell$

###### Proof.

Note that $(i,j)\in V^{\prime}$ with probability =
$(1-p_{ij})^{m}(1-q_{ij})^{m}$, and $(i,j)\in U^{\prime}$ with the remaining
probability.

(Proof of 1:) Let $U^{\prime\prime}=U\cap U^{\prime}$. Suppose there exists
$(i,j)\in U$ such that ${(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}\geq\epsilon^{2}/20$. Then this $(i,j)\in U^{\prime\prime}$ with
probability $1-(1-p_{ij})^{m}(1-q_{ij})^{m}\geq 1-(1-1/m)^{m}\geq 0.63$, in
which case the result follows. Otherwise, we consider sum of the independent
random variables, $S=\sum_{(i,j)}1_{(i,j)\in
U^{\prime\prime}}{20(p_{ij}-q_{ij})^{2}\over\epsilon^{2}(p_{ij}+q_{ij})}$,
each of which is in $[0,1]$. $\mathrm{E}[S]=\sum_{(i,j)\in
U}(1-(1-p_{ij})^{m}(1-q_{ij})^{m}){20(p_{ij}-q_{ij})^{2}\over\epsilon^{2}(p_{ij}+q_{ij})}\geq
12.6$. We apply Chernoff’s bound to get $S\geq 6.3$ with probability 0.63.

(Proof of 2:) Let $V^{\prime\prime}=V\cap V^{\prime}$. We consider sum of the
independent random variables, $S=\sum_{(i,j)}1_{(i,j)\in
V^{\prime\prime}}m^{2}(p_{ij}-q_{ij})^{2}$, each of which is in $[0,1]$.
$\mathrm{E}[S]=\sum_{(i,j)\in
V}(1-p_{ij})^{m}(1-q_{ij})^{m}m^{2}(p_{ij}-q_{ij})^{2}>(1-1/m)^{2m}\sum_{(i,j)\in
V}m^{2}(p_{ij}-q_{ij})^{2}\geq m^{2}\epsilon^{4}/250n\ell$, for $m\geq 4$. We
apply Chernoff’s bound to get $S\geq m^{2}\epsilon^{4}/500n\ell$ except for
probability at most $\exp(-m^{2}\epsilon^{4}/3000n\ell)$. ∎

Combining 6.1 and 6.3, we get for the ‘no’ case, one of the two conditions of
6.3 must hold. Algorithm 2 uses the two tests $W_{heavy}$ and $W_{light}$ to
check these two conditions separately. To analyze them, we use certain
important results from Canonne, Diakonikolas, Kane, and Stewart [2017],
assuming $W_{ij}\sim\mathrm{Poi}(p_{ij})$ and $V_{ij}\sim\mathrm{Poi}(q_{ij})$
for every $i,j$, which holds due to Poisson sampling. We assume the check of
Line 7 goes through except 1/50 probability, using the concentration of
Poisson distribution.

##### Analysis of $W_{heavy}$

######  Lemma 6.4 (Obtained from Claims 37 and 38 of Canonne, Diakonikolas,
Kane, and Stewart [2017]).

If $P=Q$ then $\mathrm{E}[W_{heavy}]=0$. If $\sum_{(i,j)\in U\cap
U^{\prime}}{(p_{ij}-q_{ij})^{2}\over p_{ij}+q_{ij}}\geq\epsilon^{2}/20$ then
$\mathrm{E}[W_{heavy}]\geq m\epsilon^{2}/60$. In both cases
$\mathrm{Var}[W_{heavy}]\leq 7n\ell+15\mathrm{E}[W_{heavy}]$

By the application of Chebyshev’s inequality we get the following.

######  Lemma 6.5.

Let $m=\Omega(\sqrt{n\ell}/\epsilon^{2})$ for a sufficiently large constant.
Then the following holds except for probability $\leq 1/25$ in each case,

  1. 1.

$P=Q$ implies $W_{heavy}\leq m\epsilon^{2}/120$

  2. 2.

$\sum_{(i,j)\in U\cap U^{\prime}}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}\geq\epsilon^{2}/20$ implies $W_{heavy}>m\epsilon^{2}/120$.

##### Analysis of $W_{light}$

######  Lemma 6.6 (Obtained from Proposition 6 of Chan, Diakonikolas, Valiant,
and Valiant [2014] and Claim 35 of Canonne, Diakonikolas, Kane, and Stewart
[2017]).

$\mathrm{E}[W_{light}]=m^{2}\sum_{(i,j)\in V^{\prime}}{(p_{ij}-q_{ij})^{2}}$
and $\mathrm{Var}[W_{light}]\leq 80m^{3}\sqrt{b}\sum_{(i,j)\in
V^{\prime}}{(p_{ij}-q_{ij})^{2}}+8m^{2}b$, where $b=\max\\{\sum_{(i,j)\in
V^{\prime}}p_{ij}^{2},\sum_{(i,j)\in V^{\prime}}q_{ij}^{2}\\}$. Furthermore,
$b\leq 50n\ell/m^{2}$ for a sufficiently large $m$, except for probability at
most $1/50$.

By the application of Chebyshev’s inequality we get the following.

######  Lemma 6.7.

Let $m=\Omega((n\ell)^{3/4}/\epsilon^{2})$ for a sufficiently large constant.
Then the following holds except for probability $\leq 1/50$ in each case,

  1. 1.

$P=Q$ implies $W_{light}\leq m^{2}\epsilon^{4}/1000n\ell$

  2. 2.

$\sum_{(i,j)\in V^{\prime}}(p_{ij}-q_{ij})^{2}\geq\epsilon^{4}/500n\ell$
implies $W_{light}>m^{2}\epsilon^{4}/1000n\ell$.

Together we get $O((n\ell)^{3/4}/\epsilon^{2})$ samples are enough to
distinguish $P=Q$ versus $\mbox{$d_{\mathrm{H}}$}(P,Q)\geq\epsilon$.

See 2.8

###  6.2 ${d}_{\mathrm{TV}}$-tester

A 2-sample tester for distinguishing $P=Q$ from
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq\epsilon$, for product distributions over
$\\{0,1\\}^{n}$, was given in Canonne, Diakonikolas, Kane, and Stewart [2017]
with sample complexity $O(\sqrt{n}/\epsilon^{2},\max\\{n^{3/4}/\epsilon\\})$.
In the following, we generalize this result for product distributions over
$\Sigma^{n}$ with sample complexity
$m=O(\max\\{\sqrt{n|\Sigma|}/\epsilon^{2},(n|\Sigma|)^{3/4}/\epsilon\\})$
which is optimal for $|\Sigma|=2$ [Canonne, Diakonikolas, Kane, and Stewart,
2017]. Let $\ell=|\Sigma|$. We assume $\min_{i,j}p_{ij}\geq\epsilon/50n\ell$
and $\min_{i,j}q_{ij}\geq\epsilon/50n\ell$ without loss of generality, using a
reduction similar to 3.4 [Canonne, Diakonikolas, Kane, and Stewart, 2017,
Daskalakis and Pan, 2017]. Let $V\subseteq[n]\times[\ell]$ be the set of
indices $(i,j)$, such that $\max\\{p_{ij},q_{ij}\\}<1/m$. Let
$U=[n]\times[\ell]\setminus V$.

######  Lemma 6.8.

Suppose $\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq\epsilon$. Suppose
$\min_{i,j}p_{ij}\geq\epsilon/50n\ell$ and
$\min_{i,j}q_{ij}\geq\epsilon/50n\ell$. Then at least one of the following two
must hold:

  1. 1.

$\sum_{(i,j)\in V}(p_{ij}-q_{ij})^{2}\geq\epsilon^{2}/n\ell$

  2. 2.

$\allowbreak\sum_{(i,j)\in U}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}\geq\epsilon^{2}/4$.

###### Proof.

We get $\sum_{(i,j)\in V}|p_{ij}-q_{ij}|+\sum_{(i,j)\in
U}|p_{ij}-q_{ij}|=2\sum_{i}\mbox{${d}_{\mathrm{TV}}$}(P_{i},Q_{i})\geq
2\mbox{${d}_{\mathrm{TV}}$}(P,Q)\geq 2\epsilon$, the second last inequality
from the following Fact.

######  Fact 6.9.

For two product distributions $P=\Pi_{i=1}^{n}P_{i}$ and
$Q=\Pi_{i=1}^{n}Q_{i}$,
$\mbox{${d}_{\mathrm{TV}}$}(P,Q)\leq\sum_{i}\mbox{${d}_{\mathrm{TV}}$}(P_{i},Q_{i})$.

Hence at least one of $\sum_{(i,j)\in V}|p_{ij}-q_{ij}|$ or $\sum_{(i,j)\in
U}|p_{ij}-q_{ij}|$ is at least $\epsilon$.

In the first case, we get

$\displaystyle\qquad\qquad\quad\sum_{(i,j)\in
V}(p_{ij}-q_{ij})^{2}\sum_{(i,j)\in V}1$ $\displaystyle\geq(\sum_{(i,j)\in
V}|p_{ij}-q_{ij}|)^{2}$ (Cauchy-Schwarz inequality)
$\displaystyle\sum_{(i,j)\in V}(p_{ij}-q_{ij})^{2}$
$\displaystyle\geq\epsilon^{2}/n\ell.$

In the second case, the proof is similar to that of the standard Facts
$\mbox{${d}_{\mathrm{TV}}$}\leq\mbox{$d_{\mathrm{H}}$}$ and 6.2 (see eg.
Daskalakis, Kamath, and Wright [2018] for both).

$\displaystyle\qquad\qquad\epsilon^{2}$ $\displaystyle\leq(\sum_{(i,j)\in
U}|p_{ij}-q_{ij}|)^{2}$ $\displaystyle=(\sum_{(i,j)\in
U}|\sqrt{p_{ij}}-\sqrt{q_{ij}}||\sqrt{p_{ij}}+\sqrt{q_{ij}}|)^{2}$
$\displaystyle\leq(\sum_{(i,j)\in
U}(\sqrt{p_{ij}}-\sqrt{q_{ij}})^{2})(\sum_{(i,j)\in
U}(\sqrt{p_{ij}}+\sqrt{q_{ij}})^{2})$ (Cauchy-Schwarz inequality)
$\displaystyle\leq(\sum_{(i,j)\in
U}(\sqrt{p_{ij}}-\sqrt{q_{ij}})^{2})(\sum_{(i,j)\in U}2(p_{ij}+q_{ij}))$
$\displaystyle\leq 4\sum_{(i,j)\in
U}{(p_{ij}-q_{ij})^{2}\over(\sqrt{p_{ij}}+\sqrt{q_{ij}})^{2}}$
$\displaystyle\leq 4\sum_{(i,j)\in U}{(p_{ij}-q_{ij})^{2}\over
p_{ij}+q_{ij}}.$

∎

We skip the rest of the details of the algorithm and its analysis since it
closely follows that of Section 6.1. We identify the partitions $U$ and $V$
approximately by checking which indices are hit in $m$ samples. For
$m=\Omega(\sqrt{n\ell}/\epsilon)$, this approximation is acceptable using a
result similar to 6.3. 6.4, 6.5 and 6.6 are as before up to the constants.
Only in 6.7, the threshold for the light part changes to
$m^{2}\epsilon^{2}/40n\ell$, and the sample complexity for the light part
changes to $m=\Theta((n\ell)^{3/4}/\epsilon)$. See 2.9

##### Acknowledgement

We thank Clément Canonne for his comments on an earlier version of this paper.
We also thank the anonymous reviewers of ALT 21 for improving the paper.

## References

  * Acharya et al. [2015] Jayadev Acharya, Constantinos Daskalakis, and Gautam Kamath.  Optimal testing for properties of distributions.  In _Advances in Neural Information Processing Systems 28: Annual Conference on Neural Information Processing Systems 2015, December 7-12, 2015, Montreal, Quebec, Canada_ , pages 3591–3599, 2015.  URL http://papers.nips.cc/paper/5839-optimal-testing-for-properties-of-distributions.
  * Batu et al. [2013] Tuğkan Batu, Lance Fortnow, Ronitt Rubinfeld, Warren D Smith, and Patrick White.  Testing closeness of discrete distributions.  _Journal of the ACM (JACM)_ , 60(1):4, 2013.
  * Bhattacharyya et al. [2020] Arnab Bhattacharyya, Sutanu Gayen, Kuldeep S. Meel, and N. V. Vinodchandran.  Efficient distance approximation for structured high-dimensional distributions via learning.  _CoRR_ , abs/2002.05378, 2020.  URL https://arxiv.org/abs/2002.05378.
  * Canonne [2020] Clément L. Canonne.  _A Survey on Distribution Testing: Your Data is Big. But is it Blue?_ Number 9 in Graduate Surveys. Theory of Computing Library, 2020.  doi: 10.4086/toc.gs.2020.009.  URL http://www.theoryofcomputing.org/library.html.
  * Canonne et al. [2017] Clément L. Canonne, Ilias Diakonikolas, Daniel M. Kane, and Alistair Stewart.  Testing bayesian networks.  In _Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017_ , pages 370–448, 2017\.  URL http://proceedings.mlr.press/v65/canonne17a.html.
  * Chan et al. [2014] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In _Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms_ , pages 1193–1203. SIAM, 2014.
  * Dasgupta [1997] Sanjoy Dasgupta.  The sample complexity of learning fixed-structure bayesian networks.  _Machine Learning_ , 29(2-3):165–180, 1997.
  * Daskalakis and Pan [2017] Constantinos Daskalakis and Qinxuan Pan.  Square hellinger subadditivity for bayesian networks and its applications to identity testing.  In _Proceedings of the 30th Conference on Learning Theory, COLT 2017, Amsterdam, The Netherlands, 7-10 July 2017_ , pages 697–703, 2017\.  URL http://proceedings.mlr.press/v65/daskalakis17a.html.
  * Daskalakis et al. [2018] Constantinos Daskalakis, Gautam Kamath, and John Wright.  Which distribution distances are sublinearly testable?  In _Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms_ , SODA ’18, pages 2747–2764, Philadelphia, PA, USA, 2018\. Society for Industrial and Applied Mathematics.  ISBN 978-1-6119-7503-1.  URL http://dl.acm.org/citation.cfm?id=3174304.3175479.
  * Daskalakis et al. [2019] Constantinos Daskalakis, Nishanth Dikkala, and Gautam Kamath.  Testing ising models.  _IEEE Trans. Inf. Theory_ , 65(11):6829–6852, 2019.  doi: 10.1109/TIT.2019.2932255.  URL https://doi.org/10.1109/TIT.2019.2932255.
  * Goldreich and Ron [2011] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  In _Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation_ , pages 68–75. Springer, 2011.
  * Jiao et al. [2018] Jiantao Jiao, Yanjun Han, and Tsachy Weissman.  Minimax estimation of the l${}_{\mbox{1}}$ distance.  _IEEE Trans. Inf. Theory_ , 64(10):6672–6706, 2018.  doi: 10.1109/TIT.2018.2846245.  URL https://doi.org/10.1109/TIT.2018.2846245.
  * Paninski [2008] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  _IEEE Transactions on Information Theory_ , 54(10):4750–4755, 2008.
  * Rubinfeld [2012] Ronitt Rubinfeld.  Taming big probability distributions.  _ACM Crossroads_ , 19(1):24–28, 2012.  doi: 10.1145/2331042.2331052.  URL https://doi.org/10.1145/2331042.2331052.
  * Valiant and Valiant [2010] Gregory Valiant and Paul Valiant.  A CLT and tight lower bounds for estimating entropy.  _Electronic Colloquium on Computational Complexity (ECCC)_ , 17:183, 2010.  URL http://eccc.hpi-web.de/report/2010/179.
  * Valiant and Valiant [2011] Gregory Valiant and Paul Valiant.  The power of linear estimators.  In _Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on_ , pages 403–412. IEEE, 2011.
  * Valiant and Valiant [2014] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  In _Proceedings of the 2014 IEEE 55th Annual Symposium on Foundations of Computer Science_ , FOCS ’14, pages 51–60, Washington, DC, USA, 2014. IEEE Computer Society.  ISBN 978-1-4799-6517-5.  doi: 10.1109/FOCS.2014.14.  URL http://dx.doi.org/10.1109/FOCS.2014.14.

##  Appendix A Proof of 3.6

See 3.6

###### Proof.

The test $T$ of Acharya, Daskalakis, and Kamath [2015] is given by
$T=\Sigma_{i=1}^{K}{(N_{i}-ms_{i})^{2}-N_{i}\over ms_{i}}$.

$\displaystyle\mathrm{E}[T]$
$\displaystyle=\mathrm{E}\left[\sum_{i}{(N_{i}-ms_{i})^{2}-N_{i}\over
ms_{i}}\right]$
$\displaystyle=\sum_{i}{\mathrm{E}[(N_{i}-ms_{i})^{2}-N_{i}]\over ms_{i}}$
$\displaystyle=\sum_{i}{\mathrm{E}[N_{i}^{2}]+m^{2}s_{i}^{2}-2ms_{i}\mathrm{E}[N_{i}]-\mathrm{E}[N_{i}]\over
ms_{i}}$ $\displaystyle=\sum_{i}{mr_{i}(1+mr_{i})+m^{2}s_{i}^{2}-2ms_{i}\cdot
mr_{i}-mr_{i}\over ms_{i}}$ (Since $N_{i}\sim\mathrm{Poi}(mr_{i})$)
$\displaystyle=m\sum_{i}{(r_{i}-s_{i})^{2}\over s_{i}}.$

$\displaystyle\mathrm{Var}[T]$
$\displaystyle=\mathrm{Var}\left[\sum_{i}{(N_{i}-ms_{i})^{2}-N_{i}\over
ms_{i}}\right]$
$\displaystyle=\sum_{i}\mathrm{Var}\left[{(N_{i}-ms_{i})^{2}-N_{i}\over
ms_{i}}\right]$ (Since $N_{i}$s are independent for different $i$s)
$\displaystyle=\sum_{i}{1\over
m^{2}s_{i}^{2}}\mathrm{Var}[N_{i}^{2}-(2ms_{i}+1)N_{i}]$
$\displaystyle=\sum_{i}{1\over
m^{2}s_{i}^{2}}[\mathrm{Var}[N_{i}^{2}]+(2ms_{i}+1)^{2}\mathrm{Var}[N_{i}]-2(2ms_{i}+1)\mathrm{Cov}(N_{i}^{2},N_{i})]$
$\displaystyle=\sum_{i}{1\over
m^{2}s_{i}^{2}}[(\mathrm{E}[N_{i}^{4}]-\mathrm{E}^{2}[N_{i}^{2}])+(2ms_{i}+1)^{2}(\mathrm{E}[N_{i}^{2}]-\mathrm{E}^{2}[N_{i}])$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad-2(2ms_{i}+1)(\mathrm{E}[N_{i}^{3}]-\mathrm{E}[N_{i}^{2}]\mathrm{E}[N_{i}])]$
$\displaystyle=\sum_{i}{1\over
m^{2}s_{i}^{2}}[\lambda(1+5\lambda+4\lambda^{2})+\lambda(2ms_{i}+1)^{2}-2(2ms_{i}+1)(\lambda(2\lambda+1))]$
(Since $N_{i}\sim\mathrm{Poi}(\lambda)$, where $\lambda=mr_{i}$)
$\displaystyle=\sum_{i}{1\over
m^{2}s_{i}^{2}}\lambda[\lambda+(2ms_{i}-2\lambda)^{2}]$
$\displaystyle=\sum_{i}{r_{i}^{2}\over
s_{i}^{2}}+\sum_{i}4mr_{i}{(r_{i}-s_{i})^{2}\over s_{i}^{2}}.$

We bound the above two summations separately.

$\displaystyle\sum_{i}{r_{i}^{2}\over s_{i}^{2}}$
$\displaystyle=\sum_{i}{(r_{i}-s_{i})^{2}+2s_{i}(r_{i}-s_{i})+s_{i}^{2}\over
s_{i}^{2}}$ $\displaystyle=\sum_{i}{(r_{i}-s_{i})^{2}\over
s_{i}^{2}}+2\sum_{i}{r_{i}-s_{i}\over s_{i}}+\sum_{i}1$ $\displaystyle\leq
2\left(\sum_{i}{(r_{i}-s_{i})^{2}\over s_{i}^{2}}+\sum_{i}1\right)$ (Using
$a^{2}+1\geq 2a$) $\displaystyle\leq
2\left({50K\over\epsilon^{2}}\sum_{i}{(r_{i}-s_{i})^{2}\over s_{i}}+K\right)$
(Using $s_{i}\geq\epsilon^{2}/50K$)
$\displaystyle=2({50K\over\epsilon^{2}}{\mathrm{E}[T]\over m}+K)$
$\displaystyle\leq\sqrt{K}\mathrm{E}[T]+2K.$ (Using $m\geq
c\sqrt{K}/\epsilon^{2}$ for c sufficiently large)
$\displaystyle\sum_{i}4mr_{i}{(r_{i}-s_{i})^{2}\over s_{i}^{2}}$
$\displaystyle\leq 4m\sqrt{\sum_{i}{r_{i}^{2}\over
s_{i}^{2}}}\sqrt{\sum_{i}{(r_{i}-s_{i})^{4}\over s_{i}^{2}}}$ (Using Cauchy-
Schwarz inequality) $\displaystyle\leq
4m\sqrt{\sqrt{K}\mathrm{E}[T]+2K}\sum_{i}{(r_{i}-s_{i})^{2}\over s_{i}}$
$\displaystyle\leq 4\mathrm{E}[T](K^{1/4}\sqrt{\mathrm{E}[T]}+\sqrt{2K}).$

Together we get

$\displaystyle\mathrm{Var}[T]$
$\displaystyle\leq\sqrt{K}\mathrm{E}[T]+2K+4\mathrm{E}[T](K^{1/4}\sqrt{\mathrm{E}[T]}+\sqrt{2K})$
$\displaystyle\leq 2K+7\sqrt{K}\mathrm{E}[T]+4K^{1/4}(\mathrm{E}[T])^{3/2}.$

∎