also mention again that negative results for testing argued via sampling with
replacement can be traced back to Example 1 of Gretton et al., (2012).
Following the construction of Lemma 1 in Barber, (2020), let
$\mathcal{L}=\\{(X_{1},Y_{1},Z_{1}),\ldots,(X_{J},Y_{J},Z_{J})\\}\overset{\mathrm{i.i.d.}}{\sim}P_{X,Y,Z}\in\mathcal{P}_{1}$
be ghost samples for some $J\geq n(n-1)$. Given $\mathcal{L}$, draw
$\\{(X_{1}^{\prime},Y_{1}^{\prime},Z_{1}^{\prime}),\ldots,(X_{n}^{\prime},Y_{n}^{\prime},Z_{n}^{\prime})\\}$
from $\mathcal{L}$ _without replacement_. We denote this conditional sampling
distribution by $P_{\mathrm{without}}$. Then by marginalizing over
$\mathcal{L}$, we simply have the identity

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi]=\mathbb{E}_{\mathcal{L}}[\mathbb{E}_{P_{\mathrm{without}}}[\phi|\mathcal{L}]].$
(24)

Next consider drawing
$\\{(X_{1}^{\prime},Y_{1}^{\prime},Z_{1}^{\prime}),\ldots,(X_{n}^{\prime},Y_{n}^{\prime},Z_{n}^{\prime})\\}$
from $\mathcal{L}$ _with replacement_ and denote this conditional sampling
distribution by $P_{\mathrm{with}}$. By Stam, (1978), the total variation
distance between $P_{\mathrm{with}}$ and $P_{\mathrm{without}}$ can be bounded
by $n(n-1)/J$. Therefore, using the identity (24), we have

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi]\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\mathbb{E}_{\mathcal{L}}[\mathbb{E}_{P_{\mathrm{with}}}[\phi|\mathcal{L}]]+\frac{n(n-1)}{J}.$

Let $\mathcal{A}$ be the event that $Z_{1},\ldots,Z_{J}\leavevmode\nobreak\
\text{are distinct}$. Under the event $\mathcal{A}$, we have
$X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y|Z$ for $(X,Y,Z)\sim P_{\mathrm{with}}$ since
the conditional distribution of $X,Y$ given any $Z$ takes a single value (i.e.
conditionally degenerate). Therefore we should have

$\displaystyle\mathbb{E}_{P_{\mathrm{with}}}[\phi|\mathcal{L},\mathcal{A}]\leq\alpha\quad\text{and}\quad\mathbb{E}_{P_{\mathrm{with}}}[\phi|\mathcal{L},\mathcal{A}^{c}]\leq
1$

as $\sup_{P\in\mathcal{P}_{0,\mathrm{disc}}}\mathbb{E}_{P}[\phi]\leq\alpha$
from our condition and $\phi\leq 1$. Combining the results together with the
law of total expectation, we have for any $P_{X,Y,Z}\in\mathcal{P}_{1}$

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}_{\mathcal{L}}[\mathbb{E}_{P_{\mathrm{with}}}[\phi|\mathcal{L},\mathcal{A}]\times\mathbb{P}(\mathcal{A}|\mathcal{L})]+\mathbb{E}_{\mathcal{L}}[\mathbb{E}_{P_{\mathrm{with}}}[\phi|\mathcal{L},\mathcal{A}^{c}]\times\mathbb{P}(\mathcal{A}^{c}|\mathcal{L})]+\frac{n(n-1)}{J}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha\times\mathbb{P}(\mathcal{A})+\mathbb{P}(\mathcal{A}^{c})+\frac{n(n-1)}{J}.$

Therefore the desired result follows.

######  Remark 10.

  * •

From Equation (2.1) of Stam, (1978), the result still holds if we replace
$\frac{n(n-1)}{J}$ in the bound (4) with $2-2\frac{J!}{(J-n)!J^{n}}$ where one
can prove that $2-2\frac{J!}{(J-n)!J^{n}}\leq\frac{n(n-1)}{J}$ by induction.

  * •

Suppose that $Z$ has a uniform distribution supported on a set of size
$M_{n}:=M>J_{n}:=J$. Then $\rho_{J,P}=\mathbb{P}(\mathcal{A})$ is the
probability that there is no collision, which can be computed as

$\displaystyle\rho_{J,P}=\frac{M}{M}\times\frac{M-1}{M}\times\cdots\times\frac{M-(J-1)}{M}=\frac{M!}{M^{J}(M-J)!}.$

This probability is lower and upper bounded by

$\displaystyle
1-\frac{J(J-1)}{2M}\leq\rho_{J,P}\leq\exp\left({-\frac{J(J-1)}{2M}}\right).$

See Equation (2.4) of Stam, (1978) for details. Therefore, in this case, the
test $\phi$ has asymptotically no power when

$\displaystyle\frac{J_{n}^{2}}{M_{n}}\rightarrow
0\quad\text{and}\quad\frac{n^{2}}{J_{n}}\rightarrow 0.$

Now let $a_{n}$ be a positive sequence that goes to zero arbitrarily slowly as
$n\rightarrow\infty$. Then by taking $J_{n}^{2}=M_{n}\times a_{n}$, the above
conditions become equivalent to

$\displaystyle\frac{n^{4}}{M_{n}\times a_{n}}\rightarrow 0.$

This essentially means that any valid test has asymptotically no power in this
setup if $M_{n}$ increases much faster than $n^{4}$.

  * •

We also note that the same proof carries over even if we assume that $(X,Y,Z)$
is supported on a compact set.

###  A.2 Proof of Lemma 2

Continuing from Lemma 1, we have the list of inequalities:

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi_{\mathrm{perm},n}]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\alpha+\mathcal{D}_{\mathrm{TV}}\big{(}Q_{X,Y,\widetilde{Z}}^{n},\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}\big{)}\overset{\text{(i)}}{\leq}\leavevmode\nobreak\
\alpha+\sqrt{2}\mathcal{D}_{\mathrm{H}}\big{(}Q_{X,Y,\widetilde{Z}}^{n},\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}\big{)}$
$\displaystyle\overset{\text{(ii)}}{\leq}\leavevmode\nobreak\ $
$\displaystyle\alpha+\sqrt{2n}\mathcal{D}_{\mathrm{H}}\big{(}Q_{X,Y,\widetilde{Z}},\widetilde{Q}_{X,Y,\widetilde{Z}}\big{)}$
$\displaystyle\overset{\text{(iii)}}{=}\leavevmode\nobreak\ $
$\displaystyle\alpha+\Bigg{\\{}2n\sum_{m=1}^{M}q_{\widetilde{Z}}(m)\times\mathcal{D}_{{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}\Bigg{\\}}^{1/2},$

where step (i) uses the well-known inequality
$\mathcal{D}_{\mathrm{TV}}(P,Q)\leq\sqrt{2}\mathcal{D}_{\mathrm{H}}(P,Q)$ and
step (ii) use subadditivity of the squared Hellinger distance for product
measures and step (iii) can be verified by the definition of the Hellinger
distance. This completes the proof of Lemma 2.

###  A.3 Proof of Theorem 2

We start with the case of $\gamma\in[1,2]$. In this case, the first inequality
(71) of Lemma 4 shows that

$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\leq\mathcal{D}_{\gamma,\mathrm{H}}^{\gamma}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\quad\text{and}$
$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}\leq\mathcal{D}_{\gamma,\mathrm{H}}^{\gamma}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}.$

Therefore, from Lemma 3, it holds that

$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
6\mathbb{E}_{Z_{m},Z_{m}^{{}^{\prime}},Z_{m}^{{}^{\prime\prime}}}\big{[}\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\times\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}\big{]}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
6\mathbb{E}_{Z_{m},Z_{m}^{{}^{\prime}},Z_{m}^{{}^{\prime\prime}}}\big{[}\mathcal{D}_{\gamma,\mathrm{H}}^{\gamma}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\times\mathcal{D}_{\gamma,\mathrm{H}}^{\gamma}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}\big{]}$
$\displaystyle\overset{\text{(i)}}{\leq}\leavevmode\nobreak\ $ $\displaystyle
6L^{2\gamma}\sup_{z,z^{\prime}\in
B_{m}}\delta^{2\gamma}(z,z^{\prime})\leavevmode\nobreak\
\overset{\text{(ii)}}{\leq}\leavevmode\nobreak\
6L^{2\gamma}h^{2\gamma}\quad\text{for any $m\in[M]$,}$

where step (i) uses $\gamma$-Hellinger Lipschitzness and step (ii) follows by
the definition of $h$ in (7). Applying this result to the type I error bound
in terms of the Hellinger distance in Lemma 2 yields the result.

Next we turn to the case of $\gamma>2$. In this case, Corollary 1 proves

$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\leq
C_{\gamma}\mathcal{D}_{\gamma,\mathrm{H}}^{2}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\quad\text{and}$
$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}\leq
C_{\gamma}^{\prime}\mathcal{D}_{\gamma,\mathrm{H}}^{2}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)},$

where $C_{\gamma}$ and $C_{\gamma}^{\prime}$ are constants that only depend on
$\gamma$. Then following the same steps as before, it holds that

$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}\leq\leavevmode\nobreak\
C_{\gamma}^{{}^{\prime\prime}}L^{2}h^{2}\quad\text{for any $m\in[M]$,}$

where $C_{\gamma}^{{}^{\prime\prime}}$ is another constant that only depends
on $\gamma$. Combining this inequality with Lemma 2 yields the result. This
completes the proof of Theorem 2.

###  A.4 Proof of Theorem 3

The proof of Theorem 3 follows exactly the same lines of the proof of Theorem
2 by replacing Corollary 1 with Lemma 5. For this reason, we omit the details.

###  A.5 Proof of Theorem 4

We proceed by considering the case of $\gamma$-Hellinger Lipschitzness
(Appendix A.5.1 for $2\leq\gamma$ and Appendix A.5.2 for $1\leq\gamma<2$) and
$\gamma$-Rényi Lipschitzness (Appendix A.5.3) in order. We start with a high-
level sketch of the proof.

  * •

As discussed in Remark 5, we would like to show that the permutation test
$\phi_{\mathrm{perm},n}^{\dagger}$ has power greater than $1-\beta$ for the
hypothesis (13). This in turn implies our desired claim that
$\phi_{\mathrm{perm},n}^{\dagger}$ has the type I error rate greater than
$1-\beta$ for $H_{0}:X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y|Z$. In this regard, we need to consider a
powerful test that can reliably distinguish between $Q_{X,Y,\widetilde{Z}}$
and $\widetilde{Q}_{X,Y,\widetilde{Z}}$ to prove the result. To this end, we
analyze the test statistic (11):

$\displaystyle T_{\mathrm{CI}}=\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}U(\bm{W}_{m}).$

  * •

However, it is quite complicated to study $T_{\mathrm{CI}}$ directly as it is
a sum of dependent variables. Our strategy to overcome this complication is to
construct a distributional setting where
$T_{\mathrm{CI}}\approx\sigma_{1}U(\bm{W}_{1})$ with high probability. More
formally, we let the marginal density of $Z$ be

$\displaystyle p_{Z}(z)=\begin{cases*}M-\epsilon,&\text{if
$z\in[0,M^{-1}]$,}\\\ \frac{\epsilon}{M-1},&\text{if $z\in(M^{-1},1]$,}\\\
0,&\text{otherwise,}\end{cases*}$ (25)

for some $\epsilon:=\epsilon_{n}>0$, which may vary depending on $n$.
Intuitively, when $\epsilon$ is sufficiently small (this will become precise
in the proof), we only observe samples from the first bin with high
probability and thus our test statistic will be dominated by the first term of
the test statistic, i.e.

$\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}U(\bm{W}_{m})\approx\sigma_{1}U(\bm{W}_{1}).$

If this is the case, then we are essentially testing for unconditional
independence between $X$ and $Y$ within the first bin, and we can leverage the
results of Kim et al., (2020) to investigate the power of the permutation test
based on $\sigma_{1}U(\bm{W}_{1})$.

  * •

In particular, Kim et al., (2020) present sufficient conditions using the
first two moments of a test statistic under which the permutation test based
on $U(\bm{W}_{1})$ has significant power. At a high-level, these sufficient
conditions guarantee that the test statistic is greater than the critical
value of the permutation test with high probability, which yields high power.

  * •

Throughout this proof, we only deal with the type II error (or $1-$power) of
$\phi_{\mathrm{perm},N}$ under Poissonization since that of
$\phi_{\mathrm{perm},n}^{\dagger}$ is upper bounded by

$\displaystyle\mathbb{E}[1-\phi_{\mathrm{perm},n}^{\dagger}]\leavevmode\nobreak\
\leq\leavevmode\nobreak$
$\displaystyle\mathbb{E}[1-\phi_{\mathrm{perm},N}]+\mathbb{P}(N>n)$ (26)
$\displaystyle\leq\leavevmode\nobreak$
$\displaystyle\mathbb{E}[1-\phi_{\mathrm{perm},N}]+e^{-n/8},$

where the second inequality uses an exponential Poisson tail bound (e.g.
Canonne,, 2017). Therefore, once we establish that the type II error of
$\phi_{\mathrm{perm},N}$ is small, it follows that the type II error of
$\phi_{\mathrm{perm},n}^{\dagger}$ is also small by taking $n$ large enough.

The next section formalizes it under $\gamma$-Hellinger Lipschitzness for
$2\leq\gamma$.

####  A.5.1 $\gamma$-Hellinger Lipschitzness for $2\leq\gamma$

Due to the inequality (26), it suffices to show that the type II error of
$\phi_{\mathrm{perm},N}$ for the hypothesis (13) is sufficiently small under
the given conditions. To proceed, let us denote the entire sample by
$\mathcal{W}_{N}=\\{(X_{i},Y_{i},Z_{i})\\}_{i=1}^{N}$ and denote the
expectation and the variance operator under the permutation law by
$\mathbb{E}_{\bm{\pi}}[\cdot|\bm{\sigma},\mathcal{W}_{N}]$ and
$\text{Var}_{\bm{\pi}}[\cdot|\bm{\sigma},\mathcal{W}_{N}]$ where we recall
$\bm{\sigma}=\\{\sigma_{1},\ldots,\sigma_{M}\\}$. First of all, we make an
observation that

$\displaystyle\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]=\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}\mathbb{E}_{\bm{\pi}}[U(\bm{W}_{m}^{\pi_{m}})|\bm{\sigma},\mathcal{W}_{N}]=0,$
(27)

where we use the fact that
$\mathbb{E}_{\bm{\pi}}[U(\bm{W}_{m}^{\pi_{m}})|\bm{\sigma},\mathcal{W}_{N}]=0$
when $\sigma_{m}\geq 4$ (see Appendix I of Kim et al.,, 2020). Thus a
modification of Lemma 3.1 of Kim et al., (2020) shows that if

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI}}]\geq\sqrt{\frac{2\text{Var}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI}}]}{\beta}}+\sqrt{\frac{2\mathbb{E}_{P_{X,Y,Z}^{N},N}\\{\text{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]\\}}{\alpha\beta}}$
(28)

holds then the power of $\phi_{\mathrm{perm},N}$ is lower bounded by
$1-\beta$. Therefore our goal is to prove the inequality (28) under the given
conditions.

In what follows, we suppress the dependence on $P_{X,Y,Z}^{N},N$ in the
expectation and the variance for notational convenience, and often write
$U(\bm{W}_{m})$ as $U_{m}$ if there is no confusion. The inequality (28) is
verified by showing that there exists
$P_{X,Y,Z}\in\mathcal{P}_{0,\mathrm{H},\gamma,\delta}(L)$ such that

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\gtrsim\leavevmode\nobreak\ nh_{n}^{4},$ (29a)
$\displaystyle\text{Var}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ \mathbb{E}[T_{\mathrm{CI}}]+1,$ (29b)
$\displaystyle\mathbb{E}\\{\text{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]\\}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ 1.$ (29c)

When these inequalities are fulfilled for large $n$, the condition (28) is
automatically satisfied since it is assumed that
$nh_{n}^{4}\rightarrow\infty$. Therefore our task boils down to confirming
(29a), (29b) and (29c).

Proof of the inequality (29a). Let us define $p_{i}=\mathbb{P}(Z\in B_{i})$
for $i=1,\ldots,M$. Since the expectation of $U_{m}$ is non-negative, the
expected value of $T_{\mathrm{CI}}$ can be lower bounded by

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\geq\leavevmode\nobreak\ $ $\displaystyle\mathbb{E}[\mathds{1}(\sigma_{1}\geq
4)\sigma_{1}U_{1}]$ (30)
$\displaystyle\overset{\text{(i)}}{\geq}\leavevmode\nobreak\ $
$\displaystyle(1-5e^{-1}/2)\min\\{np_{1},(np_{1})^{4}\\}\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2},$

where (i) makes use of Lemma 3.1 of Canonne et al., (2018) and the fact that
$\sigma_{1}\sim\text{Pois}(np_{1})$. We also use the observation that
$\mathbb{E}[U_{1}|\sigma_{1}]\mathds{1}(\sigma_{1}\geq
4)=\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}\mathds{1}(\sigma_{1}\geq 4)$. By our choice of
the density of $Z$ in (25), we have $p_{1}=1-M^{-1}_{n}\epsilon_{n}$ and we
set $\epsilon_{n}\leq 1/2$. In this case, $np_{1}\geq n/2$ and thus

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\gtrsim\leavevmode\nobreak\
n\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}.$ (31)

Therefore it is sufficient to construct $P_{X|Z}$ and $P_{Y|Z}$ that satisfy
(i) $P_{X|Z}P_{Y|Z}P_{Z}\in\mathcal{P}_{0,\mathrm{H},\gamma,\delta}(L)$ for
$\gamma\geq 2$ and (ii) the squared $L_{2}$ distance between the corresponding
$Q_{XY|\widetilde{Z}=1}$ and $Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}$ is lower bounded by

$\displaystyle\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}\gtrsim h_{n}^{4}.$ (32)

We construct such example below. For notational convenience, we often suppress
the dependence of $n$ in $h_{n}$ and $M_{n}$, and also write $h=M^{-1}$ as we
work on the equi-partition.

Example of the conditional distribution in
$\mathcal{P}_{0,H,\gamma,\delta}(L)$. Suppose $X$ and $Y$ are Bernoulli random
variables. Then the Lipschitz condition in Definition 3 can be equivalently
written as

$\displaystyle\big{|}p_{X|Z}^{1/\gamma}(x=1|z)-p_{X|Z}^{1/\gamma}(x=1|z^{\prime})\big{|}^{\gamma}+\big{|}p_{X|Z}^{1/\gamma}(x=0|z)-p_{X|Z}^{1/\gamma}(x=0|z^{\prime})\big{|}^{\gamma}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2L^{\gamma}|z-z^{\prime}|^{\gamma}.$

For any $M\geq 1$, the following probability mass functions are well-defined:

