# Probability HW5
###### tags: `Probability`

## 1
### a
以下計算 $M_X(t)$ $$\begin{align}
M_X(t) &= \int_{-\infty}^{\infty}e^{xt}f_X(x)\mathrm dx \\
&= \int_{-\infty}^{-1} e^{xt}(0)\mathrm dx + \int_{-1}^{3} e^{xt}\left(\frac 1 4\right)\mathrm dx + \int_{3}^{\infty} e^{xt}(0)\mathrm dx \\
&= 0 + \left[\frac{1}{4t}e^{xt}\right]_{-1}^{3} + 0 \\
&= \frac{e^{3t}-e^{-t}}{4t}
\end{align}$$

### b
已知 ${M_X}^{(k)}(0)=E[X^k]$ 。因此
* $E[X]={M_X}'(0)$
* $\text{Var}[X]=E[X^2]-E[X]={M_X}''(0)-{M_X}'(0)$

以下計算 $E[X]$ $$\begin{align}
E[X] &= {M_X}'(0) \\
&= \lim_{t\to0}\frac{\left(3e^{3t}+e^{-t}\right)(4t)-\left(e^{3t}-e^{-t}\right)(4)}{(4t)^2} \\
&= \lim_{t\to0}\frac{t\left(3e^{3t}+e^{-t}\right)-\left(e^{3t}-e^{-t}\right)}{4t^2} \\
&\stackrel{\text{H}}{=} \lim_{t\to0} \frac{\left(3e^{3t}+e^{-t}\right)+t\left(9e^{3t}-e^{-t}\right)-\left(3e^{3t}+e^{-t}\right)}{8t} \\
&= \lim_{t\to0} \frac{t\left(9e^{3t}-e^{-t}\right)}{8t} \\
&\stackrel{\text{H}}{=} \lim_{t\to0} \frac{\left(9e^{3t}-e^{-t}\right) + t\left(27e^{3t}+e^{-t}\right)}{8} \\
&= 1
\end{align}$$

以下計算 $\text{Var}[X]$ $$\begin{align}
\text{Var}[X] &= {M_X}''(0)-{M_X}'(0) \\
&= \lim_{t\to0}\dfrac{\left(9t^2-6t+2\right)\mathrm{e}^{4t}-t^2-2t-2}{4t^3e^t} -1 \\
&\stackrel{\text{H}}{=} \lim_{t\to0} \frac{\left(36t^2-6t+2\right)e^{4t}-2t-2}{4e^t\left(3t^2+t^3\right)} -1 \\
&\stackrel{\text{H}}{=} \lim_{t\to0} \frac{\left(144t^2+48t+2\right)e^{4t}-2}{4e^t\left(6t+6t^2+t^3\right)} -1 \\
&\stackrel{\text{H}}{=} \lim_{t\to0} \frac{\left(576t^2+488t+56\right)e^{4t}}{4e^t\left(6+18t+9t^2+t^3\right)} -1 \\
&= \frac 4 3
\end{align}$$

## 2
### a
顯然這是 $n=7, p=0.75$ 的 Binomial distribution 。因此 $$\Pr(X=x)=\begin{equation}\begin{cases}
\displaystyle\binom{7}{x}\left(\frac 3 4\right)^x\left(\frac 1 4\right)^{7-x}, & \text{if}~x\in\{0,1,2,3,4,5,6,7\} \\
\\
0, & \text{else}
\end{cases}\end{equation}$$

### b
顯然這是 Geometric distribution 。解 $$\frac{pe^x}{1-(1-p)e^x}=\frac{e^x}{2-e^x}$$

得到 $p=0.5$ ，因此 $$\Pr(X=x)=\begin{equation}\begin{cases}
2^{-x}, & \text{if}~x \in \mathbb N \\
0, & \text{else}
\end{cases}\end{equation}$$

### c
顯然這是 $\lambda=3$ 的 Poisson distribution 。因此 $$\Pr(X=x)=\begin{equation}\begin{cases}
\dfrac{3^x}{x!e^3}, & \text{if}~x \in \mathbb N ~\text{or}~ x=0 \\
\\
0, & \text{else}
\end{cases}\end{equation}$$

