## 1.

Chebyshev’s inequality gives $$\mathbb{P}(\left|X-\mu\right|\geq k\sigma)\leq1/k^{2}$$. An exact calculation yields instead $$e^{-(1+k)}$$. To see this, note that $$\beta(\mu\pm k\sigma)=1\pm k$$ and $$1-k<0$$ so that

$$$\mathbb{P}(\left|X-\mu\right|\leq k\sigma) =\mathbb{P}(X\leq\mu+k\sigma) =F(\mu+k\sigma) =1-e^{-(1+k)}$$$

## 2.

$$$\mathbb{P}(X\geq2\lambda) =\mathbb{P}(X-\lambda\geq\lambda) =\mathbb{P}(\left|X-\lambda\right|\geq\lambda)\leq1/\lambda.$$$

## 3.

First, note that $$\mathbb{V}(\overline{X})=\mathbb{V}(X_{1})/n=p(1-p)/n$$. Chebyshev’s inequality yields

$\mathbb{P}(|\overline{X}-p|>\epsilon) \leq\frac{p\left(1-p\right)}{n\epsilon^{2}} \leq\frac{\max\left\{ x\left(1-x\right)\colon0\leq x\leq1\right\} }{n\epsilon^{2}} =\frac{1}{4n\epsilon^{2}}.$

Next, note that

$\mathbb{P}(|\overline{X}-p|\geq\epsilon) =\mathbb{P}(\overline{X}-p\geq\epsilon)+\mathbb{P}(\overline{X}-p\leq-\epsilon).$

Let $$Y_{i}=(X_{i}-\mathbb{E}X_{1})/n=(X_{i}-p)/n$$ so that $$\overline{X}-p=\sum_{i}Y_{i}$$. Then, $$\mathbb{E}Y_{i}=0$$ and $$-p/n\leq Y_{i}\leq(1-p)/n$$. Hoeffding’s inequality yields

$\begin{multline} \mathbb{P}(\overline{X}-p\geq\epsilon) =\mathbb{P}\left(\sum_{i}Y_{i}\geq\epsilon\right) \leq\exp\left(-t\epsilon\right)\prod_{i}\exp\left(\frac{t^{2}}{8n^{2}}\right)\\ =\exp\left(\frac{t^{2}}{8n}-t\epsilon\right) \leq\min_{t>0}\exp\left(\frac{t^{2}}{8n}-t\epsilon\right) =\exp(-2n\epsilon^{2}). \end{multline}$

Similarly, $$\mathbb{P}(\overline{X}-p\leq-\epsilon)=\mathbb{P}(\sum_{i}(-Y_{i})\geq\epsilon)\leq\exp(-2n\epsilon^{2})$$. It follows that

$\mathbb{P}(|\overline{X}-p|\geq\epsilon) \leq2\exp(-2n\epsilon^{2}) =\frac{1}{1/2+n\epsilon^{2}+n^{2}\epsilon^{4}+O(n^{4})}$

is tighter than the Chebyshev bound for sufficiently large $$n$$.

## 4.

### a)

Applying our findings from Question 3,

$\mathbb{P}(p\in C_{n}) =1-\mathbb{P}(p\notin C_{n}) \geq1-2\exp(-2n\epsilon_{n}^{2}) =1-2\exp\left(\log\left(\frac{\alpha}{2}\right)\right) =1-\alpha.$

### b)

TODO (Computer Experiment)

### c)

The length of the interval is $$2\epsilon_{n}$$. This length is at most $$c>0$$ if and only if $$n\geq2\log(2/\alpha)/c^{2}$$.

TODO (Plot)

## 5.

As per the hint,

$\begin{multline} \mathbb{P}(|Z|>t) =2\mathbb{P}(Z\geq t) =\sqrt{\frac{2}{\pi}}\int_{t}^{\infty}\exp\left(-\frac{x^{2}}{2}\right)dx\\ \leq\sqrt{\frac{2}{\pi}}\frac{1}{t}\int_{t}^{\infty}x\exp\left(-\frac{x^{2}}{2}\right)dx =\sqrt{\frac{2}{\pi}}\frac{1}{t}\exp\left(-\frac{t^{2}}{2}\right). \end{multline}$

TODO (Plot)

## 7.

A linear combination of IID normal random variables is itself a normal random variable. Therefore, $$\overline{X}$$ is a random variable with zero mean and variance $$1/n$$. Letting $$Z\sim N(0,1)$$, Mill’s inequality yields

$$$\mathbb{P}(|\overline{X}|\geq t) =\mathbb{P}(|Z|\geq t\sqrt{n}) \leq\sqrt{\frac{2}{\pi}}\frac{1}{t \sqrt{n}}\exp\left(-\frac{t^{2}n}{2}\right).$$$

The above is tighter than the Chebyshev bound $$1 / (t^2 n)$$ for sufficiently large $$n$$.