$\displaystyle
p_{X|Z}(x=1|z)=\begin{cases}\frac{1}{2}-\frac{1}{2M}+z,\quad&\text{for
$z\in[0,1/M]$,}\\\\[5.0pt] \frac{1}{2}+\frac{1}{2M},\quad&\text{for
$z\in(1/M,1]$,}\\\\[5.0pt] 0,\quad&\text{otherwise,}\end{cases}$ (33)
$\displaystyle
p_{X|Z}(x=0|z)=\begin{cases}\frac{1}{2}+\frac{1}{2M}-z,\quad&\text{for
$z\in[0,1/M]$,}\\\\[5.0pt] \frac{1}{2}-\frac{1}{2M},\quad&\text{for
$z\in(1/M,1]$,}\\\\[5.0pt] 0,\quad&\text{otherwise.}\end{cases}$

Figure 5: Illustration of $p_{X|Z}(x=1|z)$ and $p_{X|Z}(x=0|z)$ described in
(33) as a function of $z$.

See Figure 5 for an illustration. In addition, by taking $M$ large enough, we
see that both $p_{X|Z}(x=1|z)$ and $p_{X|Z}(x=0|z)$ are bounded below and also
above by, let’s say, $[1/4,3/4]$ for $z\in[0,1]$. Thus, using Taylor’s
theorem, one can verify that

$\displaystyle\big{|}p_{X|Z}^{1/\gamma}(x=1|z)-p_{X|Z}^{1/\gamma}(x=1|z^{\prime})\big{|}^{\gamma}+\big{|}p_{X|Z}^{1/\gamma}(x=0|z)-p_{X|Z}^{1/\gamma}(x=0|z^{\prime})\big{|}^{\gamma}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
C_{\gamma}|z-z^{\prime}|^{\gamma},$

for some constant $C_{\gamma}>0$. Thus it is seen that the distribution with
the probability mass function (33) satisfies Definition 3 with
$L^{\gamma}=C_{\gamma}/2$. Similarly we let $p_{Y|Z}(y=1|z)=p_{X|Z}(x=1|z)$
and thus $p_{Y|Z}(y|z)$ is also Lipschitz in $\gamma$-Hellinger distance.

Next we calculate $q_{XY|\widetilde{Z}}(x,y|m=1)$ and
$q_{X\cdot|\widetilde{Z}}(x|m=1)q_{\cdot Y|\widetilde{Z}}(y|m=1)$. To start
with $q_{XY|\widetilde{Z}}(x,y|m=1)$, recall that

$\displaystyle d\widetilde{P}_{Z|Z\in
B_{1}}(z)=\frac{dP_{Z}(z)}{\mathbb{P}(Z\in[0,h])}$

and also recall that $Z$ has the density in (25). Then since $h=M^{-1}$

$\displaystyle q_{XY|\widetilde{Z}}(x=1,y=1|m=1)=\leavevmode\nobreak\ $
$\displaystyle\int_{0}^{h}p_{X|Z}(x=1|z)p_{Y|Z}(y=1|z)d\widetilde{P}_{Z|Z\in
B_{1}}(z)$ $\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
h^{-1}\int_{0}^{h}p_{X|Z}(x=1|z)p_{Y|Z}(y=1|z)dz$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
h^{-1}\int_{0}^{h}\left(\frac{1}{2}-\frac{h}{2}+z\right)^{2}dz$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{h^{2}}{12}+\frac{1}{4}.$

Similarly,

$\displaystyle q_{X\cdot|\widetilde{Z}}(x=1|m=1)=q_{\cdot
Y|\widetilde{Z}}(y=1|m=1)=\int_{0}^{h}p_{X|Z}(x=1|z)d\widetilde{P}_{Z|Z\in
B_{1}}(z)=\frac{1}{2}.$

For the binary case, the squared $L_{2}$ distance simply becomes

$\displaystyle\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle
4|q_{XY|\widetilde{Z}}(x=1,y=1|m=1)-q_{X\cdot|\widetilde{Z}}(x=1|m=1)q_{\cdot
Y|\widetilde{Z}}(y=1|m=1)|^{2}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{h^{4}}{144}.$

Therefore the condition (32) is fulfilled and the inequality (29a) follows.

Proof of the inequality (29b). By modifying the proof of Theorem 5.2 in Neykov
et al., (2021), the variance of $T_{\mathrm{CI}}$ is upper bounded by

$\displaystyle\text{Var}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]+\mathbb{E}\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)$ $\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]+\sum_{m\in[M]}\mathbb{P}(\sigma_{m}\geq
1)$ $\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]+1-e^{-np_{1}}+\sum_{m=2}^{M}\bigl{(}1-e^{-np_{m}}\bigr{)},$
(34)

where we use the fact that $\sigma_{m}\sim\text{Pois}(np_{m})$, and $C$ is
some positive constant. Now by choosing $\epsilon_{n}>0$ in the density
function (25) such that

$\displaystyle\epsilon_{n}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{M(M-1)}{n}\log\left(\frac{M-1}{M-2}\right),$ (35)

the summation in (34) can be controlled as $\sum_{m=2}^{M}(1-e^{-np_{m}})\leq
1$. In more detail, for any $m\geq 2$, the binned probability $p_{m}$ is the
same as $\frac{\epsilon_{n}}{M(M-1)}$. Thus we have a series of equivalent
conditions as

$\displaystyle\sum_{m=2}^{M}\bigl{(}1-e^{-np_{m}}\bigr{)}\leq
1\leavevmode\nobreak\ \Longleftrightarrow\leavevmode\nobreak\ $
$\displaystyle(M-1)(1-e^{-\frac{n\epsilon_{n}}{M(M-1)}})\leq 1$
$\displaystyle\Longleftrightarrow\leavevmode\nobreak\ $
$\displaystyle\frac{M-2}{M-1}\leq e^{-\frac{n\epsilon_{n}}{M(M-1)}}$
$\displaystyle\Longleftrightarrow\leavevmode\nobreak\ $
$\displaystyle\epsilon_{n}\leq\frac{M(M-1)}{n}\log\left(\frac{M-1}{M-2}\right).$

With the choice of such $\epsilon_{n}$ in the density of $Z$ (25) (and also
let $\epsilon_{n}\leq 1/2$ from the previous step), the variance is upper
bounded by

$\displaystyle\text{Var}[T_{\mathrm{CI}}]\lesssim\mathbb{E}[T_{\mathrm{CI}}]+1.$

Therefore the inequality (29b) follows.

Proof of the inequality (29c). Let us denote $U(\bm{W}_{m}^{\pi_{m}})$ by
$U_{m}^{\pi_{m}}$ for simplicity. Then using the independence between
$\pi_{1},\ldots,\pi_{M}$, the conditional variance of
$T_{\mathrm{CI}}^{\bm{\pi}}$ is

$\displaystyle\text{Var}_{\bm{\pi}}\big{[}T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}\big{]}=\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\text{Var}_{\bm{\pi}}[U_{m}^{\pi_{m}}|\bm{\sigma},\mathcal{W}_{N}].$

Based on the result in Appendix J of Kim et al., (2020),

$\displaystyle\mathbb{E}\\{\text{Var}_{\bm{\pi}}[U_{m}^{\pi_{m}}|\bm{\sigma},\mathcal{W}_{N}]|\bm{\sigma}\\}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ $
$\displaystyle\sigma_{m}^{-2}\max\big{\\{}\|Q_{XY|\widetilde{Z}=m}\|_{2}^{2},\|Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}\|_{2}^{2}\big{\\}}$
$\displaystyle\lesssim\leavevmode\nobreak\ $ $\displaystyle\sigma_{m}^{-2},$

where the second inequality holds since $\|P\|_{2}^{2}\leq\|P\|_{1}^{2}=1$ for
a discrete probability distribution $P$. Therefore, with the choice of
$\epsilon_{n}$ as in (35),

$\displaystyle\mathbb{E}\\{\text{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]\\}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ \sum_{m\in[M]}\mathbb{P}(\sigma_{m}\geq
4)\leavevmode\nobreak\ \lesssim\leavevmode\nobreak\ 1,$

where the last inequality holds since $\sigma_{m}\sim\text{Pois}(np_{m})$ and

$\displaystyle\sum_{m\in[M]}\mathbb{P}(\sigma_{m}\geq
4)\leq\sum_{m\in[M]}\mathbb{P}(\sigma_{m}\geq 1)\leq
1+\sum_{m=2}^{M}\bigl{(}1-e^{-np_{m}}\bigr{)}\leq 2.$

This verifies the inequality (29c).

Indeed, our proof in this subsection goes through for the case where
$1\leq\gamma<2$ as well. However, the condition
$\sqrt{n}h_{n}^{2}\rightarrow\infty$ is not tight for this case, and we need a
more careful analysis detailed in the next subsection.

####  A.5.2 $\gamma$-Hellinger Lipschitzness for $1\leq\gamma<2$

The underlying idea of the proof of this result is the same as in the previous
section. That is, we want to show that the inequality (28) holds when
$\sqrt{n}h_{n}^{\gamma}\rightarrow\infty$ for some
$P_{X,Y,Z}\in\mathcal{P}_{0,\mathrm{H},\gamma,\delta}(L)$ with
$\gamma\in[1,2]$. However, we need to obtain a sharper bound for the variance
of the test statistic in order to achieve the desired rate, which requires
some nontrivial effort.

Suppose that $X$ and $Y$ are binary random variables taking a value between
$\\{0,1\\}$. We then set

$\displaystyle p_{X|Z}(x=1|z)=\begin{cases}z^{\gamma},\quad&\text{for
$z\in[0,2^{-1/\gamma}]$,}\\\\[5.0pt] 2^{-1},\quad&\text{for
$z\in[2^{-1/\gamma},1]$,}\\\\[5.0pt] 0,\quad&\text{otherwise.}\end{cases}$
(36) $\displaystyle p_{X|Z}(x=0|z)=\begin{cases}1-z^{\gamma},\quad&\text{for
$z\in[0,2^{-1/\gamma}]$,}\\\\[5.0pt] 2^{-1},\quad&\text{for
$z\in[2^{-1/\gamma},1]$,}\\\\[5.0pt] 0,\quad&\text{otherwise.}\end{cases}$

Similarly, we let $p_{X|Z}(x=1|z)=p_{Y|Z}(y=1|z)$ and
$p_{X|Z}(x=0|z)=p_{Y|Z}(y=0|z)$. It can be checked that $P_{X|Z}$ and
$P_{Y|Z}$ with the above probability mass functions are $\gamma$-Hellinger
smooth for $\gamma\geq 1$ using Taylor’s theorem. Here we note that the
Lipschitz constant depends on $\gamma$ and is assumed to be fixed. Also note
that this example is more sophisticated than the one in (33). For instance,
when $\gamma=1$, the distribution
(LABEL:Eq:_conditional_densities_under_gamma_hellinger) is TV smooth but not
smooth in the Hellinger distance (since $\sqrt{x}$ is not a Lipschitz
function). In addition to the condition on the conditional distributions
(LABEL:Eq:_conditional_densities_under_gamma_hellinger), we let $Z$ have the
marginal density as in (25) with a sufficiently small $0<\epsilon_{n}\leq 1/2$
(specified later).

Under this setting, we will show that the mean, the variance and the expected
conditional variance of the test statistic $T_{\mathrm{CI}}$ are bounded by

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\gtrsim\leavevmode\nobreak\ nh_{n}^{4\gamma},$ (37a)
$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\
\mathbb{E}[T_{\mathrm{CI}}]h_{n}^{2\gamma}+h_{n}^{4\gamma},$ (37b)
$\displaystyle\mathbb{E}\big{\\{}\mathrm{Var}_{\bm{\pi}}\big{[}T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]\big{]}\big{\\}}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ h_{n}^{4\gamma}.$ (37c)

If this is the case, then the inequality (28) holds as
$\sqrt{n}h_{n}^{\gamma}\rightarrow\infty$, which completes the proof. In what
follows, we prove these inequalities in order.

Proof of the inequality (37a). As we define the density of $Z$ to be (25) with
$\epsilon_{n}\leq 1/2$, the inequality (31) follows in this case as well, that
is

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]\leavevmode\nobreak\
\gtrsim\leavevmode\nobreak\
n\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}.$ (38)

Therefore it is enough to show that
$\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}\gtrsim h^{4\gamma}$. Then the inequality (37a)
follows. In fact, when $h\leq 1/2$,

$\displaystyle q_{XY|\widetilde{Z}}(x=1,y=1|m=1)\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\int_{0}^{h}p_{X|Z}(x=1|z)p_{Y|Z}(y=1|z)d\widetilde{P}_{Z|Z\in
B_{1}}(z)$ $\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
h^{-1}\int_{0}^{h}p_{X|Z}(x=1|z)p_{Y|Z}(y=1|z)dz$
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
h^{-1}\int_{0}^{h}z^{2\gamma}dz=\frac{h^{2\gamma}}{2\gamma+1}.$

Similarly,

$\displaystyle q_{X\cdot|\widetilde{Z}}(x=1|m=1)=q_{\cdot
Y|\widetilde{Z}}(y=1|m=1)=\int_{0}^{h}p_{X|Z}(x=1|z)d\widetilde{P}_{Z|Z\in
B_{1}}(z)=\frac{h^{\gamma}}{\gamma+1}.$

When $X$ and $Y$ are binary, the squared $L_{2}$ norm simply becomes

$\displaystyle\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle
4\big{\\{}q_{XY|\widetilde{Z}}(x=1,y=1|m=1)-q_{X\cdot|\widetilde{Z}}(x=1|m=1)q_{\cdot
Y|\widetilde{Z}}(y=1|m=1)\big{\\}}^{2}$ (39)
$\displaystyle=\leavevmode\nobreak\ $ $\displaystyle
4h^{4\gamma}\left(\frac{1}{2\gamma+1}-\frac{1}{(\gamma+1)^{2}}\right)^{2},$

which concludes the inequality (37a).

Proof of the inequality (37b). Bounding the variance requires a bit more work.
First the law of total variance yields

$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}]=\mathbb{E}\\{\mathrm{Var}[T_{\mathrm{CI}}|\bm{\sigma}]\\}+\mathrm{Var}\\{\mathbb{E}[T_{\mathrm{CI}}|\bm{\sigma}]\\}.$
(40)

To start with the first term, we use the independence between different bins
conditional on $\bm{\sigma}$ and see

$\displaystyle\mathbb{E}\\{\mathrm{Var}[T_{\mathrm{CI}}|\bm{\sigma}]\\}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathbb{E}\\{\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\mathrm{Var}[U_{m}|\bm{\sigma}]\\}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}\\{\mathds{1}(\sigma_{1}\geq
4)\sigma_{1}^{2}\mathrm{Var}[U_{1}|\sigma_{1}]\\}+\sum_{m=2}^{M}\mathbb{E}[\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}],$

where the second inequality uses $|U_{m}|\leq 1$. Since we have freedom to
choose $\epsilon$ in the density of $Z$, we can make the second term smaller
than

$\displaystyle\sum_{m=2}^{M}\mathbb{E}[\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}]\leavevmode\nobreak\ \lesssim\leavevmode\nobreak\
h^{4\gamma}.$ (41)

For example, since $\sigma_{m}\sim\text{Pois}(np_{m})$ where
$p_{m}=\frac{\epsilon}{M(M-1)}$ for $m=2,\ldots,M$, applying Cauchy–Schwarz
inequality yields

$\displaystyle\sum_{m=2}^{M}\mathbb{E}[\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}]\leavevmode\nobreak\ \lesssim\leavevmode\nobreak\ $
$\displaystyle M\sqrt{\mathbb{P}(\sigma_{2}\geq 4)\mathbb{E}[\sigma_{2}^{4}]}$
$\displaystyle\lesssim\leavevmode\nobreak\ $ $\displaystyle
M\sqrt{1-e^{-np_{2}}},$

where the second inequality follows since $\mathbb{P}(\sigma_{2}\geq
4)\leq\mathbb{P}(\sigma_{2}\geq 1)=1-e^{-np_{2}}$ and
$\mathbb{E}[\sigma_{2}^{4}]=np_{2}(1+7np_{2}+6n^{2}p_{2}^{2}+n^{3}p_{2}^{3})\leq
15$ by assuming $np_{2}\leq 1$, which is satisfied when $\epsilon\lesssim
1/(nh^{2})$. Therefore, the inequality (41) holds, for instance, when

$\displaystyle\epsilon\leavevmode\nobreak\ \lesssim\leavevmode\nobreak\
\frac{1}{nh^{2}}\log\left(\frac{1}{1-h^{4\gamma+1}}\right).$

Next we analyze $\mathbb{E}\\{\mathds{1}(\sigma_{1}\geq
4)\sigma_{1}^{2}\mathrm{Var}[U_{1}|\sigma_{1}]\\}$. Intuitively the
conditional variance of $U_{1}|\sigma_{1}$ becomes smaller for large $M$
(equivalently small $h$) under our distributional setting
(LABEL:Eq:_conditional_densities_under_gamma_hellinger). In particular,
observe that $q_{XY|\widetilde{Z}}(x=0,y=0|m=1)\rightarrow 1$ and thus
$(X,Y)|Z\in B_{1}$ becomes degenerate at $X=0,Y=0$ as $M$ increases. However
the bound for $\mathrm{Var}[U_{1}|\sigma_{1}]$ given in Lemma 5.1 of Neykov et
al., (2021) (and also see the proof of Proposition 5.3 in Kim et al.,, 2020):

$\displaystyle\mathrm{Var}[U_{1}|\sigma_{1}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ $
$\displaystyle\frac{\mathbb{E}[U_{1}|\sigma_{1}]\max\big{\\{}\|Q_{XY|\widetilde{Z}=1}\|_{2},\|Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}\big{\\}}}{\sigma_{1}}$
$\displaystyle+\leavevmode\nobreak\ $
$\displaystyle\frac{\max\big{\\{}\|Q_{XY|\widetilde{Z}=1}\|_{2}^{2},\|Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{2}\big{\\}}}{\sigma_{1}^{2}}\quad\text{for
$\sigma_{1}\geq 4$,}$

does not capture this intuition. It turns out that this variance bound is not
tight for the binary case. In fact, we can obtain a sharper bound as

