$\displaystyle=\frac{1}{m^{2}}\left(\mathbb{E}\left[\bm{T}^{\top}\bm{\Phi}\bm{T}\right]-\mathbb{E}\left[\|\bm{T}\|_{1}\right]\right)=\frac{1}{m^{2}}\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^{2}}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]$
$\displaystyle=\frac{1}{m^{2}}\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^{2}}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]-\frac{1}{m^{2}}\sum_{i=0}^{n-1}\mathbb{E}\left[\bm{T}_{i}\right]=\frac{1}{m^{2}}\sum_{i=0}^{n-1}\sum_{j=0}^{n-1}(m\mu_{i})(m\mu_{j})\phi_{i,j}$
$\displaystyle=\mu^{\top}\phi\mu\,.\qed$

We would like to show that $\mathbb{E}\left[\bm{Y}\right]$ is small when
$\mu=\nu$ is uniform, and large when $\mu$ is far from uniform. Letting
$\bm{Y}^{(\nu)}$ denote the test statistic when $\mu$ is the uniform
distribution, we have:

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

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

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

###### Proof.

The claim follows from Proposition 4.4 and the assumption that
$\mu=\nu=\vec{1}/n$. ∎

We must now show that $\mathbb{E}\left[\bm{Y}\right]$ is larger than this
threshold when $\mu$ is far from uniform.

######  Proposition 4.6.

Write $\mu=\nu+z$. Then $\bm{Y}$ satisfies

$\mathbb{E}\left[\bm{Y}\right]=\nu^{\top}\phi\nu+2\nu^{\top}\phi
z+z^{\top}\phi z\,.$

###### Proof.

This follows immediately from Proposition 4.4 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]$. ∎

Therefore, we must find a lower bound on $2\nu^{\top}\phi z+z^{\top}\phi z$.
Our strategy will be:

  1. 1.

Show that the minimum eigenvalue of $\phi$ is large, and hence so is
$z^{\top}\phi z$ when $\|z\|_{2}^{2}$ is large; we will do this separately for
the path and the cycle.

  2. 2.

Show that the term $\nu^{\top}\phi z$ is small in absolute value, so it does
not affect the sum too much.

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.

####  4.2.1 Expectation for the Path

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 $\rho$. Recall the notation
$\eta\vcentcolon=1-\rho$.

######  Proposition 4.7.

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

$\phi^{\mathsf{path}}_{i,j}=\eta^{\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 cell 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]=\eta^{j-i}\,.\qed$

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

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

###### Proof.

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

$\phi^{-1}=\frac{1}{1-\eta^{2}}\cdot\begin{bmatrix}1&-\eta&0&0&\dotsm&0\\\
-\eta&1+\eta^{2}&-\eta&0&\dotsm&0\\\ 0&-\eta&1+\eta^{2}&-\eta&\dotsm&0\\\
&\ddots&\ddots&\ddots&\ddots&\\\ 0&\dotsc&\dotsc&-\eta&1+\eta^{2}&-\eta\\\
0&\dotsc&\dotsc&0&-\eta&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-\eta^{2}}\right)\cdot\left(1+\eta^{2}+2\eta\right)=\frac{1+\eta}{1-\eta}\,.$

Hence we obtain

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

####  4.2.2 Expectation for the Cycle

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 4.1.1) connecting $i$ and $j$, as follows.

######  Proposition 4.9.

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

$\phi^{\mathsf{cycle}}_{i,j}=\eta^{\lvert i-j\rvert}+\eta^{n-\lvert
i-j\rvert}-\eta^{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=\eta^{\lvert
i-j\rvert}+\eta^{n-\lvert i-j\rvert}-\eta^{n}\,.\qed$

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=\eta^{\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 $\rho$.

######  Proposition 4.10.

Let $\delta\in(0,1)$ be a constant. Suppose $\rho\geq\Omega(n^{-\delta})$, and
let $K>0$ be any constant. Then for all sufficiently large $n$,

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

###### Proof.

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

$\eta^{n/2}=(1-\rho)^{n/2}\leq e^{-\rho\cdot n/2}\leq
e^{-\Omega(n^{-\delta}\cdot n)}=e^{-\Omega(n^{1-\delta})}=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 4.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 4.12 (Minimum eigenvalue of
$\phi^{\operatorname{\mathsf{small}}}$).

Let $\delta\in(0,1)$ be a constant and suppose $\rho\geq\Omega(n^{-\delta})$.
Then for all sufficiently large $n$,
$\lambda_{\min}(\phi^{\operatorname{\mathsf{small}}})>\rho/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 4.11. In particular, letting $h\vcentcolon=\lfloor n/2\rfloor$
for convenience, we have

$c_{k}=\begin{cases}\eta^{k}&\text{if }k\leq h\\\ \eta^{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}\eta^{k}\omega^{\ell
k}+\sum_{k=h+1}^{n-1}\eta^{n-k}\omega^{\ell
k}=1+\sum_{k=1}^{h}\eta^{k}\omega^{\ell
k}+\sum_{k=1}^{h}\eta^{n-(n-k)}\omega^{\ell(n-k)}$
$\displaystyle=1+\sum_{k=1}^{h}\eta^{k}\omega^{\ell
k}+\sum_{k=1}^{h}\eta^{k}\omega^{-\ell
k}=1+\frac{\eta\omega^{\ell}-\eta^{h+1}\omega^{\ell(h+1)}}{1-\eta\omega^{\ell}}+\frac{\eta\omega^{-\ell}-\eta^{h+1}\omega^{-\ell(h+1)}}{1-\eta\omega^{-\ell}}$
$\displaystyle=\frac{1-\eta(\omega^{\ell}+\omega^{-\ell})+\eta^{2}+\eta\omega^{\ell}-\eta^{2}-\eta^{h+1}\omega^{\ell(h+1)}+\eta^{h+2}\omega^{\ell
h}+\eta\omega^{-\ell}-\eta^{2}-\eta^{h+1}\omega^{-\ell(h+1)}+\eta^{h+2}\omega^{-\ell
h}}{1-\eta(\omega^{\ell}+\omega^{-\ell})+\eta^{2}}$
$\displaystyle=\frac{1-\eta^{2}-\eta^{h+1}(\omega^{\ell(h+1)}+\omega^{-\ell(h+1)})+\eta^{h+2}(\omega^{\ell
h}+\omega^{-\ell
h})}{1-\eta(\omega^{\ell}+\omega^{-\ell})+\eta^{2}}=\frac{(1-\eta)(1+\eta)\pm
O(\eta^{n/2})}{1-2\eta\cos(2\pi\ell/n)+\eta^{2}}\,,$

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

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

Then, using Proposition 4.10 with $K=3\delta$,

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

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

######  Lemma 4.13.

Let $\delta\in(0,1)$ be a constant and suppose $\rho\geq\Omega(n^{-\delta})$.
Then for all sufficiently large $n$,
$\lambda_{\min}(\phi^{\mathsf{cycle}})>\rho/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}}})>\rho/3$ by Lemma
4.12, it suffices to show that $\lambda_{\min}(\phi^{\mathsf{err}})>-o(\rho)$.
Since
$\phi^{\mathsf{cycle}}_{i,j}=\eta^{\lvert\operatorname{\mathsf{small}}(i,j)\rvert-1}+\eta^{\lvert\operatorname{\mathsf{large}}(i,j)\rvert-1}-\eta^{n}$
by Proposition 4.9, we obtain

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

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

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

By the Gershgorin circle theorem and Proposition 4.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\eta^{n/2}\geq-n\cdot
o(n^{-1-\delta})=-o(n^{-\delta})\geq-o(\rho)\,.\qed$

####  4.2.3 Bounds on the Cross Term

Now we show that the cross term $\nu^{\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 the tester will be able to check).

######  Proposition 4.14.

Let $\rho\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\nu^{\top}\phi z\right\rvert\leq\frac{2\delta}{n\rho^{2}}\,.$

Proposition 4.14 is proved by constructing a worst-case vector $z$ whose
negative (respectively positive) entries are as concentrated as possible
toward the ends (respectively the middle) of the vector, subject to the
$\ell_{\infty}$ constraint, and evaluating geometric series to upper bound the
cross term. The proof is elementary, and we defer it to Appendix B.

######  Lemma 4.15.

Let $C>0$, and let $\mu$ be a distribution over $\mathbb{Z}_{n}$ satisfying
$\|\mu\|_{\infty}\leq\frac{C\log n}{m}$. Then as long as $\frac{8C\log
n}{\rho^{3}\epsilon^{2}}\leq m\leq Cn\log n$, the following holds:

$\left\lvert 2\nu^{\top}\phi z\right\rvert\leq\frac{1}{2n}\epsilon^{2}\rho\,.$

###### Proof.

Write $\mu=\nu+z$. Since $\|\mu\|_{1}=\|\nu\|_{1}=1$, it follows that
$\sum_{i}z_{i}=0$, satisfying the first condition of Proposition 4.14. We will
show that $z$ also satisfies the second condition with
$\delta\vcentcolon=\frac{C\log n}{m}$. Indeed, that $z_{i}\leq\frac{C\log
n}{m}$ for every $i$ follows immediately from the assumption on $\mu$. On the
other hand, using the assumption that $m\leq Cn\log n$ we conclude that
$z_{i}=\mu(i)-\frac{1}{n}\geq-\frac{1}{n}\geq-\frac{C\log n}{m}$ and thus
$\|z\|_{\infty}\leq\frac{C\log n}{m}$ as desired. Proposition 4.14 implies
that $\left\lvert\nu^{\top}\phi z\right\rvert\leq\frac{2C\log n}{mn\rho^{2}}$,
and combining this inequality with our assumed lower bound on $m$ we obtain

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

####  4.2.4 Gap in Expected Values

We combine the previous results to show the desired separation in the expected
value of $\bm{Y}$. The first step is to incorporate the eigenvalue bounds:

######  Proposition 4.16.

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

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

###### Proof.

Combine Propositions 4.6 and 4.5, 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 4.8 and 4.13 to obtain

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

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

######  Lemma 4.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}\rho^{3/2}}\log^{2}n$. Then for all
sufficiently large $n$ and all $\epsilon,\rho\in(0,1]$ satisfying
$\rho\geq(c/C)^{2/3}\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}$, the following
holds. Suppose $\mu$ is a distribution over $\mathbb{Z}_{n}$ satisfying
$\|\mu\|_{\infty}\leq\frac{C\log n}{m}$ and
$\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)>\epsilon$. Write $\mu=\nu+z$. Then the
test statistic $\bm{Y}$ satisfies

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

###### Proof.

By Proposition 4.16, we have

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

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

$m\geq\frac{8C\log n}{\rho^{3}\epsilon^{2}}\iff
c\frac{\sqrt{n}}{\epsilon^{2}}\cdot\frac{\log^{2}n}{\rho^{3/2}}\geq\frac{8C\log
n}{\rho^{3}\epsilon^{2}}\iff\rho\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 $\rho$. As for
the upper bound,

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

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

###  4.3 Concentration of the Test Statistic

Our goal in this section is to establish the concentration of the test
statistic $\bm{Y}$, by giving the formal version of Lemma 1.6. Recall that the
(random) partition of vertices into cells
$\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]\,.$

####  4.3.1 Relative Concentration

One of the main tools in our analysis will be “relative concentration”,
which compares the probability mass of $\mu$ inside the circular intervals $I$
to the size of that interval, weighted by the resolution $\rho$ – with the
crucial addition that intervals with weight less than some threshold $t$
essentially have no effect, so this notion differs from the standard
$\ell_{\infty}$ norm in that it “smooths out” small perturbations.

######  Definition 4.18 (Relative Concentration).

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$
and let $\mu:\mathbb{Z}_{n}\to\mathbb{R}_{\geq 0}$ be a probability
distribution. Let $t>0$. Then we define

$\chi_{t}(\mu)\vcentcolon=\max_{I\in\mathcal{I}:|I|\leq
n}\frac{\mu[I]}{\max\left\\{\rho|I^{*}|,t\right\\}}\,.$

We will instantiate this measure with $t=\frac{1}{\log n}$ and use it in the
analysis of the tester in Section 4.4. We will require the following lemma,
which allows us to find an interval $I$ exhibiting a large ratio between
$\mu[I]$ and $\rho|I^{*}|$ if we assume high relative concentration
$\chi_{t}(\mu)$.

######  Proposition 4.19.

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$,
and let $\mu:\mathbb{Z}_{n}\to\mathbb{R}_{\geq 0}$ be a probability
distribution. Then there exists $I\in\mathcal{I}$ satisfying:

  1. 1.

$\rho|I^{*}|\leq t$; and

  2. 2.

$\mu[I]\geq\frac{1}{2}\cdot t\cdot\chi_{t}(\mu)$.

###### Proof.

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

  1. 1.

$\rho|I^{*}|\leq t$ and $\mu[I]=t\cdot\chi_{t}(\mu)$; or

  2. 2.

$\rho|I^{*}|\geq t$ and $\mu[I]=\rho|I^{*}|\cdot\chi_{t}(\mu)$.

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 minimal interval satisfying $\rho|I^{*}|\geq t$ and
$\mu[I]\geq\rho|I^{*}|\chi_{t}(\mu)$ (in particular, equality will hold). Note
that we must have $|I|\geq 2$, since otherwise $I^{*}$ would be empty,
contradicting the assumption that $\rho|I^{*}|\geq t>0$.

