0}\left[\epsilon^{2}(2^{k}-1)2^{s}\cdot\frac{\sum_{d\in\mathcal{C}_{r,|T|}(h,k,s)}\mathbb{P}\left[\bm{d}=d\right]\left(\prod_{i=1}^{r}g_{0}(T(d,i))\right)}{\sum_{d\in\mathcal{M}}\mathbb{P}\left[\bm{d}=d\right]\left(\prod_{i=1}^{r}g_{0}(T(d,i))\right)}\right]\,.$

Therefore, our goal is to show the following:

$\sum_{h\geq 0,s\geq 2k\geq
2}\epsilon^{2}(2^{k}-1)2^{s}\cdot\frac{\sum_{d\in\mathcal{C}_{r,|T|}(h,k,s)}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))}{\sum_{d\in\mathcal{M}}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))}\stackrel{{\scriptstyle\mathclap{\mbox{?}}}}{{\leq}}c\cdot\epsilon^{2}\cdot\frac{|T|^{6}}{r^{2}}\,,$
(18)

where we used the fact that $\epsilon^{2}(2^{k}-1)2^{s}=0$ when $k=0$ to limit
the range of $k$ in the summation to $k\geq 1$, and then used the fact that
$s\geq 2k$ for any nonempty $\mathcal{C}_{r,|T|}(h,k,s)$ to limit the range of
$s$.

First, note that for any single-character binary string $t$ (i.e. strings “0”
and “1”), we have $g_{0}(t)=1/2$. We may hence lower bound the denominator of
(18) by counting only those $d\in\mathcal{M}$ that have no collisions at all
(i.e. $d\in\mathcal{C}_{r,|T|}(0,0,0)$), whose total probability is lower
bounded by Proposition 5.12:

$\sum_{d\in\mathcal{M}}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))\geq\sum_{d\in\mathcal{C}_{r,|T|}(0,0,0)}\mathbb{P}\left[\bm{d}=d\right]\left(\frac{1}{2}\right)^{|T|}\geq\left(\frac{1}{2}\right)^{|T|}\left(1-\frac{|T|^{2}}{r}\right)>\left(\frac{1}{2}\right)^{|T|+1}\,,$

where we used the assumption that $|T|^{4}\leq r/100$ in the last inequality.

We proceed similarly to upper bound the numerator of (18). For any
$d\in\mathcal{C}_{r,|T|}(h,k,s)$, the terms in $\prod_{i=1}^{r}g_{0}(T(d,i))$
satisfying $d_{i}=1$ are again equal to $1/2$, while all other terms are
trivially at most $1$. Moreover, by definition of $(h,k,s)$-collisions we have
$\sum_{i=1}^{r}\mathds{1}\left[d_{i}=1\right]=|T|-(2h+k+s)$. Hence, for any
$h\geq 0$ and $s\geq 2k\geq 2$, we have

$\prod_{i=1}^{r}g_{0}(T(d,i))\leq\left(\frac{1}{2}\right)^{|T|-(2h+k+s)}\leq\left(\frac{1}{2}\right)^{|T|}\cdot
2^{2h+\frac{3}{2}s}\,,$

and therefore, using Proposition 5.11,

$\displaystyle\sum_{d\in\mathcal{C}_{r,|T|}(h,k,s)}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))$
$\displaystyle\leq\left(\frac{1}{2}\right)^{|T|}\cdot
2^{2h+\frac{3}{2}s}\cdot\sum_{d\in\mathcal{C}_{r,|T|}(h,k,s)}\mathbb{P}\left[\bm{d}=d\right]$
$\displaystyle\leq\left(\frac{1}{2}\right)^{|T|}\cdot\left(\frac{(2h|T|)^{2}}{r}\right)^{h}\cdot\left(\frac{(2k|T|)^{3/2}}{r}\right)^{s}\,.$

Combining the results above, along with the observation that $h,k,s\leq|T|$
for any nonzero terms in the numerator of (18), and using the notation
$\lesssim$ to absorb constant factors, we obtain

$\displaystyle\sum_{h\geq 0,s\geq 2k\geq
2}(2^{k}-1)2^{s}\cdot\frac{\sum_{d\in\mathcal{C}_{r,|T|}(h,k,s)}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))}{\sum_{d\in\mathcal{M}}\mathbb{P}\left[\bm{d}=d\right]\prod_{i=1}^{r}g_{0}(T(d,i))}$
$\displaystyle\qquad<\sum_{\begin{subarray}{c}|T|\geq h\geq 0,\\\ |T|\geq
s\geq 2k\geq
2\end{subarray}}2^{\frac{3}{2}s}\cdot\frac{\left(\frac{1}{2}\right)^{|T|}\cdot\left(\frac{(2h|T|)^{2}}{r}\right)^{h}\cdot\left(\frac{(2k|T|)^{3/2}}{r}\right)^{s}}{\left(1/2\right)^{|T|+1}}$
$\displaystyle\qquad=2\cdot\sum_{\begin{subarray}{c}|T|\geq h\geq 0,\\\
|T|\geq s\geq 2k\geq
2\end{subarray}}\left(\frac{(2h|T|)^{2}}{r}\right)^{h}\cdot\left(\frac{(4k|T|)^{3/2}}{r}\right)^{s}$
$\displaystyle\qquad\leq 2\cdot\sum_{\begin{subarray}{c}|T|\geq h\geq 0,\\\
|T|\geq s\geq 2k\geq
2\end{subarray}}\left(\frac{4|T|^{4}}{r}\right)^{h}\left(\frac{8|T|^{3}}{r}\right)^{s}$
$\displaystyle\qquad<2\cdot\sum_{h\geq
0}\left(\frac{4|T|^{4}}{r}\right)^{h}\left[\sum_{s\geq 2}\sum_{1\leq k\leq
s/2}\cdot\left(\frac{8|T|^{3}}{r}\right)^{s}\right]$ $\displaystyle\qquad\leq
2\cdot\sum_{h\geq 0}\left(\frac{4|T|^{4}}{r}\right)^{h}\left[\sum_{s\geq
2}\frac{s}{2}\cdot\left(\frac{8|T|^{3}}{r}\right)^{s}\right]$
$\displaystyle\qquad\lesssim\left(\frac{|T|^{3}}{r}\right)^{2}\sum_{h\geq
0}\left(\frac{4|T|^{4}}{r}\right)^{h}$
$\displaystyle\qquad\lesssim\frac{|T|^{6}}{r^{2}}\,,$

where we used the assumption that $|T|^{4}\leq r/100$ to establish the
convergence of the two geometric series,151515Namely, we used the formulas
$\sum_{i\geq 0}x^{i}=\frac{1}{1-x}$ and $\sum_{i\geq
2}ix^{i}=\frac{(2-x)x^{2}}{(1-x)^{2}}$ for $|x|<1$. thus concluding the proof.
∎

We now use this result to upper bound the mutual information between $\bm{Z}$
and the subtrace produced by a range of $\Theta(n/m)$ consecutive dominoes.

######  Lemma 5.17.

Suppose $n^{-1/4}<\epsilon<1$, and let $\frac{n}{m}\leq r\leq 2\frac{n}{m}$ be
a positive integer. Suppose $\bm{Z}\sim\mathsf{Ber}(1/2)$ and let $\bm{T}$
denote the subtrace generated by a range of $r$ consecutive dominoes,
according to distribution $\mathcal{D}_{\bm{Z}}$. Suppose
$m=o\left(\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}\right)$.
Then as $n\to\infty$ we have

$I(\bm{Z}:\bm{T})=O\left(\frac{\epsilon^{4}\log^{12}n}{r^{4}}\right)\,.$

###### Proof.

As before, let $P_{z}$ denote the conditional probabilities of $\bm{T}$ given
$\bm{Z}=z$. Let $Q\vcentcolon=(P_{0}+P_{1})/2$ denote the (marginal)
distribution of $\bm{T}$.

Our strategy will be to decompose the set of possible subtraces $T$ according
to whether $|T|\lesssim\log n$ (the typical case) or $|T|\gtrsim\log n$. In
the former case, Lemma 5.16 will give that the ratio $P_{1}(T)/P_{0}(T)$ is
close to $1$, while in the latter case, we will use Poisson concentration
bounds to argue that such long traces cannot contribute too much to the mutual
information.

Concretely, we start by upper bounding $I(\bm{Z}:\bm{T})$ by the sum a
$\chi^{2}$-type expression for $|T|\leq 20\log n$, and tail probabilities for
$|T|>20\log n$:

$\displaystyle I(\bm{Z}:\bm{T})$ $\displaystyle=H(\bm{T})-H(\bm{T}|\bm{Z})$
$\displaystyle=-\sum_{T}Q(T)\log(Q(T))+\sum_{z\in\\{0,1\\}}\mathbb{P}\left[Z=z\right]\sum_{T}P_{z}(T)\log(P_{z}(T))$
$\displaystyle=-\sum_{T}\frac{P_{0}(T)+P_{1}(T)}{2}\log(Q(T))+\sum_{T}\left[\frac{P_{0}(T)}{2}\log(P_{0}(T))+\frac{P_{1}(T)}{2}\log(P_{1}(T))\right]$
$\displaystyle=\frac{1}{2}\sum_{T}\left[P_{0}(T)\log\left(\frac{P_{0}(T)}{Q(T)}\right)+P_{1}(T)\log\left(\frac{P_{1}(T)}{Q(T)}\right)\right]$
$\displaystyle\leq\frac{1}{2}\sum_{T}\left[P_{0}(T)\left(\frac{P_{0}(T)}{Q(T)}-1\right)+P_{1}(T)\left(\frac{P_{1}(T)}{Q(T)}-1\right)\right]$
$\displaystyle=\frac{1}{2}\sum_{T}\left[P_{0}(T)\left(\frac{P_{0}(T)-P_{1}(T)}{P_{0}(T)+P_{1}(T)}\right)+P_{1}(T)\left(\frac{P_{1}(T)-P_{0}(T)}{P_{0}(T)+P_{1}(T)}\right)\right]$
$\displaystyle=\frac{1}{2}\sum_{T}\left[\frac{\left(P_{1}(T)-P_{0}(T)\right)^{2}}{P_{0}(T)+P_{1}(T)}\right]$
$\displaystyle<\frac{1}{2}\sum_{T:|T|\leq 20\log
n}\frac{\left(P_{1}(T)-P_{0}(T)\right)^{2}}{P_{0}(T)}+\frac{1}{2}\sum_{T:|T|>20\log
n}\left(P_{0}(T)+P_{1}(T)\right)$ $\displaystyle=\frac{1}{2}\sum_{T:|T|\leq
20\log n}P_{0}(T)\left(\frac{P_{1}(T)}{P_{0}(T)}-1\right)^{2}$
$\displaystyle\qquad+\frac{1}{2}\underset{}{\mathbb{P}}\left[|\bm{T}|>20\log
n\;\;\mid\;\;\bm{Z}=0\right]+\frac{1}{2}\underset{}{\mathbb{P}}\left[|\bm{T}|>20\log
n\;\;\mid\;\;\bm{Z}=1\right]\,.$

We start with the first term in the last expression above. We want to show
that, when $|T|\leq 20\log n$, we have $|T|^{4}=o(r)$, which is sufficient for
satisfying the condition of Lemma 5.16. Recalling the assumptions
$\frac{n}{m}\leq r\leq 2\frac{n}{m}$,
$m=o\left(\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}\right)$ and
$\epsilon\geq\frac{1}{n^{1/4}}$, we have

$\displaystyle\frac{|T|^{4}/20^{4}}{r}$
$\displaystyle\leq\frac{\log^{4}n}{r}\leq\frac{m\log^{4}n}{n}\ll\frac{\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}\log^{4}n}{n}\leq
1\,,$

and hence the condition $|T|^{4}\leq r/100$ holds for sufficiently large $n$.
Therefore Lemma 5.16 yields

$\frac{1}{2}\sum_{T:|T|\leq 20\log
n}P_{0}(T)\left(\frac{P_{1}(T)}{P_{0}(T)}-1\right)^{2}\leq\frac{1}{2}\sum_{T:|T|\leq
20\log
n}P_{0}(T)\left(c\cdot\epsilon^{2}\cdot\frac{|T|^{6}}{r^{2}}\right)^{2}=O\left(\frac{\epsilon^{4}\log^{12}n}{r^{4}}\right)\,.$

We now deal with the second component. Recall (see 5.6) that $|\bm{T}|$ is
distributed according to a Poisson distribution completely determined by the
number of dominoes in the range:

$|\bm{T}|\sim\mathsf{Poi}\left(r\cdot\frac{2m}{n}\right)\,,$

independently of $\bm{Z}$. Let $\lambda\vcentcolon=r\cdot\frac{2m}{n}$ and
note that $2\leq\lambda\leq 4\leq\log n$. 3.4 gives, for $z\in\\{0,1\\}$,

$\underset{}{\mathbb{P}}\left[|\bm{T}|>20\log
n\;\;\mid\;\;\bm{Z}=z\right]\leq\mathbb{P}\left[|\bm{T}|-\lambda>19\log
n\right]\leq e^{-\frac{(19\log n)^{2}}{2(\lambda+19\log n)}}\leq
e^{-\frac{361\log n}{40}}\leq\frac{1}{n^{9}}\,.$

Finally, we have

$\displaystyle\frac{1}{n^{9}}\leq\frac{\epsilon^{4}}{r^{4}}\impliedby\frac{1}{n^{9}}\leq\frac{1/n}{16n^{4}/m^{4}}\iff\frac{16}{n^{4}}\leq
m^{4}\iff\frac{2}{n}\leq m\,,$

which holds trivially, completing the proof. ∎

Since subtraces produced by disjoint ranges are conditionally independent
given $\bm{Z}$, applying the chain rule along with the data processing
inequality concludes the proof.

######  Lemma 5.18 (Refinement of 5.9).

Suppose $n^{-1/4}<\epsilon<1$. Let $\bm{Z}\sim\mathsf{Ber}(1/2)$,
$\bm{\pi}\sim\mathcal{D}_{\bm{\pi}}$, and let $\bm{\mathcal{T}}$ be a trace of
size $\mathsf{Poi}(m)$ drawn from $\pi$. Then if
$m=o\left(\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}\right)$, we
have

$I(\bm{Z}:\bm{\mathcal{T}})=O\left(\frac{\epsilon^{4}m^{5}}{n^{4}}\log^{12}n\right)=o(1)\,,$

and hence any algorithm that succeeds in distinguishing the YES and NO cases
with probability at least $51\%$ (over $\bm{Z}$ and $\bm{\mathcal{T}}$)
requires sample complexity at least

$\Omega\left(\left(\frac{n}{\epsilon}\right)^{4/5}\cdot\frac{1}{\log^{4}n}\right)\,.$

###### Proof.

Fix an arbitrary partition of the domain $[2n]$ into consecutive ranges
$R_{1},\dotsc,R_{m^{\prime}}$ such that 1) each $R_{i}$ is a contiguous range
with multiple of $4$ length, and hence consists of $|R_{i}|/4$ consecutive
dominoes (recall that we assume even $n$ for simplicity); and 2) each $R_{i}$
satisfies $\frac{n}{m}\leq|R_{i}|/4\leq 2\frac{n}{m}$. It follows that
$m^{\prime}=\Theta(m)$ and, letting $r_{i}\vcentcolon=|R_{i}|/4$ for each
$i\in[m^{\prime}]$, each $r_{i}$ satisfies the requirements of Lemma 5.17.

Let $\bm{T}_{i}$ be the subtrace generated by range $R_{i}$, so that the final
trace is obtained by concatenation of all subtraces:

$\bm{\mathcal{T}}=\bm{T}_{1}\circ\bm{T}_{2}\dotsm\circ\bm{T}_{m^{\prime}}\,.$

The data processing inequality yields

$I(\bm{Z}:\bm{\mathcal{T}})\leq
I(\bm{Z}:\bm{T}_{1},\dotsc,\bm{T}_{m^{\prime}})\,.$

Note that, conditional on $\bm{Z}$, the entries of $\bm{\pi}$ in different
dominoes are mutually independent as per the process described in Definition
5.7. Then, recalling the distribution of subtraces described in Definition
5.5, it follows that the $\bm{T}_{i}$ are mutually independent conditional on
$\bm{Z}$. Thus the chain rule of mutual information and Lemma 5.17 give

$I(\bm{Z}:\bm{\mathcal{T}})\leq\sum_{i=1}^{m^{\prime}}I(\bm{Z}:\bm{T}_{i})=\Theta(m)\cdot
O\left(\frac{\epsilon^{4}m^{4}\log^{12}n}{n^{4}}\right)=O\left(m^{5}\cdot\frac{\epsilon^{4}}{n^{4}}\log^{12}n\right)=o(1)\,,$

as desired. Finally, applying 5.3 establishes the second conclusion. ∎

Putting together Proposition 5.2 and Lemma 5.18 establishes Theorem 5.1:

######  Corollary 5.19 (Refinement of Theorem 5.1).

Let $\Pi_{1}$ contain only the uniform distribution over $[2n]$, and let
$\Pi_{2}$ be the set of distributions over $[2n]$ that are $\epsilon$-far from
uniform in total variation distance. Then $(\Pi_{1},\Pi_{2},51/100)$-testing
under the parity trace requires sample complexity at least
$\Omega\left(\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}+\frac{\sqrt{n}}{\epsilon^{2}}\right)$
samples. Furthermore, this bound holds even if the input distribution $\pi$ is
guaranteed to have $1/2$ mass uniformly distributed over the zero-valued (i.e.
even) coordinates.

###### Proof.

The lower bound of $\Omega(\sqrt{n}/\epsilon^{2})$ holds by Proposition 5.2.
Moreover, we have

$\left(\frac{n}{\epsilon}\right)^{4/5}\frac{1}{\log^{4}n}\geq\frac{\sqrt{n}}{\epsilon^{2}}\iff\epsilon\geq\frac{\log^{10/3}n}{n^{1/4}}\,,$

in which case Lemma 5.18 establishes the bound. ∎

##  6 Distribution-Free Sample-Based Property Testing

In this section, we relate distribution testing under the parity trace to
distribution-free sample-based property testing. The main ideas of this
section are:

  1. 1.

We define _labeled-distribution testing_ as a generalized reformulation of
distribution-free sample-based property testing that makes the connection to
distribution testing more explicit.

  2. 2.

There is a natural type of labeled distribution properties, which we call
_density properties_ , that includes some property testing problems, and some
more challenging versions of standard distribution testing problems. We use
the edit distance and Ramsey theory to show that testing these properties is
equivalent to testing distributions under the parity trace.

  3. 3.

Using this equivalence, we get new tight positive results for distribution-
free sample-based testing (in the more general labeled-distribution
definition) by applying Theorem 1.1.

  4. 4.

There is a _testing-by-learning_ reduction for labeled-distribution testing,
similar to the standard testing-by-learning reduction of [GGR98], that allows
non-constructive upper bounds on distribution testing under the parity trace.
This will be used in Section 7 to get upper bounds for some testing problems
in the trace reconstruction model.

