1
$\begingroup$

I want to solve the following problem by simulation.

There is a bus with 100 labelled seats (labelled from 1 to 100). There are 100 persons standing in a queue. Persons are also labelled from 1 to 100.

People board on the bus in sequence from 1 to n. The rule is, if the person ‘i’ boards the bus, he checks if seat ‘i’ is empty. If it is empty, he sits there, else he randomly picks an empty seat and sits there. Given that 1st person picks seat randomly, find the probability that 100th person sits on his place i.e. 100th seat.

I found MATLAB code that performs the simulation,and I really want to learn how to implement the same algorithm in Mathematica. Will someone help me with this?

trials = 10000;
P = 100;
inmyseat = 0;
for i=1:trials
  outcome = 0;
  start = 1;
  while outcome == 0
    x = randi([start,P],1);
    if x == P-1
      outcome = 1;
      inmyseat = inmyseat+1;
    elseif x == P
      outcome = 1;
    end 
    start = x+1;
  end 
end
prob = inmyseat/trials*100;
$\endgroup$
4
  • $\begingroup$ should prob converge to 1/2? $\endgroup$ – kglr Dec 6 '20 at 20:41
  • 1
    $\begingroup$ @kglr Yes. See Taking Seats on a Plane. $\endgroup$ – MarcoB Dec 6 '20 at 20:44
  • 3
    $\begingroup$ " I really want to learn how to write the same on Mathematica...", or you want someone to do your work for you? What have you done to try? $\endgroup$ – ciao Dec 7 '20 at 4:06
  • $\begingroup$ The algorithm the MATLAB code implements does not simulate the passenger problem. It only demonstrates that a random integer, either P-1 or P, has a 50/50 chance of being P-1. Exiting the while outcome == 0 loop has only two possibilities: 1) x == P-1, or 2) x == P. If x is P-1 then inmyseat is counted, and if x is P then inmyseat is unchanged. All other values of x are ignored. The algorithm simply counts the number of P-1 events, and that happens about half the time. $\endgroup$ – creidhne Dec 7 '20 at 12:45
1
$\begingroup$

See a theoretical and intuitive explanations of the 1/2 result in this question on the Math forum: Taking Seats on a Plane

Understand that using procedural loops is not idiomatic in Mathematica so this is unlikely to be the fastest approach, but nevertheless here is the literal translation of your code. I don't know Matlab, but it seemed pretty intuitive and it could be adapted with very minimal changes. I had to choose a value for trials since you did not provide one. I went for 10^6.

P = 100;
inmyseat = 0;

trials = 1000000;

For[i = 1, i <= trials, i++,
  outcome = 0;
  start = 1;
  While[outcome == 0,
    x = RandomInteger[{start, P}];
    Switch[x,
      P - 1, outcome = 1; inmyseat = inmyseat + 1,
      P, outcome = 1
    ];
    start = x + 1;
  ]
]

prob = inmyseat/trials*100 // N

(* Out: 49.9969 *)
$\endgroup$
1
$\begingroup$

Rather than translate the Matlab code, I think this will do it in a more Mathematica way (still using simulation):

ChooseSeat[{taken_, personNumber_}] := Block[{result = taken},
   If[taken[[personNumber]] == 1,
    result[[RandomChoice[Position[taken, 0]]]] = 1;, 
    result[[personNumber]] = 1;];
   {result, personNumber + 1}
   ];
LastSeatEmpty[numberOfSeats_] := 
  With[{lastResult = 
     Nest[ChooseSeat, {ReplacePart[
        ConstantArray[0, numberOfSeats], 
        RandomInteger[{1, numberOfSeats}] -> 1], 2}, 
      numberOfSeats - 2]},
   lastResult[[1, -1]] == 0
   ];

The first function picks a seat. If the seat is taken, they choose randomly from the unoccupied seats. The fate of the last person is in the second function, which randomly seeds the start person and then simulates all others.

Simulating a few times:

Counts[Table[LastSeatEmpty[100], 10000]]

(* <|True -> 4994, False -> 5006|> *)

This is close to the actual probability of 50%.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.