How large sample $m$ is enough [closed]

Question

I have a $D$ probability distribution over $X =R^d$, i have two samples $s_1$ and $s_2$ from $D$, each having size $m_1$, $m_2$, a unit ball centered at origin $B(0)$, defined by $B(0)=\{x \in R^2: \|x\|_2 \leqslant 1\}$, How large is enough for $m$ to be, so that we can make sure that with probability at least $\epsilon$ we have $m \leqslant \delta$? any hints?

Answer 1

$\newcommand\ep\epsilon\newcommand\de\delta\newcommand\bar\overline$We have $(n_1-n_2)m=S_m:=Z_1+\cdots+Z_m$, where $Z_i:=X_i-Y_i$, and $X_1,\dots,X_m,Y_1,\dots,Y_m$ are iid Bernoulli random variables (r.v.'s) with parameter $p:=D(B(0))$ -- the probability for a sample item from distribution $D$ to be in $B(0)$. So, the $Z_i$'s are iid r.v.'s with $EZ_i=0$ and $Var\,Z_i=2pq$, where $q:=1-p$. So, by the central limit theorem, $$\de=P(|n_1-n_2|>\ep)=P(|S_m|>\ep m)\approx2\bar\Phi\Big(\frac{\ep m}{\sqrt{2pqm}}\Big)=2\bar\Phi\Big(\ep\sqrt{\frac m{2pq}}\Big),$$ where $\bar\Phi:=1-\Phi$ and $\Phi$ is the standard normal cdf.

Solving this for $m$, we get $$m\approx\frac{2pq}{\ep^2}\,\bar\Phi^{-1}(\de/2)^2.$$

Details in response to OP's comments:

1. We deal with $Z_i:=X_i-Y_i$ because, as stated above, $(n_1-n_2)m=Z_1+\cdots+Z_m$.

2. $Var\,Z_i=Var\,X_i+Var(-Y_i)=Var\,X_i+(-1)^2Var\,Y_i=Var\,X_i+Var\,Y_i=pq+pq=2pq$.

3. $$\de\approx2\bar\Phi\Big(\ep\sqrt{\frac m{2pq}}\Big) \iff \bar\Phi\Big(\ep\sqrt{\frac m{2pq}}\Big)\approx\de/2 \iff \ep\sqrt{\frac m{2pq}}\approx\bar\Phi^{-1}(\de/2)\iff m\approx\frac{2pq}{\ep^2}\,\bar\Phi^{-1}(\de/2)^2.$$