The section is organized as follows:

Section 6.1:

The definition of labeled distributions.

Section 6.2:

The definition of edit distance, which is closely related to labeled
distributions and will be necessary for all of our applications in the
remainder of the paper.

Section 6.3:

The definition of labeled distribution testing, and how it generalizes the
conventional distribution testing and distribution-free sample-based property
testing models.

Section 6.4:

A testing-by-learning reduction for labeled-distribution testing.

Section 6.5:

The definition of _density properties_ , and the equivalence of testing
density properties to distribution testing under the parity trace.

Section 6.6:

The proof of our main result on labeled distribution testing, Theorem 1.5,
which is an application of Theorem 1.1.

Section 6.7:

An upper bound on testing uniform distributions against unrestricted
distributions under the parity trace (Theorem 6.34).

Section 6.8:

The equivalence between testing support size $k$ under the parity trace, and
testing $k$-alternating functions in the distribution-free sample-based model
(Theorem 6.38), and an alternate proof of the lower bounds of [BFH21] for
testing halfspaces, among others.

###  6.1 Labeled Distributions

We shall now define labeled distributions and edit distance, which are closely
related.

######  Definition 6.1 (Labeled Distribution).

On any fixed domain $\mathcal{X}$, a _labeled distribution_ is a pair
$(f,\mathcal{D})$ of a function $f:\mathcal{X}\to\\{0,1\\}$ and a probability
distribution $\mathcal{D}$ over $\mathcal{X}$. We write $\mathcal{D}_{f}$ for
the probability distribution over $\mathcal{X}\times\\{0,1\\}$, where the
density of any $(x,b)\in\mathcal{X}\times\\{0,1\\}$ is defined as

$\mathcal{D}_{f}(x,b)\vcentcolon=\begin{cases}\mathcal{D}(x)&\text{ if
}b=f(x)\\\ 0&\text{ otherwise.}\end{cases}$

In other words, a sample from $\mathcal{D}_{f}$ is obtained by sampling
$x\sim\mathcal{D}$ and taking $(x,f(x))$.

We study the case $\mathcal{X}=\mathbb{Z}$. For a labeled distribution
$(f,\mathcal{D})$ over $\mathbb{Z}$, it may be the case that $f$ “alternates”
an infinite number of times. We restrict our attention to the “proper” labeled
distributions, where $f$ has a finite number of alternations “on the left”,
defined as follows.

######  Definition 6.2 (Proper Labeled Distributions).

A labeled distribution $(f,\mathcal{D})$ is _1-proper_ if there exists
$t\in\mathbb{Z}$ such that $f(x)=1$ for all $x<t$. It is _0-proper_ if,
instead, $f(x)=0$ for all $x<t$. If $(f,\mathcal{D})$ is either 0- or
1-proper, we call it _proper_.

######  Remark 6.3.

When studying labeled distribution testing, it suffices to consider proper
labeled distributions. This is because, for every labeled distribution
$\mathcal{D}_{f}$ and every $\delta>0$, there exists a _proper_ labeled
distribution $\mathcal{D}_{g}$ such that
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})<\delta$. So
every distribution is indistinguishable (to any algorithm with bounded sample
size) from some proper distribution.

######  Definition 6.4 (Alternation Sequence).

For any proper labeled distribution $(f,\mathcal{D})$, the _alternation
sequence_ is the unique sequence $a_{1}<a_{2}<a_{3}<\dotsm$ such that $f$ is
constant on the intervals $(-\infty,a_{1}]$, $(a_{1},a_{2}]$, $\dotsc$, and
$f(a_{i-1})\neq f(a_{i})$. Note that if $(f,\mathcal{D})$ is 1-proper, then
$f$ takes value $\mathsf{par}(i)$ on the interval $(a_{i-1},a_{i}]$, and value
1 on $(-\infty,a_{1}]$. If $(f,\mathcal{D})$ is 0-proper, it takes the
opposite values. Note that this sequence always exists when $(f,\mathcal{D})$
is proper, and it may be an infinite sequence.

######  Definition 6.5 (Density Sequence).

For any proper labeled distribution $(f,\mathcal{D})$ with alternation
sequence $a_{1}<a_{2}<a_{3}<\dotsm$, we define the _density sequence_
$\pi_{f,\mathcal{D}}:\mathbb{N}\to\mathbb{R}_{\geq 0}$ as follows. If
$(f,\mathcal{D})$ is 1-proper, we define

$\pi_{f,\mathcal{D}}(i)\vcentcolon=\begin{cases}\mathcal{D}(-\infty,a_{1}]&\text{
if }i=1\\\ \mathcal{D}(a_{i-1},a_{i}]&\text{ if }i>1\,.\end{cases}$

If $(f,\mathcal{D})$ is 0-proper, we define

$\pi_{f,\mathcal{D}}(i)\vcentcolon=\begin{cases}0&\text{ if }i=1\\\
\mathcal{D}(-\infty,a_{1}]&\text{ if }i=2\\\
\mathcal{D}(a_{i-2},a_{i-1}]&\text{ if }i>2\,.\end{cases}$

Note that $\pi_{f,\mathcal{D}}$ is a probability distribution, since
$\sum_{i=1}^{\infty}\pi_{f,\mathcal{D}}(i)=\sum_{x\in\mathbb{Z}}\mathcal{D}(x)=1$.
For any set $\Xi$ of proper labeled distributions, we write

$\Pi(\Xi)\vcentcolon=\\{\pi_{f,\mathcal{D}}:(f,\mathcal{D})\in\Xi\\}$

for the set of density sequences (probability distributions) associated with
the proper labeled distributions in $\Xi$.

The following simple formula for TV distance for labeled distributions is
often useful.

######  Proposition 6.6.

Let $(f,\mathcal{D})$ and $(g,\mathcal{E})$ be labeled distributions over
$\mathbb{Z}$. Then

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})=\frac{1}{2}\sum_{i\in\mathbb{Z}}\mathds{1}\left[f(i)\neq
g(i)\right](\mathcal{D}(i)+\mathcal{E}(i))+\mathds{1}\left[f(i)=g(i)\right]|\mathcal{D}(i)-\mathcal{E}(i)|\,.$

###### Proof.

By definition,

$\displaystyle\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})$
$\displaystyle=\frac{1}{2}\sum_{(i,b)\in\mathbb{Z}\times\\{0,1\\}}|\mathcal{D}_{f}(i,b)-\mathcal{E}_{g}(i,b)|$
$\displaystyle=\frac{1}{2}\left(\sum_{\begin{subarray}{c}(i,b)\in\mathbb{Z}\times\\{0,1\\}\\\
f(i)=g(i)=b\end{subarray}}|\mathcal{D}(i)-\mathcal{E}(i)|+\sum_{\begin{subarray}{c}(i,b)\in\mathbb{Z}\times\\{0,1\\}\\\
f(i)=b,g(i)\neq
b\end{subarray}}\mathcal{D}(i)+\sum_{\begin{subarray}{c}(i,b)\in\mathbb{Z}\times\\{0,1\\}\\\
f(i)\neq b,g(i)=b\end{subarray}}\mathcal{E}(i)\right)$
$\displaystyle=\frac{1}{2}\sum_{i\in\mathbb{Z}}\mathds{1}\left[f(i)\neq
g(i)\right](\mathcal{D}(i)+\mathcal{E}(i))+\mathds{1}\left[f(i)=g(i)\right]|\mathcal{D}(i)-\mathcal{E}(i)|\,.\qed$

###  6.2 Edit Distance

We define two notions of edit distance: one for labeled distributions on
domain $\mathbb{Z}$, and one for distributions over $\mathbb{N}$.

######  Definition 6.7 (Edit Distance for Labeled Distributions).

For any two proper labeled distributions $(f,\mathcal{D})$ and
$(g,\mathcal{E})$ on domain $\mathbb{Z}$, define

$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),(g,\mathcal{E}))\vcentcolon=\inf\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}^{\prime}_{f^{\prime}},\mathcal{E}^{\prime}_{g^{\prime}})\,,$

where the infimum is taken over all proper labeled distributions
$(f^{\prime},\mathcal{D}^{\prime})$ and $(g^{\prime},\mathcal{E}^{\prime})$
that have the same density sequences as the original distributions, i.e. that
satisfy $\pi_{f^{\prime},\mathcal{D}^{\prime}}=\pi_{f,\mathcal{D}}$ and
$\pi_{g^{\prime},\mathcal{E}^{\prime}}=\pi_{g,\mathcal{E}}$.

Next, we will define the edit distance for distributions over $\mathbb{N}$.
Recall that the TV distance is not the natural distance metric for
distribution testing under the parity trace, because distributions may have
maximum TV distance 1 while being indistinguishable under the parity trace.
Edit distance replaces the TV distance as the natural (pseudo-)metric for the
parity trace. We begin by introducing the notion of a _fractional string_.

######  Definition 6.8 (Fractional String).

A _fractional string_ is a finite sequence
$\sigma_{1}^{p_{1}}\sigma_{2}^{p_{2}}\dots\sigma_{n}^{p_{n}}$ where each
_fractional character_ $\sigma_{i}^{p_{i}}$ consists of a symbol
$\sigma_{i}\in\\{0,1\\}$ and a value $p_{i}\in\mathbb{R}_{\geq 0}$.

We now define the edit distance for fractional strings, which is an analog of
the standard edit distance for strings.

######  Definition 6.9 (Edit Distance for Fractional Strings).

Let $a=a_{1}^{p_{1}}a_{2}^{p_{2}}\dotsm a_{n}^{p_{n}}$ be a fractional string.
We define the following permitted edit operations on $a$, with associated
cost:

Insert:

For $i\in[n+1]$ and $b\in\\{0,1\\}$, $\mathsf{ins}_{i,b}(a)$ is the fractional
string obtained by inserting the fractional character $b^{0}$ immediately
before $a_{i}^{p_{i}}$. The cost of this operation is 0.

Delete:

For $i\in[n]$ such that $p_{i}=0$, $\mathsf{del}_{i}(a)$ is the fractional
string obtained by deleting the fractional character
$a_{i}^{p_{i}}=a_{i}^{0}$. The cost of this operation is 0.

Rearrange:

For $i\in[n-1]$ such that $a_{i}=a_{i+1}$, and $-p_{i}\leq\delta\leq p_{i+1}$,
$\mathsf{rearr}_{i,\delta}(a)$ is the fractional string obtained by replacing
$a_{i}^{p_{i}}a_{i+1}^{p_{i+1}}$ with
$a_{i}^{p_{i}+\delta}a_{i+1}^{p_{i+1}-\delta}$. The cost of this operation is
0.

Adjust:

For $i\in[n]$ and $\delta\geq-p_{i}$, $\mathsf{adj}_{i,\delta}(a)$ is the
fractional string obtained by replacing $p_{i}$ with $p_{i}+\delta$, so that
the fractional character $a_{i}^{p_{i}}$ becomes $a_{i}^{p_{i}+\delta}$. The
cost of this operation is $|\delta|/2$.

For a fractional string $a$, we say that a sequence of operations
$O_{1},\dotsc,O_{k}$ is permitted if for each $i\in[k]$, $O_{i}$ is a
permitted operation on the fractional string $(O_{i-1}\circ
O_{i-2}\circ\dotsm\circ O_{1})(a)$.

For two fractional strings $a$ and $b$, we define the _edit distance_
$\mathsf{dist}_{\mathsf{fr-edit}}(a,b)$ as the minimum $c$ such that there
exists a sequence of permitted operations $O_{1},\dots,O_{k}$ such that
$O_{k}\circ O_{k-1}\circ\dotsm\circ O_{1}(a)=b$ and the sum of costs of
operations $O_{i}$ is $c$.

Let $\pi:\mathbb{N}\to\mathbb{R}_{\geq 0}$ be any finitely-supported
probability distribution. We define the fractional string $\mathsf{str}(\pi)$
as follows. Since $\pi$ is finitely-supported, there is some $k\in\mathbb{N}$
such that $\pi(i)=0$ for all $i>k$. Then we define

$\mathsf{str}(\pi)\vcentcolon=1^{\pi(1)}0^{\pi(2)}1^{\pi(3)}0^{\pi(4)}\dotsm(\mathsf{par}(k))^{\pi(k)}\,.$

Finally, we may define the edit distance for distributions.

######  Definition 6.10 (Edit Distance for Distributions).

For two finitely-supported distributions $\pi,\pi^{\prime}$, we define

$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\vcentcolon=\mathsf{dist}_{\mathsf{fr-
edit}}(\mathsf{str}(\pi),\mathsf{str}(\pi^{\prime}))\,.$

The following alternate characterization of edit distance is helpful. We defer
the proof to Section D.2.

######  Lemma 6.11.

Let $\pi$ and $\pi^{\prime}$ be finitely-supported distributions over
$\mathbb{N}$. Then

$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})=\inf\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\,,$

where the infimum is taken over labeled distributions $(f,\mathcal{D})$ and
$(g,\mathcal{E})$ such that $\pi=\pi_{f,\mathcal{D}}$ and
$\pi^{\prime}=\pi_{g,\mathcal{E}}$.

From this lemma, we can see that the edit distance for distributions and
labeled distributions are essentially equivalent: for two proper labeled
distributions $(f,\mathcal{D})$ and $(g,\mathcal{E})$, the lemma implies

$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),(g,\mathcal{E}))=\mathsf{dist}_{\mathsf{edit}}(\pi_{f,\mathcal{D}},\pi_{g,\mathcal{E}})\,.$

It is easy to see that the following inequality holds in general:

$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\leq\mathsf{dist}_{\mathsf{TV}}(\pi,\pi^{\prime})\,.$
(19)

This can be verified by taking $(f,\mathcal{D})$ where $f(i)=\mathsf{par}(i)$
for $i\in\mathbb{N}$ and $f(i)=1$ for $i\leq 0$, and $\mathcal{D}(i)=\pi(i)$
for $i\in\mathbb{N}$ and $\mathcal{D}(i)=0$ for $i\leq 0$. Define
$(g,\mathcal{E})$ similarly for $\pi^{\prime}$. This satisfies
$\pi_{f,\mathcal{D}}=\pi$ and $\pi_{g,\mathcal{E}}=\pi^{\prime}$, and
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})=\mathsf{dist}_{\mathsf{TV}}(\pi,\pi^{\prime})$.

###  6.3 Labeled Distribution Testing

We now introduce _labeled distribution testing_. For labeled distributions
$(f,\mathcal{D})$ and $(g,\mathcal{E})$ over a fixed domain $\mathcal{X}$, we
abuse notation and write

$\mathsf{dist}_{\mathsf{TV}}((f,\mathcal{D}),(g,\mathcal{E}))\vcentcolon=\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\,,$

so that, for a property $\Xi$ of labeled distributions, we have

$\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)\vcentcolon=\\{(f,\mathcal{D}):\forall(g,\mathcal{E})\in\Xi,\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})>\epsilon\\}\,.$

######  Definition 6.12 (Labeled Distribution Testing).

Let $\Xi_{1}$ and $\Xi_{2}$ be properties of labeled distributions over a
fixed domain $\mathcal{X}$. A $(\Xi_{1},\Xi_{2},\alpha)$-labeled distribution
tester, with sample complexity $m$, is an algorithm $A$ that satisfies the
following, for every labeled distribution $(f,\mathcal{D})$ over
$\mathcal{X}$:

  1. 1.

If $(f,\mathcal{D})\in\Xi_{1}$, then
$\underset{S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)}{\mathbb{P}}\left[A(S_{f})\text{
accepts }\right]\geq\alpha$; and

  2. 2.

If $(f,\mathcal{D})\in\Xi_{2}$, then
$\underset{S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)}{\mathbb{P}}\left[A(S_{f})\text{
rejects }\right]\geq\alpha$.

The canonical form of this problem has
$\Xi_{2}\vcentcolon=\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1})$ for some
$\epsilon>0$.

We prove here that one can obtain the standard distribution testing and
distribution-free sample-based property testing models from our more general
labeled distribution testing model. To obtain, from the labeled distribution
testing model, the standard distribution testing model, where the goal is to
test a property $\Pi$ of distributions over domain $\mathcal{X}$, it suffices
to choose the property $\Xi=\Lambda\times\Pi$, where $\Lambda$ contains only
the constant 0 function over domain $\mathcal{X}$.

It is slightly less obvious how to obtain distribution-free sample-based
property testing from the labeled distribution testing model. Distribution-
free sample-based property testing is defined as follows.

######  Definition 6.13 (Distribution-Free Sample-Based Property Testing).

Let $\Lambda$ be a property of functions $\mathcal{X}\to\\{0,1\\}$ for some
fixed domain $\mathcal{X}$, and let $\epsilon>0$. A
$(\Lambda,\epsilon,\alpha)$-distribution-free sample-based property tester,
with sample complexity $m$, is an algorithm $A$ that satisfies the following,
for every function $f:\mathcal{X}\to\\{0,1\\}$ and distribution $\mathcal{D}$
over $\mathcal{X}$:

  1. 1.

If $f\in\Lambda$, then
$\underset{S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)}{\mathbb{P}}\left[A(S_{f})\text{
accepts }\right]\geq\alpha$; and

  2. 2.

If $\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq
g(x)\right]>\epsilon$ for all $g\in\Lambda$, then
$\underset{S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)}{\mathbb{P}}\left[A(S_{f})\text{
rejects }\right]\geq\alpha$.

This problem cannot be expressed neatly as the problem of distinguishing
between properties $\Lambda_{1}$ and $\Lambda_{2}$ of functions
$\mathcal{X}\to\\{0,1\\}$, because the set of functions that should be
rejected depends on the distribution $\mathcal{D}$. But we can express it as
distinguishing two properties $\Xi_{1}$, $\Xi_{2}$ of labeled distributions,
as shown in the next two propositions.

######  Proposition 6.14.

Fix a domain $\mathcal{X}$ and let $(f,\mathcal{D})$, $(g,\mathcal{E})$ be
labeled distributions. Then

$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq g(x)\right]\leq
2\cdot\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{G})\,.$

###### Proof.

For any event $X\subseteq\mathcal{X}\times\\{0,1\\}$, write
$\mathcal{D}_{f}(X)\vcentcolon=\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[(x,f(x))\in
X\right]$. Write
$\epsilon\vcentcolon=\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})$,
so that for any event $X\subseteq\mathcal{X}\times\\{0,1\\}$, we have
$\left|\mathcal{D}_{f}(X)-\mathcal{E}_{g}(X)\right|\leq\epsilon$.

Let $\Delta\vcentcolon=\\{x\in\mathcal{X}:f(x)\neq g(x)\\}$ and define the
event $E\vcentcolon=\\{(x,b):x\in\Delta,b=g(x)\\}$. Then
$\mathcal{D}_{f}(E)=0$ by definition, and
$\left|\mathcal{D}_{f}(E)-\mathcal{E}_{g}(E)\right|\leq\epsilon$, so
$\mathcal{E}_{g}(E)\leq\epsilon$. Then also
$\mathcal{E}(\Delta)=\mathcal{E}_{g}(E)\leq\epsilon$.