$\displaystyle\mathrm{Var}[U_{1}|\sigma_{1}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak$
$\displaystyle\frac{\mathbb{E}[U_{1}|\sigma_{1}]\max\big{\\{}q_{XY|\widetilde{Z}}(1,1|1),q_{X\cdot|\widetilde{Z}}(1|1)q_{\cdot
Y|\widetilde{Z}}(1|1)\big{\\}}}{\sigma_{1}}$ (42)
$\displaystyle+\leavevmode\nobreak$
$\displaystyle\frac{\max\big{\\{}q_{XY|\widetilde{Z}}^{2}(1,1|1),q_{X\cdot|\widetilde{Z}}^{2}(1|1)q_{\cdot
Y|\widetilde{Z}}^{2}(1|1)\big{\\}}}{\sigma_{1}^{2}}\quad\text{for
$\sigma_{1}\geq 4$,}$

where $q_{XY|\widetilde{Z}}(1,1|1)=q_{XY|\widetilde{Z}}(x=1,y=1|m=1)$ and the
other quantities are similarly defined. We will prove this inequality at the
end of this section. Therefore, using the previous calculations of
$q_{XY|\widetilde{Z}}$, $q_{X\cdot|\widetilde{Z}}$ and $q_{\cdot
Y|\widetilde{Z}}$, the (conditional) variance is bounded by

$\displaystyle\mathrm{Var}[U_{1}|\sigma_{1}]\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\
\frac{\mathbb{E}[U_{1}|\sigma_{1}]h^{2\gamma}}{\sigma_{1}}+\frac{h^{4\gamma}}{\sigma_{1}^{2}}\quad\text{for
$\sigma_{1}\geq 4$}.$ (43)

In summary, we have

$\displaystyle\mathbb{E}\\{\mathrm{Var}[T_{\mathrm{CI}}|\bm{\sigma}]\\}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak$
$\displaystyle\mathbb{E}\\{\mathds{1}(\sigma_{1}\geq
4)\sigma_{1}\mathbb{E}[U_{1}|\sigma_{1}]\\}h^{2\gamma}+h^{4\gamma}$ (44)
$\displaystyle\lesssim\leavevmode\nobreak$
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]h^{2\gamma}+h^{4\gamma}.$

Next we focus on the second term
$\mathrm{Var}\\{\mathbb{E}[T_{\mathrm{CI}}|\bm{\sigma}]\\}$ in (40) and see

$\displaystyle\mathrm{Var}\\{\mathbb{E}[T_{\mathrm{CI}}|\bm{\sigma}]\\}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathrm{Var}[\sigma_{m}\mathds{1}(\sigma_{m}\geq
4)]\times\|Q_{XY|\widetilde{Z}=m}-Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}\|_{2}^{4}$
$\displaystyle\overset{\text{(i)}}{\lesssim}\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathbb{E}[\sigma_{m}\mathds{1}(\sigma_{m}\geq
4)]\times\|Q_{XY|\widetilde{Z}=m}-Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}\|_{2}^{4}$
$\displaystyle\overset{\text{(ii)}}{\lesssim}\leavevmode\nobreak\ $
$\displaystyle
np_{1}\times\big{|}q_{X,Y|\widetilde{Z}}(1,1|1)-q_{X\cdot|\widetilde{Z}}(1|1)q_{\cdot
Y|\widetilde{Z}}(1|1)\big{|}^{4}+h^{4\gamma}$
$\displaystyle\overset{\text{(iii)}}{\lesssim}\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}]h^{2\gamma}+h^{4\gamma},$

where step (i) uses Claim 2.1 of Canonne et al., (2018), step (ii) can be
deduced by the inequality (41) and the identity (39). To give a more detail on
step (ii), consider a decomposition

$\displaystyle\sum_{m\in[M]}\mathbb{E}[\sigma_{m}\mathds{1}(\sigma_{m}\geq
4)]\times\|Q_{XY|\widetilde{Z}=m}-Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}\|_{2}^{4}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\underbrace{\mathbb{E}[\sigma_{1}\mathds{1}(\sigma_{1}\geq
4)]\times\|Q_{XY|\widetilde{Z}=1}-Q_{X\cdot|\widetilde{Z}=1}Q_{\cdot
Y|\widetilde{Z}=1}\|_{2}^{4}}_{\mathrm{(I)}}$
$\displaystyle+\underbrace{\sum_{m=2}^{M}\mathbb{E}[\sigma_{m}\mathds{1}(\sigma_{m}\geq
4)]\times\|Q_{XY|\widetilde{Z}=m}-Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}\|_{2}^{4}}_{\mathrm{(II)}}.$

For the first term (I), we make use of the identity (39) and
$\mathbb{E}[\sigma_{1}]=np_{1}$, which yields $\mathrm{(I)}\lesssim
np_{1}\times\big{|}q_{X,Y|\widetilde{Z}}(1,1|1)-q_{X\cdot|\widetilde{Z}}(1|1)q_{\cdot
Y|\widetilde{Z}}(1|1)\big{|}^{4}$. For the second term, note that the $L_{2}$
norm of $Q_{XY|\widetilde{Z}=m}-Q_{X\cdot|\widetilde{Z}=m}Q_{\cdot
Y|\widetilde{Z}=m}$ is bounded by two for any $m$. Therefore,
$\mathrm{(II)}\lesssim\sum_{m=2}^{M}\mathbb{E}[\sigma_{m}^{2}\mathds{1}(\sigma_{m}\geq
4)]\lesssim h^{4\gamma}$ by the inequality (41). This explains step (ii). Step
(iii) follows by using the lower bound for $\mathbb{E}[T_{\mathrm{CI}}]$ in
(38) and the observation that
$|q_{XY|\widetilde{Z}}(1,1|1)-q_{X\cdot|\widetilde{Z}}(1|1)q_{\cdot
Y|\widetilde{Z}}(1|1)|^{2}\lesssim h^{4\gamma}\leq h^{2\gamma}$. Combining
this with (44) yields the claim (37b). The last step is to verify the sharper
bound (42).

Verification of the bound (42). Recall that the kernel of $U_{1}$ is

$\displaystyle
h_{i_{1},i_{2},i_{3},i_{4}}=\frac{1}{4!}\sum_{\pi\in\bm{\Pi}_{4}}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\psi_{\pi(1)\pi(2)}(x,y)\psi_{\pi(3)\pi(4)}(x,y),$

where $\bm{\Pi}_{4}$ is the set of all permutations of
$\\{i_{1},i_{2},i_{3},i_{4}\\}$ and

$\displaystyle\psi_{ij}(x,y)=\mathds{1}(X_{i,1}=x,Y_{i,1}=y)-\mathds{1}(X_{i,1}=x)\mathds{1}(Y_{j,1}=y).$

Importantly, for the binary case, we observe that

$\displaystyle
h_{i_{1},i_{2},i_{3},i_{4}}=g_{i_{1},i_{2},i_{3},i_{4}}:=\frac{4}{4!}\sum_{\pi\in\bm{\Pi}_{4}}\psi_{\pi(1)\pi(2)}(1,1)\psi_{\pi(3)\pi(4)}(1,1).$
(45)

This means that $U_{1}$ is the same as another U-statistic defined with the
kernel $g_{i_{1},i_{2},i_{3},i_{4}}$. Having this observation, we work with
the U-statistic associated with $g_{i_{1},i_{2},i_{3},i_{4}}$. We then follow
basically the same lines of the proofs in Neykov et al., (2021) and Appendix J
of Kim et al., (2020) and see that the bound (42) is satisfied (more
specifically, follow the same lines of the proof in Appendix J of Kim et al.,
(2020) by setting $d_{1}=d_{2}=1$).

Proof of the inequality (37c). Similar to the proof of (29c), we can obtain

$\displaystyle\mathrm{Var}_{\bm{\pi}}\big{[}T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}\big{]}\leavevmode\nobreak\
=\leavevmode\nobreak\ $ $\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\mathrm{Var}_{\bm{\pi}}[U_{m}^{\pi_{m}}|\bm{\sigma},\mathcal{W}_{N}]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathds{1}(\sigma_{1}\geq
4)\sigma_{1}^{2}\mathrm{Var}_{\bm{\pi}}[U_{1}^{\pi_{1}}|\bm{\sigma},\mathcal{W}_{N}]+\sum_{m=2}^{M}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2},$

where the second inequality follows by $|U_{m}^{\pi_{m}}|\leq 1$. By taking
the expectation, the second term can be smaller than $h^{4\gamma}$ by the
condition (41). On the other hand, recall that for the binary case, $U_{1}$ is
equivalent to the U-statistic based on the kernel
$g_{i_{1},i_{2},i_{3},i_{4}}$ in (45). Thus, based on the results in Appendix
I and Appendix J of Kim et al., (2020) (more specifically by letting
$d_{1}=d_{2}=1$ therein),

$\displaystyle\mathbb{E}\\{\mathrm{Var}_{\bm{\pi}}[U_{1}^{\pi_{1}}|\bm{\sigma},\mathcal{W}_{N}]|\bm{\sigma}\\}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ $
$\displaystyle\sigma_{1}^{-2}\max\big{\\{}q_{XY|\widetilde{Z}}^{2}(1,1|1),q_{X\cdot|\widetilde{Z}}^{2}(1|1)q_{\cdot
Y|\widetilde{Z}}^{2}(1|1)\big{\\}}$ $\displaystyle\lesssim\leavevmode\nobreak\
$ $\displaystyle\sigma_{1}^{-2}h^{4\gamma}.$

Consequently, we obtain the desired bound
$\mathbb{E}\big{\\{}\mathrm{Var}_{\bm{\pi}}\big{[}T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma},\mathcal{W}_{N}]\big{]}\big{\\}}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ h_{n}^{4\gamma}$.

####  A.5.3 $\gamma$-Rényi Lipschitzness for $0<\gamma$

The proof of this part is essentially the same as that in the case of
$\gamma$-Hellinger Lipschitzness for $2\leq\gamma$ (Appendix A.5.1). In
particular, we consider the distribution setting in (33) and show that the
considered distribution is Rényi smooth for all $\gamma>0$. Once this is
established, the other parts of the proof follow exactly the same lines of the
proof as before in Appendix A.5.1.

Note that, for a sufficiently large $M$, $p_{X|Z}(x=1|z)$ and $p_{X|Z}(x=0|z)$
are bounded below and above by constants for any $z\in[0,1]$, say,

$\displaystyle p_{X|Z}(x=1|z)\in[1/4,3/4]\quad\text{and}\quad
p_{X|Z}(x=0|z)\in[1/4,3/4].$ (46)

Therefore, when $0<\gamma\leq 2$, there exist some constants $C_{1},C_{2}>0$
such that

$\displaystyle\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})\leavevmode\nobreak\
\overset{\text{(i)}}{\leq}\leavevmode\nobreak\ $
$\displaystyle\mathcal{D}_{\chi^{2}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})$
$\displaystyle\overset{\text{(ii)}}{\leq}\leavevmode\nobreak\ $ $\displaystyle
C_{1}\|P_{X|Z=z}-P_{X|Z=z^{\prime}}\|_{2}^{2}$
$\displaystyle\overset{\text{(iii)}}{\leq}\leavevmode\nobreak\ $
$\displaystyle C_{2}|z-z^{\prime}|^{2},$

where step (i) uses the fact that Rényi divergence is nondecreasing in
$\gamma$ (e.g. Theorem 3 of Van Erven and Harremos,, 2014) and the inequality
(74). Additionally, step (ii) holds since we set $P_{X|Z=z^{\prime}}$ is lower
bounded by some constant and step (iii) follows directly by the construction
of $P_{X|Z=z}$ in (33). Similarly we let $P_{Y|Z=z}=P_{X|Z=z}$ and thus both
$P_{X|Z=z}$ and $P_{Y|Z=z}$ are Rényi smooth when $0<\gamma\leq 2$.

We now consider the case where $\gamma>2$. Again, we make use of the
distribution given in (33) and assume that $p_{X|Z}(x=1|z)$ and
$p_{X|Z}(x=0|z)$ are bounded below and above by constants for any $z\in[0,1]$
as in (46). Since $X$ takes a binary value, Rényi divergence of $P_{X|Z=z}$
from $P_{X|Z=z^{\prime}}$ simply becomes

$\displaystyle\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\gamma-1}\log\biggl{\\{}\biggl{(}\frac{p_{X|Z}(x=1|z)}{p_{X|Z}(x=1|z^{\prime})}\biggr{)}^{\gamma}p_{X|Z}(x=1|z^{\prime})+\biggl{(}\frac{p_{X|Z}(x=0|z)}{p_{X|Z}(x=0|z^{\prime})}\biggr{)}^{\gamma}p_{X|Z}(x=0|z^{\prime})\biggr{\\}}.$

When both $z,z^{\prime}\in(1/M,1]$, Rényi divergence becomes zero and hence
there is nothing to prove. Next assume that both $z,z^{\prime}\in[0,1/M]$. In
this case, Rényi divergence can be written more explicitly as

$\displaystyle\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\gamma-1}\log\biggl{\\{}\biggl{(}\frac{\frac{1}{2}-\frac{1}{2M}+z}{\frac{1}{2}-\frac{1}{2M}+z^{\prime}}\biggr{)}^{\gamma}\biggl{(}\frac{1}{2}-\frac{1}{2M}+z^{\prime}\biggr{)}+\biggl{(}\frac{\frac{1}{2}+\frac{1}{2M}-z}{\frac{1}{2}+\frac{1}{2M}-z^{\prime}}\biggr{)}^{\gamma}\biggl{(}\frac{1}{2}+\frac{1}{2M}-z^{\prime}\biggr{)}\biggr{\\}}$
$\displaystyle:=\leavevmode\nobreak\ $ $\displaystyle f(z).$

By viewing the above expression as a function of $z$, Taylor’s theorem yields
that there exists $\xi\in(0,1/M)$ such that

$\displaystyle
f(z)=f(z^{\prime})+f^{\prime}(z^{\prime})(z-z^{\prime})+f^{\prime\prime}(\xi)(z-z^{\prime})^{2}.$

The first term $f(z^{\prime})$ is zero. We also note that the first derivative
satisfies $f^{\prime}(z^{\prime})=0$ since

$\displaystyle
f^{\prime}(z)=\frac{1}{\gamma-1}\times\frac{\gamma\biggl{(}\frac{\frac{1}{2}-\frac{1}{2M}+z}{\frac{1}{2}-\frac{1}{2M}+z^{\prime}}\biggr{)}^{\gamma-1}-\gamma\biggl{(}\frac{\frac{1}{2}+\frac{1}{2M}-z}{\frac{1}{2}+\frac{1}{2M}-z^{\prime}}\biggr{)}^{\gamma-1}}{\biggl{(}\frac{\frac{1}{2}-\frac{1}{2M}+z}{\frac{1}{2}-\frac{1}{2M}+z^{\prime}}\biggr{)}^{\gamma}\biggl{(}\frac{1}{2}-\frac{1}{2M}+z^{\prime}\biggr{)}+\biggl{(}\frac{\frac{1}{2}+\frac{1}{2M}-z}{\frac{1}{2}+\frac{1}{2M}-z^{\prime}}\biggr{)}^{\gamma}\biggl{(}\frac{1}{2}+\frac{1}{2M}-z^{\prime}\biggr{)}}.$

Furthermore, it can be seen that $\sup_{z\in[0,1/M]}|f^{\prime\prime}(z)|\leq
C_{\gamma,M}$ where $C_{\gamma,M}$ is a positive constant depending only on
$\gamma$ and $M$. This shows that
$\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})\leq
C_{\gamma,M}(z-z^{\prime})^{2}$ for all $z,z^{\prime}\in[0,1/M]$. Suppose now
that $z\in[0,1/M]$ and $z^{\prime}\in(1/M,1]$. In this case, since
$p_{X|Z}(x=1|z^{\prime})=p_{X|Z}(x=z|1/M)$ and
$p_{X|Z}(x=0|z^{\prime})=p_{X|Z}(x=0|1/M)$ for all $z^{\prime}\in(1/M,1]$, the
previous result implies that
$\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})\leq
C_{\gamma,M}(z-1/M)^{2}\leq C_{\gamma,M}(z-z^{\prime})^{2}$. The final case
where $z\in(1/M,1]$ and $z^{\prime}\in[0,1/M]$ can be similarly handled, which
concludes that
$\mathcal{D}_{\gamma\text{,\emph{R}}}(P_{X|Z=z}\|P_{X|Z=z^{\prime}})\leq
C_{\gamma,M}(z-z^{\prime})^{2}$ for all $z,z^{\prime}\in[0,1]$. Hence, by
letting $P_{Y|Z=z}=P_{X|Z=z}$, both $P_{X|Z=z}$ and $P_{Y|Z=z}$ are Rényi
smooth for $\gamma\geq 2$.

In summary, the distribution in (33) is Rényi smooth for $\gamma>0$ with a
different Lipschitz constant and therefore the result
$\sup_{P_{X,Y,Z}\in\mathcal{P}_{0,\text{\emph{R}},\gamma,\delta}(L)}\mathbb{E}_{P_{X,Y,Z}^{N},N}[\phi_{\text{{perm}},n}^{\dagger}]\geq
1-\beta$ follows.

###  A.6 Proof of Theorem 5

We start by proving the type II error bound for $\phi_{\mathrm{perm},2}$ and
then turn to $\phi_{\mathrm{perm},1}$.

$\bullet$ Type II error of $\phi_{\mathrm{perm},2}$. We note that by Lemma 6,
the type II error of $\phi_{\mathrm{perm},2}$ can be expressed as

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{N},N}[1-\phi_{\mathrm{perm},2}]=\mathbb{P}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI},W}\leq
q_{1-\alpha}],$

where $q_{1-\alpha}$ is the $1-\alpha$ quantile of the empirical distribution
of $T_{\mathrm{CI},W}^{\bm{\pi}_{1}},\ldots,T_{\mathrm{CI},W}^{\bm{\pi}_{K}}$.
Therefore, it is enough to work with the test that rejects the null when
$T_{\mathrm{CI},W}>q_{1-\alpha}$. For simplicity, we use the notation
$\bm{\mathcal{W}}_{\mathrm{weight}}:=\\{\bm{W}_{X,m},\bm{W}_{Y,m}\\}_{m\in[M]}$
to denote samples used for weights. Given this notation, we first claim that

$\displaystyle\mathbb{P}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI},W}\leq
q_{1-\alpha}]$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}_{P_{X,Y,Z}^{N},N}\Big{\\{}T_{\mathrm{CI},W}<\zeta\sqrt{\min\\{n,M\\}+\mathbb{E}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\Big{\\}}+\frac{1}{200},$
(47)

where $\zeta$ is a sufficiently large constant as in the critical value of the
test in Canonne et al., (2018). We then show that under the given condition,

$\displaystyle\mathbb{P}_{P_{X,Y,Z}^{N},N}\Big{\\{}T_{\mathrm{CI},W}<\zeta\sqrt{\min\\{n,M\\}+\mathbb{E}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\Big{\\}}\leq\frac{1}{200},$
(48)

which establishes the desired result. To ease the notation, we suppress
dependence on $P_{X,Y,Z}^{N}$ and $N$ in the expectation and probability
function, throughout this proof.

1\. Proof of the first claim (47). To show the first claim (47), let us define
an event

$\displaystyle\mathcal{A}:=\\{q_{1-\alpha}\leq\zeta\sqrt{\min(n,M)+\mathbb{E}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\\},$

and show that

$\displaystyle\mathbb{P}(\mathcal{A})\geq\frac{199}{200}.$ (49)

If this is the case, then the first claim (47) follows by the union bound. To
begin, let us simply denote the permutation distribution of
$T_{\mathrm{CI},W}^{\bm{\pi}}$ by

$\displaystyle\mathbb{P}_{\bm{\pi}}\big{[}T_{\mathrm{CI},W}^{\bm{\pi}}\leq
t\big{]}=\frac{1}{K}\sum_{\bm{\pi}_{i}\in\bm{\Pi}}\mathds{1}\big{[}T_{\mathrm{CI},W}^{\bm{\pi}_{i}}\leq
t\big{]}.$

More generally, we let $\mathbb{P}_{\bm{\pi}}[\cdot]$ be the probability
measure in terms of $\bm{\pi}$ uniformly distributed over $\bm{\Pi}$
conditional on everything else. We denote the expectation and the variance
operator under the permutation law by $\mathbb{E}_{\bm{\pi}}[\cdot]$ and
$\mathrm{Var}_{\bm{\pi}}[\cdot]$ for simplicity. As in the case of (27) for
$T_{\mathrm{CI}}^{\bm{\pi}}$, we make an observation that
$T_{\mathrm{CI},W}^{\bm{\pi}}$ is centered under the permutation law, i.e.

$\displaystyle\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI},W}^{\bm{\pi}}]=\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}\omega_{m}\mathbb{E}_{\bm{\pi}}[U_{W}(\bm{W}_{m}^{\pi_{m}})]=0,$

