Finding that probability of the event is small

Question

Let $x_1, \ldots, x_n$ be Bernoulli random variables with the probability of success $P(x_i=1)=p$.

Let $\epsilon>0$.

Show that probability $$ P\left(\left|\sum_{i=1}^nx_i-p\right|> \epsilon\right). $$ is relatively small.

Answer 1

I'll denote $\displaystyle X=\sum_{i=1}^n x_i$ and $A=X-p$

$$P=P\left(|A|>\epsilon\right)=P\left(A>\epsilon\right)+P\left(A<-\epsilon\right)$$

$$P=P\left(X>p+\epsilon\right)+P\left(X<p-\epsilon\right)$$

• For any positive integer $m$, $P(X>m)$ is the probability of having at least $(m+1)$ successes (and thus $n-(m+1)$ failures). Note that if $m\geq n$, this probability will be $0$.
• For any positive integer $m$, $P(X<m)$ is the probability of having at most $(m-1)$ successes (and thus $n-(m-1)$ failures). Note that if $m$ is not positive ($m\leq0$), this probability will be $0$.

Converting these for any positive real $m$ gives you:

• For any positive real $m$, $P(X>m)$ is the probability of having at least $(\lfloor m\rfloor+1)$ successes (and thus $n-(\lfloor m\rfloor+1)$ failures). Note that if $m\geq n$, this probability will be $0$.
• For any positive real $m$, $P(X<m)$ is the probability of having at most $(\lceil m\rceil-1)$ successes (and thus $n-(\lceil m\rceil-1)$ failures). Note that if $m$ is not positive ($m\leq0$), this probability will be $0$.

From this we have:

$$\large P\left(X>p+\epsilon\right)=\left\{\begin{array}{cc}0 && \mbox{if} & p+\epsilon\geq n\space(\epsilon\geq n-p)\\ \sum_{k=\lfloor p+\epsilon\rfloor + 1}^n P\left(X=k\right) && \mbox{otherwise}\end{array}\right.$$

and

$$\large P\left(X<p-\epsilon\right)=\left\{\begin{array}{cc}0 && \mbox{if} & p-\epsilon\leq 0 (\epsilon\geq p)\\ \sum_{k=0}^{\lceil p-\epsilon\rceil-1} P\left(X=k\right) && \mbox{otherwise}\end{array}\right.$$

The probability $P\left(X=k\right)$ is the probability of having exactly $k$ successes and $(n-k)$ failures. Which means:

$$P\left(X=k\right)=p^k(1-p)^{n-k}$$

Now you also know that since $\epsilon>0$ and $0\leq p \leq 1$ then $(p-\epsilon<p\leq1) \Rightarrow (p-\epsilon<1)$. This means that when $\epsilon<p$, $(\lceil p-\epsilon \rceil = 1)\Rightarrow(\lceil p-\epsilon \rceil-1 = 0)$

Hence, your equations become:

$$\large P\left(X>p+\epsilon\right)=\left\{\begin{array}{cc}0 && \mbox{if} & \epsilon\geq n-p\\ \sum_{k=\lfloor p+\epsilon\rfloor + 1}^n p^k(1-p)^{n-k} && \mbox{otherwise}\end{array}\right.$$

and

$$\large P\left(X<p-\epsilon\right)=\left\{\begin{array}{cc}0 && \mbox{if} & \epsilon\geq p\\ P\left(X=0\right)=(1-p)^n && \mbox{otherwise}\end{array}\right.$$

Now replace all those in your first equation and you get:

$$\large P=\left\{\begin{array}{cc} (1-p)^n+\sum_{k=\lfloor p+\epsilon\rfloor + 1}^n p^k(1-p)^{n-k} && \mbox{if} && 0<\epsilon<p \\ \sum_{k=\lfloor p+\epsilon\rfloor + 1}^n p^k(1-p)^{n-k} && \mbox{if} && p\leq\epsilon<n-p \\ 0 && \mbox{if} && \epsilon\geq n-p \end{array}\right.$$

Your turn now to see whether it is relatively small or not ;)