Define the event $F\vcentcolon=\\{(x,b):x\in\Delta,b\in\\{0,1\\}\\}$, which
satisfies $\mathcal{D}_{f}(F)=\mathcal{D}(\Delta)$ and
$\mathcal{E}_{g}(F)=\mathcal{E}(\Delta)$. Then
$\left|\mathcal{D}(\Delta)-\mathcal{E}(\Delta)\right|\leq\epsilon$, so
$\mathcal{D}(\Delta)\leq\mathcal{E}(\Delta)+\epsilon\leq 2\epsilon$. We
conclude that

$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq
g(x)\right]=\mathcal{D}(\Delta)\leq 2\epsilon\,.\qed$

######  Proposition 6.15.

Fix any domain $\mathcal{X}$. Let $\Lambda$ be any property of functions
$\mathcal{X}\to\\{0,1\\}$, and let $\Pi$ be the set of all distributions over
$\mathcal{X}$. Then, for $\Xi=\Lambda\times\Pi$,

  1. 1.

If there is a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon/2}(\Xi),\alpha)$-labeled
distribution tester with sample complexity $m$, then there is a
$(\Lambda,\epsilon,\alpha)$-distribution-free sample-based tester with sample
complexity $m$.

  2. 2.

If there is a $(\Lambda,\epsilon,\alpha)$-distribution-free sample-based
tester with sample complexity $m$, then there is a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))$-labeled distribution tester
with sample complexity $m$.

###### Proof.

For the first conclusion, the input to the distribution-free sample-based
property tester is a function $f:\mathcal{X}\to\\{0,1\\}$ and a distribution
$\mathcal{D}$ over $\mathcal{X}$. The algorithm will take a labeled sample
$S_{f}$ where $S\sim\mathsf{samp}(\mathcal{D},m)$, and simulate the labeled
distribution tester on $S_{f}$. Suppose that $f\in\Lambda$. Then
$\mathcal{D}_{f}\in\Lambda\times\Pi=\Xi$, so the labeled distribution tester
will accept with probability at least $\alpha$.

Now suppose that $f$ is $\epsilon$-far from $\Lambda$ with respect to
$\mathcal{D}$. Then for all $g:\mathcal{X}\to\\{0,1\\}$ and all distributions
$\mathcal{E}$ over $\mathcal{X}$, we have
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\geq\frac{1}{2}\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq
g(x)\right]>\epsilon/2$, due to Proposition 6.14. Therefore
$(f,\mathcal{D})\in\textsc{far}^{\mathsf{TV}}_{\epsilon/2}(\Xi)$, so the
tester will reject with probability at least $\alpha$.

For the second conclusion, we obtain a labeled distribution tester for $\Xi$
by taking, on input $(f,\mathcal{D})$, the labeled sample
$S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)$, and running the distribution-free
sample-based property tester on $S_{f}$.

If $(f,\mathcal{D})\in\Xi$ then $f\in\Lambda$, so the property tester will
accept with probability at least $\alpha$.

If $\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})>\epsilon$ for
all $(g,\mathcal{E})\in\Xi$, then in particular
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})>\epsilon$ for
all $g\in\Lambda$. Then there is an event
$E\subseteq\mathcal{X}\times\\{0,1\\}$ such that
$\left|\mathcal{D}_{f}(E)-\mathcal{D}_{g}(E)\right|>\epsilon$. We may assume
without loss of generality that $f(x)\neq g(x)$ for each $(x,b)\in E$ (since
we may remove any set of pairs $(x,b)$ where $f(x)=g(x)$ without changing this
difference). Then we can partition $E=E_{f}\cup E_{g}$ where
$E_{f}\vcentcolon=\\{(x,b)\in E:b=f(x)\\}$ and $E_{g}\vcentcolon=\\{(x,b)\in
E:b=g(x)\\}$. Then $\mathcal{D}_{f}(E)=\mathcal{D}_{f}(E_{f})$ and
$\mathcal{D}_{g}(E)=\mathcal{D}_{g}(E_{g})$.

It must be the case that either $\mathcal{D}_{f}(E_{f})>\epsilon$ or
$\mathcal{D}_{g}(E_{g})>\epsilon$. If $\mathcal{D}_{f}(E_{f})>\epsilon$, then
we can choose $\Delta\vcentcolon=\\{x\in\mathcal{X}:(x,f(x))\in E_{f}\\}$, so

$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq
g(x)\right]\geq\mathcal{D}(\Delta)=\mathcal{D}_{f}(E_{f})>\epsilon\,.$

If $\mathcal{D}_{g}(E_{g})>\epsilon$, a similar conclusion holds. Since this
holds for all $g\in\Lambda$, we see that the property tester should reject
with probability at least $\alpha$. ∎

###  6.4 Testing-by-Learning

[GGR98] observed that a proper learning algorithm for a hypothesis class $\Pi$
can be used as a property tester, by including an extra “verification” step.
It is convenient for us to adapt the same technique to a different type of
learning algorithm that works for classes of labeled distributions, where the
“hypothesis class” is not just a set of functions $\mathcal{X}\to\\{0,1\\}$,
but a joint set of function-distribution pairs.

For fixed domain $\mathcal{X}$ and property $\Pi$ of distributions over
$\mathcal{X}$, write $\textsc{close}^{\mathsf{TV}}_{\epsilon}(\Pi)$ for the
set of distributions $\pi$ over $\mathcal{X}$ satisfying
$\mathsf{dist}_{\mathsf{TV}}(\pi,\Pi)\leq\epsilon$.

######  Definition 6.16 (Labeled Distribution Learning).

Let $\Xi$ be a property of labeled distributions on some fixed domain
$\mathcal{X}$. A _labeled distribution learning algorithm_ for $\Xi$, with
success probability $\alpha$, error $\epsilon>0$, and sample complexity $m$,
is an algorithm $A$ that, on any input $(f,\mathcal{D})$, receives a labeled
sample $S_{f}\sim\mathsf{samp}(\mathcal{D}_{f},m)$ and outputs a function
$g:\mathcal{X}\to\\{0,1\\}$, and _succeeds_ with probability at least $\alpha$
over $S_{f}$ and the randomness of the algorithm. The _success_ event is
defined as follows:

Success:

If $(f,\mathcal{D})\in\Xi$, then
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})<\epsilon$.

We call the algorithm _proper_ if the success event also has the following
additional conditions:

Success∗:

If $(f,\mathcal{D})\notin\Xi$, then there exists $\mathcal{E}$ such that
$\mathcal{E}_{g}\in\Xi$.

If $(f,\mathcal{D})\in\Xi$, then there exists $\mathcal{E}$ such that
$\mathcal{E}_{g}\in\Xi$ and
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})<\epsilon$.

######  Definition 6.17 (Learner-Verifier Pair).

Let $\Xi$ be a property of labeled distributions on some fixed domain
$\mathcal{X}$, let $\epsilon,\delta>0$ and let $A$ be a _proper_ labeled
distribution learning algorithm for $\Xi$ with success probability
$1-\delta/3$, error $\epsilon/4$, and sample complexity $m_{A}$. Let
$\mathcal{G}_{A}\subseteq\\{0,1\\}^{\mathcal{X}}$ be the range of $A$. For
every $g\in\mathcal{G}_{A}$, let $\Pi_{g}$ be the property

$\Pi_{g}\vcentcolon=\\{\mathcal{E}:(g,\mathcal{E})\in\Xi\\}\,.$

Suppose $B=\\{B_{g}\\}_{g\in\mathcal{G}_{A}}$ is a family of algorithms such
that, for every $g\in\mathcal{G}_{A}$, algorithm $B_{g}$ is a
$(\textsc{close}^{\mathsf{TV}}_{\epsilon/4}(\Pi_{g}),\textsc{far}^{\mathsf{TV}}_{\epsilon/2}(\Pi_{g}),1-\delta/3)$-distribution
tester with sample complexity $m_{B}$. We call $(A,B)$ a _learner-verifier
pair_ for $\Xi$ with success probability $1-\delta$, error $\epsilon$, and
sample complexity $m_{A}+m_{B}$.

######  Proposition 6.18.

Let $\Xi$ be a property of labeled distributions such that there exists a
learner-verifier pair $(A,B)$ with success probability $1-\delta$, error
$\epsilon>0$, and sample complexity $m=m_{A}+m_{B}$. Then there is a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))$-labeled distribution tester
with sample complexity $m+O(1/\epsilon)$.

###### Proof.

On input $(f,\mathcal{D})$, the tester performs the following.

  1. 1.

Use $m_{A}$ samples to run the proper learner $A$, and obtain an output
function $g$.

  2. 2.

Use $O(1/\epsilon)$ samples from $\mathcal{D}$ to compute an estimate $z$ of
$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq g(x)\right]$, and
reject if this is greater than $\tfrac{3}{8}\epsilon$.

  3. 3.

Use $m_{B}$ samples to run the distribution tester $B_{g}$.

Suppose that $(f,\mathcal{D})\in\Xi$. Suppose that the algorithms $A$
succeeds, which occurs with probability at least $1-\delta/3$. Then there
exists $\mathcal{E}$ such that $\mathcal{E}_{g}\in\Xi$ and

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})\leq\epsilon/4\,,\qquad\text{
and
}\qquad\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})\leq\epsilon/4\,,$

by the conditions on the algorithm $A$, which is a proper learner. By the
multiplicative Chernoff bound, we have $z<\tfrac{3}{8}\epsilon$ with
probability at least $1-\delta/3$, after using $O(1/\epsilon)$ samples, so the
second step passes. Finally, assume the algorithm $B_{g}$ succeeds, which
occurs with probability $1-\delta/3$. Since $\mathcal{E}_{g}\in\Xi$, and
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})\leq\epsilon/4$, we have

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\Pi_{g})\leq\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})\leq\epsilon/4\,.$

So $\mathcal{D}\in\textsc{close}^{\mathsf{TV}}_{\epsilon/4}(\Pi_{g})$, and the
algorithm $B_{g}$ will accept. The probability of any of these steps failing
is at most $\delta$, by the union bound.

Now suppose that
$(f,\mathcal{D})\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$. Suppose for
contradiction that

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\Pi_{g})<\epsilon/2\qquad\text{ and
}\qquad\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})<\epsilon/2\,.$

Then there exists $\mathcal{E}\in\Pi_{g}$ such that $\mathcal{E}_{g}\in\Xi$
and $\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})<\epsilon/2$. Then

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\leq\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})+\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{g},\mathcal{E}_{g})=\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})+\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})<\epsilon\,,$

which is a contradiction. So it must be that either
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\Pi_{g})\geq\epsilon/2$, in which
case the third step rejects with probability at least $1-\delta/3$, or that
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})\geq\epsilon/2$,
in which case the second step rejects with probability at least $1-\delta/3$,
again using the multiplicative Chernoff bound. ∎

######  Remark 6.19.

This formalization captures the standard testing-by-learning reduction, when
$\Xi$ is a property of labeled distributions obtained by choosing a property
$\Lambda_{1}$ of functions $\mathcal{X}\to\\{0,1\\}$, setting $\Lambda_{2}$ to
be the set of all distributions over $\mathcal{X}$, and letting
$\Xi=\Lambda_{1}\times\Lambda_{2}$. In this case, the learner $A$ is the
standard PAC learning algorithm (see the proof of Lemma 6.35), and the
verifier $B$ simply accepts everything.

###  6.5 Density Properties and Distribution Testing Under the Parity Trace

Labeled-distribution testing is a more general reformulation of distribution-
free sample-based property testing, which allows a richer class of properties
to be defined. For the remainder of Section 6, we are interested in a certain
family of labeled-distribution properties that we call _density properties_.

######  Definition 6.20 (Density Property).

A property $\Xi$ of proper labeled distributions is a _density property_ if
there exists a set $\Pi$ of probability distributions over $\mathbb{N}$ such
that $\Pi=\Pi(\Xi)$; i.e. for any proper labeled distribution
$(f,\mathcal{D})$, it holds that $(f,\mathcal{D})\in\Xi$ if and only if
$\pi_{f,\mathcal{D}}\in\Pi$.

In this subsection, our goal is to establish the relationships between testing
density properties and distribution testing under the parity trace, which are
illustrated in Figure 1. Here we prove the $\to$ relations; examples showing
the $\not\to$ relations are discussed in Appendix E.

$(\textsf{LabeledDist},\mathsf{TV})$
$\begin{subarray}{c}\centernot\longrightarrow\\\ \longleftarrow\end{subarray}$
$(\textsf{ParityTrace},\mathsf{TV})$ $\downarrow\quad\centernot\uparrow$
$\downarrow\quad\centernot\uparrow$ $(\textsf{LabeledDist},\mathsf{edit})$
$\begin{subarray}{c}\longrightarrow\\\ \longleftarrow\end{subarray}$
$(\textsf{ParityTrace},\mathsf{edit})$

Figure 1: Summary of the relative strengths of testing models and distance
metrics. An arrow $(\mathcal{M}_{1},d_{1})\to(\mathcal{M}_{2},d_{2})$ means
that a tester in model $\mathcal{M}_{1}$ with respect to distance $d_{1}$
implies a tester in model $\mathcal{M}_{2}$ with respect to distance $d_{2}$,
while $\not\to$ means that the implication does not hold in general.

######  Lemma 6.21.

Let $\Xi$ be any density property, and let $\epsilon>0$. Then
$\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))\subseteq\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi(\Xi))$.

###### Proof.

Suppose that $\pi\in\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))$, so that
$\pi=\pi_{f,\mathcal{D}}$ for some
$\mathcal{D}_{f}\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$. Suppose for
contradiction that $\mathsf{dist}_{\mathsf{TV}}(\pi,\pi^{\prime})\leq\epsilon$
for some $\pi^{\prime}=\pi_{g,\mathcal{E}}\in\Pi(\Xi)$. Let
$a_{1}<a_{2}<a_{3}<\dotsm$ be the alternation sequence of $f$, and define
$a_{0}=-\infty$. Then we define the labeled distribution $\mathcal{F}_{f}$ as
follows. Below, we assume without loss of generality that $\mathcal{D}_{f}$ is
1-proper; if it is 0-proper, we require to adjust some of the indices by 1.

For each $i\in\mathbb{N}$, let
$\delta_{i}\vcentcolon=\pi^{\prime}(i)-\sum_{x\in(a_{i-1},a_{i}]}\mathcal{D}(x)$.
If $\delta_{i}\geq 0$, for $x\in(a_{i-1},a_{i}]$, we may obtain $\mathcal{F}$
on interval $(a_{i-1},a_{i}]$ by setting
$\mathcal{F}(z)=\mathcal{D}(z)+\delta$ for an arbitrarily chosen element
$z\in(a_{i-1},a_{i}]$, and then choosing $\mathcal{F}(x)=\mathcal{D}(x)$ for
the remaining $x\neq z$ in this interval.

If $\delta_{i}<0$, we may obtain $\mathcal{F}$ on interval $(a_{i-1},a_{i}]$
by subtracting a total of $|\delta_{i}|$ from the densities $\mathcal{D}(x)$
inside the interval; this is possible, since we must have $\sum_{a_{i-1}<x\leq
a_{i}}\mathcal{D}(x)\geq|\delta_{i}|$.

It is easy to verify that this construction satisfies
$\pi_{f,\mathcal{F}}=\pi^{\prime}=\pi_{g,\mathcal{E}}$. Since $\Xi$ is a
density property, it holds that $\mathcal{F}_{f}\in\Xi$. We can see that

$\displaystyle\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{F}_{f})$
$\displaystyle=\frac{1}{2}\sum_{x}|\mathcal{D}(x)-\mathcal{F}(x)|=\frac{1}{2}\sum_{i}\left(\sum_{a_{i-1}<x\leq
a_{i}}|\mathcal{D}(x)-\mathcal{F}(x)|\right)$
$\displaystyle=\frac{1}{2}\sum_{i}|\delta_{i}|=\mathsf{dist}_{\mathsf{TV}}(\pi,\pi^{\prime})\leq\epsilon\,.$

But this contradicts the assumption that
$\mathcal{D}_{f}\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$. So
$\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))\subseteq\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi(\Xi))$.
∎

Density properties are closed under Boolean operations; in particular, we
require the next fact, which follows by definition.

######  Fact 6.22.

Suppose $\Xi_{1}$ and $\Xi_{2}$ are density properties. Then
$\Xi_{1}\cap\Xi_{2}$ is a density property.

We will show that labeled distribution testing, and distribution testing under
the parity trace, are essentially equivalent for density properties. The first
step is to show that labeled distribution testers for density properties can
always be transformed into a restricted type of tester that ignores the
absolute position of the sample points, and keeps only their labels and their
order. This proof is inspired by one in [DKN15a]. We require some notation.

For any multiset $S\subseteq\mathbb{Z}$ of size $m$, write
$S=\\{x_{1},x_{2},\dotsm,x_{m}\\}$ where we put $x_{1}\leq x_{2}\leq\dotsm\leq
x_{m}$. Then for any $f:\mathbb{Z}\to\\{0,1\\}$, we will write the ordered
sequence of points in $S$ labeled by $f$ as

$S_{f}\vcentcolon=\left((x_{1},f(x_{1})),(x_{2},f(x_{2})),\dotsc,(x_{m},f(x_{m}))\right)\,.$

Then we define

$\mathsf{trace}^{*}(S_{f})\vcentcolon=(f(x_{1}),f(x_{2}),\dotsc,f(x_{k}))\,.$

######  Fact 6.23.

Let $(f,\mathcal{D})$ be any proper labeled distribution. For any $m$, let
$T\sim\mathsf{samp}(\pi_{f,\mathcal{D}},m)$ and
$S\sim\mathsf{samp}(\mathcal{D},m)$. Then the random variables
$\mathsf{trace}^{*}(S_{f})$ and $\mathsf{trace}(T)$ are identically
distributed.

######  Lemma 6.24.

Let $\Xi_{1}$ and $\Xi_{2}$ be any density properties, let $\alpha\in(0,1)$,
and suppose there is an algorithm $A$ and a number $m$ such that:

  1. 1.

If $\mathcal{D}_{f}\in\Xi_{1}$ then
$\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A(S_{f})\text{
accepts }\right]\geq\alpha$; and,

  2. 2.

If $\mathcal{D}_{f}\in\Xi_{2}$ then
$\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A(S_{f})\text{
rejects }\right]\geq\alpha$.

Then for any $\delta>0$, there is an algorithm $A^{\prime}$ satisfying

  1. 1.

If $\mathcal{D}_{f}\in\Xi_{1}$ then
$\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}^{*}(S_{f}))\text{
accepts }\right]\geq\alpha-\delta$; and,

  2. 2.

If $\mathcal{D}_{f}\in\Xi_{2}$ then
$\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}^{*}(S_{f}))\text{
rejects }\right]\geq\alpha-\delta$.

To prove this lemma, we require the infinite Ramsey theorem. For any set $X$
and $n\in\mathbb{N}$, let ${X\choose n}$ denote the set of size $n$ subsets of
$X$.

