Lower bound for testing closeness in $L_2$ norm? I was wondering if there was any lower bound (in terms of sample complexity) known for the following problem:

Given sample oracle access to two unknown distributions $D_1$, $D_2$ on $\{1,\dots,n\}$, test (whp) whether


$D_1=D_2$
or $\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon$


Batu et al. [BFR+00] showed that $O\left(\frac{1}{\epsilon^4}\right)$ samples were sufficient, but I haven't found any mention of a lower bound?

I reckon one could always show a $\Omega(\frac{1}{\epsilon^2})$ lower bound by reducing the task of distinguishing a fair vs. $\epsilon$-biased coin to this problem (simulating a distribution supported on only two points, and answering the queries of the tester according to the iid coin tosses), but that still leaves a quadratic gap...

(Another point I'd be interested in is a lower bound in estimating (up to an additive $\epsilon$) this $L_2$ distance — again, I have found no reference to such result in the literature)

Thanks for your help,
It appears that $O(1/\epsilon^2)$ samples — as usul showed below — is enough for testing, so that the sample complexity is exactly $\Theta(1/\epsilon^2)$; actually, it turns out this number of samples us even enough for learning $D$ up to an additive $\epsilon$ wrt the $L_2$ norm.



Let $\hat{D}$ be the empirical density function obtained by drawing $m$ i.i.d. samples $s_1,\dots, s_m\sim D$ and setting
$$
\hat{D}(k) \stackrel{\rm{}def}{=} \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}},\qquad k\in[n]
$$
Then
$$
\begin{align*}
\lVert D - \hat{D} \rVert_2^2 &amp;= \sum_{k=1}^n \left( \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - D(k) \right)^2 = \frac{1}{m^2}\sum_{k=1}^n \left( \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - mD(k) \right)^2 \\
&amp;= \frac{1}{m^2}\sum_{k=1}^n \left( X_k - \mathbb{E} X_k \right)^2
\end{align*}
$$
where $X_k\stackrel{\rm{}def}{=} \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}}\sim\operatorname{Bin}( m, D(k) )$. The $X_k$'s (for $k\in[n]$) are not independent, but we can write
$$
\begin{align*}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 &amp;= \frac{1}{m^2}\sum_{k=1}^n \mathbb{E}\left[ \left( X_k - \mathbb{E} X_k \right)^2 \right]
= \frac{1}{m^2}\sum_{k=1}^n \operatorname{Var} X_k \\
 &amp;= \frac{1}{m^2}\sum_{k=1}^n mD(k)\left( 1- D(k) \right) \leq \frac{1}{m}\sum_{k=1}^n D(k) \\
&amp;= \frac{1}{m}
\end{align*}
$$
so that for $m\geq \frac{3}{\epsilon^2}$, 
\begin{equation}
\mathbb{E}\lVert D - \hat{D} \rVert_2^2 \leq \frac{\epsilon^2}{3}
\end{equation}
and applying Markov's inequality
\begin{equation}
\mathbb{P}\left\{ \lVert D - \hat{D} \rVert_2 \geq \epsilon \right\} \leq \frac{1}{3}.
\end{equation}