# Probability HW1
###### tags: `Probability`
- [name=0716023 曾文鼎]

## 1a
* 當 $N=1$ 時，原式 $P\left(\displaystyle\bigcup_{n=1}^{N}A_n\right) = P(A_1) \leq \displaystyle\sum_{n=1}^{N}P\left(A_n\right)$ 顯然成立。
* 設 $N=K$ 時原式成立，則當 $N=K+1$ 時，有 $$\begin{aligned}P\left(\bigcup_{n=1}^{K+1}A_n\right) &= P\left(\bigcup_{n=1}^{K}A_n\right) + P(A_{K+1}) - P\left(\left(\bigcup_{n=1}^{K}A_n\right) \cap A_{K+1}\right) \\ &\leq \sum_{n=1}^{K}P\left(A_n\right) + P(A_{K+1}) - P\left(\left(\bigcup_{n=1}^{K}A_n\right) \cap A_{K+1}\right) \\ &= \sum_{n=1}^{K+1}P\left(A_n\right) - P\left(\left(\bigcup_{n=1}^{K}A_n\right) \cap A_{K+1}\right) \\ &\leq \sum_{n=1}^{K+1}P\left(A_n\right)\end{aligned}$$ 故當 $N=K+1$ 時原式亦成立。
* 綜合以上兩點，藉由數學歸納法，$\forall N \in \mathbb N$ 原式均成立。

Q.E.D

## 1b
* $P(\{1,3,4,5\}) = P(\{1,3\}) +P(\{4,5\}) = 0.3 + 0.2 = 0.5$
* $P(\{2\}) = P(\{1,2,3,4,5\}) - P(\{1,3,4,5\}) = 1 - 0.5 = 0.5$
* 但 $P(\{1,2,4\}) = 0.45 < 0.5 = P(\{2\})$

矛盾，故無解。

## 2a
### (i)
* 當 $N=1$ 時，原式 $\left(\displaystyle\bigcup^N_{n=1} S_n\right)^c = {S_1}^c = \displaystyle\bigcap^N_{n=1} {S_n}^c$ 顯然成立。
* 設 $N=K$ 時原式成立，則當 $N=K+1$ 時，有
$$\begin{aligned}\left(\bigcup^{K+1}_{n=1} S_n\right)^c &= \left(\bigcup^{K}_{n=1}S_n\right)^c \cap {S_{K+1}}^c \\&= \left(\bigcap^K_{n=1} {S_n}^c\right) \cap {S_{K+1}}^c \\ &= \bigcap^{K+1}_{n=1} {S_n}^c \end{aligned}$$ 故當 $N=K+1$ 時原式亦成立。
* 綜合以上兩點，藉由數學歸納法，$\forall N \in \mathbb N$ 原式均成立。

Q.E.D

### (ii)
* 當 $N=1$ 時，原式 $\left(\displaystyle\bigcap^N_{n=1} S_n\right)^c = {S_1}^c = \displaystyle\bigcup^N_{n=1} {S_n}^c$ 顯然成立。
* 設 $N=K$ 時原式成立，則當 $N=K+1$ 時，有
$$\begin{aligned}\left(\bigcap^{K+1}_{n=1} S_n\right)^c &= \left(\bigcap^{K}_{n=1}S_n\right)^c \cup {S_{K+1}}^c \\&= \left(\bigcup^K_{n=1} {S_n}^c\right) \cup {S_{K+1}}^c \\ &= \bigcup^{K+1}_{n=1} {S_n}^c \end{aligned}$$ 故當 $N=K+1$ 時原式亦成立。
* 綜合以上兩點，藉由數學歸納法，$\forall N \in \mathbb N$ 原式均成立。

Q.E.D

## 2b
定義 $B_i=\begin{equation}\begin{cases} A_1, & i=1 \\ A_i - \displaystyle\bigcup^{i-1}_{k=1}A_k, & i>1 \end{cases}\end{equation}$