######  Theorem 6.25 (Infinite Ramsey Theorem [Ram09]).

Fix any $c,n\in\mathbb{N}$ and let $X$ be any countably infinite set. For any
coloring of ${X\choose n}$ by $c$ colors, there exists an infinite set
$Y\subseteq X$ such that sets in ${Y\choose n}$ have the same color.

We may now prove our Lemma 6.24.

###### Proof of Lemma 6.24.

Since $\Xi_{1},\Xi_{2}$ are density properties, they have associated sets of
density sequences $\Pi(\Xi_{1})$ and $\Pi(\Xi_{2})$.

On input $(f,\mathcal{D})$, the algorithm $A$ receives $S_{f}$, where
$S\sim\mathsf{samp}(\mathcal{D},m)$. For each multiset $S\subseteq\mathbb{N}$
of size $m$, the algorithm’s decision on $S_{f}$ can be written as
$A(S_{f})=A_{S}(\mathsf{trace}^{*}(S_{f}))$, where
$A_{S}:\\{0,1\\}^{m}\to\\{0,1\\}$. There are at most $b=2^{2^{m}}$ possible
decision functions. We identify each possible decision function
$\Delta:\\{0,1\\}^{m}\to\\{0,1\\}$ with an element of $[b]$.

For each subset $S\subset\mathbb{N}$ of size $m$, we color $S$ with the
function $A_{S}$, which we have identified with an element of $[b]$. By
Theorem 6.25, there exists an infinite set $N\subset\mathbb{N}$ such that all
$S\subset\mathbb{N}$ of size $m$ have the same color. Then there exists a
decision function $\Delta:\\{0,1\\}^{m}\to\\{0,1\\}$ such that, for each
$S\in{N\choose m}$, $A_{S}=\Delta$.

We now define the algorithm $A^{\prime}$ as follows. On input
$\mathsf{trace}^{*}(S_{f})=(f(x_{1}),f(x_{2}),\dotsc,f(x_{m}))$, $A^{\prime}$
will simply output $\Delta(f(x_{1}),f(x_{2}),\dotsc,f(x_{m}))$. It remains to
show that this algorithm will be correct.

Fix any input $(f,\mathcal{D})$; without loss of generality, we assume
$(f,\mathcal{D})\in\Xi_{1}$, since the analogous argument will hold for
$\Xi_{2}$. Let $a_{1}<a_{2}<a_{3}<\dotsm$ be the alternation sequence for $f$.
We will also assume that $(f,\mathcal{D})$ is 1-proper, since a similar
argument will hold when $(f,\mathcal{D})$ is 0-proper (the difference being
that we would have $\pi_{f,\mathcal{D}}(1)=0$ and
$\pi_{f,\mathcal{D}}(i+1)=\mathcal{D}(a_{i-1},a_{i}]$ instead of
$\pi_{f,\mathcal{D}}(i)=\mathcal{D}(a_{i-1},a_{i}]$).

Choose $C=\lceil m^{2}/\delta\rceil$. Since $N$ is infinite, we may choose a
one-to-one mapping $\gamma:\mathbb{N}\to N\cup\\{\infty\\}$, satisfying

$1<\gamma(a_{1})<\gamma(a_{2})<\dotsm<\gamma(a_{k})<\dotsm\,,$

and define $\gamma(a_{0})=1$ for ease of notation. We may choose $\gamma$ to
satisfy $|N\cap(\gamma(a_{i-1}),\gamma(a_{i})]|\geq C$ for each $i\geq 1$.
Define a distribution $\mathcal{D}^{\prime}$ by assigning value
$\mathcal{D}^{\prime}(x)=\frac{1}{C}\cdot\mathcal{D}(a_{i-1},a_{i}]$ for the
first $C$ elements $x\in N\cap(\gamma(a_{i-1}),\gamma(a_{i})]$, and define the
function $f^{\prime}:\mathbb{Z}\to\\{0,1\\}$ as the unique function with
alternation sequence $\gamma(a_{1})<\gamma(a_{2})<\dotsm$. Observe that, for
each $i\in\mathbb{N}$,

$\pi_{f^{\prime},\mathcal{D}^{\prime}}(i)=\mathcal{D}(\gamma(a_{i-1}),\gamma(a_{i})]=C\cdot\frac{1}{C}\mathcal{D}(a_{i-1},a_{i}]=\pi_{f,\mathcal{D}}(i)\,,$

so $(f^{\prime},\mathcal{D}^{\prime})\in\Xi_{1}$ because $\Xi_{1}$ is a
density property. So

$\alpha\leq\underset{S^{\prime}\sim\mathsf{samp}(\mathcal{D}^{\prime},m)}{\mathbb{P}}\left[A_{S^{\prime}}(\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}}))\text{
accepts }\right]\,.$

We have $\operatorname{supp}(\mathcal{D}^{\prime})\subseteq N$, so
$S^{\prime}\subseteq N$ with probability 1. So, if $S^{\prime}$ is a set of
size $m$ (i.e. each element of the multiset $S$ occurs with multiplicity 1),
then $A_{S^{\prime}}=\Delta$. Let $F(S^{\prime})$ be the event that
$S^{\prime}$ is a set of size $m$. Since each element of $N$ has density at
most $1/C$, the union bound gives

$\underset{S^{\prime}}{\mathbb{P}}\left[\neg
F(S^{\prime})\right]<\frac{m^{2}}{C}\leq\delta\,.$

Then

$\displaystyle\alpha\leq\underset{S^{\prime}}{\mathbb{P}}\left[A_{S^{\prime}}(\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}}))\text{
accepts }\right]$
$\displaystyle\leq\underset{S^{\prime}}{\mathbb{P}}\left[\Delta(\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}}))\text{
accepts }\right]+\underset{S^{\prime}}{\mathbb{P}}\left[\neg
F(S^{\prime})\right]$
$\displaystyle<\underset{S^{\prime}}{\mathbb{P}}\left[\Delta(\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}}))\text{
accepts }\right]+\delta\,.$

Now observe that, for $S\sim\mathsf{samp}(\mathcal{D},m)$, the variables
$\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}})$ and $\mathsf{trace}^{*}(S_{f})$
are identically distributed. So we have

$\alpha-\delta<\underset{S^{\prime}}{\mathbb{P}}\left[\Delta(\mathsf{trace}^{*}(S^{\prime}_{f^{\prime}}))\text{
accepts
}\right]=\underset{S}{\mathbb{P}}\left[\Delta(\mathsf{trace}^{*}(S_{f}))\text{
accepts }\right]\,.$

This concludes the proof, since we may repeat the analogous argument for
$\Xi_{2}$. ∎

We may now establish the general equivalence between labeled distribution
testing and distribution testing under the parity trace. (Note that the second
part of the lemma below does not require that $\Xi_{1}$ and $\Xi_{2}$ are
density properties.)

######  Lemma 6.26.

Let $\Xi_{1}$ and $\Xi_{2}$ be properties of labeled distributions. Then:

  1. 1.

Suppose that $\Xi_{1}$ and $\Xi_{2}$ are density properties. If there is a
$(\Xi_{1},\Xi_{2})$-labeled distribution tester with sample complexity $m$ and
success probability $\alpha$, then for any $\delta>0$ there is a
$(\Pi(\Xi_{1}),\Pi(\Xi_{2}))$-distribution tester under the parity trace, with
sample complexity $m$ and success probability $\alpha-\delta$.

  2. 2.

If there is a $(\Pi(\Xi_{1}),\Pi(\Xi_{2}))$-distribution tester under the
parity trace with sample complexity $m$ and success probability $\alpha$, then
there is a $(\Xi_{1},\Xi_{2})$-labeled distribution tester with sample
complexity $m$ and success probability $\alpha$.

###### Proof.

Suppose there is a $(\Xi_{1},\Xi_{2},\alpha)$-labeled distribution tester $A$,
with sample complexity $m$. By Lemma 6.24, for any $\delta>0$, there is a
tester $A^{\prime}$ such that

$\displaystyle\mathcal{D}_{f}\in\Xi_{1}$
$\displaystyle\implies\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}^{*}(S_{f}))\text{
accepts }\right]>\alpha-\delta$ $\displaystyle\mathcal{D}_{f}\in\Xi_{2}$
$\displaystyle\implies\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}^{*}(S_{f}))\text{
rejects }\right]>\alpha-\delta\,.$

Suppose $\pi\in\Pi(\Xi_{1})$. Then there exists $\mathcal{D}_{f}\in\Xi_{1}$
such that $\pi=\pi_{f,\mathcal{D}}$. Using the fact that $\mathsf{trace}(T)$
and $\mathsf{trace}^{*}(S_{f})$ are identically distributed when
$T\sim\mathsf{samp}(\pi,m)$ and $S\sim\mathsf{samp}(\mathcal{D},m)$ (6.23), we
have

$\underset{T\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}(T))\text{
accepts
}\right]=\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A^{\prime}(\mathsf{trace}^{*}(S_{f}))\text{
accepts }\right]>\alpha-\delta\,.$

The analogous argument holds when $\pi\in\Pi(\Xi_{2})$, which concludes the
first part of the proof.

Now suppose there is a $(\Pi(\Xi_{1}),\Pi(\Xi_{2}))$-distribution tester under
the parity trace, with sample complexity $m$ and success probability $\alpha$,
so there is an algorithm $A$ such that

$\displaystyle\pi\in\Pi(\Xi_{1})$
$\displaystyle\implies\underset{T\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A(T)\text{
accepts }\right]>\alpha$ $\displaystyle\pi\in\Pi(\Xi_{2})$
$\displaystyle\implies\underset{T\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A(T)\text{
rejects }\right]>\alpha\,.$

Suppose that $\mathcal{D}_{f}\in\Xi_{1}$. Then
$\pi_{f,\mathcal{D}}\in\Pi(\Xi_{1})$. Again using the fact that
$\mathsf{trace}^{*}(S_{f})$ and $\mathsf{trace}(T)$ are identically
distributed when $S\sim\mathsf{samp}(\mathcal{D},m)$ and
$T\sim\mathsf{samp}(\pi_{f,\mathcal{D}},m)$ (6.23), we have

$\underset{S\sim\mathsf{samp}(\mathcal{D},m)}{\mathbb{P}}\left[A(\mathsf{trace}^{*}(S_{f}))\text{
accepts
}\right]=\underset{T\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A(\mathsf{trace}(T))\text{
accepts }\right]>\alpha\,.$

The analogous argument holds when $\mathcal{D}_{f}\in\Xi_{2}$, which concludes
the proof. ∎

To introduce the distance metrics into the equivalence, we require:

######  Proposition 6.27.

Let $\Xi$ be any density property and let $\epsilon>0$. Then
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)$ is a density property, and

$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))=\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))\,.$

###### Proof.

It is evident that $\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)$ is a density
property, because
$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),(g,\mathcal{E}))=\mathsf{dist}_{\mathsf{edit}}(\pi_{f,\mathcal{D}},\pi_{g,\mathcal{E}})$
for any labeled distributions $\mathcal{D}_{f}$ and $\mathcal{E}_{g}$, so that
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)$ is defined entirely by the
density sequences.

We first prove
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))\subseteq\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))$.
Let $\pi\in\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))$, so that
$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})>\epsilon$ for all
$\pi^{\prime}\in\Pi(\Xi)$. Suppose for contradiction that
$\pi\notin\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))$. Let
$(f,\mathcal{D})$ be any labeled distribution such that
$\pi_{f,\mathcal{D}}=\pi$. Then
$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),\Xi)\leq\epsilon$, so there
exists $(g,\mathcal{E})\in\Xi$, and $\mathcal{D}^{\prime}_{f^{\prime}}$ with
$\pi_{f,\mathcal{D}}=\pi_{f^{\prime},\mathcal{D}^{\prime}}$, such that
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}^{\prime}_{f^{\prime}},\mathcal{E}_{g})\leq\epsilon$.
But then

$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi(\Xi))\leq\mathsf{dist}_{\mathsf{edit}}(\pi,\pi_{g,\mathcal{E}})=\mathsf{dist}_{\mathsf{edit}}(\pi_{f^{\prime},\mathcal{D}^{\prime}},\pi_{g,\mathcal{E}})\leq\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}^{\prime}_{f^{\prime}},\mathcal{E}_{g})\leq\epsilon\,,$

which is a contradiction. This establishes
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))\subseteq\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))$.

Next, we prove
$\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))$.
Let $\pi\in\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))$, so that
$\pi=\pi_{f,\mathcal{D}}$ for some $(f,\mathcal{D})$ that satisfies
$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),\Xi)>\epsilon$. Suppose for
contradiction that
$\pi\notin\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))$, so that there
exists $\pi^{\prime}\in\Pi(\Xi)$ such that
$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\leq\epsilon$. Then
$\pi^{\prime}=\pi_{g,\mathcal{E}}$ for some $(g,\mathcal{E})\in\Xi$, so

$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),\Xi)\leq\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),(g,\mathcal{E}))=\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\leq\epsilon\,,$

which is a contradiction. This concludes the proof. ∎

We may now establish the arrow
$(\textsf{LabeledDist},\mathsf{edit})\to(\textsf{ParityTrace},\mathsf{edit})$
from Figure 1.

######  Lemma 6.28.

Let $\Xi$ be any density property and suppose there is a
$(\Xi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi),\alpha)$-labeled
distribution tester with sample complexity $m$. Then for any $\delta>0$, there
is a
$(\Pi(\Xi),\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi)),\alpha-\delta)$-distribution
tester under the parity trace, with sample complexity $m$.

###### Proof.

By Proposition 6.27, $\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)$ is a
density property. Therefore Lemma 6.26 yields a
$(\Pi(\Xi),\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)),\alpha-\delta)$-distribution
tester under the parity trace, for any $\delta>0$, with sample complexity $m$.
By Proposition 6.27, we obtain a
$(\Pi(\Xi),\textsc{far}_{\epsilon}^{\mathsf{edit}}(\Pi(\Xi)),\alpha-\delta)$-distribution
tester under the parity trace. ∎

The following simple fact establishes
$(\textsf{LabeledDist},\mathsf{TV})\to(\textsf{LabeledDist},\mathsf{edit})$
from Figure 1.

######  Fact 6.29.

Let $\Xi$ be any property of (proper) labeled distributions, and let
$\epsilon>0$. Then
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi)\subseteq\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$.

###### Proof.

This follows from the inequality
$\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),(g,\mathcal{E}))\leq\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})$
for any two proper labeled distributions $\mathcal{D}_{f}$ and
$\mathcal{E}_{g}$. ∎

We now state a convenient lemma for later use.

######  Lemma 6.30.

Let $\Xi$ be any density property and suppose there is a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),\alpha)$-labeled distribution
tester with sample complexity $m$. Then for any $\delta>0$, there is a
$(\Pi(\Xi),\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi)),\alpha-\delta)$-distribution
tester under the parity trace, with sample complexity $m$.

The arrow
$(\textsf{ParityTrace},\mathsf{edit})\rightarrow(\textsf{LabeledDist},\mathsf{edit})$
is proved as follows. Suppose we have a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi),\alpha)$-distribution
tester under the parity trace. Let $\Xi=\Xi(\Pi)$ be the corresponding density
property, so that $\Pi=\Pi(\Xi)$. By Proposition 6.27,
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi))=\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi))$,
and thus by Lemma 6.26 we have a
$(\Xi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi),\alpha)$-labeled
distribution tester.

The arrow
$(\textsf{ParityTrace},\mathsf{TV})\rightarrow(\textsf{LabeledDist},\mathsf{TV})$
is similar. Suppose we have a
$(\Pi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi),\alpha)$-distribution tester
under the parity trace. Let $\Xi=\Xi(\Pi)$ be the corresponding density
property, so that $\Pi=\Pi(\Xi)$. By Lemma 6.21,
$\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))\subseteq\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi(\Xi))$,
so we get a
$(\Pi(\Xi),\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)),\alpha)$-distribution
tester under the parity trace. By Lemma 6.26 we have a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),\alpha)$-labeled distribution
tester.

###  6.6 Testing Uniformly $k$-Alternating Functions

We now prove our main result for labeled distribution testing, restated below
for convenience, which is an application of our main Theorem 1.1. First, we
observe that the edit and TV distances coincide when one of the distributions
is uniform; we defer the proof to Section D.4.

######  Lemma 6.31.

There exists an absolute constant $c>0$ such that the following holds. Let
$\pi$ be the distribution over $\mathbb{N}$ that is uniformly supported on
$[k]$, and $\pi^{\prime}$ be another probability distribution over
$\mathbb{N}$ supported within $[k]$. Then
$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\geq
c\cdot\mathsf{dist}_{\mathsf{TV}}(\pi,\pi^{\prime})$.

######  Remark 6.32.

The statement of our main Theorem 1.1 leaves open the possibility of a
uniformity tester under the parity trace, with respect to the _edit distance_
, that beats the lower bound of that theorem. This is because an edit distance
tester is weaker than a TV distance tester, due to inequality (19). The above
lemma shows that we may strengthen the lower bound in Theorem 1.1 to hold for
testers in the edit distance as well.

######  Theorem 6.33.

Let $\Xi_{1}$ be the uniformly $2k$-alternating labeled distributions, and let
$\Xi_{2}$ be the $2k$-alternating labeled distributions that are
$\epsilon$-far in total variation distance from $\Xi_{1}$. Then the sample
complexity of $(\Xi_{1},\Xi_{2},2/3)$-labeled distribution testing is
$\widetilde{\Theta}\left(\frac{k^{4/5}}{\epsilon^{4/5}}+\frac{\sqrt{k}}{\epsilon^{2}}\right)$.

###### Proof of upper bound.

Let $K$ be the property of $2k$-alternating labeled distributions, which is a
density property, with $\Pi(K)$ being the property of density sequences
supported on $[2k]$. Then
$\Xi_{2}=\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1})\cap K$ and
$\Pi(\Xi_{2})=\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1})\cap
K)=\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1}))\cap\Pi(K)$, while
$\Pi(\Xi_{1})$ contains only the uniform distribution $\mu$ supported on
$[2k]$. By Lemma 6.21,
$\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1}))\subseteq\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi(\Xi_{1}))$.
Therefore, a
$(\Pi(\Xi_{1}),\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi(\Xi_{1}))\cap\Pi(K),\alpha)$-distribution
tester under the parity trace, with sample complexity $m$, is also a
$(\Pi(\Xi_{1}),\Pi(\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1})\cap
K),\alpha)$-distribution tester under the parity trace, with sample complexity
$m$. The conclusion now follows from Lemma 6.26. ∎

###### Proof of lower bound.