which can be shown using the result in Appendix I of Kim et al., (2020).
Therefore, for any $t>0$, Chebyshev’s inequality yields

$\displaystyle\mathbb{P}_{\bm{\pi}}\big{\\{}T_{\mathrm{CI},W}^{\bm{\pi}}\geq
t\big{\\}}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{1}{t^{2}}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}.$

Then, by the definition of the $1-\alpha$ quantile, it holds that
$q_{1-\alpha}\leq\sqrt{\alpha^{-1}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}}$
with probability one. Notice that
$\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}$ is a
non-negative random variable, changing its value depending on
$\\{\bm{W}_{X,m},\bm{W}_{Y,m},\bm{W}_{XY,m}\\}_{m=1}^{M}$. Then Markov’s
inequality verifies that the following inequality

$\displaystyle\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}<400\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{\\}}$

holds with probability at least $1-1/400$. Based on the results of Canonne et
al., (2018), Neykov et al., (2021) and Kim et al., (2020), we further prove
below that

$\displaystyle
400\alpha^{-1}\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{\\}}\leq\zeta^{1/2}\big{(}\min\\{n,M\\}+\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]\big{)},$
(50)

with probability at least $1-1/400$ by taking $\zeta$ sufficiently large
(depending on $\alpha$, but recall that $\alpha$ is assumed to be a fixed
constant). This verifies the probability bound (49) for $\mathcal{A}$,
completing the proof of the first claim (47).

Detail of the inequality (50). First of all, since $\pi_{1},\ldots,\pi_{M}$
are independent, it can be verified that

$\displaystyle\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}=\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\omega_{m}^{2}\mathbb{E}_{\bm{\pi}}\big{[}U_{W}^{2}(\bm{W}_{m}^{\pi_{m}})\big{]}.$
(51)

In order to analyze the expectation of
$\mathbb{E}_{\bm{\pi}}\big{[}U_{W}^{2}(\bm{W}_{m}^{\pi_{m}})\big{]}$, we need
some preliminary results. To this end, for $m=1,\ldots,M$, let

$\displaystyle
g_{X,m}(x_{1},x_{2}):=\sum_{x\in[\ell_{1}]}\frac{\mathds{1}(x_{1}=x)\mathds{1}(x_{2}=x)}{1+a_{x,m}}\quad\text{and}$
$\displaystyle
g_{Y,m}(y_{1},y_{2}):=\sum_{y\in[\ell_{2}]}\frac{\mathds{1}(y_{1}=y)\mathds{1}(y_{2}=y)}{1+a_{y,m}},$

and for $p:[\ell_{1}]\times[\ell_{2}]\mapsto\mathbb{R}$, denote

$\displaystyle\|p\|_{2,\bm{a}_{m}}^{2}:=\sum_{x\in[\ell_{1}]}\sum_{y\in[\ell_{2}]}\frac{p^{2}(x,y)}{(1+a_{x,m})(1+a_{y,m})}.$

Since $a_{x,m},a_{y,m}\geq 0$, the above bivariate functions are non-negative
and bounded by one. Therefore

$\displaystyle\mathbb{E}[g_{X,m}^{2}(X_{1,m},X_{2,m})g_{Y,m}^{2}(Y_{1,m},Y_{2,m})|\bm{W}_{X,m},\bm{W}_{Y,m}]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[g_{X,m}(X_{1,m},X_{2,m})g_{Y,m}(Y_{1,m},Y_{2,m})|\bm{W}_{X,m},\bm{W}_{Y,m}]\leavevmode\nobreak\
=\leavevmode\nobreak\ \|P_{XY|Z=m}\|_{2,\bm{a}_{m}}^{2}.$

Similar calculations show

$\displaystyle\mathbb{E}[g_{X,m}^{2}(X_{1,m},X_{2,m})g_{Y,m}^{2}(Y_{3,m},Y_{4,m})|\bm{W}_{X,m},\bm{W}_{Y,m}]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}$

and

$\displaystyle\mathbb{E}[g_{X,m}^{2}(X_{1,m},X_{2,m})g_{Y,m}^{2}(Y_{1,m},Y_{3,m})|\bm{W}_{X,m},\bm{W}_{Y,m}]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{2}\|P_{XY|Z=m}\|_{2,\bm{a}_{m}}^{2}+\frac{1}{2}\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2},$

where the last inequality uses the inequality
$xy\leq\frac{1}{2}x^{2}+\frac{1}{2}y^{2}$. In addition, using the triangle
inequality, we have

$\displaystyle\|P_{XY|Z=m}\|_{2,\bm{a}_{m}}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
2\|P_{X,Y|m}-P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}+2\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}.$

Since we consider half-permutation method (Remark 6) for $T_{\mathrm{CI},W}$,
we can apply the bound for the expected variance of a permuted U-statistic in
Kim et al., (2020) to $U_{W}^{2}(\bm{W}_{m}^{\pi_{m}})$. More specifically, by
the argument made in Appendix I of Kim et al., (2020) along with the above
results, we have

$\displaystyle\mathds{1}(\sigma_{m}\geq
4)\mathbb{E}\big{[}\mathbb{E}_{\bm{\pi}}\big{[}U_{W}^{2}(\bm{W}_{m}^{\pi_{m}})\big{]}|\bm{W}_{X,m},\bm{W}_{Y,m},\sigma_{m}\big{]}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{-2}\max\big{\\{}\|P_{XY|Z=m}\|_{2,\bm{a}_{m}}^{2},\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}\big{\\}}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{-2}\big{\\{}\|P_{X,Y|m}-P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}+\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}\big{\\}}.$

This result together with (51) leads to the following bound

$\displaystyle\mathbb{E}\Big{[}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI},W}^{\bm{\pi}})^{2}\big{]}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}\Big{]}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ \big{\\{}(\mathrm{I})+(\mathrm{II})\big{\\}},$

where

$\displaystyle(\mathrm{I})\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\omega_{m}^{2}\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2},$
$\displaystyle(\mathrm{II})\leavevmode\nobreak\ :=\leavevmode\nobreak\
\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\omega_{m}^{2}\|P_{X,Y|m}-P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}.$

To simplify the first term, the result of Canonne et al., (2018) and Neykov et
al., (2021) yields

$\displaystyle\mathbb{E}[\|P_{X|Z=m}P_{Y|Z=m}\|_{2,\bm{a}_{m}}^{2}]\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{1}{(1+t_{1,m})(1+t_{2,m})},$

which further shows that

$\displaystyle\mathbb{E}\big{[}(\mathrm{I})|\bm{\sigma}\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\frac{\omega_{m}^{2}}{(1+t_{1,m})(1+t_{2,m})}\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\ \min\\{N,M\\}.$

Recall that $N\sim\text{Pois}(n)$, which highly concentrates around its mean.
Thus, by Markov’s inequality as well as the union bound, one can have
$(\mathrm{I})\lesssim\min\\{n,M\\}$ with probability at least $1-1/400$. For
the second term, since $\omega_{m}\leq\sigma_{m}$, we have
$(\mathrm{II})\leq\mathbb{E}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}$.
Therefore, with probability at least $1-1/400$, it holds that

$\displaystyle(\mathrm{I})+(\mathrm{II})\leavevmode\nobreak\
\lesssim\leavevmode\nobreak\
\min\\{n,M\\}+\mathbb{E}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]},$

which proves the inequality (50).

2\. Proof of the second claim (48). Next we prove the second claim (48) under
the condition on $\epsilon$ imposed in Canonne et al., (2018). In particular,
for $\ell_{1}\geq\ell_{2}$ and
$\inf_{Q\in\mathcal{P}_{0,[M]}}\mathcal{D}_{\mathrm{TV}}(P_{X,Y,Z},Q)\geq\varepsilon$,
equation (1) of Canonne et al., (2018) assumes that $\varepsilon$ satisfies

$\displaystyle n\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\zeta^{\prime}\times\max\Biggl{(}$
$\displaystyle\min\Biggl{\\{}\frac{M^{7/8}\ell_{1}^{1/4}\ell_{2}^{1/4}}{\varepsilon},\frac{M^{6/7}\ell_{1}^{2/7}\ell_{2}^{2/7}}{\varepsilon^{8/7}}\Biggr{\\}},$
(52)
$\displaystyle\frac{M^{3/4}\ell_{1}^{1/2}\ell_{2}^{1/2}}{\varepsilon},\frac{M^{2/3}\ell_{1}^{2/3}\ell_{2}^{1/3}}{\varepsilon^{4/3}},\frac{M^{1/2}\ell_{1}^{1/2}\ell_{2}^{1/2}}{\varepsilon^{2}}\Biggr{)},$

where $\zeta^{\prime}$ is a sufficiently large positive constant. A sufficient
condition for this inequality in the form of $\varepsilon\gtrsim
f(M,\ell_{1},\ell_{2},n)$ is

$\displaystyle\varepsilon\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\zeta^{\prime\prime}\times\max\Biggl{(}\frac{M^{7/8}\ell_{1}^{1/4}\ell_{2}^{1/4}}{n},$
$\displaystyle\frac{M^{3/4}\ell_{1}^{1/2}\ell_{2}^{1/2}}{n},\frac{M^{1/2}\ell_{1}^{1/2}\ell_{2}^{1/4}}{n^{3/4}},$
$\displaystyle\frac{M^{1/4}\ell_{1}^{1/4}\ell_{2}^{1/4}}{n^{1/2}},\frac{M^{3/4}\ell_{1}^{1/4}\ell_{2}^{1/4}}{n^{7/8}}\Biggr{)},$

where $\zeta^{\prime\prime}$ is some large positive constant. Let us define an
event $\mathcal{E}$ such that
$\mathbb{E}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}\gtrsim\sqrt{\zeta^{\prime}\min\\{n,M\\}}$
and

$\displaystyle\mathrm{Var}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\min\\{n,M\\}+\sqrt{\min\\{n,M\\}}\mathbb{E}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}+\mathbb{E}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}^{3/2}.$

If
$\inf_{Q\in\mathcal{P}_{0,[M]}}\mathcal{D}_{\mathrm{TV}}(P_{X,Y,Z},Q)\geq\varepsilon$,
Lemma 5.4 of Canonne et al., (2018) guarantees that
$\mathbb{P}(\mathcal{E})\geq 399/400$. Under this event, by choosing
$\zeta^{\prime}$ sufficiently large depending on $\zeta$, we see that

$\displaystyle\zeta\sqrt{\min\\{n,M\\}+\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{1}{2}\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}].$

Thus

$\displaystyle\mathbb{P}\Big{[}T_{\mathrm{CI},W}<\zeta\sqrt{\min\\{n,M\\}+\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\Big{]}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}\Big{[}T_{\mathrm{CI},W}\leq\frac{1}{2}\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]|\mathcal{E}\Big{]}+\frac{1}{400}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{1}{200},$

where the last inequality uses Chebyshev’s inequality, as detailed in the
proof of Lemma 5.6 in Canonne et al., (2018).

$\bullet$ Type II error of $\phi_{\mathrm{perm},1}$. The type II error bound
for $\phi_{\mathrm{perm},1}$ follows similarly as $\phi_{\mathrm{perm},2}$.
Indeed it is simpler to prove the result of $\phi_{\mathrm{perm},1}$ than
$\phi_{\mathrm{perm},2}$ as $T_{\mathrm{CI}}$ does not involve randomness from
weights. We note from Lemma 6 again that the type II error of
$\phi_{\mathrm{perm},1}$ is equivalent to
$\mathbb{P}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI}}\leq q_{1-\alpha}]$ where
$q_{1-\alpha}$ is the $1-\alpha$ quantile of the empirical distribution of
$T_{\mathrm{CI}}^{\bm{\pi}_{1}},\ldots,T_{\mathrm{CI}}^{\bm{\pi}_{K}}$ (with
some abuse of notation). We then prove the results in two steps as before. In
the first step, we show that

$\displaystyle\mathbb{P}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI}}\leq
q_{1-\alpha}]\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\mathbb{P}_{P_{X,Y,Z}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta\sqrt{\min\\{n,M\\}}\big{]}+\frac{1}{200}.$
(53)

In the second step, we verify that

$\displaystyle\mathbb{P}_{P_{X,Y,Z}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta\sqrt{\min\\{n,M\\}}\big{]}\leq\frac{1}{200},$
(54)

under the condition on $\varepsilon$ imposed by Canonne et al., (2018).

1\. Proof of the first claim (53). To start with the first claim (53), by
Chebyshev’s inequality along with Markov’s inequality, we have

$\displaystyle
q_{1-\alpha}\leq\sqrt{200\alpha^{-1}\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI}}^{\bm{\pi}})^{2}\big{]}\big{\\}}},$

with probability at least $1-1/200$. Again, by the independence between
$\pi_{1},\ldots,\pi_{M}$ and following the analysis in the proof of Theorem 4
— especially the proof of the inequality (29c), the conditional expectation
becomes

$\displaystyle\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI}}^{\bm{\pi}})^{2}\big{]}|\bm{\sigma}\big{\\}}\leavevmode\nobreak\
=\leavevmode\nobreak$ $\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\mathbb{E}\big{[}U_{W}^{2}(\bm{W}_{m}^{\pi_{m}})|\bm{\sigma}\big{]}$
(55) $\displaystyle\leavevmode\nobreak\
\overset{\mathrm{(i)}}{=}\leavevmode\nobreak$
$\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\mathbb{E}\big{[}\mathrm{Var}_{\bm{\pi}}\\{U_{W}(\bm{W}_{m}^{\pi_{m}})|\bm{W}_{m},\bm{\sigma}\\}|\bm{\sigma}\big{]}$
$\displaystyle\overset{\mathrm{(ii)}}{\lesssim}\leavevmode\nobreak$
$\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
1)\overset{\mathrm{(iii)}}{\lesssim}\min\\{N,M\\},$

where step (i) uses the fact that
$\mathbb{E}_{\bm{\pi}}\\{U_{W}(\bm{W}_{m}^{\pi_{m}})|\bm{W}_{m},\bm{\sigma}\\}=0$,
step (ii) follows based on the analysis in the proof of the inequality (29c)
and step (iii) follows by combining the two inequalities
$\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq 1)\leq\sum_{m\in[M]}1=M$ and
$\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq 1)\leq\sum_{m\in[M]}\sigma_{m}=N$. By
taking the expectation over $\bm{\sigma}$, we then have
$\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI}}^{\bm{\pi}})^{2}\big{]}\big{\\}}\lesssim\min\\{n,M\\}$.
Therefore, the inequality (53) holds by taking $\zeta$ sufficiently large and
the union bound.

2\. Proof of the second claim (54). The proof of this result directly follows
by Section 3.1 of Canonne et al., (2018). In particular, for fixed $\ell_{1}$
and $\ell_{2}$, and
$\inf_{Q\in\mathcal{P}_{0,[M]}}\mathcal{D}_{\mathrm{TV}}(P_{X,Y,Z},Q)\geq\varepsilon$,
Canonne et al., (2018) assume that $\varepsilon$ satisfies

$\displaystyle n\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\zeta^{\prime}\times\max\Biggl{(}\frac{M^{1/2}}{\varepsilon^{2}},\min\Biggl{(}\frac{M^{7/8}}{\varepsilon},\frac{M^{6/7}}{\varepsilon^{8/7}}\Biggr{)}\Biggr{)},$
(56)

where $\zeta^{\prime}$ is a sufficiently large positive constant. A sufficient
condition for this inequality in the form of $\varepsilon\gtrsim f(M,n)$ is

$\displaystyle\varepsilon\leavevmode\nobreak\ \geq\leavevmode\nobreak\
\zeta^{\prime\prime}\max\Biggl{(}\frac{M^{1/4}}{n^{1/2}},\frac{M^{7/8}}{n},\frac{M^{3/4}}{n^{7/8}}\Biggr{)},$

for some large $\zeta^{\prime\prime}>0$ as mentioned in the main text. Under
this condition, Section 3.1 of Canonne et al., (2018) shows that the second
claim (54) holds by taking $\zeta$ sufficiently large. Finally, combining the
two inequalities (53) and (54) yields the desired result. This completes the
proof of Theorem 5.

###  A.7 Proof of Theorem 6

We first study the type II error bound of $\phi_{\mathrm{perm},1}^{\dagger}$
and then turn to the type II error bound of
$\phi_{\mathrm{perm},2}^{\dagger}$.

$\bullet$ Type II error of $\phi_{\mathrm{perm},1}^{\dagger}$. The proof of
this part is similar to that of Theorem 5, especially the result of
$\phi_{\mathrm{perm},1}$. The only difference is that we are now dealing with
the discretized probability $Q_{X,Y,\widetilde{Z}}$ defined in Section 4.2,
rather than the original probability $P_{X,Y,Z}$. Since the upper bound for
the expected variance
$\mathbb{E}\big{\\{}\mathbb{E}_{\bm{\pi}}\big{[}(T_{\mathrm{CI}}^{\bm{\pi}})^{2}\big{]}|\bm{\sigma}\big{\\}}$
in (55) does not depend on the underlying discrete distribution, the same
proof carries through and we can obtain the bound (53) for
$Q_{X,Y,\widetilde{Z}}$ as well. In particular, since we set
$\min\\{n,M\\}\leq M=\lceil n^{2/5}\rceil$, we have

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{N},N}[1-\phi_{\mathrm{perm},1}^{\dagger}]\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\mathbb{P}_{Q_{X,Y,\widetilde{Z}}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta
n^{1/5}\big{]}+\frac{1}{200}+e^{-n/8},$

where we note that
$\mathbb{P}_{Q_{X,Y,\widetilde{Z}}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta
n^{1/5}\big{]}=\mathbb{P}_{P_{X,Y,Z}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta
n^{1/5}\big{]}$ since $T_{\mathrm{CI}}$ is defined only through the binned
data. We also note that $e^{-n/8}$ comes from the truncation probability of
$N$ as in (26). This probability is essentially the type II error of the test
of Neykov et al., (2021) by adjusting the value of $\zeta$, and thus we have

