Skip to main content
added 461 characters in body
Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

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

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

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

Source Link
Iosif Pinelis
  • 127.7k
  • 8
  • 107
  • 229

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