We begin with a specialized variant of the argument from Lemma 6.28. Suppose
there is a $(\Xi_{1},\Xi_{2},2/3)$-labeled distribution tester with sample
complexity $m$, and recall that
$\Xi_{2}=\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi_{1})\cap K$. By 6.29, we
have
$\textsc{far}^{\mathsf{edit}}(\Xi_{1})\subseteq\textsc{far}^{\mathsf{TV}}(\Xi_{1})$,
so this is also a
$(\Xi_{1},\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1})\cap K,2/3)$-labeled
distribution tester. By Proposition 6.27,
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1})$ is a density property, so
by 6.22, $\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1})\cap K$ is a density
property. From Lemma 6.26, we then obtain a
$(\Pi(\Xi_{1}),\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1})\cap
K),2/3-\delta)$-distribution tester under the parity trace, for any
$\delta>0$, with sample complexity $m$. Observe that
$\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1})\cap
K)=\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi_{1}))\cap\Pi(K)$. By
Proposition 6.27, we have a
$(\Pi(\Xi_{1}),\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi_{1}))\cap\Pi(K),2/3-\delta)$-distribution
tester under the parity trace.

Note that $\Pi(\Xi_{1})=\\{\mu\\}$, where $\mu$ is the uniform distribution
supported on $[2k]$. Let $0<c<1$ be the constant from Lemma 6.31, and consider
any distribution
$\pi\in\textsc{far}^{\mathsf{TV}}_{\epsilon/c}(\Pi(\Xi_{1}))$. Then by Lemma
6.31, we have

$\mathsf{dist}_{\mathsf{edit}}(\pi,\mu)\geq
c\cdot\mathsf{dist}_{\mathsf{TV}}(\pi,\mu)>c\cdot(\epsilon/c)=\epsilon\,,$

so $\pi\in\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi_{1}))$. Then
$\textsc{far}^{\mathsf{TV}}_{\epsilon/c}(\Pi(X_{1}))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi(\Xi_{1}))$.

Therefore, our tester is also a
$(\Pi(\Xi_{1}),\textsc{far}^{\mathsf{TV}}_{\epsilon/c}(\Pi(\Xi_{1}))\cap\Pi(K),2/3-\delta)$-distribution
tester under the parity trace, with sample complexity $m$. By
LABEL:thm:lower_bound, we must have the desired lower bound of

$m=\widetilde{\Omega}\left(\left(\frac{n}{\epsilon}\right)^{4/5}+\frac{\sqrt{n}}{\epsilon^{2}}\right)\,.\qed$

###  6.7 Promise-Free Testing $k$-Alternating and Uniformly $k$-Alternating
Functions

Theorem 1.1 proves a tight bound on testing whether a distribution supported
on $[k]$ is uniform, under the parity trace. We use testing-by-learning to
prove a bound on the harder problem of testing whether a distribution is
uniform on $[k]$, _without_ the promise that the input is supported on $[k]$.

######  Theorem 6.34.

Fix domain $\mathbb{N}$. Let $\Pi$ contain only the uniform distribution over
$[k]$. There is a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi),2/3)$-distribution tester
under the parity trace, with sample complexity
$O\left(\frac{k}{\epsilon}+\frac{k}{\epsilon^{2}\log k}\right)$.

This will follow from the next lemma, using fact that $\Pi=\Pi(\Xi)$, where
$\Xi$ is the property of uniformly $k$-alternating labeled distributions,
together with Lemma 6.30.

######  Lemma 6.35.

Let $\Xi$ be the uniformly $k$-alternating functions. Then there is a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),2/3)$-labeled distribution
tester with sample complexity
$O\left(\frac{k}{\epsilon}+\frac{k}{\epsilon^{2}\log k}\right)$.

###### Proof.

Let $c\in(0,1)$ be the universal constant in Lemma 6.31. We will construct a
learner-verifier pair. Let $A$ be the standard PAC learning algorithm for the
class of $k$-alternating functions, with error $c\epsilon/4$. This algorithm,
using a sample of size $m_{A}=O(k/\epsilon)$, outputs a $k$-alternating
function $g:\mathbb{Z}\to\\{0,1\\}$, such that with probability at least
$8/9$,

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})=\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)\neq
g(x)\right]<c\epsilon/4\,,$

where the equality is due to D.1. It is clear that there exists a distribution
$\mathcal{E}$ such that $\mathcal{E}_{g}\in\Xi$.

Suppose that $(f,\mathcal{D})\in\Xi$. We must show that there exists a
distribution $\mathcal{E}$ such that $\mathcal{E}_{g}\in\Xi$ and
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})\leq\epsilon/4$. Let
$\mu$ be the uniform distribution over $[k+1]$. Using Proposition D.2, we
obtain $\mathcal{E}$ such that

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{g},\mathcal{E}_{g})=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\pi_{g,\mathcal{E}})=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\mu)\,.$

Using $\pi_{g,\mathcal{E}}=\mu=\pi_{f,\mathcal{D}}$ and Lemma 6.31, we have

$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\pi_{g,\mathcal{E}})=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\pi_{f,\mathcal{D}})\leq\frac{1}{c}\cdot\mathsf{dist}_{\mathsf{edit}}(\pi_{g,\mathcal{D}},\pi_{f,\mathcal{D}})\leq\frac{1}{c}\cdot\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{g},\mathcal{D}_{f})\,,$

where the last inequality holds by definition. Then

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D},\mathcal{E})=\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{g},\mathcal{E}_{g})\leq\frac{1}{c}\cdot\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{g},\mathcal{D}_{f})\leq\epsilon/4\,.$

So algorithm $A$ satisfies the conditions for the learner-verifier pair. It
remains to construct the verifier $B$. Let $g:\mathbb{Z}\to\\{0,1\\}$ be any
possible output of the learner, which must be a $k$-alternating function. Then
$\Pi_{g}$ is the set of all distributions $\mathcal{E}$ such that
$\pi_{g,\mathcal{E}}=\mu$, where $\mu$ is the uniform distribution over
$[k+1]$. Define the algorithm $B_{g}$ as follows:

  1. 1.

Sample $S\sim\mathsf{samp}(\mathcal{D},m_{B})$ and construct the multiset
$S^{\prime}$ by taking each $x\in S$ and including the number $i\in[k+1]$ in
$S^{\prime}$, where $i$ is the unique interval $(a_{i-1},a_{i}]$ that contains
$x$. Then $S^{\prime}$ is distributed as
$\mathsf{samp}(\pi_{g,\mathcal{D}},m_{B})$.

  2. 2.

Use an $(\epsilon/4,\epsilon/2)$-tolerant uniformity tester on sample
$S^{\prime}$ to test if
$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\mu)<\epsilon/4$ or
$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{D}},\mu)>\epsilon/2$. This step
requires $m_{B}=O\left(\frac{k}{\epsilon^{2}\log k}\right)$ samples [VV17b].

Suppose that
$\mathcal{E}\in\textsc{close}^{\mathsf{TV}}_{\epsilon/4}(\Pi_{g})$, so there
exists $\mathcal{F}$ such that $\pi_{g,\mathcal{F}}=\mu$ and
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{E}_{g},\mathcal{F}_{g})<\epsilon/4$.
Then

$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\mu)=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\pi_{g,\mathcal{F}})\leq\mathsf{dist}_{\mathsf{TV}}(\mathcal{E}_{g},\mathcal{F}_{g})<\epsilon/4\,,$

so the tolerant uniformity tester will accept.

Now suppose that
$\mathcal{E}\in\textsc{far}^{\mathsf{TV}}_{\epsilon/2}(\Pi_{g})$. For
contradiction, suppose that

$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\mu)\leq\epsilon/2\,.$

Using Proposition D.2, we obtain $\mathcal{F}$ such that
$\pi_{g,\mathcal{F}}=\mu$ (so $\mathcal{F}\in\Pi_{g}$), and

$\mathsf{dist}_{\mathsf{TV}}(\mathcal{E}_{g},\mathcal{F}_{g})=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\pi_{g,\mathcal{F}})=\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\mu)\leq\epsilon/2\,.$

This contradicts
$\mathcal{E}\in\textsc{far}^{\mathsf{TV}}_{\epsilon/2}(\Pi_{g})$, so it must
be the case that
$\mathsf{dist}_{\mathsf{TV}}(\pi_{g,\mathcal{E}},\mu)>\epsilon/2$. Then the
tolerant uniformity tester will correctly reject. ∎

We also note that the no-promise problem of testing the $k$-alternating
labeled distributions inherits an upper bound of $O(k/\epsilon)$ from the
equivalence to distribution-free sample-based testing:

######  Lemma 6.36.

Let $\Xi$ be the set of labeled distributions $(f,\mathcal{D})$ such that $f$
is a $k$-alternating function and $\mathcal{D}$ is any distribution over
$\mathbb{Z}$. Let $m(k,\epsilon)$ be the optimal sample complexity of a
distribution-free sample-based tester for $k$-alternating functions. Then the
optimal sample complexity of
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi))$-labeled distribution
testing is $\Theta(m(k,\epsilon))$. In particular, there is such a tester with
sample complexity $O(k/\epsilon)$.

###### Proof.

The first part of the statement follows from Proposition 6.15. The second part
follows from standard PAC learning theory, since the class of $k$-alternating
functions has VC dimension $k+1$, along with the testing by learning reduction
[GGR98]. ∎

As with the previous result, this lemma implies a bound for testing the
_support size_ of distributions under the parity trace; this is the starting
point for our next discussion, on the connections between distribution testing
under the parity trace and distribution-free sample based testing.

###  6.8 Distribution-Free Sample-Based Property Testing

We now prove that testing support size $k$ under the parity trace is
equivalent to testing $k$-alternating functions in the standard distribution-
free sample-based model (whose optimal sample complexity is unknown [BFH21]).
This has the interesting consequence, in Lemma 6.43, that an improved lower
bound on testing support size under the parity trace could give a better lower
bound for testing halfspaces in the distribution-free sample-based model.

We require the following proposition about edit distance, which is proved in
Section D.5.

######  Proposition 6.37.

Let $\Xi$ be the property of proper labeled distributions $(g,\mathcal{E})$
where $\pi_{g,\mathcal{E}}$ has support size at most $k$. Then for any proper
labeled distribution $(f,\mathcal{D})$,
$\mathsf{dist}_{\mathsf{TV}}((f,\mathcal{D}),\Xi)\leq\mathsf{dist}_{\mathsf{edit}}((f,\mathcal{D}),\Xi)$.

######  Theorem 6.38.

Let $\Pi$ be the class of distributions on domain $\mathbb{N}$ with support
size at most $k$. Let $m_{1}(k,\epsilon)$ be the optimal sample complexity of
a $(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi),2/3)$-distribution tester
under the parity trace, and let $m_{2}(k,\epsilon)$ be the optimal sample
complexity of a distribution-free sample-based tester for $k$-alternating
functions. Then $m_{1}(k,\epsilon)=\Theta(m_{2}(k,\epsilon))$.

###### Proof of first direction.

We wish to construct a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi),2/3)$-distribution tester
under the parity trace, with sample complexity $O(m_{2}(k,\epsilon))$. Let
$\Xi$ be the set of labeled distributions $(f,\mathcal{D})$ such that $f$ is a
$(k-1)$-alternating function and $\mathcal{D}$ is any distribution over
$\mathbb{Z}$. Let $\Xi^{\prime}$ be the set of labeled distributions
$(f,\mathcal{D})$ on domain $\mathbb{Z}$ such that $\pi_{f,\mathcal{D}}$ has
support size at most $k$, so that $\Pi(\Xi^{\prime})=\Pi$. Lemma 6.36 gives a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),3/4)$-labeled distribution
tester with sample complexity $O(m_{2}(k,\epsilon))$. We will construct a
$(\Xi^{\prime},\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime}),3/4)$-labeled
distribution tester with sample complexity $O(m_{2}(k,\epsilon))$, from which
the conclusion will hold by Lemma 6.30.

Observe that $\Xi\subset\Xi^{\prime}$ since for any $(k-1)$ alternating
function $f$ and any distribution $\mathcal{D}$, $\pi_{f,\mathcal{D}}$ has
support size at most $k$. We show that for any labeled distribution
$(f,\mathcal{D})\in\Xi^{\prime}$, there exists a labeled distribution
$(g,\mathcal{D})\in\Xi$ such that
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})=0$, so that
$\mathcal{D}_{f}=\mathcal{D}_{g}$. Let $a_{1}<a_{2}<\dotsm$ be the alternation
sequence for $f$, and use the convention $a_{0}=-\infty$. Since
$\pi_{f,\mathcal{D}}$ has support size at most $k$, there are at most $k$
intervals $(a_{i-1},a_{i}]$ such that $\mathcal{D}(a_{i-1},a_{i}]>0$.
Construct $g$ by assigning $g(x)=1-f(x)$ for all $x$ belonging to any interval
$(a_{i-1},a_{i}]$ that satisfies $\mathcal{D}(a_{i-1},a_{i}]=0$. By D.4, we
have $\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{D}_{g})=0$. The
resulting function has at most $k-1$ alternation points, so
$(g,\mathcal{D})\in\Xi$.

Suppose $(f,\mathcal{D})\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$ and
suppose for contradiction that there is $(g,\mathcal{E})\in\Xi^{\prime}$ such
that
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\leq\epsilon$.
Then there is $(g^{\prime},\mathcal{E}^{\prime})\in\Xi$ such that
$\mathcal{E}^{\prime}_{g^{\prime}}=\mathcal{E}_{g}$, so
$\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}^{\prime}_{g^{\prime}})=\mathsf{dist}_{\mathsf{TV}}(\mathcal{D}_{f},\mathcal{E}_{g})\leq\epsilon$,
and $(f,\mathcal{D})\notin\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)$, a
contradiction. So
$(f,\mathcal{D})\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime})$. Then
$\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi)=\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime})$.

Then any $(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),3/4)$-labeled
distribution tester is also a
$(\Xi^{\prime},\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime}),3/4)$-labeled
distribution tester, since samples from elements of $\Xi$ are
indistinguishable from samples from elements of $\Xi^{\prime}$. ∎

###### Proof of second direction.

We wish to construct a
$(\Xi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi),2/3)$-labeled distribution
tester; then the conclusion will follow from Proposition 6.15.

As shown in the upper bound argument, this is equivalent to a
$(\Xi^{\prime},\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime}),2/3)$-labeled
distribution tester, where $\Xi^{\prime}$ is the class of labeled
distributions $(f,\mathcal{D})$ where $\pi_{f,\mathcal{D}}$ has support size
at most $k$. Note that $\Pi=\Pi(\Xi^{\prime})$.

By Proposition 6.37,
$\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Xi^{\prime})=\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi^{\prime})$,
so this is equivalent to a
$(\Xi^{\prime},\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi^{\prime}),2/3)$-labeled
distribution tester. Since $\Xi^{\prime}$ and
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi^{\prime})$ are density
properties, it suffices to obtain a
$(\Pi(\Xi^{\prime}),\Pi(\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Xi^{\prime})),2/3)$-distribution
tester under the parity trace, due to Lemma 6.26. Finally, apply Proposition
6.27. ∎

The above theorem relates the sample complexity of testing $k$-alternating
functions to the complexity of testing support size under the parity trace,
with respect to the edit distance. From here, we will reproduce the result of
[BFH21], that testing $k$-alternating functions requires $\Omega(k/\log k)$
samples, which will follow from the $\Omega(n/\log n)$ lower bound for
estimating support size, due to [VV11, WY19]. We use the following formulation
of the result of [VV11]:

######  Theorem 6.39 ([VV11]).

For any sufficiently small constant $\delta>0$, there exists a pair of
distributions $\pi^{+},\pi^{-}$ whose non-zero densities are at least
$\frac{1}{n}$, such that $\pi^{+}$ has support size at least $(1-\delta)n$,
$\pi^{-}$ has support size at most $(1+\delta)\frac{n}{2}$, and distinguishing
between them requires $\Omega\left(\frac{n}{\log n}\right)$ samples.

Their result also applies to estimating the _entropy_ of distributions, in
which case they obtain an $\Omega(n/\epsilon\log n)$ lower bound by
constructing distributions $\pi^{+}_{\epsilon},\pi^{-}_{\epsilon}$ that with
probability $\epsilon$ draw from $\pi^{+},\pi^{-}$ respectively, and otherwise
draw an element $\bot$; this shrinks the entropy gap to an $\epsilon$ fraction
of the original gap, and distinguishing between $\pi^{+}_{\epsilon}$ and
$\pi^{-}_{\epsilon}$ requires an $\frac{1}{\epsilon}$ fraction more samples.
While this argument does not apply to the support size estimation problem,
which requires that densities be lower bounded by $1/n$, it does apply to
testing support size against TV distance:

######  Corollary 6.40.

Let $\Pi$ be the set of distributions over $\mathbb{N}$ with support size at
most $n$, and let $\epsilon>0$. Then any
$(\Pi,\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi))$-distribution tester
requires sample size at least $\Omega\left(\frac{n}{\epsilon\log n}\right)$.

To apply this lower bound, we reduce from testing with respect to TV distance,
to testing with respect to the edit distance. We require the following lemma,
whose proof we defer to Section D.6.

######  Lemma 6.41.

Let $k\in\mathbb{N}$. Let $\Pi_{k}$ be the set of distributions over
$\mathbb{N}$ supported on at most $k$ elements, and let $\Pi_{2k}$ be the set
of distributions over $\mathbb{N}$ supported on at most $2k$ elements. Let
$\pi$ be a finitely-supported probability distribution over $\mathbb{N}$, and
let $\pi^{\prime}$ be the probability distribution over $\mathbb{N}$ given by
$\pi^{\prime}(2i-1)=\pi^{\prime}(2i)\vcentcolon=\pi(i)/2$ for each
$i\in\operatorname{supp}(\pi)$. Then
$\mathsf{dist}_{\mathsf{edit}}(\pi^{\prime},\Pi_{2k})\geq\frac{1}{4}\cdot\mathsf{dist}_{\mathsf{TV}}(\pi,\Pi_{k})$.

We may now establish the simple reduction.

######  Lemma 6.42.

Let $\Pi_{2k}$ be the set of distributions on domain $\mathbb{N}$ with support
size at most $2k$, and let $\epsilon>0$. Then the sample complexity of a
$(\Pi_{2k},\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi_{2k}))$-distribution
tester is at least $\Omega\left(\frac{k}{\epsilon\log k}\right)$.

###### Proof.

Let $\Pi_{k}$ be the set of distributions on domain $\mathbb{N}$ with support
size at most $k$. We will reduce
$(\Pi_{k},\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi_{k}))$-distribution
testing to
$(\Pi_{2k},\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi_{k}))$-distribution
testing, from which the conclusion follows, due to Corollary 6.40.

On input distribution $\pi$, the algorithm proceeds as follows. We define the
distribution $\pi^{\prime}$ where for each $i\in\mathbb{N}$,
$\pi^{\prime}(2i)\vcentcolon=\pi(i)/2$ and
$\pi^{\prime}(2i-1)\vcentcolon=\pi(i)/2$. The algorithm may simulate a sample
from $\pi^{\prime}$ by sampling $\bm{i}\sim\pi$ and then taking $2\bm{i}$ or
$2\bm{i}-1$ with equal probability. The algorithm then simulates the
$(\Pi_{2k},\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi_{2k}))$-distribution
tester on input $\pi^{\prime}$. If $\pi\in\Pi_{k}$, then it is clear that
$\pi^{\prime}\in\Pi_{2k}$, so the algorithm will correctly accept (with
probability at least $2/3$). If
$\pi\in\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi_{k})$, then by Lemma 6.41,
$\pi^{\prime}\in\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi_{2k})$, so the
algorithm will correctly reject (with probability at least $2/3$). ∎