$\displaystyle\sup_{P_{X,Y,Z}\in\mathcal{P}_{1,[0,1],\mathrm{TV}}(L):\inf_{Q\in\mathcal{P}_{0,[0,1]}}\mathcal{D}_{\mathrm{TV}}(P_{X,Y,Z},Q)\geq\varepsilon}\mathbb{P}_{P_{X,Y,Z}^{N},N}\big{[}T_{\mathrm{CI}}<\zeta
n^{1/5}\big{]}\leavevmode\nobreak\ \leq\leavevmode\nobreak\ \frac{1}{100}.$

See the proof of Theorem 5.2 in Neykov et al., (2021) for more details.
Therefore, we conclude that $\phi_{\mathrm{perm},1}^{\dagger}$ has the same
power guarantee as $\phi_{\mathrm{NBW},1}$.

$\bullet$ Type II error of $\phi_{\mathrm{perm},2}^{\dagger}$. Given that
$\phi_{\mathrm{perm},2}^{\dagger}$ uses the same test statistic
$T_{\mathrm{CI},W}$ as in Theorem 5, the proof of this result is similar to
that of Theorem 5, especially the result of $\phi_{\mathrm{perm},2}$. The only
difference is, again, that we now work with the discretized probability
distribution $Q_{X,Y,\widetilde{Z}}$ defined in Section 4.2. Following exactly
the same lines in the proof of Theorem 5, there exists an absolute constant
$\zeta^{\prime}>0$ such that

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{N},N}[1-\phi_{\mathrm{perm},2}^{\dagger}]$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}_{Q_{X,Y,\widetilde{Z}}^{N},N}\Big{\\{}T_{\mathrm{CI},W}<\zeta^{\prime}\sqrt{\min\\{n,M\\}+\mathbb{E}_{Q_{X,Y,\widetilde{Z}}^{N},N}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\Big{\\}}+\frac{1}{200}+e^{-n/8},$

where the second line also holds by replacing $Q_{X,Y,\widetilde{Z}}^{N}$ with
$P_{X,Y,Z}^{N}$ in the probability and the expectation since
$T_{\mathrm{CI},W}$ is defined only through the binned data.

To further bound the given probability, we recall the results in Neykov et
al., (2021). By ignoring the dependence on $Q_{X,Y,\widetilde{Z}}^{N}$, the
following two bounds hold with probability at least $399/400$ under the given
conditions for the guarantee (20):

$\displaystyle\mathrm{Var}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}$
$\displaystyle\lesssim\leavevmode\nobreak\ $ $\displaystyle
M+(\sqrt{M}+1)\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]+[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]^{3/2}$

and

$\displaystyle\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]\gtrsim\sqrt{\zeta
M},$

where $\zeta>0$ is a sufficiently large constant given in
$\phi_{\mathrm{NBW},2}$, which differs from $\zeta^{\prime}$ above. See Lemma
C.10 of Neykov et al., (2021) for details on these bounds. Let $\mathcal{E}$
be an event that both inequalities hold simultaneously. Under this event, by
taking $\zeta$ sufficiently large depending on $\zeta^{\prime}$, we have

$\displaystyle\zeta^{\prime}\sqrt{\min\\{n,M\\}+\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\frac{1}{2}\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}].$

Then by Chebyshev’s inequality and Lemma C.13 of Neykov et al., (2021),

$\displaystyle\mathbb{P}\Big{[}T_{\mathrm{CI},W}<\zeta^{\prime}\sqrt{\min\\{n,M\\}+\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]}\Big{]}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}\Big{[}T_{\mathrm{CI},W}\leq\frac{1}{2}\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]|\mathcal{E}\Big{]}+\frac{1}{400}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{1}{200}.$

This completes the proof of the second part.

###  A.8 Proof of Theorem 7

The proof of this result is essentially the same as that of the second part of
Theorem 6, which builds on the proof of Theorem 5. The only difference is that
we are now in a situation where $X,Y,Z$ are all discretized. Under this
binning scheme, the mean and the variance of $T_{\mathrm{CI},W}$ have been
studied in Neykov et al., (2021). In particular, Lemma G.9 of Neykov et al.,
(2021) yields that the following two events hold under the conditions of the
theorem with probability at least $399/400$:

$\displaystyle\mathrm{Var}\big{[}T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}\big{]}$
$\displaystyle\lesssim\leavevmode\nobreak\ $
$\displaystyle\big{\\{}M+(\sqrt{M}+1)\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]+[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]^{3/2}\big{\\}}$

and

$\displaystyle\mathbb{E}[T_{\mathrm{CI},W}|\bm{\mathcal{W}}_{\mathrm{weight}},\bm{\sigma}]\gtrsim\sqrt{\zeta
M},$

where $\zeta>0$ is a sufficiently large constant given in
$\phi_{\mathrm{NBW},2}$. Building upon this result, we can proceed by
following the same lines of the proof of Theorem 6 to complete the proof. We
omit the details.

###  A.9 Proof of Proposition 1

The proof of this result follows by modifying the proof of the validity of
usual permutation tests based on exchangeability (e.g. Lehmann and Romano,,
2006). Here we provide a detail for completeness. Let
$\mathcal{X}:=\\{(X_{i},Y_{i},\widetilde{Z}_{i})\\}_{i=1}^{n}\sim\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}$
be a set of $n$ i.i.d. draws from the CI projection
$\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}$. For each
$\bm{\pi},\bm{\pi}^{\prime}\in\bm{\Pi}_{\mathrm{cyclic}}$, write
$\mathcal{X}^{\bm{\pi}}=\\{(X_{i},Y_{\bm{\pi}(i)},\widetilde{Z}_{i})\\}_{i=1}^{n}$
and
$\mathcal{X}^{\bm{\pi}\circ\bm{\pi}^{\prime}}=\\{(X_{i},Y_{\bm{\pi}\circ\bm{\pi}^{\prime}(i)},\widetilde{Z}_{i})\\}_{i=1}^{n}$
where $\bm{\pi}\circ\bm{\pi}^{\prime}$ denotes the composition of two
permutation maps $\bm{\pi}$ and $\bm{\pi}^{\prime}$. Throughout this proof, we
use the notation $T(\mathcal{X}^{\bm{\pi}})=T_{\mathrm{CI}}^{\bm{\pi}}$ and
$T(\mathcal{X})=T_{\mathrm{CI}}$. Let $T^{(1)}(\mathcal{X})\leq\ldots\leq
T^{(K_{\ast})}(\mathcal{X})$ be the ordered statistics of
$T(\mathcal{X}^{\bm{\pi}_{1}}),\ldots,T(\mathcal{X}^{\bm{\pi}_{K_{\ast}}})$
where
$\\{\bm{\pi}_{1},\ldots,\bm{\pi}_{K_{\ast}}\\}=\bm{\Pi}_{\mathrm{cyclic}}$.
Note that the set
$\\{T(\mathcal{X}^{\bm{\pi}_{1}}),\ldots,T(\mathcal{X}^{\bm{\pi}_{K_{\ast}}})\\}$
has the same components as
$\\{T(\mathcal{X}^{\bm{\pi}_{1}\circ\bm{\pi}}),\ldots,T(\mathcal{X}^{\bm{\pi}_{K_{\ast}}\circ\bm{\pi}})\\}$
for any $\bm{\pi}\in\bm{\Pi}_{\mathrm{cyclic}}$. Therefore,
$T^{(i)}(\mathcal{X})=T^{(i)}(\mathcal{X}^{\bm{\pi}})$ for any
$i=1,\ldots,K_{\ast}$ and $\bm{\pi}\in\bm{\Pi}_{\mathrm{cyclic}}$.

Having the above preliminaries in place, suppose we reject the null when
$T(\mathcal{X})>T^{(k)}(\mathcal{X})$ where
$k=\lceil(1-\alpha)K_{\ast}\rceil$. Then, by letting $\bm{\pi}_{0}$ have the
uniform distribution on $\bm{\Pi}_{\mathrm{cyclic}}$, we have

$\displaystyle\mathbb{P}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}\big{\\{}T(\mathcal{X})>T^{(k)}(\mathcal{X})\big{\\}}\leavevmode\nobreak\
\overset{(\mathrm{i})}{=}\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}\big{\\{}T(\mathcal{X}^{\bm{\pi}_{0}})>T^{(k)}(\mathcal{X}^{\bm{\pi}_{0}})\big{\\}}$
$\displaystyle\overset{(\mathrm{ii})}{=}\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}\big{\\{}T(\mathcal{X}^{\bm{\pi}_{0}})>T^{(k)}(\mathcal{X})\big{\\}},$

where step (i) uses the fact that $\mathcal{X}$ and $\mathcal{X}^{\bm{\pi}}$
have the same distribution for all $\bm{\pi}\in\bm{\Pi}_{\mathrm{cyclic}}$
under the law $\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}$, and step (ii) holds due
to $T^{(k)}(\mathcal{X})=T^{(k)}(\mathcal{X}^{\bm{\pi}})$. Now since
$\bm{\pi}_{0}$ is uniformly distributed on $\bm{\Pi}_{\mathrm{cyclic}}$, we
have

$\displaystyle\mathbb{P}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}\big{\\{}T(\mathcal{X}^{\bm{\pi}_{0}})>T^{(k)}(\mathcal{X})\big{\\}}=\mathbb{E}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}\Bigg{[}\frac{1}{K_{\ast}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}}\mathds{1}\big{\\{}T(\mathcal{X}^{\bm{\pi}_{i}})>T^{(k)}(\mathcal{X})\big{\\}}\Bigg{]}\leq\alpha,$

where the last inequality holds since

$\displaystyle\frac{1}{K_{\ast}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}}\mathds{1}\big{\\{}T(\mathcal{X}^{\bm{\pi}_{i}})>T^{(k)}(\mathcal{X})\big{\\}}\leq\alpha.$

Finally, by Lemma 6, the permutation test from Algorithm 2 can be equivalently
written as
$\phi_{\mathrm{perm},n}=\mathds{1}\\{T(\mathcal{X})>T^{(k)}(\mathcal{X})\\}$.
Therefore, we have

$\displaystyle\mathbb{E}_{\widetilde{Q}_{X,Y,\widetilde{Z}}^{n}}[\phi_{\mathrm{perm},n}]\leq\alpha.$

Having this inequality, the other steps are exactly the same as the proofs of
Theorem 2 and Theorem 3. This completes the proof of Proposition 1.

###  A.10 Proof of Theorem 8

The main idea of the proof of this result is similar to that of Theorem 6.
However, it requires a much more involved analysis for the mean and the
variance due to a sophisticated dependence structure among local permutations
over smaller bins. For the single-binning method, there is a symmetric
structure of the U-statistic under the (global) permutation, which allows us
to show that the mean of the permuted U-statistic is zero and its variance is
bounded by some tractable quantities (e.g. Theorem 5.1 of Kim et al.,, 2020).
However, this is no longer the case for the double-binning method, which leads
to a technical challenge.

Throughout this proof, we only deal with the type II error (or $1-$power) of
$\phi_{\mathrm{perm},N}$ since the result of
$\phi_{\mathrm{perm},N}^{\dagger}$ follows directly by the inequality (26).
For a sufficiently large $\zeta>0$ (depending on $L$), Neykov et al., (2021)
prove that the test
$\phi_{\mathrm{NBW},1}^{\prime}=\mathds{1}(T_{\mathrm{CI}}\geq\zeta n^{1/5})$
has a small type II error in the sense of (18) (indeed, without $e^{-n/8}$
term) when $\varepsilon\geq cn^{-2/5}$ for a sufficiently large $c$ depending
on ($\zeta,L,\ell_{1},\ell_{2}$). Moreover, since
$\mathcal{P}^{\prime}_{1,[0,1],\mathrm{TV}}(L)\subseteq\mathcal{P}_{1,[0,1],\mathrm{TV}}(L)$,
it holds that

$\displaystyle\sup_{P_{X,Y,Z}\in\mathcal{P}^{\prime}_{1,[0,1],\mathrm{TV}}(L):\inf_{Q\in\mathcal{P}_{0,[0,1]}}\mathcal{D}_{\mathrm{TV}}(P_{X,Y,Z},Q)\geq\varepsilon}\mathbb{P}_{P_{X,Y,Z}^{N},N}[T_{\mathrm{CI}}\geq\zeta
n^{1/5}]\leq\frac{1}{200}.$ (57)

Now let $q_{1-\alpha}$ be the $1-\alpha$ quantile of the empirical
distribution of
$T_{\mathrm{CI}}^{\bm{\pi}_{1}},\ldots,T_{\mathrm{CI}}^{\bm{\pi}_{K_{\ast}}}$
where $\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}$. Our main goal is to show
that $q_{1-\alpha}\leq\zeta^{\prime}n^{1/5}$ for a sufficiently large
$\zeta^{\prime}$ with high probability (say $1/200$) under the given
conditions. Since the type II error of $\phi_{\mathrm{perm},N}$ can be written
as $\mathbb{P}(T_{\mathrm{CI}}\leq q_{1-\alpha})$ in view of Lemma 6, this
bound for the quantile together with the union bound implies that the type II
error of $\phi_{\mathrm{perm},N}$ is smaller than $1/100$ by taking $\zeta$
sufficiently large.

We break down the proof into several pieces for readability.

  * •

Step 1. Bounding the quantile. In the first step, we prove that the $1-\alpha$
quantile is upper bounded by

$\displaystyle q_{1-\alpha}\leavevmode\nobreak\ \lesssim\leavevmode\nobreak\
\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]},$

with high probability where $\bm{\pi}\sim F_{\bm{\pi}}$ defined in (59) below.
Here we note that the expectation and the variance are with respect to both
randomness from $\bm{\pi}$ and samples.

  * •

Step 2. Bounding the expectation. In the second step, we upper bound the
expectation of $T_{\mathrm{CI}}^{\bm{\pi}}$ where $\bm{\pi}\sim F_{\bm{\pi}}$
in (59) and prove that

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\Bigg{(}\frac{n}{M^{2}}+1+\frac{M^{2}}{n}\Bigg{)},$

  * •

Step 3. Bounding the variance. In the third step, we upper bound the variance
of $T_{\mathrm{CI}}^{\bm{\pi}}$ where $\bm{\pi}\sim F_{\bm{\pi}}$ in (59) and
prove that

$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\frac{n^{2}}{M^{4}}+\frac{n}{M^{2}}+\frac{M^{2}}{n}+M\right).$

  * •

Step 4. Completing the proof. Lastly, we combine the previous results and
prove the desired type II error bound for $\phi_{\mathrm{perm},N}$.

Step 1. Bounding the quantile. We start by bounding the $1-\alpha$ quantile

$\displaystyle
q_{1-\alpha}=\inf\bigg{\\{}x\in\mathbb{R}:1-\alpha\leq\frac{1}{K_{\ast}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}}\mathds{1}\big{(}T_{\mathrm{CI}}^{\bm{\pi}_{i}}\leq
x\big{)}\bigg{\\}}.$

Consider a subset of $\bm{\Pi}_{\mathrm{cyclic}}$ where we remove the identity
permutation within each small bin. Let us denote the resulting subset by
$\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}$ whose cardinality is
$K_{\ast}^{-\mathrm{id}}:=\prod_{(m,k)\in[M]\times[b]}\max\\{\sigma_{m,k}-1,1\\}$.
By letting $\alpha_{\ast}$ such that
$1-\alpha_{\ast}=\min\big{\\{}(1-\alpha)K_{\ast}/K_{\ast}^{\mathrm{-id}},1\big{\\}}$,
define

$\displaystyle q_{1-\alpha_{\ast}}^{\mathrm{-id}}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\inf\bigg{\\{}x\in\mathbb{R}:\min\bigg{\\{}(1-\alpha),\frac{K_{\ast}^{\mathrm{-id}}}{K_{\ast}}\bigg{\\}}\leq\frac{1}{K_{\ast}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}}\mathds{1}\big{(}T_{\mathrm{CI}}^{\bm{\pi}_{i}}\leq
x\big{)}\bigg{\\}}$ $\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\inf\bigg{\\{}x\in\mathbb{R}:\min\bigg{\\{}(1-\alpha)\frac{K_{\ast}}{K_{\ast}^{\mathrm{-id}}},1\bigg{\\}}\leq\frac{1}{K_{\ast}^{\mathrm{-id}}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}}\mathds{1}\big{(}T_{\mathrm{CI}}^{\bm{\pi}_{i}}\leq
x\big{)}\bigg{\\}}.$

Since
$\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}}\mathds{1}\big{(}T_{\mathrm{CI}}^{\bm{\pi}_{i}}\leq
x\big{)}$ is a sum of non-negative numbers, we have $q_{1-\alpha}\leq
q_{1-\alpha_{\ast}}^{\mathrm{-id}}$. Therefore

$\displaystyle\mathbb{P}(T_{\mathrm{CI}}\leq q_{1-\alpha})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \mathbb{P}(T_{\mathrm{CI}}\leq
q_{1-\alpha_{\ast}}^{\mathrm{-id}}).$

Let us define an event $\mathcal{A}$ as

$\displaystyle\mathcal{A}=\bigg{\\{}\frac{K_{\ast}}{K_{\ast}^{\mathrm{-id}}}\leq\frac{1-\alpha/2}{1-\alpha}\bigg{\\}},$
(58)

and let $q_{1-\alpha/2}^{\mathrm{-id}}$ be the $1-\alpha/2$ quantile of the
empirical distribution

$\displaystyle
F_{\bm{\pi}}(x):=\frac{1}{K_{\ast}^{\mathrm{-id}}}\sum_{\bm{\pi}_{i}\in\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}}\mathds{1}\big{(}T_{\mathrm{CI}}^{\bm{\pi}_{i}}\leq
x\big{)}.$ (59)

Then, since $q_{1-\alpha_{\ast}}^{\mathrm{-id}}\leq
q_{1-\alpha/2}^{\mathrm{-id}}$ under $\mathcal{A}$, we have

$\displaystyle\mathbb{P}(T_{\mathrm{CI}}\leq
q_{1-\alpha_{\ast}}^{\mathrm{-id}})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \mathbb{P}(T_{\mathrm{CI}}\leq
q_{1-\alpha/2}^{\mathrm{-id}})+\mathbb{P}(\mathcal{A}^{c}).$

In what follows, we use the notation $\mathbb{E}_{\bm{\pi}}[\cdot]$ and
$\mathrm{Var}_{\bm{\pi}}[\cdot]$ to denote the expectation and variance
operators with respect to $F_{\bm{\pi}}$ and let
$\mathbb{P}_{\bm{\pi}}[\cdot]=\mathbb{E}_{\bm{\pi}}[\mathds{1}(\cdot)]$. Given
this notation, we further upper bound $q_{1-\alpha/2}^{\mathrm{-id}}$. To this
end, we follow the proof of Lemma 3.1 of Kim et al., (2020). First, for $t>0$,
by Chebyshev’s inequality,

$\displaystyle\mathbb{P}_{\bm{\pi}}(T_{\mathrm{CI}}^{\bm{\pi}}-\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\geq
t)\leq\leavevmode\nobreak\
\frac{1}{t^{2}}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}].$

By setting the right-hand side to be $\alpha/2$, we see that
$q_{1-\alpha/2}^{\mathrm{-id}}$ is deterministically bounded by

