# Distribution Testing Under the Parity Trace

Renato Ferreira Pinto Jr.
University of Waterloo
<EMAIL_ADDRESS>Partly funded by an NSERC Canada Graduate Scholarship
Doctoral Award. Nathaniel Harms
EPFL
<EMAIL_ADDRESS>Partly funded by an NSERC Postdoctoral Fellowship.
Much of this work was done while the author was at the University of Waterloo.

###### Abstract

_Distribution testing_ is a fundamental statistical task with many
applications, but we are interested in a variety of problems where systematic
mislabelings of the sample prevent us from applying the existing theory. To
apply distribution testing to these problems, we introduce _distribution
testing under the parity trace_ , where the algorithm receives an ordered
sample $S$ that reveals only the least significant bit of each element. This
abstraction reveals connections between the following three problems of
interest, allowing new upper and lower bounds:

  1. 1.

In distribution testing with a _confused collector_ , the collector of the
sample may be incapable of distinguishing between nearby elements of a domain
(e.g. a machine learning classifier). We prove bounds for distribution testing
with a confused collector on domains structured as a cycle or a path.

  2. 2.

Recent work on the fundamental _testing vs. learning_ question established
tight lower bounds on _distribution-free sample-based_ property testing by
reduction from distribution testing, but the tightness is limited to
_symmetric_ properties. The parity trace allows a broader family of
equivalences to _non-symmetric_ properties, while recovering and strengthening
many of the previous results with a different technique.

  3. 3.

We give the first results for property testing in the well-studied _trace
reconstruction_ model, where the goal is to test whether an unknown string $x$
satisfies some property or is far from satisfying that property, given only
independent random _traces_ of $x$.

Our main technical result is a tight bound of
$\widetilde{\Theta}\left((n/\epsilon)^{4/5}+\sqrt{n}/\epsilon^{2}\right)$ for
testing uniformity of distributions over $[n]$ under the parity trace, leading
also to results for the problems above.

###### Contents

  1. 1 Introduction
    1. 1.1 Distribution Testing under the Parity Trace
    2. 1.2 Distribution Testing with a Confused Collector
    3. 1.3 Distribution-Free Sample-Based Property Testing
    4. 1.4 Property Testing for Trace Reconstruction
    5. 1.5 Proof Overview
    6. 1.6 Discussion & Open Problems
  2. 2 Preliminaries and Common Framework for Upper Bounds
    1. 2.1 Notation
    2. 2.2 Confused Collector: Definition & Terminology
    3. 2.3 Parity Trace: Definition & Terminology
    4. 2.4 Path- and Cycle-Structured Poisson Random Variables.
    5. 2.5 Shared Analysis
  3. 3 Testing Uniformity in the Confused Collector Model
    1. 3.1 Easy Case: Highly Concentrated Distributions
    2. 3.2 Expected Value of the Test Statistic
    3. 3.3 Concentration of the Test Statistic
    4. 3.4 Correctness of the Tester
  4. 4 Testing Uniformity in the Parity Trace Model
    1. 4.1 The Small $\epsilon$ Case
    2. 4.2 Easy Cases: Unbalanced and Highly-Concentrated Distributions
    3. 4.3 Expected Value of the Test Statistic
    4. 4.4 Concentration of the Test Statistic
    5. 4.5 Correctness of the Tester for Large $\epsilon$
  5. 5 Lower Bound for Testing Uniformity in the Parity Trace Model
    1. 5.1 Outline of the Argument
    2. 5.2 Construction of YES and NO Distributions
    3. 5.3 Partial Fingerprints and their Probabilities
    4. 5.4 YES and NO Dominoes Behave Similarly
    5. 5.5 Information Bound
  6. 6 Distribution-Free Sample-Based Property Testing
    1. 6.1 Labeled Distributions
    2. 6.2 Edit Distance
    3. 6.3 Labeled Distribution Testing
    4. 6.4 Testing-by-Learning
    5. 6.5 Density Properties and Distribution Testing Under the Parity Trace
    6. 6.6 Testing Uniformly $k$-Alternating Functions
    7. 6.7 Promise-Free Testing $k$-Alternating and Uniformly $k$-Alternating Functions
    8. 6.8 Distribution-Free Sample-Based Property Testing
  7. 7 Property Testing in the Trace Reconstruction Model
    1. 7.1 Single-Trace Upper Bounds
    2. 7.2 Multiple-Trace Upper Bound
    3. 7.3 Lower Bounds
  8. A Poissonization and Boosting
  9. B Missing Proofs from Section 3
  10. C Missing Proofs from Section 4
    1. C.1 Testing Uniformity: the Small $\epsilon$ Case
  11. D Edit Distance Proofs
    1. D.1 Facts About Edit Distance and Labeled Distributions
    2. D.2 Equivalence of Edit Distance Definitions
    3. D.3 Equivalence of Edit Distances for Strings and Distributions
    4. D.4 Edit Distance for the Uniform Distribution
    5. D.5 Edit Distance for Labeled Distribution Support Size
    6. D.6 Edit Distance for Distribution Support Size
    7. D.7 String Edit Distance for Support Size
  12. E Comparison of Labeled Distribution Testing vs. the Parity Trace

##  1 Introduction

Making decisions about an unknown probability distribution $\mathcal{D}$,
using only random samples, is a basic type of statistical task. Deciding
whether $\mathcal{D}$ satisfies some property, or is _far_ (according to some
distance metric) from all distributions satisfying that property, is the
purpose of a _distribution testing_ algorithm. Distribution testing is well-
studied and interesting on its own, and also has many useful applications. But
we are interested in some problems where systematic mislabelings of data
prevent us from applying the existing theory. So we define _distribution
testing under the parity trace_ to help understand these problems. Before
defining this abstraction, let us explain these problems.

##### 1\. Distribution testing with a confused collector.

We wish to make a decision about an unknown distribution $\mathcal{D}$ over
some domain $\mathcal{X}$, using only a random sample $S$ from $\mathcal{D}$.
Unfortunately, $S$ has been collected or labeled by an entity who does not
know the difference between some elements of $\mathcal{X}$. Perhaps our sample
of woodland flora was tabulated by a research assistant who cannot
differentiate between black spruce and white spruce, or between red maple and
sugar maple, and has counted the spruces together and the maples together by
mistake111We thank ecologist Prof. Julie Messier for these examples of species
that are easily confused by students.. Or, the sample was labeled by a machine
learning classifier, and for each pair of elements $x,y\in\mathcal{X}$ there
is some chance that it has not learned to distinguish $x$ from $y$ and lumps
together all the samples of $x$ and $y$. Or, the sample labels have been
hashed by a function that introduces collisions between nearby elements of
$\mathcal{X}$. Or, we wish to know about the distribution of fossils by year,
but it is not possible to distinguish between fossils from year $x$ and
fossils from year $y$, unless a random geological event leaves a mark in the
rock between years $x$ and $y$. Recent work in learning theory notes that this
type of problem is common in the applied literature, but little is known
theoretically [FKKT21]. We introduce a model for this type of problem, called
_distribution testing with a confused collector_.

##### 2\. Distribution-free sample-based property testing.

The _testing vs. learning_ question of [GGR98] is one of the fundamental
questions in property testing. It asks which properties can be _tested_ more
efficiently than they can be _learned_. _Distribution-free sample-based
property testing_ is the property testing model corresponding to standard PAC
learning, so understanding testing vs. learning in this model is essential for
many of the standard motivations for property testing [GGR98]. Recent progress
on testing vs. learning used connections to distribution testing to get new
upper bounds [GR16] and lower bounds [ES20, BFH21, CP22] on property testing,
exhibiting in particular an equivalence between property and distribution
testing for _symmetric_ properties of functions $[n]\to\\{0,1\\}$ (i.e.
properties which are closed under permutations on $[n]$) [GR16, BFH21]. But
these techniques fall short of answering the testing vs. learning question for
important properties like $k$-alternating functions and halfspaces, because
these properties are non-symmetric and do not allow the same equivalences,
which leaves a gap between the lower bounds of [BFH21] and the upper bounds
from PAC learning that requires new techniques to resolve.

Distribution testing under the parity trace overcomes some of the limitations
of [BFH21] by giving us the first equivalence between distribution testing and
testing _non-symmetric_ properties. We recover many of the lower bounds of
[BFH21] using a different technique with stronger consequences for testing vs.
learning, and we also get new tight positive results for distribution-free
sample-based testing of joint function-distribution properties, adding to the
short list of positive results on distribution-free sample-based testing
[GR16, RR20, RR21, BFH21].

##### 3\. Property testing for trace reconstruction.

Trace reconstruction is a beautiful problem posed in [Lev01, BKKM04]. Relevant
to us is trace reconstruction under the _deletion channel_ , which has
recently received significant attention (e.g. [HMPW08, DOS17, NP17, HL20,
KMMP21, GSZ22, CDL+22, Rub22, CDL+23]). The problem is this: There is a string
$x\in\\{0,1\\}^{N}$ and a deletion rate $\delta\in(0,1)$. A random _trace_ is
obtained from $x$ by deleting each character independently with probability
$\delta$ to produce a substring. The algorithm is given a sequence of
independent traces and it must reconstruct the string $x$ using as few traces
as possible. The problem is often motivated by computational biology, where
this is a simplified model of the way biologists typically have access to DNA
strings: the “true” DNA is not available, but instead there are a number of
corrupted copies. See [BPRS20] for a survey on biological applications.

Trace reconstruction is notoriously difficult to analyze, with a huge gap
between the best known lower bound of $\widetilde{\Omega}(N^{3/2})$ [Cha21a]
and upper bound of $\exp(\widetilde{O}(N^{1/5}))$ [Cha21b] (where the hidden
constants depend on $\delta$). However, if the goal is to make a decision
about the unknown string $x$, complete _reconstruction_ may be unnecessary. We
propose _property testing_ in the trace reconstruction model, which, to our
knowledge, has not yet been studied. The goal is simply to make a decision
about $x$ from its traces, without reconstructing $x$ completely. In terms of
the standard biological application, we wish to make a decision about a DNA
string, from a number of corrupted copies, _without_ reconstructing it. We
prove the first non-trivial property testing results for trace reconstruction,
which follow from an equivalence to distribution testing under the parity
trace.

##### This paper.

Standard distribution testing algorithms make their decisions based on the
_histogram_ , which counts the number of times each element of the domain
occurs in the sample. The common challenge in each of the problems above is
that, to apply distribution testing, the tester needs to handle a certain
structured mislabeling of the sample that prevents it from constructing the
histogram. _Distribution testing under the parity trace_ is an abstraction of
this challenge. The purpose of this paper is to relate this model to the
problems above, and to begin understanding the model by proving tight bounds
on the most fundamental distribution testing task, _testing uniformity_. This
is significantly more difficult to analyze than in the standard model, and we
believe it is necessary before advancing to some more difficult problems that
we will discuss.

###  1.1 Distribution Testing under the Parity Trace

Let us now define distribution testing under the parity trace. Let $\Pi$ be a
property (i.e. set) of probability distributions over $\mathbb{N}$. As in
standard distribution testing, for a distribution $\pi$ over $\mathbb{N}$, a
distribution tester under the parity trace must accept (with probability
$2/3$) any input $\pi\in\Pi$, and reject (with probability $2/3$) any input
$\pi$ that is $\epsilon$-far from $\Pi$, meaning that its distance to any
$\pi^{\prime}\in\Pi$ is at least $\epsilon$. (Standard distribution testing
often uses the total variation distance, but we will see that this is not the
natural choice in this case.) Instead of receiving a sample $S$ from the
distribution $\pi$, the tester receives the _parity trace_ of $S$, denoted by
$\mathsf{trace}(S)$, defined as follows. For any multiset $S\subset\mathbb{N}$
of size $m$, put $S=\\{x_{1},x_{2},\dotsc,x_{m}\\}$ in sorted order $x_{1}\leq
x_{2}\leq\dotsm\leq x_{m}$, and write $\mathsf{par}(x)\vcentcolon=(x\mod 2)$
for the parity of $x$. Then

$\mathsf{trace}(S)\vcentcolon=(\mathsf{par}(x_{1}),\mathsf{par}(x_{2}),\dotsc,\mathsf{par}(x_{m}))\,.$

For example, on sample $S=\\{5,1,6,2,4,2\\}$, the algorithm receives
$\mathsf{trace}(S)=100010$, which is the string of parities of
$(1,2,2,4,5,6)$. Notice that, for example, the uniform distribution over
$\\{1,\dotsc,n\\}$ and the uniform distribution over $\\{n+1,\dotsc,2n\\}$ are
indistinguishable under the parity trace when $n$ is even, although they have
total variation (TV) distance 1, so it is not obvious _a priori_ which
distribution testing tasks are even possible under the parity trace.

##### Testing uniformity.

To begin understanding the parity trace, consider the problem of _testing
uniformity_ (e.g. [GR00, Pan08, ADK15, DKN15b], see [Can22]). The goal is to
accept the uniform distribution over $[2n]$ and reject the distributions over
$[2n]$ that are $\epsilon$-far from uniform. One may see that testing
uniformity under the parity trace is indeed possible, even with respect the TV
distance, using a coupon-collector argument. After receiving a trace of size
$\Theta(n\log n)$, with high probability the trace either included every
element of the domain $[2n]$, or it can safely reject. If the trace included
every element of the domain, the algorithm can deduce the exact identity of
each sample point, and simulate the standard distribution tester, giving a
bound of $O(n\log n+\sqrt{n}/\epsilon^{2})$, which follows from the tight
$\Theta(\sqrt{n}/\epsilon^{2})$ bound in the standard model [Pan08, VV17a,
DGPP18, DGPP19].

It is not immediately clear whether a sample of size $o(n)$ suffices. The main
technical contribution of this paper is to establish tight bounds on this
problem: sublinear sample size is indeed achievable, but the problem exhibits
a gap between the standard model and the parity trace model. We discuss the
proof in Sections 1.2 and 1.5, as the confused collector model will serve as a
warm-up.

######  Theorem 1.1 (Informal; see Theorem 4.1).

Testing uniformity of distributions on domain $[2n]$ under the parity trace,
with respect to the TV distance, requires sample size
$\widetilde{\Theta}\left(\left(\frac{n}{\epsilon}\right)^{4/5}+\frac{\sqrt{n}}{\epsilon^{2}}\right)$.

##### Edit distance.

Theorem 1.1 uses the TV distance, but this is not always possible. Two
distributions may have TV distance 1 while being indistinguishable under the
parity trace, so TV distance is not the most natural metric, and we require a
new one in order to relate the parity trace model to the other problems
discussed in this paper. We define the _edit distance_ pseudo-metric for
distributions, which has the desired property that two distributions $\pi$ and
$\pi^{\prime}$ are indistinguishable under the parity trace, if and only if
the edit distance is 0. We think of a distribution $\pi$ over $\mathbb{N}$ as
an alternating “fractional string”,

$1^{\pi(1)}0^{\pi(2)}1^{\pi(3)}\dotsm 1^{\pi(2i-1)}0^{\pi(2i)}\dotsm$

where $b^{p}$ indicates that $b$ is repeated $p$ times (which is fractional).
Then the parity trace of size $m$ from $\pi$ is obtained by sampling $m$
independent random characters proportional to their fractional number of
repetitions $p$, and concatenating them in order. The distribution of the
parity trace is invariant under certain “free” edit operations, like $b^{p}\to
b^{p/2}b^{p/2}$, $a^{p}c^{q}\to a^{p}b^{0}c^{q}$, or $a^{p}b^{0}c^{q}\to
a^{p}c^{q}$, while other “expensive” edit operations like $b^{p}c^{q}\to
b^{p-\delta}c^{q+\delta}$ may change the distribution of the trace. The edit
distance is the cost of transforming one distribution into another; see
Definition 6.10.

###  1.2 Distribution Testing with a Confused Collector

We introduce the _confused collector_ to model distribution testing problems
where the algorithm receives a random sample $S$ that has been systematically
mislabeled; recall the examples on the first page. To formalize the problem,
imagine that for each two elements $x$ and $y$ in the domain, there is some
probability that all appearances of $x$ and $y$ in the sample $S$ have been
joined and counted together. These joins must be transitive, so the
probabilities that the pairs $(x,y)$, $(y,z)$, or $(x,z)$ are joined are not
independent. That means there must be some structured random process that
joins the domain elements, which we choose to model as follows.

Let $p$ be a distribution over a (finite) structured domain $V$, whose
structure is given by a “base graph” $G=(V,E)$. For example, $G$ could be a
tree representing the taxonomy of a collection of fauna. The distribution
testing algorithm has a parameter $\eta\in(0,1]$ called the _resolution_
(representing the accuracy of the classifier), and it receives a random sample
$S$ of size $m$ produced as follows. First sample a subgraph $H$ of $G$ by
including each edge $uv\in E$ with probability $1-\eta$, and let
$C_{1},\dotsc,C_{t}$ be its connected components. For each $C_{i}$, let
$c_{i}\in C_{i}$ be an arbitrary representative of the component. Then sample
a set $S^{\prime}$ of $m$ independent points from $p$ and label each $s\in
S^{\prime}$ with the representative $c_{i}$ of its component. The resulting
sample $S$ is given to the algorithm. Note that, with resolution $\eta=1$, the
graph $H$ is an independent set and each element is given its proper label, so
the model becomes the standard distribution testing model.

Given a property $\Pi$ of distributions over $V$ and parameter $\epsilon$, a
tester for $\Pi$, with resolution $\eta$ and sample complexity $m$, must
accept (with probability222Unlike standard testers, we cannot simply repeat
the tester to boost the success probability, which depends partly on the
resolution $\eta$. $2/3$) any distribution in $\Pi$, and reject (with
probability $2/3$) any distribution that is $\epsilon$-far in TV distance from
all distributions in $\Pi$.

##### Results.

We get results when the base graph $G$ is a cycle or path, which capture
situations where the domain is $[n]$ and domain elements are distinguishable
only if a random “separator” occurs between them (like the fossil example
given on the first page, or if the sample labels have been randomly hashed by
a monotone hash function333A monotone hash function is one that preserves the
order of the keys, see e.g. [AFCK23]).

######  Theorem 1.2 (Informal; see Theorem 3.23.).

