PRML演習問題 2.3(標準) www - 機械学習基礎理論独習

問題

この演習問題では、二項分布 $(2.9)$ が正規化されていることを説明する。
まず、全部で $N$ 個ある対象から $m$ 個の同じものを選ぶ組み合わせの数の定義 $(2.10)$ を用いて、

$\begin{eqnarray} \begin{pmatrix}N\\m\end{pmatrix}+\begin{pmatrix}N\\m-1\end{pmatrix}=\begin{pmatrix}N+1\\m\end{pmatrix}\tag{2.262} \end{eqnarray}$

を示せ。
この結果を用い、帰納法で次の結果を証明せよ。

$\begin{eqnarray} (1+x)^N=\sum_{m=0}^N\begin{pmatrix}N\\m\end{pmatrix}x^m\tag{2.263} \end{eqnarray}$

これは、二項定理(binomial theorem)として知られ、すべての実数値 $x$ について成り立つ。
最後に、二項分布が次のように正規化されていることを、 $(1-\mu)^N$ を和の外に出してから、二項定理を使うことで示せ。

$\begin{eqnarray} \sum_{m=0}^N\begin{pmatrix}N\\m\end{pmatrix}\mu^m(1-\mu)^{N-m}=1\tag{2.264} \end{eqnarray}$

参照

$\begin{eqnarray} {\rm Bin}(m|N,\mu)=\begin{pmatrix}N\\m\end{pmatrix}\mu^m(1-\mu)^{N-m}\tag{2.9} \end{eqnarray}$

$\begin{eqnarray} \begin{pmatrix}N\\m\end{pmatrix}\equiv\frac{N!}{(N-m)!m!}\tag{2.10} \end{eqnarray}$

解答

式 $(2.262)$ の左辺を計算します。

$\begin{eqnarray} \begin{pmatrix}N\\m\end{pmatrix}+\begin{pmatrix}N\\m-1\end{pmatrix}&=&\frac{N!}{(N-m)!m!}+\frac{N!}{(N-m+1)!(m-1)!}\\ &=&\frac{(N-m+1)N!+mN!}{(N-m+1)!m!}\\ &=&\frac{(N+1)N!}{(N-m+1)!m!}\\ &=&\frac{(N+1)!}{(N+1-m)!m!}\\ &=&\begin{pmatrix}N+1\\m\end{pmatrix}\tag{1} \end{eqnarray}$

式 $(1)$ より、式 $(2.262)$ が示せました。

帰納法で式 $(2.263)$ を示します。
$N=1$ のとき、

$\begin{eqnarray} (1+x)^1&=&\sum_{m=0}^1\begin{pmatrix}1\\m\end{pmatrix}x^m\\ &=&\begin{pmatrix}1\\0\end{pmatrix}x^0+\begin{pmatrix}1\\1\end{pmatrix}x^1\\ &=&1+x\tag{2} \end{eqnarray}$

となり、式 $(2.263)$ が成り立ちます。

$N=k$ のとき、式 $(2.263)$ が成り立つとします。

$\begin{eqnarray} (1+x)^{k+1}&=&(1+x)(1+x)^{k}\\ &=&(1+x)\sum_{m=0}^k\begin{pmatrix}k\\m\end{pmatrix}x^m\\ &=&\sum_{m=0}^k\begin{pmatrix}k\\m\end{pmatrix}x^m+\sum_{m=0}^k\begin{pmatrix}k\\m\end{pmatrix}x^{m+1}\\ &=&\sum_{m=0}^k\begin{pmatrix}k\\m\end{pmatrix}x^m+\sum_{m=1}^{k+1}\begin{pmatrix}k\\m-1\end{pmatrix}x^m\\ &=&\begin{pmatrix}k\\0\end{pmatrix}x^0+\sum_{m=1}^k\begin{pmatrix}k\\m\end{pmatrix}x^m+\sum_{m=1}^{k}\begin{pmatrix}k\\m-1\end{pmatrix}x^m+\begin{pmatrix}k\\k\end{pmatrix}x^{k+1}\\ &=&\begin{pmatrix}k\\0\end{pmatrix}x^0+\sum_{m=1}^{k}\left(\begin{pmatrix}k\\m\end{pmatrix}+\begin{pmatrix}k\\m-1\end{pmatrix}\right)x^m+\begin{pmatrix}k\\k\end{pmatrix}x^{k+1}\\ &=&\begin{pmatrix}k\\0\end{pmatrix}x^0+\sum_{m=1}^{k}\begin{pmatrix}k+1\\m\end{pmatrix}x^m+\begin{pmatrix}k\\k\end{pmatrix}x^{k+1}\\ &=&\begin{pmatrix}k+1\\0\end{pmatrix}x^0+\sum_{m=1}^{k}\begin{pmatrix}k+1\\m\end{pmatrix}x^m+\begin{pmatrix}k+1\\k+1\end{pmatrix}x^{k+1}\\ &=&\sum_{m=0}^{k+1}\begin{pmatrix}k+1\\m\end{pmatrix}x^m\tag{3} \end{eqnarray}$

式 $(3)$ より、 $N=k+1$ のとき、式 $(2.263)$ が成り立ちます。
以上より、式 $(2.263)$ が示せました。

式 $(2.264)$ の左辺を計算します。

$\begin{eqnarray} \sum_{m=0}^N\begin{pmatrix}N\\m\end{pmatrix}\mu^m(1-\mu)^{N-m}&=&(1-\mu)^N\sum_{m=0}^N\begin{pmatrix}N\\m\end{pmatrix}\mu^m(1-\mu)^{-m}\\ &=&(1-\mu)^N\left(1+\frac{\mu}{1-\mu}\right)^N\\ &=&(1-\mu)^N\left(\frac{1}{1-\mu}\right)^N\\ &=&1\tag{4} \end{eqnarray}$

式 $(4)$ より、式 $(2.264)$ が示せました。