$\displaystyle
q_{1-\alpha/2}^{\mathrm{-id}}\leq\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\frac{2}{\alpha}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]}.$

Next applying Chebyshev’s inequality and Markov’s inequality yields

$\displaystyle\mathbb{P}\bigg{(}\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\geq\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\frac{2}{\beta}\mathrm{Var}\big{\\{}\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}}\bigg{)}\leq\frac{\beta}{2}\quad\text{and}$
$\displaystyle\mathbb{P}\bigg{(}\frac{2}{\alpha}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\geq\frac{4}{\alpha\beta}\mathbb{E}\big{\\{}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}\bigg{)}\leq\frac{\beta}{2}.$

From the above observation together with the union bound, it holds with
probability at least $1-\beta$ that

$\displaystyle q_{1-\alpha/2}^{\mathrm{-id}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\frac{2}{\beta}\mathrm{Var}\big{\\{}\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}}+\sqrt{\frac{4}{\alpha\beta}\mathbb{E}\big{\\{}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\frac{32}{\alpha\beta}\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]},$

where the last inequality uses
$\mathrm{Var}\big{\\{}\mathbb{E}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}+\mathbb{E}\big{\\{}\mathrm{Var}_{\bm{\pi}}[T_{\mathrm{CI}}^{\bm{\pi}}]\big{\\}}\leq\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]$.
In summary, by taking $\alpha=1/100$ and $\beta=1/200$, we have obtained that

$\displaystyle\mathbb{P}(T_{\mathrm{CI}}\leq q_{1-\alpha})\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\mathbb{P}\Big{(}T_{\mathrm{CI}}\lesssim\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]}\Big{)}+\frac{1}{200}+\mathbb{P}(\mathcal{A}^{c}).$
(60)

Step 2. Upper bounding the expectation. Recall that

$\displaystyle T_{\mathrm{CI}}^{\bm{\pi}}\leavevmode\nobreak\
=\leavevmode\nobreak\ $ $\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}U(\bm{W}_{m}^{\bm{\pi}}),$

where $\bm{\pi}$ is uniformly distributed on
$\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}$. When $\sigma_{m}<4$,
$\mathds{1}(\sigma_{m}\geq 4)\sigma_{m}U(\bm{W}_{m}^{\bm{\pi}})$ becomes zero,
which does not contribute to $T_{\mathrm{CI}}^{\bm{\pi}}$. Hence, we assume
$\sigma_{m}\geq 4$ and show that

$\displaystyle\mathbb{E}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]=O\left(\frac{1}{M^{2}}+\frac{1}{M\sigma_{m}}+\frac{1}{\sigma_{m}^{2}}\right)\quad\text{for
each $m\in[M]$.}$ (61)

Recall $U(\bm{W}_{m}^{\bm{\pi}})$ is the U-statistic with the kernel that
takes the form

$\displaystyle\varphi_{i,j,k,\ell}^{\bm{\pi}}:=\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}$
$\displaystyle\big{\\{}\mathds{1}(X_{i,m}=x,Y_{{\pi}_{i,m}}=y)-\mathds{1}(X_{i,m}=x)\mathds{1}(Y_{{\pi}_{j,m}}=y)\big{\\}}\times$
$\displaystyle\big{\\{}\mathds{1}(X_{k,m}=x,Y_{{\pi}_{k,m}}=y)-\mathds{1}(X_{k,m}=x)\mathds{1}(Y_{{\pi}_{\ell,m}}=y)\big{\\}},$

where $\\{i,j,k,\ell\\}$ are distinct integers between $1$ and $\sigma_{m}$,
and $\\{\pi_{i,m},\pi_{j,m},\pi_{k,m},\pi_{\ell,m}\\}$ are components of
$\bm{\pi}$ that are used to permute the corresponding components of
$\\{Y_{i,m},Y_{j,m},Y_{k,m},Y_{\ell,m}\\}$. Due to a complicated local
structure of $\bm{\pi}$, it is not trivial to compute the expectation of this
kernel. This is in contrast to the single-binning case where this expectation
of the kernel is zero under the local permutation law. We instead upper bound
the expectation using the following observation. Suppose that there is no
collision, meaning that neither of $Y_{i,m},Y_{k,m}$ corresponds to
$Y_{\pi_{i,m}},Y_{\pi_{j,m}},Y_{\pi_{k,m}},Y_{\pi_{\ell,m}}$. In this case,
$\\{X_{i,m},X_{j,m},Y_{\pi_{i,m}},Y_{\pi_{j,m}},Y_{\pi_{k,m}},Y_{\pi_{\ell,m}}\\}$
are mutually independent, and the expectation of the kernel is bounded above
by

$\displaystyle\big{|}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\big{|}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
\Bigg{|}\max_{k_{1},k_{2},k_{3},k_{4}\in[b]}\Bigg{[}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}$
$\displaystyle\\{p_{m,k_{1}}(x)q_{m,k_{1}}(y)-p_{m,k_{1}}(x)q_{m,k_{2}}(y)\\}\times$
(62)
$\displaystyle\\{p_{m,k_{3}}(x)q_{m,k_{3}}(y)-p_{m,k_{3}}(x)q_{m,k_{4}}(y)\\}\Bigg{]}\Bigg{|},$

where $p_{m,k}(x):=\mathbb{P}(X=x|Z\in B_{m,k})$ and
$q_{m,k}(y):=\mathbb{P}(Y=y|Z\in B_{m,k})$. Furthermore, since we assume
$P_{X,Y,Z}\in\mathcal{P}^{\prime}_{1,[0,1],\mathrm{TV}(L)}$,

$\displaystyle\mathcal{D}_{\mathrm{TV}}(q_{m,k_{1}},q_{m,k_{2}})$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\frac{1}{2}\sum_{y\in[\ell_{2}]}\bigg{|}\int_{B_{m,k_{1}}}p_{Y|Z}(y|z)d\widetilde{P}_{Z|Z\in
B_{m,k_{1}}}(z)-\int_{B_{m,k_{2}}}p_{Y|Z}(y|z^{\prime})d\widetilde{P}_{Z|Z\in
B_{m,k_{2}}}(z^{\prime})\bigg{|}$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\frac{1}{2}\int_{B_{m,k_{1}}}\int_{B_{m,k_{2}}}\sum_{y\in[\ell_{2}]}\big{|}p_{Y|Z}(y|z)-p_{Y|Z}(y|z^{\prime})\big{|}d\widetilde{P}_{Z|Z\in
B_{m,k_{1}}}(z)d\widetilde{P}_{Z|Z\in B_{m,k_{2}}}(z^{\prime})$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{1}{2}\max_{z\in
B_{m,k_{1}},z^{\prime}\in
B_{m,k_{2}}}\delta(z,z^{\prime})\leq\frac{C_{1}}{M},$

for some constant $C_{1}>0$. Therefore
$\big{|}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}]\big{|}$ is further bounded
by

$\displaystyle\big{|}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\big{|}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\Bigg{|}\max_{k_{1},k_{2},k_{3},k_{4}\in[b]}\Bigg{[}\sum_{x\in[\ell_{1}]}p_{m,k_{1}}(x)p_{m,k_{3}}(x)\sum_{y\in[\ell_{2}]}|q_{m,k_{1}}(y)-q_{m,k_{2}}(y)|\sum_{y\in[\ell_{2}]}|q_{m,k_{3}}(y)-q_{m,k_{4}}(y)|\Bigg{]}\Bigg{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
4\max_{k_{1},k_{2},k_{3},k_{4}\in[b]}\mathcal{D}_{\mathrm{TV}}(q_{m,k_{1}},q_{m,k_{2}})\times\mathcal{D}_{\mathrm{TV}}(q_{m,k_{3}},q_{m,k_{4}})$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{C_{2}}{M^{2}}.$

Suppose that there is only one collision, i.e. there exists only one dependent
pair of $(X,Y)$ among
$\\{X_{i,m},X_{j,m},Y_{\pi_{i,m}},Y_{\pi_{j,m}},Y_{\pi_{k,m}},Y_{\pi_{\ell,m}}\\}$.
Since we deal with a cyclic permutation excluding the identity map, there are
only a few possibilities of one collision. In particular, a cyclic
permutation, which is not the identity map, is a derangement (i.e. no point
will be at its original place). This guarantees that $X_{i,m}$ and
$Y_{\pi_{i,m}}$ are independent for each $i$ and $m$, which simplifies our
analysis.

Case 1) Suppose that $X_{i,m}$ and $Y_{\pi_{j,m}}$ collide. In this case,
$\\{X_{k,m},Y_{\pi_{k,m}},Y_{\pi_{\ell,m}}\\}$ are still independent, which
leads to the bound of the expectation

$\displaystyle\big{|}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\big{|}\leavevmode\nobreak\
:=\leavevmode\nobreak\ $
$\displaystyle\bigg{|}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\mathbb{E}\big{\\{}\mathds{1}(X_{i,m}=x,Y_{{\pi}_{i,m}}=y)-\mathds{1}(X_{i,m}=x)\mathds{1}(Y_{{\pi}_{j,m}}=y)\big{\\}}\times$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{E}\big{\\{}\mathds{1}(X_{k,m}=x,Y_{{\pi}_{k,m}}=y)-\mathds{1}(X_{k,m}=x)\mathds{1}(Y_{{\pi}_{\ell,m}}=y)\big{\\}}\bigg{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\big{|}\mathbb{E}\big{\\{}\mathds{1}(X_{k,m}=x,Y_{{\pi}_{k,m}}=y)-\mathds{1}(X_{k,m}=x)\mathds{1}(Y_{{\pi}_{\ell,m}}=y)\big{\\}}\big{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2\sup_{k_{1},k_{2}\in[b]}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}p_{m,k_{1}}(x)\times\big{|}q_{m,k_{1}}(y)-q_{m,k_{2}}(y)\big{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{C_{3}}{M},$

where the last inequality follows similarly as the previous analysis.

Case 2) Next, suppose that $X_{i,m}$ and $Y_{\pi_{k,m}}$ collide. In this
case, $Y_{\pi_{i,m}}$ and $Y_{\pi_{j,m}}$ are independent of the others. Using
this property, the expectation is bounded by

$\displaystyle\big{|}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\big{|}\leavevmode\nobreak\
:=\leavevmode\nobreak\ $
$\displaystyle\bigg{|}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\mathbb{E}\big{\\{}\mathds{1}(Y_{{\pi}_{i,m}}=y)-\mathds{1}(Y_{{\pi}_{j,m}}=y)\big{\\}}\mathbb{E}[\mathds{1}(X_{k,m}=x)]\times$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
\mathbb{E}\big{[}\mathds{1}(X_{i,m}=x)\big{\\{}\mathds{1}(Y_{{\pi}_{k,m}}=y)-\mathds{1}(Y_{{\pi}_{\ell,m}}=y)\big{\\}}\big{]}\bigg{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
2\sup_{k_{1},k_{2}\in[b]}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}p_{m,k_{1}}(x)\times\big{|}q_{m,k_{1}}(y)-q_{m,k_{2}}(y)\big{|}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{C_{3}}{M}.$

The other cases with one collision can be bounded similarly by $O(M^{-1})$.

Now consider another representation of the U-statistic:

$\displaystyle U(\bm{W}_{m}^{\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{(\sigma_{m}-4)!}{\sigma_{m}!}\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}}\varphi_{i,j,k,\ell}^{\bm{\pi}},$

where $\bm{i}_{4}^{\sigma_{m}}$ denotes the set of all $4$-tuples drawn
without replacement from $[\sigma_{m}]$. Next we decompose the summation into
three cases depending on whether there exists a collision among

$\displaystyle\\{(X_{i,m},Y_{\pi_{i,m}}),(X_{j,m},Y_{\pi_{j,m}}),(X_{k,m},Y_{\pi_{k,m}}),(X_{\ell,m},Y_{\pi_{\ell,m}})\\}.$
(63)

In particular,

$\displaystyle\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}}\varphi_{i,j,k,\ell}^{\bm{\pi}}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A_{\mathrm{collision}}^{0}}\varphi_{i,j,k,\ell}^{\bm{\pi}}+\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A_{\mathrm{collision}}^{1}}\varphi_{i,j,k,\ell}^{\bm{\pi}}$
$\displaystyle+\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A_{\mathrm{collision}}^{1+}}\varphi_{i,j,k,\ell}^{\bm{\pi}},$

where 1) $\bm{i}_{4}^{\sigma_{m}}\cap A_{\mathrm{collision}}^{0}$ is the
subset of $\bm{i}_{4}^{\sigma_{m}}$ such that there exists no collision, 2)
$\bm{i}_{4}^{\sigma_{m}}\cap A_{\mathrm{collision}}^{1}$ is the subset of
$\bm{i}_{4}^{\sigma_{m}}$ such that there exists only one collision, and 3)
$\bm{i}_{4}^{\sigma_{m}}\cap A_{\mathrm{collision}}^{1+}$ is the subset of
$\bm{i}_{4}^{\sigma_{m}}$ such that there exists more than one collision.

Now we upper bound each summation. First of all, by the previous analysis,

$\displaystyle\frac{(\sigma_{m}-4)!}{\sigma_{m}!}\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A^{0}_{\mathrm{collision}}}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(\frac{1}{M^{2}}\right).$

Next, since $\bm{\pi}\in\bm{\Pi}_{\mathrm{cyclic}}^{\mathrm{-id}}$ is a
derangement by construction, if we pick four observations (63) with no
collision (i.e. $\\{i,j,k,\ell\\}$ and
$\\{\pi_{i},\pi_{j},\pi_{k},\pi_{\ell}\\}$ have no shared component) out of
$\sigma_{m}$ observations, there are at least
$\sigma_{m}(\sigma_{m}-2)(\sigma_{m}-4)(\sigma_{m}-6)$ ways. Thus in order to
have a collision, we have at most $O(\sigma_{m}^{3})$ choices. Moreover, as
analyzed before, the expectation of the kernel is bounded by $O(M^{-1})$ if
there is one collision. Therefore

$\displaystyle\frac{(\sigma_{m}-4)!}{\sigma_{m}!}\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A_{\mathrm{collision}}^{1}}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(\frac{1}{M\sigma_{m}}\right).$

Lastly, there are at most $\asymp\sigma_{m}^{2}$ cases to have more than one
collision. In this case, using the fact that the kernel
$\varphi_{i,j,k,\ell}^{\bm{\pi}}$ is bounded between $-1$ and $1$, we have

$\displaystyle\frac{(\sigma_{m}-4)!}{\sigma_{m}!}\sum_{\\{i,j,k,\ell\\}\in\bm{i}_{4}^{\sigma_{m}}\cap
A_{\mathrm{collision}}^{1+}}\mathbb{E}[\varphi_{i,j,k,\ell}^{\bm{\pi}}|\sigma_{m}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(\frac{1}{\sigma_{m}^{2}}\right).$

These three bounds imply the claim (61). Therefore

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\
O\Bigg{(}\frac{n}{M^{2}}+1+\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{-1}\big{]}\Bigg{)}.$

By recalling $\sigma_{m}\sim\mathrm{Pois}(np_{m})$, we have the following
inequalities

$\displaystyle\mathbb{E}\bigg{[}\mathds{1}(\sigma_{m}\geq
4)\frac{1}{\sigma_{m}}\bigg{]}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{5}{4}\mathbb{E}\bigg{[}\mathds{1}(\sigma_{m}\geq
4)\frac{1}{\sigma_{m}+1}\bigg{]}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
\frac{5}{4}\mathbb{E}\bigg{[}\frac{1}{\sigma_{m}+1}\bigg{]}.$ (64)

Furthermore,

$\displaystyle\mathbb{E}\bigg{[}\frac{1}{\sigma_{m}+1}\bigg{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{1-e^{-np_{m}}}{np_{m}}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{M}{c_{\mathrm{low}}n},$

where the last inequality uses the condition $p_{m}\geq
c_{\mathrm{low}}M^{-1}$ for all $m\in[M]$. Therefore, we have

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\Bigg{(}\frac{n}{M^{2}}+1+\frac{M^{2}}{n}\Bigg{)}.$

Step 3. Upper bounding the variance. Next we upper bound the variance of the
U-statistic $U(\bm{W}_{m}^{\bm{\pi}})$. To compute the variance of
$U(\bm{W}_{m}^{\bm{\pi}})$, first set up some notation. Similarly as in
Section 4.3, let

$\displaystyle\psi_{ij}^{m,\bm{\pi}}(x,y)=\mathds{1}(X_{i,m}=x,Y_{\pi_{i,m}}=y)-\mathds{1}(X_{i,m}=x)\mathds{1}(Y_{\pi_{j,m}}=y),$

and define a symmetrized kernel function as

$\displaystyle
h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}}=\frac{1}{4!}\sum_{\pi\in\bm{\Pi}_{4}}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\pi(1)\pi(2)}(x,y)\psi^{m,\bm{\pi}}_{\pi(3)\pi(4)}(x,y)$

where $\bm{\Pi}_{4}$ is the set of all permutations of
$\\{i_{1},i_{2},i_{3},i_{4}\\}$. Then the U-statistic can be written as

$\displaystyle U(\bm{W}_{m}^{\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{1}{\binom{\sigma_{m}}{4}}\sum_{i_{1}<i_{2}<i_{3}<i_{4}:(i_{1},i_{2},i_{3},i_{4})\in[\sigma_{m}]}h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},$

and it variance has the form as

$\displaystyle\mathrm{Var}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]\leavevmode\nobreak\
=\leavevmode\nobreak\
\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{\begin{subarray}{c}i_{1}<i_{2}<i_{3}<i_{4}\\\
:(i_{1},i_{2},i_{3},i_{4})\in[\sigma_{m}]\end{subarray}}\sum_{\begin{subarray}{c}j_{1}<j_{2}<j_{3}<j_{4}\\\
:(j_{1},j_{2},j_{3},j_{4})\in[\sigma_{m}]\end{subarray}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}).$

Here and hereafter, we often ignore the conditional event $\sigma_{m}$ when we
write the expectation and the (co)variance operator for simplicity.

Now we decompose the summation into a few different parts depending on the
number of common indices between $\\{i_{1},i_{2},i_{3},i_{4}\\}$ and
$\\{j_{1},j_{2},j_{3},j_{4}\\}$. In particular, let $A_{\mathrm{com}}^{k}$ be
the set of indices
$\\{i_{1},i_{2},i_{3},i_{4},j_{1},j_{2},j_{3},j_{4}\\}\in[\sigma_{m}]$ such
that $i_{1}<i_{2}<i_{3}<i_{4}$, $j_{1}<j_{2}<j_{3}<j_{4}$ and there are $k$
elements in common between $\\{i_{1},i_{2},i_{3},i_{4}\\}$ and
$\\{j_{1},j_{2},j_{3},j_{4}\\}$. Using this notation, the variance can be
written as

$\displaystyle\mathrm{Var}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]$
$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{0}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})+\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{1}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})$
$\displaystyle+\leavevmode\nobreak\ $
$\displaystyle\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{1+}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}).$