Let $G=(V,E)$ be a path or cycle on $n$ vertices, let
$\epsilon\geq\widetilde{\Omega}(n^{-1/4})$ and
$\eta\geq\widetilde{\Omega}(n^{-1/5}\epsilon^{-4/5})$. Then testing uniformity
requires $\widetilde{O}\left(\frac{\sqrt{n}}{\epsilon^{2}\eta^{3/2}}\right)$
samples.

This interpolates between the optimal $\Theta(\sqrt{n}/\epsilon^{2})$ bound
for uniformity testing with resolution $\eta=1$, and
$\widetilde{O}\left((n/\epsilon)^{4/5}\right)$ when $\eta$ is as small as the
theorem allows444Note that a lower bound on $\eta$ in the theorem is
necessary. For example, a sample of woodland fauna labeled by the authors
would have resolution $\eta=0$ and no decisions could be made based on this,
regardless of sample size..

##### Techniques.

We describe our techniques for Theorems 1.1 and 1.2 in more detail in Section
1.5, but briefly mention the main idea here. Theorem 1.2 serves as a sort of
warm-up to Theorem 1.1, which is proved by considering a similar problem on
the _weighted_ cycle, although the confused collector poses its own separate
challenges in handling the resolution parameter $\eta$.

Let $\bm{T}_{i}$ denote the multiplicity of element $i$ in the sample. A
standard simplification is to assume that $\bm{T}_{i}$ is distributed as the
independent Poisson $\mathsf{Poi}(m\cdot p(i))$. The random graph $\bm{H}$
introduces dependencies in the observed variables, and we let $\bm{\Phi}$ be
the random Boolean matrix describing these dependences, with
$\bm{\Phi}_{i,j}=1$ iff vertices $i,j$ belong to the same connected component.
Our proof boils down to an analysis of the random quadratic form
$\bm{T}^{\top}\bm{\Phi}\bm{T}$. While concentration bounds for quadratic forms
$\bm{X}^{\top}A\bm{X}$ have been studied (including Hanson-Wright type
inequalities, see e.g. [GSS21]), we are not aware of bounds when the matrix
$A$ is itself random, and inequalities of the type we require may be of
independent interest. See Section 1.5 for more details.

##### Related Work.

Similar models have been proposed independently in the recent literature on
machine learning and distribution testing, with similar motivations. See
[FKKT21] and references therein for a discussion of the applied literature.
[FKKT21] propose a different model from ours, where the partition of the
domain is more general, but it is resampled independently for each sample
point555The reason for the difference is, briefly, that [FKKT21] assume sample
points may be labeled by different entities with different classifications,
while we assume sample points are labeled by one entity with imperfect
classification., and they study questions of learning. In distribution
testing, [GR22, CFG+22] study a model where the sample contains “huge
objects”, which themselves support queries, so again the algorithm is not
given the histogram, and must perform queries on its sample. [CW21] studies
systematic mislabelings that are guaranteed to be permutations. In [CW20], the
goal is to test if there exists a partition into intervals that makes the
input distribution $p$ equal to a reference distribution $q$. Other models
with imperfect information about the samples include locally private testing
[GR18, She18, ACFT19] and inference under information constraints [ACT19,
ACT20, ACF+21].

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

We are interested in the fundamental _testing vs. learning_ question of
[GGR98], especially in the distribution-free sample-based property testing
model corresponding to standard PAC learning. This is essential for some
proposed applications of property testing, like model selection (i.e.
selecting an appropriate hypothesis class $\mathcal{H}$ for learning) [GGR98].
Formal connections between property testing and distribution testing, which we
believe are essential for understanding the testing vs. learning question,
were first articulated by [GR16], but their results applied only to
_symmetric_ properties of functions (i.e. properties closed under permutations
on the domain).

As noted in [GGR98, BFH21], testing vs. learning is essentially _testing vs.
VC dimension_ , since the sample size required for PAC learning a hypothesis
class $\mathcal{H}$ (ignoring the error $\epsilon$) is $\Theta(\mathsf{VC})$,
where $\mathsf{VC}$ is the VC dimension of $\mathcal{H}$. Therefore, the goal
is to determine which classes $\mathcal{H}$ can be tested using
$o(\mathsf{VC})$ samples. For many important hypothesis classes, including
halfspaces over $\mathbb{R}^{n}$, and $k$-alternating functions over
$\mathbb{R}$, [BFH21] show a lower bound of
$\Omega\left(\frac{\mathsf{VC}}{\log\mathsf{VC}}\right)$ by defining the
“lower VC dimension” and using it to construct a reduction from _support-size
distinction_ (see [RRSS09, VV11, WY19]), which is the problem of deciding
whether a distribution on $[n]$ has support size at most $\alpha n$ or at
least $\beta n$. The bound is tight in some cases, due to an
$O\left(\frac{\mathsf{VC}}{\log\mathsf{VC}}\right)$ bound of [GR16] for some
symmetric properties, reducing in the other direction to testing support size.

This leaves a gap between the sample size required for testing and learning
many of the most important hypothesis classes, like halfspaces. As in [GR16],
we consider the gap between
$\Omega\left(\frac{\mathsf{VC}}{\log\mathsf{VC}}\right)$ and $O(\mathsf{VC})$
to be significant; firstly because it leaves open the question of whether
testing can be done with sample size _sublinear_ in the sample size required
for PAC learning, and secondly because of the relationship to distribution
testing, especially support-size estimation, where this log factor is
surprising and important [RRSS09, VV11, WY19]. Unfortunately, the technique of
[BFH21] cannot close this gap, because, informally speaking, the tightness of
the relationship between distribution testing and property testing reaches its
limit at the symmetric properties.

Our goal is to develop a stronger relationship between distribution testing
and property testing that surpasses this limitation. Distribution testing
under the parity trace is a step towards this goal. Consider the (non-
symmetric) property of $k$-alternating functions, which are the functions
$\mathbb{R}\to\\{0,1\\}$ which alternate between 0 and 1 at most $k$ times
(equivalently, the class of unions of $k$ intervals), studied in [KR00, Nee14,
BBBY12, BH18, CGG+19, BFH21], for which the testing vs. learning question
remains open. A first example of our technique is the following:

######  Theorem 1.3 (Informal; see Theorem 6.38).

Let $m_{1}(k,\epsilon)$ be the sample size required to test if a distribution
has support size $k$, or is $\epsilon$-far in _edit distance_ from having
support size $k$, under the parity trace. Let $m_{2}(k,\epsilon)$ be the
sample size required to test if a function is $k$-alternating in the
distribution-free sample-based model. Then
$m_{1}(k,\epsilon)=\Theta(m_{2}(k,\epsilon))$.

This is the first tight relationship between distribution testing and property
testing for a _non-symmetric_ property, and it is only a special case of a
more general equivalence between distribution testing and testing _density
properties_ , explained below, which is required for our results in the trace
reconstruction model. The appearance of the edit distance highlights its
importance for applications of the parity trace. The authors disagree on what
the correct sample size $m_{1}(k,\epsilon)$ in this theorem should be666In
fact, this doesn’t seem to be known even in the _standard_ model: the best
upper bounds we could find are $O\left(\tfrac{n}{\epsilon^{2}\log n}\right)$
and $O(n/\epsilon)$, compared to a lower bound of
$\Omega\left(\tfrac{n}{\epsilon\log n}\right)$., which we will study in future
work; the current paper focuses on the simpler problem of testing uniformity,
which is already significantly more challenging to analyze in the parity trace
model than the standard model. But, even without knowing $m_{1}(k,\epsilon)$,
we use Theorem 1.3 to recover many of the bounds of [BFH21] using a different
proof that has stronger consequences for the testing vs. learning question. We
state the bounds for $k$-alternating functions and halfspaces, but we also
recover the bounds for intersections of halfspaces, and decision trees777Our
statement includes a dependence on $\epsilon$, which [BFH21] does not. Ours
follows from bounds on the distribution testing problem, but the $\epsilon$
dependence can be appended to the [BFH21] results in a standard way (as in
[ES20]).. (See [MORS10, BBBY12, Har19, CP22] for other prior work on testing
halfspaces.)

######  Theorem 1.4 (See [BFH21]).

Distribution-free sample-based testing $k$-alternating functions on domain
$\mathbb{R}$ requires $\Omega(\tfrac{k}{\epsilon\log k})$ samples, and testing
halfspaces on domain $\mathbb{R}^{n}$ requires $\Omega(\tfrac{n}{\epsilon\log
n})$ samples.

Unlike the technique of [BFH21], it is possible that our technique can lead to
better answers for testing vs. learning for $k$-alternating functions,
halfspaces, and others. Better lower bounds on distribution testing under the
parity trace would imply better lower bounds for $k$-alternating functions,
halfspaces, intersections of halfspaces, and decision trees. On the other
hand, an $o(\mathsf{VC})$ _upper bound_ on (say) testing halfspaces, would
imply an analog of the surprising $o(n)$ bounds of [VV11, WY19] for
distinguishing support size $\leq\alpha n$ from $\geq n$, which would hold
_even under the parity trace_ , where the tester does not know the identities
of the sample points.

To clarify the connection between distribution testing and distribution-free
sample-based property testing, we expand our view of distribution-free
property testing to allow properties of _labeled distributions_. A labeled
distribution on is a pair $(f,\mathcal{D})$ of a function $f$ and a
distribution $\mathcal{D}$. The idea is that one may wish to test not only a
property of a function $f$, but a joint property of the function $f$ and
probability distribution $\mathcal{D}$. (We also point the reader to a
different interesting type of joint function-distribution testing in [RV23,
GKK23].)

For example, we may wish to test not only whether $f$ is $k$-alternating, but
that it also evenly partitions $\mathcal{D}$ into uniform monochromatic
intervals. We call these the _uniformly $k$-alternating_ functions, and we get
a tight result for testing uniformly $2k$-alternating functions (assuming the
input is promised to be $2k$ alternating). This adds to the short list of
positive results in distribution-free sample-based testing [GR16, BFH21, RR20,
RR21].

######  Theorem 1.5 (Informal; see Theorem 6.33).

Let $f$ be $2k$-alternating. Then testing if it is _uniformly_
$2k$-alternating with respect to the TV distance requires
$\widetilde{\Theta}((k/\epsilon)^{4/5}+\sqrt{k}/\epsilon^{2})$ samples.

(For the more challenging non-promise version of this problem, we get a bound
of $O(\tfrac{k}{\epsilon}+\tfrac{k}{\epsilon^{2}\log k})$ by defining a
suitable “testing-by-learning” reduction for labeled distributions and using
the tolerant uniformity tester of [VV17a]; see Lemma 6.35). The proof of
Theorems 1.5 and 1.3 use an equivalence to distribution testing under the
parity trace that holds in general for a natural class of labeled
distributions that we call _density properties_.

##### Density properties.

Informally888For simplicity, this discussion ignores the possibility of
infinitely many alternation points., every Boolean function
$f:\mathbb{R}\to\\{0,1\\}$ has a unique set of _alternation points_ in
$\mathbb{R}$ where it changes value from 0 to 1 or vice-versa. A _density
property_ is a set of labeled distributions where membership of
$(f,\mathcal{D})$ is determined by its _density sequence_ : the sequence of
probability masses $\mathcal{D}(a,b]$ where $a,b$ are consecutive alternation
points of $f$.

$k$-Alternating and uniformly $k$-alternating functions are both definable as
density properties, but there are many other interesting examples. The
difficulty in testing density properties is that the tester does not know
_which_ interval of alternation points a sample belongs to. Given two sample
points $x,y\in\mathbb{R}$, the tester does not know if $x,y$ belong to the
same interval or different intervals, unless $f(x)\neq f(y)$, or $f(x)=f(y)$
and there is another sample point $z$ between $x$ and $y$ with $f(z)\neq
f(x)$. Prior work has used _queries_ to overcome this difficulty [CGG+19], but
this is not possible in the sample-based model.

Distribution testing under the parity trace captures this difficulty: testing
density properties is essentially equivalent to testing distributions under
the parity trace. For any density property $\Xi$, let $\Pi(\Xi)$ be the set of
density sequences (i.e. probability distributions) that define $\Xi$. Using
Ramsey theory (inspired by [Fis04, DKN15a], see also [CW20]), we prove:

######  Lemma 1.6 (Informal; see Lemma 6.26).

Testing $\Xi$ in the labeled-distribution model, with respect to an
appropriate analogue of _edit distance_ , is equivalent to testing $\Pi(\Xi)$
under the parity trace with respect to the edit distance.

##### Techniques.

The key contributions here are the definitions of edit distance and the parity
trace, which allow sample-based property testing to be related to distribution
testing using an application of Ramsey theory in Lemma 1.6. The main results
in this section (including the recovery of the results of [BFH21]) then follow
by reductions that mainly rely on properties of the edit distance.

###  1.4 Property Testing for Trace Reconstruction

We now turn to property testing for trace reconstruction, which had interested
us separately from the other problems in this paper, and the formal connection
we present here was unexpected. In the trace reconstruction problem (with the
deletion channel), there is a string $x\in\\{0,1\\}^{N}$ and a deletion rate
$\delta\in(0,1)$. A _trace_ $\bm{T}$ of $x$ is obtained by deleting each
character of $x$ independently with probability $\delta$ and taking the
resulting substring. For example, a trace of $x=110011001100$ might look like
$11110000$ or $101010$. The goal is to reconstruct $x$ using as few
independent traces as possible (see references above).

We are interested in making decisions about $x$ _without_ completely
reconstructing it, so we propose property testing in the trace reconstruction
model. For a property $\Psi$ of strings $\\{0,1\\}^{N}$, the algorithm should
accept (with probability $2/3$) strings $x\in\Psi$, and reject (with
probability $2/3$) strings that are _far_ from $\Psi$. A natural choice of
metric is the (relative999The relative edit distance between two strings of
length $N$ is $\frac{1}{N}$ times the edit distance.) edit distance on
strings, which is the standard choice for _approximate_ trace reconstruction
[CDL+22]. The edit distance on strings is closely related to our notion of
edit distance on probability distributions.

To measure the complexity of a trace tester, we consider both the _number of
traces_ , and the _expected size_ of each trace. Trace reconstruction is
usually studied with _constant_ deletion rate $\delta$, corresponding to
traces of expected size $\Theta(N)$. For testing, we hope to permit extremely
high deletion rates, so that traces have expected size $\rho N=o(N)$ where
$\rho=1-\delta$ is the _retention rate_ (which puts our study in the same low-
retention-rate regime as the recent independent work [CDL+23] on trace
reconstruction). This is consistent with conventional property testing
problems, where the goal is to make a decision while seeing less than a
constant fraction of the input. We relate this problem to distribution testing
under the parity trace and labeled-distribution testing, and give results for
three trace testing problems, which appear to be the first results on this
type of problem (the most similar problem in prior work is distinguishing
between two arbitrary strings $x,y$ that are close in Hamming- or edit
distance [GSZ22]).

##### Results.

To initiate the study of property testing for trace reconstruction, we prove
bounds on testing three basic properties of strings. For $n\in\mathbb{N}$, we
say that $x\in\\{0,1\\}^{N}$ is an _$n$ -block string_ if $x$ consists of at
most $n$ consecutive _blocks_ , where a block is a (maximal) all-1s string or
all-0s string. The _uniform_ $n$-block strings are those consisting of $n$
blocks of equal length. We give results for:

  1. 1.

Testing if an $n$-block string is a _uniform_ $n$-block string;

  2. 2.

Testing if an arbitrary string is a _uniform_ $n$-block string; and

  3. 3.

Testing if an arbitrary string is an $n$-block string.

These results use general two-way reductions between trace testing and
distribution testing under the parity trace (Lemmas 7.9 and 7.24). The naïve
application of our reduction gives an upper bound for testing with a _single_
trace, which corresponds to the single-trace approximate reconstruction
problem whose study was initiated in concurrent and independent work [CDL+23].
Our main application uses an additional trick to apply the reduction, which
gives a bound for an arbitrary number of traces. Observe that even when the
number of blocks $n$ is large, e.g. $n=\Theta(N)$, we can still test the
property with a _single_ trace of sublinear size (i.e. deletion rate
$\delta=1-o(1)$).

######  Theorem 1.7 (Informal; see Theorems 7.19 and 7.25).

Suppose $x\in\\{0,1\\}^{N}$ is promised to be an $n$-block string. For any
$k$, trace testing whether $x$ is a uniform $n$-block string, or
$\epsilon$-far from a uniform $n$-block string in relative edit distance, can
be done with $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)$.
Meanwhile, for large enough $N$, we must have $k\rho
N=\widetilde{\Omega}\left(\frac{n^{4/5}}{\epsilon^{4/5}}+\frac{\sqrt{n}}{\epsilon^{2}}\right)$.

We find it convenient to measure complexity using the expected size of each
trace, but one may rephrase our result in more conventional trace
reconstruction language by saying that for fixed $k$, if $\rho_{k}\cdot N$ is
the bound on expected trace size, then for all retention rates
$\rho\geq\rho_{k}$, the number of traces required for testing is at most $k$.
Increasing the number of traces $k$ allows the tester to handle smaller
retention rates, but the total number of observed bits $k\rho N$ will
increase.

For the final two results, we do not have tight bounds for the corresponding
distribution testing problems under the parity trace, but we get non-trivial
bounds that beat the coupon-collector argument, almost “for free” from the
theory we have developed. For the labeled-distribution testing model (Section
1.3), we show that a “testing-by-learning” reduction holds, similar to the
standard reduction of [GGR98], by defining a “proper learner-and-verifier
pair” that uses a distribution testing task instead of the “verification step”
of [GGR98]. We then use Lemma 1.6, and the relationship to trace testing, to
get a general “testing-by-learning” technique for trace testing.

######  Theorem 1.8 (Informal; see Theorem 7.15).

Testing whether $x\in\\{0,1\\}^{N}$ is a uniform $n$-block string, or
$\epsilon$-far in relative edit distance from the uniform $n$-block strings,
can be done with a single trace of expected size $\rho
N=O\left(\frac{n}{\epsilon}+\frac{n}{\epsilon^{2}\log n}\right)$.

######  Theorem 1.9 (Informal; see Theorems 7.13 and 7.26.).

Testing whether $x\in\\{0,1\\}^{N}$ is an $n$-block string, or $\epsilon$-far
in relative edit distance from all $n$-block strings, can be done with a
single trace of expected size $\rho N=O(n/\epsilon)$, while for large enough
$N$, any trace tester using $k$ traces must satisfy $k\rho N=\Omega(n/\log
n)$.