Consider any partition partition $I=L\cup R$ into two intervals $L,R$ such
that $L$ is on the left and $R$ is on the right. Then the following inequality
holds:

$\chi_{t}(\mu)=\frac{\mu[I]}{\rho|I^{*}|}=\frac{\mu[L]+\mu[R]}{\rho|L^{*}|+\rho|I^{*}\setminus
L^{*}|}\leq\max\left\\{\frac{\mu[L]}{\rho|L^{*}|},\frac{\mu[R]}{\rho|I^{*}\setminus
L^{*}|}\right\\}\leq\max\left\\{\frac{\mu[L]}{\rho|L^{*}|},\frac{\mu[R]}{\rho|R^{*}|}\right\\}\,.$

Consider separately the cases where $|I|$ is even or odd. First suppose $|I|$
is even. Then partition $I=L\cup R$ such that $|L|=|R|=|I|/2$ and observe that
$|L^{*}|=|R^{*}|$, so either $\rho|L^{*}|,\rho|R^{*}|<t$ or
$\rho|L^{*}|,\rho|R^{*}|\geq t$. If $\rho|L^{*}|<t$ then either
$\mu[L]\geq\mu[I]/2\geq\frac{t}{2}\chi_{t}(\mu)$ and $L$ satisfies the desired
conditions (due to the inequality above), or $\mu[R]\geq\mu[I]/2$ and $R$
satisfies the desired conditions. On the other hand, if $\mu[L]\geq t$ then
either $L$ or $R$ contradicts the minimality of $I$.

Now suppose $|I|$ is odd. Consider two ways to partition $I$ into intervals.
Let $I=L_{-}\cup R_{-}$ be the partition such that
$|L_{-}|=\lfloor|I|/2\rfloor$ and $|R_{-}|=\lceil|I|/2\rceil$, and let
$I=L_{+}\cup R_{+}$ be the partition such that $|L_{+}|=\lceil|I|/2\rceil$ and
$|R_{+}|=\lfloor|I|/2\rfloor$. Note that $|L_{-}^{*}|=|R_{+}^{*}|$ and
$|L_{+}^{*}|=|R_{-}^{*}|=|I^{*}|/2$.

Suppose that $\mu[L_{-}]\geq\frac{1}{2}\mu[I]$. If $\rho|L_{-}^{*}|\leq t$
then $L_{-}^{*}$ satisfies the required conditions and we are done, so assume
$\rho|L_{-}^{*}|>t$. Since $|I^{*}|>2|L_{-}^{*}|$, we have

$\mu[L_{-}]\geq\frac{1}{2}\mu[I]=\frac{1}{2}\rho|I^{*}|\chi_{t}(\mu)>\rho|L_{-}^{*}|\chi_{t}(\mu)\,,$

which contradicts the minimality of $I$. A similar argument shows that $R_{+}$
satisfies the required conditions when $\mu[R_{+}]\geq\frac{1}{2}\mu[I]$. So
we may assume $\mu[L_{-}],\mu[R_{+}]<\frac{1}{2}\mu[I]$ in the sequel, which
implies $\mu[L_{+}],\mu[R_{-}]\geq\frac{1}{2}\mu[I]$.

Now if $\rho|L_{+}^{*}|\leq t$, then $L_{+}^{*}$ satisfies the required
conditions and we are done. Suppose $\rho|L_{+}^{*}|>t$ and recall
$|L_{+}^{*}|=|R_{-}^{*}|=|I^{*}|/2$. Then $\rho|I^{*}|=2\rho|L_{+}^{*}|$, so

$\mu[L_{+}]\geq\frac{1}{2}\mu[I]\geq\frac{1}{2}\rho|I^{*}|\chi_{t}(\mu)=\rho|L_{+}^{*}|\chi_{t}(\mu)\,,$

which contradicts the minimality of $I$ and concludes the proof. ∎

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

We bound the first component of the variance,
$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]$.

######  Proposition 4.20.

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 Boolean-valued:

$\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 4.21.

Let
$\mathcal{I}\in\\{\mathcal{I}^{\mathsf{cycle}},\mathcal{I}^{\mathsf{path}}\\}$.
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
5\zeta(\mathcal{I})+c\cdot\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}\mu_{i}\mu_{i+d-1}\mu[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^{2}}\mathbb{E}\left[\bm{T}^{\top}\Phi\bm{T}\right]-\frac{1}{m^{2}}\mathbb{E}\left[\|\bm{T}\|_{1}\right]=\frac{1}{m^{2}}\sum_{i,j\in\mathbb{Z}_{n}}\mathbb{E}\left[\bm{T}_{i}\bm{T}_{j}\right]\Phi_{i,j}-\frac{1}{m^{2}}\mathbb{E}\left[\mathsf{Poi}(m)\right]$
$\displaystyle=\frac{1}{m^{2}}\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)-\frac{1}{m}=\frac{1}{m^{2}}\left(m+m^{2}\mu^{\top}\Phi\mu\right)-\frac{1}{m}$
$\displaystyle=\mu^{\top}\Phi\mu\,,$

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]=\underset{\bm{H}}{\mathrm{Var}}\left[\mu^{\top}\bm{\Phi}\mu\right]\,.$

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

$\displaystyle\mathrm{Var}\left[\mu^{\top}\bm{\Phi}\mu\right]$
$\displaystyle=\mathbb{E}\left[\left(\mu^{\top}\bm{\Phi}\mu\right)^{2}\right]-\left(\mathbb{E}\left[\mu^{\top}\bm{\Phi}\mu\right]\right)^{2}=\mathbb{E}\left[\left(\mu^{\top}\bm{\Phi}\mu\right)^{2}\right]-\left(\mu^{\top}\phi\mu\right)^{2}$
$\displaystyle=\mathbb{E}\left[\left(\sum_{i,j\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\bm{\Phi}_{i,j}\right)^{2}\right]-\left(\sum_{i,j\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\phi_{i,j}\right)^{2}$
$\displaystyle=\mathbb{E}\left[\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\mu_{k}\mu_{\ell}\bm{\Phi}_{i,j}\bm{\Phi}_{k,\ell}\right]-\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\mu_{k}\mu_{\ell}\phi_{i,j}\phi_{k,\ell}$
$\displaystyle=\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\mu_{k}\mu_{\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 4.20 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}}\mu_{i}\mu_{j}\mu_{k}\mu_{\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}}\mu_{i}\mu_{j}\mu_{k}\mu_{\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\zeta+\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\mu_{k}\mu_{\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})\|\mu\|_{1}^{4}+\sum_{i,j,k,\ell\in\mathbb{Z}_{n}}\mu_{i}\mu_{j}\mu_{k}\mu_{\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\mu_{i}\mu_{i+d-1}\sum_{j,k\in
I}\mu_{j}\mu_{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}\mu_{j}\mu_{k}=\mu[I]^{2}$, we obtain

$\mathrm{Var}\left[\mu^{\top}\Phi(\bm{J})\mu\right]\leq
5\zeta(\mathcal{I})+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]\mu_{i}\mu_{i+d-1}\mu[I]^{2}\,.\qed$

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

Let $\delta\in(0,1)$ be a constant, let $n\in\mathbb{N}$ be sufficiently large
and let $\mu$ be a probability distribution over $\mathbb{Z}_{n}$. Suppose
that $\rho\geq\Omega(n^{-\delta})$ and $0<t<1$. Then

$\underset{\bm{H}}{\mathrm{Var}}\left[\underset{\bm{T}}{\mathbb{E}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq
O\left(\frac{\chi_{t}(\mu)^{2}}{\rho}\right)\cdot\|\mu\|_{2}^{2}\,.$

###### Proof.

By Lemma 4.21, 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
5\zeta(\mathcal{I})+c\cdot\sum_{\begin{subarray}{c}I=\langle\\!\langle
i,d\rangle\\!\rangle\in\mathcal{I}\\\ 1\leq d\leq
n\end{subarray}}\mu_{i}\mu_{i+d-1}\mu[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\eta^{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}}\mu_{i}\mu_{i+d-1}\mu[I]^{2}\mathbb{E}\left[\bm{J}(I)\right]\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}\mu_{i}\mu_{i+d-1}\mu[\langle\\!\langle
i,d\rangle\\!\rangle]^{2}\eta^{d-1}$
$\displaystyle\quad\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}\mu_{i}\mu_{i+d-1}\eta^{d-1}\left[\chi_{t}(\mu)\cdot\max\left\\{\rho(d-1),t\right\\}\right]^{2}$
(Relative concentration)
$\displaystyle\quad\leq\sum_{i=0}^{n-1}\sum_{d=1}^{n}\mu_{i}\mu_{i+d-1}\eta^{d-1}\left[\chi_{t}(\mu)^{2}\cdot\left(\rho^{2}d^{2}+1\right)\right]$
(Since $t<1$)
$\displaystyle\quad=\chi_{t}(\mu)^{2}\left(\rho^{2}\sum_{d=1}^{n}d^{2}\eta^{d-1}\sum_{i=0}^{n-1}\mu_{i}\mu_{i+d-1}+\sum_{d=1}^{n}\eta^{d-1}\sum_{i=0}^{n-1}\mu_{i}\mu_{i+d-1}\right)$
$\displaystyle\quad\leq\chi_{t}(\mu)^{2}\|\mu\|_{2}^{2}\left(\rho^{2}\sum_{d=1}^{n}d^{2}\eta^{d-1}+\sum_{d=1}^{n}\eta^{d-1}\right)$
(By Cauchy-Schwarz)
$\displaystyle\quad\leq\chi_{t}(\mu)^{2}\|\mu\|_{2}^{2}\left(\rho^{2}\cdot\frac{1+\eta}{\rho^{3}}+\frac{1}{\rho}\right)$
(Since $\rho=1-\eta$) $\displaystyle\quad\leq
3\cdot\frac{\chi_{t}(\mu)^{2}}{\rho}\|\mu\|_{2}^{2}$
$\displaystyle\text{(Since $\eta<1$)}\,,$

as desired. Now, we show that the term $5\zeta(\mathcal{I})$ satisfies the
claimed bound. First, Proposition 4.10 implies that $\zeta(\mathcal{I})\leq
1/n^{3}$. Note that, by taking intervals $I=\langle\\!\langle
i,1\rangle\\!\rangle$ in Definition 4.18, we have that
$\chi_{t}(\mu)\geq\mu(i)/t$ for every $i$, and hence $\chi_{t}(\mu)\geq 1/nt$.
Along with the inequalities $\|\mu\|_{2}^{2}\geq 1/n$, $\rho\leq 1$ and $t<1$,
we obtain

$\zeta(\mathcal{I})\leq\frac{1}{n^{3}}\leq\frac{1}{n^{3}t^{2}}\leq\frac{\chi_{t}(\mu)^{2}}{n}\leq\frac{\chi_{t}(\mu)^{2}}{\rho}\|\mu\|_{2}^{2}\,.\qed$

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

We now bound the second component of the variance,
$\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]$.
The first step is to relate it to the 2- and 3-norms of the clustered vector
$\mu$. Recall that $\bm{T}_{i}\sim\mathsf{Poi}(m\mu_{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 4.23.

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$

Recall the notation ${\mu}_{\lfloor{\Gamma}\rfloor}$ for the distribution on
the cluster representatives induced by $\mu$ (Definition 2.3).

######  Lemma 4.24.

Let $H$ be a subgraph with induced cells
$\Gamma=(\Gamma_{1},\dotsc,\Gamma_{b})$, and let $\mu$ be a distribution 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]=\frac{2}{m^{2}}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{2}^{2}+\frac{4}{m}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{3}^{3}\,.$

###### Proof.

Using Proposition 4.23, 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^{2}}\sum_{i=1}^{b}\bm{X}_{i}(\bm{X}_{i}-1)\right]=\frac{1}{m^{4}}\sum_{i=1}^{b}\left[4\left(m\mu\left[\Gamma_{i}\right]\right)^{3}+2\left(m\mu\left[\Gamma_{i}\right]\right)^{2}\right]$
$\displaystyle=\frac{4}{m}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{3}^{3}+\frac{2}{m^{2}}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{2}^{2}\,.\qed$

We will need the following auxiliary result.

######  Proposition 4.25 (Cells are almost always small).

Let $K\geq 2$ be a constant, and suppose $n\geq 3$. Then the cells
$\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}{\rho}\qquad\forall
i\in[\bm{b}]$

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

###### Proof.

Let $d\vcentcolon=\left\lceil\frac{2K\log n}{\rho}\right\rceil$, and fix any
interval $I=\langle\\!\langle i,d\rangle\\!\rangle$. The probability that $I$
is joined is

$\mathbb{P}\left[\bm{J}(I)=1\right]=(1-\rho)^{d-1}\leq(1-\rho)^{\frac{2K\log
n}{\rho}-1}\leq(1-\rho)^{\frac{(2K-1)\log n}{\rho}}\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}{\rho}\geq 1$ and
that $K\geq 2\implies 2K-1\geq K+1$. Now, if any cell 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. ∎

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