Since 1) the number of cases in which $\\{i_{1},i_{2},i_{3},i_{4}\\}$ and
$\\{j_{1},j_{2},j_{3},j_{4}\\}$ have more than one common index is at most
$\asymp\sigma_{m}^{6}$ and 2) that the kernel is bounded, the last term in the
above display is bounded by

$\displaystyle\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{1+}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(\sigma_{m}^{-2}\right).$

Next consider the cases in which $\\{i_{1},i_{2},i_{3},i_{4}\\}$ and
$\\{j_{1},j_{2},j_{3},j_{4}\\}$ have the exactly one common index. Without
loss of generality, we let $i_{1}=j_{1}$ and consider the resulting pairs

$\displaystyle\\{$
$\displaystyle(X_{i_{1},m},Y_{\pi_{i_{1},m}}),(X_{i_{2},m},Y_{\pi_{i_{2},m}}),(X_{i_{3},m},Y_{\pi_{i_{3},m}}),(X_{i_{4},m},Y_{\pi_{i_{4},m}}),$
$\displaystyle(X_{j_{2},m},Y_{\pi_{j_{2},m}}),(X_{j_{3},m},Y_{\pi_{j_{3},m}}),(X_{j_{4},m},Y_{\pi_{j_{4},m}})\\}.$

For now, we assume that there is no collision among the above set. Then we can
treat them as if they are i.i.d. observations with
$X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y$. Conditional on this assumption of no
collision, we can follow the proof of Lemma 5.1 of Neykov et al., (2021) and
show

$\displaystyle\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\ O(M^{-2}).$ (65)

To prove this, first let $\bm{\tau}:=\\{\tau(1),\tau(2),\tau(3),\tau(4)\\}$ be
sampled uniformly from the set of all permutations of
$\\{i_{1},i_{2},i_{3},i_{4}\\}$. Similarly let
$\bm{\tau}^{\prime}:=\\{\tau^{\prime}(1),\tau^{\prime}(2),\tau^{\prime}(3),\tau^{\prime}(4)\\}$
be sampled uniformly from the set of all permutations of
$\\{j_{1},j_{2},j_{3},j_{4}\\}$. Then by treating $\bm{\tau}$ and
$\bm{\tau}^{\prime}$ to be independent random vectors, we can re-write the
expectation as

$\displaystyle\mathbb{E}[h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}}h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}\Bigg{[}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\sum_{x^{\prime}\in[\ell_{1}],y^{\prime}\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\tau^{\prime}(1)\tau^{\prime}(2)}(x^{\prime},y^{\prime})\psi^{m,\bm{\pi}}_{\tau^{\prime}(3)\tau^{\prime}(4)}(x^{\prime},y^{\prime})\Bigg{]}.$

Using the condition that there exists exactly one common index between
$\\{\tau(1),\tau(2),\tau(3),\tau(4)\\}$ and
$\\{\tau^{\prime}(1),\tau^{\prime}(2),\tau^{\prime}(3),\tau^{\prime}(4)\\}$
(without loss of generality, let the shared common index be between
$\\{\tau(1),\tau(2)\\}$ and $\\{\tau^{\prime}(1),\tau^{\prime}(2)\\}$), the
above expectation becomes

$\displaystyle\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\sum_{x^{\prime}\in[\ell_{1}],y^{\prime}\in[\ell_{2}]}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\psi^{m,\bm{\pi}}_{\tau^{\prime}(1)\tau^{\prime}(2)}(x^{\prime},y^{\prime})\big{]}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\big{]}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau^{\prime}(3)\tau^{\prime}(4)}(x^{\prime},y^{\prime})\big{]}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\sqrt{\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\sum_{x^{\prime}\in[\ell_{1}],y^{\prime}\in[\ell_{2}]}\Big{\\{}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\psi^{m,\bm{\pi}}_{\tau^{\prime}(1)\tau^{\prime}(2)}(x^{\prime},y^{\prime})\big{]}\Big{\\}}^{2}}\times$
$\displaystyle\sqrt{\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\sum_{x^{\prime}\in[\ell_{1}],y^{\prime}\in[\ell_{2}]}\Big{\\{}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\big{]}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau^{\prime}(3)\tau^{\prime}(4)}(x^{\prime},y^{\prime})\big{]}\Big{\\}}^{2}},$

where the second step follows by Cauchy–Schwarz inequality. Now, based on the
notation used in (62)

$\displaystyle\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\Big{\\{}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\big{]}\Big{\\}}^{2}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\max_{k_{1},k_{2}\in[b]}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\Big{\\{}p_{m,k_{1}}(x)q_{m,k_{1}}(x)-p_{m,k_{1}}(x)q_{m,k_{2}}(x)\Big{\\}}^{2}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\max_{k_{1},k_{2}\in[b]}\mathcal{D}_{\mathrm{TV}}^{2}(q_{m,k_{1}},q_{m,k_{2}})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \frac{C_{1}}{M^{2}}.$ (66)

This bound gives

$\displaystyle\mathbb{E}[h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}}h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(M^{-2}\right).$ (67)

Next we look at the product of the expectations

$\displaystyle\mathbb{E}[h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}}]\times\mathbb{E}[h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\mathbb{E}\Bigg{[}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\Bigg{]}\times\mathbb{E}\Bigg{[}\sum_{x^{\prime}\in[\ell_{1}],y^{\prime}\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\tau^{\prime}(1)\tau^{\prime}(2)}(x^{\prime},y^{\prime})\psi^{m,\bm{\pi}}_{\tau^{\prime}(3)\tau^{\prime}(4)}(x^{\prime},y^{\prime})\Bigg{]}.$

By focusing on the first term, Cauchy–Schwarz inequality together with the
previous bound (66) yields

$\displaystyle\Bigg{|}\mathbb{E}\Bigg{[}\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\Bigg{]}\Bigg{|}$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ $
$\displaystyle\sqrt{\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\Big{\\{}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(1)\tau(2)}(x,y)\big{]}\Big{\\}}^{2}}\times\sqrt{\sum_{x\in[\ell_{1}],y\in[\ell_{2}]}\Big{\\{}\mathbb{E}\big{[}\psi^{m,\bm{\pi}}_{\tau(3)\tau(4)}(x,y)\big{]}\Big{\\}}^{2}}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle\frac{C_{2}}{M^{2}}.$

The other term can be similarly analyzed and thus

$\displaystyle\mathbb{E}[h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}}]\times\mathbb{E}[h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\ O\left(M^{-4}\right).$

Combining the above with the bound (67) yields the claim (65).

Suppose that there are at least one collision among

$\displaystyle\\{$
$\displaystyle(X_{i_{1},m},Y_{\pi_{i_{1},m}}),(X_{i_{2},m},Y_{\pi_{i_{2},m}}),(X_{i_{3},m},Y_{\pi_{i_{3},m}}),(X_{i_{4},m},Y_{\pi_{i_{4},m}}),$
$\displaystyle(X_{j_{1},m},Y_{\pi_{j_{1},m}}),(X_{j_{2},m},Y_{\pi_{j_{2},m}}),(X_{j_{3},m},Y_{\pi_{j_{3},m}}),(X_{j_{4},m},Y_{\pi_{j_{4},m}})\\}.$

where $\\{i_{1},i_{2},i_{3},i_{4},j_{1},j_{2},j_{3},j_{4}\\}\in
A_{\mathrm{com}}^{1}$. The number of such cases is at most
$O(\sigma_{m}^{6})$. Therefore

$\displaystyle\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{1}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\frac{1}{\sigma_{m}M^{2}}+\frac{1}{\sigma_{m}^{2}}\right).$

Lastly we focus on the case when
$\\{i_{1},i_{2},i_{3},i_{4},j_{1},j_{2},j_{3},j_{4}\\}\in
A_{\mathrm{com}}^{0}$. First of all, when there is no collision, two kernels
become independent and thus
$\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})=0$.
When there is one collision, we are basically in the same situation where
$\\{i_{1},i_{2},i_{3},i_{4},j_{1},j_{2},j_{3},j_{4}\\}\in
A_{\mathrm{com}}^{1}$ and there is no collision. Therefore we can re-use the
previous bound for the covariance (65). Furthermore, since there are at most
$O(\sigma_{m}^{7})$ cases of one collision, $O(\sigma_{m}^{6})$ of two
collisions and so on, we have

$\displaystyle\frac{1}{\binom{\sigma_{m}}{4}^{2}}\sum_{A_{\mathrm{com}}^{0}}\mathrm{Cov}(h_{i_{1},i_{2},i_{3},i_{4}}^{m,\bm{\pi}},h_{j_{1},j_{2},j_{3},j_{4}}^{m,\bm{\pi}})\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\frac{1}{\sigma_{m}M^{2}}+\frac{1}{\sigma_{m}^{2}}\right).$

Therefore, combining the results yields

$\displaystyle\mathrm{Var}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\frac{1}{\sigma_{m}M^{2}}+\frac{1}{\sigma_{m}^{2}}\right).$

Given the above bound, the variance of the combined test statistic is

$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\
\mathbb{E}\big{[}\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}+\mathrm{Var}\big{[}\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}.$

Let us upper bound these two terms separately. Starting with the first term,
note that

$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\leavevmode\nobreak\
=\leavevmode\nobreak\ $ $\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\times\mathrm{Var}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]$
$\displaystyle=\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq 4)\sigma_{m}^{2}\times
O\left(\frac{1}{\sigma_{m}M^{2}}+\frac{1}{\sigma_{m}^{2}}\right),$

which results in

$\displaystyle\mathbb{E}\big{[}\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}=O\left(\frac{n}{M^{2}}+M\right).$
(68)

For the second term,

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\leavevmode\nobreak\
=\leavevmode\nobreak\ \sum_{m\in[M]}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}\times\mathbb{E}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}].$

Since $\sigma_{1},\ldots,\sigma_{M}$ are independent,

$\displaystyle\mathrm{Var}\big{[}\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathrm{Var}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}\times\mathbb{E}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]\big{]}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\times\big{\\{}\mathbb{E}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]\big{\\}}^{2}\big{]}.$

Recall from the claim (61) that

$\displaystyle\mathbb{E}[U(\bm{W}_{m}^{\bm{\pi}})|\sigma_{m}]=O\left(\frac{1}{M^{2}}+\frac{1}{M\sigma_{m}}+\frac{1}{\sigma_{m}^{2}}\right)\quad\text{for
each $m\in[M]$.}$ (69)

Therefore

$\displaystyle\mathrm{Var}\big{[}\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\ $
$\displaystyle\frac{C_{1}}{M^{4}}\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\big{]}+\frac{C_{2}}{M^{2}}\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\big{]}$ $\displaystyle+\leavevmode\nobreak\ $ $\displaystyle
C_{3}\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{-2}\big{]}.$

Now using the property that
$\sigma_{m}\overset{\mathrm{i.i.d.}}{\sim}\text{Pois}(np_{m})$ where
$\sum_{m=1}^{M}p_{m}=1$ and $p_{m}\geq 0$, we can upper bound

$\displaystyle\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{2}\big{]}\leq\sum_{m\in[M]}np_{m}+n^{2}p_{m}^{2}\leq
n+n^{2}\quad\text{and}$
$\displaystyle\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\big{]}\leq\sum_{m\in[M]}\mathbb{E}[\sigma_{m}]\leq n.$

Furthermore, the inequality (64) implies that

$\displaystyle\sum_{m\in[M]}\mathbb{E}\big{[}\mathds{1}(\sigma_{m}\geq
4)\sigma_{m}^{-2}\big{]}\leavevmode\nobreak\ \leq\leavevmode\nobreak\
O\left(\frac{M^{2}}{n}\right).$

Putting pieces together yields

$\displaystyle\mathrm{Var}\big{[}\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}|\bm{\sigma}]\big{]}\leavevmode\nobreak\
\leq\leavevmode\nobreak\
O\left(\frac{n^{2}}{M^{4}}+\frac{n}{M^{2}}+\frac{M^{2}}{n}\right).$

Combining the above with (68) concludes

$\displaystyle\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]\leavevmode\nobreak\
=\leavevmode\nobreak\
O\left(\frac{n^{2}}{M^{4}}+\frac{n}{M^{2}}+\frac{M^{2}}{n}+M\right).$

Step 4. Completing the proof. Now by taking $M=\lceil n^{2/5}\rceil$, the
previous bounds for the mean and the variance yield

$\displaystyle\mathbb{E}[T_{\mathrm{CI}}^{\bm{\pi}}]+\sqrt{\mathrm{Var}[T_{\mathrm{CI}}^{\bm{\pi}}]}\leavevmode\nobreak\
=\leavevmode\nobreak\ O\big{(}n^{1/5}\big{)}.$

This together with the inequality (60) gives

$\displaystyle\mathbb{P}(T_{\mathrm{CI}}\leq q_{1-\alpha})\leavevmode\nobreak\
\leq\leavevmode\nobreak\ \mathbb{P}\big{(}T_{\mathrm{CI}}\lesssim
n^{1/5}\big{)}+\frac{1}{200}+\mathbb{P}(\mathcal{A}^{c}).$

Finally, we prove that $\mathbb{P}(\mathcal{A}^{c})$ converges to zero
uniformly over a class of distributions of
$(X,Y,Z)\in[\ell_{1}]\times[\ell_{2}]\times[0,1]$ where the density of $Z$ is
lower bounded by some small constant $c_{\mathrm{low}}>0$. In particular, we
recall the event $\mathcal{A}$ in (58) and define

$\displaystyle\rho_{n}:=\sup_{P_{X,Y,Z}\in\mathcal{P}^{\prime}_{1,[0,1],\mathrm{TV}}(L)}\mathbb{P}_{P_{X,Y,Z}^{N},N}(\mathcal{A}^{c}).$
(70)

We then show that $\rho_{n}\rightarrow 0$ under the conditions in Theorem 8.

By letting $\sigma_{m,k}$ be the sample size within the bin $B_{m,k}$ and
$\tau_{\alpha}>\log^{-1}((1-\alpha/2)/(1-\alpha))$, let us define another
event $\mathcal{E}$ in which
$\min_{(m,k)\in[M]\times[b]}\sigma_{m,k}\geq\tau_{\alpha}\times(Mb)$. Note
that, under Poissonization, each $\sigma_{m,k}\sim\text{Pois}(np_{m,k})$ where
$np_{m,k}\geq c_{\mathrm{low}}n/(Mb)$ since the density of $Z$ is bounded
below by $c_{\mathrm{low}}$. We further assume that
$c_{\mathrm{low}}n/(Mb)\geq 2\tau_{\alpha}\times(Mb)$. Then, by Lemma 7 in
Appendix B.3, the event $\mathcal{E}$ holds with probability at least

$\displaystyle 1-\sum_{(m,k)\in[M]\times[b]}e^{-\frac{np_{m,k}}{6}}\geq
1-Mb\times e^{-\frac{c_{\mathrm{low}}n}{6Mb}}.$

This probability converges to one as $n\rightarrow\infty$ as long as $M,b$ are
chosen such that $n/(Mb)\rightarrow\infty$. Therefore, we can work under the
assumption that
$\min_{(m,k)\in[M]\times[b]}\sigma_{m,k}\geq\tau_{\alpha}\times(Mb)$. Under
this event $\mathcal{E}$ with $\tau_{\alpha}(Mb)\geq 2$ (this can be assumed
as $Mb\rightarrow\infty$), $\mathbb{P}(\mathcal{A}^{c}|\mathcal{E})$ is
equivalent to

$\displaystyle\mathbb{P}\Bigg{(}\frac{\prod_{(m,k)\in[M]\times[b]}\max\\{\sigma_{m,k}-1,1\\}}{\prod_{(m,k)\in[M]\times[b]}\max\\{\sigma_{m,k},1\\}}\leq\frac{1-\alpha}{1-\alpha/2}\bigg{|}\mathcal{E}\Bigg{)}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}\Bigg{(}\prod_{(m,k)\in[M]\times[b]}(1-\sigma_{m,k}^{-1})\leq\frac{1-\alpha}{1-\alpha/2}\bigg{|}\mathcal{E}\Bigg{)}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathds{1}\Bigg{(}\big{(}1-\tau_{\alpha}^{-1}(Mb)^{-1}\big{)}^{Mb}\leq\frac{1-\alpha}{1-\alpha/2}\Bigg{)}.$

Given that $\tau_{\alpha}>\log((1-\alpha/2)/(1-\alpha))$ and
$(1-a/n)^{n}\rightarrow e^{-a}$ for any constant $a$, the last display
converges to zero as $Mb\rightarrow\infty$. Finally, as we argued before, we
have $\mathbb{P}(\mathcal{E}^{c})\rightarrow 0$. Therefore

$\displaystyle\mathbb{P}(\mathcal{A}^{c})\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}(\mathcal{A}^{c}|\mathcal{E})\mathbb{P}(\mathcal{E})+\mathbb{P}(\mathcal{A}^{c}|\mathcal{E}^{c})\mathbb{P}(\mathcal{E}^{c})$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\mathbb{P}(\mathcal{A}^{c}|\mathcal{E})+\mathbb{P}(\mathcal{E}^{c})\rightarrow
0,$

as desired. Since we set $\alpha=0.01$, we can take
$\tau_{\alpha}=200>\log^{-1}((1-\alpha/2)/(1-\alpha))\approx 198.5$ and the
above conditions are satisfied when $n/(Mb)^{2}\geq 400c_{\mathrm{low}}^{-1}$
and $Mb\rightarrow\infty$ as $n\rightarrow\infty$. These are the conditions
imposed in Theorem 8 and thus we complete the proof of Theorem 8.

##  Appendix B Auxiliary lemmas and additional results

This section collects some auxiliary lemmas used for the main proofs as well
as additional results.

###  B.1 Metrics and inequalities

The next lemma connects the Hellinger distance between binned distributions
$Q_{X,Y|\widetilde{Z}=m}$ and $\widetilde{Q}_{X,Y|\widetilde{Z}=m}$, defined
in Section 4.2, to that between the underlying conditional distributions. This
lemma is the basis for the proof of Theorem 2 and Theorem 3.

######  Lemma 3 (A bound on the Hellinger distance).

