題目敘述
這道題是我在 UChicago Booth 的 CAAI 做到的，題目敘述大致如下：
- A 每天會到他最愛的餐廳吃午餐。這間餐廳的菜單上有三十道不一樣的菜，A 每次吃飯都會隨機（uniformly）點一道菜。問 A 平均而言要花多少天才能把菜單上的菜至少都吃過一次？此問題接受模擬的數值解，也接受數學上的解析解。
- 承上題，如果 A 不是均勻隨機地點餐，那平均而言他會花更長還是更短的時間才能至少每道菜都吃過一次？
Monte Carlo Simulation
遇到暫時想不到怎麼解的問題，當然先用模擬的看一下近似的答案應該是多少，然後再拼湊看看！幸好規則相當容易，要模擬並不困難。
eat_them_all <- function(){
# once called: A visits the lunch place until eating all 30 dishes
# input: none
# output: the number of days A spent finishing the task
menu <- 1:30
count <- 0
eaten_items <- c()
while( sum(unique(eaten_items) %in% menu)!=30 ){
eaten_items <- c(eaten_items, sample(1:30, size = 1, replace = T))
count <- count + 1
}
return(count)
}
# Monte Carlo
res <- replicate(n = 1000, eat_them_all())
hist(res)
mean(res) #119.8727
sd(res) #36.3763
模擬的結果告訴我們 A 平均而言要花上 119.8728 天才能吃過每一道菜。但第二小題就非常不好模擬了，因為我們沒辦法窮盡所有的點菜法（如何「隨機」地點菜），所以不容易透過模擬得出答案。
做到這裡時，我便開始想這背後的機率分配會是什麼。直覺告訴我跟 Negative Binomial 或者 Geometry 很像，只是一直沒辦法好好找到「一個」隨機變數來描述上面的過程。於是開始利用模擬出來的結果算各階動差，想要湊湊看會是哪個分配的隨機變數最像。
殊不知，其實這個問題很巧妙地，只是「多個」不同參數的幾何分配隨機變數加總的結果！
解析解
我們先來看看一個數列的和：
total <- 0
for(i in 1:30){
total <- total + 30/i
}
print(total)
>>> 119.8496
也就是：
$$ \frac{30}{1} + \frac{30}{2} + \frac{30}{3} + \dots + \frac{30}{30} $$
看起來跟我們的模擬解相當像！實際上這個數列就代表 30 個幾何分配隨機變數的期望值，而我們想求得的解正式這 30 個隨機變數的期望值加總！
我們用：
$$ Geo(p_k) $$ 表示要至少吃到一次第 k 道菜的機率分配
什麼意思呢？當 A 第一天去吃午餐的時候，他從 30 道菜隨機地任選一道，我們就把這道菜當成第一道菜，也就是它被吃到的機率就是 30/30 = 1。所以吃到第一道菜 （ k = 1 ）可以機率可以用 Geo(1) 來描述。
到了第二天， A 再去吃午餐時仍舊是擲個三十面的公正骰子來決定吃哪道菜。此時無論吃到哪一道菜，只要不是前一天吃到的那道，我們便把它當成第二道菜。我們便知道第二道菜被吃到的機率是 29/30 ，而且每天都是一樣且獨立的！那當然就可以用 Geo(29/30) 來描述囉！
依此類推，直到剩下最後一道菜還沒被吃到時，我們知道它被吃到的機率是 1/30 ，而且每天都是相同的獨立成敗試驗，直到吃到最後一道菜才停下來。那當然就是以 Geo(1/30) 來描述。所以最終我們想知道的平均天數就會是以下這個期望值的和：
$$ E(X_1 + X_2 + X_3 + \dots + X_30) where X_k \stackrel{i.i.d.}{\sim} Geo(p_k)$$
所以答案才會是上面提到的數列的和。至於第二小題，只要用幾何分配去想就十分簡單了！