Theorem 1.8 uses the tolerant tester for uniformity from [VV17b] in the
“verification step” of the testing-by-learning reduction, while Theorem 1.9
uses the $O(k/\epsilon)$ upper bound for testing $k$-alternating functions
which follows from the VC dimension. We find these bounds somewhat mysterious,
because our testing-by-learning reduction for trace testing goes through the
non-constructive Ramsey theory argument of Lemma 1.6 and therefore the trace
testers, which do not know the positions of the characters of the trace, are
obtained non-constructively from a labeled-distribution learner and verifier
that strongly rely on knowing the absolute positions of the sample points.

###  1.5 Proof Overview

We briefly describe our proofs for testing uniformity under the parity trace
and with a confused collector, Theorems 1.1 and 1.2.

##### Upper bounds.

Let us review the standard uniformity tester [GR00, DGPP19] (see also
[Can22]). Let $p$ be the input distribution over $[n]$. For a sample $S$ of
size $m$, let $X_{i}$ be the multiplicity of element $i$ in $S$. The tester
counts the number of “collisions” in the sample: it computes
$Y\vcentcolon=\frac{1}{m(m-1)}\sum_{i=1}^{n}X_{i}(X_{i}-1)$, and rejects if
this is too large. This works because
$\mathbb{E}\left[\bm{Y}\right]=p^{\top}p=\|p\|_{2}^{2}$, which is large when
$p$ is far from uniform. Now we describe the tester for the confused
collector. For input distribution $p$ on domain $\mathbb{Z}_{n}$ (which are
the vertices of the path or cycle), we use the standard simplification that
element $j$ occurs in the sample with multiplicity
$\bm{T}_{j}\sim\mathsf{Poi}(mp_{j})$ independently of the other elements. Now
redefine $\bm{X}_{i}$ as the number of sample points contained in the $i^{th}$
connected component of $\bm{H}$, which the tester cannot distinguish: the
$\bm{X}_{i}$ variables remain Poisson, but they are not independent. The
tester computes a “collision count”, as in the standard algorithm:

$\bm{Y}\vcentcolon=\frac{1}{m}\sum_{i}\bm{X}_{i}(\bm{X}_{i}-1)=\frac{1}{m}\left(\bm{T}^{\top}\bm{\Phi}\bm{T}-\|\bm{T}\|_{1}\right)\,,$

where $\bm{\Phi}$ is the random Boolean matrix with $\bm{\Phi}_{i,j}=1$ iff
$i,j$ belong to the same connected component of $\bm{H}$. The expected value
is $\mathbb{E}\left[\bm{Y}\right]=m\cdot p^{\top}\phi p$ where
$\phi=\mathbb{E}\left[\bm{\Phi}\right]$, and we show that this is again large
when $p$ is far from uniform, using spectral analysis of the matrix $\phi$
which is either Toeplitz (for paths) or circulant (for cycles). To complete
the analysis, we require a concentration inequality for the random quadratic
form $\bm{T}^{\top}\bm{\Phi}\bm{T}-\|\bm{T}\|_{1}$, which we obtain as long as
$p$ is not too “highly concentrated” in any interval (which the algorithm can
test separately); see Lemma 3.21:

$\mathbb{P}\left[|\bm{Y}-\mathbb{E}\left[\bm{Y}\right]|\geq
t\right]\leq\frac{\|p\|_{2}^{2}}{\eta t^{2}}\cdot\operatorname{poly}\log n\,.$
(1)

Extending the result to the parity trace is more challenging. On domain
$[2n]$, we separate the input distribution $\pi$ into the “odd part” $p$ and
“even part” $q$, so
$\pi=\pi(p,q)=(p_{1},q_{1},p_{2},q_{2},\dotsc,p_{n},q_{n})$. The tester
receives a trace of the form

$\mathsf{trace}(S)=1^{X_{1}}0^{Z_{1}}1^{X_{2}}0^{Z_{2}}\dotsc
1^{X_{t}}0^{Z_{t}}\,,$

where each $X_{i},Z_{i}$ is the length of a consecutive “run” of 1s or 0s in
the trace (i.e. $X_{i},Z_{i}>0$ except we may have $X_{0}=0$ or $Z_{t}=0$). By
analogy to the standard tester, the natural thing to try is to compute the
number of “collisions”
$\sum_{i=1}^{n}X_{i}(X_{i}-1)+\sum_{i=1}^{n}Z_{i}(Z_{i}-1)$ and pray that it
works, which it does, more or less. Our tester considers the runs of 1s and 0s
separately: first, we think of $p$ as being a distribution over the vertices
of a cycle, with $q$ giving weights to the edges. If $q$ was uniform, the
analysis for the confused collector would now apply, but it may not be.

To handle this, we define the _uniform conjugate_ of $q$ and denote it by
$\tilde{p}$. Informally, $\tilde{p}$ is the “worst case” instance of $p$ that
makes every connected component of $\bm{H}$ (sampled according to the weights
determined by $q$) have the same expected mass $\tau$, which would minimize
$\mathbb{E}\left[\bm{Y}\right]$. We essentially calculate a closed form
solution for $\tilde{p}$ with
$\tau=\frac{1-\|q\|_{1}}{\sum_{i=1}^{n}\tanh(mq_{i}/2)}$ by approximating the
process of sampling components of $\bm{H}$ with a Markov process (for which
the use of a cycle instead of a path is helpful). Then we write
$p=\tilde{p}+z$ and, crucially, use the deviation $z$ from the uniform
conjugate to control both the mean and variance of $\bm{Y}$. We get an analog
of equation (1) that holds under some conditions on $p,q$ that the algorithm
can test separately; see Lemma 4.21:

$\mathbb{P}\left[|\bm{Y}-\mathbb{E}\left[\bm{Y}\right]|\geq
t\right]\leq\frac{\tfrac{1}{m}+z^{\top}\phi
z}{t^{2}}\cdot\operatorname{poly}\log n\,.$ (2)

The main condition that the algorithm must test separately is that $p$ is not
too “highly concentrated” relative to $q$, meaning that there is no interval
where $p$ and $q$ are both sufficiently large but $p$ is much larger than $q$.
The algorithm repeats these tests with the roles of $p$ and $q$ reversed.

##### Lower bound.

To get the lower bound in Theorem 1.1, consider an adversary who flips a
random bit $\bm{Z}$ and gives the algorithm a input distribution sampled from
“meta-distribution” $\mathcal{D}_{\bm{Z}}$, where $\mathcal{D}_{0}$ and
$\mathcal{D}_{1}$ are constructed out of _dominoes_ as follows. A domino is a
4-element piece $(p_{i},q_{i},p_{i+1},q_{i+1})$ of a distribution
$\pi(p,q)=(p_{1},q_{1},p_{2},q_{2},\dotsc,p_{n},q_{n})$, so that $\pi(p,q)$ on
domain $[2n]$ is made of $n/2$ dominoes. We use the dominoes
$(\tfrac{1}{2n},\tfrac{1}{2n},\tfrac{1}{2n},\tfrac{1}{2n})$,
$(\tfrac{1-\epsilon}{2n},\tfrac{1}{2n},\tfrac{1+\epsilon}{2n},\tfrac{1}{2n})$,
and
$(\tfrac{1+\epsilon}{2n},\tfrac{1}{2n},\tfrac{1-\epsilon}{2n},\tfrac{1}{2n})$.
$\mathcal{D}_{0}$ contains only the uniform distribution ($n/2$ copies of the
first domino), while $\mathcal{D}_{1}$ is obtained by a sequence of $n/2$
random choices from the last two dominoes.

We use an information-theoretic argument inspired by [DK16], to show that the
algorithm receives insufficient information about $\bm{Z}$ unless it receives
$\widetilde{\Omega}((n/\epsilon)^{4/5})$ samples. The tester gains no
information about $\bm{Z}$ from any domino receiving fewer than 3 sample
points. We use the chain rule of information over small-enough sequences of
dominoes, and use bounds on the number of dominoes receiving 3 sample points
to bound the information from each small-enough sequence.

###  1.6 Discussion & Open Problems

The reader may notice three unfortunate negative qualities of this paper: The
upper bounds have $\widetilde{O}(\cdot)$ instead of $O(\cdot)$; the testing
algorithms have more than 1 step; and the number of pages seems excessive. We
suspect that these three birds can be killed with one stone, if one could
prove tighter, unconditional concentration bounds on the quadratic forms
$\bm{T}^{\top}\bm{\Phi}\bm{T}$.

Regarding the testing vs. learning question, the next step is to prove tight
bounds on testing support size under the parity trace, which would either give
better lower bounds for $k$-alternating functions (and therefore halfspaces
and intersections of halfspaces) or possibly a surprising $O(k/\log k)$ upper
bound for $k$-alternating functions. We intend to study this in follow-up
work.

Our results for the confused collector were limited to paths and cycles, due
to the connection to the parity trace, but we suspect that a similar upper
bound holds for trees, which we think would be the next most natural problem
in this model, given the ubiquity of tree-structured data.

Density properties are a natural class of properties where property testing is
equivalent to distribution testing under the parity trace. Adapting other
distribution testing results, like testing monotonicity ([BKR04, CDGR18]), to
the parity trace model, would imply new results in distribution-free sample-
based testing (for labeled-distributions), and the trace reconstruction model.

We consider property testing in the trace reconstruction model to be one of
the main conceptual contributions of this paper. We have shown that testing
properties of $n$-block strings is related to distribution testing under the
parity trace and testing density properties in the labeled-distribution
testing model. Other interesting properties to study would be subsequence-
freeness (with non-binary alphabet), which could possibly build on recent work
in sample-based testing [RR21], or testing regular languages, which are
testable in the standard query model (e.g. [AKNS01, BS21]) and which are
already related to trace reconstruction [Cha21b].

##  2 Preliminaries and Common Framework for Upper Bounds

In this section, we give the formal definitions for the parity trace and
confused collector models of distribution testing, and we introduce a common
terminology and framework for analyzing our algorithms in these models. The
section is organized as follows: Section 2.1 introduces notation we use
throughout the paper. Sections 2.2 and 2.3 define the confused collector and
parity trace models of distribution testing, respectively. Section 2.4
introduces unifying vocabulary that views these two models as outcomes from
Poisson random variables on certain path- and cycle-structured domains. Then
Section 2.5 uses this vocabulary to establish generic results that will be
specialized into our upper bounds for the confused collector and parity trace
models in the subsequent sections.

###  2.1 Notation

In this paper, $\log x$ denotes the natural logarithm of $x$. $\mathbb{N}$
denotes the set of positive integers, i.e. it does not include 0. For any $x$,
we write $\mathbb{Z}_{>x}$ for the set of integers greater than $x$, and
$\mathbb{Z}_{<x},\mathbb{Z}_{\geq x},\mathbb{Z}_{\leq x}$ are defined
similarly. We denote random variables by boldface symbols, e.g. $\bm{X}$. We
write $x=a\pm b$ as a shorthand for $a-b\leq x\leq a+b$. For an event $E$,
$\mathds{1}\left[E\right]$ is the indicator variable for $E$, which takes
value 1 if and only if $E$ occurs.

For a distance metric $\mathsf{dist}(\cdot,\cdot)$ on a domain $\mathcal{X}$,
an element $y\in\mathcal{X}$, and a set $X\subseteq\mathcal{X}$, we write

$\mathsf{dist}(y,X)\vcentcolon=\inf_{x\in X}\mathsf{dist}(y,x)\,.$

For a probability distribution $\mathcal{D}$ over (countable) domain
$\mathcal{X}$ and any set $S\subseteq\mathcal{X}$, we write
$\mathcal{D}(S)=\sum_{x\in S}\mathcal{D}(x)$.

Given a probability distribution $\pi$ and $m\in\mathbb{N}$, we will write
$\bm{S}\sim\mathsf{samp}(\pi,m)$ for the distribution over multisets $S$
obtained by drawing $m$ independent samples from $\pi$.

For a fixed domain $\mathcal{X}$ and set $\Pi$ of probability distributions
over $\mathcal{X}$, we will write $\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi)$
to denote the set of distributions $\pi$ over $\mathcal{X}$ such that
$\mathsf{dist}_{\mathsf{TV}}(\pi,\Pi)>\epsilon$. We will use a similar
notation for other domains such as classes of labeled distributions $\Xi$ and
strings $\Psi$, and for other applicable (pseudo)-metrics (e.g.
$\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi)$ for distributions that are far
from $\Pi$ in edit distance).

We will often use the notations
$\stackrel{{\scriptstyle\mathclap{\mbox{?}}}}{{\geq}}$,
$\stackrel{{\scriptstyle\mathclap{\mbox{?}}}}{{\leq}}$,
$\stackrel{{\scriptstyle\mathclap{\mbox{?}}}}{{=}}$ , etc., within proofs,
when stating an (in)equality that will be established later on in the proof.

###  2.2 Confused Collector: Definition & Terminology

We will introduce the general confused collector model, although for this
paper we will be interested only in path- and cycle-structured domains. The
confused collector model on these domains also serves as a warm-up to the
parity trace, so we introduce and analyze it first. Standard practice in
distribution testing is to analyze a “Poissonized” version of the algorithms,
where instead of receiving a $m$ independent random sample points from the
input distribution $\pi$, the algorithm first chooses
$\bm{m}\sim\mathsf{Poi}(m)$ and then samples $\bm{m}$ independent random
points from $\pi$; this means that each point $x$ of the domain appears in the
sample $\mathsf{Poi}(m\cdot\pi(x))$-many times, independently of the other
points. For simplicity, we will define the Poissonized version of the confused
collector (See Appendix A and references therein for more details).

######  Definition 2.1 (Confused Collector Sampling).

Let $G=(V,E)$ be a graph, and let $w:E\to[0,1]$ be a vector of non-negative
weights. We define the following sampling process. A random subgraph $\bm{H}$
of $G$ is chosen by including each edge $e$ independently with probability
$1-w(e)$. Let $\bm{C}_{1},\dotsc,\bm{C}_{k}$ be the connected components of
$\bm{H}$; assign to each $\bm{C}_{i}$ an arbitrary representative vertex
$\bm{c}_{i}$ of $\bm{C}_{i}$.

For a probability distribution $\pi$ (or indeed any non-negative vector
$\pi:V\to\mathbb{R}_{\geq 0}$) and sample-size parameter $m$, we define a
_confused collector sample_ $\bm{S}$ from $\pi$ as follows. $\bm{H}$ is chosen
as above. For each vertex $v\in V$, we sample an independent Poisson random
variable $\bm{s}(v)\sim\mathsf{Poi}(m\pi(v))$, and add $\bm{c}(v)$ to the
sample $\bm{S}$ with multiplicity $\bm{s}(v)$, where $\bm{c}(v)$ is the
representative of the connected component $\bm{C}_{i}$ that contains vertex
$v$.

For the moment, we are interested only in the case where the weights $w$ are
constant, so that there is some $\eta\in[0,1]$ such that $w(e)=\eta$ for all
edges $e$. We call $\eta$ the _resolution_.

######  Definition 2.2 (Distribution Testing with a Confused Collector).

Fix a graph $G=(V,E)$ and a resolution parameter $\eta$. Let $\Pi_{1},\Pi_{2}$
be properties of probability distributions over $V$, and let $\alpha\in(0,1)$.
A $(\Pi_{1},\Pi_{2},\alpha)$-distribution tester with resolution $\eta$ and
sample complexity $m$ is an algorithm $A$ that receives a confused collector
sample $\bm{S}$ from the input distribution $\pi$ and satisfies:

  1. 1.

If $\pi\in\Pi_{1}$ then $\mathbb{P}\left[A(\bm{S})\text{ accepts
}\right]\geq\alpha$; and

  2. 2.

If $\pi\in\Pi_{2}$ then $\mathbb{P}\left[A(\bm{S})\text{ rejects
}\right]\geq\alpha$.

We will drop $\alpha$ from the notation when we assume $\alpha=2/3$. However,
we remark that the confused collector does not allow to boost the success
probability in the same way as a standard distribution tester, due to the
modified sampling process.

###  2.3 Parity Trace: Definition & Terminology

In this section we will formally define distribution testing under the parity
trace and introduce the notation and terminology that we will use to analyze
our tester and prove Theorem 1.1. For a multiset $S\subset\mathbb{N}$, recall
the definition of the trace $\mathsf{trace}(S)$ from the introduction. Then we
define our testing model:

######  Definition 2.3.

Let $\Pi_{1}$ and $\Pi_{2}$ be any properties of distributions over domain
$\mathbb{N}$. A $(\Pi_{1},\Pi_{2},\alpha)$-distribution tester under the
parity trace, with sample complexity $m$, is an algorithm $A$ which satisfies
the following.

  1. 1.

If $\pi\in\Pi_{1}$, then
$\underset{\bm{S}\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A(\mathsf{trace}(\bm{S}))\text{
accepts }\right]\geq\alpha$.

  2. 2.

If $\pi\in\Pi_{2}$, then
$\underset{\bm{S}\sim\mathsf{samp}(\pi,m)}{\mathbb{P}}\left[A(\mathsf{trace}(\bm{S}))\text{
rejects }\right]\geq\alpha$.

The canonical version of this problem will have
$\Pi_{2}=\textsc{far}^{\mathsf{edit}}_{\epsilon}(\Pi_{1})$ or, in some cases,
$\Pi_{2}=\textsc{far}^{\mathsf{TV}}_{\epsilon}(\Pi_{1})$.

We say that a vector $r\in\mathbb{R}^{\mathbb{N}}$ is a partial distribution
if all of its entries are non-negative, and $\sum_{i}r_{i}\leq 1$.

In the parity trace model, we think of a probability distribution $\pi$ over
$\mathbb{N}$ as defined by two partial distributions
$p,q\in\mathbb{R}^{\mathbb{N}}_{\geq 0}$, so that $\pi=\pi(p,q)$ where

$\pi(p,q)\vcentcolon=(p_{1},q_{1},p_{2},q_{2},p_{3},q_{3},\dotsc)\,,$

so that $p$ defines the part of the distribution over the odd elements, and
$q$ defines the part of the distribution over the even elements. We will
always use the letters $p$ and $q$ for the partial distributions over the odd
and even elements, respectively.

