歌曲隨機播放，每首最少播放一次的期望是多少？

02-02

假設我有100首歌，現在開始隨機播放，我平均需要播放多少遍才能讓每首歌最少播放一遍。遇到這樣的問題應該怎麼考慮。

實際的播放次數其實與播放器的隨機播放實現有關。如果我們假設這個隨機播放是真的隨機的，那麼這個問題在知乎上以不同形式出現過N次了，我來總結一下以及相應的增強版，其中相關問題的鏈接中可以找到對應的答案。

樓主的問題對應問題一或問題四。

問題一：依次地做獨立試驗，其中每次實驗有n種等概率的結果，問：要使得每種結果都至少出現一次平均需要做多少次試驗。

答案： $nleft(1+frac{1}{2}+cdots +frac{1}{n} ight)$

相關問題：假設小浣熊隨機贈送的卡片共有 100 種（出現概率相同），那麼集齊所有卡片所需購買小浣熊包數的數學期望是多少？ - 趣味數學

問題二：依次地做獨立試驗，其中每次實驗有n種等概率的結果，問：要使得每種結果都至少出現m次平均需要做多少次試驗。

相關問題：A B C D E F G H I 9個字母，每次隨機獲得其中一個概率相等。集齊兩套不重複的9字母平均需要多少次獲取？ - 程序員

問題三：依次地做獨立試驗，其中每次實驗有n種等概率的結果，實驗分批進行，每批進行k個實驗。問：要使得每種結果都至少出現一次平均需要做多少批試驗。

答案： $sum_{i=1}^n (-1)^{i+1}inom{n}{i}frac{1}{1-inom{n-i}{k}ig/inom{n}{k}}$

相關問題：樣本空間為M，每次隨機選取N個樣本，X次選取之後剛好每個樣本都至少被選取一次，請問X的期望值是多少？ - 數學

問題四：依次地做獨立試驗，其中每次實驗有n種結果，其概率依次為 $p_1,p_2,cdots,p_n$ 。問：要使得每種結果都至少出現1次平均需要做多少次試驗。

答案： $sum_{i=1}^n sum_{1leq k_1 < cdots < k_ileq n} (-1)^{i+1}frac{1}{p_{k_1}+cdots + p_{k_i}} = sum_{i=1}^n frac{1}{p_i} - sum_{1leq k_1<k_2leq n}frac{1}{p_{k_1} + p_{k_2}} + cdots$

考慮到某些播放器的隨機其實是shuffle而不是random, 只要100次就夠了...(

See Coupon collectors problem, its about 100 * ln(100) ~ 460.5 times.

這是coupon collector problem，wiki有的。在對n首歌隨便選時，全遍歷到所用的次數的期望為 n(1+1/2+1/3+...+1/n) 趨於nlogn，當n趨於無窮

大致是這樣

這個簡單，看你的播放器隨機播放的代碼就好了