今日頭條、支付寶集卡過程中學習點新知識!——卡券收集問題

新春快到了,首先祝福大家新的一年裡身體健康,小朋友們學業有成,大朋友們事業順利!然後新春佳節之際大家心心念的就是馬雲爸爸的五福、張一鳴叔叔的十二生肖有木有集齊,小編表示支付寶和今日頭條全部差一張卡,心痛!

時間彷彿又回到了 20 年前,那些年我們還是懵懂無知少年,買著5毛一袋的小浣熊速食麵,就是為了集齊那夢寐以求的 108 張水滸英雄卡。

時間不斷流逝,收集的東西不斷的發生變化,不變的是我一直集不齊。

Coupon Collector『s Problem

上面的無論是支付寶集五福,還是今日頭條集十二生肖,抑或是集水滸傳卡、寵物小精靈卡等等等,都可以看做是概率論中一類重要問題——Coupon Collector『s Problem。其形式化定義如下:

Advertisements

假設有 n 種卡券,每種卡券獲取機率已知,而且卡券亦無限供應。假設我們想集齊這 n 種卡券,我們平均需要獲取多少張卡券?

顯然這是個求期望問題,而且結果取決於每張卡券獲取的幾率。首先我們看個簡單的情形,即所有卡券獲取概率相等。

1.每張卡券獲取概率均等

這時每種卡券都是等價的,我們只需依次計算收集第 1、2、...、n 種卡券所需的次數即可。顯然收集第 i 種卡券所需的次數服從幾何分佈——即概率為 p 的事件 A ,以 X 記 A 首次發生所進行的試驗次數,則X的分佈列

由 Moment Generating Function 函數易得幾何分佈的期望和方差如下:

所以現在我們只需搞明白收集到第 1、2、...、n 種卡券的概率即可。假設我們已經收集到了 k 種卡券,那麼對於第 k+1 種卡券,我們有 k/n 的概率拿到已有的卡券,所以收集到第 k+1 種卡券的概率為 (1-k/n)。

Advertisements

綜上,我們集齊所有 n 中卡券的期望為:

最下的 Hn 表示第 n 個調和數。用 Python 簡單寫個計算公式算一下我們集齊 n 種卡券的期望。

使用上面函數計算 n = 5, 14, 108時的結果:

(1)假設 n = 5,即我們集齊五福的期望收集次數為 11.4 次。

(2)假設 n = 14,即我們集齊發財十二生肖的期望收集次數為 45.5 次。

(3)假設 n = 108,即我們集齊108將的期望收集次數為 568.5 次。

對於支付寶五福我收集的數量遠遠超過這個數了,然而還是沒有集齊!顯而易見我們知道支付寶卡「敬業福」,今日頭條卡「發卡」,寵物小精靈卡「超夢」,水滸卡卡啥我記不清了,印象中是令狐沖?這就引出了卡券獲取概率不等情形下的期望求解。

2.每張卡券獲取概率不等

假設第 1、2、...、m 種卡券的概率分別為 p1、p2、...、pm。這時我們可以將收集這 m 種卡券看成 m 個獨立的泊松過程。那麼問題的答案就可以等價位這 m 個泊松過程第一次出現事件時刻的最大值。由單個泊松過程的事件概率以及獨立事件概率公式可得:

那麼此時期望次數為:

我們使用 scipy 來計算這個定積分,其中 probability 是一個列表,表示每個事件發生的概率。

我們對支付寶五張卡片分配概率來驗證一下這個函數正不正確:

(1)首先回歸特殊情形,讓每張卡片的概率都相等,那麼 probability = [0.2,0.2,0.2,0.2,0.2], 此時其計算結果也為11.4,說明我們的公式應該是正確的。

(2)然後假設我們的敬業福獲取概率只有 0.01,其餘四張概率均等,那麼期望值為 100.4 次,即我們要掃 100 次福或者澆 100 次水才能集齊,這貌似比較有道理了。

(3)最後我們讓五張福卡的獲取概率分別為[0.9999/4, 0.9999/4, 0.9999/4, 0.9999/4, 0.0001], 此時集齊的期望次數為 10000 次!這彷彿再次感受到了 2016 年被敬業福支配到的恐懼!

總結

本文主要介紹了概率論中一個有意思的問題——卡券收集問題,並給出了卡券收集問題由簡單到複雜情形的分析,並用代碼做了實際驗證。當然這裡面只考慮了一個人集卡的情形,若考慮到不同人可以交換卡和某些卡的數量有真實數量限制那麼問題將非常複雜,此時用蒙特卡洛模擬分析會是一個更好的選擇!

最後祝願大家都能集齊想要的東西!

Advertisements

你可能會喜歡