跳到主要內容

Expectation On Non-disjoint Events


本文為紀錄簡易博弈模型，若滿足有交集則彩金"疊加性"，則傳統期望值可推廣到非互斥事件上。

給定 開獎結果(樣本空間) $\Omega$ ，投注項目集 $B$ ，
投注項目 $b$所對應的開獎結果集 $\Omega_{b}$

$$ \bigwedge_{b \in B}\left(\Omega_{b} \subset \Omega\right)$$

以及定義 $\Omega_{b}$補集:
$$\displaystyle{\bigwedge_{b \in B} \left( \bar{\Omega}_{b}:= \Omega \setminus \Omega_{b} \right) }$$

機率公設與 $\Omega_{b}$ 定義計算如下:
$$\displaystyle{ \sum_{\omega \in \Omega} P(\omega) = 1} $$
$$\displaystyle{\bigwedge_{b \in B} \left( P(\Omega_{b}) := \sum_{\omega \in \Omega_{b}} P(\omega) \right)} $$

描述文氏圖互斥分割集概念如下:
$$\displaystyle{\Omega = \bigcup^{\text{disjoint}}_{S \subseteq B} \left(\bigcap_{b \in S}\Omega_{b} \cap \bigcap_{b \in B\setminus S} \bar{\Omega}_{b}\right)  }$$

開獎機制如下:
假定 開獎結果 $\omega$，投注$b$ 項目中獎可獲得彩金 $c^{bingo}_{b}$ 元，槓龜獲得彩金 $c^{turtle}_{b}$ 元