For each $m=1,\ldots,M$, we let $Z_{m}$ denote a random variable from the
conditional distribution $Z|Z\in B_{m}$, and we let
$Z_{m}^{{}^{\prime}},Z_{m}^{{}^{\prime\prime}}$ be i.i.d. copies of $Z_{m}$.
Then under $X\mathchoice{\mathrel{\hbox
to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y|Z$, it holds that

$\displaystyle\mathcal{D}_{\text{\emph{H}}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}$
$\displaystyle\leq\leavevmode\nobreak\ $ $\displaystyle
6\mathbb{E}_{Z_{m},Z_{m}^{{}^{\prime}},Z_{m}^{{}^{\prime\prime}}}\big{[}\mathcal{D}_{\text{\emph{H}}}^{2}\big{(}P_{X|Z=Z_{m}},P_{X|Z=Z_{m}^{{}^{\prime}}}\big{)}\times\mathcal{D}_{\text{\emph{H}}}^{2}\big{(}P_{Y|Z=Z_{m}},P_{Y|Z=Z_{m}^{{}^{\prime\prime}}}\big{)}\big{]}.$

It is interesting to observe that Lemma 3 connects the distance between the
joint conditional distributions of the binned data to the distances between
the marginal conditional distributions of the unbinned data. In particular,
the upper bound consists of the product between two distances, which allows us
to control the type I error more tightly. The constant factor of $6$ is a
convenient choice from our analysis and it is by no means tight. To prove this
result, we use Jensen’s inequality for a vector valued function and the proof
can be found in Appendix D.1.

The next lemma presents an inclusion property of the generalized Hellinger
distance, which is useful for the proof of Theorem 2.

######  Lemma 4 (Generalized Hellinger distance).

For any $1\leq\gamma_{1}\leq\gamma_{2}$, we have

$\displaystyle\mathcal{D}_{\gamma_{2},\text{\emph{H}}}^{\gamma_{2}}(P,Q)\leq\mathcal{D}_{\gamma_{1},\text{\emph{H}}}^{\gamma_{1}}(P,Q).$
(71)

On the other hand, for any $\gamma\geq 1$ and $1\leq\alpha\leq 2$, it holds
that

$\displaystyle\mathcal{D}_{\gamma,\text{\emph{H}}}(P,Q)\leq
2^{1-1/\gamma+1/(\gamma\alpha)}\mathcal{D}_{\gamma\alpha,\text{\emph{H}}}(P,Q).$
(72)

We note that the first inequality (71) was proved in Kamps, (1989) and, as far
as we are aware, the second inequality (72) is new in the literature. In
particular, the inequality (72) generalizes the well-known inequality between
the TV distance and the Hellinger distance:

$\displaystyle\mathcal{D}_{\mathrm{TV}}(P,Q)\leq\sqrt{2}\mathcal{D}_{\mathrm{H}}(P,Q),$

by taking $\gamma=1$ and $\alpha=2$. The proof of Lemma 4 can be found in
Appendix D.2. As a direct consequence of Lemma 4, we have the following
corollary.

######  Corollary 1 (A bound on the Hellinger distance).

Suppose that $\gamma>2$ is within the range of $2^{k}<\gamma\leq 2^{k+1}$ for
some positive integer $k$. Then

$\displaystyle\mathcal{D}_{\text{\emph{H}}}(P,Q)\leq
2^{k}\mathcal{D}_{\gamma,\text{\emph{H}}}(P,Q).$ (73)

Next we state a few inequalities related to Rényi divergence, which will be
useful for the proof of Theorem 3. Let $\mathcal{D}_{\text{KL}}(P\|Q)=\int
p\log(p/q)d\mu$ and $\mathcal{D}_{\chi^{2}}(P\|Q)=\int(p-q)^{2}/qd\mu$ be the
KL divergence and the $\chi^{2}$ divergence of $P$ from $Q$, respectively.
Then we have the identities:

$\displaystyle\mathcal{D}_{1/2\text{,R{\'{e}}nyi}}(P\|Q)=-2\log\\{1-\mathcal{D}_{\mathrm{H}}^{2}(P,Q)/2\\},$
$\displaystyle\mathcal{D}_{1\text{,R{\'{e}}nyi}}(P\|Q)=\mathcal{D}_{\text{KL}}(P\|Q),$
$\displaystyle\mathcal{D}_{2\text{,R{\'{e}}nyi}}(P\|Q)=\log\\{1+\mathcal{D}_{\chi^{2}}(P\|Q)\\}.$

Notice that $\mathcal{D}_{\gamma,\text{R{\'{e}}nyi}}(P\|Q)$ is nondecreasing
in $\gamma$ and thus, by the inequality $\log t\leq t-1$ for all $t>0$, we
have

$\displaystyle\mathcal{D}_{\mathrm{H}}^{2}(P,Q)\leq\mathcal{D}_{1/2\text{,R{\'{e}}nyi}}(P\|Q)\leq\mathcal{D}_{\text{KL}}(P\|Q)=R_{1}(f\|g)\leq\mathcal{D}_{2\text{,R{\'{e}}nyi}}(P\|Q)\leq\mathcal{D}_{\chi^{2}}(P\|Q).$
(74)

Other notable inequalities are

$\displaystyle\frac{\gamma_{1}}{1-\gamma_{1}}\frac{1-\gamma_{2}}{\gamma_{2}}\mathcal{D}_{\gamma_{2}\text{,R{\'{e}}nyi}}(P\|Q)\leq\mathcal{D}_{\gamma_{1}\text{,R{\'{e}}nyi}}(P\|Q)\leq\mathcal{D}_{\gamma_{2}\text{,R{\'{e}}nyi}}(P\|Q)\quad\text{for
$0<\gamma_{1}<\gamma_{2}<1$}.$

Based on the above inequalities, we can upper bound the Hellinger distance by
Rényi divergence as follows.

######  Lemma 5 (Rényi divergence).

For any $\gamma\geq 1/2$, we have

$\displaystyle\mathcal{D}_{\text{\emph{H}}}^{2}(P,Q)\leq\mathcal{D}_{\gamma,\text{\emph{R{\'{e}}nyi}}}(P\|Q).$

On the other hand, for $0<\gamma<1/2$, it holds that

$\displaystyle\mathcal{D}_{\text{\emph{H}}}^{2}(P,Q)\leq\mathcal{D}_{1/2,\text{\emph{R{\'{e}}nyi}}}(P\|Q)\leq\frac{1-\gamma}{\gamma}\mathcal{D}_{\gamma,\text{\emph{R{\'{e}}nyi}}}(P\|Q).$

The proof of the above lemma can be found in Van Erven and Harremos, (2014).

###  B.2 Connection between permutation $p$-value and quantile

The next lemma provides an alternative expression of the permutation test in
terms of the quantile of the permutation distribution, which is more intuitive
to analyze.

######  Lemma 6 (Quantile).

Recall the permutation $p$-value $p_{\text{\emph{perm}}}$ in (3). Let
$q_{1-\alpha}$ be the $1-\alpha$ quantile of the empirical distribution of
$T_{\text{\emph{CI}}}^{\bm{\pi}_{1}},\ldots,T_{\text{\emph{CI}}}^{\bm{\pi}_{K}}$.
Then it holds that

$\displaystyle\mathds{1}(p_{\text{\emph{perm}}}>\alpha)=\mathds{1}(T_{\text{\emph{CI}}}\leq
q_{1-\alpha}).$

Furthermore, by letting $k=\lceil(1-\alpha)K\rceil$, $q_{1-\alpha}$ is the
same as the $k$th order statistic $T_{\mathrm{CI}}^{\bm{\pi}_{(k)}}$ of
$T_{\text{\emph{CI}}}^{\bm{\pi}_{1}},\ldots,T_{\text{\emph{CI}}}^{\bm{\pi}_{K}}$.

The proof of this result follows by the definition of the quantile function
and the details can be found in Appendix D.3.

###  B.3 Poissonization

In the following proposition, we demonstrate that the local permutation test
under Poissonization has the same validity as before.

######  Proposition 2 (Validity under Poissonization).

Let $\mathcal{P}_{0}^{\prime}\subset\mathcal{P}_{0}$ be the collection of
distributions for which it holds that
$\sup_{P_{X,Y,Z}\in\mathcal{P}_{0}^{\prime}}\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi_{\text{\emph{perm}},n}]\leq\alpha+C_{1}n^{-\epsilon}$
where $C_{1}>0$ is a universal constant, $\epsilon>0$ and $n\geq 1$. We
further let $\phi_{\text{\emph{perm}},n}=0$ when $n=0$. Then under
Poissonization where $N\sim\text{\emph{Pois}}(n)$, the local permutation test
has the type I error guarantee as

$\displaystyle\sup_{P_{X,Y,Z}\in\mathcal{P}_{0}^{\prime}}\mathbb{E}_{P_{X,Y,Z}^{N},N}[\phi_{\text{\emph{perm}},N}]\leq\alpha+C_{2}(\epsilon)\cdot
n^{-\epsilon}+ne^{-n/12},$

where $C_{2}(\epsilon)>0$ is a constant that only depends on $\epsilon$.

The proof of Proposition 2 uses the fact that a Poisson random variable is
tightly concentrated around its mean, and the details can be found in Appendix
D.4. Suppose we choose the maximum diameter $h$ such that the upper bounds in
Theorem 2 and Theorem 3 converge to $\alpha$ at a certain rate. Then
Proposition 2 essentially implies that the same convergence rate of the type I
error can be obtained under Poissonization as well.

The following lemma provides a concentration bound for the minimum of Poisson
random variables.

######  Lemma 7 (Poisson concentration).

For $m=1,\ldots,M$, let $X_{m}$ be a Poisson random variable with parameter
$\lambda_{m}\geq c_{0}$. Then

$\displaystyle\mathbb{P}\Big{(}\min_{m\in[M]}X_{m}\leq
c_{0}/2\Big{)}\leq\sum_{m=1}^{M}e^{-\frac{\lambda_{m}}{6}}.$

###  B.4 Unbounded support of $Z$

In this subsection, we discuss how to deal with unbounded support of $Z$ for
type I error control. In particular, we demonstrate that it is possible to
obtain similar validity results as in Theorem 2 and Theorem 3, up to a
vanishing term in the sample size, even when the support of the conditional
variable $Z$ is unbounded.

To fix ideas, suppose $Z$ is a univariate random variable and let
$\\{B_{1},\ldots,B_{M}\\}$ denote a partition of $[a,b]$ for some
$a,b\in\mathbb{R}$. We further denote the complement of $\cup_{i=1}^{M}B_{i}$
by $B_{M+1}=(-\infty,a)\cup(b,\infty)$ so that
$\cup_{i=1}^{M+1}B_{i}=\mathbb{R}$. Under this setting, the permutation test
that builds on partitions $\\{B_{1},\ldots,B_{M+1}\\}$ has the same type I
error guarantee as those in Theorem 2 and Theorem 3 except that we have an
additional term to control:
$nq_{\widetilde{Z}}(m+1)\times\mathcal{D}_{\mathrm{H}}^{2}(Q_{X,Y|\widetilde{Z}=m+1},\widetilde{Q}_{X,Y|\widetilde{Z}=m+1})$.
In particular, since the Hellinger distance is bounded by one, this extra term
goes to zero as long as $nq_{\widetilde{Z}}(m+1)\rightarrow 0$ as
$n\rightarrow\infty$. Therefore, the problem boils down to controlling
$nq_{\widetilde{Z}}(m+1)$. We discuss two strategies to handle this depending
on whether there exists prior knowledge on the distribution of $Z$.

  1. 1.

Prior information on $Z$. Suppose that we have prior knowledge on the
distribution of $Z$. To fix ideas, suppose that $Z$ has an exponential tail
such that $\mathbb{P}(|Z|>t)\leq Ce^{-t}$ for some $C>0$ and for all $t\geq
0$. Then by choosing $b$ sufficiently larger than $\log n$ and by letting
$a=-b$, it is guaranteed that the extra term vanishes as
$nq_{\widetilde{Z}}(m+1)\rightarrow 0$.

  2. 2.

Sample splitting. When there is no information on the distribution of $Z$ a
priori, we may choose $a$ and $b$ in a data-dependent way. In detail, we split
the sample into two sets of size $n_{1}$ and $n_{2}$, denoted by $D_{1}$ and
$D_{2}$, respectively. Let $Z_{(1)}$ and $Z_{(n_{1})}$ be the minimum and the
maximum order statistic of the first set $D_{1}$ and let $a=Z_{(1)}$ and
$b=Z_{(n_{1})}$. We then work with the second set $D_{2}$ to perform the local
permutation test. Provided that $Z$ has a density with respect to the Lebesgue
measure, it can be seen that $\mathbb{P}(Z<Z_{(1)})=\frac{1}{n_{1}+1}$ and
$\mathbb{P}(Z>Z_{(n_{1})})=\frac{1}{n_{1}+1}$ where $Z$ is independent of
$D_{1}$. Note that
$q_{\widetilde{Z}}(m+1)=\mathbb{P}(Z<Z_{(1)}|D_{1})+\mathbb{P}(Z>Z_{(n_{1})}|D_{1})$
and therefore $\mathbb{E}_{D_{1}}[q_{\widetilde{Z}}(m+1)]=\frac{2}{n_{1}+1}$.
In view of (6), the type I error is bounded by

$\displaystyle\mathbb{E}_{P_{X,Y,Z}^{n}}[\phi_{\mathrm{perm},n_{2}}]=\mathbb{E}_{D_{1}}[\mathbb{E}_{D_{2}}[\phi_{\mathrm{perm},n_{2}|D_{1}}]]$
$\displaystyle\leavevmode\nobreak\ \leq\leavevmode\nobreak\ $
$\displaystyle\alpha+\mathbb{E}_{D_{1}}\Bigg{[}\Bigg{\\{}2n_{2}\sum_{m=1}^{M+1}q_{\widetilde{Z}}(m)\times\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}\Bigg{\\}}^{1/2}\Bigg{]}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\alpha+\underbrace{\mathbb{E}_{D_{1}}\Bigg{[}\Bigg{\\{}2n_{2}\sum_{m=1}^{M}q_{\widetilde{Z}}(m)\times\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}\Bigg{\\}}^{1/2}\Bigg{]}}_{(\mathrm{I})}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\
+\underbrace{\mathbb{E}_{D_{1}}\Bigg{[}\Bigg{\\{}2n_{2}q_{\widetilde{Z}}(M+1)\times\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=M+1},\widetilde{Q}_{X,Y|\widetilde{Z}=M+1}\big{)}\Bigg{\\}}^{1/2}\Bigg{]}}_{(\mathrm{II})}.$

The first term $(\mathrm{I})$ can be handled similarly as in the bounded case.
For the second term $(\mathrm{II})$, it can be seen that
$(\mathrm{II})\leq\sqrt{\frac{4n_{2}}{n_{1}+1}}$ by using the fact that the
Hellinger distance is bounded by one together with Jensen’s inequality. Thus,
the second term is asymptotically vanishing as long as $n_{2}/n_{1}\rightarrow
0$ as $n\rightarrow\infty$.

##  Appendix C Definitions

We recall a Hölder smoothness class from Neykov et al., (2021), which is used
to analyze the local permutation test for continuous data.

######  Definition 5 (Hölder Smoothness).

Let $s>0$ be a fixed real number, and let $\lfloor s\rfloor$ denote the
maximum integer strictly smaller than $s$. Denote by $\mathcal{H}^{2,s}(L)$,
the class of functions $f:[0,1]^{2}\mapsto\mathbb{R}$, which posses all
partial derivatives up to order $\lfloor s\rfloor$ and for all
$x,y,x^{\prime},y^{\prime}\in[0,1]$ we have

$\displaystyle\sup_{k\leq\lfloor s\rfloor}\bigg{|}\frac{\partial^{k}}{\partial
x^{k}}\frac{\partial^{\lfloor s\rfloor-k}}{\partial y^{\lfloor
s\rfloor-k}}f(x,y)-\frac{\partial^{k}}{\partial x^{k}}\frac{\partial^{\lfloor
s\rfloor-k}}{\partial y^{\lfloor
s\rfloor-k}}f(x^{\prime},y^{\prime})\bigg{|}\leq
L((x-x^{\prime})^{2}+(y-y^{\prime})^{2}))^{\frac{s-\lfloor s\rfloor}{2}},$

and in addition

$\displaystyle\sup_{k\leq\lfloor s\rfloor}\bigg{|}\frac{\partial^{k}}{\partial
x^{k}}\frac{\partial^{\lfloor s\rfloor-k}}{\partial y^{\lfloor
s\rfloor-k}}f(x,y)\bigg{|}\leq L.$

The next definition describes a cyclic permutation used in Section 6.

######  Definition 6 (Cyclic permutation).

For a set $\mathcal{X}$ with finite elements $a_{0},a_{2},\ldots,a_{n-1}$, a
cyclic permutation $\pi$ is a bijective function from $\mathcal{X}$ to
$\mathcal{X}$ such that for some integer $k$, $\pi(a_{i})=a_{(i+k)\bmod n}$.

##  Appendix D Proofs of the auxiliary lemmas

This section collects the proof of the lemmas in Appendix B.

###  D.1 Proof of Lemma 3

To ease the notation, we suppress $(x,y|m)$ in $q_{XY|\widetilde{Z}}(x,y|m)$
and write $q_{XY|\widetilde{Z}}$. Similarly, we write
$q_{X\cdot|\widetilde{Z}}(x|m)$ and $q_{\cdot Y|\widetilde{Z}}(y|m)$ by
$q_{X\cdot|\widetilde{Z}}$ and $q_{\cdot Y|\widetilde{Z}}$, respectively.
Using this shorthand notation, consider an alternative expression of the
Hellinger distance and its upper bounds

$\displaystyle
2\mathcal{D}_{\mathrm{H}}^{2}\big{(}Q_{X,Y|\widetilde{Z}=m},\widetilde{Q}_{X,Y|\widetilde{Z}=m}\big{)}\leavevmode\nobreak\
=\leavevmode\nobreak\ $
$\displaystyle\int\int\big{(}\sqrt{q_{XY|\widetilde{Z}}}-\sqrt{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}\big{)}^{2}d\mu_{X}d\mu_{Y}$
$\displaystyle\leavevmode\nobreak\ =\leavevmode\nobreak\ $
$\displaystyle\int\int\frac{\big{(}{q_{XY|\widetilde{Z}}}-{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}\big{)}^{2}}{\big{(}\sqrt{q_{XY|\widetilde{Z}}}+\sqrt{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}\big{)}^{2}}d\mu_{X}d\mu_{Y}$
$\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle\int\int\frac{\big{(}{q_{XY|\widetilde{Z}}}-{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}\big{)}^{2}}{{q_{XY|\widetilde{Z}}}+{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}}d\mu_{X}d\mu_{Y}$ $\displaystyle\leq\leavevmode\nobreak\ $
$\displaystyle
3\int\int\frac{\big{(}{q_{XY|\widetilde{Z}}}-{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}\big{)}^{2}}{{q_{XY|\widetilde{Z}}}+3{q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}}}d\mu_{X}d\mu_{Y}.$

Under $X\mathchoice{\mathrel{\hbox to0.0pt{$\displaystyle\perp$\hss}\mkern
2.0mu{\displaystyle\perp}}}{\mathrel{\hbox
to0.0pt{$\textstyle\perp$\hss}\mkern 2.0mu{\textstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptstyle\perp$\hss}\mkern
2.0mu{\scriptstyle\perp}}}{\mathrel{\hbox
to0.0pt{$\scriptscriptstyle\perp$\hss}\mkern
2.0mu{\scriptscriptstyle\perp}}}Y|Z$, the term inside of the last expression
is equivalent to

$\displaystyle\frac{\big{(}q_{XY|\widetilde{Z}}-q_{X\cdot|\widetilde{Z}}q_{\cdot
Y|\widetilde{Z}}\big{)}^{2}}{q_{XY|\widetilde{Z}}+3q_{X\cdot|\widetilde{Z}}q_{\cdot