How to simulate a martingale problem in R ?

100 people are watching a theater.At the end of the show all of them are visiting the vesting room in order to take their coats.The man working on the vesting room give back people's coat totally at random.The customers that they will pick the right coat leave.The other that have picked the wrong one, give back the coat and the man again randomly gives back the coat.The process ends when all the customers of the theater take back their right coat.

I want to simulate in R this martingale process in order to find the expected time that this process will end. But I don't know how .Any help ?


# 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


The expected time is how many iterations where needed .

I'm sure there is a much cleaner way to do this, but I think this works the way you described

x = seq(1,100,by=1);x
iterations = 0
customer = 1
while(customer<=100){
  iterations = iterations + 1;
  rand = sample(x[1]:x[length(x)],1);
  if(customer == rand){
    customer = customer + 1
    x <- tail(x, -1);
  }
}
iterations

edit: I realized I might have misinterpreted how iterations are counted, my initial solution assumed you were trying one coat at a time; if the problem counts distributing a random coat to everyone as one iteration, then this should work:

x = seq(1,100,by=1);x
y = sample(x,100,replace=FALSE);y
iterations = 0
while(length(x)>0){
  x <- x[!(x==y)];x
  y = sample(x,length(x),replace=FALSE)
  iterations = iterations + 1
}
iterations
1 Like

awesome!!!! thanks for your answer.very clear and meaningful code.