## 3
### a
已知 $$f_{X_1}(x)=f_{X_2}(x)=\begin{equation}\begin{cases}
0.5, & \text{if}~x\in[0,2] \\
0, & \text{else}
\end{cases}\end{equation}$$

可以推導出 $$f_{X_1}(t-x)=\begin{equation}\begin{cases}
0.5, & \text{if}~x\in[t-2,t] \\
0, & \text{else}
\end{cases}\end{equation}$$

因此
* 當 $x<0$ 時 $f_{X_1+X_2}(t)=\displaystyle\int_{-\infty}^0 0^2~\mathrm dx =0$
* 當 $x\in[0,2]$ 時 $f_{X_1+X_2}(t)=\displaystyle\int_0^t 0.5^2~\mathrm dx = \dfrac t 4$
* 當 $x\in[2,4]$ 時 $f_{X_1+X_2}(t)=\displaystyle\int_t^4 0.5^2~\mathrm dx =1-\dfrac t 4$
* 當 $x>4$ 時 $f_{X_1+X_2}(t)=\displaystyle\int_{4}^\infty 0^2~\mathrm dx =0$

答案為 $$f_{X_1+X_2}(t) =
\begin{cases}
\dfrac t 4, & \text{if}~t\in[0,2]\\
1-\dfrac t 4, & \text{if}~t\in[2,4]\\
0, &\text{else}
\end{cases}$$

### b
已知 $Z=3Y_1+4Y_2=\mathcal N(3\mu_{Y_1}+4\mu_{Y_2}, 3^2{\sigma_{Y_1}}^2+4^2{\sigma_{Y_2}}^2)=\mathcal N(19,180)$ 。 因此 $$\begin{align}\Pr(Z>20)
&= 1-\frac 1 2\left(1+\text{erf}\left(\frac{20-19}{\sqrt {180} \sqrt {2}}\right)\right) \\
&= 1-\frac 1 2\left(1+\text{erf}\left(\frac{1}{\sqrt{360}}\right)\right) \\
&\approx 0.47029
\end{align}$$

## 4
### a
已知 $$\begin{align}\Pr(X>\pi\mu)
&= \Pr(X-\mu>(\pi-1)\mu) \\
&\leq \Pr(|X-\mu|>(\pi-1)\mu) \\
&\leq \frac{\mu}{((\pi-1)\mu)^2} \\
&= \frac{1}{(\pi-1)^2\mu}
\end{align}$$

所以 $$\Pr(X>\pi\mu) \leq \frac{1}{(\pi-1)^2\mu}$$

### b
令 $H(n)$ 表示執行 $n$ 次演算法正確的次數。根據 Hoeffding's inequality 若 $a\in[0,1]$ ，則有 $$\Pr(H(n)\leq (p-a)n) \leq \exp(-2a^2n)$$

在此例中 $p=0.5+\delta$ ，並且若 $H(n)\leq n/2$ 則預測失敗。解 $(p-a)n=n/2$ 得到 $a=\delta$ 。故預測失敗的機率為 $$\Pr\left(H(n)\leq \frac n 2\right) \leq \exp\left(-2\delta^2n\right)$$

當 $n\geq (1/2)\delta^{-2}\ln(\varepsilon^{-1})$ 時，預測失敗的機率將為 $$\begin{align}
\Pr\left(H(n)\leq \frac n 2\right)
&\leq \exp\left(-2\delta^2n\right) \\
&\leq \exp\left(-2\delta^2\frac 1 {2\delta^2}\ln\left(\frac 1 \varepsilon\right)\right) \\
&= \varepsilon
\end{align}$$

故得知失敗機率至多為 $\varepsilon$ ，亦即預測成功機率至少為 $1-\varepsilon$ 。 Q.E.D 。

## 5
### a
已知 $f_{X_i}(x)\leq1$ ，因此 $$\begin{align}
E[\exp(-tX_i)] &= \int_{-\infty}^{\infty}e^{-tx}\cdot f_{X_i}(x)\mathrm dx \\
&\leq \int_{-\infty}^{\infty}e^{-tx}\cdot 1\mathrm dx \\
&= \frac 1 t
\end{align}$$

### b
I don't know.