Let $n\in\mathbb{N}$ be sufficiently large and let $\mu$ be a probability
distribution over $\mathbb{Z}_{n}$. Suppose $m\leq\operatorname{poly}(n)$ and
$0<t<1$. Then

$\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]\leq
O\left(\frac{\log n}{m^{2}\rho}\cdot\left(1+m\chi_{t}(\mu)\log
n\right)\right)\cdot\|\mu\|_{2}^{2}\,.$

###### Proof.

Let $K\geq 2$ be some constant such that $m\leq O(n^{K-1})$. By Proposition
4.25, the cells $\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}{\rho}$ 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 cells
$\Gamma=(\Gamma_{1},\dotsc,\Gamma_{b})$ satisfy
$\left\lvert\Gamma_{i}\right\rvert\leq\frac{2K\log n}{\rho}$ for every
$i\in[b]$. 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 4.24:

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

We start by bounding the first term in the RHS. For each cell $\Gamma_{i}$, we
have

$\left({\mu}_{\lfloor{\Gamma}\rfloor}\right)_{i}^{2}=\left(\sum_{j\in\Gamma_{i}}\mu_{j}\right)^{2}=\sum_{j,k\in\Gamma_{i}}\mu_{j}\mu_{k}\leq\sum_{j,k\in\Gamma_{i}}\frac{\mu_{j}^{2}+\mu_{k}^{2}}{2}=\left\lvert\Gamma_{i}\right\rvert\sum_{j\in\Gamma_{i}}\mu_{j}^{2}\leq
O\left(\frac{\log n}{\rho}\right)\sum_{j\in\Gamma_{i}}\mu_{j}^{2}\,.$

Hence, we obtain

$\frac{1}{m^{2}}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{2}^{2}=\frac{1}{m^{2}}\sum_{i=1}^{b}{\mu}_{\lfloor{\Gamma}\rfloor}(i)^{2}\leq
O\left(\frac{\log n}{m^{2}\rho}\right)\|\mu\|_{2}^{2}\,,$

as desired. Moving on to the second term, first note that
$\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{3}^{3}=\sum_{i}\mu[\Gamma_{i}]^{3}\leq\sum_{i}(\max_{j}\mu[\Gamma_{j}])\mu[\Gamma_{i}]^{2}=\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{\infty}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{2}^{2}$.
We claim that $\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{\infty}\leq
O\left(\chi_{t}(\mu)\log n\right)$. Fix any $i\in[b]$ and consider entry
$\left({\mu}_{\lfloor{\Gamma}\rfloor}\right)_{i}=\mu\left[\Gamma_{i}\right]$.
The anticoncentration of $\mu$ yields

$\mu\left[\Gamma_{i}\right]\leq\chi_{t}(\mu)\cdot\max\left\\{\rho\left(\left\lvert\Gamma_{i}\right\rvert-1\right),t\right\\}\,.$

Combining with the assumption that $\left\lvert\Gamma_{i}\right\rvert\leq
O\left(\frac{\log n}{\rho}\right)$ and recalling that $t<1$, we obtain that
$\mu\left[\Gamma_{i}\right]\leq O\left(\chi_{t}(\mu)\log n\right)$, as
claimed. We have already shown that
$\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{2}^{2}\leq\frac{\|\mu\|_{2}^{2}}{\rho}\cdot
O(\log n)$, and thus

$\frac{1}{m}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{3}^{3}\leq\frac{1}{m}\cdot
O\left(\chi_{t}(\mu)\log n\right)\cdot\frac{\|\mu\|_{2}^{2}}{\rho}\cdot O(\log
n)=O\left(\frac{\log n}{m^{2}\rho}\cdot m\chi_{t}(\mu)\log
n\right)\cdot\|\mu\|_{2}^{2}\,,$

which concludes Case 1.

Case 2. In the rare event that $\bm{H}=H$ is a subgraph that fails the small-
cells condition of Case 1, we will fall back to a looser upper bound for the
conditional variance that holds for every $H$. We once again start with the
result from Lemma 4.24:

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

Using $\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{1}=1$ along with the monotonicity
of $\ell_{p}$ norms gives

$\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]\leq\frac{2}{m^{2}}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{1}^{2}+\frac{4}{m}\|{\mu}_{\lfloor{\Gamma}\rfloor}\|_{1}^{3}\leq\frac{6}{m^{2}}\cdot
m=\frac{1}{m^{2}}\cdot O(n^{K-1})\,.$

Concluding the argument. We now combine both cases to upper bound the expected
variance. Using Proposition 4.25, we have

$\displaystyle\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\right]$
$\displaystyle\leq\left[\begin{array}[]{l}\mathbb{P}\left[\bm{H}\text{
satisfies }\|\bm{\Gamma}\|_{\infty}\leq\frac{2K\log
n}{\rho}\right]\underset{\bm{H}}{\mathbb{E}}\left[\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}\right.\right]\;\;\left|\;\;\bm{H}\text{
satisfies }\|\bm{\Gamma}\|_{\infty}\leq\frac{2K\log n}{\rho}\right.\right]\\\
+\mathbb{P}\left[\bm{H}\text{ does not satisfy
}\|\bm{\Gamma}\|_{\infty}\leq\frac{2K\log
n}{\rho}\right]\max_{H}\left\\{\underset{\bm{T}}{\mathrm{Var}}\left[\bm{Y}\;\;\left|\;\;\bm{H}=H\right.\right]\right\\}\end{array}\right]$
$\displaystyle\leq O\left(\frac{\log
n}{m^{2}\rho}\cdot\left(1+m\chi_{t}(\mu)\log
n\right)\right)\cdot\|\mu\|_{2}^{2}+\frac{1}{n^{K}}\cdot\frac{1}{m^{2}}\cdot
O(n^{K-1})\,.$

Since $\|\mu\|_{2}^{2}\geq\|\nu\|_{2}^{2}=1/n$, the first term dominates the
second, concluding the proof. ∎

We obtain the general form of our concentration bound; the result below gives
Lemma 1.6 with $\chi(\mu)=\chi_{t}(\mu)$ for any $0<t<1$. While we use a
specialized version in the analysis of our tester (Lemma 4.33) that is better
by logarithmic factors, we prove the following for the sake of generality.

######  Lemma 4.27 (Formal version of Lemma 1.6).

Let $\delta\in(0,1)$ be a constant, let $n\in\mathbb{N}$ be sufficiently large
and let $\mu$ be a probability distribution over $\mathbb{Z}_{n}$. Suppose
$\rho\geq\Omega(n^{-\delta})$, $m\leq\operatorname{poly}(n)$ and $0<t<1$. Then
for all $\tau>0$,

$\mathbb{P}\left[\left\lvert\bm{Y}-\mathbb{E}\left[\bm{Y}\right]\right\rvert\geq\tau\right]\leq\frac{\|\mu\|_{2}^{2}}{\rho\tau^{2}}\cdot\max\left\\{\chi_{t}(\mu),\frac{1}{m}\right\\}^{2}\cdot
O(\log^{2}n)\,.$

###### Proof.

By Lemmas 4.22 and 4.26, along with the law of total variance, we obtain

$\displaystyle\mathrm{Var}\left[\bm{Y}\right]$ $\displaystyle\leq
O\left(\frac{\chi_{t}(\mu)^{2}}{\rho}\right)\cdot\|\mu\|_{2}^{2}+O\left(\frac{\log
n}{m^{2}\rho}\cdot\left(1+m\chi_{t}(\mu)\log
n\right)\right)\cdot\|\mu\|_{2}^{2}$
$\displaystyle\leq\frac{\|\mu\|_{2}^{2}}{\rho}\cdot
O\left(\chi_{t}(\mu)^{2}+2\cdot\chi_{t}(\mu)\cdot\frac{1}{m}+\frac{1}{m^{2}}\right)\cdot
O(\log^{2}n)$
$\displaystyle=\frac{\|\mu\|_{2}^{2}}{\rho}\cdot\max\left\\{\chi_{t}(\mu),\frac{1}{m}\right\\}^{2}\cdot
O(\log^{2}n)\,.$

The claim follows by Chebyshev’s inequality. ∎

###  4.4 Testing Uniformity Without Queries

We now give the upper bound for testing uniformity on either the path or the
cycle with zero queries. 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}{\rho^{3/2}}$.
Constants: $\alpha,\beta,L,c>0$ to be defined later.
Requires: $\rho\geq\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}$.

1:procedure UniformityTester-ConfusedCollector($\mu,n,\epsilon,\rho$)

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

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

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

5: If
$Y\geq\frac{1}{n^{2}}\sum_{i,j}\phi_{i,j}+\beta\frac{1}{n}\epsilon^{2}\rho$
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 [GR11] when $\rho=1$, it may
seem surprising that we obtain 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,
DKN15, VV17]) 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 the relative concentration test, which upper bounds
$\|\mu\|_{\infty}$, and indeed specializing our proof to the case $\rho=1$
would yield a sample complexity 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)$ (see Remark 4.36), the
term $\sqrt{n}/\epsilon^{2}$ dominates $1/\epsilon^{4}$.

####  4.4.1 Easy Case: Highly Concentrated Distributions

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

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

To understand this definition (in particular, the choice of $t$), observe that
Algorithm 1 tries to reject highly concentrated distributions by checking
whether any entry $\bm{X}_{i}$ in its clustered sample is large, namely
$\bm{X}_{i}\geq\alpha\log n$ (which is unlikely to occur under the uniform
distribution). When $\mu$ is highly concentrated, Proposition 4.19 ensures an
interval $I$ exists, satisfying $\rho|I^{*}|\leq 1/\log n$ (so $I$ is likely
to be joined in the clustering) and $\mu[I]\geq\frac{C\log n}{2m}$; so, for
sufficiently large $C$, the $\mathsf{Poi}(m\mu[I])$ will be larger than
$\alpha\log n$, causing the algorithm to reject.

Furthermore, when $\mu$ is not highly concentrated, the condition
$\chi_{t}(\mu)<\frac{C\log^{2}n}{m}$ means that the term
$\max\left\\{\chi_{t}(\mu),\frac{1}{m}\right\\}$ in the general concentration
inequality (Lemma 4.27) cannot be improved by more than logarithmic factors.
Therefore this choice of definition is both sensible for the first step of the
tester, and nearly optimal for our analysis of the second step of the tester.

######  Observation 4.29.

Let $t\vcentcolon=\frac{1}{\log n}$. Then by inspecting the definition of
relative concentration and breaking down into the cases where $|I|=1$ or
$|I|\geq 2$, we have $\chi_{t}(\mu)\leq\max\left\\{\frac{2}{\rho},\log
n\right\\}\cdot\|\mu\|_{\infty}$.

######  Remark 4.30.

If $\mu$ is not $C$-highly concentrated, then in particular
$\|\mu\|_{\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 $\mu$ is not highly
concentrated when analyzing the second step of the tester.

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

######  Fact 4.31.

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 uses the hypothesis $m\leq n\rho$, which intuitively
corresponds to the sublinear sample complexity regime in the standard
uniformity testing model. This hypothesis holds in the range of parameters we
consider, but not necessarily in more extreme regimes (see Remark 4.36).

######  Lemma 4.32.

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

  1. 1.

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

  2. 2.

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

###### Proof.

Completeness. Suppose $\mu$ is the uniform distribution over $\mathbb{Z}_{n}$.
From Proposition 4.25, we obtain that every cell has size at most $\frac{4\log
n}{\rho}$ except with probability $o(1)$. Assume that this is the case, and
fix some particular cell $\Gamma_{i}$. The number of elements sampled from
this cell is distributed as
$\bm{X}_{i}\sim\mathsf{Poi}\left(m\mu\left[\Gamma_{i}\right]\right)=\mathsf{Poi}\left(m|\Gamma_{i}|/n\right)$.
Then, using 4.31 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}{\rho}\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\rho$)
$\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 $\mu$ is $4\alpha$-highly concentrated. Using Proposition
4.19 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)\rho\leq\frac{1}{\log n}$, and thus $|I|=d\leq 1+\frac{1}{\rho\log n}$;
and

  2. 2.