In the parity trace model, the algorithm receives a trace $\mathsf{trace}(S)$
containing 1s and 0s, and it will separately consider the statistics of the 1s
and of the 0s. In the analysis, we will treat only the statistics of the 1s,
because the statistics for the 0s may be handled symmetrically. For the
purpose of analyzing the 1s, we may write the trace received by the algorithm
(in regular expression notation) in the form

$\mathsf{trace}(S)=1^{Z_{1}}\;0^{+}\;1^{Z_{2}}\;0^{+}\dotsm
1^{Z_{t}}\;0^{*}\,,$

for some $t$, where $Z_{2},\dotsc,Z_{t}>0$ and we allow $Z_{1}=0$. A
contiguous sequence of 1s is called a “run”, and we call the values $Z_{i}$
the “run-lengths”.

It will be convenient for our tester to actually use the “circular trace”,
obtained from $\mathsf{trace}(S)$ string by stitching the ends of the string
together, to form a necklace. If the trace begins and ends with the same
symbol, the first and last “run” are combined. So the algorithm sees a
circular trace of the form

$1^{X_{1}}\;0^{+}\;1^{X_{2}}\;0^{+}\dotsm 1^{X_{b}}\;0^{+}\,,$

where we might have $X_{1}=Z_{1}+Z_{t}$. (Here, $\sigma^{+}$ indicates that
symbol $\sigma$ occurs at least once.) For the purpose of testing uniformity,
we are concerned only with the domain $[2n]$, with the partial distributions
$p,q$ being over $[n]$, so we may think of the domain itself as being stitched
into a necklace. Equivalently, we think of the domain $[n]$ of $p$ as being
the vertices of a cycle.

More precisely, we think of a cycle on vertices $\mathbb{Z}_{n}$ with a
partial distribution $p$ over the vertices, and we define a weight vector $w$
on the edges, where the edge between vertex $i$ and $i+1$ has weight
$1-e^{-mq_{i}}$. Then, sampling a subgraph $\bm{H}$ as in the confused
collector sampling process, we see that vertices $i$ and $i+1$ in the cycle
are adjacent in $\bm{H}$ with probability
$e^{-mq_{i}}=\mathbb{P}\left[\mathsf{Poi}(mq_{i})=0\right]$, which is the
probability that these vertices will contribute to the same run-length $X_{j}$
in the trace.

###  2.4 Path- and Cycle-Structured Poisson Random Variables.

It is convenient to introduce a shared vocabulary for analyzing Poisson random
variables on the cycle and on the path. We will label the $n$ vertices of the
cycle with the set $\mathbb{Z}_{n}$ of integers mod $n$, and we will also
label the _edges_ of the cycle with the set $\mathbb{Z}_{n}$, so that edge $i$
connects vertices $i$ and $i+1$ (with arithmetic mod $n$). We will treat the
path on $n$ vertices as the subgraph of the cycle that excludes edge $n-1$
connecting vertices labeled $0$ and $n-1$. When the subgraph $H$ contains edge
$e$, we will sometimes abuse notation and write $e\in H$.

A circular interval is a tuple $\langle\\!\langle i,d\rangle\\!\rangle$ where
$i\in\mathbb{Z}_{n}$ and $d\in\mathbb{Z}$. If $d\geq 0$, we define the
elements $\mathcal{E}\langle\\!\langle i,d\rangle\\!\rangle$ as the multiset
of elements starting at vertex $i\in\mathbb{Z}_{n}$ and containing the $d-1$
elements “clockwise” from $i$, i.e. the multiset
$\\{i,i+1,i+2,\dotsc,i+d-1\\}$, where addition is mod $n$. Note that for $d=1$
this contains only $i$, while for $d>n$ this contains some elements with
multiplicity greater than 1\. If $d<0$, we define the elements
$\mathcal{E}\langle\\!\langle i,d\rangle\\!\rangle$ as the multiset of
elements starting at vertex $i\in\mathbb{Z}_{n}$ and containing the $|d|-1$
elements “counter-clockwise”, i.e. the multiset
$\\{i,i-1,i-2,\dotsc,i-|d|+1\\}$.

The endpoints of $\langle\\!\langle i,d\rangle\\!\rangle$ are the integers $i$
and $i+d-1$ if $d\geq 0$, or $i+d+1$ and $i$ if $d<0$. We will often drop the
$\mathcal{E}$ from the notation, and equivocate between the tuple
$\langle\\!\langle i,d\rangle\\!\rangle$ and its multiset of elements, so that
we write $x\in\langle\\!\langle i,d\rangle\\!\rangle$ instead of
$\mathcal{E}\langle\\!\langle i,d\rangle\\!\rangle$. However, a circular
interval is _not_ identified with its multiset of elements; for example, the
circular intervals $\langle\\!\langle i,n\rangle\\!\rangle$ and
$\langle\\!\langle i+1,n\rangle\\!\rangle$ both contain the same elements
$\mathbb{Z}_{n}$, but they have different endpoints.

For a circular interval $I$ and a vector $u:\mathbb{Z}\to\mathbb{R}$, we
define

$u[I]\vcentcolon=\sum_{s\in I}u_{s}\,,$

where we note that $s$ may occur multiple times in $I$ and $u_{s}$ is counted
each time.

For a circular interval $\langle\\!\langle i,d\rangle\\!\rangle$, we will
define the circular interval $\langle\\!\langle i,d\rangle\\!\rangle^{*}$ to
be the integers corresponding to the _edges_ induced by the vertices
$\langle\\!\langle i,d\rangle\\!\rangle$; specifically

$\langle\\!\langle i,d\rangle\\!\rangle^{*}=\begin{cases}\emptyset&\text{ if
}d=0\\\ \langle\\!\langle i,d-1\rangle\\!\rangle&\text{ if }d\geq 1\\\
\langle\\!\langle i-1,1-|d|\rangle\\!\rangle&\text{ if }d\leq-1\,.\end{cases}$

For any $s\in\mathbb{Z}_{n}$, we say that a circular interval $I$ crosses $s$
if $s\in I^{*}$; i.e. $s$ is an edge between two vertices in $I$.

Fix any subgraph $H$ of the cycle (or path), and suppose that $H$ has $b$
connected components; note that each connected component is a circular
interval. We define the buckets induced by $H$ as
$\Gamma_{1},\dotsc,\Gamma_{n}$ such that $\Gamma_{1},\dotsc,\Gamma_{b}$ are
the connected components of $H$, while
$\Gamma_{b+1},\dotsc,\Gamma_{n}=\emptyset$. For each vertex
$i\in\mathbb{Z}_{n}$, we define

$\gamma(i)\vcentcolon=t\text{ such that }i\in\Gamma_{t}\,.$

We say that two vertices $i,j$ are joined if $\gamma(i)=\gamma(j)$, and we
define the join matrix $\Phi=\Phi(H)$ as

$\Phi_{i,j}\vcentcolon=\begin{cases}1&\text{ if }\gamma(i)=\gamma(j)\\\
0&\text{ otherwise.}\end{cases}$

We define a join function $J$ such that for any circular interval
$I=\langle\\!\langle i,d\rangle\\!\rangle$,

$J(I)\vcentcolon=\mathds{1}\left[\forall e\in\langle\\!\langle
i,d\rangle\\!\rangle^{*}:e\in H\right]\,.$

Thus if $J(I)=1$, then for every $i,j\in\mathcal{E}(I)$ we have
$\Phi_{i,j}=1$.

For a fixed sample (i.e. multiset) $S\subset\mathbb{Z}_{n}$ and for
$i\in\mathbb{Z}_{n}$, write $T_{i}$ for the multiplicity of element $i$ in
$S$. We then define for each $i\in[n]$ the variable

$X_{i}\vcentcolon=\sum_{j\in\mathbb{Z}_{n}:\gamma(j)=i}T_{j}\,,$

which is the total multiplicity of elements from bucket $\Gamma_{i}$ that
occur in $S$.

Observe that the above variables depend on the subgraph $H$ and the sample
$S$. For a fixed weight vector $w$ and random subgraph $\bm{H}$ chosen
according to the confused collector sampling procedure, and a random sample
$\bm{S}$ of vertices, we write the above variables in bold to denote the
random variables depending on $\bm{H}$ and $\bm{S}$. We will then write

$\phi\vcentcolon=\mathbb{E}\left[\bm{\Phi}\right]\,,$

and observe that

$\phi_{i,j}=\mathbb{P}\left[\bm{\gamma}(i)=\bm{\gamma}(j)\right]\,.$

In our analysis of the confused collector and the parity trace, we have a
sample-size parameter $m$ and an input (partial) distribution
$p:\mathbb{Z}_{n}\to[0,1]$. We will then have

$\bm{T}_{j}\sim\mathsf{Poi}(mp_{j})$

for each $j\in\mathbb{Z}_{n}$, and therefore

$\bm{X}_{i}\sim\mathsf{Poi}(m\cdot p[\bm{\Gamma}_{i}])$

for each $i\in[n]$. We will also have the random Boolean matrix $\bm{\Phi}$
which indicates the connected components of $\bm{H}$. Our testing algorithms
will rely on an analysis of the following _test statistic_.

######  Definition 2.4 (Test Statistic).

For a fixed parameter $m$ and weight vector $w$, and random variables defined
as above, we define the test statistic

$\bm{Y}\vcentcolon=\frac{1}{m}\sum_{i=1}^{n}\bm{X}_{i}(\bm{X}_{i}-1)\,.$

By expanding the variables $\bm{X}_{i}$, the test statistic may be written as
the quadratic form

$\bm{Y}=\frac{1}{m}\left(\bm{T}^{\top}\bm{\Phi}\bm{T}-\|\bm{T}\|_{1}\right)\,.$

###  2.5 Shared Analysis

We now proceed with a part of the analysis that is shared between our confused
collector and parity trace results, reflecting common challenges presented by
each model. The application of these results in the subsequent sections will
then exploit the particularities of each model—essentially, that the
resolution $\eta$ is fixed in the confused collector model, whereas in the
parity trace model the partial distributions and the selected sample size
affect the sampling rate of both vertices and edges.

####  2.5.1 Circular Intervals

Our analysis will handle the cases where $G$ is a cycle or a path. For the
path, the circular intervals that cross the edge between vertices $0$ and
$n-1$ are irrelevant, so it is convenient to define
$\mathcal{I}^{\mathsf{cycle}}$ as the set of all circular intervals, and
$\mathcal{I}^{\mathsf{path}}$ as the set of all circular intervals that do not
cross edge $n-1$.

We will use
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$
to denote the set of circular intervals relevant to the analysis. In the case
$\mathcal{I}=\mathcal{I}^{\mathsf{cycle}}$, each pair of vertices $i\leq j$
has two disjoint paths connecting them and therefore may be joined together in
two ways. We define $\operatorname{\mathsf{small}}(i,j)$ and
$\operatorname{\mathsf{large}}(i,j)$ as the two circular intervals defined as
follows. Let

$I_{1}\vcentcolon=\langle\\!\langle i,j-i+1\rangle\\!\rangle\qquad\text{ and
}\qquad I_{2}\vcentcolon=\langle\\!\langle j,n-(j-i)+1\rangle\\!\rangle$

as the circular intervals corresponding to the two separate paths between $i$
and $j$. Then we define

$\operatorname{\mathsf{small}}(i,j)\vcentcolon=\arg\max_{I\in\\{I_{1},I_{2}\\}}\mathbb{E}\left[\bm{J}[I]\right]\qquad\text{
and
}\qquad\operatorname{\mathsf{large}}(i,j)\vcentcolon=\arg\min_{I\in\\{I_{1},I_{2}\\}}\mathbb{E}\left[\bm{J}[I]\right]\,,$

breaking ties arbitrarily. Note that, in the case of the path, we will have
only one way of joining $i$ and $j$, so that
$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{large}}(i,j)]\right]=0$ in this
case. Symmetrically, when $i>j$ we define
$\operatorname{\mathsf{small}}(i,j)\vcentcolon=\operatorname{\mathsf{small}}(j,i)$
and
$\operatorname{\mathsf{large}}(i,j)\vcentcolon=\operatorname{\mathsf{large}}(j,i)$.

For
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$,
we define

$\zeta(\mathcal{I})\vcentcolon=\max_{i,j}\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{large}}(i,j)]\right]\,.$

The analysis proceeds in two cases. For the confused collector, we assume that
the weight vector is constant, so that $w(j)=\eta$ for each edge $j$, where
$\eta$ is the resolution parameter; then the probability that edge $j$ appears
in $\bm{H}$ is $1-w(j)=1-\eta$. For the parity trace, we have two partial
distributions, $p$ and $q$, which are the parts of the input distribution
corresponding to the odd and even elements of the domain, respectively. We
treat $p$ as the distribution over the vertices of the cycle, and we define
the weight vector $w(j)\vcentcolon=1-e^{-mq_{j}}$, so that the probability of
edge $j$ appearing in $\bm{H}$ is
$1-w(j)=e^{-mq_{j}}=\mathbb{P}\left[\mathsf{Poi}(mq_{j})=0\right]$.

######  Proposition 2.5.

$\zeta(\mathcal{I}^{\mathsf{path}})=0$. For constant weights $w(j)=\eta$, we
have

$\zeta(\mathcal{I}^{\mathsf{cycle}})\leq(1-\eta)^{n/2}\,,$

and for weights $w(j)=1-e^{-mq_{j}}$, we have

$\zeta(\mathcal{I}^{\mathsf{cycle}})\leq e^{-\frac{m\|q\|_{1}}{2}}\,.$

###### Proof.

For distinct $i,j\in\mathbb{Z}_{n}$, define $I_{1}$ and $I_{2}$ as above, and
note that for $a\in\\{1,2\\}$,

$\mathbb{E}\left[\bm{J}[I_{a}]\right]=\prod_{j\in I_{a}^{*}}(1-w(j))\,.$

In the case $w(j)=\eta$, this is $(1-\eta)^{|I_{a}^{*}|}$, while in the case
$w(j)=1-e^{-mq_{j}}$, this is $e^{-mq[I_{a}^{*}]}$. Note that $I_{1},I_{2}$
partition $\mathbb{Z}_{n}$, so in the first case we have either $|I_{1}|\geq
n/2$ or $|I_{2}|\geq n/2$, so the minimum is at most $(1-\eta)^{n/2}$. In the
second case we have either $q[I^{*}_{1}]\geq\|q\|_{1}/2$ or
$q[I^{*}_{2}]\geq\|q\|_{1}/2$, so the minimum is at most
$e^{-\frac{m\|q\|_{1}}{2}}$. ∎

####  2.5.2 Expectation of the Test Statistic

We start by giving an expression for the expectation of the statistic
$\bm{Y}$. Recall that we write $p:\mathbb{Z}_{n}\to[0,1]$ for the (partial)
distribution over the vertices (of either the path or the cycle), $m$ is the
sample-size parameter, and $\phi=\mathbb{E}\left[\bm{\Phi}\right]$.

######  Proposition 2.6.

The statistic $\bm{Y}$ satisfies

$\mathbb{E}\left[\bm{\bm{Y}}\right]=mp^{\top}\phi p\,.$

###### Proof.

We use the facts that $\bm{T}$ and $\bm{\Phi}$ are independent and that, for
$i\neq j$, $\bm{T}_{i}$ and $\bm{T}_{j}$ are independent. We will also use the
property that, for $\bm{Z}\sim\mathsf{Poi}(\lambda)$, we have
$\mathbb{E}\left[\bm{Z}\right]=\mathrm{Var}\left[\bm{Z}\right]=\lambda$ and,
therefore,
$\mathbb{E}\left[\bm{Z}^{2}\right]=\mathbb{E}\left[\bm{Z}\right]+\mathbb{E}\left[\bm{Z}\right]^{2}$.
We obtain:

$\displaystyle\mathbb{E}\left[\bm{Y}\right]$
$\displaystyle=\frac{1}{m}\left(\mathbb{E}\left[\bm{T}^{\top}\bm{\Phi}\bm{T}\right]-\mathbb{E}\left[\|\bm{T}\|_{1}\right]\right)=\frac{1}{m}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\bm{T}_{j}\right]\mathbb{E}\left[\bm{\Phi}_{i,j}\right]-\frac{1}{m}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]$
$\displaystyle=\frac{1}{m}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]\mathbb{E}\left[\bm{T}_{j}\right]\phi_{i,j}+\frac{1}{m}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]-\frac{1}{m}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]=\frac{1}{m}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(mp_{i})(mp_{j})\phi_{i,j}$
$\displaystyle=mp^{\top}\phi p\,.\qed$

It will sometimes be useful to write $p=p^{*}+z$ where $p^{*}$ is a reference
partial distribution, in which case we require:

######  Proposition 2.7.

Write $p=p^{*}+z$. Then $\bm{Y}$ satisfies

$\mathbb{E}\left[\bm{Y}\right]=m\left(p^{*}\right)^{\top}\phi
p^{*}+2m\left(p^{*}\right)^{\top}\phi z+mz^{\top}\phi z\,.$

###### Proof.

This follows immediately from Proposition 2.6 by expanding the quadratic form
and recalling that $\bm{\Phi}$ is always a symmetric matrix, and hence so is
$\phi=\mathbb{E}\left[\bm{\Phi}\right]$. ∎

####  2.5.3 Variance of the Test Statistic: First Component

In this section, we will establish upper bounds for the variance of $\bm{Y}$
that are general to both the parity trace and confused collector models. The
sections dealing with each particular model will proceed from here.

Recall that the (random) partition of vertices into buckets
$\bm{\Gamma}_{1},\dotsc,\bm{\Gamma}_{n}$ depends on the random subgraph
$\bm{H}$. We start by noting that we can break down the variance of $\bm{Y}$
into two components by the law of total variance:

$\mathrm{Var}\left[\bm{Y}\right]=\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]+\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\,.$

We will handle the first term here, and the second term in Section 2.5.4.

Recall that the weight vector $w$ is either the constant $\eta$ vector, or
$w(j)=1-e^{-mq_{j}}$.

######  Proposition 2.8.

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$.
For every $i,j,k,\ell\in\mathbb{Z}_{n}$, the following hold:

  1. 1.

$\mathbb{E}\left[\Phi(\bm{J})_{i,j}\right]\geq\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]$;

  2. 2.

$\mathbb{E}\left[\Phi(\bm{J})_{i,j}\cdot\Phi(\bm{J})_{k,\ell}\right]\leq\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\cdot\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]+4\cdot\zeta(\mathcal{I})$.

