0$, $$\P\left(\frac{X_{1}+\cdots+X_{n}}{n}-p>r\right)\leq e^{-trn}( e^{-tp}[pe^{t}+(1-p)])^{n}.$$ And if we choose $t$ appropriately, then the quantity $\P\left(\frac{1}{n}\sum_{i=1}^{n}(X_{i}-p)>r\right)$ becomes exponentially small as either $n$ or $r$ become large. That is, $\frac{1}{n}\sum_{i=1}^{n}X_{i}$ becomes very close to its mean. Importantly, the Chernoff bound is much stronger than either Markov's or Cheyshev's inequality, since they only respectively imply that $$\P\left(\abs{\frac{X_{1}+\cdots+X_{n}}{n}-p}>r\right)\leq \frac{2p(1-p)}{r}, % E|X-p| = p (1-p) + (1-p)p=2p(1-p) \quad\P\left(\abs{\frac{X_{1}+\cdots+X_{n}}{n}-p}>r\right)\leq \frac{p(1-p)}{nr^{2}}.$$ % var(X-p)= E(X-p)^2 = p(1-p)^2+(1-p)p^2= p(1-p)[1-p+p]=p(1-p) \end{exercise} \begin{exercise}[\embolden{Confidence Intervals}] Among $625$ members of a bank chosen uniformly at random among all bank members, it was found that $25$ had a savings account. Give an interval of the form $[a,b]$ where $0\leq a,b\leq625$ are integers, such that with about $95\%$ certainty, if we sample $625$ bank members independently and uniformly at random (from a very large bank membership), then the number of these people with savings accounts lies in the interval $[a,b]$. (Hint: if $Y$ is a standard Gaussian random variable, then $\P(-2\leq Y\leq 2)\approx.95$.) \end{exercise} \begin{exercise}[\embolden{Hypothesis Testing}] Suppose we run a casino, and we want to test whether or not a particular roulette wheel is biased. Let $p$ be the probability that red results from one spin of the roulette wheel. Using statistical terminology, ``$p=18/38$'' is the null hypothesis, and ``$p\neq 18/38$'' is the alternative hypothesis. (On a standard roulette wheel, 18 of the 38 spaces are red.) For any $i\geq1$, let $X_{i}=1$ if the $i^{th}$ spin is red, and let $X_{i}=0$ otherwise. Let $\mu\colonequals\E X_{1}$ and let $\sigma\colonequals\sqrt{\mathrm{var}(X_{1})}$. If the null hypothesis is true, and if $Y$ is a standard Gaussian random variable $$\lim_{n\to\infty}\P\left(\,\abs{\frac{X_{1}+\cdots+X_{n}-n\mu}{\sigma\sqrt{n}}}\geq2\right)=\P(\abs{Y}\geq2)\approx.05.$$ To test the null hypothesis, we spin the wheel $n$ times. In our test, we reject the null hypothesis if $\abs{X_{1}+\cdots+X_{n}-n\mu}>2\sigma\sqrt{n}$. Rejecting the null hypothesis when it is true is called a type $I$ error. In this test, we set the type $I$ error percentage to be $5\%$. (The type $I$ error percentage is closely related to the p-value.) Suppose we spin the wheel $n=3800$ times and we get red $1868$ times. Is the wheel biased? That is, can we reject the null hypothesis with around $95\%$ certainty? \end{exercise} \begin{exercise} A community has $m>0$ families. Each family has at least one child. The largest family has $k>0$ children. For each $i\in\{1,\ldots,k\}$, there are $n_{i}$ families with $i$ children. So, $n_{1}+\cdots+n_{k}=m$. Choose a child randomly in the following two ways. \textbf{Method 1}. First, choose one of the families uniformly at random among all of the families. Then, in the chosen family, choose one of the children uniformly at random. \textbf{Method 2}. Among all of the $n_{1}+2n_{2}+3n_{3}+\cdots+kn_{k}$ children, choose one uniformly at random. What is the probability that the chosen child is the first-born child in their family, if you use Method 1? What is the probability that the chosen child is the first-born child in their family, if you use Method 2? \end{exercise} % %\begin{exercise}\label{exercise8} %Let $Y_{1},Y_{2},\ldots\colon\Samplespace\to\R$ be random variables that converge almost surely to a random variable $Y\colon\Samplespace\to\R$. Show that $Y_{1},Y_{2},\ldots$ converges in probability to $Y$ in the following way. %\begin{itemize} %\item For any $\epsilon>0$ and for any positive integer $n$, let %$$A_{n,\epsilon}\colonequals\bigcup_{m=n}^{\infty}\{\omega\in\Samplespace\colon \abs{Y_{m}(\omega)-Y(\omega)}>\epsilon\}.$$ %Show that $A_{n,\epsilon}\supset A_{n+1,\epsilon}\supset A_{n+2,\epsilon}\supset\cdots$. %\item Show that $\P(\cap_{n=1}^{\infty}A_{n,\epsilon})=0$. %\item Using Continuity of the Probability Law, deduce that $\lim_{n\to\infty}\P(A_{n,\epsilon})=0$. %\end{itemize} % %Now, show that the converse is false. That is, find random variables $Y_{1},Y_{2},\ldots$ that converge in probability to $Y$, but where $Y_{1},Y_{2},\ldots$ do not converge to $Y$ almost surely. %\end{exercise} \begin{exercise}\label{exercise8.1} Let $0