$\mu[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\rho\leq\frac{1}{\rho\log
n}\cdot\rho=\frac{1}{\log n}=o(1)\,.$

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

$m\mu\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 4.31, 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$

####  4.4.2 Correctness of the Tester

Combining our separation and concentration results, we can show that $\bm{Y}$
is concentrated on the correct side of the tester’s threshold. First, we
specialize our general concentration result to the case of non-highly-
concentrated distributions.

######  Lemma 4.33.

Let $C>0$ and $\delta\in(0,1)$ be constants, let $n\in\mathbb{N}$ be
sufficiently large and suppose $\mu$ is a probability distribution over
$\mathbb{Z}_{n}$ that is not $C$-highly concentrated with respect to $m$.
Suppose $\rho\geq\Omega(n^{-\delta})$ and $m\leq\operatorname{poly}(n)$. Then
for all $\tau>0$,

$\mathbb{P}\left[\left\lvert\bm{Y}-\mathbb{E}\left[\bm{Y}\right]\right\rvert\geq\tau\right]\leq\frac{\|\mu\|_{2}^{2}}{\rho
m^{2}\tau^{2}}\cdot O\left(\log^{4}n\right)\,.$

###### Proof.

We again combine Lemmas 4.22 and 4.26, which apply since here
$0<t=\frac{1}{\log n}<1$, via the law of total variance, and conclude with
Chebyshev’s inequality (directly applying the general Lemma 4.27 would also
work, but lead to a small loss in logarithmic factors). We have

$\displaystyle\mathrm{Var}\left[\bm{Y}\right]$ $\displaystyle\leq
O\left(\frac{\chi_{t}(\mu)^{2}}{\rho}\right)\cdot\|\mu\|_{2}^{2}+O\left(\frac{\log
n}{m^{2}\rho}\cdot\left(1+m\chi_{t}(\mu)\log
n\right)\right)\cdot\|\mu\|_{2}^{2}$ $\displaystyle\leq
O\left(\frac{\log^{4}n}{\rho
m^{2}}\right)\cdot\|\mu\|_{2}^{2}+O\left(\frac{\log
n}{m^{2}\rho}\cdot\left(1+m\cdot\frac{\log^{2}n}{m}\cdot\log
n\right)\right)\cdot\|\mu\|_{2}^{2}=\frac{\|\mu\|_{2}^{2}}{\rho m^{2}}\cdot
O\left(\log^{4}n\right)\,.\qed$

######  Lemma 4.34.

Let $\alpha,L>0$ be constants. Then there exist constants $\beta>0$, and
$c=c_{\alpha,\beta}>0$ such that the following holds for all sufficiently
large $n$. Let $\epsilon,\rho\in(0,1]$ satisfy
$\rho\geq\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}$. Suppose $\mu$ is a
probability distribution over $\mathbb{Z}_{n}$ that is not $4\alpha$-highly
concentrated with respect to
$m=c\cdot\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n$. Let
$T\vcentcolon=\frac{1}{n^{2}}\sum_{i,j}\phi_{i,j}+\beta\frac{1}{n}\epsilon^{2}\rho$
be the threshold used by the second step of Algorithm 1. Then the test
statistic $\bm{Y}$ satisfies the following:

  1. 1.

(Completeness) If $\mu=\nu$, then $\bm{Y}<T$ with probability at least
$99/100$;

  2. 2.

(Soundness) If $\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)>\epsilon$, then
$\bm{Y}>T$ with probability at least $99/100$.

###### Proof.

Completeness. Suppose $\mu=\nu$. By Proposition 4.5, $\bm{Y}$ satisfies
$\mathbb{E}\left[\bm{Y}\right]=\frac{1}{n^{2}}\sum_{i,j}\phi_{i,j}$. Hence for
any fixed $\beta$ (to be chosen below), it suffices to show that
$\bm{Y}<\mathbb{E}\left[\bm{Y}\right]+\beta\frac{1}{n}\epsilon^{2}\rho$ with
good probability. By Lemma 4.33 and using the fact that $\|\nu\|_{2}^{2}=1/n$,

$\mathbb{P}\left[\bm{Y}\geq\mathbb{E}\left[\bm{Y}\right]+\beta\frac{1}{n}\epsilon^{2}\rho\right]\leq\mathbb{P}\left[\left\lvert\bm{Y}-\mathbb{E}\left[\bm{Y}\right]\right\rvert\geq\beta\frac{1}{n}\epsilon^{2}\rho\right]\leq\frac{\|\mu\|_{2}^{2}}{\rho
m^{2}\left(\beta\frac{1}{n}\epsilon^{2}\rho\right)^{2}}\cdot
O(\log^{4}n)=\frac{O(n\log^{4}n)}{\beta^{2}m^{2}\epsilon^{4}\rho^{3}}\,,$

and we have

$\frac{O(n\log^{4}n)}{\beta^{2}m^{2}\epsilon^{4}\rho^{3}}\leq 1/100\iff
m\geq\frac{1}{\beta}\cdot
O\left(\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n\right)\,,$ (1)

as desired. Thus, there exists constant $c^{(1)}=c^{(1)}_{\alpha,\beta}$ such
that if $m\geq c^{(1)}\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n$ then,
for all sufficiently large $n$, $\bm{Y}<T$ with probability at least $99/100$.

Soundness. We proceed similarly. We first note that the conditions of Lemma
4.17 are met: the condition $\|\mu\|_{\infty}\leq\frac{C\log n}{m}$ holds with
$C=4\alpha$ by Remark 4.30, and the lower bound on $\rho$ holds for the
following reason. First, since $\rho\leq 1$ always, its lower bound implies
that $\epsilon\geq\Omega(n^{-1/4})$:

$\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}\leq\rho\leq
1\implies\epsilon\geq\frac{L^{5/4}\log n}{n^{1/4}}\,.$

Then, we conclude that
$\rho=\Omega\left(\frac{\log^{2/3}n}{n^{1/3}\epsilon^{4/3}}\right)$, since
$\rho\geq\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}$ and

$\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)\,.$

Thus, writing $\mu=\nu+z$, by Lemmas 4.17 and 4.5 we have

$\mathbb{E}\left[\bm{Y}\right]>\mathbb{E}\left[\bm{Y}^{(\nu)}\right]+\frac{\rho}{8}\|z\|_{2}^{2}=\frac{1}{n^{2}}\sum_{i,j}\phi_{i,j}+\frac{\rho}{8}\|z\|_{2}^{2}\,.$

Therefore it suffices to show that, for appropriately chosen $\beta$, we have

$\bm{Y}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny?}}}}{{>}}\mathbb{E}\left[\bm{Y}\right]-\frac{\rho}{8}\|z\|_{2}^{2}+\beta\frac{1}{n}\epsilon^{2}\rho\,.$

Recall that, when $\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)>\epsilon$, we have
$\|z\|_{1}>2\epsilon$, which implies $\|z\|_{2}^{2}>4\epsilon^{2}/n$ and hence
$\frac{\rho}{8}\|z\|_{2}^{2}>\frac{1}{2n}\epsilon^{2}\rho$, so that

$\mathbb{E}\left[\bm{Y}\right]-\frac{\rho}{8}\|z\|_{2}^{2}+\beta\frac{1}{n}\epsilon^{2}\rho<\mathbb{E}\left[\bm{Y}\right]-\frac{\rho}{8}\|z\|_{2}^{2}+2\beta\frac{\rho}{8}\|z\|_{2}^{2}=\mathbb{E}\left[\bm{Y}\right]-(1-2\beta)\frac{\rho}{8}\|z\|_{2}^{2}\,.$

Thus, for $\beta\leq 1/3$, we have $1-2\beta\geq\beta$ and it suffices to show
that the following holds with probability at least $99/100$:

$\bm{Y}\stackrel{{\scriptstyle\mathclap{\mbox{\tiny?}}}}{{>}}\mathbb{E}\left[\bm{Y}\right]-\beta\frac{\rho}{8}\|z\|_{2}^{2}\,.$

We apply Lemma 4.33 again, along with
$\|\mu\|_{2}^{2}=\|\nu\|_{2}^{2}+\|z\|_{2}^{2}=\frac{1}{n}+\|z\|_{2}^{2}$ and
$\|z\|_{2}^{2}\geq\frac{4\epsilon^{2}}{n}$.

$\displaystyle\mathbb{P}\left[\bm{Y}\leq\mathbb{E}\left[\bm{Y}\right]-\beta\frac{\rho}{8}\|z\|_{2}^{2}\right]$
$\displaystyle\leq\mathbb{P}\left[\left\lvert\bm{Y}-\mathbb{E}\left[\bm{Y}\right]\right\rvert\geq\beta\frac{\rho}{8}\|z\|_{2}^{2}\right]\leq\frac{\|\mu\|_{2}^{2}}{\rho
m^{2}\left(\beta\frac{\rho}{8}\|z\|_{2}^{2}\right)^{2}}\cdot O(\log^{4}n)$
$\displaystyle=\frac{(\frac{1}{n}+\|z\|_{2}^{2})O(\log^{4}n)}{\beta^{2}m^{2}\rho^{3}\|z\|_{2}^{4}}\leq\frac{\frac{1}{n}O(\log^{4}n)}{\beta^{2}m^{2}\rho^{3}(\epsilon^{2}/n)^{2}}+\frac{O(\log^{4}n)}{\beta^{2}m^{2}\rho^{3}(\epsilon^{2}/n)}=\frac{O(n\log^{4}n)}{\beta^{2}m^{2}\rho^{3}\epsilon^{4}}\,.$

This failure probability is asymptotically the same as that obtained in the
completeness case. Thus there exists a constant
$c^{(2)}=c^{(2)}_{\alpha,\beta}>0$ such that, for $m\geq
c^{(2)}\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n$ and all sufficiently
large $n$, $\bm{Y}>T$ with probability at least $99/100$. Setting
$c=\max\left\\{c^{(1)}_{\alpha,\beta},c^{(2)}_{\alpha,\beta}\right\\}$
concludes the proof. ∎

Finally, we establish correctness by combining our results for the two steps
of the tester:

######  Theorem 4.35 (Formal version of Theorem 1.4).

There exist constants $\alpha>0$, $\beta>0$, $c=c_{\alpha,\beta}>0$, and
$L=L_{c}>0$ such that the following holds for all sufficiently large $n$.
Suppose $\epsilon,\rho\in(0,1]$ satisfy
$\rho\geq\frac{L\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}$ and let $G$ be either the
cycle or the path on $n$ vertices. Then Algorithm 1 (instantiated with
constants $\alpha,\beta,L\text{ and }c$) is an $(\epsilon,\rho)$-tester for
uniformity with sample complexity
$\Theta\left(\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n\right)$ and
query complexity 0.

###### Proof.

We start by instantiating $\alpha>0$ large enough as per Lemma 4.32. That
lemma also requires that $m\leq n\rho$, which we now verify. Fix any constant
$c>0$ and suppose $m=c\cdot\frac{\sqrt{n}}{\epsilon^{2}\rho^{3/2}}\log^{2}n$.
Then

$m\leq n\rho\iff
c\cdot\frac{\sqrt{n}}{\epsilon^{2}}\cdot\frac{\log^{2}n}{\rho^{3/2}}\leq
n\rho\iff\rho^{5/2}\geq
c\cdot\frac{\log^{2}n}{n^{1/2}\epsilon^{2}}\iff\rho\geq\frac{c^{2/5}\log^{4/5}n}{n^{1/5}\epsilon^{4/5}}\,.$

Therefore, for any choice of $c$, setting $L=L_{c}\geq c^{2/5}$ ensures that
$m\leq n\rho$.

Thus, instantiate $\beta,c>0$ as provided by Lemma 4.34, and the corresponding
$L_{c}$ as above. Now, we can use Lemmas 4.32 and 4.34 to establish overall
correctness of the tester. (Note that the sample complexity claim follows from
the specification of the algorithm.)

Completeness. By Lemma 4.32, the first step of the tester rejects only with
probability at most $1/100$. Likewise, by Lemma 4.34, the second step of the
tester rejects only with probability at most $1/100.$ Hence the total
rejection probability is at most $2/100<1/10$.

Soundness. There are two cases depending on the concentration of $\mu$. First,
suppose $\mu$ is $4\alpha$-highly concentrated. Then the first step of the
tester rejects with probability at least $99/100$ by Lemma 4.32. On the other
hand, if $\mu$ is not $4\alpha$-highly concentrated, then the second step of
the tester rejects with probability at least $99/100$ by Lemma 4.34. Either
way, the tester rejects with probability at least $99/100>9/10$. ∎

######  Remark 4.36.

Our tester and analysis cover the range of resolution parameter
$\rho\geq\widetilde{\Theta}\left(n^{-1/5}\epsilon^{-4/5}\right)$, which, as
shown in the proof of Lemma 4.34, also implies an
$\epsilon\geq\widetilde{\Theta}\left(n^{-1/4}\right)$ bound. As shown above,
together with our sample complexity these bounds ensure that $m\leq n\rho$,
which was required by our Lemma 4.32. An interesting question is whether there
exists a zero-query tester for more extreme parameter ranges, in particular
those requiring sample complexity $m\gg n$. For the situation where queries
are allowed, see the next subsection.

###  4.5 Testing Uniformity With Queries

We show that the uniformity testing result from Theorem 4.35 can be improved
if queries are allowed. The tester will use the instance-optimal identity
tester of [VV17] to test identity on the _singletons_ of the random
clustering.

######  Definition 4.37.

Let $\mathcal{X}$ be a set and let $\Gamma$ be a clustering of $\mathcal{X}$.
We say that $x\in\mathcal{X}$ is a _$\Gamma$ -singleton_ if
$\Gamma_{\gamma(x)}=\\{x\\}$.

######  Theorem 4.38.

There exists a constant $L>0$ such that the following holds for all
sufficiently large $n\in\mathbb{N}$. Let $G$ be the path or cycle on
$\mathbb{Z}_{n}$. Let $\epsilon\in(0,1)$ and let
$\rho\in\left[L(n\epsilon)^{-1/4},1\right]$. Then there is an
$(\epsilon,\rho)$-tester for uniformity on $G$ using
$O\left(\frac{\sqrt{n}}{\rho\epsilon^{2}}\right)$ clustered samples and
$O(\rho n\log n)$ label queries.

