Weak laws of large numbers

Both the encryption algorithm and the hypothetical algorithms used by the adversary involve random events. We will need a theorem that says that, if an event with probability $p$ is tried $r$ times, the chance that the number of successes is not close to $pr$ is small. The paper uses⁷(p. 293)

Lemma 24   Let $S_r$ be the number of successes in $r$ tries. For any $\psi$

$$\Pr\left(\left\vert\frac{S_r}{r}-p\right\vert >\psi\right)<\frac{1}{4r\psi^2}$$

Proof: $S_r$ is a random variable, which is the sum of $r$ independent random variables, each having value 0 or 1. Let $V$ be the variance of $S_r$. Each of the 0-1 variables has variance $\le1/4$, so

$$r^2\psi^2\Pr(\vert S_r-rp\vert>r\psi)<V\le\frac{r}{4}$$

Lemma 24 provides a very rough estimate of the probability. An improvement requiring much more work is:

Lemma 25   With the same notation as Lemma 24,

$$\begin{eqnarray*}&&\Pr\left(\frac{S_r}{r}\ge p+\psi\right)\ && \le\frac{1}{\sqr... ...xp\left( -\frac{r\psi^2(1+\psi)}{2(1-p)(p+\psi)}\right) \qquad(*)\end{eqnarray*}$$

For comparison, if $p=.5$, $r=1000$, the probability that there are $\ge520$ successes is .1087. Lemma 24 gives⁸an upper limit of .3125, while Lemma 25 gives .1498. (these figures courtesy of Mathematica)

One reason the paper does not use Lemma 25 is that it does not give a simple formula for how large $r$ would have to be in terms of the other quantities. We will not use this result later, and you should skip to section 7.3 unless you like to manipulate formulas.

Proof: We will assume $pr+r\psi$ is integer. From the binomial theorem:

$$\begin{eqnarray*} \Pr(S_r\ge rp+r\psi)&=&\sum_{i\ge pr+r\psi} \left(\begin{array... ...\ &&\hbox{where }\alpha=\frac{p(r-pr-r\psi)}{(1-p)(pr+r\psi+1)} \end{eqnarray*}$$

$p+\psi\le1$ implies $p-p\psi-p^2>0$ and

$$\sum\alpha^i=\frac{1}{1-\alpha}=\frac{(1-p)(pr+r\psi+1)}{r\psi+1-p}\le \frac{(1-p)(p+\psi)}{\psi}$$

which gives the second factor of $(*)$. We use Stirling's formula on the binomial coefficient and group it with the powers of $p$ and $1-p$ to obtain:

$$\left(\frac{1}{\sqrt{2\pi r(p+\psi)(1-p-\psi)}}\right) \left(... ...r\psi} \left(\frac{1-p}{1-p-\psi}\right)^{r-pr-\psi r}\quad(**)$$

The first factor of $(**)$ is the first factor of $(*)$. We obtain upper bounds on the rest of $(**)$, using

$$-A-\frac{A^2}{2(1-A)} \le \ln(1-A)\le-A-\frac{A^2}{2}$$

(the lower bound on $\ln(1-A)$ involves a geometric series)

$$\begin{eqnarray*}(pr+r\psi)\ln\left(1-\frac{\psi}{p+\psi}\right) &\le&-r\psi-\fr... ...\psi)}\\ &=&r\psi-\frac{\psi^2r}{1-p}\left(-1+\frac{1}{2}\right)\end{eqnarray*}$$

Adding these and using $\exp$ gives the remaining factor of $(*)$.

Footnotes

... uses⁷

The usual central limit theorem cannot be used because it does not tell you how large $r$ must be for the normal distribution to give a good estimate.

... gives⁸

We divide by 2 to eliminate the probability of $\le480$.