###### Proof.

Recall that $\Phi(\bm{J})_{i,j}=1$ if and only if
$\bm{\gamma}(i)=\bm{\gamma}(j)$. This will occur if
$\operatorname{\mathsf{small}}(i,j)\subseteq\bm{\Gamma}_{\gamma(i)}$, which
happens when $\bm{J}[\operatorname{\mathsf{small}}(i,j)]=1$, yielding the
first conclusion. Next, observe

$\displaystyle\bm{\Phi}_{i,j}=\max\\{\bm{J}[\operatorname{\mathsf{small}}(i,j)],\bm{J}[\operatorname{\mathsf{large}}(i,j)]\\}\leq\bm{J}[\operatorname{\mathsf{small}}(i,j)]+\bm{J}[\operatorname{\mathsf{large}}(i,j)]\,.$

To prove the second statement, expand the product and use the fact that
$\bm{J}$ is a Boolean vector:

$\displaystyle\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}$
$\displaystyle\leq\left(\bm{J}[\operatorname{\mathsf{small}}(i,j)]+\bm{J}[\operatorname{\mathsf{large}}(i,j)]\right)\left(\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]+\bm{J}[\operatorname{\mathsf{large}}(k,\ell)]\right)$
$\displaystyle\leq\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]+2\left(\bm{J}[\operatorname{\mathsf{large}}(i,j)]+\bm{J}[\operatorname{\mathsf{large}}(k,\ell)]\right)\,.$

We have
$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{large}}(i,j)]\right],\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{large}}(k,\ell)]\right]\leq\zeta(\mathcal{I})$
by definition, so the conclusion follows from taking the expectation. ∎

######  Lemma 2.9.

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$
and let $w$ be the weights on the edges. There exists an absolute constant
$c>0$ such that the first component of the variance of $\bm{Y}$ satisfies

$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq
5m^{2}\zeta(\mathcal{I})\|p\|_{1}^{4}+cm^{2}\cdot\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}p_{i}p_{i+d-1}p[I]^{2}\mathbb{E}\left[\bm{J}(I)\right]\,.$

###### Proof.

Fix any subgraph $H$. Conditional on $\bm{H}=H$,

$\displaystyle\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]$
$\displaystyle=\frac{1}{m}\mathbb{E}\left[\bm{T}^{\top}\Phi\bm{T}\right]-\frac{1}{m}\mathbb{E}\left[\|\bm{T}\|_{1}\right]=\frac{1}{m}\sum_{i,j\in\mathbb{Z}_{n}}\mathbb{E}\left[\bm{T}_{i}\bm{T}_{j}\right]\Phi_{i,j}-\frac{1}{m}\mathbb{E}\left[\mathsf{Poi}(m)\right]$
$\displaystyle=\frac{1}{m}\left(\sum_{i\in\mathbb{Z}_{n}}\mathbb{E}\left[\bm{T}_{i}\right]+\sum_{i,j\in\mathbb{Z}_{n}}\mathbb{E}\left[\bm{T}_{i}\right]\mathbb{E}\left[\bm{T}_{j}\right]\Phi_{i,j}\right)-1=\frac{1}{m}\left(m+m^{2}p^{\top}\Phi
p\right)-1$ $\displaystyle=mp^{\top}\Phi p\,,$

and therefore the desired variance is

$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]=m^{2}\underset{\bm{H}}{\mathrm{Var}}\left[p^{\top}\bm{\Phi}p\right]\,.$

Then, recalling that $\phi=\mathbb{E}\left[\bm{\Phi}\right]$, we expand
$\underset{\bm{H}}{\mathrm{Var}}\left[p^{\top}\bm{\Phi}p\right]$ as follows:

$\displaystyle\mathrm{Var}\left[p^{\top}\bm{\Phi}p\right]$
$\displaystyle=\mathbb{E}\left[\left(p^{\top}\bm{\Phi}p\right)^{2}\right]-\left(\mathbb{E}\left[p^{\top}\bm{\Phi}p\right]\right)^{2}=\mathbb{E}\left[\left(p^{\top}\bm{\Phi}p\right)^{2}\right]-\left(p^{\top}\phi
p\right)^{2}$
$\displaystyle=\mathbb{E}\left[\left(\sum_{i,j\in\mathbb{Z}_{n}}p_{i}p_{j}\bm{\Phi}_{i,j}\right)^{2}\right]-\left(\sum_{i,j\in\mathbb{Z}_{n}}p_{i}p_{j}\phi_{i,j}\right)^{2}$
$\displaystyle=\mathbb{E}\left[\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\phi_{i,j}\phi_{k,\ell}$
$\displaystyle=\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\left(\mathbb{E}\left[\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\phi_{i,j}\phi_{k,\ell}\right)\,.$

We now use Proposition 2.8 to simplify the quantity
$\mathbb{E}\left[\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\phi_{i,j}\phi_{k,\ell}$:

$\displaystyle\mathbb{E}\left[\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\phi_{i,j}\phi_{k,\ell}$
$\displaystyle\qquad\leq\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]-\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]+4\cdot\zeta(\mathcal{I})\,.$

If the intervals $\operatorname{\mathsf{small}}(i,j)$ and
$\operatorname{\mathsf{small}}(k,\ell)$ are disjoint, then

$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]-\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]=0\,.$

On the other hand, if these intervals are not disjoint, we will employ the
simple upper bound

$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]-\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]\leq\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]\,.$

We then consider two cases.

First, suppose that for every edge $s\in\mathbb{Z}_{n}$,
$\operatorname{\mathsf{small}}(i,j)$ crosses $s$ or
$\operatorname{\mathsf{small}}(k,\ell)$ crosses $s$. Then
$\mathbb{Z}_{n}\subseteq\operatorname{\mathsf{small}}(i,j)^{*}\cup\operatorname{\mathsf{small}}(k,\ell)^{*}$,
so
$\bm{J}(\operatorname{\mathsf{small}}(i,j))\cdot\bm{J}(\operatorname{\mathsf{small}}(k,\ell))=1$
only when every edge appears in $\bm{H}$, which happens with probability at
most $\zeta(\mathcal{I})$ (since this event implies that every large interval
is joined). In this case,
$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]\leq\zeta(\mathcal{I})$.

As for the second case, let $s\in\mathbb{Z}_{n}$ be such that neither
$\operatorname{\mathsf{small}}(i,j)$ nor
$\operatorname{\mathsf{small}}(k,\ell)$ crosses $s$. Since
$\operatorname{\mathsf{small}}(i,j)$ and
$\operatorname{\mathsf{small}}(k,\ell)$ are not disjoint, it follows that
there exists an interval $I=I_{i,j,k,\ell}\in\mathcal{I}$ satisfying the
following:

  1. 1.

The set
$\operatorname{\mathsf{small}}(i,j)\cup\operatorname{\mathsf{small}}(k,\ell)$
is equal to the set of elements of $I_{i,j,k,\ell}$, where we are here taking
the union as sets (not as multisets);

  2. 2.

The endpoints of $I_{i,j,k,\ell}$ are two of the indices $i,j,k,\ell$; and,

  3. 3.

$|I_{i,j,k,\ell}|\leq n$ (because, in particular, $I_{i,j,k,\ell}$ does not
cross $s$).

It follows that
$\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]=1$
if and only if $\bm{J}[I]=1$, and hence we have the upper bound
$\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]-\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]\leq\mathbb{E}\left[\bm{J}[I]\right]$.
Therefore,

$\displaystyle\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\left(\mathbb{E}\left[\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\phi_{i,j}\phi_{k,\ell}\right)$
$\displaystyle\leq\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\left(\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]-\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(i,j)]\right]\mathbb{E}\left[\bm{J}[\operatorname{\mathsf{small}}(k,\ell)]\right]+4\cdot\zeta\right)$
$\displaystyle\leq
4\cdot\|p\|_{1}^{4}\cdot\zeta+\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\left(\mathds{1}\left[\mathbb{Z}_{n}\subseteq\operatorname{\mathsf{small}}(i,j)^{*}\cup\operatorname{\mathsf{small}}(k,\ell)^{*}\right]\cdot\zeta(\mathcal{I})+\mathds{1}\left[I_{i,j,k,\ell}\text{
exists}\right]\cdot\mathbb{E}\left[\bm{J}[I_{i,j,k,\ell}]\right]\right)$
$\displaystyle\leq
5\zeta(\mathcal{I})\|p\|_{1}^{4}+\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}p_{i}p_{j}p_{k}p_{\ell}\mathds{1}\left[I_{i,j,k,\ell}\text{
exists}\right]\cdot\mathbb{E}\left[\bm{J}[I_{i,j,k,\ell}]\right]\,.$

The latter is bounded by summing over all intervals $I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}$ with $d\leq n$ and for each one taking the
expression $c\cdot p_{i}p_{i+d-1}\sum_{j,k\in
I}p_{j}p_{k}\cdot\mathbb{E}\left[\bm{J}[I]\right]$, where $i$ and $i+d-1$ are
the endpoints of $I$, and $c$ is a constant counting the number of ways to get
intersecting intervals with endpoints in $i,(i+d-1),k,\ell$. Now, using
$\sum_{j,k\in I}p_{j}p_{k}=p[I]^{2}$, we obtain

$\mathrm{Var}\left[p^{\top}\Phi(\bm{J})p\right]\leq
5\zeta(\mathcal{I})\|p\|_{1}^{4}+c\cdot\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}\mathbb{E}\left[\bm{J}[I]\right]p_{i}p_{i+d-1}p[I]^{2}\,.\qed$

####  2.5.4 Variance of the Test Statistic: Second Component

We introduce some notation for the partial distribution over the buckets
$\Gamma_{i}$ (i.e. connected components of $H$) induced by $p$.

######  Definition 2.10 (Bucketed Vector).

Let $\Gamma=(\Gamma_{1},\dotsc,\Gamma_{b})$ be the buckets resulting from a
subgraph $H$, and let $u:\mathbb{Z}_{n}\to\mathbb{R}$. Then _$\Gamma$
-bucketing of $u$_ is the vector $u_{|\Gamma}\in\mathbb{R}^{b}$ given by

$\left(u_{|\Gamma}\right)_{i}\vcentcolon=u\left[\Gamma_{i}\right]=\sum_{j\in\Gamma_{i}}u_{j}\quad\text{for
all }i\in[b]\,.$

We now show that the second component of the variance is captured by 2- and
3-norms of the bucketed vector $p$. Recall that
$\bm{T}_{i}\sim\mathsf{Poi}(mp_{i})$ is the number of occurrences of vertex
$i\in\mathbb{Z}_{n}$ in the sample. We first compute the variance of the terms
$\bm{X}_{i}(\bm{X}_{i}-1)$ that make up the test statistic:

######  Proposition 2.11.

If $\bm{X}\sim\mathsf{Poi}(\lambda)$, then
$\mathrm{Var}\left[\bm{X}(\bm{X}-1)\right]=4\lambda^{3}+2\lambda^{2}$.

###### Proof.

The Poisson random variable $\bm{X}$ has the following raw moments (see e.g.
[Rio37]):

$\displaystyle\mathbb{E}\left[X\right]$ $\displaystyle=\lambda\,,$
$\displaystyle\mathbb{E}\left[X^{2}\right]$
$\displaystyle=\lambda+\lambda^{2}\,,$
$\displaystyle\mathbb{E}\left[X^{3}\right]$
$\displaystyle=\lambda+3\lambda^{2}+\lambda^{3}\,,$
$\displaystyle\mathbb{E}\left[X^{4}\right]$
$\displaystyle=\lambda+7\lambda^{2}+6\lambda^{3}+\lambda^{4}\,.$

Therefore we have

$\displaystyle\mathrm{Var}\left[X(X-1)\right]$
$\displaystyle=\mathbb{E}\left[(X(X-1))^{2}\right]-\mathbb{E}\left[X(X-1)\right]^{2}=\mathbb{E}\left[(X^{2}-X)^{2}\right]-(\mathbb{E}\left[X^{2}\right]-\mathbb{E}\left[X\right])^{2}$
$\displaystyle=\mathbb{E}\left[X^{4}\right]-2\mathbb{E}\left[X^{3}\right]+\mathbb{E}\left[X^{2}\right]-\mathbb{E}\left[X^{2}\right]^{2}+2\mathbb{E}\left[X^{2}\right]\mathbb{E}\left[X\right]-\mathbb{E}\left[X\right]^{2}$
$\displaystyle=(\lambda+7\lambda^{2}+6\lambda^{3}+\lambda^{4})-2(\lambda+3\lambda^{2}+\lambda^{3})+(\lambda+\lambda^{2})-(\lambda+\lambda^{2})^{2}+2(\lambda+\lambda^{2})\lambda-\lambda^{2}$
$\displaystyle=4\lambda^{3}+2\lambda^{2}\,.\qed$

######  Lemma 2.12.

Let $H$ be a subgraph with induced buckets
$\Gamma=(\Gamma_{1},\dotsc,\Gamma_{b})$, and let $p$ be a measure on
$\mathbb{Z}_{n}$ Then the conditional variance of $\bm{Y}$ given $\bm{H}=H$
satisfies

$\displaystyle\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]=2\|p_{|\Gamma}\|_{2}^{2}+4m\|p_{|\Gamma}\|_{3}^{3}\,.$

###### Proof.

Using Proposition 2.11, the desired variance is

$\displaystyle\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]$
$\displaystyle=\mathrm{Var}\left[\frac{1}{m}\sum_{i=1}^{b}\bm{X}_{i}(\bm{X}_{i}-1)\right]=\frac{1}{m^{2}}\sum_{i=1}^{b}\left[4\left(mp\left[\Gamma_{i}\right]\right)^{3}+2\left(mp\left[\Gamma_{i}\right]\right)^{2}\right]$
$\displaystyle=4m\|p_{|\Gamma}\|_{3}^{3}+2\|p_{|\Gamma}\|_{2}^{2}\,.\qed$

####  2.5.5 Relative Concentration

One of the main tools in our analysis will be “relative concentration”,
which compares the probability mass of $p$ inside the circular intervals $I$,
to another measure $q$ on the edges.

######  Definition 2.13 (Relative Concentration).

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$
and let $p,q:\mathbb{Z}_{n}\to\mathbb{R}_{\geq 0}$ be partial distributions.
Let $t\in\mathbb{R}$. Then we define

$\rho_{t}(p\;\|\;q)\vcentcolon=\max_{I\in\mathcal{I}:|I|\leq
n}\frac{p[I]}{\max\left\\{q[I^{*}],t\right\\}}\,.$

We will require the following lemma, which allows us to find an interval $I$
exhibiting a large difference between $p[I]$ and $q[I^{*}]$ if we assume high
relative concentration $\rho_{t}(p\;\|\;q)$.

######  Lemma 2.14.

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$,
and let $p,q:\mathbb{Z}_{n}\to\mathbb{R}_{\geq 0}$ be partial distributions.
Then there exists $I\in\mathcal{I}$ of size at most $n$ satisfying the
following:

  1. 1.

$q[I^{*}]\leq t$; and

  2. 2.

$p[I]\geq\frac{1}{2}\cdot t\cdot\rho_{t}(p\;\|\;q)$.

###### Proof.

By definition of relative concentration, there exists an interval
$I\in\mathcal{I}$ of size at most $n$ such that either

  1. 1.

$q[I^{*}]\leq t$ and $p[I]=t\rho_{t}(p\;\|\;q)$; or

  2. 2.

$q[I^{*}]\geq t$ and $p[I]=q[I^{*}]\rho_{t}(p\;\|\;q)$.

In the former case, $I$ satisfies the required conditions and we are done.

Therefore, we may assume that the second condition holds. Let $I$ be an
interval of minimum size satisfying $q[I^{*}]\geq t$ and $p[I]\geq
q[I^{*}]\rho_{t}(p\;\|\;q)$ (in particular, equality will hold). Note that we
must have $|I|\geq 2$, since otherwise $I^{*}$ would be empty, contradicting
the assumption that $q[I^{*}]\geq t>0$. We now consider two cases.

Case 1. Suppose that we may partition $I=L\cup R$ where $L,R$ are nonempty
circular intervals such that one of the following two conditions hold101010For
two intervals $I_{1}=\langle\\!\langle i,d_{1}\rangle\\!\rangle$ and
$I_{2}=\langle\\!\langle i,d_{2}\rangle\\!\rangle$ with $d_{1}>d_{2}>0$ (i.e.
$I_{2}$ is a nonempty prefix of $I_{1}$), we will write $I_{1}\setminus I_{2}$
to denote the interval $\langle\\!\langle
i+d_{2},d_{1}-d_{2}\rangle\\!\rangle$., call this pair of conditions ($*$):

  1. 1.

$q[L^{*}],q[I^{*}\setminus L^{*}]\leq t$; or

  2. 2.

$q[L^{*}],q[I^{*}\setminus L^{*}]\geq t$.

If the first condition holds, we conclude the proof as follows. Since
$p[I]=p[L]+p[R]$ and $p[I]=q[I^{*}]\rho_{t}(p\;\|\;q)\geq
t\rho_{t}(p\;\|\;q)$, it must be that either
$p[L]\geq\frac{1}{2}t\rho_{t}(p\;\|\;q)$ or
$p[R]\geq\frac{1}{2}t\rho_{t}(p\;\|\;q)$. In the first case, $L$ satisfies the
required conditions. In the second case, since $q[R^{*}]\leq q[I^{*}\setminus
L^{*}]\leq t$, we conclude that $R$ satisfies the required conditions and we
are done.

If the second condition holds (which in particular implies that
$L^{*},I^{*}\setminus L^{*}$ are nonempty), note that since $p[I]=p[L]+p[R]$
and $q[I^{*}]=q[L^{*}]+q[I^{*}\setminus L^{*}]$, we have

$\rho_{t}(p\;\|\;q)=\frac{p[I]}{q[I^{*}]}=\frac{p[L]+p[R]}{q[L^{*}]+q[I^{*}\setminus
L^{*}]}\leq\max\left\\{\frac{p[L]}{q[L^{*}]},\frac{p[R]}{q[I^{*}\setminus
L^{*}]}\right\\}\,.$