###### Proof.

Let $\nu$ be the uniform distribution over $\mathbb{Z}_{n}$. Let
$c_{1},c_{2}>0$ be universal constants to be specified later. The algorithm is
the following:

  1. 1.

Using binary search, attempt to learn every cell of the clustering using
$O(\log n)$ label queries per cell. Stop and reject if more than
$c_{1}\cdot\rho n$ cells are discovered, so that $O(\rho n\log n)$ queries are
used at most.

  2. 2.

Let $S\subseteq\mathbb{Z}_{n}$ be the set of $\Gamma$-singletons of
$\mathbb{Z}_{n}$, and let $\overline{S}\vcentcolon=\mathbb{Z}_{n}\setminus S$.
If $|S|>3\rho^{2}n$, halt and reject. Let $\Gamma^{\prime}$ be the clustering
$\\{\overline{S}\\}\cup\\{\\{x\\}\;|\;x\in S\\}$, i.e. $\Gamma^{\prime}$ has
one cluster for each $\Gamma$-singleton plus one cluster for any remaining
elements. Run the instance-optimal identity tester of [VV17] on input
distribution ${\mu}_{\lfloor{\Gamma^{\prime}}\rfloor}$ against target
distribution ${\nu}_{\lfloor{\Gamma^{\prime}}\rfloor}$ with proximity
parameter $c_{2}\rho^{2}\epsilon$ and success probability $99/100$, and accept
or reject according to the output of the tester.

First step. We first claim that the first step rejects only with probability
at most $1/100$. Note that the number of clusters satisfies $|\bm{\Gamma}|\leq
1+\sum_{e\in G}\mathds{1}\left[e\not\in\bm{H}\right]$, and this sum ranges
over edges $e=(x,x+1)$ for $0\leq x\leq n-1$ when $G$ is the cycle, and $0\leq
x\leq n-2$ when $G$ is the path. Since each edge of $G$ appears in $\bm{H}$
with probability $1-\rho$, the expected number of clusters is
$\mathbb{E}\left[|\bm{\Gamma}|\right]\leq 1+\rho n\leq 2\rho n$, the last
inequality since $\rho n\geq Ln^{3/4}\epsilon^{-1/4}\geq 1$. Choosing
$c_{1}=200$, Markov’s inequality yields that $|\bm{\Gamma}|\geq c_{1}\cdot\rho
n=200\rho n$ only with probability at most $1/100$.

Number of singletons. Let us also upper bound the number of singletons. Let
$A_{1}\vcentcolon=\\{2k:k\in\mathbb{Z}_{\geq 0}\\}\cap\\{1,\dotsc,n-2\\}$, and
let $A_{2}\vcentcolon=\\{2k+1:k\in\mathbb{Z}_{\geq
0}\\}\cap\\{1,\dotsc,n-2\\}$. Note that for each $i$, the vertices of $G$
indexed by elements of $A_{i}$ form an independent set, so the random
variables $\\{\mathds{1}\left[x\in\bm{S}\right]\;|\;x\in A_{i}\\}$ are
mutually independent. Moreover, for each $x\in A_{i}$ we have that $(x-1,x)$
and $(x,x+1)$ are both edges of $G$, so
$\mathbb{P}\left[x\in\bm{S}\right]=\mathbb{P}\left[(x-1,x)\not\in\bm{H}\text{
and }(x,x+1)\not\in\bm{H}\right]=\rho^{2}$. For each $i\in\\{1,2\\}$, define
$\bm{X}_{i}\vcentcolon=|\bm{S}\cap A_{i}|=\sum_{x\in
A_{i}}\mathds{1}\left[x\in\bm{S}\right]$. Let $a_{i}\vcentcolon=|A_{i}|$, and
note that $n/3\leq a_{i}\leq n/2$ for all sufficiently large $n$. Then
$\mathbb{E}\left[\bm{X}_{i}\right]=\rho^{2}a_{i}$ and a Chernoff bound yields,
for any constant $0<\delta<1$,

$\mathbb{P}\left[\bm{X}_{i}\geq(1+\delta)\rho^{2}a_{i}\right]\leq
e^{-\frac{\delta^{2}\rho^{2}a_{i}}{3}}\leq
e^{-\frac{\delta^{2}\rho^{2}n}{9}}\leq 1/100\,,$

the third inequality since $\rho^{2}n\geq
L^{2}n^{1/2}\epsilon^{-1/2}=\omega_{n}(1)$. Then, observing that
$|\bm{S}|\leq\bm{X}_{1}+\bm{X}_{2}+2$ since at most two elements of $\bm{S}$
do not appear in $A_{1}\cup A_{2}$, the Chernoff and union bounds yield

$\mathbb{P}\left[|\bm{S}|\geq
3\rho^{2}n\right]\leq\mathbb{P}\left[|\bm{S}|-2\geq
2\rho^{2}n\right]\leq\mathbb{P}\left[\bm{X}_{1}\geq\rho^{2}n\right]+\mathbb{P}\left[\bm{X}_{2}\geq\rho^{2}n\right]\leq
2/100\,,$

the first inequality since $\rho^{2}n\geq 2$. Thus $|\bm{S}|\leq 3\rho^{2}n$
except with probability at most $2/100$.

Second step (correctness). To show correctness of the second step, we need to
show that the identity tester will accept when $\mu=\nu$ and reject when
$\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)>\epsilon$, both with probability at
least (say) $98/100$. When $\mu=\nu$, we have
${\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}={\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}$
for any value of $\bm{\Gamma}$, so the identity tester will indeed accept.

Now, suppose $\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)>\epsilon$. We need to show
that
$\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor},{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor})\geq
c_{2}\rho^{2}\epsilon$ with good probability. We again break the analysis into
even- and odd-indexed elements to make use of independence. For each
$x\in\mathbb{Z}_{n}$, let
$b_{x}\vcentcolon=\left(\frac{1}{n}-\mu(x)\right)^{+}$. For each
$i\in\\{1,2\\}$, let

$w_{i}\vcentcolon=\sum_{x\in A_{i}}\left(\nu(x)-\mu(x)\right)^{+}=\sum_{x\in
A_{i}}b_{x}\,.$

Let $\epsilon_{0}\vcentcolon=\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)$. Recalling
that $\mu$ and $\nu$ have total mass $1$ each, we have

$\epsilon_{0}=\mathsf{dist}_{\mathsf{TV}}(\mu,\nu)=\sum_{x\in\mathbb{Z}_{n}}b_{x}\leq\left(\sum_{x\in
A_{1}}b_{x}\right)+\left(\sum_{x\in A_{2}}b_{x}\right)+b_{0}+b_{n-1}\leq
w_{1}+w_{2}+\frac{2}{n}\,.$

Since $\epsilon_{0}\geq\epsilon\geq L^{4}\rho^{-4}n^{-1}\geq 4/n$, we conclude
that either $w_{1}\geq\epsilon_{0}/4$ or $w_{2}\geq\epsilon_{0}/4$. Suppose
without loss of generality that $w_{1}\geq\epsilon_{0}/4$.

Define random variable
$\bm{y}_{x}\vcentcolon=\mathds{1}\left[x\in\bm{S}\right]\cdot b_{x}$ for each
$x\in\mathbb{Z}_{n}$. Let $\bm{Y}\vcentcolon=\sum_{x\in A_{1}}\bm{y}_{x}$.
Then

$\displaystyle\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor},{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor})$
$\displaystyle=\frac{1}{2}\sum_{z\in\bm{\Gamma}^{\prime}}\left\lvert{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}(z)-{\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}(z)\right\rvert\geq\frac{1}{2}\sum_{z\in\bm{\Gamma}^{\prime}:z\neq\overline{\bm{S}}}\left({\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}(z)-{\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}(z)\right)^{+}$
$\displaystyle=\frac{1}{2}\sum_{x\in\bm{S}}\left(\frac{1}{n}-\mu(x)\right)^{+}\geq\frac{1}{2}\sum_{x\in
A_{1}}\mathds{1}\left[x\in\bm{S}\right]\cdot b_{x}=\frac{1}{2}\bm{Y}\,.$

Thus our task is to show that $\bm{Y}\geq 2c_{2}\rho^{2}\epsilon$ with good
probability. We have

$\mathbb{E}\left[\bm{Y}\right]=\sum_{x\in
A_{1}}\mathbb{P}\left[x\in\bm{S}\right]\cdot
b_{x}=\rho^{2}w_{1}\geq\rho^{2}\epsilon_{0}/4\,.$

The random variables $\bm{y}_{x}$ for $x\in A_{1}$ are mutually independent
and bounded in $[0,b_{x}]$, so Hoeffding’s inequality gives

$\mathbb{P}\left[\bm{Y}\leq\rho^{2}\epsilon_{0}/8\right]\leq\mathbb{P}\left[\bm{Y}\leq\mathbb{E}\left[\bm{Y}\right]-\rho^{2}\epsilon_{0}/8\right]\leq
e^{-\frac{\rho^{4}\epsilon_{0}^{2}/32}{\sum_{x\in A_{1}}b_{x}^{2}}}\,.$

Since $\sum_{x\in A_{1}}b_{x}=w_{1}$ and each $b_{x}$ lies within $[0,1/n]$,
it holds that $\sum_{x\in
A_{1}}b_{x}^{2}\leq\frac{1}{n^{2}}\cdot\frac{w_{1}}{1/n}=w_{1}/n$ (which would
be attained if there were $n\cdot w_{1}$ values $x$ with $b_{x}=1/n$). Also
noticing that $w_{1}\leq\epsilon_{0}$ and recalling that
$\epsilon_{0}\geq\epsilon$, we obtain

$\mathbb{P}\left[\bm{Y}\leq\rho^{2}\epsilon_{0}/8\right]\leq
e^{-\frac{\rho^{4}\epsilon_{0}^{2}/32}{w_{1}/n}}\leq
e^{-\rho^{4}\epsilon_{0}n/32}\leq e^{-L^{4}(n\epsilon)^{-1}\cdot\epsilon
n/32}=e^{-L^{4}/32}\leq 1/100$

for sufficiently large $L$. Thus
$\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor},{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor})\geq\rho^{2}\epsilon/16$
except with probability at most $1/100$. Hence the second step, with constant
$c_{2}=1/16$, rejects with probability at least $98/100$.

Second step (sample complexity). Finally, we show that the second step
satisfies the claimed sample complexity. The instance-optimal identity tester
of [VV17] requires at most
$O\left(\max\left\\{\frac{1}{\delta},\frac{\|p^{-\max}\|_{2/3}}{\delta^{2}}\right\\}\right)$
samples, where $p$ is the known target distribution, $p^{-\max}$ is the vector
obtained by removing a largest entry from $p$, and $\delta$ is the distance
parameter. Here we have $p={\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}$ and
$\delta=c_{2}\rho^{2}\epsilon$. Since removing a non-largest entry as opposed
to a largest entry from ${\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}$ can
only overestimate the sample complexity, we may upper bound
$\|{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}^{-\max}\|_{2/3}$ by removing
the entry corresponding to $\overline{\bm{S}}$, so that only the singletons
remain:

$\|{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}^{-\max}\|_{2/3}\leq\left(|\bm{S}|\cdot(1/n)^{2/3}\right)^{3/2}\,.$

We have shown that $\bm{S}\leq 3\rho^{2}n$ except with probability at most
$2/100$, in which case the algorithm rejects, so all we need to show is that
the sample complexity is as claimed when $\bm{S}\leq 3\rho^{2}n$. In this
case,

$\|{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}^{-\max}\|_{2/3}\leq\left(3\rho^{2}\cdot
n^{1/3}\right)^{3/2}=O\left(\rho^{3}\sqrt{n}\right)$

and thus

$\frac{\|{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}^{-\max}\|_{2/3}}{\delta^{2}}\leq
O\left(\frac{\sqrt{n}}{\rho\epsilon^{2}}\right)\,.$

This term dominates the expression
$\max\left\\{\frac{1}{\delta},\frac{\|{\nu}_{\lfloor{\bm{\Gamma}^{\prime}}\rfloor}^{-\max}\|_{2/3}}{\delta^{2}}\right\\}$
as long as

$\frac{1}{\rho^{2}\epsilon}\leq\frac{\sqrt{n}}{\rho\epsilon^{2}}\iff\rho\geq\frac{\epsilon}{n^{1/2}}\impliedby\frac{L}{n^{1/4}\epsilon^{1/4}}\geq\frac{\epsilon}{n^{1/2}}\iff
Ln^{1/4}\geq\epsilon^{5/4}\,,$

which holds since the RHS is at most $1$, concluding the proof. ∎

Acknowledgments

We thank Eric Blais for helpful discussions and comments on the presentation
of this article, and Maryam Aliakbarpour for references on testing with
imperfect information. We thank the anonymous reviewers for their comments and
references to related work.

