跳到主要內容

Efficient Way From Events To Disjoint Events



本文說明機率論如何在給定機率事件(Events) 如何轉成互斥機率事件(Disjoint Events) 的一些方法

[機率論複習/符號定義]
令 $\omega \in \Omega$ 為樣本點(sample)，樣本空間(sample space)。以及已經定義的(pre-defined)一些事件集 (Events) $ e \in E$ ，與每個事件 $e$ 所對應的樣本點集 $\omega \in \Omega_{e}$
當隨機發生時，相當於從樣本空間 $\Omega$ 根據機率分布 $p_{\Omega}$ 而產出一個元素 $\omega_{*}$ 
當 $\omega_{*} \in \Omega_{e}$  我們說事件 $e$ 發生，反之沒發生，發生的機率為 $$p_{e}:=\sum_{\omega \in \Omega_{e}}p_{\omega}$$

註: 現實生活中，事件 $e$ 的樣本集通常是 $\{0,1\}^{n}$ 的子集, $n$ 可能為"實驗次數"或是"黑箱個數"
$$\bigwedge_{e \in E} \left( \Omega_{e} \subseteq \{0,1\}^{n} \right)$$

[問題定義]
如何給定 $ \Omega_{E} :=  \{\Omega_{e}\}_{e \in E}$ 找到互斥事件集 $E^{disjoint}$ 與其樣本集
$\Omega_{E^{disjoint}}:= \{\Omega_{e} \}_{e \in E^{disjoint}}$ 而且 $$  \bigwedge_{e \in E} \bigg( p_{e} \in Span \bigg\{ p_{e'}: e'\in E^{disjoint} \bigg\} \bigg)$$

[文氏圖交集想法]
很明顯有一個解 $\Omega_{E^{disjoint}} =  \bigg\{\displaystyle{ \bigcap_{e \in S}\Omega_{e} \cap \bigcap_{e \in E\setminus S}\bar{\Omega}_{e } : S \subseteq E    }  \bigg\}$，也就是把文氏圖切成 $2^{|E|}$ 塊。但現實生活中，如果 $|E| = 50$，則要做 $2^{50}-1$次集合組合間交集運算，而且很多"塊"可能都是空集合，稀疏的(Sparse)，實作上可能不能直接這樣思考!!

[從樣本點角度出發]
可以先把 $\bigg\{ \Omega_{e}: e \in E \bigg\}$ 做自然對偶對應 (Natural Dual Correspondence) (筆者自己的用詞) ，產生 $\color{red}{\bigg\{ E_{\omega} :   \omega \in  \displaystyle{\bigcup_{e \in E}\Omega_{e}} \bigg\}}$ ，也就是 
$$  \bigwedge_{e\in E} \bigwedge_{\omega \in \Omega} \bigg(  \omega \in \Omega_{e} \Longleftrightarrow e \in  \color{red}{E_{\omega}}        \bigg) $$

計算複雜度只要 $\displaystyle{O\left(\sum_{e\in E}|\Omega_{e}|\right)}$
白話來說，我們把焦點從 $\color{blue}{"事件 e  發生所需要的樣本點 \omega"}$ 轉移到 $\color{green}{"樣本點 \omega 出現時，哪些事件  e  會發生"}$
另外考慮 $E_{\omega}$ 上的事件們 $$\left\{\begin{array}{c}e \in E_{\omega}  \Longrightarrow \omega \in \Omega_{e} \\ e' \in E_{\omega}  \Longrightarrow \omega \in \Omega_{e}\\  e'' \not\in E_{\omega}  \Longrightarrow \omega \not\in \Omega_{e''}    \\\end{array}\right. \Longrightarrow  \omega \in \Omega_{e}\cap \Omega_{e'} \cap \bar{\Omega}_{e''}$$
廣義來說 : $$ \omega \in \left(\bigcap_{e \in E_{\omega}} \Omega_{e}\right) \cap \left( \bigcap_{e \in E\setminus E_{\omega}} \bar{\Omega}_{e} \right) $$
會發現恰好就是文氏圖，$2^{|E|}$裡"非空"的那一塊，於是我們可以定義集合的集合 $\mathcal{C} := \{\underset{=c}{E_{\omega}}\}$ ，而且很明顯 $\mathcal{C}$ 互斥，以及 $\forall e \in E ,  p_{e} \in  Span \bigg\{  p_{c} : c \in \mathcal{C}  \bigg\}$
其中 $p_{c} := \sum_{\omega \in  \#} p_{\omega}$ ， $ \# := \bigg\{\omega' \in \Omega :  E_{\omega'} = \underset{= c}{E_{\omega}}   \bigg\} $

[舉例]
假設隨機試驗為丟3次銅板，F為正面，T為反面，定義事件集 $ e \in E := \{ AM1T, AL1T , E1T,ALLT , ALLF , F1T, C2T \}$
以及樣本點集 $ e : \Omega_{e}$
$AM1T = At-Most-1-T  : \{FFF,TFF,FTF,FFT\}$
$AL1T =  At-Least-1-T : \{TFF,FTF,FFT,TTF,FTT,TFT,TTT\}$
$E1T = Exact-1-T : \{TFF,FFT,FTF\}$
$ALLT = All-T : \{TTT\}$
$ALLF = All-F : \{FFF\}$
$FIT = First-is-T : \{TFF,TTF,TFT,TTT\}$
$C2T = Consecutive-2-T : \{ FTT,TTF\}$

構造出 $\omega : E_{\omega}$

$FTF : \color{red}{\{AL1T,AM1T,E1T\}}$
$TFF : \{AL1T,AM1T,FIT,E1T\}$
$FFT : \color{red}{\{AL1T,AM1T,E1T\}}$
$FFF : \{ALLF,AM1T\}$
$FTT : \{C2T,AL1T\}$
$TTF : \{C2T,AL1T,FIT\}$
$TTT :\{ALLT,AL1T,FIT\}$
$TFT :\{AL1T,FIT\}$

構造出互斥事件群 !! $c :  \Omega_{c}$
$\color{red}{\{AL1T,AM1T,E1T\}} : \{FTF,FFT\}$
$ \{AL1T,AM1T,FIT,E1T\} : \{TFF\}$
$ \{ALLF,AM1T\} :  \{FFF\}$
$\{C2T,AL1T\} : \{FTT\}$
$ \{C2T,AL1T,FIT\} : \{TTF\} $
$\{ALLT,AL1T,FIT\} : \{TTT\}$
$\{AL1T,FIT\} : \{TFT\} $
其餘狀況 : $\emptyset$

[小結]
本文提供一個簡單的方法，從樣本點的對應出發，會比從事件間交集間還來的有效率。


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



留言

張貼留言

這個網誌中的熱門文章

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)...
張貼留言
閱讀完整內容