跳到主要內容

Expectation Of More Trials

本文為分析電玩裡常見的期望值小問題:

==================================================
如果有 $n$ 個庫存物/道具。每使用 $1$ 次庫存物/道具時，有 $p \in [0,1]$ 的機率不會消耗這次使用，那麼平均而言總共可以使用幾次 ??  有多少扣達(quota) ?? (假設每次使用的機率機制相同，獨立同分布，Bernoulli 試驗)
==================================================

首先先定義隨機變數 $T$ ，代表總共只可以使用了 $T$ 次，而以 $t$ 表示隨機變數的"取值"，根據生活經驗很明顯 $t \in [n,\infty)_{\mathbb{Z}} = \{n,n+1,n+2,.....\}$ 

定義當 $T = t$ (當隨機變數 $T$ 取值為 $t$) 的機率為 $$ P_t := Pr(T=t)  $$

則本文目標為計算期望值:

$$ E[T] =  (\text{可能次數} \times \text{對應的機率}) \text{的總和} $$ $$ = \sum_{t \in [n,\infty)_{\mathbb{Z}}} t \cdot Pr(T=t) = \sum^{\infty}_{t = n} t \cdot P_{t} = \underbrace{ \lim_{N \rightarrow \infty} \left(\sum^{N}_{t = n} t \cdot P_{t}\right) }_{\text{嚴謹寫法}}$$

而機率計算如下:

$$ P_{t}= \overbrace{\left[ \underset{\text{不盡相異物直線排列數}}{\left( \begin{array}{c} t-1 \\ n-1 \\ \end{array} \right)} p^{t-n} (1-p)^{n-1} \right]}^{\text{前 $t-1$ 次，共消耗了 $n-1$ 個道具，得到了$t-n$ 次再使用機會}} \cdot \overbrace{(1-p)}^{\text{最後 1 次 消耗了 1 個道具 }}  $$

則期望值可以寫成一個無窮級數(Infinite Series)

$$  E[T] = \left[ \sum_{t \in [n,\infty)_{\mathbb{Z}}}t \cdot \left( \begin{array}{c} t-1 \\ n-1 \\ \end{array} \right) p^{t-n} (1-p)^{n} \right] $$

因為"組合"等價 :
$$  \left( \begin{array}{c} t-1 \\ n-1 \\ \end{array} \right) =   \left( \begin{array}{c} t-1 \\ t-n \\ \end{array} \right)$$

使用變數變換 : 
$$t \in [n,\infty)  \Longleftrightarrow   k := t-n \in [0,\infty)  \text{ and } t = n+k $$

再提出常數$(1-p)^{n}$ 可以把期望值改寫成
$$ E[T] = (1-p)^{n} \sum_{k=0}^{\infty}\left[(n+k) \left( \begin{array}{c}  n+k-1 \\ k \\  \end{array} \right) p^{k} \right] $$

因為 $(n+k) \left( \begin{array}{c}  n+k-1 \\ k \\  \end{array} \right) = \frac{(n+k)(n+k-1)!}{k! (n-1)!} = n \cdot \frac{(n+k)!}{n!k!} = n \cdot   \left( \begin{array}{c}  n+k \\ k \\  \end{array} \right) $

所以最後得到~
$$E[T] = n(1-p)^{n} \underbrace{\left[\sum^{\infty}_{k= 0} \left( \begin{array}{c}  n+k \\ k \\  \end{array} \right) p^{k}\right]}_{(1-p)^{-(n+1)}} = \frac{n}{1-p} $$


其中會用到的"以下式子"為二項式定理的結果，可參考 wiki (Probability mass function  章節)
$$ (1-p)^{-(n+1)} =  \left[\sum^{\infty}_{k= 0} \left( \begin{array}{c}  n+k \\ k \\  \end{array} \right) p^{k}\right] $$

我們可以做個邊界分析~ 檢驗一下計算的答案是否合理~   當 $p = 0$ 時 則  $E[T] = n$ 合乎常理 ，當 $p \rightarrow 1$ 則 $E[T] \rightarrow \infty$ 合乎常理!!

實際應用 : 身上帶了 10 瓶藥水，每次使用有 $25\%$ 的機率不會消耗。則根據期望值公式相當於身上帶了 $\frac{10}{1-0.25} = \frac{10}{0.75} = 13.33333  $ 瓶


[小結]
事實上此問題為負二項分布(nonegative binomial distribution)的應用版本，而本文是以直接計算方法解決!! 分享對機率有興趣的讀者~



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

留言

張貼留言

這個網誌中的熱門文章

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

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

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