* 對於任意 $i, j \in \mathbb N$ 且 $i>j$ ，由於 $B_i=A_i-\displaystyle\bigcup_{k=1}^{i-1}A_k \Longrightarrow B_i \cap \bigcup_{k=1}^{i-1}A_k = \phi$ ，又 $B_j \subseteq A_j\ \subseteq \displaystyle\bigcup_{k=1}^{j} A_k \subseteq \displaystyle\bigcup_{k=1}^{i-1} A_k$ ，因此 $B_i \cap B_j = \phi$ 。

故對於任意 $i, j\in \mathbb N$ 且 $i \neq j$ ，恆有 $B_i \cap B_j = \phi$ 。

* 以下證明 $\forall n \in\mathbb N,~\displaystyle\bigcup_{i=1}^{n} B_i=\bigcup_{i=1}^n A_i$ 。 $$\begin{align} \bigcup_{i=1}^{n} B_i &= (A_n-A_{n-1}-A_{n-2}-\cdots-A_1) \\ &~~~~~~\cup (A_{n-1}-A_{n-2}-A_{n-3}-\cdots-A_1) \\ &~~~~~~\cup (A_{n-2}-A_{n-3}-A_{n-4}-\cdots-A_1) \\ &~~~~~~\cup \cdots \\ &~~~~~~\cup( A_2-A_1) \\ &~~~~~~\cup (A_1) \\&=\bigcup_{i=1}^n A_i \end{align}$$

## 3a
1. 定義一個函數 $f(n,k)$ ，表示數字 $n$ 小數點後第 $k$ 位的 digit 。例如 $0.0716023$ 小數點後第 $4$ 位為 $6$ ，故 $f(0.0716023, 4)=6$ 。
1. 假設實數在 $[0,1]$ 中為 countably infinite 。我們將該區間所有的數字任意排序於一張長度無限長的清單 $L$ 。定義 $a_i$ 為 $L$ 的第 $i$ 個數字。
2. 現在規定一個實數 $x\in[0,1]$ ，此數的任意位數可以用以下函數定義： $$f(x,k)=\begin{equation}\begin{cases} 6, & f(a_k,k)\neq 6 \\ 9 & f(a_k,k)=6 \end{cases}\end{equation}$$
4. 顯然 $x$ 不會與 $L$ 中任一個數字相等，亦即 $x$ 不在清單 $L$ 中。但 $x\in[0,1]$ 應該要在 $L$ 中，所以發生矛盾。所以實數區間 $[0,1]$ 是 uncountably infinite 。
5. 承上，故實數為 uncountably infinite 。

Q.E.D

## 3b
1. 以下證明有理數在 $[0,1]$ 中為 countable finite：
* 所有有理數都可以化為各不相同的最簡分數。將這些最簡分數按分母排列。分母相同者，按分子排列。於是生成一個清單 $$\frac 1 1, \frac 1 2, \frac 1 3, \frac 2 3, \frac 1 4, \frac 3 4, \dots$$
* 則有理數 $x$ 可以映射至整數 $n$ ，其中 $n$ 為 $x$ 出現在清單中的位置。
* 於是有理數在 $[0,1]$ 可以一對一映射至正整數。
* 故 $[0,1]$ 中的有理數是 countable infinite 。

2. 由題目 3a 的推導中已知實數在 $[0,1]$ 為 uncountable infinite 。

因為無理數為實數與有理數的差集，由以上兩點可知無理數在 [0,1] 中為 uncountable inifinte 。

## 4a
定義 $A_i$ 為第 $i$ 次丟硬幣人頭朝上的事件，然後定義 $$B_k=\bigcup_{i=k}^{\infty}A_i$$

因為 $\displaystyle\sum_{i=1}^{\infty}P(A_i)$ 收斂且 $A_i$ 項兩兩互斥，所以顯然 $\forall k\in \mathbb N$ 恆有 $$P(B_k)= P\left(\bigcup_{i=k}^{\infty}A_i\right) = \displaystyle\sum_{i=k}^{\infty}P(A_i) \leq \displaystyle\sum_{i=1}^{\infty}P(A_i)$$

因此可以推測出 $$\lim_{k\to\infty} P(B_k) \leq \lim_{k\to\infty}\sum_{i=k}^{\infty}P(A_i) = 0$$

亦即 $$\lim_{k\to\infty}P(B_i) = 0$$

