在 R 中餐厅的平均时间

Question

我正在访问一家菜单上有 N 道菜的餐厅。每次我去餐厅我都会随机挑选一道菜。我在想，我把餐厅的N道菜都吃完平均需要多少时间？

我认为我在餐厅n次访问后品尝的菜品数量是一个具有转移概率的马尔可夫链：

p_{k,k+1} = (N-k)/N

和

p_{k,k} = k/N 

for k =0,1,2,...,N

我想在R中模拟这个过程。鉴于餐厅有 100 道菜，我这样做（我在这里需要帮助）：

nits <- 1000 #simulate the problem 1000 times
count <- 0
N = 100 # number of dishes 
for (i in 1:nits){
 x <- 1:N
 while(length(x) > 0){
   x <- x[x != sample(x=x,size=1)] # pick one dish at random that I have not tasted
   count <- count + 1/nits
 } 
}
count

我需要一些帮助，因为我的数学结果是平均时间是 N*log(N) 而上面的代码产生了不同的结果。

Answer 1

您有 2 个问题。

当你循环 i 时，它总是一个危险信号，但不要在循环内使用 i。设置一个结构来保存每次迭代的结果：

results = integer(length = nits)
...
for (i in 1:nits){
 ...
 while(length(x) > 0){
   ...
 } 
 results[i] <- count
}

你的文字说

pick one dish at random

你的代码说

pick one dish at random that I have not tasted

如果您总是挑一道没尝过的菜，那么问题就微不足道了——需要 N 次访问。让我们调整你的代码来随机选择菜品，无论你是否品尝过：

nits <- 1000 #simulate the problem 1000 times
results = integer(length = nits)
N = 100 # number of dishes 
for (i in 1:nits){
  dishes = 1:N
  tasted = rep(0, N) 
  count = 0
  while(sum(tasted) < N){
    tasted[sample(dishes, size = 1)] = 1
    count = count + 1
  } 
  results[i] = count
}
results

看结果，我想你可能犯了一个数学错误：

100 * log(100)
# [1] 460.517
mean(results)
# [1] 518.302

您可以在维基百科上阅读有关此问题的更多信息：Coupon Collector's Problem。使用那里的结果，模拟效果很好：

100 * log(100) + .577 * 100 + 0.5
# [1] 518.717

在 R 中餐厅的平均时间

Average time in a restaurant in R

r

probability

stochastic-process