We are now prepared to recover a number of the results of [BFH21] for testing
properties with domain $\mathbb{R}^{n}$, including halfspaces, intersections
of halfspaces, and decision trees. The idea is to reduce from testing
$k$-alternating functions to testing the property in question, by taking the
one-dimensional space and embedding it into $\mathbb{R}^{n}$ in an appropriate
way. This technique was also used in [ES20, BFH21]. We provide a formal proof
for halfspaces, and refer to [BFH21] for the details on intersections of
halfspaces and decision trees.

######  Lemma 6.43.

Let $\Pi$ be the property of distributions on $\mathbb{N}$ with support size
at most $k$. For any $d$ and $\epsilon>0$, let $h(d,\epsilon)$ be the sample
complexity of testing _halfspaces_ on domain $\mathbb{R}^{d}$, in the
distribution-free sample-based model.Then there is a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi),2/3)$-distribution tester
under the parity trace, with sample complexity $O(h(k+1,\epsilon))$.

###### Proof.

This follows from Theorem 6.38 and the following reduction from testing
$k$-alternating functions to testing halfspaces.

On input $f:\mathbb{Z}\to\\{0,1\\}$ and distribution $\mathcal{D}$ over
$\mathbb{Z}$, consider the one-to-one function
$\psi(x)\vcentcolon=(1,x,x^{2},\dotsc,x^{k})$ and the distribution
$\psi\mathcal{D}$ defined as the distribution over $\psi(x)$ where
$x\sim\mathcal{D}$. The tester will simulate the halfspace tester on samples
$(\psi(x),f(x))$ where $(x,f(x))\sim\mathcal{D}_{f}$.

Note that a function $f:\mathbb{Z}\to\\{0,1\\}$ is $k$-alternating if and only
if there exists a degree $k$ polynomial $p:\mathbb{Z}\to\mathbb{R}$ such that
$f(x)=\operatorname{sign}(p(x))$, where we define $\operatorname{sign}(z)=0$
of $z\leq 0$ and $\operatorname{sign}(z)=1$ if $z>0$. Then $f$ is
$k$-alternating if and only if there exists
$w=(w_{0},w_{1},\dotsc,w_{k})\in\mathbb{R}^{k+1}$ such that
$f(x)=\operatorname{sign}(\langle w,\psi(x)\rangle)$. So $f$ is
$k$-alternating if and only if there exists a halfspace
$g:\mathbb{R}^{k+1}\to\\{0,1\\}$ such that $f(x)=g(\phi(x))$ on all $x$.

Write $\psi(\mathcal{D}_{f})$ for the distribution of $(\psi(x),f(x))$ when
$x\sim\mathcal{D}$. So for any $k$-alternating function $f$, there exists a
halfspace $g$ such that $\psi(\mathcal{D}_{f})=(\psi\mathcal{D})_{g}$. On the
other hand, for any halfspace $g$, there exists a $k$-alternating function $f$
such that $\psi(\mathcal{D}_{f})=(\psi\mathcal{D})_{g}$.

Then, for any $k$-alternating function $f$ and distribution $\mathcal{D}$,
samples from $\psi(\mathcal{D}_{f})$ are indistinguishable from samples from
$(\psi\mathcal{D})_{g}$, where $g$ is a halfspace, so a halfspace tester will
accept. On the other hand, for any function $f$ that is $\epsilon$-far from
$k$-alternating under distribution $\mathcal{D}$, consider an arbitrary
function $f^{\prime}:\mathbb{R}^{k+1}\to\\{0,1\\}$ such that
$f^{\prime}(\psi(x))=f(x)$ on all $x\in\mathbb{Z}$, so
$(\psi\mathcal{D})_{f^{\prime}}=\psi(\mathcal{D}_{f})$, so halfspace tester
will perform identically on the simulated samples $(\psi(x),f(x))$ as on the
samples $(z,f^{\prime}(z))\sim(\psi\mathcal{D})_{f^{\prime}}$, so the tester
performs as if it was given input $f^{\prime}$ and $\psi\mathcal{D}$.

If there exists a halfspace $g$ such that
$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f^{\prime}(\psi(x))=g(\psi(x))\right]\leq\epsilon$,
then
$\underset{x\sim\mathcal{D}}{\mathbb{P}}\left[f(x)=g(\psi(x))\right]\leq\epsilon$,
where $g(\psi(\cdot))$ is $k$-alternating, which is a contradiction. So it
must be that $f^{\prime}$ is $\epsilon$-far from being a halfspace with
respect to $\psi\mathcal{D}$, so the halfspace tester rejects $f^{\prime}$. ∎

With this reduction, together with the lower bound provided by Lemma 6.42, we
recover the following bounds. Note that [BFH21] only stated their bounds for
constant $\epsilon$, but the amplification argument above could also be
applied directly to their results.

######  Corollary 6.44 (See [BFH21]).

The following lower bounds hold for the sample complexity of testing in the
distribution-free sample-based model:

  1. 1.

$k$-Alternating functions over $\mathbb{R}$:
$\Omega\left(\frac{k}{\epsilon\log k}\right)$;

  2. 2.

Halfspaces over $\mathbb{R}^{n}$: $\Omega\left(\frac{n}{\epsilon\log
n}\right)$;

  3. 3.

Intersections of $k$ halfspaces over $\mathbb{R}^{n}$:
$\Omega\left(\frac{nk}{\epsilon\log(nk)}\right)$;

  4. 4.

Size $k$ decision trees over $\mathbb{R}^{n}$:
$\Omega\left(\frac{k}{\epsilon\log k}\right)$.

##  7 Property Testing in the Trace Reconstruction Model

We begin by formally defining property testing in the trace reconstruction
model. We then discuss the connection between the (relative) edit distance on
strings and the edit distance on distributions that we introduced, which will
be a crucial component of our results.

For a string $x\in\\{0,1\\}^{N}$ and retention rate $\rho\in(0,1)$,
$\mathsf{del}(x,\rho)$ is the distribution of substrings of $x$ obtained by
deleting each character of $x$ independently with probability $1-\rho$. A
sample $\bm{T}\sim\mathsf{del}(x,\rho)$ is called a _trace_ from $x$ with
deletion rate $1-\rho$.

######  Definition 7.1 (Trace Testing).

Let $\Psi_{1}$ and $\Psi_{2}$ be properties of strings in $\\{0,1\\}^{N}$, and
let $\alpha,\rho\in(0,1)$, which we call the _success probability_ and
_retention rate_ , respectively. A _$(\Psi_{1},\Psi_{2},\rho,\alpha)$ -trace
testing algorithm using $m$ traces_ is an algorithm $A$ such that, for $m$
independent traces $\bm{T}_{1}(x),\dotsc,\bm{T}_{m}(x)$ obtained from $x$ with
deletion rate $1-\rho$,

  1. 1.

If $x\in\Psi_{1}$ then
$\mathbb{P}\left[A(\bm{T}_{1}(x),\dotsc,\bm{T}_{m}(x))\text{ accepts
}\right]\geq\alpha$; and,

  2. 2.

If $x\in\Psi_{2}$ then
$\mathbb{P}\left[A(\bm{T}_{1}(x),\dotsc,\bm{T}_{m}(x))\text{ rejects
}\right]\geq\alpha$.

Many of our results refer to $n$-block strings and uniform $n$-block strings,
which we now define.

######  Definition 7.2.

Fix $N\in\mathbb{N}$. We say $x\in\\{0,1\\}^{N}$ is an _$n$ -block string_ if
$x$ consists of at most $n$ blocks, where a block is an all-1s string or
all-0s string. For integer $n$ that divides $N$, the _1-uniform $n$-block
string_ is $1^{N/n}0^{N/n}1^{N/n}\dotsm\mathsf{par}(n)^{N/n}$ and the
_0-uniform $n$-block string_ is
$0^{N/n}1^{N/n}0^{N/n}\dotsm(1-\mathsf{par}(n))^{N/n}$. We say that $x$ is a
_uniform $n$-block string_ if it is the 1-uniform or 0-uniform $n$-block
string.

######  Definition 7.3 (Relative Edit Distance).

Writing $\mathsf{dist}_{\mathsf{string-
edit}}:\\{0,1\\}^{*}\times\\{0,1\\}^{*}\to\mathbb{Z}$ for the edit distance on
strings, we define the _relative_ string edit distance on strings
$x\in\\{0,1\\}^{N}$ and $y\in\\{0,1\\}^{M}$ as

$\mathsf{dist}_{\mathsf{rel-
edit}}(x,y)=\frac{2}{N+M}\mathsf{dist}_{\mathsf{string-edit}}(x,y)\,.$

We define a correspondence between strings and probability distributions,
which allow us to relate property testing for trace reconstruction to
distribution testing under the parity trace.

######  Definition 7.4 (String to Distribution Correspondence).

For any fixed $N\in\mathbb{N}$ and probability distribution $\pi$ over
$\mathbb{N}$, whose densities are integer multiples of $1/N$, we define the
string $\psi(\pi)\in\\{0,1\\}^{N}$ as

$\psi(\pi)\vcentcolon=1^{\pi(1)\cdot N}0^{\pi(2)\cdot N}1^{\pi(3)\cdot
N}0^{\pi(3)\cdot N}\dotsm\,,$

where $b^{k}$ denotes the character $b$ repeated $k$ times. This map is not
one-to-one. But, for strings $x\in\\{0,1\\}^{N}$, we define a probability
distribution $\psi^{-1}(x)$ as follows. Define the function
$f_{x}:\mathbb{N}\to\\{0,1\\}$ as $f_{x}(i)=x_{i}$ for each $i\in[N]$ (and 1
elsewhere), and let $\mathcal{D}$ be the uniform distribution over $[N]$. Then

$\psi^{-1}(x)\vcentcolon=\pi_{f_{x},\mathcal{D}}\,.$

One may verify that $\psi(\psi^{-1}(x))=x$ for any string $x\in\\{0,1\\}^{N}$.
To each property $\Psi$ of strings in $\\{0,1\\}^{N}$, we associate the
property of probability distributions
$\Pi=\Pi(\Psi)\vcentcolon=\\{\psi^{-1}(x):x\in\Psi\\}$, with $\psi^{-1}$ as
defined in Definition 7.4. For any such $\Psi$, let
$\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi)$ denote the set of strings
$x\in\\{0,1\\}^{N}$ such that $\mathsf{dist}_{\mathsf{rel-
edit}}(x,\Psi)>\epsilon$, where

$\mathsf{dist}_{\mathsf{rel-
edit}}(x,\Psi)\vcentcolon=\min_{y\in\Psi}\mathsf{dist}_{\mathsf{rel-
edit}}(x,y)\,.$

######  Observation 7.5.

If $x$ is an $n$-block string, then $\psi^{-1}(x)$ is supported on at most $n$
elements. If $x$ is the 1-uniform $n$-block string, then $\psi^{-1}(x)$ is the
uniform distribution over $\\{1,2,\dotsc,n\\}$. If $x$ is the 0-uniform
$n$-block string, then $\psi^{-1}(x)$ is the uniform distribution over
$\\{2,3,\dotsc,n+1\\}$.

Recall that we have defined the edit distance on distributions as the natural
metric for distribution testing under the parity trace. The next lemma shows
that the edit distance for distributions is essentially equivalent to the
relative edit distance on strings, under the string-to-distribution
correspondence. This will allow us to obtain equivalences between distribution
testing under the parity trace, and property testing for trace reconstruction.
We defer the proof to Section D.3.

######  Lemma 7.6.

Fix any $N$ and let $\pi,\pi^{\prime}$ be probability distributions over
$\mathbb{N}$ whose densities are integer multiples of $1/N$. Then
$\frac{1}{2}\cdot\mathsf{dist}_{\mathsf{rel-
edit}}(\psi(\pi),\psi(\pi^{\prime}))\leq\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})\leq\mathsf{dist}_{\mathsf{rel-
edit}}(\psi(\pi),\psi(\pi^{\prime}))$.

###  7.1 Single-Trace Upper Bounds

We seek to obtain algorithms for testing properties of strings, with respect
to the relative edit distance, by reducing to testing properties of
distributions under the parity trace, with respect to the edit distance on
distributions. We will make use of the following simple technique, which turns
a trace from a string (i.e. produced by a deletion channel) into (the parity
trace of) a Poissonized sample from the associated probability distribution
(i.e. the result of sampling with replacement).

######  Proposition 7.7.

Fix $\rho\in(0,1)$. There exists an algorithm Poissonize which consumes a
binary string and produces another binary string satisfying the following. Let
$N\in\mathbb{N}$ and $x\in\\{0,1\\}^{N}$, and suppose the input is a random
trace from $x$ with deletion rate $1-\rho$. Then the output is distributed as
$\mathsf{trace}(\bm{S})$, where $\bm{S}\sim\mathsf{samp}(\psi^{-1}(x),\bm{m})$
and $\bm{m}\sim\mathsf{Poi}\left(N\log\left(\frac{1}{1-\rho}\right)\right)$.

###### Proof.

The idea is to treat each symbol in the input as indicating the event that a
corresponding Poisson random variable was non-zero, and then up-sample the
symbol to the appropriate conditional distribution to obtain a Poissonized
sample.

Let $\lambda\vcentcolon=\log\left(\frac{1}{1-\rho}\right)$ and let
$\mathsf{Poi}_{>0}(\lambda)$ denote the distribution of a
$\mathsf{Poi}(\lambda)$ random variable conditional on being nonzero.

The algorithm proceeds as follows: on input string $s$, for each symbol
$s_{j}$ from left to right, independently sample
$\bm{z}_{j}\sim\mathsf{Poi}_{>0}(\lambda)$ and append $\bm{z}_{j}$ copies of
$s_{j}$ to the output.

For each $i\in[N]$, let $\bm{X}_{i}\sim\mathsf{Ber}(\rho)$ independently. Then
the input is distributed as

$x_{1}^{\bm{X}_{1}}x_{2}^{\bm{X}_{2}}\dotsm
x_{N-1}^{\bm{X}_{N-1}}x_{N}^{\bm{X}_{N}}\,.$

Let $\pi\vcentcolon=\psi^{-1}(x)$, say it is supported on $[n]$. For each
$i\in[n]$, let $\bm{Y}_{i}\sim\mathsf{Poi}(N\lambda\pi(i))$ independently.
Then the target output distribution is identical to that of

$1^{\bm{Y}_{1}}0^{\bm{Y}_{2}}\dotsm\mathsf{par}(n-1)^{\bm{Y}_{n-1}}\mathsf{par}(n)^{\bm{Y}_{n}}\,.$

By additivity of the Poisson distribution and definition of $\psi^{-1}$, this
distribution is identical to

$x_{1}^{\bm{Z}_{1}}x_{2}^{\bm{Z}_{2}}\dotsm
x_{N-1}^{\bm{Z}_{N-1}}x_{N}^{\bm{Z}_{N}}\,.$

where for each $i\in[N]$, $\bm{Z}_{i}\sim\mathsf{Poi}(\lambda)$ independently.

By considering the random process that produces the trace from $x$ along with
the random process of the algorithm, we may identify each symbol in the output
of the algorithm with the location $i\in[N]$ corresponding to the appearance
of $x_{i}$ in the trace. For each $i\in[N]$, let $\bm{K}_{i}$ be the random
variable denoting how many times $x_{i}$ was appended to the output. Then
$\bm{K}_{i}$ is distributed according to the following random process: if
$\bm{X}_{i}=0$ then $\bm{K}_{i}\leftarrow 0$, otherwise
$\bm{K}_{i}\leftarrow\mathsf{Poi}_{>0}(\lambda)$. Note that the $\bm{K}_{i}$
are mutually independent, and the output of the algorithm is

$x_{1}^{\bm{K}_{1}}x_{2}^{\bm{K}_{2}}\dotsm
x_{N-1}^{\bm{K}_{N-1}}x_{N}^{\bm{K}_{N}}\,.$

Therefore we will be done if, for each $i\in[N]$, $\bm{Z}_{i}$ and
$\bm{K}_{i}$ are distributed identically, which we now check. We have
$\mathbb{P}\left[\bm{K}_{i}=0\right]=\mathbb{P}\left[\bm{X}_{i}=0\right]=1-\rho$
and $\mathbb{P}\left[\bm{Z}_{i}=0\right]=e^{-\lambda}=1-\rho$, and for each
$k\geq 1$,

$\displaystyle\mathbb{P}\left[\bm{Z}_{i}=k\right]$
$\displaystyle=\mathbb{P}\left[\bm{Z}_{i}>0\right]\underset{}{\mathbb{P}}\left[\bm{Z}_{i}=k\;\;\mid\;\;\bm{Z}_{i}>0\right]=\rho\cdot\mathbb{P}\left[\mathsf{Poi}_{>0}(\lambda)=k\right]$
$\displaystyle=\mathbb{P}\left[\bm{X}_{i}=1\right]\cdot\underset{}{\mathbb{P}}\left[\bm{K}_{i}=k\;\;\mid\;\;\bm{X}_{i}=1\right]=\mathbb{P}\left[\bm{K}_{i}=k\text{
and }\bm{X}_{i}=1\right]=\mathbb{P}\left[\bm{K}_{i}=k\right]\,.\qed$

######  Remark 7.8.

Although we assume that $\rho$ is explicitly known to obtain Proposition 7.7,
this assumption is not crucial: if we only knew a lower bound $\rho_{0}$ on
$\rho$, we could obtain essentially equivalent results by sub-sampling
$\mathsf{Bin}(N,\rho^{\prime})$ elements from the trace with
$\rho^{\prime}=\rho_{0}/C$ for some large constant $C$. Then, except with
negligible probability of failure, the sample would be distributed as a trace
with known deletion rate $1-\rho^{\prime}$.

Equipped with this result, we obtain testers in the trace reconstruction model
from testers in the parity trace model via a black-box reduction.

######  Lemma 7.9.

Let $N,m\in\mathbb{N}$. Let $\Psi_{1},\Psi_{2}$ be properties of strings in
$\\{0,1\\}^{N}$, and let $\alpha>0$. If there is a Poissonized
$(\Pi(\Psi_{1}),\Pi(\Psi_{2}),\alpha)$-distribution tester under the parity
trace with sample complexity $m$, then there is a
$(\Psi_{1},\Psi_{2},\rho,\alpha)$-trace tester using one trace, for
$\rho=1-e^{-m/N}$.

###### Proof.

Let $A$ be a Poissonized $(\Pi(\Psi_{1}),\Pi(\Psi_{2}),\alpha)$-distribution
tester under the parity trace with sample complexity $m$. Our trace tester $B$
works as follows:

  1. 1.

Receive a trace $x$ with deletion rate $1-\rho$.

  2. 2.

Let $y\leftarrow\textsc{Poissonize}(x)$.

  3. 3.

Return $A(y)$.