## References

  * [ACF+21] Jayadev Acharya, Clément L Canonne, Cody Freitag, Ziteng Sun, and Himanshu Tyagi.  Inference under information constraints iii: Local privacy constraints.  IEEE Journal on Selected Areas in Information Theory, 2(1):253–267, 2021.
  * [ACFT19] Jayadev Acharya, Clément Canonne, Cody Freitag, and Himanshu Tyagi.  Test without trust: Optimal locally private distribution testing.  In Proceedings, International Conference on Artificial Intelligence and Statistics (AISTATS), pages 2067–2076. PMLR, 2019.
  * [ACH+20] Jayadev Acharya, Clément L Canonne, Yanjun Han, Ziteng Sun, and Himanshu Tyagi.  Domain compression and its application to randomness-optimal distributed goodness-of-fit.  In Proceedings, Conference on Learning Theory (COLT), pages 3–40. PMLR, 2020.
  * [ACT19] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Inference under information constraints: Lower bounds from chi-square contraction.  In Proceedings, Conference on Learning Theory (COLT), pages 3–17. PMLR, 2019.
  * [ACT20] Jayadev Acharya, Clément L Canonne, and Himanshu Tyagi.  Inference under information constraints ii: Communication constraints and shared randomness.  IEEE Transactions on Information Theory, 66(12):7856–7877, 2020\.
  * [AGP+19] Maryam Aliakbarpour, Themis Gouleakis, John Peebles, Ronitt Rubinfeld, and Anak Yodpinyanee.  Towards testing monotonicity of distributions over general posets.  In Proceedings, Conference on Learning Theory (COLT), pages 34–82. PMLR, 2019.
  * [AKR19] Maryam Aliakbarpour, Ravi Kumar, and Ronitt Rubinfeld.  Testing mixtures of discrete distributions.  In Proceedings, Conference on Learning Theory (COLT), pages 83–114. PMLR, 2019.
  * [AS20] Maryam Aliakbarpour and Sandeep Silwal.  Testing properties of multiple distributions with few samples.  In Proceedings, Innovations in Theoretical Computer Science (ITCS), 2020.
  * [BCG19] Eric Blais, Clément L Canonne, and Tom Gur.  Distribution testing lower bounds via reductions from communication complexity.  ACM Transactions on Computation Theory, 11(2):1–37, 2019.
  * [BKR04] Tugkan Batu, Ravi Kumar, and Ronitt Rubinfeld.  Sublinear algorithms for testing monotone and unimodal distributions.  In Proceedings of the thirty-sixth annual ACM symposium on Theory of computing, pages 381–390, 2004.
  * [Can16] Clément L Canonne.  Are few bins enough: Testing histogram distributions.  In Proceedings, ACM Symposium on Principles of Database Systems (PODS), pages 455–463, 2016.
  * [Can17] Clément Canonne.  A short note on poisson tail bounds, 2017.  http://www.cs.columbia.edu/~ccanonne/files/misc/2017-poissonconcentration.pdf.
  * [Can20] Clément L Canonne.  A survey on distribution testing: Your data is big. but is it blue?  Theory of Computing, pages 1–100, 2020.
  * [Can22] Clément Canonne.  Topics and techniques in distribution testing: A biased but representative sample.  Foundations and Trends in Communications and Information Theory, 19(6):1032–1198, 2022.
  * [CDGR18] Clément L Canonne, Ilias Diakonikolas, Themis Gouleakis, and Ronitt Rubinfeld.  Testing shape restrictions of discrete distributions.  Theory of Computing Systems, 62(1):4–62, 2018.
  * [CDKL22] Clément L Canonne, Ilias Diakonikolas, Daniel Kane, and Sihan Liu.  Nearly-tight bounds for testing histogram distributions.  Proceedings, Advances in Neural Information Processing Systems (NeurIPS), 35:31599–31611, 2022.
  * [CDVV14] Siu-On Chan, Ilias Diakonikolas, Paul Valiant, and Gregory Valiant.  Optimal algorithms for testing closeness of discrete distributions.  In Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms, pages 1193–1203. SIAM, 2014.
  * [CFG+22] Sourav Chakraborty, Eldar Fischer, Arijit Ghosh, Gopinath Mishra, and Sayantan Sen.  Testing of index-invariant properties in the huge object model, 2022.  arXiv:2207.12514.
  * [CW20] Clément L Canonne and Karl Wimmer.  Testing data binnings.  In Proceedings of APPROX/RANDOM. Schloss Dagstuhl-Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2020.
  * [CW21] Clément L Canonne and Karl Wimmer.  Identity testing under label mismatch.  In Proceedings, International Symposium on Algorithms and Computation (ISAAC). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2021\.
  * [DGPP19] Ilias Diakonikolas, Themis Gouleakis, John Peebles, and Eric Price.  Collision-based testers are optimal for uniformity and closeness.  Chicago Journal of Theoretical Computer Science, 1:1–21, 2019.
  * [DGTZ18] Constantinos Daskalakis, Themis Gouleakis, Chistos Tzamos, and Manolis Zampetakis.  Efficient statistics, in high dimensions, from truncated samples.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 639–649. IEEE, 2018.
  * [DK16] Ilias Diakonikolas and Daniel M Kane.  A new approach for testing properties of discrete distributions.  In Proceedings, IEEE Symposium on Foundations of Computer Science (FOCS), pages 685–694. IEEE, 2016.
  * [DKN15] Ilias Diakonikolas, Daniel M Kane, and Vladimir Nikishkin.  Testing identity of structured distributions.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 1841–1854. SIAM, 2015.
  * [DNNR11] Khanh Do Ba, Huy L Nguyen, Huy N Nguyen, and Ronitt Rubinfeld.  Sublinear time algorithms for earth mover’s distance.  Theory of Computing Systems, 48:428–442, 2011.
  * [DNS23] Anindya De, Shivam Nadimpalli, and Rocco A Servedio.  Testing convex truncation.  In Proceedings, ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 4050–4082. SIAM, 2023.
  * [FH23] Renato Ferreira Pinto Jr. and Nathaniel Harms.  Distribution testing under the parity trace, 2023.  arXiv:2304.01374.
  * [FKKT21] Dimitris Fotakis, Alkis Kalavasis, Vasilis Kontonis, and Christos Tzamos.  Efficient algorithms for learning from coarse labels.  In Proceedings, Conference on Learning Theory (COLT), pages 2060–2079. PMLR, 2021.
  * [Gol20] Oded Goldreich.  The uniform distribution is complete with respect to testing identity to a fixed distribution.  In Computational Complexity and Property Testing: On the Interplay Between Randomness and Computation. Springer, 2020.  ECCC TR16-015.
  * [GR11] Oded Goldreich and Dana Ron.  On testing expansion in bounded-degree graphs.  In Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation, pages 68–75. Springer, 2011.
  * [GR18] Marco Gaboardi and Ryan Rogers.  Local private hypothesis testing: Chi-square tests.  In Proceedings, International Conference on Machine Learning (ICML), pages 1626–1635. PMLR, 2018.
  * [GR22] Oded Goldreich and Dana Ron.  Testing distributions of huge objects.  In Proceedings, Innovations in Theoretical Computer Science (ITCS). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [Gra06] Robert M Gray.  Toeplitz and circulant matrices: A review.  Foundations and Trends in Communications and Information Theory, 2(3):155–239, 2006.
  * [HY22] Nathaniel Harms and Yuichi Yoshida.  Downsampling for testing and learning in product distributions.  In Proceedings, International Colloquium on Automata, Languages and Programming (ICALP). Schloss Dagstuhl-Leibniz-Zentrum für Informatik, 2022.
  * [ILR12] Piotr Indyk, Reut Levi, and Ronitt Rubinfeld.  Approximating and testing k-histogram distributions in sub-linear time.  In Proceedings, ACM Symposium on Principles of Database Systems (PODS), pages 15–22, 2012.
  * [IT03] Piotr Indyk and Nitin Thaper.  Fast image retrieval via embeddings.  In International Workshop on Statistical and Computational Theories of Vision (ICCV), 2003.
  * [LRR13] Reut Levi, Dana Ron, and Ronitt Rubinfeld.  Testing properties of collections of distributions.  Theory of Computing, 9(1):295–347, 2013.
  * [LRR14] Reut Levi, Dana Ron, and Ronitt Rubinfeld.  Testing similar means.  SIAM Journal on Discrete Mathematics, 28(4):1699–1724, 2014.
  * [LSV20] Yin Tat Lee, Aaron Sidford, and Santosh S Vempala.  Efficient convex optimization with oracles.  In Building Bridges II: Mathematics of László Lovász, pages 317–335. Springer, 2020.
  * [Pan08] Liam Paninski.  A coincidence-based test for uniformity given very sparsely sampled discrete data.  IEEE Transactions on Information Theory, 54(10):4750–4755, 2008\.
  * [Rio37] John Riordan.  Moment recurrence relations for binomial, poisson and hypergeometric frequency distributions.  The Annals of Mathematical Statistics, 8(2):103–111, 1937.
  * [RV23] Ronitt Rubinfeld and Arsen Vasilyan.  Testing distributional assumptions of learning algorithms.  In Proceedings, ACM Symposium on Theory of Computing (STOC). ACM, 2023.
  * [She18] Or Sheffet.  Locally private hypothesis testing.  In Proceedings, International Conference on Machine Learning (ICML), pages 4605–4614. PMLR, 2018.
  * [Sra] Suvrit Sra.  Diagonalizing a certain real and symmetric toeplitz matrix.  MathOverflow.  https://mathoverflow.net/q/68471 (version: 2011-07-05).
  * [VV17] Gregory Valiant and Paul Valiant.  An automatic inequality prover and instance optimal identity testing.  SIAM Journal on Computing, 46(1):429–455, 2017.

##  Appendix A EMD Inequality and Testing on the Hypergrid

In this appendix, we prove the inequality we require between the EMD and total
variation distance of distributions under a hierarchical clustering, and apply
this result to obtain identity and equivalence testers for the hypergrid under
EMD. These results are relatively straightforward adaptations of [IT03,
DNNR11].

###  A.1 EMD-Total Variation Inequality under Hierarchical Clusterings

######  Definition A.1.

Let $(\mathcal{X},\mathsf{dist})$ be a metric space and let
$\Gamma^{(1)},\dotsc,\Gamma^{(t)}$ be clusterings of $\mathcal{X}$. We say
$(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$ is a _hierarchical clustering_ of
$\mathcal{X}$ if $\Gamma^{(i+1)}$ is a refinement of $\Gamma^{(i)}$ for each
$i\in[t-1]$. We say that $(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$ has _diameter
bounds_ $\delta_{1},\dotsc,\delta_{t}$ if
$\mathsf{diam}_{\mathsf{dist}}\left(\Gamma^{(i)}_{j}\right)\leq\delta_{i}$ for
each $i\in[t]$ and $\Gamma^{(i)}_{j}\in\Gamma^{(i)}$. For convenience, we also
define $\delta_{0}\vcentcolon=\mathsf{diam}_{\mathsf{dist}}(\mathcal{X})$.

The following lemma relates the EMD to the TV distance of clustered
distributions, as shown by [IT03] and applied by [DNNR11] to the problem of
EMD testing. These works focused on the case of a fixed explicit clustering or
max-diameter error bounds, but the same proof (which we sketch below for
completeness) applies to the formulation we require.

######  Lemma A.2.

Let $(\mathcal{X},\mathsf{dist})$ be a finite metric space and let
$(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$ be a hierarchical clustering of
$\mathcal{X}$ with diameter bounds $\delta_{1},\dotsc,\delta_{t}$. Equip each
$\Gamma^{(i)}$ with its cluster assignment function function $\gamma^{(i)}$.
Then for every pair of probability distributions $\mu,\nu$ over $\mathcal{X}$,

$\mathsf{EMD}_{\mathsf{dist}}(\mu,\nu)\leq\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor})+\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(\bm{x})}\right)\right]\,.$

###### Proof sketch.

For any measure $m$ on $\mathcal{X}\times\mathcal{X}$ and $z\in\mathcal{X}$,
define $m(z,*)\vcentcolon=\sum_{y\in\mathcal{X}}m(z,y)$ and
$m(*,z)\vcentcolon=\sum_{x\in\mathcal{X}}m(x,z)$. Also, define two trivial
clusterings: $\Gamma^{(0)}$ containing the single cluster $\mathcal{X}$, and
$\Gamma^{(t+1)}$ containing singleton clusters $\\{x\\}$ for each
$x\in\mathcal{X}$.

We give a coupling $\pi\in\Pi(\mu,\nu)$ iteratively by a sequence of measures
$\pi^{(-2)},\pi^{(-1)},\pi^{(0)},\dotsc,\pi^{(t)}$ over
$\mathcal{X}\times\mathcal{X}$ as follows. Let $\pi^{(-2)}$ be zero
everywhere. Then for each $i=-1,\dotsc,t$,

  1. 1.

Define $r^{(i)},s^{(i)}:\mathcal{X}\to\mathbb{R}_{\geq 0}$ by
$r^{(i)}(x)\vcentcolon=\mu(x)-\pi^{(i-1)}(x,*)$ and
$s^{(i)}(y)\vcentcolon=\nu(y)-\pi^{(i-1)}(*,y)$.

  2. 2.

Let $\rho^{(i)}:\mathcal{X}\times\mathcal{X}\to\mathbb{R}_{\geq 0}$ be a
measure satisfying

    1. (a)

