隨機模擬【2】：隨機模擬的研究範圍和特徵-2

09-18

來自專欄確定性隨機

個人覺得隨機模擬有一個很大的優勢，那就是用類似於思想實驗的方式對理論進行驗證，同時也能夠解決很多理論上無法最終解析的事情，給出一個近似但很實際用處的結論。

1. 優惠券收集問題

曾經在知乎上看過這樣一個問題：

話說古代中國帝王都是後宮佳麗三千，問若每天晚上皇帝都隨機地寵幸一位妃嬪，問需要多少天才能將三千妃嬪都寵幸一遍？

這個問題就是典型的所謂優惠券收集問題。上面那個問題和小時候吃脆面攢齊梁山水滸一百單八將平均需要吃多少包脆面呢。我們可以假設，當前我們已經湊了 $n$ 個水滸人物，假設要抽到 $n+1$ 人物，需要再消費 $x$ 包乾脆面。在消費者 $x$ 包乾脆面中，我們抽到重複卡片的概率：

$P_1 = P( 抽到重複角色)=frac{n}{N}，其中 N=108$ , $P_2 = P（抽到不重複角色）＝frac{N-n}{N}$

我們成功抽到 $n+1$ 個人物角色時，一共失敗了 $x$ 次，符合幾何分布：

$P(n ightarrow n+1) = (1-P_2)^x imes P_2 Rightarrow E(x) = frac {1} {P_2} = frac { N } {N - n } = frac {108}{108-n}$

所以，你要集齊108個梁山好漢，那麼你要吃掉的（或者買）乾脆面的數量為：

$S = sum_{i=1}^{107} frac {108}{108-i} = 527$ ，

期望你要吃500多包才能湊夠。（同樣，我們可以計算那個皇帝寵幸3000妃嬪的題目）。當然，這都是理想情況，我們假設的是每個卡片出現的概率是一樣的，但實際情況是商家會故意讓某些卡片出現的概率很低，從而就會增加購買的次數。

現在我們將問題反過來一下，為了簡化下問題，我們把問題改為集齊6張優惠券而不是108個英雄好漢卡，現在問題是我買了12包脆面，那麼我能夠集齊6張優惠券的概率是多少呢？其實這個是一個累計概率的計算問題，設 $P_i$ 為第 $i$ 次集齊6張優惠券的概率，顯然有 $i geq 6$ ,於是我們的原問題就是求解:

$P (X = 集齊6張優惠)＝ sum_{i=6}^{12} P_i$

這個問題直接求解的難度較高，我們可以用隨機模擬的方式來解決這個問題。我們考慮1-6為數字平均分布，每次連續獲取12個隨機數，如果這12個隨機數裡面包含完整的1-6共6個數字，那麼就認為這12次的抽券獲得了完整的優惠券組合。Python代碼如下（雖然這本書要求使用的是Matlab，這個我之後再了解下吧：P）：

import numpy as npdef simulate_lottery(num_of_take): ret = 0 upper = 6 # 完整優惠券組合的數量 lottery_number_set = set() for n in range(num_of_take): rand_lottery_number = np.random.randint(1,upper+1) lottery_number_set.add(rand_lottery_number) len_of_set = len(lottery_number_set) if len_of_set == 6: ret = 1 print "collect a different cards" else: ret = 0 print "this card is what i have already owned" return retnum_of_experiences = 1000 num_of_lottery_to_take = 12 #抽取優惠券的次數##completed_collect = 0for i in range(num_of_experiences): completed_collect += simulate_lottery(num_of_lottery_to_take)print completed_collect

重複做了1000次實驗，得到的結果是431，也就是說連續抽12次，能夠集齊優惠券的概率大概是43.1%。下面的問題是，隨著抽的次數增加，能夠集齊優惠券的概率是如何變化的呢。對上面的代碼稍微修改下：

# -*- coding: utf-8 -*-import numpy as npdef simulate_lottery(num_of_take): ret = 0 upper = 6 lottery_number_set = set() for n in range(num_of_take): rand_lottery_number = np.random.randint(1,upper+1) lottery_number_set.add(rand_lottery_number) len_of_set = len(lottery_number_set) if len_of_set == 6: ret = 1 print "collect a different cards" else: ret = 0 print "this card is what i have already owned" return retnum_of_experiences = 1000#num_of_lottery_to_take = 12completed_collect = 0pro_ret = {}for num_of_lottery_to_take in [12,20,25,35,45,50,60]: #定義抽取的次數 for i in range(num_of_experiences): completed_collect += simulate_lottery(num_of_lottery_to_take) pro_ret[num_of_lottery_to_take] = completed_collect print pro_ret

結果是：

{35: 982, 12: 421, 45: 998, 50: 1000, 20: 846, 25: 956, 60: 1000}

可見，抽到25次以後，能收集完整獎券的概率已經升到95.6%。