因此 $$P(I) = P\left(\bigcap_{k=1}^{\infty}\bigcup_{i=k}^{\infty}A_i\right)=P\left(\bigcap_{i=1}^{\infty}B_i\right)=P(\lim_{i\to\infty}B_i) = 0$$

上式第三個等號成立，因為 $B_1 \supseteq B_2 \supseteq B_3 \supseteq \cdots B_i \supseteq B_{i+1} \supseteq \cdots$ 。

Q.E.D

## 4b
定義 $A_i$ 為第 $i$ 次丟硬幣人頭朝上的事件。因為 $A_i$ 兩兩獨立，且 $1-x\leq e^{-x}$ ，因此 $$\begin{align} P\left(\bigcap_{i=1}^\infty {A_i}^c\right) &= \prod_{i=1}^{\infty}P({A_i}^c) \\ &=\prod_{i=1}^\infty (1-P(A_i)) \\&\leq \prod_{i=1}^\infty e^{-P(A_i)} \\&=\exp\left(-\sum_{i=1}^\infty P(A_i) \right) \end{align}$$

然後因為 $\displaystyle\sum_{i=1}^\infty P(A_i)$ 發散，顯然 $$P\left(\bigcap_{i=1}^\infty {A_i}^c\right) \leq \exp\left(-\sum_{i=1}^\infty P(A_i) \right) = 0$$

簡之 $$P\left(\bigcap_{i=1}^\infty {A_i}^c\right) = 0$$

上式意同於 $$P\left(\bigcup_{n=1}^\infty\bigcap_{i=n}^\infty{A_i}^c\right)=0$$

最終得出 $$\begin{aligned} P(I)&=P\left(\bigcap_{n=1}^{\infty}\bigcup_{i=n}^{\infty}A_i\right) \\ &= 1-P\left(\bigcup_{n=1}^\infty\bigcap_{i=1}^\infty{A_i}^c\right) \\ &= 1 \end{aligned}$$

Q.E.D

## 5a
$p\varepsilon_0 + (1-p)\varepsilon_1$

## 5b
* 所有 bit 接收成功的機率為 $(p(1-\varepsilon_0) + (1-p)(1-\varepsilon_1))^3$
* 恰一 bit 接收失敗的機率為 $C^3_2(p(1-\varepsilon_0) + (1-p)(1-\varepsilon_1))^2(p\varepsilon_0 + (1-p)\varepsilon_1)$

故至多一 bit 接收失敗的機率為 $$(p(1-\varepsilon_0) + (1-p)(1-\varepsilon_1))^3 + 3(p(1-\varepsilon_0) + (1-p)(1-\varepsilon_1))^2(p\varepsilon_0 + (1-p)\varepsilon_1)$$

## 5c
送出零且接收失敗的機率為 $p\varepsilon_0$ ，故失敗的前提下送出零的機率為 $$\displaystyle\frac{p\varepsilon_0}{p\varepsilon_0 + (1-p)\varepsilon_1}$$
送出一且接收失敗的機率為 $(1-p)\varepsilon_1$ ，故失敗的前提下送出一的機率為 $$\displaystyle\frac{(1-p)\varepsilon_1}{p\varepsilon_0 + (1-p)\varepsilon_1}$$

故答案為上述乘積 $$\displaystyle\frac{p(1-p)\varepsilon_0\varepsilon_1}{(p\varepsilon_0 + (1-p)\varepsilon_1)^2}$$

## 5d
* 既然前兩位 $01$ 已收到，那送出的前兩位就是 $01$ 。
* 在接收失敗的情況下，實際送出零的機率為 $\displaystyle\frac{p\varepsilon_0}{p\varepsilon_0 + (1-p)\varepsilon_1} = \dfrac{5}{13}$ 。
* 在接收失敗的情況下，實際送出一的機率為 $1-\dfrac{5}{13}=\dfrac{8}{13}$ 。
* 在接收失敗的情況下，送出零比一的機率低。因此末兩碼最有可能是 $11$ 。

因此最有可能送出的 bits 是 $0111$ 。