$\rho^{(i)}(x,y)=0$ if $\gamma^{(t-i)}(x)\neq\gamma^{(t-i)}(y)$;

    2. (b)

For each $z\in\mathcal{X}$, $\rho^{(i)}(z,*)\leq r^{(i)}(z)$ and
$\rho^{(i)}(*,z)\leq s^{(i)}(z)$; and

    3. (c)

For each $\Gamma^{(t-i)}_{j}\in\Gamma^{(t-i)}$, either $\rho(z,*)=r^{(i)}(z)$
for every $z\in\Gamma^{(t-i)}_{j}$ or $\rho(*,z)=s^{(i)}(z)$ for every
$z\in\Gamma^{(t-i)}_{j}$.

The existence of such an object is given by standard arguments, e.g. by seeing
$\rho^{(i)}$ as the flows in a flow network.

  3. 3.

Set $\pi^{(i)}(x,y)\vcentcolon=\pi^{(i-1)}(x,y)+\rho^{(i)}(x,y)$ for each
$x,y\in\mathcal{X}$.

Let $\pi\vcentcolon=\pi^{(t)}$. We first observe that $\pi\in\Pi(\mu,\nu)$. It
is clear by construction that $\pi(z,*)\leq\mu(z)$ and $\pi(*,z)\leq\nu(z)$
for every $z\in\mathcal{X}$, since the contributions $\rho^{(i)}$ are
constrained to ensure this. On the other hand, property (c) in the $t$-th
iteration ensures that either $\rho^{(t)}(z,*)=r^{(t)}(z)$ for every
$z\in\mathcal{X}$, or $\rho^{(t)}(*,z)=s^{(t)}(z)$ for every
$z\in\mathcal{X}$. This means that either $\pi(x,*)=\mu(x)$ for every
$z\in\mathcal{X}$ or $\pi(*,z)=\nu(z)$ for every $z\in\mathcal{X}$, and either
of these conditions (along with the aforementioned upper bounds) implies the
other. Thus the marginals or $\pi$ are $\mu$ and $\nu$, as needed.

Then, we show that
$\underset{(\bm{x},\bm{y})\sim\pi}{\mathbb{E}}\left[\mathsf{dist}(x,y)\right]$
satisfies the claimed upper bound. We will need the following observation: for
each $i=0,\dotsc,t$ and $\Gamma^{(t-i)}_{j}\in\Gamma^{(t-i)}$,

$\sum_{x,y\in\Gamma^{(t-i)}_{j}}\rho^{(i)}(x,y)\leq\frac{1}{2}\sum_{\Gamma^{(t-i+1)}_{j^{\prime}}\subseteq\Gamma^{(t-i)}_{j}}\left\lvert\mu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]-\nu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]\right\rvert\,.$

This follows from properties (a)–(c) of the $(i-1)$-st iteration, which imply
that for each $\Gamma^{(t-i+1)}_{j}\in\Gamma^{(t-i+1)}$, either
$\sum_{x\in\Gamma^{(t-i+1)}_{j}}r^{(i)}(x)=\left\lvert\mu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]-\nu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]\right\rvert$
and $s^{(i)}(y)=0$ for every $y\in\Gamma^{(t-i+1)}_{j}$, or vice versa. Now,

$\displaystyle\underset{(\bm{x},\bm{y})\sim\pi}{\mathbb{E}}\left[\mathsf{dist}(x,y)\right]$
$\displaystyle=\sum_{i=0}^{t}\sum_{\Gamma^{(t-i)}_{j}\in\Gamma^{(t-i)}}\sum_{x,y\in\Gamma^{(t-i)}_{j}}\mathsf{dist}(x,y)\rho^{(i)}(x,y)$
$\displaystyle\leq\sum_{i=1}^{t}\delta_{t-i}\sum_{\Gamma^{(t-i)}_{j}\in\Gamma^{(t-i)}}\frac{1}{2}\sum_{\Gamma^{(t-i+1)}_{j^{\prime}}\subseteq\Gamma^{(t-i)}_{j}}\left\lvert\mu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]-\nu\left[\Gamma^{(t-i+1)}_{j^{\prime}}\right]\right\rvert$
$\displaystyle\qquad+\sum_{\Gamma^{(t)}_{j}\in\Gamma^{(t)}}\sum_{x,y\in\Gamma^{(t)}_{j}}\mathsf{diam}\left(\Gamma^{(t)}_{j}\right)\rho^{(0)}(x,y)$
$\displaystyle=\sum_{i=1}^{t}\delta_{t-i}\mathsf{dist}_{\mathsf{TV}}\left({\mu}_{\lfloor{\Gamma^{(t-i+1)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(t-i+1)}}\rfloor}\right)+\sum_{\Gamma^{(t)}_{j}\in\Gamma^{(t)}}\sum_{x\in\Gamma^{(t)}_{j}}\mathsf{diam}\left(\Gamma^{(t)}_{j}\right)\rho^{(0)}(x,*)$
$\displaystyle\leq\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}\left({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor}\right)+\sum_{x\in\mathcal{X}}\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(x)}\right)\mu(x)$
$\displaystyle=\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}\left({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor}\right)+\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(\bm{x})}\right)\right]\,.$

Note that in the first equality, we could skip $i=-1$ in the summation because
$\rho^{(-1)}(x,y)>0$ only when $x=y$, in which case $\mathsf{dist}(x,y)=0$. ∎

This lemma may also be extended to cover continuous settings such as
$[0,1]^{d}$, e.g. by a discretization argument:

######  Lemma A.3.

Let $\mathcal{X}\subset\mathbb{R}^{d}$ be a bounded set in Euclidean space.
Let $p\geq 1$ and equip $\mathcal{X}$ with normalized $\ell_{p}$ metric
$\mathsf{dist}(\cdot,\cdot)$. Suppose $(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$ is
a hierarchical clustering of $\mathcal{X}$ with diameter bounds
$\delta_{1},\dotsc,\delta_{t}$, such that every cell
$\Gamma^{(i)}_{j}\in\Gamma^{(i)}$ is $\mu$\- and $\nu$-measurable. Then for
every pair of probability distributions $\mu,\nu$ over $\mathcal{X}$,

$\mathsf{EMD}_{\mathsf{dist}}(\mu,\nu)\leq\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor})+\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(x)}\right)\right]\,.$

###### Proof.

Recall that a metric space is said to be _totally bounded_ if it has a finite
$\epsilon$-net for every $\epsilon>0$. It is a standard result that every
bounded subspace of Euclidean space is totally bounded. Thus each
$\Gamma^{(t)}_{j}\in\Gamma^{(t)}$ admits a finite $\epsilon$-net under
Euclidean distance, and since every $\ell_{p}$ metric in $\mathbb{R}^{d}$ is
within a finite factor of each other, we obtain a finite $\epsilon$-net under
metric $\mathsf{dist}(\cdot,\cdot)$. Since clusterings have finitely many
clusters by definition, we conclude that for every $\epsilon>0$ there exists a
finite set $S_{\epsilon}\subset\mathcal{X}$ such that
$S_{\epsilon}\cap\Gamma^{(t)}_{j}$ is an $\epsilon$-net for $\Gamma^{(t)}_{j}$
for every $\Gamma^{(t)}_{j}\in\Gamma^{(t)}$.

Fix some $\epsilon>0$. Let $f:\mathcal{X}\to S_{\epsilon}$ map each point
$x\in\mathcal{X}$ to a closest point in
$S_{\epsilon}\cap\Gamma^{(t)}_{\gamma^{(t)}(x)}$. Note that, since the
clustering is hierarchical, it follows that
$\gamma^{(i)}(x)=\gamma^{(i)}(f(x))$ for every $i\in[t]$. Let $\mu^{\prime}$
be the probability distribution of $f(\bm{x})$ where $\bm{x}\sim\mu$, and
similarly let $\nu^{\prime}$ be the probability distribution of $f(\bm{y})$
where $\bm{y}\sim\nu$.

We first claim that
$\mathsf{EMD}_{\mathsf{dist}}(\mu,\mu^{\prime})\leq\epsilon$. Indeed, the
probability distribution over $\mathcal{X}\times\mathcal{X}$ given by
$\pi(x,f(x))=\mu(x)$ for all $x\in\mathcal{X}$ and $\pi(x,y)=0$ elsewhere is a
coupling in $\Pi(\mu,\mu^{\prime})$, and
$\underset{(\bm{x},\bm{y})\sim\pi}{\mathbb{E}}\left[\mathsf{dist}(\bm{x},\bm{y})\right]=\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{dist}(\bm{x},f(\bm{x})\right]\leq\epsilon$,
the inequality since $S_{\epsilon}\cap\Gamma^{(t)}_{\gamma^{(t)}(x)}$ is an
$\epsilon$-net for $\Gamma^{(t)}_{\gamma^{(t)}(x)}$. Similarly, we get that
$\mathsf{EMD}_{\mathsf{dist}}(\nu,\nu^{\prime})\leq\epsilon$.

We also note that for any $i\in[t]$,
${\mu}_{\lfloor{\Gamma^{(i)}}\rfloor}={\mu^{\prime}}_{\lfloor{\Gamma^{(i)}}\rfloor}$
and
${\nu}_{\lfloor{\Gamma^{(i)}}\rfloor}={\nu^{\prime}}_{\lfloor{\Gamma^{(i)}}\rfloor}$.
This holds because each point $x$ is mapped to another point in the same
cluster, which does not change the induced distributions. Similarly,
$\underset{\bm{x}\sim\mu^{\prime}}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(\bm{x})}\right)\right]=\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(\bm{x})}\right)\right]$,
since the total probability mass in each cluster remains unchanged between
$\mu$ and $\mu^{\prime}$. Now, $(S_{\epsilon},\mathsf{dist})$ is a finite
metric space, so Lemma A.2 and the triangle inequality give

$\displaystyle\mathsf{EMD}_{\mathsf{dist}}(\mu,\nu)$
$\displaystyle\leq\mathsf{EMD}_{\mathsf{dist}}(\mu,\mu^{\prime})+\mathsf{EMD}_{\mathsf{dist}}(\mu^{\prime},\nu^{\prime})+\mathsf{EMD}_{\mathsf{dist}}(\nu^{\prime},\nu)$
$\displaystyle\leq
2\epsilon+\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}({\mu^{\prime}}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu^{\prime}}_{\lfloor{\Gamma^{(i)}}\rfloor})+\underset{\bm{x}\sim\mu^{\prime}}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(x)}\right)\right]$
$\displaystyle=2\epsilon+\sum_{i=1}^{t}\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor})+\underset{\bm{x}\sim\mu}{\mathbb{E}}\left[\mathsf{diam}\left(\Gamma^{(t)}_{\gamma^{(t)}(x)}\right)\right]\,.$

This holds for every $\epsilon>0$, so the claim follows. ∎

We will also use the special case where there is a single clustering $\Gamma$;
for convenience, we state this simplified version below.

See 3.4

###  A.2 EMD Testing on the Hypergrid

Similar to [DNNR11], Lemma A.2 implies algorithms for testing identity and
equivalence of distributions with respect to EMD using a hierarchical
clustering, with sample complexity depending on the clustering, as shown
below.

Let $m^{\mathsf{id}}(n,\epsilon)\vcentcolon=n^{1/2}/\epsilon^{2}$ denote the
optimal sample complexity of testing identity of distributions supported on at
most $n$ elements with distance parameter $\epsilon$ [VV17], and let
$m^{\mathsf{eq}}(n,\epsilon)\vcentcolon=\max\\{n^{1/2}/\epsilon^{2},n^{2/3}/\epsilon^{4/3}\\}$
denote the same for equivalence testing [CDVV14].

######  Proposition A.4.