Let $\bm{x}$ and $\bm{y}$ be random variables denoting the inputs to $B$ and
$A$, respectively. By Proposition 7.7, $\bm{y}$ is distributed as
$\mathsf{trace}(\bm{S})$ where $\bm{S}\sim\mathsf{samp}(\psi^{-1}(x),\bm{m})$
and $\bm{m}\sim\mathsf{Poi}(N\lambda)$, where
$\lambda=\log\left(\frac{1}{1-\rho}\right)=m/N$. In other words, $\bm{y}$ is
distributed as the parity trace of a sample from $\psi^{-1}(x)$ of size
$\mathsf{Poi}(m)$. Moreover, by definition of $\Pi(\Psi_{1})$ we have that if
$x\in\Psi_{1}$ then $\psi^{-1}(x)\in\Pi(\Psi_{1})$, and the same for
$\Psi_{2}$. Therefore the correctness of $B$ follows from the correctness of
$A$. ∎

We now conclude each of our single-trace upper bounds from Section 1.4, using
the following immediate consequence of the equivalence of edit distances
between strings and distributions.

######  Proposition 7.10.

Let $N\in\mathbb{N}$ and $\epsilon>0$, and let $\Psi$ be a property of strings
in $\\{0,1\\}^{N}$. Then $\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))$.

###### Proof.

Let $\pi\in\Pi(\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi))$. By
definition of $\Pi(\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi))$, we
have $\pi=\psi^{-1}(x)$ for some $x\in\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi)$. Thus $x\in\\{0,1\\}^{N}$ and for each $y\in\Psi$,
$\mathsf{dist}_{\mathsf{rel-edit}}(x,y)>\epsilon$, and by Lemma 7.6
$\mathsf{dist}_{\mathsf{edit}}(\psi^{-1}(x),\psi^{-1}(y))>\epsilon/2$.

By definition of $\Pi(\Psi)$, for each $\pi^{\prime}\in\Pi(\Psi)$ we have
$\pi^{\prime}=\psi^{-1}(y^{\prime})$ for some $y^{\prime}\in\Psi$. But then
$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{\prime})=\mathsf{dist}_{\mathsf{edit}}(\psi^{-1}(x),\psi^{-1}(y^{\prime}))>\epsilon/2$.
Therefore $\pi\in\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))$. ∎

Our result for testing $n$-block strings will require the following
equivalence between the relative edit distance of strings to the property of
$n$-block strings, and the edit distance of appropriate probability
distributions to the property of distributions supported on at most $n$
elements. We defer the proof to Section D.7.

######  Proposition 7.11.

Let $N,n\in\mathbb{N}$. Let $\Psi$ be the set of $n$-block strings in
$\\{0,1\\}^{N}$, and let $\Pi$ be the set of probability distributions over
$\mathbb{N}$ with support size at most $n$. Then for every distribution $\pi$
over $\mathbb{N}$ whose densities are integer multiples of $1/N$ and for
$x=\psi(\pi)$,

$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)\leq\mathsf{dist}_{\mathsf{rel-
edit}}(x,\Psi)\leq 2\cdot\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)\,.$

This implies:

######  Proposition 7.12.

Let $N\in\mathbb{N}$. Let $\Psi$ be a property of strings in $\\{0,1\\}^{N}$
and let $\Pi$ be a property of probability distributions over $\mathbb{N}$.
Suppose that for every distribution $\pi$ over $\mathbb{N}$ whose densities
are integer multiples of $1/N$ and for $x=\psi(\pi)$, it holds that
$\mathsf{dist}_{\mathsf{rel-edit}}(x,\Psi)\leq
2\cdot\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)$. Then

$\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)\,.$

###### Proof.

Let $I$ be the set of distributions over $\mathbb{N}$ whose densities are
integer multiples of $1/N$. We claim that
$\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))\cap
I\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)$.

Fix any $\pi\in\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))\cap I$. We
have that $\mathsf{dist}_{\mathsf{edit}}(\pi,\psi^{-1}(y))>\epsilon/2$ for
every $y\in\Psi$, and since all densities in $\pi$ are integer multiples of
$1/N$ by $\pi\in I$, letting $x\vcentcolon=\psi(\pi)$ we conclude by Lemma 7.6
that $\mathsf{dist}_{\mathsf{rel-edit}}(x,y)>\epsilon/2$. Therefore
$\mathsf{dist}_{\mathsf{rel-edit}}(x,\Psi)>\epsilon/2$, and using the
hypothesis, we conclude that
$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)>\epsilon/4$ and thus
$\pi\in\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)$, establishing the first
claim.

By Proposition 7.10, $\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))$,
and therefore $\Pi(\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi))\cap
I\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/2}(\Pi(\Psi))\cap
I\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)$. Finally, note that
$\Pi(\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi))\cap
I=\Pi(\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi))$ because every member
of the latter has the form $\pi=\psi^{-1}(x)$ for some $x\in\\{0,1\\}^{N}$, so
we are done. ∎

The following result establishes the upper bound portion of Theorem 1.9.

######  Theorem 7.13.

Let $N,n\in\mathbb{N}$ and $\epsilon>0$, and let $\Psi$ be the set of
$n$-block strings in $\\{0,1\\}^{N}$. There is a
$(\Psi,\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi),\rho,2/3)$-trace
tester using one trace with expected trace size $\rho N=O(n/\epsilon)$.

###### Proof.

Let $\Pi$ be the class of distributions over $\mathbb{N}$ with support size at
most $n$. By Theorem 6.38, there is a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi),2/3)$-distribution tester
under the parity trace, which we may assume is Poissonized by Proposition A.1,
with sample complexity $O(n/\epsilon)$.

Since for every $x\in\Psi$ we have that $\psi^{-1}(x)$ has support size at
most $n$ (7.5), it follows that $\Pi(\Psi)\subseteq\Pi$. Proposition 7.12
together with Proposition 7.11 gives that $\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)$.

Therefore we obtain a $(\Pi(\Psi),\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi)),2/3)$-distribution tester under the parity trace with
sample complexity $m=O(n/\epsilon)$. Then Lemma 7.9 yields a
$(\Psi,\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi),\rho,2/3)$-trace
tester using one trace for $\rho=1-e^{-m/N}\leq m/N$, i.e. expected trace size
$\rho N=O(n/\epsilon)$. ∎

Our results for trace testing uniform $n$-block strings are simpler to obtain
from distribution testing under the parity trace, because now the
corresponding property $\Pi$ of probability distributions contains only the
distributions corresponding to the uniform $n$-block strings.

##### Notation.

For fixed $N\in\mathbb{N}$ and $n$ that divides $N$, let $u^{(1)}$ denote the
1-uniform $n$-block string and let $u^{(0)}$ denote the 0-uniform $n$-block
string.

######  Proposition 7.14.

Let $N,n\in\mathbb{N}$ be such that $n$ divides $N$. Let $\Psi$ contain only
the 1-uniform $n$-block string $u^{(1)}$, and let $\Pi$ contain only the
uniform distribution over $[n]$. For every distribution $\pi$ over
$\mathbb{N}$ whose densities are integer multiples of $1/N$ and for
$x=\psi(\pi)$,

$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)\leq\mathsf{dist}_{\mathsf{rel-
edit}}(x,\Psi)\leq 2\cdot\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)\,.$

###### Proof.

Let $\pi^{*}$ be the uniform distribution over $[n]$, so that
$\pi^{*}=\psi^{-1}(u^{(1)})$ (7.5). The two inequalities are immediate
consequences of Lemma 7.6. First, we have
$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)=\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{*})\leq\mathsf{dist}_{\mathsf{rel-
edit}}(x,u^{(1)})=\mathsf{dist}_{\mathsf{rel-edit}}(x,\Psi)$. Similarly,
$\mathsf{dist}_{\mathsf{edit}}(\pi,\Pi)=\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{*})\geq\frac{1}{2}\mathsf{dist}_{\mathsf{edit}}(x,u^{(1)})=\frac{1}{2}\mathsf{dist}_{\mathsf{edit}}(x,\Psi)$.
∎

We first show a tester for the 1-uniform $n$-block strings, and then
generalize it to both types of uniform strings to obtain Theorem 1.8, restated
here:

######  Theorem 7.15.

Let $N,n\in\mathbb{N}$ be such that $n$ divides $N$, and let $\epsilon>0$. Let
$\Psi$ contain only the uniform $n$-block strings in $\\{0,1\\}^{N}$. There is
a $(\Psi,\textsc{far}^{\mathsf{rel-edit}}_{\epsilon}(\Psi),\rho,2/3)$-trace
tester using one trace with expected trace size $\rho
N=O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log n}\right)$.

######  Lemma 7.16.

Let $N,n\in\mathbb{N}$ be such that $n$ divides $N$, and let $\epsilon>0$. Let
$\Psi$ contain only the 1-uniform $n$-block string $u^{(1)}\in\\{0,1\\}^{N}$.
There is a $(\Psi,\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi),\rho,2/3)$-trace tester using one trace with expected
trace size $\rho N=O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log
n}\right)$.

###### Proof.

Let $\Pi$ contain only the uniform distribution $\pi=\psi^{-1}(u^{(1)})$ over
$[n]$. By Theorem 6.34, there is a
$(\Pi,\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi),2/3)$-distribution tester
under the parity trace, which we may assume is Poissonized by Proposition A.1,
with sample complexity $O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log
n}\right)$.

Note that $\Pi=\\{\pi\\}=\\{\psi^{-1}(u^{(1)})\\}=\Pi(\Psi)$. Moreover,
Proposition 7.12 together with Proposition 7.14 gives that
$\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi))\subseteq\textsc{far}^{\mathsf{edit}}_{\epsilon/4}(\Pi)$,
so we obtain a $(\Pi(\Psi),\Pi(\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi),2/3)$-distribution tester under the parity trace with
sample complexity $m=O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log
n}\right)$. Then Lemma 7.9 yields a $(\Psi,\textsc{far}^{\mathsf{rel-
edit}}_{\epsilon}(\Psi),\rho,2/3)$-trace tester using one trace for
$\rho=1-e^{-m/N}$, i.e. expected trace size $\rho
N=O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log n}\right)$. ∎

###### Proof of Theorem 7.15.

Use a version of the tester for the 1-uniform $n$-block string from Lemma 7.16
with success probability $5/6$, repeat it with all symbols negated, and accept
if either execution accepts. If the input $x=u^{(1)}$, the first execution
accepts with probability at least $5/6$, and if $x=u^{(0)}$, the second
execution accepts with probability at least $5/6$. If
$\mathsf{dist}_{\mathsf{rel-edit}}(x,\Psi)>\epsilon$, then $x$ is far from
both $u^{(1)}$ and $u^{(0)}$, so each execution only accepts with probability
at most $1/6$, and by the union bound the probability that $x$ is accepted is
at most $1/3$. ∎

Toward establishing the upper bound portion of Theorem 1.7, we introduce the
following definition. We say that $x\in\\{0,1\\}^{N}$ is a _type-1 $n$-block
string_ if $x=1^{t_{1}}0^{t_{2}}1^{t_{3}}\dotsm\mathsf{par}(n)^{t_{n}}$ for
some choice of non-negative integers $t_{1},\dotsc,t_{n}$. We say that $x$ is
a _type-0 $n$-block string_ if
$x=0^{t_{1}}1^{t_{2}}0^{t_{3}}\dotsm(1-\mathsf{par}(n))^{t_{n}}$ for some
choice of non-negative integers $t_{1},\dotsc,t_{n}$.

######  Remark 7.17.

A string $x$ may be _both_ a type-1 $n$-block string and a type-0 $n$-block
string. Moreover, $x$ is an $n$-block string if and only if it is a type-1
$n$-block string or a type-0 $n$-block string.

If $x$ is a type-1 $n$-block string, then $\psi^{-1}(x)$ is supported within
$[n]$, and if $x$ is a type-0 $n$-block string, then $\psi^{-1}(x)$ is
supported within $\\{2,3,\dotsc,n+1\\}$.

######  Lemma 7.18.

Let $N,n\in\mathbb{N}$ be such that $n$ is even and divides $N$, and let
$\epsilon>0$. Let $\Psi_{1}$ contain only the 1-uniform $n$-block string
$u^{(1)}\in\\{0,1\\}^{N}$, and let $\Psi_{2}$ contain all type-1 $n$-block
strings in $\\{0,1\\}^{N}$ that are $\epsilon$-far from $\Psi_{1}$ in
(relative) edit distance. There is a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace
tester using one trace of expected size $\rho
N=\widetilde{O}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$.

###### Proof.

Let $\Pi_{1}$ contain only the uniform distribution
$\pi^{*}=\psi^{-1}(u^{(1)})$ over $[n]$, and let $\Pi_{2}$ contain the
distributions over $[n]$ that are $\epsilon/2$-far from uniform in edit
distance. By Theorem 4.1 together with 6.29, there is a
$(\Pi_{1},\Pi_{2},2/3)$-distribution tester under the parity trace, which we
may assume is Poissonized by Proposition A.1, with sample complexity
$\widetilde{O}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$.

We claim that $\Pi(\Psi_{1})\subseteq\Pi_{1}$ and
$\Pi(\Psi_{2})\subseteq\Pi_{2}$. First, let $\pi\in\Pi(\Psi_{1})$, so that
necessarily $\pi=\psi^{-1}(u^{(1)})$. Then indeed $\pi$ is uniform over $[n]$,
so $\pi\in\Pi_{1}$. Now, suppose $\pi\in\Pi(\Psi_{2})$, so that
$\pi=\psi^{-1}(x)$ for some $x\in\\{0,1\\}^{N}$ such that $x$ is a type-1
$n$-block string and $\mathsf{dist}_{\mathsf{rel-edit}}(x,u^{(1)})>\epsilon$.
It follows that $\pi$ is supported within $[n]$ by Remark 7.17 and, by Lemma
7.6,
$\mathsf{dist}_{\mathsf{edit}}(\pi,\pi^{*})\geq\frac{1}{2}\mathsf{dist}_{\mathsf{rel-
edit}}(\psi(\pi),\psi(\pi^{*}))=\frac{1}{2}\mathsf{dist}_{\mathsf{rel-
edit}}(x,u^{(1)})>\epsilon/2$, so $\pi\in\Pi_{2}$.

Therefore we obtain a $(\Pi(\Psi_{1}),\Pi(\Psi_{2}),2/3)$-distribution tester
under the parity trace with sample complexity
$m=\widetilde{O}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$. Then Lemma 7.9
yields a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester using one trace for
$\rho=1-e^{-m/N}$, i.e. expected trace size $\rho
N=\widetilde{O}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$. ∎

Now, we obtain the single-trace upper bound portion of Theorem 1.7:

######  Theorem 7.19.

Let $N,n\in\mathbb{N}$ be such that $n$ is even and divides $N$, and let
$\epsilon>0$. Let $\Psi_{1}$ contain only the uniform $n$-block strings
$u^{(1)},u^{(0)}\in\\{0,1\\}^{N}$, and let $\Psi_{2}$ contain all $n$-block
strings in $\\{0,1\\}^{N}$ that are $\epsilon$-far from $\Psi_{1}$ in
(relative) edit distance. There is a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace
tester using one trace of expected size $\rho
N=\widetilde{O}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$.

###### Proof.

The key observation is that the algorithm $A$ obtained in Lemma 7.18 is
invariant to negation of all the symbols in the input: it is a combination of
the distribution tester from Theorem 4.1, which only depends on run lengths,
and the Poissonize algorithm from Proposition 7.7, which transforms the input
in the same way regardless of the values of the symbols. Formally, for
$x\in\\{0,1\\}^{N}$ and letting $\overline{x}$ denote the string obtained by
negating every symbol in $x$, the outputs $A(x)$ and $A(\overline{x})$ are
identically distributed.

Therefore, we claim that $A$ is also a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace
tester. Indeed if the input $x\in\Psi_{1}$, then either $x=u^{(1)}$ and $A$
accepts with probability at least $2/3$ by Lemma 7.18, or $x=u^{(0)}$ and
therefore $\overline{x}=u^{(1)}$, so again $A$ accepts. On the other hand, if
$x\in\Psi_{2}$ then $\mathsf{dist}_{\mathsf{rel-edit}}(x,u^{(1)})>\epsilon$
and $\mathsf{dist}_{\mathsf{rel-
edit}}(\overline{x},u^{(1)})=\mathsf{dist}_{\mathsf{rel-
edit}}(x,u^{(0)})>\epsilon$. Moreover, either $x$ or $\overline{x}$ is a
type-1 $n$-block string, so $A$ rejects with probability at least $2/3$. ∎

We remark that the probability of success $2/3$ in the results above could be
replaced with any higher constant without affecting the asymptotic bounds, by
using the distribution tester under the parity trace with correspondingly
better constant probability of success. Alternatively, multiple independent
traces may be used to amplify the result into the high probability regime.

###  7.2 Multiple-Trace Upper Bound

The ability to make inferences from multiple independent traces is a central
component of the trace reconstruction model. Accordingly, we would like to
test the class of uniform $n$-block strings with smaller traces than afforded
by our single-trace results, at the cost of taking more traces. The main idea
is to _reduce_ to the single-trace case by concatenating the $k$ traces
together, and thinking of the result as one trace from the input string copied
$k$ times.

For any strings $x,y\in\\{0,1\\}^{*}$ and integer $k>0$, denote by $x\circ y$
the concatenation of $x$ and $y$, and by $x^{\circ k}$ the concatenation
$x\circ\dotsm\circ x$ with $k$ terms in total.

######  Proposition 7.20.

There exists a universal constant $c>0$ such the following holds. Let
$N,n,k\in\mathbb{N}$ be such that $n$ is even and divides $N$. Let
$u=u^{(1)}\in\\{0,1\\}^{N}$ be the 1-uniform $n$-block string and let
$x\in\\{0,1\\}^{N}$ be a type-1 $n$-block string. Then

$\mathsf{dist}_{\mathsf{rel-edit}}(u^{\circ k},x^{\circ k})\geq
c\cdot\mathsf{dist}_{\mathsf{rel-edit}}(u,x)\,.$

###### Proof.

Let $\pi_{u}\vcentcolon=\psi^{-1}(u)$ and $\pi_{x}\vcentcolon=\psi^{-1}(x)$,
so that $\pi_{u}$ and $\pi_{x}$ are supported within $[n]$ and
$\psi(\pi_{u})=u,\psi(\pi_{x})=x$. Define $\pi_{u}^{k}$ as the following
distribution on $\mathbb{N}$: for all $t\in\mathbb{Z}_{\geq 0}$ and $i\in[n]$,

$\pi_{u}^{k}(tn+i)\vcentcolon=\begin{cases}\pi_{u}(i)/k,&\text{if $t\leq
k-1$}\\\ 0,&\text{if $t\geq k$.}\end{cases}$

