點樣用 random integers 黎 estimate π？

 不如我地試下做少少 experiment 先，求其寫兩個 positive integers，睇下佢地嘅 greatest common divisor（gcd，或者香港學生見開既 H.C.F.）係 1 嘅 probability，比如抽到 $21$ 同 $34$ 就係屬 favourable outcome，抽到 $21$ 同 $35$ 嘅話就唔係一個 favourable outcome。

由於電腦出 random integers 未能做到冇 upper bound 嘅情況，所以我退而求其次，去睇下唔同 upper bound $M$ 嘅結果會係點啦！

$M$	$100$	$10000$	$1000000$
The total number of pairs ($N$)	$100000$	$100000$	$100000$
The number of pairs whose gcd is $1$ ($n$)	$60949$	$60894$	$60647$
The probability of getting a coprime pair ($P=\frac{n}{N}$)	$0.60949$	$0.60894$	$0.60647$
$\sqrt{\frac{6}{P}}$	$3.137562119$	$3.138978736$	$3.145364377$

不如我地將呢個 process 各重覆 $30$ 次，睇下會點~eh... 咁熟口面嘅，好似同我地熟悉既 π 好似喎！

$M$	$100$	$10000$	$1000000$
Sample mean of $\sqrt{\frac{6}{P}}$	$3.139835545$	$3.141452666$	$3.142048756$
Sample standard deviation of $\sqrt{\frac{6}{P}}$	$0.004702442$	$0.003096638$	$0.003385599$

哇，真係好似喎！因為宜家每組有 $30$ 個 data，我地可以 assume 佢地係 normal，咁樣只有 $M=100$ 嘅 case 計到嘅 sample mean 係 significant smaller than $\pi$。

究竟點解呢個數字會咁接近 $\pi$ 呢？

我地可以睇下呢個 probability 可以點樣計出黎先~

首先，我地搵兩個數嘅 gcd 首先會搵左呢兩個數嘅 prime factorization（即小學教嘅質因數連乘式），點樣做到兩個數嘅 gcd 係 1？就係佢地唔會同時係 2 嘅倍數、唔會同時係 3 嘅倍數、唔會同時係 5 嘅倍數、唔會同時係 7 嘅倍數…… 即佢地唔會同時係同一個質數嘅倍數；而因為質數 $p$ 嘅倍數係每 $p$ 就會有一個，所以一個數字係質數 $p$ 嘅倍數嘅 probability 就會係 $\frac{1}{p}$，因此兩個數都唔係質數 $p$ 嘅倍數嘅 probability 就會係 $\frac{1}{p^{2}}$；考慮哂個咁多個 prime numbers，就會得到 $$P=\prod_{p\textbf{ prime}}\left(1-\frac{1}{p^{2}}\right)= \left(1-\frac{1}{2^{2}}\right)\times\left(1-\frac{1}{3^{2}}\right)\times\left(1-\frac{1}{5^{2}}\right)\times\cdots。$$

跟住我地就可以嘗試爆開上面，因為 $0<\frac{1}{p^{2}}<1$，根據 GS sum to infinity，我地知道 $$\frac{1}{1-\frac{1}{p^{2}}} = \sum_{k=0}^{\infty}\frac{1}{p^{2k}}=1+\frac{1}{p^{2}}+\frac{1}{p^{4}}+\frac{1}{p^{6}}+\cdots，$$  所以我地可以將上面個 product 寫成 $$\frac{1}{P}=\prod_{p\textbf{ prime}}\left(\sum_{k=0}^{\infty}\frac{1}{p^{2k}}\right) = \left(1+\frac{1}{2^{2}}+\frac{1}{2^{4}}+\frac{1}{2^{6}}\right) \times \left(1+\frac{1}{3^{2}}+\frac{1}{3^{4}}+\frac{1}{3^{6}}\right) \times \left(1+\frac{1}{5^{2}}+\frac{1}{5^{4}}+\frac{1}{5^{6}}\right) \times \cdots$$

因為我地小學已經學左嘅 Fundamental Theorem of Arithmetic，即每個整數都可以寫成一個 unique 嘅 prime factorization，我地就會見到其實爆開出黎嘅 terms 都係 $\frac{1}{m^{2}}$，而 $m$ 係任何 integers 嘅樣，而且唔會重覆。比如因為 $12=2^{2}\times 3$，所以 $\frac{1}{12^{2}}$ 就可以由第一個 bracket 揀 $\frac{1}{2^{4}}$、第二個 bracket 揀 $\frac{1}{3^{2}}$ 同埋剩餘嘅 brackets 都揀 $1$ 得出，所以 $$\frac{1}{P}=\sum_{k=1}^{\infty} \frac{1}{k^{2}}=1^{2}+2^{2}+3^{2}+\cdots。$$

1735 年，數學家 Euler 發現左 $$\sum_{k=1}^{\infty} \frac{1}{k^{2}}=1^{2}+2^{2}+3^{2}+\cdots=\frac{\pi^{2}}{6}，$$  而呢條式就可以幫我地計到 $$P=\frac{6}{\pi^{2}}，$$  亦因此我地就知道 $$\pi=\sqrt{\frac{6}{P}}$$  喇！

如果想知上面條式點黎，我可以下次打番架！

當然同學都可以諗下點解當 $M$ 係細數嘅時候，點解 estimate 出黎嘅 $\pi$ 通常會細過 actual value？