Let $(\mathcal{X},\mathsf{dist})$ be a finite metric space, let $\epsilon>0$,
and let $(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$ be a hierarchical clustering with
diameter bounds $\delta_{1},\dotsc,\delta_{t}$ such that
$\delta_{t}\leq\epsilon/2$. There exists an $\mathsf{EMD}_{\mathsf{dist}}$
identity tester with sample complexity

$O\left(\log(t)\sum_{i=1}^{t}m^{\mathsf{id}}\left(|\Gamma^{(i)}|,\frac{\epsilon}{2t\delta_{i-1}}\right)\right)$

and an $\mathsf{EMD}_{\mathsf{dist}}$ equivalence tester with sample
complexity

$O\left(\log(t)\sum_{i=1}^{t}m^{\mathsf{eq}}\left(|\Gamma^{(i)}|,\frac{\epsilon}{2t\delta_{i-1}}\right)\right)\,.$

###### Proof.

Each algorithm iterates over $i=1,\dotsc,t$, and in each step runs a standard
identity/equivalence tester on distributions
${\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor}$
with distance parameter $\frac{\epsilon}{2t\delta_{i-1}}$, paying an extra
$O(\log t)$ factor in the sample complexity to amplify the success probability
to $1-\frac{1}{3t}$; it rejects if that tester rejects in any step, and
accepts otherwise. Correctness follows from Lemma A.2 and an averaging
argument: if $\mathsf{EMD}_{\mathsf{dist}}(\mu,\nu)>\epsilon$ and
$\delta_{t}\leq\epsilon/2$, then there exists $i\in[t]$ for which
$\delta_{i-1}\mathsf{dist}_{\mathsf{TV}}({\mu}_{\lfloor{\Gamma^{(i)}}\rfloor},{\nu}_{\lfloor{\Gamma^{(i)}}\rfloor})>\frac{\epsilon}{2t}$,
so some step of the algorithm rejects with good probability. On the other
hand, if $\mu=\nu$ then each step only causes the algorithm to reject with
probability at most $\frac{1}{3t}$, and an union bound completes the proof. ∎

Applying this general strategy to the hypergrid $[n]^{d}$, with the same
hierarchical clustering as [DNNR11], yields the EMD testing results we use. We
note that, by virtue of having used the optimal sample complexity of
equivalence testing from [CDVV14] in the reduction, the bounds we obtain are
slightly better than those explicitly computed in [DNNR11] for some values of
$d$.

See 3.12

###### Proof.

We let $t=\log(2/\epsilon)$ and fix the following hierarchical clustering
$(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$: for each $i\in[t]$, $\Gamma^{(i)}$
partitions the domain into $2^{id}$ equal-sized hypercubes, so that each cell
of $\Gamma^{(i)}$ is a hypercube whose side length is a $1/2^{i}$ fraction of
the side length of $[n]^{d}$. Recall that $\mathsf{dist}$ is a normalized
metric, so that $[n]^{d}$ has unit diameter. It follows that
$\delta_{i}=2^{-i}$, $i\in[t]$, is a diameter bound for
$(\Gamma^{(1)},\dotsc,\Gamma^{(t)})$, and indeed $\delta_{t}\leq\epsilon/2$.
Then Proposition A.4 gives an $\mathsf{EMD}_{\mathsf{dist}}$ identity tester
with sample complexity

$\widetilde{O}\left(\sum_{i=1}^{t}\frac{\left(2^{id}\right)^{1/2}}{(\epsilon/2^{-i+1})^{2}}\right)=\widetilde{O}\left(\epsilon^{-2}\sum_{i=1}^{t}\left(2^{\frac{d}{2}-2}\right)^{i}\right)\,.$

and an $\mathsf{EMD}_{\mathsf{dist}}$ equivalence tester with sample
complexity

$\widetilde{O}\left(\sum_{i=1}^{t}\max\left\\{\frac{\left(2^{id}\right)^{1/2}}{(\epsilon/2^{-i+1})^{2}},\frac{\left(2^{id}\right)^{2/3}}{(\epsilon/2^{-i+1})^{4/3}}\right\\}\right)=\widetilde{O}\left(\max\left\\{\epsilon^{-2}\sum_{i=1}^{t}\left(2^{\frac{d}{2}-2}\right)^{i},\epsilon^{-\frac{4}{3}}\sum_{i=1}^{t}\left(2^{\frac{2}{3}d-\frac{4}{3}}\right)^{i}\right\\}\right)\,.$

The summand $\left(2^{\frac{d}{2}-2}\right)^{i}$ is maximized at $i=1$ when
$d\leq 4$ and at $i=t$ when $d\geq 5$, while
$\left(2^{\frac{2}{3}d-\frac{4}{3}}\right)^{i}$ is maximized at $i=1$ when
$d\leq 2$ and at $i=t$ when $d\geq 3$. Additionally, each sum may be upper
bounded by $t=\log(2/\epsilon)$ times its maximum summand. The sample
complexity claims follow. ∎

######  Remark A.5.

At least for input distributions $\mu,\nu$ that are absolutely continuous with
respect to the Lebesgue measure, Lemma 3.12 also holds when the domain is
$[0,1]^{d}$ instead of $[n]^{d}$, since in this case we also have the EMD
inequality by Lemma A.3. In this case, the $\mu$\- and $\nu$-measurability
requirement on the (Lebesgue measurable) cells follows from the Radon-Nikodym
theorem.

##  Appendix B Missing Proofs from Section 4.2

See 4.14

###### Proof.

When $\phi=\phi^{\mathsf{cycle}}$, we have that $\nu^{\top}\phi$ is a constant
vector (this is true for any circulant matrix), and hence $\nu^{\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 $\nu^{\top}\phi z$. We expand this expression as follows:

$\nu^{\top}\phi
z=\sum_{i,j\in\mathbb{Z}_{n}}\nu_{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{\tiny?}}}}{{\leq}}\frac{2\delta}{\rho^{2}}\,,$
(2)

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 (2) (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
(2), 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]\,.$
(3)

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 (3) 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}=\eta^{\lvert
i-j\rvert}$. In the edge case when $\rho=1$ and thus $\eta=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 (2) and we are done. Now, suppose $0<\eta<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}{\rho^{2}}\,,$

where the last inequality is due to Proposition B.1 below. ∎

######  Proposition B.1.

Let $\rho\in(0,1)$. Let $S_{i}$ denote the sum of the entries in the $i$-th
column of $\phi^{\mathsf{path}}$ for each $i\in\mathbb{Z}_{n}$, and let
$h\vcentcolon=(n-1)/2$. Then for any non-negative integer $N\leq n/2$,

$-\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}<\frac{2}{\rho^{2}}\,.$

###### Proof.

Recall that $\phi^{\mathsf{path}}_{i,j}=\eta^{\lvert i-j\rvert}$ where
$\eta=1-\rho$. We express the column sums explicitly and reduce the geometric
sums that emerge:

$\displaystyle\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]$
$\displaystyle\quad=\left[\begin{array}[]{l}-\sum_{i=0}^{\lceil
N/2\rceil-1}\sum_{j=0}^{n-1}\eta^{\lvert i-j\rvert}-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\sum_{j=0}^{n-1}\eta^{\lvert n-1-i-j\rvert}\\\
+\sum_{i=0}^{\lceil N/2\rceil-1}\sum_{j=0}^{n-1}\eta^{\lvert\lceil
h\rceil+i-j\rvert}+\sum_{i=0}^{\lfloor
N/2\rfloor-1}\sum_{j=0}^{n-1}\eta^{\lvert\lfloor h\rfloor-
i-j\rvert}\end{array}\right]$
$\displaystyle\quad=\left[\begin{array}[]{l}-\sum_{i=0}^{\lceil
N/2\rceil-1}\left(\sum_{j=0}^{i}\eta^{i-j}+\sum_{j=i+1}^{n-1}\eta^{j-i}\right)\\\
-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\left(\sum_{j=0}^{n-1-i}\eta^{n-1-i-j}+\sum_{j=n-i}^{n-1}\eta^{j+i+1-n}\right)\\\
+\sum_{i=0}^{\lceil N/2\rceil-1}\left(\sum_{j=0}^{\lceil
h\rceil+i}\eta^{\lceil h\rceil+i-j}+\sum_{j=\lceil
h\rceil+i+1}^{n-1}\eta^{j-i-\lceil h\rceil}\right)\\\ +\sum_{i=0}^{\lfloor
N/2\rfloor-1}\left(\sum_{j=0}^{\lfloor h\rfloor-i}\eta^{\lfloor h\rfloor-
i-j}+\sum_{j=\lfloor h\rfloor-i+1}^{n-1}\eta^{j+i-\lfloor
h\rfloor}\right)\end{array}\right]$
$\displaystyle\quad=\left[\begin{array}[]{l}-\sum_{i=0}^{\lceil
N/2\rceil-1}\left(\frac{\eta^{i}-\eta^{-1}}{1-\eta^{-1}}+\frac{\eta-\eta^{n-i}}{1-\eta}\right)-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\left(\frac{\eta^{n-1-i}-\eta^{-1}}{1-\eta^{-1}}+\frac{\eta-\eta^{i+1}}{1-\eta}\right)\\\
+\sum_{i=0}^{\lceil N/2\rceil-1}\left(\frac{\eta^{\lceil
h\rceil+i}-\eta^{-1}}{1-\eta^{-1}}+\frac{\eta-\eta^{n-i-\lceil
h\rceil}}{1-\eta}\right)+\sum_{i=0}^{\lfloor
N/2\rfloor-1}\left(\frac{\eta^{\lfloor
h\rfloor-i}-\eta^{-1}}{1-\eta^{-1}}+\frac{\eta-\eta^{n+i-\lfloor
h\rfloor}}{1-\eta}\right)\end{array}\right]$
$\displaystyle\quad=\frac{1}{\rho}\left[\begin{array}[]{l}-\sum_{i=0}^{\lceil
N/2\rceil-1}\left(1-\eta^{i+1}+\eta-\eta^{n-i}\right)-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\left(1-\eta^{n-i}+\eta-\eta^{i+1}\right)\\\ +\sum_{i=0}^{\lceil
N/2\rceil-1}\left(1-\eta^{\lceil h\rceil+1+i}+\eta-\eta^{n-i-\lceil
h\rceil}\right)+\sum_{i=0}^{\lfloor N/2\rfloor-1}\left(1-\eta^{\lfloor
h\rfloor+1-i}+\eta-\eta^{n+i-\lfloor h\rfloor}\right)\end{array}\right]$
$\displaystyle\quad=\frac{1}{\rho}\left[\begin{array}[]{l}\sum_{i=0}^{\lceil
N/2\rceil-1}\eta^{i+1}+\sum_{i=0}^{\lceil
N/2\rceil-1}\eta^{n-i}+\sum_{i=0}^{\lfloor
N/2\rfloor-1}\eta^{n-i}+\sum_{i=0}^{\lfloor N/2\rfloor-1}\eta^{i+1}\\\
-\sum_{i=0}^{\lceil N/2\rceil-1}\eta^{\lceil h\rceil+1+i}-\sum_{i=0}^{\lceil
N/2\rceil-1}\eta^{n-i-\lceil h\rceil}-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\eta^{\lfloor h\rfloor+1-i}-\sum_{i=0}^{\lfloor
N/2\rfloor-1}\eta^{n+i-\lfloor h\rfloor}\end{array}\right]$
$\displaystyle\quad=\frac{1}{\rho}\left[\begin{array}[]{l}\frac{\eta-\eta^{\lceil
N/2\rceil+1}}{1-\eta}+\frac{\eta^{n}-\eta^{n-\lceil
N/2\rceil}}{1-\eta^{-1}}+\frac{\eta^{n}-\eta^{n-\lfloor
N/2\rfloor}}{1-\eta^{-1}}+\frac{\eta-\eta^{\lfloor N/2\rfloor+1}}{1-\eta}\\\
-\frac{\eta^{\lceil h\rceil+1}-\eta^{\lceil h\rceil+1+\lceil
N/2\rceil}}{1-\eta}-\frac{\eta^{n-\lceil h\rceil}-\eta^{n-\lceil
h\rceil-\lceil N/2\rceil}}{1-\eta^{-1}}-\frac{\eta^{\lfloor
h\rfloor+1}-\eta^{\lfloor h\rfloor+1-\lfloor
N/2\rfloor}}{1-\eta^{-1}}-\frac{\eta^{n-\lfloor h\rfloor}-\eta^{n+\lfloor
N/2\rfloor-\lfloor h\rfloor}}{1-\eta}\end{array}\right]$
$\displaystyle\quad=\frac{1}{\rho^{2}}\left[\begin{array}[]{l}\eta-\eta^{\lceil
N/2\rceil+1}+\eta^{n+1-\lceil N/2\rceil}-\eta^{n+1}\\\ +\eta^{n+1-\lfloor
N/2\rfloor}-\eta^{n+1}+\eta-\eta^{\lfloor N/2\rfloor+1}\\\ -\eta^{\lceil
h\rceil+1}+\eta^{\lceil h\rceil+1+\lceil N/2\rceil}-\eta^{n+1-\lceil
h\rceil-\lceil N/2\rceil}+\eta^{n+1-\lceil h\rceil}\\\ -\eta^{\lfloor
h\rfloor+2-\lfloor N/2\rfloor}+\eta^{\lfloor h\rfloor+2}-\eta^{n-\lfloor
h\rfloor}+\eta^{n+\lfloor N/2\rfloor-\lfloor h\rfloor}\end{array}\right]$
$\displaystyle\quad=\frac{1}{\rho^{2}}\left[\begin{array}[]{l}(\eta+\eta)+(\eta^{n+1-\lceil
N/2\rceil}-\eta^{\lceil N/2\rceil+1})+(\eta^{n+1-\lfloor
N/2\rfloor}-\eta^{\lfloor N/2\rfloor+1})-(\eta^{n+1}+\eta^{n+1})\\\
+(\eta^{\lceil h\rceil+1+\lceil N/2\rceil}-\eta^{\lceil
h\rceil+1})+(\eta^{n+1-\lceil h\rceil}-\eta^{n+1-\lceil h\rceil-\lceil
N/2\rceil})\\\ +(\eta^{\lfloor h\rfloor+2}-\eta^{\lfloor h\rfloor+2-\lfloor
N/2\rfloor})+(\eta^{n+\lfloor N/2\rfloor-\lfloor h\rfloor}-\eta^{n-\lfloor
h\rfloor})\end{array}\right]$ $\displaystyle\quad<\frac{2}{\rho^{2}}\,,$

where we used the facts that $0<\eta<1$ and, in the last step, that $2\lceil
N/2\rceil\leq n$ (which holds because $2N\leq n$ by assumption). ∎