If $\frac{p[L]}{q[L^{*}]}\geq\rho_{t}(p\;\|\;q)$, then since $q[L^{*}]\geq t$,
we conclude that $L$ contradicts the minimality of $I$. Therefore we must have
$\frac{p[R]}{q[R^{*}]}\geq\frac{p[R]}{q[I^{*}\setminus
L^{*}]}\geq\rho_{t}(p\;\|\;q)$. Now, if $q[R^{*}]\leq t$, then $R$ satisfies
the required conditions, since we have $p[R]\geq q[I^{*}\setminus
L^{*}]\rho_{t}(p\;\|\;q)\geq t\rho_{t}(p\;\|\;q)$. Otherwise, if $q[R^{*}]>t$,
then $R$ contradicts the minimality of $I$. This completes the proof in the
first case.

Case 2. In the second case, we have that every partition $I=L\cup R$ with
nonempty $L$ and $R$ fails both of the conditions in ($*$). Write
$I=\langle\\!\langle i,d\rangle\\!\rangle$ where, as previously remarked,
$d\geq 2$. Consider the sequences of circular intervals $L_{1},\dotsc,L_{d-1}$
given by $L_{j}\vcentcolon=\langle\\!\langle i,j\rangle\\!\rangle$, and write
$R_{j}\vcentcolon=\langle\\!\langle i+j,d-j\rangle\\!\rangle=I\setminus
L_{i}$, so that $L^{*}_{j}=\langle\\!\langle i,j-1\rangle\\!\rangle$ and
$R^{*}_{j}=\langle\\!\langle i+j,d-j-1\rangle\\!\rangle$. Then each $L_{j}\cup
R_{j}$ for $j\in[d-1]$ is a partition of $I$ with nonempty $L_{j}$ and
$R_{j}$, which therefore must fail the two conditions in ($*$).

Now observe that $q[L^{*}_{j}]$ is non-decreasing with $j$ and
$q[I^{*}\setminus L^{*}_{j}],q[R^{*}_{j}]$ are non-increasing with $j$, while
$q[L^{*}_{1}]=q[\emptyset]=0$ and hence $q[L^{*}_{1}]\leq q[I^{*}\setminus
L^{*}_{1}]$. Fix the maximum index $j\in[d-1]$ satisfying $q[L^{*}_{j}]\leq
q[I^{*}\setminus L^{*}_{j}]$. We claim that $q[L^{*}_{j}],q[R^{*}_{j}]\leq t$.

Assume for the sake of contradiction that $q[L^{*}_{j}]>t$. By the selection
of $j$, we have $q[I^{*}\setminus L^{*}_{j}]>t$. But then the partition
$I=L_{j}\cup R_{j}$ satisfies the second condition in ($*$), a contradiction.
So we have verified that $q[L^{*}_{j}]\leq t$.

Now assume for the sake of contradiction that $q[R^{*}_{j}]>t$. Then
$R^{*}_{j}$ is nonempty, implying that $j<d-1$, and one can verify that
$R^{*}_{j}=I^{*}\setminus L^{*}_{j+1}$. Therefore $q[I^{*}\setminus
L^{*}_{j+1}]>t$. If $q[L^{*}_{j+1}]\geq t$, then the partition $I=L_{j+1}\cup
R_{j+1}$ satisfies the second condition in ($*$), again a contradiction. We
may therefore assume that $q[L^{*}_{j+1}]<t$. But this implies that
$q[L^{*}_{j+1}]<q[I^{*}\setminus L^{*}_{j+1}]$, contradicting the maximality
of our choice of $j$. Therefore we have verified that $q[R^{*}_{j}]\leq t$.

Finally, recall that $p[L_{j}]+p[R_{j}]=p[I]\geq
q[I^{*}]\rho_{t}(p\;\|\;q)\geq t\rho_{t}(p\;\|\;q)$, and therefore either
$p[L_{j}]\geq\frac{1}{2}t\rho_{t}(p\;\|\;q)$ or
$p[R_{j}]\geq\frac{1}{2}t\rho_{t}(p\;\|\;q)$. Since
$q[L^{*}_{j}],q[R^{*}_{j}]\leq t$, it follows that either $L_{j}$ or $R_{j}$
satisfies the required conditions. ∎

##  3 Testing Uniformity in the Confused Collector Model

Following the setup from Section 2, we consider the task of testing uniformity
of an unknown distribution $p$ over the vertices $\mathbb{Z}_{n}$ of a base
graph $G=(\mathbb{Z}_{n},E)$ in the confused collector model. Here, $G$ is the
path or the cycle and every edge $(i,i+1)\in E$ has weight $w(e)=\eta$, where
$\eta$ is the resolution parameter.

Our analysis will treat the cases of the cycle and the path in a unified
presentation. In the case of the cycle, $E$ contains all $n$ edges connecting
each vertex $i$ to $i+1$ (mod $n$), and the set of relevant intervals is
$\mathcal{I}=\mathcal{I}^{\mathsf{cycle}}$. We will write
$\bm{\Phi}=\bm{\Phi}^{\mathsf{cycle}}$ for the corresponding join matrix. In
the case of the path, $E$ does not contain an edge between $0$ and $n-1$, the
set of relevant intervals is $\mathcal{I}=\mathcal{I}^{\mathsf{path}}$, and
the join matrix is $\bm{\Phi}=\bm{\Phi}^{\mathsf{path}}$. When a result
depends on the choice of domain, we will explicitly state the domain under
consideration.

The tester is Algorithm 1, and consists of two steps:

  1. 1.

Concentration test: checks whether any count in the sample is too large; this
case corresponds to highly concentrated distributions, which can be rejected.

  2. 2.

Collision-based test: accept or reject depending on whether the test statistic
$\bm{Y}$ is below a certain threshold.

Algorithm 1 Uniformity tester in the confused collector model.

Set $m\leftarrow
c\cdot\frac{\sqrt{n}}{\epsilon^{2}}\cdot\frac{\log^{2}n}{\eta^{3/2}}$.
Constants: $\alpha,\beta,L,c>0$ to be defined later.
Requires: $\eta\geq\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}$.

1:procedure UniformityTester-ConfusedCollector($p,n,\epsilon,\eta$)

2: Let $X=(X_{1},\dotsc,X_{n})$ be the variables defined in Section 2 for a
sample of size $\mathsf{Poi}(m)$ from $p$.

3: If $\max_{i}X_{i}\geq\alpha\log n$ then reject.

4: $Y\leftarrow\frac{1}{m}\sum_{i}X_{i}(X_{i}-1)$.

5: If
$Y\geq\frac{m}{n^{2}}\sum_{i,j}\phi_{i,j}+\beta\frac{m}{n}\epsilon^{2}\eta$
then reject.

6: Accept.

##### Remark on the optimality of the collision-based tester.

Considering that we give a Poissonized tester whose main statistic $\bm{Y}$ is
equivalent to the collision-based statistic of [GR00] when $\eta=1$, it may
seem surprising that we claim a sample complexity of
$\widetilde{O}\left(\sqrt{n}/\epsilon^{2}\right)$ — as opposed to
$O\left(\sqrt{n}/\epsilon^{4}\right)$— when it is known that, for an analysis
based on bounding the variance of $\bm{Y}$ and applying Chebyshev’s
inequality, establishing the optimal sample complexity is only possible with a
different test statistic (e.g. the modified chi-squared statistic [CDVV14,
DKN15b, VV17a]) or a careful analysis of the non-Poissonized tester [DGPP19]
(see also the Remark in Section 2 therein). Our analysis implicitly avoids
this issue via our relative concentration test, which upper bounds
$\|p\|_{\infty}$, but another way to resolve the apparent conflict is to
notice that dropping this extra test and specializing our proof to the case
$\eta=1$ would only incur a dependence on $1/\epsilon^{4}$, rather than
$\sqrt{n}/\epsilon^{4}$; and since our analysis only handles the case
$\epsilon\geq\widetilde{\Omega}\left(n^{-1/4}\right)$, the term
$\sqrt{n}/\epsilon^{2}$ dominates $1/\epsilon^{4}$.

###  3.1 Easy Case: Highly Concentrated Distributions

We would like to call distribution $p$ “highly concentrated” if it contains
too much mass in a small contiguous range of the vertices $V$. The tester will
detect the highly concentrated distributions and reject, while non-highly
concentrated distributions are well-behaved in our analysis of the variance of
the main test statistic. Concretely, we define highly concentrated
distributions by imposing a threshold on the relative concentration
$\rho_{t}(p\;\|\;w)$ introduced in Section 2, where $w$ is the constant vector
of edge weights given by $w(e)=\eta$.

######  Definition 3.1 (Highly concentrated distributions).

Given a constant $C>0$, positive integer $m$, resolution parameter $\eta$, and
probability distribution $p$ over $\mathbb{Z}_{n}$, we say that $p$ is _$C$
-highly concentrated (under resolution $\eta$ with respect to $m$)_ if
$\rho_{t}(p\;\|\;w)\geq\frac{C\log^{2}n}{m}$, where $t=\frac{1}{\log n}$.

One may think of this definition as follows: the average size of a bucket
(connected component) with resolution $\eta$ is $\approx 1/\eta$. In such an
interval $I=\langle\\!\langle i,d\rangle\\!\rangle$ with
$I^{*}=\langle\\!\langle i,d-1\rangle\\!\rangle$, we obtain $w[I^{*}]\approx
1$. If $p[I]/w[I^{*}]\geq\operatorname{poly}\log(n)/m$, then the sample
$\mathsf{Poi}(mp[I])$ ought to produce a large entry $\bm{X}_{i}$, so the
algorithm should be able to reject such distributions. On the other hand, for
intervals $I$ that are very small, the only way to ensure that the algorithm
will likely reject is if $p[I]$ is still large regardless of how small
$w[I^{*}]$ is, which motivates the choice of $t$ in the definition.

######  Remark 3.2.

If $p$ is not $C$-highly concentrated, then in particular
$\|p\|_{\infty}<\frac{C\log n}{m}$, as can be seen by taking intervals
$I=\langle\\!\langle i,1\rangle\\!\rangle$ for each $i\in\mathbb{Z}_{n}$.

We now show that the first step of the tester correctly accepts the uniform
distribution and rejects highly concentrated distributions with good
probability. Therefore, we will be able to assume that $p$ is not highly
concentrated when analyzing the second step of the tester. We will need the
following auxiliary result.

######  Proposition 3.3 (Buckets are almost always small).

Let $K\geq 2$ be a constant, and suppose $n\geq 3$. Then the buckets
$\bm{\Gamma}=(\bm{\Gamma}_{i},\dotsc,\bm{\Gamma}_{\bm{b}})$ induced by
$\bm{H}$ satisfy

$\left\lvert\bm{\Gamma}_{i}\right\rvert\leq\frac{2K\log n}{\eta}\qquad\forall
i\in[\bm{b}]$

except with probability at most $1/n^{K}$.

###### Proof.

Let $d$ be the smallest integer satisfying $d\geq\frac{2K\log n}{\eta}$, and
fix any interval $I=\langle\\!\langle i,d\rangle\\!\rangle$. The probability
that all vertices in this interval are joined is

$\mathbb{P}\left[\bm{J}(I)=1\right]=(1-\eta)^{d-1}\leq(1-\eta)^{\frac{2K\log
n}{\eta}-1}\leq(1-\eta)^{\frac{(2K-1)\log n}{\eta}}\leq e^{-(2K-1)\log
n}=1/n^{2K-1}\leq 1/n^{K+1}\,,$

where we used the facts that $n\geq 3\implies\frac{\log n}{\eta}\geq 1$ and
that $K\geq 2\implies 2K-1\geq K+1$. Now, if any bucket has size at least $d$,
then some interval $I=\langle\\!\langle i,d\rangle\\!\rangle$ satisfies
$J(I)=1$. Since there are at most $n$ such intervals, the probability of this
event is at most $1/n^{K}$ by the union bound. ∎

We will need the following tail bounds for the Poisson distribution, as stated
in [Can17].

######  Fact 3.4.

Let $\bm{X}\sim\mathsf{Poi}(\lambda)$ for some $\lambda>0$. Then for any
$t>0$,

$\mathbb{P}\left[\bm{X}\leq\lambda-t\right],\mathbb{P}\left[\bm{X}\geq\lambda+t\right]\leq
e^{-\frac{t^{2}}{2(\lambda+t)}}\,.$

The result below makes the assumption that $m\leq n\eta$, which simplifies the
analysis and intuitively corresponds to the sublinear sample complexity regime
in the standard uniformity testing model. This assumption turns out to hold
for the range of parameters we consider, but not necessarily in more extreme
regimes (see Remark 3.24).

######  Lemma 3.5.

For sufficiently large constant $\alpha>0$ and all sufficiently large $n$, the
following holds. Suppose $m\leq n\eta$. Then for any distribution $p$ over
$\mathbb{Z}_{n}$, we have:

  1. 1.

If $p$ is uniform, the first step of the tester only rejects with probability
at most $1/100$; and

  2. 2.

If $p$ is $4\alpha$-highly concentrated, the first step of the tester rejects
with probability at least $99/100$.

###### Proof.

Completeness. Suppose $p$ is the uniform distribution over $\mathbb{Z}_{n}$.
From Proposition 3.3, we obtain that every bucket has size at most
$\frac{4\log n}{\eta}$ except with probability $o(1)$. Assume that this is the
case, and fix some particular bucket $\Gamma_{i}$. The number of elements
sampled from this bucket is distributed as
$\bm{X}_{i}\sim\mathsf{Poi}\left(mp\left[\Gamma_{i}\right]\right)=\mathsf{Poi}\left(m|\Gamma_{i}|/n\right)$.
Then, using 3.4 and for $\alpha>16$, the probability that $\bm{X}_{i}$ is so
large that the tester rejects is

$\displaystyle\mathbb{P}\left[\bm{X}_{i}\geq\alpha\log n\right]$
$\displaystyle\leq\mathbb{P}\left[\mathsf{Poi}\left(m\cdot\frac{4\log
n}{\eta}\cdot\frac{1}{n}\right)\geq\alpha\log n\right]$
$\displaystyle\leq\mathbb{P}\left[\mathsf{Poi}(4\log n)\geq\alpha\log
n\right]\qquad$ (Since $m\leq n\eta$)
$\displaystyle=\mathbb{P}\left[\mathsf{Poi}(4\log n)-4\log n\geq(\alpha-4)\log
n\right]$ $\displaystyle\leq e^{-\frac{(\alpha-4)^{2}\log^{2}n}{2(4\log
n+(\alpha-4)\log n)}}\leq e^{-\frac{(\alpha/2)^{2}\log n}{2\alpha}}\leq
e^{-2\log n}=1/n^{2}\,.$

Hence, the probability that this happens for any $\bm{X}_{i}$ is at most
$1/n=o(1)$.

Soundness. Suppose $p$ is $4\alpha$-highly concentrated. Using Lemma 2.14 and
the definition of high concentration, we may choose some interval
$I=\langle\\!\langle i,d\rangle\\!\rangle\in\mathcal{I}$ satisfying

  1. 1.

$(d-1)\eta=w[\langle\\!\langle i,d-1\rangle\\!\rangle]\leq\frac{1}{\log n}$,
and thus $|I|=d\leq 1+\frac{1}{\eta\log n}$; and

  2. 2.

$p[I]\geq\frac{1}{2}\cdot\frac{1}{\log
n}\cdot\frac{4\alpha\log^{2}n}{m}=\frac{2\alpha\log n}{m}$.

We first claim that all the elements in $I$ will be joined with high
probability, i.e. every edge in $I^{*}$ will be sampled into $\bm{H}$. Indeed,
by the union bound, we have

$\mathbb{P}\left[J(I)=0\right]=\mathbb{P}\left[\exists e\in
I^{*}:e\not\in\bm{H}\right]\leq(|I|-1)\cdot\eta\leq\frac{1}{\eta\log
n}\cdot\eta=\frac{1}{\log n}=o(1)\,.$

Now, suppose every element in $I$ belongs to the same bucket, say
$\Gamma_{i}$. Recall that the random variable
$\bm{X}_{i}\sim\mathsf{Poi}\left(mp\left[\Gamma_{i}\right]\right)$ represents
the number of elements drawn from this bucket, and by our assumption on $I$,
we have

$mp\left[\Gamma_{i}\right]\geq m\cdot\frac{2\alpha\log n}{m}=2\alpha\log n\,.$

We now claim that, with high probability, $\bm{X}_{i}>\alpha\log n$ and hence
the tester will reject. Indeed, using 3.4, the probability that this does not
occur is

$\displaystyle\mathbb{P}\left[\bm{X}_{i}\leq\alpha\log n\right]$
$\displaystyle\leq\mathbb{P}\left[\mathsf{Poi}\left(2\alpha\log
n\right)\leq\alpha\log n\right]=\mathbb{P}\left[\mathsf{Poi}\left(2\alpha\log
n\right)\leq 2\alpha\log n-\alpha\log n\right]$ $\displaystyle\leq
e^{-\frac{\alpha^{2}\log^{2}n}{2(2\alpha\log n+\alpha\log
n)}}=e^{-\frac{\alpha\log n}{6}}=o(1)\,.\qed$

We now proceed to the second step of the tester, and analyze the test
statistic $\bm{Y}$.

###  3.2 Expected Value of the Test Statistic

##### Notation.

Let $\mu$ denote the uniform distribution over $\mathbb{Z}_{n}$. We will write
$\bm{\Phi}$ for the random join matrix and $\phi$ for its expectation when
statements hold for both the path and the cycle. Otherwise, we will specify
$\bm{\Phi}^{\mathsf{path}}$ or $\bm{\Phi}^{\mathsf{cycle}}$.

Start by recalling that, as shown in Proposition 2.6, we may write the
expected value of $\bm{Y}$ as

$\mathbb{E}\left[\bm{Y}\right]=mp^{\top}\phi p\,.$ (3)

When $G$ is the path, the expected join matrix
$\phi^{\mathsf{path}}\vcentcolon=\mathbb{E}\left[\bm{\Phi}^{\mathsf{path}}\right]$
has a simple formulation in terms of $\eta$. It will be useful to name the
quantity $1-\eta$, i.e. the probability of including each edge in $\bm{H}$:

$\nu\vcentcolon=1-\eta\,.$

######  Proposition 3.6.

The matrix $\phi^{\mathsf{path}}$ is given by

$\phi^{\mathsf{path}}_{i,j}=\nu^{\lvert i-j\rvert}$

for each $i,j\in\mathbb{Z}_{n}$.

