Lattice & Multinomial Theorem

本文介紹格子點(Lattice) 幾何意義與多項式定理(Mutinomial Theorem) 的關係，並可協助我們理解計算一些機率問題。


[符號定義]
非負整數 / 非負實數:  $\mathbb{Z}_{\geq 0} := \{0,1,2,3,4,......\}  \subseteq [0,\infty) =: \mathbb{R}_{\geq 0}$
離散機率向量:  $$p_{I} := (p_{i})_{i \in I} \text{ s.t } \sum_{i\in I}p_i =1 ，|I|<\infty$$
發生事件 $i \in I$ 的累積次數向量:
$$k_{I} := (k_i)_{i \in I} \in \mathbb{Z}^{|I|}_{\geq 0}$$
$\mathbb{Z}^{|I|}_{\geq 0}$ 就是 $|I|$ 維格子點 !!

[格子點情境]
出發點定義為 $k^{start}_{I}:= \overbrace{(0,0...,0)}^{|I|}$，今發生一次 $p_{I}$ 分布隨機互斥事件，等價於"點的移動"(state transition)，數學定義如下:

$$\text{Event } i  \text{ happens }  \Longleftrightarrow  \overbrace{(\color{red}{k_i},k_{-i})}^{k^{old}_{I}}  \underset{\text{with probability }p_{i}}{\longrightarrow}   \overbrace{(\color{red}{k_i+1},k_{-i})}^{ k^{new}_{I}}$$
PS1: 其中  $k_{-i} := (k_{i'})_{i' \in I-\{i\}}$
PS2: 不管怎麼走都在第一象限，也就是只能往右，往上，往高....

當發生 $n$ 次獨立同分布 $p_{I}$ (iid) 的事件後，所有可能點位置在以下的集合上

$$S_{n}(\color{red}{\mathbb{Z}^{|I|}_{\geq 0}}) :=\bigg \{k_{I} \in  \color{red}{\mathbb{Z}^{|I|}_{\geq 0}} :  \sum_{i\in I} k_i = n  \bigg\}$$

由高中經典組合數學問題: "$n$個相同物件分給$|I|$個人"，可知 $|S_{n}| := H^{|I|}_{n}$
註: $S_{n}(\mathbb{Z}^{|I|}_{\geq 0})$ 在幾何意義上為超平面 $S_{n}(\mathbb{R}^{|I|}_{\geq 0})$ 的離散點集

[點的機率質量]
由上面的格子點情境定義，可在$\mathbb{Z}^{|I|}_{\geq 0}$每個點上定義 "機率質量" $p(k_{I})$
註: $p(k_{I})$ , $p_{I}$ 意義不同，不能混淆
而且除了邊界點之外，每個點 $k_{I}$ 都有 $|I|$ 個舊鄰居，$|I|$個新鄰居，定義舊鄰居集合 ${k'}_{I} \in K^{old}_{k_{I}}$，由加法原理可知以下遞迴關係:
$$p(\color{blue}{k_{I}}) := \sum_{\color{red}{k'_{I}} \in K^{old}_{\color{blue}{k_{I}}}} \underbrace{p_{\color{blue}{k_{I}},\color{red}{k'_{I}}}}_{\text{Arc Probability}}  \cdot  p(\color{red}{k'_{I}})$$

其中: $$\bigg( p_{\color{blue}{k_{I}},\color{red}{k'_{I}}}  = p_{i} \bigg)   \Longleftrightarrow  \bigg( k_{i} = k'_{i} + 1 \bigg)$$

註: 以上這個式子也可想成 Markov 轉移矩陣的味道 :)
註: 當 $|I| = 2$ 時，以上的加法原理類似於"巴斯卡定理"
https://en.wikipedia.org/wiki/Pascal%27s_rule

[多項式定理]
不失一般性令 $I \equiv \{1,2,3,4,....|I|\}$
若詳細推導會發現 $p(k_{I})$ 就是多項式定理 :D
https://en.wikipedia.org/wiki/Multinomial_theorem
$$p(k_{I}) \equiv  \bigg(  \begin{array}{c}  n\\  k_1,k_2,...k_{|I|} \\  \end{array}    \bigg) \prod_{i \in I}p_i$$
其中 : $\sum_{i =1}^{|I|} k_{i}   = n$
註: 當 $|I| = 2$ 時，以上就是二項式定理 !!
https://en.wikipedia.org/wiki/Binomial_theorem

[小結]
本文介紹離散機率在格子點上的幾何意義，而多項式定理(係數)存在於完整的 $\mathbb{Z}^{|I|}_{\geq 0}$，(邊界點外，每個格子點上都有$|I|$ 個舊鄰居，有完整的邊有向連通性)，但現實問題往往不會是完整的 $\mathbb{Z}^{|I|}_{\geq 0}$。如: 破產邊界條件 ... 等等，是由許多限制式把$\mathbb{Z}^{|I|}_{\geq 0}$ 交集出來的，而是一個 Lattice  $\mathcal{L} \subseteq  \mathbb{Z}^{|I|}_{\geq 0}$ ，機率遞迴層狀結構 $\{p({k_{I}})\}$也會完全改變(有些邊會被砍掉)，但計算機率還是可以使用加法原理 !!!

[以上純為學術經驗交流知識分享，如有錯誤或建議可留言~~] 

by Plus & Minus 2018.08