$$\displaystyle{\bigwedge_{(b,\omega) \in B\times \Omega}\left\{\begin{array}{l}\omega \in \Omega_{b} \Longleftrightarrow \text{得到 } c^{bingo}_{b}\\ \omega \not\in \Omega_{b} \Longleftrightarrow  \text{得到 } c^{turtle}_{b} \\\end{array}  \right.}$$


(註: 若有 $\omega$ 同時被許多 $\Omega_{b}$ 交集 則彩金"疊加")

則期望彩金值滿足下面的等式，左式為推廣式，右式為傳統算法(互斥集合相加)
$$ \displaystyle{\sum_{b\in B}\left[ c^{bingo}_{b}P(\Omega_{b}) + c^{turtle}_{b}P(\bar{\Omega}_{b}) \right]}= \sum_{S \subseteq B}\left[\left(\sum_{b\in S}c^{bingo}_{b} + \sum_{b \in B\setminus S} c^{turtle}_{b}\right) P\underbrace{\left(\bigcap_{b \in S}\Omega_{b} \cap \bigcap_{b \in B\setminus S} \bar{\Omega}_{b}\right)}_{\text{disjoint sets}}\right] $$

舉例:

$B = \{ X,Y\}$ , $|B|=2$ 則期望值

 $$ \text{左式 } = c^{bingo}_{X} P(\Omega_{X}) + c^{turtle}_{X} P(\bar{\Omega}_{X})  + c^{bingo}_{Y} P(\Omega_{Y})  + c^{turtle}_{Y} P(\bar{\Omega}_{Y}) $$

$$ \text{右式 } = \overbrace{(c^{bingo}_{X}+c^{bingo}_{Y})  P(\Omega_{X} \cap \Omega_{Y})}^{S = \{X,Y\}= \Omega}  +  \overbrace{(c^{bingo}_{X}+c^{turtle}_{Y})P(\Omega_{X} \cap \bar{\Omega}_{Y})}^{S=\{X\}} +  \overbrace{ (c^{turtle}_{X}+c^{bingo}_{Y}) P(\bar{\Omega}_{X} \cap \Omega_{Y}) }^{S=\{Y\}}+  \overbrace{(c^{turtle}_{X}+c^{turtle}_{Y})P(\bar{\Omega}_{X} \cap \bar{\Omega}_{Y})}^{S=\emptyset}
$$

[小結]
此公式是非常自然，好理解的，有交集就疊加!!  比較神奇的是左式是$|B|$項相加，右式則需要 $2^{|B|}$項相加。 如果考慮到彩金疊加性，事實上我們只要 $|B|$ 個維度就能算出期望值，不需要 $2^{|B|}-1$ 個維度，而且算法跟傳統期望值定義一模一樣!!

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

留言

張貼留言

這個網誌中的熱門文章

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

Linear Regression By Using Linear Programming

當拿到一筆資料準備玩統計，往往會想要做線性迴歸( Linear Regression )，找出一個模型( mathematical model )來解釋變數間的關係，一般都是使用平方距離，但是如果我們採用絕對值距離呢?? 而剛好在工業工程( Industrial Engineering )，作業研究( Operation Research ) 領域，發展成熟的線性規劃( Linear Programming ) 恰好可以來解決，是一個跨領域的應用 !! 已經存在有許多商業或open source 軟體，如: Gurobi ， Cplex ， Xpress ， Mosek ， SCIP  可以輕易求解大型的線性規劃問題。而不僅如此也可以利用整數規劃( Integer Programming )來做特徵選擇 ( Feature Selection )，甚至可以偵測離群值( Detect Outlier ) !! 本文只介紹最小絕對值和，關於 Feature Selection , Detect Outlier 可以參考 Mixed-Integer Linear Programming Robust Regression with Feature Selection , Oleksii Omelchenko , 2010 的論文。 [Data Fitting Problem] 給定$n$筆實數型訓練資料 (training data) $\{(x^{k},y^{k})\}^{n}_{k=1} = \mathcal{D} , x^{k} =(x^{k}_1,x^{k}_2, ... , x^{k}_{p})\in \mathbb{R}^{p}$ , $y^{k} \in \mathbb{R}$ ， 我們目標是想要找到一個函數 $f_{\mathcal{D}} : \mathbb{R}^p \rightarrow \mathbb{R}$ 使得  $\forall x \in \mathbb{R}^{p} , f_{\mathcal{D}}(x) \approx y$ ， 精確來說: $$ \text{Find } f_{\mathcal{D}} \text{ such that } f_{\mathcal{D}}(x)\...
張貼留言
閱讀完整內容

Nash Equilibrium & Best Responce Function (BRF) In Continuous Strategies

經濟學重要的賽局理論( Game Theory )領域，用數學描述人與人之間的理性互動，最重要的就是尋找奈許均衡( Nash equilibrium )， 本篇介紹其數學規劃與非線性方程組!!  假設有 $p$ 名玩家(player $i$)，$i=1,2,3,4,5,....p$ ， 正在玩一場遊戲(Game)~~，完全不合作，各自獨立作決策 每個人有決策向量 $x_i \in \Omega_i \subseteq R^{n_i}$ (有$n_i$個決策變數)  定義長向量: $\underbrace{x =  (x_1,x_2,x_3,....x_p)}_{\# \text{ of } \sum^{p}_{i=1}n_i \text{ variables }} \in  \prod^{p}_{i=1} \Omega_i = \Omega $ 對於每個 player $i$ ，長向量可以寫成 $x = (x_i , x_{-i})$ ，$x_{-i}$ 代表其他人(不是 player $i$) 能做的決策向量。 所有人各自作決策後，每個人都會個自的存在報酬效用函數 $f_i (x)  \in \mathbb{R} $ (報酬函數皆為公開已知資訊) 假設每位玩家是理性人(會極大化自己效用) 即 $$\forall i = 1,2,3,4....p \qquad  \underset{x_i \in \Omega_i}{\text{max }}f_i(x)  $$ [註: 如果為合作可視為多目標規劃問題( multiobjective )，即 $x_1,x_2,...x_p$ 可以由領導人一起決定] [註: 如果為合作而且把效用加總，即目標式變成 $\sum_{i=1}^{p} f_i(x)$ ，可能對集體效益有更大的幫助，但是如何分配效益給 ( player $i$ )會是個議題，可以查關鍵字 fair optimization ] 我們可以定義每個 player i 的 Best Response Function (BRF) or Best Reponce Set $S_i(x_{-i}) \subset \Omega_i$ $$  S_i(x...
張貼留言
閱讀完整內容