## 6a
* $P(A_1 \cap B) = \dfrac 1 3 \times 0.3 = \dfrac 1 {10}$
* $P(A_2 \cap B) = \dfrac 1 3 \times 0.5 = \dfrac 1 {6}$
* $P(A_3 \cap B) = \dfrac 1 3 \times 0.7 = \dfrac 7 {30}$
* $P(B) = \displaystyle\sum_{i=1}^3 P(A_i\cap B) = \dfrac 1 2$

$P(A_1|B) = \dfrac {1/10}{1/2} = \dfrac 1 5$
$P(A_2|B) = \dfrac {1/6}{1/2} = \dfrac 1 3$
$P(A_3|B) = \dfrac {7/30}{1/2} = \dfrac 7 {15}$

## 6b
因為 $P(A_i\cap C)=P(A_i)[P(H|A_i)]^8[P(T|A_i)]^2$ ，可以推斷：
* $P(A_1 \cap C)=\dfrac 1 3 (0.3^8 \times 0.7^2)$
* $P(A_2 \cap C)=\dfrac 1 3 (0.5^8 \times 0.5^2)$
* $P(A_3 \cap C)=\dfrac 1 3 (0.7^8 \times 0.3^2)$

然後得出
* $P(C) = \displaystyle\sum_{i=1}^3P(A_i\cap C) \approx 2.066\times 10^{-3}$

以下計算 $P(A_i|C) = P(A_i\cap C)/P(C)$ 的值：
* $P(A_1|C) \approx 0.52\%$
* $P(A_2|C) \approx 15.76\%$
* $P(A_3|C) \approx 83.72\%$

故 $\theta=0.7$ 的可能性最高。

## 6c
因為 $P(A_i\cap C)=P(A_i)[P(H|A_i)]^8[P(T|A_i)]^2$ ，可以推斷：
* $P(A_1 \cap C)=0.4 \times (0.3^8 \times 0.7^2)$
* $P(A_2 \cap C)=0.4 \times (0.5^8 \times 0.5^2)$
* $P(A_3 \cap C)=0.2 \times (0.7^8 \times 0.3^2)$

然後得出
* $P(C) = \displaystyle\sum_{i=1}^3P(A_i\cap C) \approx 1.441\times 10^{-3}$

以下計算 $P(A_i~|~C) = \dfrac{P(A_i\cap C)}{P(C)}$ 的值：
* $P(A_1|C) \approx 0.89\%$
* $P(A_2|C) \approx 27.11\%$
* $P(A_3|C) \approx 72.00\%$

故 $\theta=0.7$ 的可能性最高。

## 7a
* 令 $f(x)=(1+x)^n$ ，則其展開式第 $i$ 次的係數 $C^n_i$ 。

所以 $(1+x)^{2n} = (1+x)^n(1+x)^n$ 的第 $n$ 次項係數為 $$\displaystyle\sum_{i=0}^n C^n_i C^n_{n-i} = \displaystyle\sum_{i=0}^n C^n_i C^n_i = \displaystyle\sum_{i=0}^n (C^n_i)^2$$

Q.E.D

## 7b
以下證明 $C_r^{n+1}=C_r^n+C_{r-1}^n$ 。 $$\begin{align} C_r^{n+1} &=\frac {(n+1)!}{r!(n-r+1)!} \\ &=\frac{n!}{r!(n-r)!}\frac{n+1}{n-r+1} \\ &= \frac{n!}{r!(n-r)!}\left(1+\frac r {n-r+1}\right) \\ &= \frac{n!}{r!(n-r)!} + \frac{n!}{(r-1)!(n-r+1)!} \\ &= C^n_r+C^n_{r-1} \end{align}$$

於是 $$\begin{align}\sum_{i=0}^r C^{n+i}_i &= C^n_0 + C^{n+1}_1 + C^{n+2}_2 + \cdots + C^{n+r}_r \\ &= C^{n+1}_0 + C^{n+1}_1 + C^{n+2}_2 + \cdots + C^{n+r}_r \\ &= C^{n+2}_1 + C^{n+2}_2 + C^{n+3}_3 + \cdots + C^{n+r}_r \\ &= \cdots \\ &= C^{n+r+1}_r \end{align}$$

Q.E.D