Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries
August 05, 2024
Abstract
We study property testing in the subcube conditional model introduced by Bhattacharyya and Chakraborty (2017). We obtain the first equivalence test for \(n\)-dimensional distributions that is quasi-linear in \(n\), improving the previously known \(\tilde{O}(n^2/\varepsilon^2)\) query complexity bound to \(\tilde{O}(n/\varepsilon^2)\). We extend this result to general finite alphabets with logarithmic cost in the alphabet size.
By exploiting the specific structure of the queries that we use (which are more restrictive than general subcube queries), we obtain a cubic improvement over the best known test for distributions over \(\{1,\ldots,N\}\) under the interval querying model of Canonne, Ron and Servedio (2015), attaining a query complexity of \(\tilde{O}((\log N)/\varepsilon^2)\), which for fixed \(\varepsilon\) almost matches the known lower bound of \(\Omega((\log N)/\log\log N)\). We also derive a product test for \(n\)-dimensional distributions with \(\tilde{O}(n / \varepsilon^2)\) queries, and provide an \(\Omega(\sqrt{n} / \varepsilon^2)\) lower bound for this property.
1 Introduction↩︎
Property testing seeks to efficiently distinguish between objects that have some property and objects that are \(\varepsilon\)-far from any object that has it, with respect to a predefined metric and a proximity parameter \(\varepsilon\). Property testing of functions, and in particular string testing, was initiated in [1], [2]. The term “efficiently” usually refers to a sublinear amount of resources for moderately-sized tasks, but for high-dimensional inputs practicality mandates to restrict this amount further to the poly-logarithmic scale.
The study of distribution testing was implicitly initiated in [3] (originally as [4], motivated by a problem in graph testing), and formally defined as the sampling model in [5], [6]. In this model, the algorithm gets access to a sequence of independent samples identically distributed from the input distribution, and then decides whether to accept or reject based on them. A major topic of investigation concerns testing that a distribution over \(\{1,\ldots,n\}\) is the uniform one. A long string of results, starting with the original [3] and culminating in [7] (for most values of \(\varepsilon\); for extreme cases, it has been completed by [8] and [9]), has reached the tight bound of \(\Theta(\sqrt{n}/\varepsilon^2)\).
A square-root lower bound on one of the most basic of properties is impractical in many real-world settings. For example, the square-root sample complexity of uniformity testing is impractical when the input ranges over \(100\)-bit binary strings, an example which is still smaller than real-world inputs. There are three approaches to overcome this problem: the first, on which we expand below, is moving to stronger query models. The second is narrowing the scope of the allowable inputs, such as product distributions and Bayesian networks [10]. The third is moving to a model where the metric is more lax (possibly coupled with an even weaker query model), such as Hellinger distance [11] and the Huge Object Model defined in [12] that is concerned with the earth-mover distance metric.
We focus here on the first (and most common) approach to the scaling problem, that of considering a model with stronger queries. In the distribution testing setting, this usually focuses on conditional sampling. Instead of drawing a sequence of independent unconditional samples, we allow the algorithm to choose a subset of the possible outcomes and draw a sample conditioned on belonging to it. The models within this paradigm differ in the subset conditions they allow.
The first investigation of such a model was the fully conditional model [13], [14]. In this model, the algorithm can choose any subset to condition on. This model is very powerful but not realistic. If we are able to restrict the input distribution to any subset, we probably already have access to an explicit description of the distribution and thus have no need to sample it.
Further studies consider restricted forms of the conditional model. For example, [14] considers two additional models: the pair model and the interval model. In the pair model, the algorithm can still draw unconditional samples, and additionally it can draw conditional samples from any subset of two elements. Uniformity testing in the pair model requires \(\tilde{\Theta}(1/\varepsilon^2)\) samples. In the interval model, we test distributions over \(\Omega = \{1,\ldots,N\}\) (for some \(N\)), and the algorithm can condition on interval sets, which are sets of the form \(\{ a \le x \le b \}\). The lower bound for uniformity testing in the interval model is \(\tilde{\Omega}(\log N)\). The best known upper bound is \(\tilde{O}((\log N)^3 / \varepsilon^2)\).
The subcube conditional model [15] is motivated by database analysis. In this model, we test distributions over the set \(\prod_{i=1}^n \Omega_i\), and the algorithm can query subcube subsets, which are sets of the form \(\prod_{i=1}^n A_i\) where \(A_i \subseteq \Omega_i\) for every \(1 \le i \le n\). While not being extremely restrictive, its queries correspond to selection by attribute values, which is common in practice. Some of the prior work refers to a weaker variant of this model, where each \(A_i\) is either trivial (\(A_i = \Omega_i\)) or a singleton (\(A_i=\{a_i\}\) for some \(a_i\in\Omega_i\)). In this paper we mainly deal with the strong model, where general \(A_i\subseteq\Omega_i\) are allowed. In the most investigated setting, the binary setting where \(\Omega_i=\{0,1\}\) for all \(i\), the two models are the same.
Uniformity testing [16], [17] can be done in the weak model using \(\tilde{O}(m^{21} \sqrt{n} / \varepsilon^2)\) queries where \(m = \max_i |\Omega_i|\), and requires at least \(\Omega(\sqrt{mn} / \varepsilon^2)\) queries [18]. Other properties studied under the subcube model include identity to some fixed distribution [15], [19] and having a probability density function supported on a low-dimensional subspace [20].
Two related properties are of particular interest in distribution testing, the identity property and the equivalence property. In the identity property, a reference distribution is given to the algorithm in advance, and the task is to check whether the input distribution is identical to it. The equivalence property (henceforth: ) has an input consisting of two distributions, both of which accessible through the testing model, and the task is to check whether they are equal to each other.
In the subcube conditional model, since the input distribution is defined over a set of tuples, another natural property is that of being a product distribution (henceforth: , also known as independence testing in [6], [8], [9]). A distribution over tuples is called a product if its entries are independently distributed.
Our main upper bound result is a test for that for the binary setting (\(\Omega_i=\{0,1\}\)) uses only \(\tilde{O}(n/\epsilon^2)\) subcube queries, which improves on the previously known result of \(\tilde{O}(n^2/\varepsilon^2)\) from [15]. Additionally our result uses only prefix queries from one distribution and marginal prefix queries from the other, which we define below and are rather restricted forms of subcube queries. One can think of prefix queries as the queries that can be made fast when the database is sorted according to a concatenation of its attributes in a pre-defined order (functioning as its primary key). Importantly, the use of restricted queries allows us to derive an improved test also for , and to generalize the test to general \(\Omega_1,\ldots,\Omega_n\) with a logarithmic cost in the alphabet size.
The restricted form of our queries also allows us to tighten the previously known upper bound on equivalence testing (and through it the special case of uniformity testing) in the interval conditional model, obtaining an upper bound of \(\tilde{O}(\log N / \varepsilon^2)\) interval queries, which matches the lower bound for every fixed \(\varepsilon\) up to poly-double-logarithmic factors in \(N\).
We complement our upper bound for with an \(\Omega(\sqrt{n}/\varepsilon^2)\) lower bound. The question of whether we can go below \(O(n)\) for testing our properties (even for the binary setting and a fixed \(\varepsilon\)) remains open.
2 Organization of the paper↩︎
In Section 3 we summarize our contributions. After some preliminaries in Section 4, we provide the core of our main proofs, followed by the more technical details. In Section 5 we provide the testing upper bound in the binary setting, and a short proof of the corollary about interval queries. In Section 6 we provide the testing lower bound.
Then we prove the theorems derived from this upper bound: in Section 7 we extend the test to the non-binary setting, and in Section 8 we derive a test for .
All upper bound proofs implicitly construct their algorithms. For reference, explicit representations of the binary setting algorithms for and are given in the appendix.
3 Our results↩︎
We improve on the previously known result of \(\tilde{O}(n^2/\varepsilon^2)\) queries for equivalence testing of two distributions over \(\{0,1\}^n\) [15]. Our methods can also supersede the \(\tilde{O}(n/\varepsilon)\) algorithm of [19] which tests identity with a distribution given in advance that belongs to a very restricted class of inputs (their parameter refers to KL-divergence, which indeed incurs a quadratic gap when converted to total-variation distance). We provide more details on the latter below (before Lemma 9).
theoremthZclosenessZlinearithmic Let \(\tau\), \(\mu\) be two distributions over \(\{0,1\}^n\), where \(\tau\) is accessible through the prefix oracle access and \(\mu\) is accessible through the marginal prefix oracle access. For every \(\varepsilon> 0\) we can distinguish between \(\tau = \mu\) and \(d_\mathrm{TV}(\tau,\mu) > \varepsilon\) using \(\tilde{O}(n / \varepsilon^2)\) queries.
The prefix queries in the statement above are a special case of subcube queries, but they can also be seen as interval queries, allowing us to prove the following corollary:
corollarycorZintervalZlinearZtilde Let \(\tau\), \(\mu\) be two distributions over \(\{1,\ldots,N\}\), both accessible through the interval oracle. Then we can distinguish between \(\tau = \mu\) and \(d_\mathrm{TV}(\tau, \mu) > \varepsilon\) using \(\tilde{O}((\log N) / \varepsilon^2)\) queries.
We show a lower bound for testing a distribution \(\mu\) over \(\{0,1\}^n\) for being a product. To the best of our knowledge, it is the first lower bound for product testing in the binary setting. Our construction is similar to the lower bound for uniformity testing of [10].
theoremthZlbndZindependence Every \(\varepsilon\)-test for must make at least \(\Omega\left(\sqrt{n} / \varepsilon^2\right)\) subcube queries.
We generalize our upper bound for equivalence testing to strings of size \(n\) over larger alphabets. Our result is incomparable with the previously known result of \(\tilde{O}(\frac{n^5}{\varepsilon^5} \log \log |\Omega|)\) [15]. Note that the cited result refers to strings over a single alphabet (that is, \(\Omega^n\)), whereas our result refers to strings over mixed alphabets (that is, \(\prod_{i=1}^n \Omega_i\)). Additionally, our result is more efficient when \(|\Omega|\) is not very large with respect to \(n\).
theoremthZclosenessZomegas Let \(\mu\) and \(\tau\) be two distributions over \(\prod_{i=1}^n \Omega_i\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. If \(\mu\) is accessible through the marginal prefix oracle and \(\tau\) is accessible through the prefix oracle, then we can distinguish between \(\tau = \mu\) and \(d_\mathrm{TV}(\tau, \mu) > \varepsilon\) using \(\tilde{O}(\sum_{i=1}^n \log_2 |\Omega_i| / \varepsilon^2)\) queries.
We apply the same generalization for product testing as well. In the binary setting, it also improves on the previously known result of \(\tilde{O}(n^2 / \varepsilon^2)\) [15].
theoremthZubndZproduct Let \(\mu\) be a distribution over \(\prod_{i=1}^n \Omega_i\). For every \(0 < \varepsilon< 1\), we can distinguish between the case where \(\mu\) is a product distribution and the case where it is \(\varepsilon\)-far from every product distribution at the cost of \(\tilde{O}(\sum_{i=1}^n \log |\Omega_i| / \varepsilon^2)\) subcube queries. Moreover, if \(|\Omega_i| = 2\) for every \(1 \le i \le n\), then all these queries are prefix queries.
4 Preliminaries↩︎
For brevity, for \(m\in\mathbb{N}\) we let \([m]\) denote the set \(\{1,\ldots,m\}\).
Definition 1 (Bernoulli distribution). Let \(0 \le p \le 1\). The Bernoulli distribution with parameter \(p\), denoted by \(\mathrm{Ber}(p)\), is the distribution over \(\{0,1\}\) whose probability to draw \(1\) is \(p\).
Definition 2 (Common statistical divergence measures). Let \(\mu\) and \(\tau\) be two distributions over a finite set \(\Omega\). We use two well known divergence measures, namely the total-variation distance \(d_\mathrm{TV}(\mu, \tau) = \frac{1}{2} \sum_{x \in \Omega} \left|{\mu(x) - \tau(x)}\right| = \max_{E \subseteq \Omega} \left|{\mu(E) - \tau(E)}\right|\) and the KL-divergence \(D_\mathrm{KL}(\mu, \tau) = \mathop{{\rm E}\/}_{x \sim \mu}\left[\log_2 \frac{\mu(x)}{\tau(x)} \right]\). Note that this notation is only well-defined where \(\Pr_\mu[B] > 0\).
Definition 3 (Conditional distribution). Let \(\mu\) be a distribution over \(\Omega\), and let \(B \subseteq \Omega\) be an event. The corresponding conditional distribution is denoted by \(\mu|^B\) and is defined by \(\mu|^B(x)=0\) for \(x\notin B\) and \(\mu|^B(x)=\mu(x)/\Pr_{\mu}[B]\) for \(x\in B\).
Definition 4 (Index-restricted distribution). Let \(\mu\) be a distribution over \(\prod_{i=1}^n\Omega_i\), and let \(I \subseteq [n]\) be a set of indices. We use \(\mu|_I\) to denote the distribution that draws \(x \sim \mu\), and returns the restricted string \(x|_I \in \prod_{i\in I}\Omega_i\).
Note that the correct way to parse the overloaded notation \(\mu|^B_I\) is “\((\mu|^B)|_I\)”, that is, we first apply the condition and then restrict the indices.
Here we define the query model for distributions over binary strings. The definitions for general alphabets appear in Section 7.
Definition 5 (Subcube oracle access). Let \(\mu\) be an unknown distribution over \(\{0,1\}^n\). The subcube oracle has a set \(I \subseteq [n]\) and a string \(w \in \{0,1\}^I\) as input, and its output distributes as \(\mu|^{x_I = w}\). If \(\Pr_\mu[x_I = w] = 0\), then the oracle indicates an error. Note that the answers of the oracle are fully independent of the answers that were given to previous queries.
We note that the “error behavior” in the above definition does not really affect our results, since all our upper bounds use only restrictions to guaranteed positive probability outcomes, while our lower bounds use distributions that have no zero-probability elements.
Definition 6 (Prefix oracle access). Let \(\mu\) be an unknown distribution over \(\{0,1\}^n\). The prefix oracle is a restricted case of the subcube oracle, where \(I = [k]\) for some \(0 \le k \le n - 1\).
Definition 7 (Marginal subcube oracle access). Let \(\mu\) be an unknown distribution over \(\{0,1\}^n\). The marginal subcube oracle has a set \(I \subseteq [n]\), an index \(i \in [n] \setminus I\) and a string \(w \in \{0,1\}^I\) as input, and its output is a single bit that distributes as \(\mu|_i^{x_I = w}\). If \(\Pr_\mu[x_I = w] = 0\), then the oracle indicates an error.
Definition 8 (Marginal prefix oracle access). Let \(\mu\) be an unknown distribution over \(\{0,1\}^n\). The marginal prefix oracle is a restricted case of the marginal subcube oracle, where \(I \!=\! [i-1]\).
We now define the interval querying model for which we derive a new bound.
Definition 9 (Interval oracle access). Let \(\mu\) be an unknown distribution over \([N]\). The interval oracle has two elements \(1\leq a\leq b\leq N\) as input, and its output distributes as \(\mu|^{\{a,\ldots,b\}}\).
We next define our properties for distributions over general alphabet strings, and what it means to test for a property.
Definition 10 (). A pair of distributions \(\mu\), \(\tau\) over \(\prod_{i=1}^n\Omega_i\) belongs to the equivalence property if \(\mu = \tau\). The distance of a given pair \((\mu,\tau)\) from is explicitly defined as \(d_\mathrm{TV}(\mu,\tau)\) instead of the natural \(\inf_\nu (d_\mathrm{TV}(\mu,\nu)+ d_\mathrm{TV}(\tau,\nu))\). The two quantities are easily seen to be identical using the triangle inequality.
Definition 11 (). A distribution \(\mu\) over \(\prod_{i=1}^n\Omega_i\) is called a product distribution if there exist distributions \(\mu_1,\ldots,\mu_n\) over \(\Omega_1,\ldots,\Omega_n\) respectively, for which \(\mu \sim \mu_1 \times \cdots \times \mu_n\). We denote by the set of all product distributions over \(\prod_{i=1}^n\Omega_i\).
Definition 12 (\(\varepsilon\)-test). For some property \(\mathcal{P}\) of distributions (which is a set of distributions) and \(\varepsilon> 0\), we say that an algorithm \(\mathcal{A}\) is an \(\varepsilon\)-test for \(\mathcal{P}\) if:
For every input distribution \(\mu \in \mathcal{P}\), \(\mathcal{A}\) accepts with probability at least \(\frac{2}{3}\).
For every input distribution \(\mu\) for which \(d_\mathrm{TV}(\mu,\nu) > \varepsilon\) for all \(\nu \in \mathcal{P}\), \(\mathcal{A}\) rejects with probability at least \(\frac{2}{3}\).
5 Linear sample-complexity algorithm for ↩︎
To construct our improvement on the algorithm of [15], we first define some templates for analyzing and comparing differences between distributions.
Definition 13 (Single-bit divergence). We call \(d : [0,1] \times [0,1] \to [0,\infty)\) a single-bit divergence if:
For every \(p,q \in [0,1]\), \(d(p,q) = 0\) if and only if \(p=q\) (Positivity).
For every \(p' \le p \le q \le q'\), \(d(p,q) \le d(p', q')\) and \(d(q,p) \le d(q', p')\) (Monotonicity).
Three useful single-bit divergences are \(\mathrm{TV}(p,q) = |p - q|\), \(\mathrm{KL}(p,q) = p \log_2 \frac{p}{q} + (1-p)\log_2 \frac{1-p}{1-q}\) and \(\chi^2(p,q) = \frac{(p-q)^2}{(p+q)(2 -(p + q))}\). Note that all three are derived from their probability-theoretic counterparts for \(\mathrm{Ber}(p)\) and \(\mathrm{Ber}(q)\). We have two motivations to prefer this symmetric form of \(\chi^2\): first, the symmetry matches the idea of two unknown distributions, which is not the case in standard \(\chi^2\)-tests, and second, it is bounded by \(1\), which makes the analysis more similar to total-variation distance than to KL-divergence. In this paper, we use the name “chi-square” (and the notation \(\chi^2\)) to indicate this symmetric form.
Definition 14 (Slice-wise divergence). Let \(d\) be a single-bit divergence. For every \(n\) and two distributions \(\tau\), \(\mu\) over \(\{0,1\}^n\), the slice-wise divergence of \(\tau\) and \(\mu\) with respect to \(d\) is: \[\Delta_d(\tau, \mu) = \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[d(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1))\right]\] (note that the \(d\)-divergence is fed the probabilities of the two single-bit distributions to draw \(1\)).
Recall the \(\tilde{O}(n^5 / \mathrm{poly}(\varepsilon))\) algorithm of [15], which is actually \(\tilde{O}(n^2 / \varepsilon^2)\) for the binary setting. As a motivation, the paper uses (and has a self-contained proof of) the following bound: \[d_\mathrm{TV}(\tau, \mu) \le \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[d_\mathrm{TV}(\tau|_i^{x_{[i-1]} = w_{[i-1]}}, \mu|_i^{x_{[i-1]} = w_{[i-1]}})\right] = \Delta_\mathrm{TV}(\tau, \mu)\] The algorithm then distinguishes between \(\Delta_\mathrm{TV}(\tau, \mu) = 0\) (which always holds if \(\tau = \mu\)) and \(\Delta_\mathrm{TV}(\tau, \mu) > \varepsilon\) (which always holds if \(d_\mathrm{TV}(\tau, \mu) > \varepsilon\)).
To improve their test, inside the slice-wise divergence expression we substitute the single-bit total-variation distance with the single-bit \(\chi^2\)-distance, and analyze the more convenient \(\Delta_{\chi^2}(\tau,\mu)\).
The following is immediate, and in fact holds for every slice-wise divergence:
Observation 1. Let \(\tau\), \(\mu\) be two distributions over \(\{0,1\}^n\). If \(\tau = \mu\) then \(\Delta_{\chi^2}(\tau, \mu) = 0\).
The following lemma, which we prove in Subsection 5.1, provides the conversion from the total variation distance to the slice-wise chi-square divergence.
Lemma 2. Let \(\tau\), \(\mu\) be two distributions over \(\{0,1\}^n\). If \(\tau \ne \mu\), then \(\Delta_{\chi^2}(\tau, \mu) \ge \frac{(d_\mathrm{TV}(\tau,\mu))^2}{24 \log ({2n}/d_\mathrm{TV}(\tau,\mu))}\).
The following lemma, which we prove in Subsection 5.2, states that we can distinguish between single bit distributions using linearly many samples with respect to the inverse of their \(\chi^2\)-divergence.
lemmalemmaZsingleZbitZchiZsquareZtest Let \(p,q \in [0,1]\) be two probabilities. Given unconditional sampling access to \(\mathrm{Ber}(p)\) and \(\mathrm{Ber}(q)\), we can distinguish, with probability \(\frac{2}{3}\), between the case where \(p=q\) and the case where \(\chi^2(p, q) > \varepsilon\), at the cost of \(O(1 / \varepsilon)\) samples from each of them.
We use a common variant of the Levin’s work balance method:
Lemma 3 ([21], optimization exercise 8.4 in [22]). Let \(X\) be a non-negative random variable that is bounded by \(1\). Assume that there exists some random variable \(Y\) such that for every \(y \in \mathrm{supp}(Y)\) and every \(\varepsilon' > 0\), we can distinguish between \(\mathop{{\rm E}\/}[X|Y=y] = 0\) and \(\mathop{{\rm E}\/}[X|Y=y] > \varepsilon'\) using some black-box algorithm whose resource cost is \(O(1/\varepsilon')\). Also, assume that we can draw independent unconditional samples from \(Y\) at resource cost \(O(1)\) per sample. Then we can distinguish between \(\mathop{{\rm E}\/}[X] = 0\) and \(\mathop{{\rm E}\/}[X] > \varepsilon\) at a total resource cost of \(O(\varepsilon^{-1} \log (1/\varepsilon))\).
Using the above we can efficiently detect a large slicewise \(\chi^2\) divergence between two distributions.
lemmalemmaZclosenessZlinearitmicZDeltaZtest Let \(\tau\), \(\mu\) be two distributions over \(\{0,1\}^n\). Then for every \(\rho > 0\), we can distinguish between \(\Delta_{\chi^2}(\tau, \mu) = 0\) and \(\Delta_{\chi^2}(\tau, \mu) > \rho\) using \(O(\frac{n}{\rho} \log \frac{n}{\rho})\) prefix queries.
Proof. We normalize the divergence: \[\begin{align} \frac{1}{n}\Delta_{\chi^2}(\tau,\mu) &=& \frac{1}{n}\sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\chi^2(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)) \right] \\ &=& \mathop{{\rm E}\/}_{\substack{w \sim \tau \\ i \sim [n]}} \left[\chi^2(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)) \right] \end{align}\]
Then we apply Levin’s method, Lemma 3, with the following input. \(Y\) is a random variable that receives a value \((i,w)\) where \(i\) is uniformly drawn from \([n]\) and \(w\) is drawn from \(\tau\) (independently of \(i\)). The parameter \(\varepsilon\) is set to \(\rho/n\), and the random variable \(X\) is defined as a function of \(Y=(i,w)\) (meaning that it is constant when conditioned on a specific value of \(Y\)) by \[X(i,w)=\chi^2\left(\mu|_i^{x_{[i-1]} = w_{[i-1]}}(1), \tau|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right)\] The distinction between the cases \(X(Y)=0\) and \(X(Y)>\varepsilon'\) is performed using \(O(1/\varepsilon')\) many queries (our resource cost) through the single-bit \(\chi^2\)-test of Lemma [lemma:single-bit-chi-square-test]. ◻
Our main theorem follows immediately from the above statements:
Proof. Apply Lemma [lemma:closeness-linearitmic-Delta-test] using \(\rho = \frac{\varepsilon^2}{24 \log (2n / \varepsilon)}\). Completeness follows from Observation 1 and soundness follows from Lemma 2. ◻
Proof. Without loss of generality, assume that \(N=2^\ell\) for some integer \(\ell\) (otherwise we just pad the two distributions with zero-probability elements). For every \(i \ge 0\), let \(\mathrm{bin}_i : \{0,\ldots,2^i - 1\} \to \{0,1\}^i\) and \(\mathrm{unbin}_i : \{0,1\}^i \to \{0,\ldots,2^i-1\}\) be the mappings between small integers and their representation as \(i\)-bit strings. That is, \(\mathrm{unbin}_i (x_1,\ldots,x_i)=\sum_{j=1}^i2^{i-j}x_i\) and \(\mathrm{bin}_i=(\mathrm{unbin}_i)^{-1}\).
To apply our equivalence algorithm on distributions over \([N]\), every \(t \in [N]\) is interpreted as an \(\ell\)-bit string (using the map \(t \to \mathrm{bin}_\ell(t-1)\)). Then every prefix query \(\tau|^{x|_{[i-1]} = w}\) (respectively \(\mu|^{x|_{[i-1]} = w}\)) is simulated using the interval query \(\tau|^{\{a,\ldots,b\}}\) (respectively \(\mu|^{\{a,\ldots,b\}}\)), where \(a = 2^{N-i} \mathrm{unbin}_{i-1}(w) + 1\) and \(b = 2^{N-i} (\mathrm{unbin}_{i-1}(w) + 1)\). Since the simulated algorithm uses \(\tilde{O}(\ell / \varepsilon^2)\) prefix queries, the simulation uses \(\tilde{O}((\log N) / \varepsilon^2)\) interval queries. ◻
5.1 Proof of Lemma 2↩︎
The proof works by comparing the TV-distance and the slice-wise chi-square divergence with the KL-divergence, which is equal to its slice-wise version as per the following lemmas.
Lemma 4 (Basic chain rule for \(D_\mathrm{KL}\), folklore). Let \(\mu\) and \(\tau\) be distributions over \(\Omega\). Then for every random variable \(X : \Omega\to R\), we have the equality \(D_\mathrm{KL}(\mu,\tau) = D_\mathrm{KL}(X(\mu),X(\tau)) + \mathop{{\rm E}\/}_{x \sim X(\tau)}\left[D_\mathrm{KL}\left(\mu|^{X = x}, \tau|^{X=x}\right)\right]\).
Lemma 5 (Chain rule for \(D_\mathrm{KL}\), repeated form). Let \(\mu\) and \(\tau\) be distributions over \(\{0,1\}^n\). Then \(D_\mathrm{KL}(\mu,\tau) = \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \mu}\left[ D_\mathrm{KL}(\mu|_i^{x_{[i-1]} = w_{[i-1]}}, \tau|_i^{x_{[i-1]} = w_{[i-1]}}) \right] = \Delta_\mathrm{KL}(\mu,\tau)\).
Proof. We obtain this result by repeatedly applying the basic chain rule using induction. ◻
We recall two folklore bounds for the KL-divergence of Bernoulli distributions.
Lemma 6 (Well known). For \(p,q \in [0,1]\), \(\mathrm{KL}(p, q) \le \frac{(p-q)^2}{q(1-q)}\). More formally, in \((0,1) \times (0,1)\), the ratio between these expressions is a non-negative continuous function that is bounded by \(1\).
Lemma 7 (Direct corollary). Let \(p,q \in [0,1]\). If \(p = aq\) for some real \(a\), then \[\mathrm{KL}(aq, q) \le \frac{(a-1)^2}{1-q} q\]
Based on these bounds, the following technical lemma provides some connection between the chi-square distance and the KL-divergence of Bernoulli distributions.
Lemma 8. Let \(p, q \in [0,1]\). Then \(\chi^2(p,q) \ge \frac{1}{12} \mathrm{KL}(p,q) / \log \max\{\frac{1}{q}, \frac{1}{1-q}\}\).
Proof. We actually prove that \(\chi^2(p,q) / \mathrm{KL}(p,q) \ge \frac{1}{12 \log \max\{\frac{1}{q}, \frac{1}{1-q}\}}\) for every \(p\in [0,1]\) and \(q \in (0,1)\). For the edge cases of \(q\) (which we do not use in our proofs anyway except when \(p=q\)), the bound remains correct by considering the limit of \(\mathrm{KL}(p,q) / \log \max\{\frac{1}{q}, \frac{1}{1-q}\}\).
Without loss of generality, \(q \le \frac{1}{2}\). We can assume so since \(\chi^2(p,q) = \chi^2(1-p, 1-q)\), \(\mathrm{KL}(p,q) = \mathrm{KL}(1 - p, 1 - q)\) and \(\max\{\log 1/q, \log 1/(1-q)\} = \max\{\log 1/(1-q), \log 1/(1-(1-q))\}\). Based on this assumption it is sufficient to show that \(\frac{\chi^2(p,q)}{\mathrm{KL}(p,q)} \ge \frac{1}{12 \log q^{-1}}\).
Let \(a = p/q\) (\(0 < a \le 1/q\)). If \(a \ge 2\): \[\begin{align} \chi^2(aq,q) &\ge& \frac{(a-1)^2}{2(a+1)}q \\ \mathrm{KL}(aq,q) &\le& p \log \frac{p}{q} \le a \log q^{-1} \cdot q \\ \frac{\chi^2(aq,q)}{\mathrm{KL}(aq,q)} &\ge& \frac{(a-1)^2}{2a(a+1) \log q^{-1}} \ge \frac{1}{12 \log q^{-1}} \end{align}\] If \(a \le 2\): \[\begin{align} \chi^2(aq,q) &\ge& \frac{(a-1)^2}{2(a+1)}q \\ \mathrm{KL}(aq,q) &\le& \frac{(a-1)^2}{1-q} q \\ \frac{\chi^2(aq,q)}{\mathrm{KL}(aq,q)} &\ge& \frac{1-q}{2(a+1)} \ge \frac{1}{12 \log q^{-1}} \end{align}\] Where the second equation follows from Lemma 7, and the very last inequality in the third equation uses the assumption that \(q\le\frac{1}{2}\). ◻
At this point we prove a version of Lemma 2 for a parameterized restricted case. We then reduce the general case to this lemma using an appropriate parameter. We note here that if we were to use the following parameterized lemma directly instead of Lemma 2, we would have obtained a direct generalization of the binary setting part of [19].
Lemma 9. Let \(0 < q < \frac{1}{2}\). Assume that for every \(1 \le i \le n\) and for every condition \(w \in \{0,1\}^{i-1}\), the prefix marginal \(\mu|_i^{x_{[i-1]} = w}\) is equivalent to \(\tau|_i^{x_{[i-1]} = w}\) or equivalent to \(\mathrm{Ber}(p_{i,w})\) for some \(q \le p_{i,w} \le 1 - q\) (or both). Then \(\Delta_{\chi^2}(\tau, \mu) \ge \frac{1}{6} (d_\mathrm{TV}(\tau,\mu))^2 / \log q^{-1}\).
Proof. By Pinsker’s inequality and Lemma 5 we obtain: \[2(d_\mathrm{TV}(\tau, \mu))^2 \le D_\mathrm{KL}(\tau, \mu) = \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\mathrm{KL}\left(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right)\right]\] By our assumption, for every \(1\leq i\leq n\), if \(D_\mathrm{KL}(\tau|_i^{x_{[i-1]} = w_{[i-1]}}, \mu|_i^{x_{[i-1]} = w_{[i-1]}}) \neq 0\) then the probability of \(\mu|_i^{x_{[i-1]} = w_{[i-1]}}\) to draw \(1\) is between \(q\) and \(1 - q\). By Lemma 8 we obtain: \[2(d_\mathrm{TV}(\tau, \mu))^2 \le \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\chi^2\left(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right) \cdot 12 \log q^{-1} \right]\] That is, \[\frac{(d_\mathrm{TV}(\tau, \mu))^2}{6\log q^{-1}} \le \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\chi^2\left(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right) \right] = \Delta_{\chi^2}(\tau, \mu) \qedhere\] ◻
We could bound the KL-divergence of single bits using the \(\chi^2\) distance only because we assumed that the marginal probabilities of \(\mu\) are not too close to \(0\) or \(1\) (unless they are equal to their counterparts in \(\tau\)). In the general case we cannot assume it, hence we need to instead consider a distribution \(\mu'\) which is close to \(\mu\) while satisfying this assumption.
We consider \(\mu\) as a “probability tree”, where the root represents the empty string, every edge represents an additional bit, and every leaf represents a complete sample. This tree (and hence the distribution \(\mu\)) is fully determined using probabilities of the form \(\Pr_{x \sim \mu}[x_i = 1 | x_{[i-1]} = w]\), where \(1 \le i \le n\) and \(w \in \{0,1\}^{i-1}\).
We construct another distribution \(\mu'\) based on such a tree pattern. For every \(1 \le i \le n\) and \(w \in \{0,1\}^{i-1}\), we set \(\Pr_{x \sim \mu'}[x_i = 1 | x_{[i-1]} = w]\) as follows: \[\begin{align} \min\left\{\frac{d_\mathrm{TV}(\tau, \mu)}{2n}, \Pr_{x \sim \tau}[x_i = 1 | x_{[i-1]} = w]\right\} &\mathrm{if}& \Pr_{x \sim \mu}[x_i = 1 | x_{[i-1]} = w] < \frac{d_\mathrm{TV}(\tau,\mu)}{2n} \\ 1 - \min\left\{\frac{d_\mathrm{TV}(\tau, \mu)}{2n}, \Pr_{x \sim \tau}[x_i = 0 | x_{[i-1]} = w]\right\} &\mathrm{if}& \Pr_{x \sim \mu}[x_i = 1 | x_{[i-1]} = w] > 1- \frac{d_\mathrm{TV}(\tau,\mu)}{2n} \\ \Pr_{x \sim \mu}[x_i = 1 | x_{[i-1]} = w] \phantom{\bigg\}} && \mathrm{otherwise} \end{align}\] Observe that for every \(1 \le i \le n\) and \(w \in \{0,1\}^{i-1}\), \(d_\mathrm{TV}\left(\mu|_i^{x_{[i-1]} = w}, \mu'|_i^{x_{[i-1]} = w}\right) \le \frac{d_\mathrm{TV}(\tau,\mu)}{2n}\). Hence, \(d_\mathrm{TV}(\mu,\mu') \le \Delta_\mathrm{TV}(\mu,\mu') \le \frac{1}{2}d_\mathrm{TV}(\tau,\mu)\). By the triangle inequality, \(d_\mathrm{TV}(\tau,\mu') \ge \frac{1}{2}d_\mathrm{TV}(\tau,\mu)\).
Since the assumptions of Lemma 9 hold for \(\mu'\) (with \(q = \frac{1}{2n}d_\mathrm{TV}(\tau,\mu)\)), we can now conclude the proof of Lemma 2: \[\begin{align} \Delta_{\chi^2}(\tau, \mu) &=&& \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\chi^2\left(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right)\right] \\ \text{[Monotonicity of \chi^2]} &\ge&& \sum_{i=1}^n \mathop{{\rm E}\/}_{w \sim \tau} \left[\chi^2\left(\tau|_i^{x_{[i-1]} = w_{[i-1]}}(1), \mu'|_i^{x_{[i-1]} = w_{[i-1]}}(1)\right)\right] \\ \text{[Lemma \ref{lemma:closeness-linearithmic-fd-soundness-if-nice} with \textstyle q = \frac{1}{2n}d_\mathrm{TV}(\tau,\mu)]} &\ge&& \left. {(d_\mathrm{TV}(\tau,\mu'))^2} \middle/ {6 \log \frac{2n}{d_\mathrm{TV}(\tau,\mu)}} \right. \\ \text{[\textstyled_\mathrm{TV}(\tau,\mu') \ge \frac{1}{2}d_\mathrm{TV}(\tau,\mu)]} &\ge&& \left. {(d_\mathrm{TV}(\tau,\mu))^2} \middle/ {24 \log \frac{2n}{d_\mathrm{TV}(\tau,\mu)}} \right. & \!\!\!\!\qed \end{align}\]
5.2 Proof of Lemma [lemma:single-bit-chi-square-test]↩︎
Here we prove the lemmas deferred from Section 5. We start with some helper lemmas.
Lemma 10. Let \(0 \le p \le q \le 1\) for which \(p + q \le 1\) and let \(X\) be the sum of \(N\) independent bits drawn from \(\mathrm{Ber}(p)\). Then, \[\Pr[X \ge \frac{1}{2}(p + q)N] \le e^{-\frac{1}{12} \chi^2(p, q)}\]
Proof. Let \(\delta = q - p\). If \(\delta \le 2p\) then by Chernoff’s bound: \[\begin{align} \Pr[X \ge \frac{1}{2}(p + q)N] &=& \Pr[X \ge (1 + \frac{\delta}{2p}) \mathop{{\rm E}\/}[X]] \\ &\le& e^{-\frac{\delta^2}{12p^2} pN} = e^{-\frac{\delta^2}{12p} N} \le e^{-\frac{(p-q)^2}{12(p + q)(2 - (p+q))} N} = e^{-\frac{1}{12}\chi^2(p,q) N} \end{align}\] If \(\delta > 2p\) then: \[\begin{align} \Pr[X \ge \frac{1}{2}(p + q)N] &=& \Pr[X \ge (1 + \frac{\delta}{2p}) \mathop{{\rm E}\/}[X]] \\ &\le& e^{-\frac{\delta}{6p} pN} = e^{-\frac{\delta}{6} N} \le e^{-\frac{(q-p)^2}{6(p+q)}} \le e^{-\frac{1}{12} \chi^2(p,q) N} \end{align}\] ◻
Lemma 11. Let \(0 \le p \le q \le 1\) for which \(p + q \le 1\) and let \(X\) be the sum of \(N\) independent bits drawn from \(\mathrm{Ber}(q)\). Then, \[\Pr[X \le \frac{1}{2}(p + q)N] \le e^{-\frac{1}{8} \chi^2(p, q)} \le e^{-\frac{1}{12} \chi^2(p, q)}\]
Proof. Let \(\delta = q - p \le q\). By Chernoff’s bound: \[\begin{align} \Pr[X \le \frac{1}{2}(p + q)N] &=& \Pr[X \le (1 - \frac{\delta}{2q}) \mathop{{\rm E}\/}[X]] \\ &\le& e^{-\frac{\delta^2}{8q^2} qN} = e^{-\frac{\delta^2}{8q} N} \le e^{-\frac{(p-q)^2}{8(p + q)(2 - (p+q))} N} = e^{-\frac{1}{8}\chi^2(p,q) N} \end{align}\] ◻
Lemma 12. Let \(p,q \in [0,1]\). Let \(X\) be the sum of \(N\) independent bits drawn from \(\mathrm{Ber}(p)\) and \(Y\) be the sum of \(N\) independent bits drawn from \(\mathrm{Ber}(q)\). Then, with probability at least \(\left(1 - e^{-\frac{1}{12}\chi^2(p,q)N}\right)^2\), the sign of \(X-Y\) matches the sign of \(p-q\).
Proof. Without loss of generality, \(p + q \le 1\) (otherwise use \(1-q\) and \(1-p\) instead of \(p\) and \(q\), noting that \(d(1-q,1-p) = d(p,q)\) and that the sign of \((1-q)-(1-p)\) matches the sign of \(p-q\)).
If \(p = q\) then the lemma is vacuously correct. If \(p < q\), then by Lemma 10, \[\begin{align} \Pr[X - Y < 0] = \Pr[X < Y] &\ge& \Pr[X < \frac{1}{2}(p + q)N] \Pr[Y > \frac{1}{2}(p + q)N] \\ &\ge& \left(1 - e^{\frac{1}{12} \chi^2(p,q) N} \right)^2 \end{align}\] The case where \(p > q\) is analogous, using Lemma 11. ◻
We recall and prove Lemma [lemma:single-bit-chi-square-test]:
Proof. We repeat the following procedure \(64\) times: let \(N = {\left\lceil{24 / \varepsilon}\right\rceil}\). Also, let \(X\) be the sum of \(N\) independent samples drawn from \(\mathrm{Ber}(p)\) and \(Y\) be the sum of \(N\) independent samples drawn from \(\mathrm{Ber}(q)\). To conclude a single trial we check whether \(A>B\) or \(A<B\) (or neither) holds.
Let \(A\) be the number of trials with \(X>Y\) and \(B\) be the number of trials with \(X<Y\). If \(|A|,|B| \le 40\) we accept (\(p=q\)), and otherwise we reject (\(\chi^2(p,q) > \varepsilon\)).
If \(p=q\), then by symmetry, \(\mathop{{\rm E}\/}[X < Y] = \mathop{{\rm E}\/}[X > Y] \le \frac{1}{2}\). That is, \(\mathop{{\rm E}\/}[A] = \mathop{{\rm E}\/}[B] \le 32\). By Chernoff’s bound, \(\Pr[A \ge 41] < e^{-2 \cdot 9^2 / 64} < \frac{1}{6}\) and \(\Pr[B \ge 41] < \frac{1}{6}\). Hence, the probability to accept is at least \(1 - \frac{2}{6} = \frac{2}{3}\).
If \(\chi^2(p,q) > \varepsilon\), then by Lemma 12, one of \(\Pr[X < Y]\) and \(\Pr[X > Y]\) is at least \((1 - e^{-\frac{1}{12} \chi^2(p,q)N})^2 \ge (1 - e^{-2})^2 > 0.74\). Without loss of generality, we assume that \(p < q\). In this case, \(\mathop{{\rm E}\/}[A] > 47.36\). By the Chernoff bound, the probability to reject is at least \(1-\Pr[A \le 40] \ge 1-e^{-2 \cdot 7.36^2/64} > \frac{2}{3}\). ◻
6 Lower bound for ↩︎
This section is devoted to the following lower bound:
Let \(\pi_n\) denote the uniform distribution over \(\{0,1\}^n\). We show that distinguishing between \(\pi_n\) (which is in particular a product distribution) and a distribution that is \(\varepsilon\)-far from every product distribution requires \(\tilde{\Omega}(\sqrt{n}/\varepsilon^2)\) many queries.
Before we present our construction, we cite the corresponding lower bound for uniformity of a product distribution [10]:
Lemma 13 ([10]). Let \(\mathcal{N}\) be the following distribution over inputs: draw \(b_1,\ldots,b_n \sim \{+1, -1\}\) uniformly and independently, and return the distribution \(\prod_{i=1}^n \mathrm{Ber}\left(\frac{1}{2} + b_i \frac{\varepsilon}{\sqrt{n}} \right)\). Then the drawn input is always \(\Omega(\varepsilon)\)-far from \(\pi_n\), and any unconditional sampling algorithm that distinguishes between inputs drawn from \(\mathcal{N}\) and \(\pi_n\) must take at least \(\Omega(\sqrt{n} / \varepsilon^2)\) many samples.
In our construction, instead of adding a random bias for each coordinate, we partition the coordinates into pairs, and in each pair introduce a random “anti-product bias” as follows.
For \(b \in \{0, +1, -1\}\), let \(\nu_b\) be the following distribution over \(\{0,1\}^2\): \[\begin{array}{lcrclcr} \nu_b(00) &=& \frac{1}{4} + b_i \frac{\varepsilon}{\sqrt{n}} & \nu_b(01) &=& \frac{1}{4} - b_i \frac{\varepsilon}{\sqrt{n}} \\ \nu_b(10) &=& \frac{1}{4} - b_i \frac{\varepsilon}{\sqrt{n}} & \nu_b(11) &=& \frac{1}{4} + b_i \frac{\varepsilon}{\sqrt{n}} \end{array}\] That is, \(\nu_0\) is the uniform distribution over two bits, and \(\nu_{+1}\), \(\nu_{-1}\) are non-product distributions over two bits.
Let \(\mathcal{Y}\) be the distribution over inputs that always returns the uniform distribution over \(\{0,1\}^n\), and let \(\mathcal{N}\) be the following distribution over “bad” inputs over \(\{0,1\}^n\): we partition \([n]\) into fixed pairs (for example, \((2i-1,2i)\) for every \(1 \le i \le {\left\lfloor{n/2}\right\rfloor}\)). For every pair we draw \(b_i \in \{+1, -1\}\) uniformly and independently. The distribution of the \(i\)th pair is \(\nu_{b_i}\). All pairs are independent of each other. We assume that \(n\) is even, since for an odd \(n\) we can just assume that the \(n\)th bit is distributed uniformly and independently of the rest.
The following lemma, whose proof appears in Subsection 6.1, states that \(\mathcal{N}\) always draws a distribution far from .
lemmalemmaZsqrtZNZfarZfromZproduct Every input distribution drawn from \(\mathcal{N}\) is \(\Omega(\varepsilon)\)-far from any product distribution.
We now prove the indistinguishability of \(\mathcal{N}\) from the uniform distribution, starting with the sampling model, to which we later show a reduction from the subcube conditional model.
Lemma 14. An unconditional sampling algorithm that distinguishes between the uniform distribution and inputs that are drawn from \(\mathcal{N}\) must make \(\Omega(\sqrt{n} / \varepsilon^2)\) many queries.
Proof. Without loss of generality, assume that \(n\) is even. Consider the following bijection over \(\{0,1\}^2\): \((x,y) \to (x \oplus y, y)\). For \(b \in \{+1, 0, -1\}\), Let \(\nu'_b\) be the distribution that draws \((x,y) \sim \nu_b\) and returns \((x \oplus y, y)\). Observe that \(\nu'_b\) is identical to the product distribution \(\mathrm{Ber}(\frac{1}{2} + \frac{2b\varepsilon}{\sqrt{n}}) \times \mathrm{Ber}(\frac{1}{2})\). Let \(f : \{0,1\}^n \to \{0,1\}^n\) be a bijection that applies the above mapping for every pair individually.
Let \(\mathcal{N}'\) be the distribution over inputs that draws \(\mu \sim \mathcal{N}\), and then returns the distribution that draws \(x \sim \mu\) and returns \(f(x)\). Note also that the distribution that drawn \(x \sim \pi_n\) and returns \(f(x)\) is identical to \(\pi_n\). Since \(f\) is a bijection, this means that the number of samples needed to distinguish between the uniform distribution and \(\mathcal{N}\) is exactly the same as the number of samples needed to distinguish between the uniform distribution and \(\mathcal{N}'\).
Observe that the form of a distribution resulting from \(\mathcal{N}'\) is \(\prod_{i=1}^{n/2} \left(\mathrm{Ber}\left(\frac{1}{2} + \frac{2b_i\varepsilon}{\sqrt{n}}\right) \times \mathrm{Ber}\left(\frac{1}{2}\right)\right)\). The restriction of \(\mathcal{N}'\) to odd indexes is identical to the construction of Lemma 13 (with parameters \(\sqrt{2}\varepsilon\) and \(n/2\)), which requires at least \(\Omega(\sqrt{n} / \varepsilon^2)\) many unconditional samples to distinguish between it and the uniform distribution. Hence, this is also a lower bound for the number of samples needed to distinguish between the uniform distribution and inputs drawn from \(\mathcal{N}\). ◻
Lemma 15. Let \(b \in \{0,+1,-1\}\). Then for every subcube restriction \(q \in \{0,1,*\}^2\), we can simulate a \(q\)-conditioned sample from \(\nu_b\) by drawing a single unconditional sample from \(\nu_b\), without having any knowledge about \(b\).
Proof. Let \(q \in \{0,+1,*\}^2\) and let \(b \in \{0,+1,-1\}\). We first draw an unconditional sample \(x \sim \nu_b\). There are three kinds of subcube restrictions:
Trivial: \(q \in \{00, 01, 10, 11\}\). To simulate such a query, we simply return \(q\), ignoring the unconditional sample we have.
Unconditional: \(q = **\). To simulate such a query, we simply return \(x\).
Single restriction: \(q \in \{0*, 1*, *0, *1\}\). We denote the parity of \(x\) by \(p = x|_1 \oplus x|_2\), and construct the output as the concatenation of the two bits \(\mathrm{out}_1\) and \(\mathrm{out}_2\), based on the following table: \[\begin{array}{rllll} q & 0* & 1* & *0 & *1 \\ \mathrm{out}_1 & 0 & 1 & p & 1\oplus p \\ \mathrm{out}_2 & p & 1\oplus p & 0 & 1 \\ \end{array}\]
The correctness of the output in the trivial case and the unconditional case is trivial. We prove the correctness of the single-restriction case only for \(q = 0*\), since the other cases are analogous. \[\Pr_{\nu_b}[00 | 0*] = \frac{\Pr_{\nu_b}[00]}{\Pr_{\nu_b}[0*]} = \frac{\frac{1}{4} + \frac{b_i \varepsilon}{\sqrt{n}}}{\frac{1}{4} + \frac{b_i \varepsilon}{\sqrt{n}} + \frac{1}{4} - \frac{b_i \varepsilon}{\sqrt{n}}} = \frac{1}{2} + 2 \frac{b_i \varepsilon}{\sqrt{n}} = \Pr_{\nu_b}[00 \vee 11] = \Pr_{x\sim \nu_b}[x|_1 \oplus x|_2 = 0] \qedhere\] ◻
At this point we can prove Theorem [th:lbnd-independence].
Proof of Theorem [th:lbnd-independence]. By Lemma [lemma:sqrt-N-far-from-product], \(\mathcal{N}\) draws an input distribution that is \(\Omega(\varepsilon)\)-far from any product distribution. Observe that since the structure of the pairs is known in advance and since they are independent, we can simulate every \(q\)-subcube-query algorithm using a \(q\)-unconditional-sample algorithm: for each query we draw a single sample and then use the simulation procedure of Lemma 15 for every pair in itself.
Since an unconditional test requires \(\Omega(\sqrt{n} / \varepsilon^2)\) queries to distinguish inputs drawn from \(\mathcal{N}\) from the uniform distribution by Lemma 14, and every subcube query to the uniform distribution or an input drawn from \(\mathcal{N}\) can be simulated using a single unconditional query, the lower bound holds for subcube algorithms as well. ◻
6.1 Technical proofs for the lower bound↩︎
Recall that we denote the uniform distribution over \(\{0,1\}^n\) by \(\pi_n\).
Before we prove Lemma [lemma:sqrt-N-far-from-product], we need the following technical lemmas.
Lemma 16. For a string \(y \in \{0,1\}^n\), let \(C_1(y)\) be the number of \(1\)s in \(y\). If \(n \ge 70\), then \(\Pr_{y\sim \pi_n}[C_1(y) > \frac{1}{2}n + \frac{1}{4}\sqrt{n}] \ge \frac{1}{4}\).
Proof. We use the well-known bound \(\binom{n}{{\left\lfloor{n/2}\right\rfloor}} \le 2^n \cdot \sqrt{\frac{2}{\pi n}}\) (for all \(n \ge 1\)) to obtain for \(n\ge 70\):
\[\begin{align} \Pr_{y\sim \pi_n}\left[\left|{C_1(y) - \frac{1}{2}n}\right| \le \frac{1}{4}\sqrt{n}\right] &=& \sum_{k = {\left\lceil{\frac{1}{2}n - \frac{1}{4} \sqrt{n}}\right\rceil}}^{{\left\lfloor{\frac{1}{2}n + \frac{1}{4} \sqrt{n}}\right\rfloor}} \Pr_{y\sim \pi_n}\left[C_1(y) = k\right] \\ \text{[Since \textstyle{\binom{n}{k}\le \binom{n}{{\left\lfloor{n/2}\right\rfloor}}}]} &\le& \left(2 \cdot \frac{1}{4}\sqrt{n} + 1\right) 2^{-n} \binom{n}{{\left\lfloor{n/2}\right\rfloor}} \\ &\le& \left(\frac{1}{2}\sqrt{n} + 1\right) \frac{\sqrt{2}}{\sqrt{\pi n}} \le \frac{1}{2} \end{align}\]
By symmetry reasons, if \(n\ge 70\) then: \[\begin{align} \Pr_{y\sim \pi_n}\left[C_1(y) > \frac{1}{2}n + \frac{1}{4}\sqrt{n}\right] &=& \frac{1}{2}\Pr_{y\sim \pi_n}\left[\left|{C_1(y) - \frac{1}{2}n}\right| > \frac{1}{4}\sqrt{n}\right] \\ &=& \frac{1}{2}\left(1 - \Pr_{y\sim \pi_n}\left[\left|{C_1(y) - \frac{1}{2}n}\right| \le \frac{1}{4}\sqrt{n}\right]\right) \ge \frac{1}{4} \end{align}\] ◻
Lemma 17. Let \(0 < \delta < \frac{1}{4 \sqrt{n}}\) and \(\tau\) be a product distribution over \(\{0,1\}^n\). For sufficiently large \(n\), if \(\left|{\Pr_\tau[x_i = 1] - \frac{1}{2}}\right| > \delta\) for every \(1 \le i \le n\), then the distance of \(\tau\) from the uniform distribution over \(\{0,1\}^n\) is at least \(\frac{1}{16} \delta \sqrt{n}\).
Proof. Without loss of generality, we can assume that \(\Pr_\tau[x_i = 1] \ge \frac{1}{2}\) for every \(1 \le i \le n\). Otherwise, we can negate the “wrong” bits while preserving the distance from the uniform distribution. Based on this assumption, we have a product distribution whose probability to draw \(1\) at any individual index is at least \(\frac{1 + \delta}{2}\).
Let \(\tau'\) be the product distribution whose probability to draw \(1\) at any index is exactly \(\frac{1+\delta}{2}\). Observe that the distance of \(\tau'\) from the uniform distribution is a lower bound of the distance of \(\tau\) from the uniform distribution.
Let \(y \in \{0,1\}^n\) be a string, and let \(C_1(y)\) (respectively \(C_0(y)\)) be the number of \(1\)s (respectively \(0\)s) in \(y\). If \(C_1(y) \ge \frac{1}{2}n + \frac{1}{4}\sqrt{n}\), then: \[\begin{align} \frac{\Pr_{\tau'}[y]}{\Pr_{\pi_n}[y]} &=& (1 + \delta)^{C_1(y)} \cdot (1 - \delta)^{n - C_1(y)} \\ &=& (1 + \delta)^{C_1(y) - C_0(y)} \cdot ((1 + \delta)(1 - \delta))^{C_0(y)} \\ &\ge& (1 + \delta)^{\sqrt{n} / 2} \cdot ((1 + \delta)(1 - \delta))^{\frac{1}{2}n - \frac{1}{4}\sqrt{n}} \\ &=& (1 + \delta)^{\sqrt{n} / 2} \cdot (1 - \delta^2)^{\frac{1}{2}n - \frac{1}{4}\sqrt{n}} \\ &\ge& (1 + \delta)^{\sqrt{n} / 2} \cdot (1 - \delta^2)^{\frac{1}{2}n} \\ \text{[(1+a)^b \ge 1+ab for b \ge 1, |a|<1]}&\ge& \left(1 + \frac{1}{2}\delta\sqrt{n}\right) \cdot \left(1 - \frac{1}{2}\delta^2 n\right) \\ \text{[\textstyle \delta < \frac{1}{4\sqrt{n}}]} &\ge& 1 + \frac{1}{4} \delta\sqrt{n} \end{align}\]
In particular, \[\frac{\Pr_{y \sim \tau'}\left[C_1(y) > \frac{1}{2}n + \frac{1}{4}\sqrt{n}\right]}{\Pr_{y \sim \pi_n}\left[C_1(y) > \frac{1}{2}n + \frac{1}{4}\sqrt{n}\right]} \ge 1+\frac{1}{4}\delta\sqrt{n}\]
Since \(\Pr_{y \sim \pi_n}\left[C_1(y) > \frac{1}{2}n + \frac{1}{4}\sqrt{n}\right] \ge \frac{1}{4}\) by Lemma 16, we obtain that \(d_\mathrm{TV}(\tau', \pi_n) \ge \frac{1}{4}\delta\sqrt{n} \cdot \frac{1}{4} = \frac{1}{16}\delta\sqrt{n}\). ◻
We recall and prove Lemma [lemma:sqrt-N-far-from-product]:
Proof. Without loss of generality, we assume that \(n\) is even. Let \(b_1,\ldots,b_{n/2} \in \{+1, -1\}\) be the parameters of the construction, that is, the drawn input is \(\mu = \prod_{i=1}^{n/2} \nu_{b_i}\). Recall that for \(b \in \{+1, -1\}\), \(\Pr_{\nu_b}[x_1 = 1] = \Pr_{\nu_b}[x_2 = 1] = \frac{1}{2}\) and \(\Pr_{\nu_b}[x_1 \oplus x_2 = 1] = \frac{1}{2} - \frac{2b \varepsilon}{\sqrt{n}}\). We assume that \(n\) is sufficiently large so that \({\left\lfloor{n/6}\right\rfloor}\) satisfies the constraints of Lemma 17.
For a given product distribution \(\tau\), for every \(1 \le i \le n/2\), let: \[\begin{align} \delta_{i,0} &=& \Pr_\tau[x_{2i} = 1] - \frac{1}{2} \\ \delta_{i,1} &=& \Pr_\tau[x_{2i-1} = 1] - \frac{1}{2} \\ \delta_{i,2} &=& \Pr_\tau[x_{2i} \oplus x_{2i-1} = 1] - \frac{1}{2} \end{align}\]
Let \(I_0\) be the set of indexes for which \(\left|{\delta_{i,0}}\right| > \frac{\varepsilon}{10\sqrt{n}}\). Let \(I_1\) be defined analogously for \(\delta_{i,1}\), and let \(I_2 = [n/2] \setminus (I_0 \cup I_1)\) be the set of all other indexes. Since \(|I_0| + |I_1| + |I_2| = n/2\), at least one of them contains at least \(\frac{1}{6}n\) elements.
6.1.0.1 Case I. \(|I_0| \ge \frac{1}{6}n\)
Let \(I = \{ 2i : i \in I_0\}\). Observe that \(\mu|_I\) is uniform over \(\{0,1\}^{n/2}\), since \(\mu\) is the product of \(n/2\) independent distributions over pairs whose marginals are \(\frac{1}{2}\), and every pair contributes exactly one index. According to Lemma 17, \[d_\mathrm{TV}(\tau,\mu) \ge d_\mathrm{TV}(\tau|_I, \mu|_I) \ge \frac{1}{16} \cdot \frac{\varepsilon}{10 \sqrt{n}} \cdot \sqrt{\frac{1}{6}n} = \frac{1}{160\sqrt{6}}\varepsilon> \frac{1}{400}\varepsilon\]
6.1.0.2 Case II. \(|I_1| \ge \frac{1}{6}n\)
Completely analogous to Case I. Again \(d_\mathrm{TV}(\tau,\mu)>\frac{1}{400}\varepsilon\).
6.1.0.3 Case III. \(|I_2| \ge \frac{1}{6}n\)
For every \(i \in I_2\), \(|\delta_{i,0}|, |\delta_{i,1}| \le \frac{\varepsilon}{10\sqrt{n}}\). Hence, \[\begin{align} |\delta_{i,2}| = \left|{\Pr_\tau[x_{2i-1} \oplus x_{2i} = 1] - \frac{1}{2}}\right| &=& \left|{\left(\frac{1}{2} - \delta_{i,0}\right)\left(\frac{1}{2} + \delta_{i,1}\right) + \left(\frac{1}{2} + \delta_{i,0}\right)\left(\frac{1}{2} - \delta_{i,1}\right) - \frac{1}{2}}\right| \\ &=& 2|\delta_{i,0}| |\delta_{i,1}| \le \frac{\varepsilon^2}{50n} \end{align}\]
Let \(I = \{ 2i : i \in I_2 \} \cup \{ 2i - 1 : i \in I_2 \}\) Let \(f : \{0,1\}^I \to \{0,1\}^{|I_2|}\) be the function that maps every pair in \(I_2\) to its parity bit. In other words, for every \(i \in I_2\), the bits \(x_{2i-1}, x_{2i}\) are mapped to a single bit \(x_{2i-1} \oplus x_{2i}\). Let \(\mu'\) (respectively \(\tau'\)) be the distribution over \(\{0,1\}^{|I_2|}\) that draws a sample \(x \sim \mu\) (respectively \(x \sim \tau\)) and returns \(f(x)\). Observe that both \(\mu'\) and \(\tau'\) are product distributions over \(\{0,1\}^{|I_2|}\), since the pairs are independent and every pair is mapped into a single bit.
Note that \(d_\mathrm{TV}(\tau', \pi_{|I_2|}) \le \Delta_\mathrm{TV}(\tau', \pi_{|I_2|}) = \sum_{i=1}^{|I_2|} d_\mathrm{TV}\left(\tau'|_i, \mathrm{Ber}(1/2)\right) \le |I_2| \cdot \frac{\varepsilon^2}{50n} \le \frac{1}{50}\varepsilon^2\).
In \(\mu'\), by definition of the \(\nu_b\)s, all marginals have the form \(\frac{1}{2} \pm \frac{\varepsilon}{\sqrt{n}}\), hence by Lemma 17, \[d_\mathrm{TV}(\mu', \pi_{|I_2|}) \ge \frac{1}{16} \cdot \frac{\varepsilon}{\sqrt{n}} \cdot \sqrt{\frac{1}{6}n} = \frac{\varepsilon}{16\sqrt{6}} \ge \frac{1}{40}\varepsilon\]
By a data processing inequality and the triangle inequality, \[d_\mathrm{TV}(\mu, \tau) \ge d_\mathrm{TV}(\mu', \tau') \ge d_\mathrm{TV}(\mu', \pi_{|I_2|}) - d_\mathrm{TV}(\tau', \pi_{|I_2|}) \ge \frac{1}{40}\varepsilon- \frac{1}{50}\varepsilon^2 > \frac{1}{400}\varepsilon\qedhere\] ◻
7 Extending the test to general alphabets↩︎
We extend the definitions of the prefix oracle to non-binary settings.
Definition 15 (Subcube oracle access in non-binary strings). Let \(\mu\) be an unknown distribution over \(\prod_{i=1}^n \Omega_n\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. The subcube oracle has as input a tuple \((A_1,\ldots,A_n)\) where \(A_i \subseteq \Omega_i\) for every \(1 \le i \le n\). The output distributes as \(\mu|^{\prod_{i=1}^n A_i}\). For technical reasons, if \(\Pr_\mu[\prod_{i=1}^n A_i] = 0\), then the oracle indicates an error. Note that the answers of the oracle are fully independent of the answers that were given to previous queries.
In the corresponding definition for a prefix oracle, we still demand that until the “break-off index” \(i\) all conditions force single outcomes from the sets \(\Omega_j\), while after the break-off index there are no restrictions at all. However, at index \(i\) we allow conditions to any subset of \(\Omega_i\) to take place. There is no such distinction in the binary case, where \(|\Omega_i|=2\) and hence all non-trivial conditions are to a single outcome.
Definition 16 (Prefix oracle access in non-binary settings). Let \(\mu\) be an unknown distribution over \(\prod_{i=1}^n \Omega_n\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. The input of the prefix oracle consists of an index \(1 \le i \le n\), which we refer to as the index of the prefix, elements \(a_j \in \Omega_j\) for every \(1 \le j \le i-1\), and a condition \(A \subseteq \Omega_i\). The output of the oracle distributes like \(\mu|^{\{x : x_i \in A \wedge x_1=a_1,\ldots, x_{i-1} = a_{i-1}\}}\).
Definition 17 (Marginal subcube oracle access in non-binary settings). Let \(\mu\) be an unknown distribution over \(\prod_{i=1}^n \Omega_n\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. The marginal subcube oracle has as input an index \(i\) and a tuple \((A_1,\ldots,A_n)\) where \(A_j \subseteq \Omega_j\) for every \(1 \le j \le n\). The output distributes as \(\mu|_i^{\prod_{j=1}^n A_j}\). For technical reasons, if \(\Pr_\mu[\prod_{i=1}^n A_i] = 0\), then the oracle indicates an error.
Definition 18 (Marginal prefix oracle access in non-binary settings). Let \(\mu\) be an unknown distribution over \(\prod_{i=1}^n \Omega_n\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. The input of the marginal prefix oracle consists of an index \(1 \le i \le n\), which we refer to as the index of the prefix, elements \(a_j \in \Omega_j\) for every \(1 \le j \le i-1\), and a condition \(A \subseteq \Omega_i\). The output of the oracle distributes like \(\mu|_i^{\{x : x_i \in A \wedge x_1=a_1,\ldots,x_{i-1}=a_{i-1}\}}\).
Based on these definitions, we state Theorem [th:closeness-omegas]:
Before we prove Theorem [th:closeness-omegas], we need the following.
Lemma 18 (Binary form of a composite distribution). Let \(\mu\) be a distribution over \(\prod_{i=1}^n \Omega_i\), where \(\Omega_1,\ldots,\Omega_n\) are non-empty finite sets. There exists a distribution \(\mu^*\) over \(\{0,1\}^{\sum_{i=1}^n {\left\lceil{\log_2 |\Omega_i|}\right\rceil}}\) that is equivalent to \(\mu\) up to relabeling, for which every subcube (respectively prefix) query to \(\mu^*\) can be simulated using a single subcube (respectively prefix) query to \(\mu\), and every marginal subcube (respectively prefix) query to \(\mu^*\) can be simulated using a single marginal subcube (respectively prefix) query to \(\mu\).
Proof. For every \(1 \le i \le n\), let \(f_i : \Omega_i \to \{0,1\}^{{\left\lceil{\log_2 |\Omega_i|}\right\rceil}}\) be an arbitrary injective function from \(\Omega_i\) to \(\{0,1\}^{{\left\lceil{\log_2 |\Omega_i|}\right\rceil}}\). Let \(f : \prod_{i=1}^n \Omega_i \to \{0,1\}^{\sum_{i=1}^n {\left\lceil{\log_2 |\Omega_i|}\right\rceil}}\) be the concatenation of these mappings. More precisely, \(f((x_1,\ldots,x_n)) = \mathrm{concatenate}(f_1(x_1),\ldots,f_n(x_n))\). Let \(N = \sum_{i=1}^n {\left\lceil{\log_2 |\Omega_i|}\right\rceil}\).
For every \(1 \le i \le n\), we define a projection function \(g_i : \{0,1\}^{\sum_{j=1}^n {\left\lceil{\log_2 |\Omega_i|}\right\rceil}} \to \Omega_i\) by \[g_i(x) = (f_i)^{-1}\left( x|_{\{\sum_{j=1}^{i-1} {\left\lceil{\log_2 |\Omega_j|}\right\rceil} + 1,\ldots,\sum_{j=1}^{i} {\left\lceil{\log_2 |\Omega_j|}\right\rceil} \}}\right)\] where \(g_i(x)\) is defined arbitrarily if the corresponding binary string is not in \(f_i\)’s image, as this will be a zero-probability event. Observe that for every \((x_1,\ldots,x_n) \in \prod_{i=1}^n \Omega_i\) and for every \(1 \le i \le n\), \(x_i = g_i(f(x_1,\ldots,x_n))\).
Let \(\mu^*\) be the distribution over \(\{0,1\}^{\sum_{i=1}^n {\left\lceil{\log_2 |\Omega_i|}\right\rceil}}\) that draws \(x \sim \mu\) and returns \(f(x)\). Since \(f\) is an injective function, \(\mu^*\) is equivalent to \(\mu\) up to relabeling.
For simulating subcube queries consider some \(I^* \subseteq [N]\) and \(w^* \in \{0,1\}^{I^*}\). For every \(1 \le i \le n\) and \(x^* \in \{0,1\}^N\), let \(x_i = g_i(x^*)\) (that is, we decompose \(x^*\) using \(x^* = f(x_1,\ldots,x_n)\)). Also, for every \(1 \le i \le n\), let \(A_i(I^*,w^*) = \left\{g_i(s^*) : s^* \in \{0,1\}^N \wedge s^*|_{I^*} = w^* \right\}\). Based on this composition, we obtain: \[\left\{ x^* \in \{0,1\}^N : x^*|_{I^*} = w^* \right\} = \left\{ f(x_1,\ldots,x_n) : \bigwedge_{i=1}^n \left(x_i \in A_i(I^*, w^*) \right) \right\}\] The last expression is the \(f\)-image of all elements in the \(\mu\)-subcube condition \(\prod_{i=1}^n A_i(I^*,w^*)\). Hence, every subcube query of \(\mu^*\) can be simulated using a single subcube query to \(\mu\).
Observe that this construction preserves prefix queries. That is, if a subcube query to \(\mu^*\) is a prefix query, then the simulated subcube query to \(\mu\) is a prefix query as well. Note that this argument holds for marginal queries as well, since we can extract the relevant bit of the sampled coordinate. ◻
Theorem [th:closeness-omegas] now follows.
Proof of Theorem [th:closeness-omegas]. Let \(\mu\) and \(\tau\) be two distributions over \(\prod_{i=1}^n \Omega_i\), where \(\Omega_1,\ldots,\Omega_n\) are all finite. We use Lemma 18 to define two distributions \(\mu^*\), \(\tau^*\) that are identical to \(\mu\), \(\tau\) respectively up to relabeling (which is the same in both constructions). Based on this lemma:
\(d_\mathrm{TV}(\tau^*, \mu^*) = d_\mathrm{TV}(\tau, \mu)\), since \(\mu^*\), \(\tau^*\) are the same as \(\mu\), \(\tau\) up to relabeling (which is the same for both constructions \(\mu \to \mu^*\) and \(\tau \to \tau^*\)).
Every prefix query to \(\tau^*\) can be simulated using a single prefix query to \(\tau\).
Every marginal prefix query to \(\mu^*\) can be simulated using a single marginal prefix query to \(\mu\).
Hence, we can distinguish between \(\tau = \mu\) and \(d_\mathrm{TV}(\tau, \mu) > \varepsilon\) using Theorem \(\ref{th:closeness-linearithmic}\) with the input \((\mu^*, \tau^*, \varepsilon)\) by simulating every query to \(\tau^*\) or \(\mu^*\) through a single query to the corresponding input distribution \(\tau\) or \(\mu\). ◻
8 Upper bound for ↩︎
We reduce a test for to a test for , based on the following key observation:
Observation 19. Let \(\mu\) be a distribution over \(\prod_{i=1}^n \Omega_i\). If \(\mu\) is \(\varepsilon\)-far from any product distribution, then in particular it is \(\varepsilon\)-far from the product of its marginals, \(\prod_{i=1}^n \mu|_i\).
In the binary setting, simulating a marginal prefix query to the product of marginals is pretty straightforward and can be done using one unconditional query to \(\mu\), which is in particular a prefix query:
Observation 20. Let \(\mu\) be a distribution over \(\{0,1\}^n\), and let \(\mu' = \prod_{i=1}^n \mu|_i\) be the product of \(\mu\)’s marginals. Then we can simulate every marginal prefix query to \(\mu'\) using one unconditional sample from \(\mu\) (and keeping its \(i\)th entry).
In the general setting, we need the stronger subcube access. The reason is that when taking a prefix marginal query at index \(i\) from the binary representation of \(\mu' = \prod_{j=1}^n \mu|_j\), it may be that that \(i\) is “in the middle” of the \(\lceil\log |\Omega_j|\rceil\)-bit representation of \(j\)th coordinate of \(\mu'\), and then this query must translate to a non-trivial set \(A_j\subseteq\Omega_j\) when simulating it using query access to \(\mu\).
Observation 21. Let \(\mu\) be a distribution over \(\prod_{i=1}^n \Omega_i\), and let \(\mu' = \prod_{i=1}^n \mu|_i\) be the product of \(\mu\)’s marginals. Then we can simulate every marginal prefix query to \(\mu'\) using one subcube query to \(\mu\).
At this point, we can prove Theorem [th:ubnd-product].
Proof. Let \(\mu' = \prod_{i=1}^n \mu|_i\) be the product of \(\mu\)’s marginals. If \(\mu\) is a product distribution then \(\mu' = \mu\), and if \(\mu\) is \(\varepsilon\)-far from every product distribution, then in particular \(d_\mathrm{TV}(\mu, \mu') > \varepsilon\).
Since \(\mu\) is accessible through the subcube oracle, we can use Observation 21 to simulate every marginal prefix query to \(\mu'\) at the cost of one subcube query to \(\mu\). If \(|\Omega_i| = 2\) for every \(1 \le i \le n\), then we can use an unconditional sample instead of a subcube query by Observation 20.
Hence, we can reduce the \(\varepsilon\)-test of \(\mu\) for to an \(\varepsilon\)-test of the equivalence of \(\mu'\) and \(\mu\), which we perform using Theorem [th:closeness-omegas]. As noted above, this produces subcube queries for general alphabets, and only prefix queries for the binary setting. ◻
9 Explicit algorithms↩︎
We provide here explicit representations for the binary setting algorithms constructed in this paper.
9.0.0.1 Levin’s work-balance method
For a random variable \(X\) that is bounded between \(0\) and \(1\), it distinguishes between \(\mathop{{\rm E}\/}[X] = 0\) and \(\mathop{{\rm E}\/}[X] > \varepsilon\). To do that, we use another random variable \(Y\), for which we can distinguish between \(\mathop{{\rm E}\/}[X | Y=y] = 0\) and \(\mathop{{\rm E}\/}[X | Y=y] > \rho\) for every \(0 < \rho < 1\), at a cost of \(O(1 / \rho)\). Overall, the cost of the algorithm is \(O(\log^2 \varepsilon^{-1} / \varepsilon)\). The original construction is found in [21] and the following optimized version appears as an exercise in [22].
The black box is run a logarithmic number of times for every \(y\) that we draw (as opposed to once in, for example, [22]) since it refers here to a procedure with two-sided error.
9.0.0.2 \(\chi^2\)-test of single-bit distributions
The following is the algorithm that detects the difference between two Bernoulli distributions as it was described in Lemma [lemma:single-bit-chi-square-test].
9.0.0.3 Testing
The proof of Theorem [th:closeness-linearithmic] translates to the following explicit algorithm.
9.0.0.4 Testing
The proof of Theorem [th:ubnd-product] translates in the binary setting to the following explicit algorithm. Note that it is almost identical to Algorithm 3, since we only substitute the marginal prefix oracle \(\tau|_i^{x_{[i-1]} = w_{[i-1]}}\) with the marginal oracle of \(\mu\).
References↩︎
Technion - Israel Institute of Technology, Israel. Email: tomer-adar@campus.technion.ac.il.↩︎
Technion - Israel Institute of Technology, Israel. Email: eldar@cs.technion.ac.il. Research supported by an Israel Science Foundation grant number 879/22.↩︎
University of Haifa and Technion - Israel Institute of Technology, Israel. Email: alevi@ds.haifa.ac.il.↩︎