跳到主要內容

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

留言

張貼留言

這個網誌中的熱門文章

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

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

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