###### Proof.

Here, the relevant intervals are $\mathcal{I}=\mathcal{I}^{\mathsf{path}}$.
Hence, for any $i<j$, we have that $i$ and $j$ are in the same bucket if and
only if every edge between them is in $\bm{H}$:

$\phi^{\mathsf{path}}_{i,j}=\mathbb{P}\left[\bm{\Phi}^{\mathsf{path}}_{i,j}=1\right]=\mathbb{P}\left[\forall
e\in\langle\\!\langle
i,j-i+1\rangle\\!\rangle^{*}:e\in\bm{H}\right]=\nu^{j-i}\,.\qed$

When $G$ is the cycle, so that the expected join matrix is
$\phi^{\mathsf{cycle}}\vcentcolon=\mathbb{E}\left[\bm{\Phi}^{\mathsf{cycle}}\right]$,
we need to account for the small and large intervals (in the notation of
Section 2.5.1) connecting $i$ and $j$, as follows.

######  Proposition 3.7.

The matrix $\phi^{\mathsf{cycle}}$ is given by

$\phi^{\mathsf{cycle}}_{i,j}=\nu^{\lvert i-j\rvert}+\nu^{n-\lvert
i-j\rvert}-\nu^{n}\,.$

###### Proof.

The sets $\operatorname{\mathsf{small}}(i,j)^{*}$ and
$\operatorname{\mathsf{large}}(i,j)^{*}$ have sizes $\min\\{\lvert
i-j\rvert,n-\lvert i-j\rvert\\}$ and $\max\\{\lvert i-j\rvert,n-\lvert
i-j\rvert\\}$, respectively (recall they partition the edges of the cycle). By
the principle of inclusion-exclusion,

$\displaystyle\phi^{\mathsf{cycle}}_{i,j}$
$\displaystyle=\mathbb{P}\left[\bm{\Phi}^{\mathsf{cycle}}_{i,j}=1\right]$
$\displaystyle=\mathbb{P}\left[\bm{J}(\operatorname{\mathsf{small}}(i,j))=1\right]+\mathbb{P}\left[\bm{J}(\operatorname{\mathsf{large}}(i,j))=1\right]-\mathbb{P}\left[\forall
e\in E:e\in\bm{H}\right]$ $\displaystyle=\nu^{\lvert i-j\rvert}+\nu^{n-\lvert
i-j\rvert}-\nu^{n}\,.\qed$

We would like to show that $\mathbb{E}\left[\bm{Y}\right]$ is large when $p$
is far from uniform. Write $p=\mu+z$ where $z\in\mathbb{R}^{\mathbb{Z}_{n}}$.
As shown in Proposition 2.7, we may decompose the expectation as

$\mathbb{E}\left[\bm{Y}\right]=m\mu^{\top}\phi\mu+2m\mu^{\top}\phi
z+mz^{\top}\phi z\,.$ (4)

Letting $\bm{Y}^{(\mu)}$ denote the test statistic when $p$ is the uniform
distribution, we notice that the first term above is precisely the baseline
against which Algorithm 1 thresholds the test statistic:

######  Proposition 3.8 (Expectation of $\bm{Y}$ in the uniform case).

When $p=\mu$, $\bm{Y}=\bm{Y}^{(\mu)}$ satisfies

$\mathbb{E}\left[\bm{Y}^{(\mu)}\right]=m\mu^{\top}\phi\mu=\frac{m}{n^{2}}\sum_{i,j}\phi_{i,j}\,.$

###### Proof.

The claim follows from (3) and the assumption that $p=\mu=\vec{1}/n$. ∎

Therefore, our strategy will be to show that 1) the minimum eigenvalue of
$\phi$ is large, and hence so is $z^{\top}\phi z$ when $\|z\|_{2}^{2}$ is
large; and 2) the term $\mu^{\top}\phi z$ is small in absolute value (in fact
zero when $G$ is the cycle), so it does not affect the sum too much. We start
with the first goal. Both $\phi^{\mathsf{path}}$ and $\phi^{\mathsf{cycle}}$
enjoy nice properties (they are a Toeplitz and a circulant matrix,
respectively), and we bound the minimum eigenvalue of each in turn. Let
${\lambda_{\min}}(\cdot),{\lambda_{\max}}(\cdot)$ denote the minimum and
maximum eigenvalues of a (real symmetric) matrix, respectively.

######  Lemma 3.9 (Minimum eigenvalue of $\phi^{\mathsf{path}}$).

Let $\eta\in(0,1]$. Then $\lambda_{\min}(\phi^{\mathsf{path}})>\eta/2$.

###### Proof.

The matrix $\phi^{\mathsf{path}}$ is a symmetric Toeplitz matrix, and its
inverse may be found as in [Sra]. Recall that $\nu=1-\eta$, so that
$0\leq\nu<1$ and $\phi^{\mathsf{path}}_{i,j}=\nu^{\lvert i-j\rvert}$ by
Proposition 3.6. Then the inverse of $\phi^{\mathsf{path}}$ (written
$\phi^{-1}$ for short) is the following tridiagonal matrix:

$\phi^{-1}=\frac{1}{1-\nu^{2}}\cdot\begin{bmatrix}1&-\nu&0&0&\dotsm&0\\\
-\nu&1+\nu^{2}&-\nu&0&\dotsm&0\\\ 0&-\nu&1+\nu^{2}&-\nu&\dotsm&0\\\
&\ddots&\ddots&\ddots&\ddots&\\\ 0&\dotsc&\dotsc&-\nu&1+\nu^{2}&-\nu\\\
0&\dotsc&\dotsc&0&-\nu&1\\\ \end{bmatrix}\,.$

Now, we may upper bound the maximum eigenvalue of $\phi^{-1}$ using the
Gershgorin circle theorem:

$\lambda_{\max}\left(\phi^{-1}\right)\leq\max_{i\in\mathbb{Z}_{n}}\left\\{\phi^{-1}_{i,i}+\sum_{j\neq
i}\left\lvert\phi^{-1}_{i,j}\right\rvert\right\\}\leq\left(\frac{1}{1-\nu^{2}}\right)\cdot\left(1+\nu^{2}+2\nu\right)=\frac{1+\nu}{1-\nu}\,.$

Hence we obtain

$\lambda_{\min}(\phi^{\mathsf{path}})=\frac{1}{\lambda_{\max}\left(\phi^{-1}\right)}\geq\frac{1-\nu}{1+\nu}>\frac{1-\nu}{2}=\eta/2\,.\qed$

When $G$ is the cycle, it is convenient to work with a simplified close
approximation for $\phi^{\mathsf{cycle}}$. Essentially, we wish to ignore the
large intervals and instead work with the matrix
$\phi^{\operatorname{\mathsf{small}}}$ given by

$\phi^{\operatorname{\mathsf{small}}}_{i,j}\vcentcolon=\nu^{\left\lvert\operatorname{\mathsf{small}}(i,j)\right\rvert-1}\,.$

We will need the observation that $\zeta(\mathcal{I})$ is negligibly small in
our range of parameter $\eta$.

######  Proposition 3.10.

Suppose $\eta\geq\Omega(n^{-1/5})$, and let $K>0$ be any constant. Then for
all sufficiently large $n$,

$\zeta(\mathcal{I})\leq\nu^{n/2}=o(n^{-K})\,.$

###### Proof.

The first inequality is Proposition 2.5. The second one is easy to check:

$\nu^{n/2}=(1-\eta)^{n/2}\leq e^{-\eta\cdot n/2}\leq e^{-\Omega(n^{-1/5}\cdot
n)}=e^{-\Omega(n^{4/5})}=o(n^{-K})\,.\qed$

We are now ready to lower bound the eigenvalues of
$\phi^{\operatorname{\mathsf{small}}}$ and $\phi^{\mathsf{cycle}}$. We first
lower bound $\lambda_{\min}(\phi^{\operatorname{\mathsf{small}}})$, and then
show that the approximation error is negligible.

######  Fact 3.11 (Eigenvalues of circulant matrices; see [Gra06]).

Let $c_{0},c_{1},\dotsc,c_{n-1}\in\mathbb{R}$. Then the matrix

$M=\begin{bmatrix}c_{0}&c_{1}&c_{2}&\cdots&c_{n-1}\\\
c_{n-1}&c_{0}&c_{1}&\cdots&c_{n-2}\\\ \vdots&\vdots&\vdots&\ddots&\vdots\\\
c_{2}&c_{3}&c_{4}&\cdots&c_{1}\\\ c_{1}&c_{2}&c_{3}&\cdots&c_{0}\end{bmatrix}$

given by $M_{j,k}=c_{(k-j)\mod n}$ has eigenvalues

$\lambda_{\ell}=\sum_{k=0}^{n-1}c_{k}\omega^{\ell
k}\qquad\ell=0,1,\dotsc,n-1\,,$

where $\omega=e^{-\frac{2\pi i}{n}}$ is a primitive $n$-th root of unity.

######  Lemma 3.12 (Minimum eigenvalue of
$\phi^{\operatorname{\mathsf{small}}}$).

Let $\eta\in(0,1]$ satisfy $\eta\geq\Omega(n^{-1/5})$. Then for all
sufficiently large $n$,
$\lambda_{\min}(\phi^{\operatorname{\mathsf{small}}})>\eta/3$.

###### Proof.

First assume $n$ is odd. For each $k=0,1,\dotsc,n-1$, let
$c_{k}\vcentcolon=\phi^{\operatorname{\mathsf{small}}}_{0,k}$, so that
$\phi^{\operatorname{\mathsf{small}}}$ is a symmetric circulant matrix of the
form stated in 3.11. In particular, letting $h\vcentcolon=\lfloor n/2\rfloor$
for convenience, we have

$c_{k}=\begin{cases}\nu^{k}&\text{if }k\leq h\\\ \nu^{n-k}&\text{if
}k>h\,.\end{cases}$

Therefore for each $\ell=0,1,\dotsc,n-1$, the eigenvalue $\lambda_{\ell}$ is

$\displaystyle\lambda_{\ell}$ $\displaystyle=\sum_{k=0}^{n-1}c_{k}\omega^{\ell
k}=c_{0}+\sum_{k=1}^{h}\nu^{k}\omega^{\ell
k}+\sum_{k=h+1}^{n-1}\nu^{n-k}\omega^{\ell
k}=1+\sum_{k=1}^{h}\nu^{k}\omega^{\ell
k}+\sum_{k=1}^{h}\nu^{n-(n-k)}\omega^{\ell(n-k)}$
$\displaystyle=1+\sum_{k=1}^{h}\nu^{k}\omega^{\ell
k}+\sum_{k=1}^{h}\nu^{k}\omega^{-\ell
k}=1+\frac{\nu\omega^{\ell}-\nu^{h+1}\omega^{\ell(h+1)}}{1-\nu\omega^{\ell}}+\frac{\nu\omega^{-\ell}-\nu^{h+1}\omega^{-\ell(h+1)}}{1-\nu\omega^{-\ell}}$
$\displaystyle=\frac{1-\nu(\omega^{\ell}+\omega^{-\ell})+\nu^{2}+\nu\omega^{\ell}-\nu^{2}-\nu^{h+1}\omega^{\ell(h+1)}+\nu^{h+2}\omega^{\ell
h}+\nu\omega^{-\ell}-\nu^{2}-\nu^{h+1}\omega^{-\ell(h+1)}+\nu^{h+2}\omega^{-\ell
h}}{1-\nu(\omega^{\ell}+\omega^{-\ell})+\nu^{2}}$
$\displaystyle=\frac{1-\nu^{2}-\nu^{h+1}(\omega^{\ell(h+1)}+\omega^{-\ell(h+1)})+\nu^{h+2}(\omega^{\ell
h}+\omega^{-\ell
h})}{1-\nu(\omega^{\ell}+\omega^{-\ell})+\nu^{2}}=\frac{(1-\nu)(1+\nu)\pm
O(\nu^{n/2})}{1-2\nu\cos(2\pi\ell/n)+\nu^{2}}\,,$

where we used the identity $e^{i\theta}+e^{-i\theta}=2\cos(\theta)$ in the
last step. Thus, recalling that $\nu=1-\eta\in[0,1)$, we conclude that
$\lambda_{\ell}$ is lower bounded by

$\frac{(1-\nu)(1+\nu)\pm
O(\nu^{n/2})}{1-2\nu\cos(2\pi\ell/n)+\nu^{2}}\geq\frac{(1-\nu)(1+\nu)}{(1+\nu)^{2}}-\frac{O(\nu^{n/2})}{(1-\nu)^{2}}\geq\frac{\eta}{2}-\frac{O(\nu^{n/2})}{(1-\nu)^{2}}\,.$

Then, using Proposition 3.10,

$\frac{O(\nu^{n/2})}{(1-\nu)^{2}}\leq\frac{o(n^{-3/5})}{\eta^{2}}\leq
o(n^{-3/5}\cdot n^{2/5})=o(n^{-1/5})=o(\eta)\,,$

and thus $\lambda_{\ell}>\eta/3$. When $n$ is even, the same argument applies
with an extra term of order $O(\nu^{n/2})$, which leaves the asymptotic
analysis unaffected. ∎

######  Lemma 3.13.

Let $\eta\in(0,1]$ satisfy $\eta\geq\Omega(n^{-1/5})$. Then for all
sufficiently large $n$, $\lambda_{\min}(\phi^{\mathsf{cycle}})>\eta/4$.

###### Proof.

Let
$\phi^{\mathsf{err}}\vcentcolon=\phi^{\mathsf{cycle}}-\phi^{\operatorname{\mathsf{small}}}$.
It is standard to check that
$\lambda_{\min}(\phi^{\mathsf{cycle}})\geq\lambda_{\min}(\phi^{\operatorname{\mathsf{small}}})+\lambda_{\min}(\phi^{\mathsf{err}})$.
Since $\lambda_{\min}(\phi^{\operatorname{\mathsf{small}}})>\eta/3$ by Lemma
3.12, it suffices to show that $\lambda_{\min}(\phi^{\mathsf{err}})>-o(\eta)$.
Since
$\phi^{\mathsf{cycle}}_{i,j}=\nu^{\lvert\operatorname{\mathsf{small}}(i,j)\rvert-1}+\nu^{\lvert\operatorname{\mathsf{large}}(i,j)\rvert-1}-\nu^{n}$
by Proposition 3.7, we obtain

$\phi^{\mathsf{err}}_{i,j}=\nu^{\lvert\operatorname{\mathsf{large}}(i,j)\rvert-1}-\nu^{n}$

for all $i,j\in\mathbb{Z}_{n}$. By definition of $\zeta(\mathcal{I})$ and
recalling Proposition 2.5, we conclude that

$\|\phi^{\mathsf{err}}\|_{\infty}\leq\zeta(\mathcal{I})\leq\nu^{n/2}\,.$

By the Gershgorin circle theorem and Proposition 3.10,

$\displaystyle\lambda_{\min}(\phi^{\mathsf{err}})$
$\displaystyle\geq\min_{i\in\mathbb{Z}_{n}}\Big{\\{}\phi^{\mathsf{err}}_{i,i}-\sum_{j\neq
i}\left\lvert\phi^{\mathsf{err}}_{i,j}\right\rvert\Big{\\}}>-n\cdot\nu^{n/2}\geq-n\cdot
o(n^{-6/5})=-o(n^{-1/5})\geq-o(\eta)\,.\qed$

We use the minimum eigenvalue of $\phi$ to show that, if $\|p-\mu\|_{2}^{2}$
is large, then $\mathbb{E}\left[\bm{Y}\right]$ is large. The following
intermediate formulation of the expected value will be useful.

######  Proposition 3.14.

For all sufficiently large $n$, the following holds. Let $p$ be a distribution
over $\mathbb{Z}_{n}$ such that $\mathsf{dist}_{\mathsf{TV}}(p,\mu)>\epsilon$,
and write $p=\mu+z$. Then

$\mathbb{E}\left[\bm{Y}\right]>\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+m\frac{\eta}{8}\|z\|_{2}^{2}+\frac{m}{2n}\epsilon^{2}\eta+2m\mu^{\top}\phi
z\,.$

###### Proof.

First, combine (4) and Proposition 3.8, along with the fact that
$x^{\top}Mx\geq\lambda_{\min}(M)\|x\|_{2}^{2}$ for any symmetric matrix $M$
and vector $x$ and the eigenvalue bounds Lemmas 3.9 and 3.13 to obtain

$\displaystyle\mathbb{E}\left[\bm{Y}\right]$
$\displaystyle=m\mu^{\top}\phi\mu+2m\mu^{\top}\phi z+mz^{\top}\phi z$
$\displaystyle\geq\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+m\lambda_{\min}(\phi)\|z\|_{2}^{2}+2m\mu^{\top}\phi
z$
$\displaystyle\geq\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+m\frac{\eta}{4}\|z\|_{2}^{2}+2m\mu^{\top}\phi
z$
$\displaystyle=\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+m\frac{\eta}{8}\|z\|_{2}^{2}+m\frac{\eta}{8}\|z\|_{2}^{2}+2m\mu^{\top}\phi
z\,.$

Then, since $\|z\|_{1}=2\mathsf{dist}_{\mathsf{TV}}(p,\mu)>2\epsilon$, we have
$\|z\|_{2}^{2}>\left(\frac{2\epsilon}{n}\right)^{2}\cdot n=4\epsilon^{2}/n$,
concluding the proof. ∎

Now we show that the cross term $\mu^{\top}\phi z$ is small. When $G$ is the
cycle, this term will in fact be zero; when $G$ is the path, the cross term is
relevant due to the asymmetry between the vertices closer to the endpoints or
to the middle. However, this will not be a problem as long as $\|z\|_{\infty}$
is not too large, which indeed holds when $p$ is not highly concentrated.

######  Proposition 3.15.

Let $\eta\in(0,1]$ and let $\phi=\mathbb{E}\left[\bm{\Phi}\right]$ be the
corresponding expected join matrix. Let $\delta>0$ be any positive real
number. Then for any $z\in\mathbb{R}^{n}$ satisfying

  1. 1.

$\sum_{i}z_{i}=0$; and

  2. 2.

$\|z\|_{\infty}\leq\delta$,

it is the case that

$\left\lvert\mu^{\top}\phi z\right\rvert\leq\frac{2\delta}{n\eta^{2}}\,.$

###### Proof.

