跳到主要內容

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



留言

張貼留言

這個網誌中的熱門文章

Chain Rule & Identity Function Trick

本文為筆者學習微積分，函數概念與Chain Rule 的時候，遇到的一些概念大坑。本文一一澄清一些個人看法，並分享 Chain Rule 廣義的樣子，以及對於遞迴系統該如何計算...等等看法。 [坑1 : 變數/值符號的認識] 一切從 $y = f(x)$ 開始，我們習慣把 Input 變數用"括號"刮起來，Output y 代表值，f 代表函數。或是可以想成這樣:   $$ x \overset{f}{\longrightarrow} y $$ 這種表示法概念上很嚴謹，但缺點是你必須要用三個符號 $x$，$y$，$f$ 而在微分方程領域出現這種寫法 $y = y(x)$  (把 $f$ 換成 $y$) ，這種寫法就頗簡潔，Chain Rule 通常都是這類表示法。缺點是心裡要能確實明白在哪個場合 $y$ 到底是給定的"值"還是"函數"(註: 通常大多代表函數 $y$，值的話通常會這樣寫 $y(x_{0})$,$y_{0}$) ============================================================== [Bonus] $y=y(x)$這種表示法還有一個好處，如果允許 $f$ 是一對多，那麼 $y(x)$ 就是 $y \text{ is depend on } x$ 的意思，如果你喜歡用集合論來表示可以先定義$f$ 的定義域/對應域 $$ f : X \rightarrow Y$$ 然後 $y(x)$ 可以寫成這樣 $y \in Y_{x}$，其中值域為 $$ f(X):=\bigcup_{x \in X}Y_{x} \subseteq Y$$ ============================================================== [坑2 : Input 的變數到底是哪些] 這邊舉兩個例子提醒： (Ex1) 代換法會重新改變函數的 Input 例如 : $y = f(x) = x+1$ , $ z = g(y) = 2y$ 　可以代換一下，寫成 $z = g[f(x)] = 2(x+1)$ 如果你用簡記你會發現　$y(x) , z(y) , z(y(x)) \equiv z...
張貼留言
閱讀完整內容

General Solution Of Eigen System In Linear Algebra

本文從淺白的角度回顧線性代數( Linear Algebra )，了解特徵值( eigenvalue )，特徵向量( eigenvector )，還有特徵多項式( Characteristic Polynomial ) 的框架，並推廣其概念，還有它在解差分方程式，微分方程式，差分方程組，微分方程組的關係。 ----------------------------------------------------------- [預備知識]    向量空間( vector space ) $V$，field over $\mathbb{C}$ ，線性獨立( linear independent )， Span ， Basis 等概念。 線性函數的定義為 $L : V \longrightarrow V$ ， $$\forall \alpha , \beta  \in \mathbb{C} , v_1 ,v_2 \in V \quad L(\alpha v_1 + \beta v_2) =\alpha L(v_1) + \beta L(v_2) $$ 其中 $L(0) = 0 \in V$ 其中 $+$ 都是$V$裡的加法，線性函數空間記做 $L \in \mathcal{L}^{V}$ 其中存在 $O \in \mathcal{L}^{V}$ 零函數 $O(V) = \{0\}$ ，即 $\forall v \in V ,  O(v) = 0 \in V $ 其中存在 $I \in \mathcal{L}^{V}$ 送到自己函數 ，即 $\forall v \in V ,  I(v) = v \in V $ ----------------------------------------------------------- [主要動機] 給定 $b \in V$ ,  $L \in \mathcal{L}^{V}$ 如何解線性系統 $L(x) = b$ ，換句話說就是構造出 $$ S_{b}:= \left\{x \in V : L(x) = b  \right\} $$ ，而 $Ker(L) := S_{0}$ ( Kernel ) 註: 構造出...
張貼留言
閱讀完整內容

All Different Expansion & Bell Numbers

本文分享筆者在計算排列組合(combinatorics)時，發現並描述系統性的窮舉公式 :) 暫時命名為 $\color{red}{\text{All Different Expansion }}$ ??  (有歷史文獻名詞歡迎筆者補充) [情境/動機] 假設箱子裡面有很多種物品，種類集記做 $I$ , 每種物品 $i$ 各有 $\#_i$ 個，向量記做 $\#_{I} := (\#_{i})_{i \in I}$ $$\text{箱子裡共有 } \sum_{i \in I} \#_i  \text{ 個物品}$$    令 $T := \{1,2,3,....|T|\}$，今從箱子裡"逐一"抽取物品共 $|T|$ 次 (抽出 $|T|$ 個物品) ============================================================= $$\color{blue}{\text{形成序列 : } x_{T} := (x_{t})^{|T|}_{t=1} \in I^{|T|}} $$ 註: $x_{t}$ 代表第 $t$ 次抽到的物品 ============================================================= 以下舉個小小的例子，來說明動機~ $I := \{a,b,c,d\}$，$|T| = 4 $，且假設物品個數無上限  $\color{red}{ \forall i \in I \quad \#_{i} = \infty}$ 於是我們可以開始窮舉(brute & force)情況 ~~ $\color{green}{(1)}$  $aaaa$，$bbbb$，$cccc$，$dddd$ 代表全同的情況 $\color{green}{(2)}$  $abcd$，$bcda$，$acbd$，....  代表全異的情況，共 $4!$種 $\color{green}{(3)}$  $abad$，$cbcd$，$bcba$，....  代表二同二異(且$x_{1}=x_{3}$) $\color{green}{(4)...
張貼留言
閱讀完整內容