Let \(S_n\) be the number of successes in \(n\) Bernoulli trials with probability \(p\) for success on each trial. Show, using Chebyshev’s Inequality, that for any \(\epsilon > 0\)
\(P(\bracevert{\frac{S_n}{n} - p}\bracevert \geq \epsilon) \leq \frac{p(1-p)}{n \epsilon ^2}\)
\(\Rightarrow\) The Chebyshev inequality is:
\(P(\bracevert X- \mu \bracevert \geq \epsilon) \leq \frac{V(X)}{\epsilon^2}\)
Given: \(n\) Bernoulli Trials and \(S_n\) is the total number of successes in \(n\) trials;
Each of the \(n\) trials has two possible outcomes; either success with probability \(p\) or failure with probability \(1-p\)
\(\Rightarrow\) The mean of \(S_n\) is \(\mu = E(S_n) = np\) and
\(\Rightarrow\) The variance of \(S_n\) is \(\sigma ^2 =var(S_n)=np(1-p)\) (1)
So, \(P(\bracevert X- \mu \bracevert \geq \epsilon) \leq \frac{V(X)}{\epsilon^2}=\frac{\sigma^2}{\epsilon^2}\)
Based on the proof of Theorem 8.2 page 307: (Law of Large Numbers), we can substitute \(X\) by \(\frac{S_n}{n}\) where:
Mean: \(E(\frac{S_n}{n}) = p\) (2) and
Variance: (substitute equation (1) in the following):
\(Var(\frac{S_n}{n}) = Var(\frac{1}{n} \cdot S_n) = \frac{1}{n^2} Var(S_n) = \frac{1}{n^2} (np(1-p)) = \frac{p(1-p)}{n}\) (3)
Now, let’s substitute equations (2) and (3) on the Chebyshev Inequality:
\(P(\bracevert \frac{S_n}{n} - p \bracevert \geq \epsilon) \leq \frac{Var(\frac{S_n}{n})}{\epsilon^2} = \frac{\frac{p(1-p)}{n}}{\epsilon^2} = \frac{p(1-p)}{n\epsilon^2}\)
SO, For any \(\epsilon >0\):
\(P(\bracevert{\frac{S_n}{n} - p}\bracevert \geq \epsilon) \leq \frac{p(1-p)}{n \epsilon ^2}\)