Блог

100 человек смотрят театр.В конце шоу все они посещают раздевалку, чтобы взять свои пальто.Человек, работающий в раздевалке, отдает пальто людям совершенно случайным образом.Участники, которым они подберут подходящее пальто, уходят.Другой, который выбрал не того, вернет пальто, и мужчина снова случайным образом вернет пальто.Процесс заканчивается, когда все посетители театра забирают свое правое пальто.

Я хочу смоделировать в R этот процесс мартингейла, чтобы определить ожидаемое время окончания этого процесса. Но я не знаю, как это сделать .Какая-нибудь помощь ? Что-то вроде:

 

# 100 customers
x = seq(1,100,by=1);x
# random sample from x 
y = sample(x,100,replace=FALSE)
x==y
# for the next iteration exclude those how are TRUE and run it again until everyone is TRUE


 

Ожидаемое время-это количество итераций там, где это необходимо .

Или что-то в этом роде :

 
n = 100
X = seq(1,100,by=1)
martingale = rep(NA,n)

iterations = 0
accept     = 0
while (X != n) {
  iterations =  iterations   1
  y = sample(1:100,100,replace=FALSE)
  if (X = y){ 
    accept = accept   1
    X = X 1
    martingale [X] = y
  }
}
accept
iterations

 

Один из способов сделать это заключается в следующем (используя 10 человек в качестве примера, оператор печати не нужен, просто чтобы показать, что делается на каждой итерации):

 set.seed(0)
x <- 1:10
count <- 0
while(length(x) > 0){
  x <- x[x != sample(x)]
  print(x)
  count <- count   1
}

# [1]  1  2  3  4  5  6  7  9 10
# [1] 3 4 5 6 7 9
# [1] 3 4 5 6 7
# [1] 3 4 5 6 7
# [1] 3 4 5 6 7
# [1] 3 4 5 6 7
# [1] 3 4 5 6 7
# [1] 3 4 5 6 7
# [1] 3 6
# 
count
# [1] 10
 

Для каждого шага цикла он удаляет значения x, в которых клиенты были случайным образом распределены по своему пальто, до тех пор, пока их не останется.

Чтобы использовать этот код для получения ожидаемого времени, затраченного на 100 человек, вы можете расширить его до:

 set.seed(0)
nits <- 1000 #simulate the problem 1000 times
count <- 0
for (i in 1:nits){
  x <- 1:100
  while(length(x) > 0){
    x <- x[x != sample(x)]
    count <- count   1/nits
  } 
}
count
# [1] 99.901
 

Я выдвигаю гипотезу без доказательств, что ожидаемое время для n человек — это n итераций-это кажется довольно близким, когда я пробовал с 50, 100 или 200 людьми.

Я не следил за вашим обсуждением выше, и я не совсем уверен, что вы этого хотите, но мое обоснование было следующим:

• У вас есть N человек, и вы ставите их в очередь.
• В первом раунде у первого человека есть шанс 1/N правильно одеться.
• На данный момент у вас есть два варианта. Либо человек 1 правильно одевается, либо нет.
• Если человек 1 правильно оденется, то у человека 2 есть шанс 1/(N-1) правильно одеться. Если человек 1 не получил правильную одежду, человек 1 остается в бассейне (в конце), и у человека 2 также есть вероятность 1/N, чтобы правильно одеться.
• Вы продолжаете назначать эти вероятности до тех пор, пока все N человек не увидят клерка один раз. Затем вы сортируете тех, у кого есть правильная одежда, и повторяете шаг 1, пока у всех не будет подходящей одежды.
• Для целей моделирования вы, конечно, повторили бы все это 1000 или 10000 раз.

Если я вас правильно понимаю, вас интересует количество итераций, т. Е. Как часто клерку приходится проходить всю очередь (или то, что от нее осталось), пока все не получат свою одежду.

библиотека(tidyverse)

 people <- 100
results <- data.frame(people     = 1:people,
                      iterations = NA)

counter <- 0
finished <- 0

while (finished < people)
{
  loop_people <- results %>%
    filter(is.na(iterations)) %>%
    pull(people)

  loop_prob <- 1/length(loop_people)
  loop_correct <- 0

  for (i in 1:length(loop_people))
  {
    correct_clothes_i <- sample(c(0,1), size = 1, prob = c(1-loop_prob, loop_prob))
    if (correct_clothes_i == 1)
    {
      results[loop_people[i], 2] <- counter   1
      loop_correct <- loop_correct   1
      loop_prob <- 1/(length(loop_people) - loop_correct)
    }
  }
  counter <- counter   1
  finished <- length(which(!is.na(results$iterations)))
}

max(results$iterations)

[1] 86

head(results)

  people iterations
1      1          7
2      2         42
3      3         86
4      4         67
5      5          2
6      6          9
 

results$iterations Столбец содержит номер итерации, в которой каждый человек правильно оделся, таким образом max(results$iterations) , вы получите общее количество циклов.

У меня нет доказательств, но эмпирически и интуитивно количество требуемых итераций должно приближаться к N.