When $\phi=\phi^{\mathsf{cycle}}$, we have that $\mu^{\top}\phi$ is a constant
vector (this is true for any circulant matrix), and hence $\mu^{\top}\phi z=0$
(since $\sum_{i}z_{i}=0$). Therefore we may now assume that
$\phi=\phi^{\mathsf{path}}$.

Note that, by symmetry between $z$ and $-z$ in the LHS, it suffices upper
bound $\mu^{\top}\phi z$. We expand this expression as follows:

$\mu^{\top}\phi
z=\sum_{i,j\in\mathbb{Z}_{n}}\mu_{i}z_{j}\phi_{i,j}=\frac{1}{n}\sum_{j=0}^{n-1}z_{j}\left(\sum_{i=0}^{n-1}\phi_{i,j}\right)\,.$

Hence our goal is to show

$\sum_{j=0}^{n-1}z_{j}S_{j}\stackrel{{\scriptstyle\mathclap{\mbox{?}}}}{{\leq}}\frac{2\delta}{\eta^{2}}\,,$
(5)

where $S_{j}\vcentcolon=\left(\sum_{i=0}^{n-1}\phi_{i,j}\right)$ is the sum of
the entries in the $j$-th column of $\phi$. Note that
$(S_{j})_{j=0,\dotsc,n-1}$ is a symmetric unimodal sequence (first increasing,
then decreasing) with strict inequalities everywhere except for indices
$\lfloor(n-1)/2\rfloor$ and $\lceil(n-1)/2\rceil$ when $n$ is even. We will
use a “rearrangement and saturation” argument to construct a vector $z^{*}$
that upper bounds the LHS of (5) (hereafter called the _objective value_).

Let $z^{\prime}$ be a vector satisfying the conditions from the statement
(hereafter called a _feasible solution_) that maximizes the objective value.
Let $\sigma$ be a permutation of $\\{0,\dotsc,n-1\\}$ that puts the sequence
of column sums in non-decreasing order: $S_{\sigma(0)}\leq\dotsm\leq
S_{\sigma(n-1)}$. Then we can also assume that $z^{\prime}$ respects this
order: $z^{\prime}_{\sigma(0)}\leq\dotsm\leq z^{\prime}_{\sigma(n-1)}$, since
otherwise rearranging the entries of $z^{\prime}$ would yield another feasible
solution with equal or larger objective value.

We now argue that we may assume that, among all nonzero entries of
$z^{\prime}$, all have absolute value equal to $\delta$ (which we call
_saturated entries_) except for at most one positive entry and one negative
entry. Indeed, if two consecutive (under $\sigma)$ nonzero entries with the
same sign are not saturated, i.e. they satisfy $\left\lvert
z^{\prime}_{\sigma(i)}\right\rvert,\left\lvert
z^{\prime}_{\sigma(i+1)}\right\rvert<\delta$, then we can obtain another
feasible solution with equal or larger objective value by “saturating” this
pair of entries, i.e. making $z^{\prime}_{\sigma(i)}$ smaller and
$z^{\prime}_{\sigma(i+1)}$ larger until either of them reaches a value in
$\\{-\delta,0,\delta\\}$.

We claim that we may also assume that the multiset of values of the positive
entries of $z^{\prime}$ is equal to the multiset of absolute values of the
negative entries of $z^{\prime}$. Suppose $z^{\prime}$ has $N^{+}$ entries
equal to $\delta$, $N^{-}$ entries equal to $-\delta$, $M^{+}\in\\{0,1\\}$
entries in the interval $(0,\delta)$, and $M^{-}\in\\{0,1\\}$ entries in the
interval $(-\delta,0)$. If $N^{+}=N^{-}$, then since
$\sum_{j}z^{\prime}_{j}=0$, we must also have $M^{+}=M^{-}$ and, if this value
is $1$, then the corresponding entries of $z^{\prime}$ must have the same
absolute value so that they add to zero. On the other hand, if $N^{+}\neq
N^{-}$, say $N^{+}>N^{-}$ without loss of generality, then
$\sum_{i}z^{\prime}_{i}>0$ since the sum of the saturated values of
$z^{\prime}$ is at least $\delta$ while the sum of the non-saturated values
must be in $(-\delta,\delta)$. This contradicts the fact that $z^{\prime}$ is
a feasible solution.

Now we construct $z^{*}$ by saturating the remaining (zero or two) entries of
$z^{\prime}$:

$z^{*}_{i}\vcentcolon=\begin{cases}\delta,&\text{if $z^{\prime}_{i}>0$}\\\
-\delta,&\text{if $z^{\prime}_{i}<0$}\\\ 0,&\text{if
$z^{\prime}_{i}=0$.}\end{cases}$

Then by the same arguments as above, $z^{*}$ has equal or larger objective
value as $z^{\prime}$. We now upper bound this objective value by the RHS of
(5), which will conclude the argument.

Let $N$ be the number of positive entries of $z^{*}$. By construction, we have

$N=|\\{i\in\mathbb{Z}_{n}:z^{*}_{i}=\delta\\}|=|\\{i\in\mathbb{Z}_{n}:z^{*}_{i}=-\delta\\}|\,.$

Then our objective value is

$\sum_{j}z^{*}_{j}S_{j}=\delta\left[-\sum_{i=0}^{N-1}S_{\sigma(i)}+\sum_{i=0}^{N-1}S_{\sigma(n-1-i)}\right]\,.$
(6)

Let $h\vcentcolon=(n-1)/2$. Since $(S_{j})_{j=0,\dotsc,n-1}$ is a symmetric
unimodal sequence attaining its maximum in the middle, we may say without loss
of generality that the indices $\sigma(i)$ in the first summation term in the
RHS of (6) are $\\{0,\dotsc,\lceil N/2\rceil-1\\}\cup\\{n-1,\dotsc,n-\lfloor
N/2\rfloor\\}$. As for the indices $\sigma(n-1-i)$, an exact account depends
on the parity of $n$, but we can only make the objective value larger by
simply using the indices $\\{\lceil h\rceil,\dotsc,\lceil h\rceil+\lceil
N/2\rceil-1\\}\cup\\{\lfloor h\rfloor,\dotsc,\lfloor h\rfloor-\lfloor
N/2\rfloor+1\\}$. Note that when $n$ is odd, this choice slightly
overestimates the objective value by using the maximum value $S_{h}$ twice,
but this looser bound suffices for our purposes.

Therefore, we may finally express and compute our upper bound on the objective
value of any feasible vector $z$. Recall that $\phi_{i,j}=\nu^{\lvert
i-j\rvert}$. In the edge case when $\eta=1$ and thus $\nu=0$, we have that
$\phi$ is the identity matrix and hence $S_{j}=1$ for every
$j\in\mathbb{Z}_{n}$. Therefore we obtain

$\displaystyle\sum_{j=0}^{n-1}z_{j}S_{j}=\sum_{j=0}^{n-1}z_{j}=0\,,$

which satisfies (5) and we are done. Now, suppose $0<\nu<1$. Then

$\displaystyle\sum_{j=0}^{n-1}z_{j}S_{j}$
$\displaystyle\leq\delta\left[-\sum_{i=0}^{N-1}S_{\sigma(i)}+\sum_{i=0}^{N-1}S_{\sigma(n-1-i)}\right]$
$\displaystyle\leq\delta\left[-\sum_{i=0}^{\lceil
N/2\rceil-1}S_{i}-\sum_{i=0}^{\lfloor
N/2\rfloor-1}S_{n-1-i}+\sum_{i=0}^{\lceil N/2\rceil-1}S_{\lceil
h\rceil+i}+\sum_{i=0}^{\lfloor N/2\rfloor-1}S_{\lfloor
h\rfloor-i}\right]\leq\frac{2\delta}{\eta^{2}}\,,$

where we defer the tedious geometric sum calculations for the last inequality
to Proposition B.1. ∎

######  Lemma 3.16.

Let $C>0$, and let $p$ be a distribution over $\mathbb{Z}_{n}$ that is not
$C$-highly concentrated. Then as long as $\frac{8C\log
n}{\eta^{3}\epsilon^{2}}\leq m\leq Cn\log n$, the following holds:

$\left\lvert 2m\mu^{\top}\phi
z\right\rvert\leq\frac{m}{2n}\epsilon^{2}\eta\,.$

###### Proof.

Write $p=\mu+z$. Since $\|p\|_{1}=\|\mu\|_{1}=1$, it follows that
$\sum_{i}z_{i}=0$, satisfying the first condition of Proposition 3.15. We will
show that $z$ also satisfies the second condition with
$\delta\vcentcolon=\frac{C\log n}{m}$.

Indeed, since $0\leq\frac{1}{n}+z_{i}\leq\frac{C\log n}{m}$ (the second
inequality by Remark 3.2) we get, on the one hand,

$z_{i}\geq-\frac{1}{n}\geq-\frac{C\log n}{m}\,,$

where we used the assumption that $m\leq Cn\log n$, and on the other hand,

$z_{i}\leq\frac{C\log n}{m}-\frac{1}{n}\leq\frac{C\log n}{m}\,,$

and thus $\|z\|_{\infty}\leq\frac{C\log n}{m}$ as desired. Proposition 3.15
implies that

$\left\lvert\mu^{\top}\phi z\right\rvert\leq\frac{2C\log n}{mn\eta^{2}}\,.$

Finally, it suffices to combine this inequality with our assumed lower bound
on $m$. We obtain

$\left\lvert 2m\mu^{\top}\phi z\right\rvert\leq 2m\cdot\frac{2C\log
n}{mn\eta^{2}}=\frac{8C\log
n}{\eta^{3}\epsilon^{2}}\cdot\frac{\epsilon^{2}\eta}{2n}\leq\frac{m}{2n}\epsilon^{2}\eta\,.\qed$

We combine the previous results to show the desired separation in the expected
value of $\bm{Y}$:

######  Lemma 3.17 (Separation in the expected value of $\bm{Y}$).

Let $C,c>0$ be constants, and let
$m=c\cdot\frac{\sqrt{n}}{\epsilon^{2}\eta^{3/2}}\log^{2}n$. Then for all
sufficiently large $n$ and all $\epsilon,\eta\in(0,1]$ satisfying
$\eta\geq(c/C)^{2/3}\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}$, the following
holds. Suppose $p$ is a distribution over $\mathbb{Z}_{n}$ that is not
$C$-highly concentrated such that
$\mathsf{dist}_{\mathsf{TV}}(p,\mu)>\epsilon$. Write $p=\mu+z$. Then the test
statistic $\bm{Y}$ satisfies

$\mathbb{E}\left[\bm{Y}\right]>\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+\frac{m\eta}{8}\|z\|_{2}^{2}\,.$

###### Proof.

By Proposition 3.14, we have

$\mathbb{E}\left[\bm{Y}\right]>\mathbb{E}\left[\bm{Y}^{(\mu)}\right]+\frac{m\eta}{8}\|z\|_{2}^{2}+\frac{m}{2n}\epsilon^{2}\eta+2m\mu^{\top}\phi
z\,.$

Hence, we will be done if we can show that $2m\mu^{\top}\phi
z\geq-\frac{m}{2n}\epsilon^{2}\eta$. This will follow immediately from Lemma
3.16 as long as we can verify the preconditions on $m$. We first check the
lower bound:

$m\geq\frac{8C\log n}{\eta^{3}\epsilon^{2}}\iff
c\frac{\sqrt{n}}{\epsilon^{2}}\cdot\frac{\log^{2}n}{\eta^{3/2}}\geq\frac{8C\log
n}{\eta^{3}\epsilon^{2}}\iff\eta\geq(8C/c)^{2/3}\frac{1}{n^{1/3}\log^{2/3}n}\,,$

which holds for all sufficiently large $n$ by our assumption on $\eta$. As for
the upper bound,

$m\leq Cn\log n\iff
c\frac{\sqrt{n}}{\epsilon^{2}}\cdot\frac{\log^{2}n}{\eta^{3/2}}\leq Cn\log
n\iff\eta\geq(c/C)^{2/3}\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}\,,$

which holds by assumption. Hence Lemma 3.16 applies and we are done. ∎

######  Remark 3.18.

The condition
$\eta=\Omega\left(\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}\right)$ in the
statement above will hold in the range of parameters considered by the present
argument. Concretely, when
$\eta=\Omega\left(\frac{\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}\right)$ and
$\epsilon=\Omega\left(\frac{1}{n^{1/4}}\right)$, the condition holds because

$\frac{\left(\frac{\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}\right)}{\left(\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}\right)}=(\log
n)^{2/15}n^{2/15}\epsilon^{8/15}\geq(\log
n)^{2/15}n^{2/15}\Omega(n^{-2/15})=\omega(1)\,.$

###  3.3 Concentration of the Test Statistic

We apply the general results presented in Section 2.5.3 to upper bound the
variance of $\bm{Y}$.

######  Lemma 3.19 (First component of the variance).

Let $C>0$ be a constant, let $n\in\mathbb{N}$ be sufficiently large and
suppose $p$ is a probability distribution over $\mathbb{Z}_{n}$ that is not
$C$-highly concentrated. Suppose that $m\leq\operatorname{poly}(n)$ and
$\eta\geq\Omega(n^{-1/5})$. Then

$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq\frac{\|p\|_{2}^{2}}{\eta}\cdot
O\left(\log^{4}n\right)\,.$

###### Proof.

By Lemma 2.9, for some constant $c>0$ we have

$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq
5m^{2}\zeta(\mathcal{I})\|p\|_{1}^{4}+cm^{2}\cdot\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}p_{i}p_{i+d-1}p[I]^{2}\mathbb{E}\left[\bm{J}(I)\right]\,.$

We start with the second component of the RHS. Recall that for any
$I=\langle\\!\langle i,d\rangle\\!\rangle$,
$\mathbb{E}\left[\bm{J}(I)\right]\leq\nu^{d-1}$ (this value may be zero if
$\mathcal{I}=\mathcal{I}^{\mathsf{path}}$ and $I$ crosses the edge between
vertices $0$ and $n-1$). We have

$\displaystyle\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}p_{i}p_{i+d-1}p[I]^{2}\mathbb{E}\left[\bm{J}(I)\right]\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}p_{i}p_{i+d-1}p[\langle\\!\langle
i,d\rangle\\!\rangle]^{2}\nu^{d-1}$
$\displaystyle\quad\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}p_{i}p_{i+d-1}\nu^{d-1}\left[\frac{C\log^{2}n}{m}\cdot\max\left\\{\eta(d-1),\frac{1}{\log
n}\right\\}\right]^{2}$ ($p$ is not $C$-highly-concentrated)
$\displaystyle\quad\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}p_{i}p_{i+d-1}\nu^{d-1}\left[\frac{C^{2}\log^{4}n}{m^{2}}\cdot\left(\eta^{2}d^{2}+\frac{1}{\log^{2}n}\right)\right]$
$\displaystyle\quad=\frac{C^{2}\log^{2}n}{m^{2}}\left(\eta^{2}\log^{2}(n)\sum_{d=1}^{n}d^{2}\nu^{d-1}\sum_{i=0}^{n-1}p_{i}p_{i+d-1}+\sum_{d=1}^{n}\nu^{d-1}\sum_{i=0}^{n-1}p_{i}p_{i+d-1}\right)$
$\displaystyle\quad\leq\frac{C^{2}\|p\|_{2}^{2}\log^{2}n}{m^{2}}\left(\eta^{2}\log^{2}(n)\sum_{d=1}^{n}d^{2}\nu^{d-1}+\sum_{d=1}^{n}\nu^{d-1}\right)$
(by Cauchy-Schwarz)
$\displaystyle\quad\leq\frac{C^{2}\|p\|_{2}^{2}\log^{2}n}{m^{2}}\left(\eta^{2}\log^{2}(n)\frac{1+\nu}{\eta^{3}}+\frac{1}{\eta}\right)$
(since $\eta=1-\nu$)
$\displaystyle\quad\leq\frac{3C^{2}\|p\|_{2}^{2}\log^{4}n}{m^{2}\eta}$ (since
$\nu<1$)
$\displaystyle\quad=\frac{1}{m^{2}}\cdot\frac{\|p\|_{2}^{2}}{\eta}\cdot
O\left(\log^{4}n\right)\,,$

as desired. Then, it suffices to show that the term
$5m^{2}\zeta(\mathcal{I})\|p\|_{1}^{4}$ is $O(1/n)$, since
$\|p\|_{2}^{2}\geq\|\mu\|_{2}^{2}=1/n$. Let $K>0$ be a constant such that
$m\leq n^{K}$ for sufficiently large $n$, as per the assumption that
$m\leq\operatorname{poly}(n)$. Then we have $\|p\|_{1}^{4}=1$ and
$m^{2}\zeta(\mathcal{I})=o(m^{2}/n^{2K+1})\leq o(1/n)$ by Proposition 3.10, as
needed. ∎

######  Lemma 3.20 (Second component of the variance).

Let $C>0$ be a constant, let $n\in\mathbb{N}$ be sufficiently large and
suppose $p$ is a probability distribution over $\mathbb{Z}_{n}$ that is not
$C$-highly concentrated. Suppose $m\leq\operatorname{poly}(n)$. Then

$\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq\frac{\|p\|_{2}^{2}}{\eta}\cdot
O(\log^{4}n)\,.$

###### Proof.

Let $K\geq 2$ be some constant such that $m\leq O(n^{K-1})$. Recall that, from
Proposition 3.3, the buckets
$\bm{\Gamma}=(\bm{\Gamma}_{1},\dotsc,\bm{\Gamma}_{n})$ induced by $\bm{H}$ are
such that $\left\lvert\bm{\Gamma}_{i}\right\rvert\leq\frac{2K\log n}{\eta}$
for all $i$, except with probability at most $1/n^{K}$. We show that the
variance is small when this condition holds, and that the low-probability case
where the condition fails does not contribute too much to the expectation.

Case 1. Suppose $H$ is such that its induced buckets
$\Gamma=(\Gamma_{1},\dotsc,\Gamma_{b})$ satisfy
$\left\lvert\Gamma_{i}\right\rvert\leq\frac{2K\log n}{\eta}$ for every
$i\in[n]$. We wish to show that
$\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]$
satisfies the upper bound from the statement. We start with the result from
Lemma 2.12:

$\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]=2\|p_{|\Gamma}\|_{2}^{2}+4m\|p_{|\Gamma}\|_{3}^{3}\,.$