Processing math: 1%
跳到主要內容

Expected Ratio of n trials & Probability Generating Function



本文介紹如何利用機率母函數(Probability Generating Function) 推導  \color{red}{獨立n 局期望比例(投資報酬率)的解析式},相關概念與延伸問題

[機率情境]
現實生活中,往往是有付出(Paid) 可能會有回報(Gain)。
設樣本元/空間記做 \omega \in \Omega|\Omega|<\infty,單局發生機率為 p_{\omega} 此時會有產生成對樣本 (Gain(\omega),Paid(\omega))
代表有 \color{red}{p_{\omega}} 機率,你會先付出\color{blue}{Paid(\omega)} \neq 0 元,而最後會回收 \color{blue}{Gain(\omega)} 元 ,當局淨收入為 Gain(\omega)-Paid(\omega),單局投資報酬率為 \frac{Gain(\omega)}{Paid(\omega)}
而單局期望投資報酬率為 \sum_{\omega \in \Omega} p_{\omega}\left(\frac{Gain(\omega)}{Paid(\omega)}\right) =:  E\left[\frac{X_i}{Y_i}\right]
其中 (X_i, Y_i) 為隨機變數序對 : (回收值,付出值) (X_i,Y_i) \overset{iid}{\in} \bigg\{(Gain(\omega),Paid(\omega))  \bigg\}_{p_{\Omega}=(p_{\omega})}

[n局期望比例(投資報酬率)]
然而往往會參與 n 局,投資報酬率(隨機變數)為 \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i} ,目標是如何計算出 E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right]  ??,很明顯即使每局是獨立同分布,一般情況下,E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right] \neq E\left[\frac{X_i}{Y_i}\right]

[機率母函數]
以上問題可以從另一個角度切入,首先考慮以下二元多項式 f(x,y) := \sum_{\omega \in \Omega} p_{\omega} x^{Gain(\omega)}y^{Paid(\omega)}
===========================================================
多項式意義:
其中每一項 x 的指數部分代表回收值Gain(\omega)y 的指數部分代表付出值Paid(\omega),"係數(coefficient)"代表機率,"多項式乘法"代表邏輯 and ,"多項式加法" 代表邏輯互斥 or  ,而且 f(1,1) = 1 = \sum_{\omega \in \Omega} p_{\omega} 代表機率和為 1 ,f(x,y) 的每一項相當於描述了以上的機率情境
===========================================================
參與獨立 n 局的機率母函數相當於  [f(x,y)]^n =  {\left[\sum_{\omega \in \Omega} p_{\omega} x^{Gain(\omega)}y^{Paid(\omega)}\right]}^{n}
雖然現實往往項數 m \approx |\Omega|^{n} 過多(即使是電腦)也無法短時間完全展開,但理想狀況應該會長的像以下那樣

[f(x,y)]^{n} =  \overbrace{ (p_{1} x^{Gain_1}y^{Paid_1} ) + .... +  ( p_{m} x^{Gain_m}y^{Paid_m} ) }^{\text{天文項數}}

所求如以下的式子:
\color{red}{E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right] =  \sum_{i=1}^{m} p_{i}\left(\frac{Gain_{i}}{Paid_{i}}\right)}
註: 這裡的 p_{i}p_{\omega} 意義不同,勿混淆

[微積分操作妙用]
仔細觀察[f(x,y)]^{n} 的每個單項,也就是(p_{i} x^{Gain_i}y^{Paid_i}),碰巧先對它對 x 偏微分,除 y 後再對 y 偏不定積分,會變成以下的樣子

p_i \bigg( \underbrace{Gain_i \cdot  x^{Gain_i-1}}_{\text{對 $x$ 偏微效果}} \cdot  \overbrace{ \frac{y^{(Paid_i-1) +1} }{(Paid_{i}-1) +1}  + C(x)}^{\text{先除 $y$ 再對 $y$ 偏不定積分}} \bigg)

這時取 x=1y \in [0,1] 定積分,如果 Paid_{i} \neq 0 ,會發現單項變成 p_{i} \cdot \left(\frac{Gain_{i}}{Paid_{i}}\right) 就是我們要的~
============================================================
\color{blue}{背後精神:  微分可以把指數丟到係數的分子部分,不定積分可以把指數丟到係數的分母部分}
============================================================

所以所求可以寫成
   E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right] = \int_{y \in (0,1]}\frac{1}{y} \left. \frac{\partial}{\partial x} [f(x,y)]^n \right|_{x=1}     
\color{purple} {此時 \text{Chain Rule} 大招登場 !!,可以不用真的把多元多項式天文展開就可以求值了 }
  \frac{\partial}{\partial x}  [f(x,y)]^n  =   n [f(x,y)]^{n-1}  \frac{\partial}{\partial x} f(x,y)

最後就得到"獨立n 局期望比例(投資報酬率)的解析式"

\color{red} { E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right] =  n \int_{y\in (0,1]}   \left( \sum_{\omega \in \Omega} p_{\omega} y^{Paid(\omega)}   \right)^{n-1}  \left(\sum_{\omega \in \Omega} p_{\omega} \cdot Gain(\omega) \cdot y^{Paid(\omega)-1} \right) } =\text{定積分 $ \int_{0}^{1}g(y)dy $ 問題} 

此時就可以使用黎曼積分/數值積分(Numerical Integration)演算法群,馬上估算出精確值 :)
[小統計應用]
如果夠多的人參與此機率情境,而且都玩 n 局,根據大數法則,投資報酬率的平均為所求 !!


[延伸問題]
有兩個問題,由於筆者不確定是否正確,留給讀者幫忙尋找真相,若有想法/證明也歡迎留言來信。
(1) 當 n \rightarrow \infty 是否一定存在極限 ??
(2) 若有極限是否一定等於"單局期望回報值"除以"單局期望付出值" ?? \lim_{n \rightarrow \infty } E\left[ \frac{\sum_{i=1}^{n}X_i}{\sum_{i=1}^{n}Y_i}\right] \color{red}{\overset{?}{=}} \frac{\sum_{\omega} p_{\omega} Gain(\omega) }{\sum_{\omega} p_{\omega} Paid(\omega)} = \frac{ \lim_{n \rightarrow \infty}E[\bar{X}]}{ \lim_{n \rightarrow \infty} E[\bar{Y}]} = \frac{E[X]}{E[Y]}

\color{red}{\text{**Warning**}  筆者的不負責直覺概念是 (1) 存在,(2) 不相等!! }



[小結]
利用機率母函數計算期望值發現,多元多項式的"指數"用途並非只是拿來當作取值次方使用,而是可以拿來當作"計數",雖然項數很多不切實際,但往往是容易讓人理解的方法,而配合微積分的操作,恰好有機會可以捕捉一些我們想計算的值 !!


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



留言

這個網誌中的熱門文章

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...

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}(\col...

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)\...