Sampling Coin Tosses
We toss \(n\) fair coins and count the number of heads. Let \(X_i\) be an indicator variable for the \(i^{th}\) coin. Let \(A_n=\dfrac{\sum_{i=1}^nX_i}{n}\).
Please format fractional answers as x/y.-
What is \(E[A_n]\)?
By linearity of expectation, \(E[A_n]=\frac{1}{n}\cdot\sum_{i=1}^nE[X_i]=\frac{1}{2}\). -
What is the smallest \(n\) can be to guarantee \(\Pr[|A_n-E[A_n]|>\frac{1}{10}]\leq \frac{1}{25}\)?
Using Chebyshev's Theorem, with \(\delta=\frac{1}{10}\) and \(\sigma^2 = \frac{1}{4n}\), we get \(\Pr[|A_n-E[A_n]|>\frac{1}{10}]\leq \frac{25}{n}\), so if \(n\geq 625\) the bound holds. -
What is the smallest \(\delta\) if \(\Pr[|A_{100}-E[A_{100}]|>\delta]\leq \frac{1}{4}\)
We are given that \(n=100\), and from Chebyshev's theorem we get: \[\frac{1}{4}=\frac{\frac{1}{4n}}{\delta^2}.\] Solving for \(\delta\), we get \(\delta = \frac{1}{10}\).