Define $\pi_{x}^{k}$ analogously. Then
$\mathsf{dist}_{\mathsf{TV}}(\pi_{u}^{k},\pi_{x}^{k})=\mathsf{dist}_{\mathsf{TV}}(\pi_{u},\pi_{x})$,
since the entries of the former are aligned in each of the $k$ rescaled copies
of the latter. Also, the entries of $\pi_{u}^{k},\pi_{x}^{k}$ are integer
multiples of $1/kN$, and their corresponding strings over $\\{0,1\\}^{kN}$
satisfy $\psi(\pi_{u}^{k})=u^{\circ k}$ and $\psi(\pi_{x}^{k})=x^{\circ k}$.

By Lemma 7.6, we have $\mathsf{dist}_{\mathsf{rel-edit}}(u^{\circ k},x^{\circ
k})=\mathsf{dist}_{\mathsf{rel-
edit}}(\psi(\pi_{u}^{k}),\psi(\pi_{x}^{k}))\geq\mathsf{dist}_{\mathsf{edit}}(\pi_{u}^{k},\pi_{x}^{k})$.
Since $n$ is even, $u^{\circ k}$ is the 1-uniform $kn$-block string, and
therefore $\pi_{u}^{k}$ is uniformly distributed on $[kn]$. It is also clear
that $\pi_{x}^{k}$ is supported within $[kn]$. It follows from Lemma 6.31 that
$\mathsf{dist}_{\mathsf{edit}}(\pi_{u}^{k},\pi_{x}^{k})\geq
c^{\prime}\cdot\mathsf{dist}_{\mathsf{TV}}(\pi_{u}^{k},\pi_{x}^{k})=\mathsf{dist}_{\mathsf{TV}}(\pi_{u},\pi_{x})$
for some universal constant $c^{\prime}>0$. It is easy to see from the
definition of edit distance that
$\mathsf{dist}_{\mathsf{TV}}(\pi_{u},\pi_{x})\geq\mathsf{dist}_{\mathsf{edit}}(\pi_{u},\pi_{x})$.
Finally, applying Lemma 7.6 again yields
$\mathsf{dist}_{\mathsf{edit}}(\pi_{u},\pi_{x})\geq\frac{1}{2}\mathsf{dist}_{\mathsf{rel-
edit}}(\psi(\pi_{u}),\psi(\pi_{x}))$. Recalling that $\psi(\pi_{u})=u$ and
$\psi(\psi_{x})=x$, this concludes the proof. ∎

We first use the result above to show a multiple-trace upper bound for testing
the 1-uniform strings among the type-1 $n$-block strings, and then generalize
this result to both types of (uniform) strings to obtain the upper bound
portion of Theorem 1.7.

######  Lemma 7.21.

Let $N,n,k\in\mathbb{N}$ be such that $n$ is even and divides $N$, and let
$\epsilon>0$. Let $\Psi_{1}$ contain only the 1-uniform $n$-block string
$u^{(1)}\in\\{0,1\\}^{N}$, and let $\Psi_{2}$ be the set of type-1 $n$-block
strings that are $\epsilon$-far from $\Psi_{1}$ in (relative) edit distance.
Then there is a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester using $k$ traces
of expected size $\rho
N=\widetilde{O}\left(\frac{n^{4/5}}{k^{1/5}\epsilon^{4/5}}+\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right)$.

###### Proof.

Let $u\vcentcolon=u^{(1)}$ for convenience of notation. Let
$\Psi^{\prime}_{1}$ contain only the 1-uniform $kn$-block string $u^{\circ
k}\in\\{0,1\\}^{kN}$, and let $\Psi^{\prime}_{2}$ be the set of type-1
$kn$-block strings in $\\{0,1\\}^{kN}$ that are $c\epsilon$-far from
$\Psi^{\prime}_{1}$ in relative edit distance, where $c$ is the constant from
Proposition 7.20.

By Lemma 7.18 we obtain algorithm $A$, a
$(\Psi^{\prime}_{1},\Psi^{\prime}_{2},\rho^{\prime},2/3)$-trace tester using
one trace of expected size
$\rho^{\prime}(kN)=\widetilde{O}((kn)^{4/5}/\epsilon^{4/5}+\sqrt{kn}/\epsilon^{2})$.
Our algorithm $B$, which will be a $(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester
using $k$ traces, works as follows:

  1. 1.

Obtain $k$ independent traces $x_{1},\dotsc,x_{k}$ of expected size $\rho
N=\widetilde{O}\left(\frac{n^{4/5}}{k^{1/5}\epsilon^{4/5}}+\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right)$.

  2. 2.

Return the output of $A$ on $x_{1}\circ\dotsm\circ x_{k}$.

Let $x\in\\{0,1\\}^{N}$ be the unknown input to $B$. If $x\in\Psi_{1}$, then
$x=u$ and hence $x^{\circ k}\in\Psi^{\prime}_{1}$. On the other hand, if
$x\in\Psi_{2}$, then $\mathsf{dist}_{\mathsf{rel-edit}}(x,u)>\epsilon$ and we
use Proposition 7.20 to conclude that $\mathsf{dist}_{\mathsf{rel-
edit}}(x^{\circ k},u^{\circ k})>c\epsilon$, so $x^{\circ
k}\in\Psi^{\prime}_{2}$. Moreover, the input
$\bm{x}_{1}\circ\dotsm\circ\bm{x}_{k}$ to $A$ is distributed as a trace from
$x^{\circ k}$ of expected size $k(\rho N)$, i.e. deletion rate $\rho$.
Therefore $A$ will produce the correct output (and hence so will $B$) with
probability at least $2/3$ as long as we satisfy

$k\rho
N\geq\widetilde{O}\left(\frac{(kn)^{4/5}}{\epsilon^{4/5}}+\frac{\sqrt{kn}}{\epsilon^{2}}\right)\,,$

which holds when

$\rho
N\geq\widetilde{O}\left(\frac{n^{4/5}}{k^{1/5}\epsilon^{4/5}}+\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right)\,.\qed$

We now obtain the upper bound portion of Theorem 1.7.

######  Theorem 7.22.

Let $N,n,k\in\mathbb{N}$ be such that $n$ is even and divides $N$, and let
$\epsilon>0$. Let $\Psi_{1}$ contain only the uniform $n$-block strings in
$\\{0,1\\}^{N}$, and let $\Psi_{2}$ be the set of $n$-block strings that are
$\epsilon$-far from $\Psi_{1}$ in (relative) edit distance. Then there is a
$(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester using $k$ traces of expected size
$\rho
N=\widetilde{O}\left(\frac{n^{4/5}}{k^{1/5}\epsilon^{4/5}}+\frac{\sqrt{n}}{\sqrt{k}\epsilon^{2}}\right)$.

###### Proof.

The argument is identical to the proof of Theorem 7.19. Letting $A$ be the
algorithm from Lemma 7.21, we observe that the output $A(x)$ is distributed
identically to $A(\overline{x})$. Therefore $A$ is also a
$(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester using $k$ traces: if
$x\in\Psi_{1}$, then either $x=u^{(1)}$ or $\overline{x}=u^{(1)}$, so $A$
accepts, and if $x\in\Psi_{2}$, then both $x$ and $\overline{x}$ are far from
$u^{(1)}$ and moreover either $x$ or $\overline{x}$ is a type-1 $n$-block
string, so $A$ rejects. ∎

###  7.3 Lower Bounds

We wish to reduce from distribution testing under the parity trace to testing
properties of strings in the trace reconstruction model. We define a “trace
splitting” procedure, which takes a parity trace from distribution $\pi$ and
produces $k$ strings that look like independent traces from string
$\psi(\pi)$.

######  Proposition 7.23 (Poissonized trace splitting).

There exists a randomized algorithm Split that satisfies the following. Let
$N,k\in\mathbb{N}$ and let $\rho>0$ satisfy $\rho<\frac{1}{20\cdot\sqrt{kN}}$.
Let $\pi$ be any probability distribution over $\mathbb{N}$ whose densities
are integer multiples of $1/N$. Then on inputs $N,k\text{ and }\rho$, Split
draws a parity trace of size $\mathsf{Poi}\left(k\cdot\frac{\rho}{1-\rho}\cdot
N\right)$ from $\pi$ and outputs a sequence of $k$ binary strings satisfying
the following. Let $\bm{x}_{1},\dotsc,\bm{x}_{k}$ be the random variables
denoting the output of Split (over the randomness of the parity trace and
internal randomness of the algorithm), and let $\bm{y}_{1},\dotsc,\bm{y}_{k}$
be such that each $\bm{y}_{i}$ is an independent trace from $\psi(\pi)$ with
expected size $\rho N$. Then

$\mathsf{dist}_{\mathsf{TV}}((\bm{x}_{1},\dotsc,\bm{x}_{k}),(\bm{y}_{1},\dotsc,\bm{y}_{k}))<1/100\,.$

###### Proof.

Let $\lambda\vcentcolon=\rho/(1-\rho)$. The algorithm Split proceeds as
follows:

  1. 1.

Draw a parity trace $T$ of size $\mathsf{Poi}(k\lambda N)$ from $\pi$;

  2. 2.

Initialize empty strings $x_{1},\dotsc,x_{k}$;

  3. 3.

For each symbol $b$ in $T$ from left to right, append $b$ to $x_{i}$ where $i$
is drawn uniformly at random from $[k]$;

  4. 4.

Return the strings $(x_{1},\dotsc,x_{k})$.

For each $i\in[k]$ and $j\in[N]$, let $\bm{X}_{i,j}\sim\mathsf{Poi}(\lambda)$
independently. Define random variables
$\bm{x}^{\prime}_{1},\dotsc,\bm{x}^{\prime}_{k}$ as follows: for each
$i\in[k]$,

$\bm{x}^{\prime}_{i}=\psi(\pi)_{1}^{\bm{X}_{i,1}}\psi(\pi)_{2}^{\bm{X}_{i,2}}\dotsm\psi(\pi)_{N}^{\bm{X}_{i,N}}\,.$

We claim that $(\bm{x}_{1},\dotsc,\bm{x}_{k})$ is distributed identically to
$(\bm{x}^{\prime}_{1},\dotsc,\bm{x}^{\prime}_{k})$. Indeed, first recall that
the parity trace $\bm{T}$ from Step 1 is distributed as follows:

$\bm{T}=\psi(\pi)_{1}^{\bm{A}_{1}}\psi(\pi)_{2}^{\bm{A}_{2}}\dotsm\psi(\pi)_{N}^{\bm{A}_{N}}\,,$

where $\bm{A}_{j}\sim\mathsf{Poi}(k\lambda)$ independently for each $j\in[N]$.
Then, Step 3 is equivalent to splitting each $\bm{A}_{j}$ into random
variables
$(\bm{A}_{1,j},\dotsc,\bm{A}_{k,j})\sim\mathsf{Multinomial}(\bm{A}_{j},(1/k,\dotsc,1/k))$,
and producing each $\bm{x}_{i}$ by concatenation:

$\bm{x}_{i}=\psi(\pi)_{1}^{\bm{A}_{i,1}}\psi(\pi)_{2}^{\bm{A}_{i,2}}\dotsm\psi(\pi)_{N}^{\bm{A}_{i,N}}\,.$

It follows from standard arguments that $\bm{A}_{1,j},\dotsc,\bm{A}_{k,j}$ are
i.i.d. random variables distributed as $\bm{A}_{i,j}\sim\mathsf{Poi}(\lambda)$
for each $i\in[k]$. Therefore the $\bm{A}_{i,j}$ are distributed identically
to the $\bm{X}_{i,j}$, and so $(\bm{x}_{1},\dotsc,\bm{x}_{k})$ is distributed
identically to $(\bm{x}^{\prime}_{1},\dotsc,\bm{x^{\prime}}_{k})$.

Now, for each $i\in[k]$ and $j\in[N]$, let
$\bm{Y}_{i,j}\sim\mathsf{Ber}(\rho)$ independently. By definition of trace, we
have

$\bm{y}_{i}=\psi(\pi)_{1}^{\bm{Y}_{i,1}}\psi(\pi)_{2}^{\bm{Y}_{i,2}}\dotsm\psi(\pi)_{N}^{\bm{Y}_{i,N}}\,.$

Therefore, we will be done if we can show that the $\bm{X}_{i,j}$ are
sufficiently similar to the $\bm{Y}_{i,j}$.

Concretely, fix some $i\in[k]$ and $j\in[N]$, and let $\bm{X}=\bm{X}_{i,j}$
and $\bm{Y}=\bm{Y}_{i,j}$ for convenience. We claim that
$\mathsf{dist}_{\mathsf{TV}}(\bm{X},\bm{Y})\leq\lambda^{2}$. Indeed, first,
note that the distribution of $\bm{X}$ conditional on $\bm{X}\leq 1$ is
identical to that of $\bm{Y}$:

$\underset{}{\mathbb{P}}\left[\bm{X}=1\;\;\mid\;\;\bm{X}\leq
1\right]=\frac{\mathbb{P}\left[\bm{X}=1\right]}{\mathbb{P}\left[\bm{X}=0\right]+\mathbb{P}\left[\bm{X}=1\right]}=\frac{\lambda
e^{-\lambda}}{e^{-\lambda}+\lambda
e^{-\lambda}}=\frac{\lambda}{1+\lambda}=\rho=\mathbb{P}\left[\bm{Y}=1\right]\,,$

and therefore

$\displaystyle\mathsf{dist}_{\mathsf{TV}}(\bm{X},\bm{Y})$
$\displaystyle=\mathbb{P}\left[\bm{X}\geq
2\right]=1-\mathbb{P}\left[\bm{X}=0\right]-\mathbb{P}\left[\bm{X}=1\right]=1-e^{-\lambda}-\lambda
e^{-\lambda}=1-e^{-\lambda}(1+\lambda)$ $\displaystyle\leq
1-(1-\lambda)(1+\lambda)=\lambda^{2}\,.$

Finally, since the $\bm{X}_{i,j}$ and $\bm{Y}_{i,j}$ are all mutually
independent, we obtain

$\mathsf{dist}_{\mathsf{TV}}((\bm{X}_{i,j})_{i\in[k],j\in[N]},(\bm{Y}_{i,j})_{i\in[k],j\in[N]})\leq
kN\cdot\lambda^{2}<kN(2\rho)^{2}<1/100\,,$

and thus
$\mathsf{dist}_{\mathsf{TV}}((\bm{x}_{1},\dotsc,\bm{x}_{k}),(\bm{y}_{1},\dotsc,\bm{y}_{k}))<1/100$
by the data processing inequality. ∎

We use this procedure to give our general lower bound for trace testing:

######  Lemma 7.24.

Let $\alpha>0$. Let $N,k\in\mathbb{N}$, and let $\Pi_{1},\Pi_{2}$ be
properties of probability distributions over $\mathbb{N}$ whose densities are
integer multiples of $1/N$, and such that $(\Pi_{1},\Pi_{2},\alpha)$-testing
under the parity trace requires sample complexity at least $m$. Then any
$(\Psi(\Pi_{1}),\Psi(\Pi_{2}),\rho,\alpha+1/100)$-trace tester using $k$
traces of expected size $\rho N$ must satisfy $k\rho
N=\Omega\left(\min\left(m,\sqrt{kN}\right)\right)$.

###### Proof.

Suppose $B$ is a $(\Psi(\Pi_{1}),\Psi(\Pi_{2}),\alpha+1/100)$-trace tester
using $k$ traces of expected size $\rho N$, and suppose $k\rho
N<\sqrt{kN}/20$. Then $\rho<\frac{1}{20\sqrt{kN}}$ and our goal is to show
that $k\rho N=\Omega(m)$. We do so by constructing an algorithm $A$ in the
parity trace model and showing that $A$ is a $(\Pi_{1},\Pi_{2},\alpha)$-tester
under the parity trace with sample complexity $O(k\rho N)$. The algorithm
works as follows:

  1. 1.

Take a parity trace of size $\mathsf{Poi}\left(k\cdot\frac{\rho}{1-\rho}\cdot
N\right)$.

  2. 2.

Apply Split to obtain $k$ binary strings $x_{1},\dotsc,x_{k}$.

  3. 3.

Return the output of $B$ on inputs $x_{1},\dotsc,x_{k}$.

Note that $A$ has sample complexity $O(k\rho N)$. Let $\pi$ be the input
distribution; recall that if $\pi\in\Pi_{1}$ then $\psi(\pi)\in\Psi(\Pi_{1})$,
and if $\pi\in\Pi_{2}$ then $\psi(\pi)\in\Psi(\Pi_{2})$. Let
$\bm{x}_{1},\dotsc,\bm{x}_{k}$ be the inputs fed to $B$, and let
$\bm{y}_{1},\dotsc,\bm{y}_{k}$ be mutually independent traces from
$\psi(\pi)$, each with expected size $\rho N$. By Proposition 7.23,
$\mathsf{dist}_{\mathsf{TV}}((\bm{x}_{1},\dotsc,\bm{x}_{k}),(\bm{y}_{1},\dotsc,\bm{y}_{k}))<1/100$,
and we know that $B$ would succeed (i.e. accept if
$\psi(\pi)\in\Psi(\Pi_{1})$, reject if $\psi(\pi)\in\Psi(\Pi_{2})$) with
probability at least $\alpha+1/100$ if it were given inputs
$\bm{y}_{1},\dotsc,\bm{y}_{k}$. Therefore $A$ succeeds with probability at
least $\alpha$, and $k\rho N=\Omega(m)$. ∎

We now obtain the lower bounds stated in Theorems 1.7 and 1.9.

######  Theorem 7.25.

There exists a universal constant $C>0$ such that the following holds. Let
$n,N\in\mathbb{N}$ and $\rho,\epsilon>0$ be such that $n$ is even and divides
$N$, $\epsilon$ is smaller than some sufficiently small universal constant,
and $N\geq C\cdot\max\left\\{(n/\epsilon)^{8/5},n/\epsilon^{4}\right\\}$. Let
$\Psi_{1}$ contain only the uniform $n$-block strings in $\\{0,1\\}^{N}$, and
let $\Psi_{2}$ be the set of all $n$-block strings that are $\epsilon$-far
from $\Psi_{1}$ in (relative) edit distance. Then any
$(\Psi_{1},\Psi_{2},\rho,2/3)$-trace tester using $k$ traces of expected size
$\rho N$ must satisfy $k\rho
N=\widetilde{\Omega}((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2})$.

###### Proof.

Let $\Pi_{1}$ contain only the uniform distribution
$\pi^{*}=\psi^{-1}(u^{(1)})$ on $[n]$. Let $\epsilon^{*}\vcentcolon=8\epsilon$
for convenience. Using the value
$\epsilon^{\prime}\in(\epsilon^{*},2\epsilon^{*}]$ defined below, let
$\Pi_{2}$ be the set of distributions over $[n]$ that 1) are
$(\epsilon^{\prime}/c)$-far from uniform in total variation distance (where
$c$ is the constant from Lemma 6.31); and 2) have all densities in the set
$\left\\{\frac{1}{n},\frac{1-4\epsilon^{\prime}/c}{n},\frac{1+4\epsilon^{\prime}/c}{n}\right\\}$.
Note that, by Lemma 6.31, every distribution in $\Pi_{2}$ is
$\epsilon^{\prime}$-far from uniform in _edit_ distance.