# Quod Erat Demonstrandum

## 2008/07/29

### 中華民族會滅亡嗎？

$X_n$ = 第 $n$ 代成員的數目。
$Z_i^{(n)}$ = 第 $n$ 代第 $i$ 個成員的「子女」（offspring）數目。

$X_{n+1} = Z^{(n)}_1 + Z^{(n)}_2 + \dots + Z^{(n)}_{X_n}$

$F(s) = P(X = 0) + P(X = 1)s + P(X = 2)s^2 + P(X = 3)s^3 + \dots$（ 取 $|s| \le 1$

1. 要求 $X$ 等於 $r$ 的機會，即是求 $s^r$ 的系數（coefficient）；
2. $F(1) = 1$ （概率總和是一）；
3. $F'(1) = 1\times P(X = 1) + 2\times P(X = 2) + \dots = E(X)$
4. $Var(X) = F''(1) + F'(1)(1 - F'(1))$（這個是 Applied Mathematics (II) 的習題，有關同學試證明之。）
5. 設隨機變量 $X, Y$ 的 PGF 分別為 $F$$G$，則 $X + Y$ 的 PGF 就是 $F\times G$。（嗯，證明也不難，大家試試。）

$F_{n+1}(s)$
= $\sum_{k=0}^{\infty}s^kP(X_{n+1} = k)$
= $\sum_{k=0}^{\infty}\sum_{j=0}^{\infty}s^kP(X_{n+1} = k | X_{n} = j)P(X_n = j)$
(看看如何和前一代的情況有關，體現上回提及的馬可夫鏈吧。)

$\sum_{k=0}^{\infty}s^k\{\delta_{k0}P(X_n = 0)$
$+ P(Z^{(n)}_1 = k)P(X_n = 1)$
$+ P(Z^{(n)}_1 + Z^{(n)}_2 = k)P(X_n = 2)$
$+ P(Z^{(n)}_1 + Z^{(n)}_2 + Z^{(n)}_3 = k)P(X_n = 3)$
$\dots\}$

$P(X_n = 0)$
$+ P(X_n = 1)\sum_{k=0}^{\infty}s^kP(Z^{(n)}_1 = k)$
$+ P(X_n = 2)\sum_{k=0}^{\infty}s^kP(Z^{(n)}_1 + Z^{(n)}_2 = k)$
$+ P(X_n = 3)\sum_{k=0}^{\infty}s^kP(Z^{(n)}_1 + Z^{(n)}_2 + Z^{(n)}_3 = k)$
$\dots$

$f(s) = \sum_{k=0}^{\infty}s^kP(Z^{(n)}_1 = k) = \sum_{k=0}^{\infty}s^kP(Z^{(0)}_1 = k) = \sum_{k=0}^{\infty}s^kP(X_1 = k)$

$F_{n+1}(s)$
$= P(X_n = 0) + P(X_n = 1)F_1(s) + P(X_n = 2)F_1^2(s) + P(X_n = 3)F_1^3(s) \dots$
$= F_{n}(F_1(s))$

$F_2(s) = F_1(F_1(s))$ – – – – – – (1)

$F_3(s) = F_2(F_1(s))$
$= F_1(F_1(F_1(s)))$ [by (1)]
$= F_1(F_2(s))$ [by (1) again] – – – – – – (2)

$F_4(s) = F_3(F_1(s))$
$= F_2(F_1(F_1(s)))$
$= F_1(F_1(F_1(F_1(s))))$
$= F_1(F_1(F_2(s)))$ [by (1)]
$= F_1(F_3(s))$ [by (2)]

$F_{n+1}(s) = F_1(F_{n}(s))$

$x_{n+1} = F_1(x_{n})$，還記得方程有解的條件嗎？

$\lim_{n \rightarrow \infty}F_{n+1}(0) = \lim_{n \rightarrow \infty}F_1(F_{n}(0))$
$\lim_{n \rightarrow \infty}F_{n+1}(0) = F_1(\lim_{n \rightarrow \infty}F_{n}(0))$
$\alpha = F_1(\alpha)$

$E(Z^{(n)}_i) = 1$ for any $n$ and $i$
$E(Z^{(0)}_1) = 1 = E(X_1) = F_1'(1)$ （請參考上文 PGF 的特性 3）

$\frac{F_1(1) - F_1(s)}{1 - s} = F_1'(\beta)$ for some $\beta \in (0,1)$
$\frac{F_1(1) - F_1(s)}{1 - s} < F_1'(1)$ （因 $F_1'(s)$ 嚴格遞增）
$\frac{F_1(1) - F_1(s)}{1 - s} < 1$ （一孩政策嘛）
$\Rightarrow s < F_1(s) \forall s \in (0 , 1)$

$F_{n+1}(s) = F_1(F_n(s))$

$F_{n+1}'(s) = F_1'(F_n(s))F_n'(s)$

$F_{n+1}'(1) = F_1'(F_n(1))F_n'(1)$
$F_{n+1}'(1) = F_1'(1)F_n'(1)$
$E(X_{n+1}) = E(X_1)E(X_n)$

$E(X_n) = E^n(X_1)$