標籤：

概率概率論演算法統計

一張五十首歌的歌單，每首歌三到五分鐘，隨機播放。至少聽多少分鐘才能有90%的把握把每首歌都聽過了？

01-21

「隨機播放」指的就是音樂軟體里的隨機播放模式。
「三到五分鐘」指歌曲時長服從（3min，5min）均勻分布
假設我不快進不快退不暫停，一直聽
今天聽歌時想到這個問題，覺得蠻有意思的，求解答或解答思路

寫了個程序來模擬。模擬時有如下假設：

模擬以秒為單位進行，一首歌的長度服從180s ~ 300s的離散均勻分布；
一首歌播放完畢後，以等概率選擇下一首歌；
歌曲的長度是事先未知的。實際上，哪怕是已經播放過的歌曲，再次播放時我仍然認為其長度是未知的。否則需要記住已經播放過的每首歌的長度，就麻煩了。

模擬過程是這樣的：

用二元組 $(i,j)$ 表示當前播放狀態：

下標 $i$ 表示還有多少首歌沒有開始播放， $0 le i le 50$ ；
下標 $j$ 表示當前歌曲還剩下多少秒， $0 le j < 300$ 。

按上面定義，狀態 $(0,0)$ 表示剛剛播放完所有歌曲。

我們同時令它成為一個吸收態，即播放完所有歌曲之後，永遠停留在這個狀態。

用 $P_{i,j}^{(k)}$ 表示 $k$ 秒後狀態的概率分布。

初始分布為 $P_{50,0}^{(0)} = 1$ ，其它 $P_{i,j}^{(0)} = 0$ 。

由 $k$ 秒向 $k+1$ 秒的遞推如下進行：

對於任何 $j>0$ ， $P_{i,j}^{(k)}$ 全部傳遞給 $P_{i,j-1}^{(k+1)}$ ；
對於 $j=0$ ， $i>0$ ， $P_{i,j}^{(k)}$ 中有 $i/50$ 的比例平均分配給 $P_{i-1,179}^{(k+1)}$ 至 $P_{i-1,299}^{(k+1)}$ （下一首播放的是新歌），有 $1-i/50$ 的比例平均分配給 $P_{i,179}^{(k+1)}$ 至 $P_{i,299}^{(k+1)}$ （下一首播放的是老歌）；
$P_{0,0}^{(k)}$ 全部傳遞給 $P_{0,0}^{(k+1)}$ 。

我們認為「所有歌都聽過」指的是「所有歌都聽完」，那麼要求的就是使得 $P_{0,0}^{(k)} ge 90\%$ 的最小的 $k$ 。

$P_{0,0}^{(k)}$ 的圖象如下，使得 $P_{0,0}^{(k)} ge 90\%$ 的最小的 $k = 73119 , ext{s} = 1218.65 , ext{min}$ 。

@宇詡的答案雖然錯誤地使用了獨立性假設，但結果與我的模擬竟然十分接近。

這裡還有一個實際問題就是播放軟體往往是偽隨機……各首歌不是等概率出現的。

大家看看這樣做有沒有什麼問題呢？（見圖片）

聽N首之後還沒有聽過第i首歌的概率是

$(frac{49}{50})^N$

我們用union bound拿一個上限的估計，那麼需要N使得上式小於等於(1-0.95)/50, 也就是N = 342，

這時，有95%的可能聽過所有的歌。

當然還有一層tail bound,也就是播放時間，342首歌的播放時間的話應該和Gaussian差不多了(嚴格的話換用Hoeffding"s inequality)，期望是

4*342=1368min,

標準差 sqrt(342/3) min， 3個sigma差不多，所以聽1368+11*3= 1401min時有95%的概率聽完342首歌。

再用一次union bound,在聽過1401分鐘之後至少有90%概率聽過所有歌。

並不緊，不過提升空間不大了。。

現在的播放器是不重的擦汗

你們都是神嗎？

亂答一通。請指正。

播放n首歌曲的總耗時大致符合高斯分布 $mathcal{N}(4n,frac{n}{3})$ ，有概率密度函數 $f_n(t)$ .

又知道當t&>5n or t&<3n的時候 $f_n(t)=0$

P[消耗時間不超過 $T$ |播放n首歌曲]= $int_{-infty}^{T} f_n(t)dt$

P[播放恰好n首歌曲|消耗時間恰好是 $T$ ]= $G(n,T)=frac{frac{ ext{d}int_{-infty}^{T} f_n(t) ext{d}t}{ ext{d}t}}{ frac{ ext{d}sum_{n=1}^{infty}{ int_{-infty}^{T} f_n(t) ext{d}t}}{ ext{d}T} } =frac{f_n(t)}{sum_{n=1}^{infty}f_n(t)}$

播放n首歌曲之後有k首已經聽過的概率是

$P(n,k)=frac{51-k}{50}P(n-1,k-1)+frac{k}{50}P(n,k)$

$P(1,1)=1;P(1,m)=0 ext{ for } m>1$

（計算知道 $P(300,50)=0.88909$ ，沒啥用……）

消耗時間不超過T，恰好有50首聽過的概率是 $sum_{n=1}^{infty}{P[n,50]G(n,T)}$

當 $T=1221.694$ ,這個式子大概是0.9。

這個數字竟然和 @王贇 Maigo 以及 @宇詡的答案如此接近……

在所有的討論中T&<1500,所以可以給n設個上限500.

請問哪個音樂播放軟體的隨機播放一直不停地放會重複播放放過的歌？所以不懂都在算些什麼

推薦閱讀：

※伽瑪分布和指數分布的關係？
※誰能比較淺顯易懂地解釋下Restricted Boltzmann Machine,或者提供相關的鏈接？
※一群人同時咳嗽的機率有多大？
※廣義線性模型（GLM）中的Binomial分布的連接函數為什麼是logit？
※如何計算空方格數的期望？

TAG:演算法 | 概率 | 統計 | 概率論 |