Home > programming, research resources > Simulation Solution to the Passenger Seat Assignment Probability Problem

## Simulation Solution to the Passenger Seat Assignment Probability Problem

Today I solved a pretty interesting probability problem, of course, as what hardcore data scientist usually does, using a computer. 🙂

The problem statement embedded in the code below, and the convergence rate as well as the distribution of the simulations are posted at the end.

% Victor Fang, 20140705, www.VictorFang.com
% Simulation Solution to the passenger seat probability problem in Matlab.
% Problem:
% 100 passengers have queued up to board a plane, and are lined up in the
% order of the seats on the plane (n=1..100). However, the first person
% lost his ticket and selects a random seat. The remaining passengers will
% occupy their assigned seat if it is available, or a random seat
% otherwise.
% Question : What is the probability that passenger 100 sits in seat 100?

clear all;
clc

numP = 100;
numItr = 1000;
numMeta = 100;

probList = zeros(1, numMeta);
countList = zeros(1, numMeta*numItr);

%% simulation
pc = 0;
for meta = 1:numMeta
count = 0;

% each simulation, one independent experiment.
for itr = 1:numItr
seat = zeros(1,numP);

% 1st passenger randomly picks a seat
r = randi(numP, 1,1);
seat(r) = 1;

% simulate the rest
for j = 2:numP

% if his seat is empty
if(seat(j) == 0)
seat(j) = j;
else
% if its seat occupied, randomly picks an empty one.
idx = find(seat == 0);
p = randi(length(idx), 1,1);
r = idx(p);
seat(r) = j;
end
end

pc = pc + 1;
if(seat(numP) == numP)
count = count +1;
countList(pc) = 1;
end

end
prob = count/numItr;
probList(meta) = prob;

end
%% analysis
m = mean(probList)
s = std(probList)

figure(1)
hist(probList);
xlim([0,1])
grid on;
title(['Distribution of probability, \mu=', num2str(m) , ...
' ; \sigma=' , num2str(s) , ' ; #sim=', num2str(numItr*numMeta)])

figure(2)
tmp = cumsum(countList)./(1:length(countList));
plot(tmp,'LineWidth',5 )
ylim([0,1])
grid on;
title(['Convergence rate of probability of assigned seat'])
xlabel('# Simulations')
ylabel('Probability')

%% results
% numItr = 1000; numMeta = 100:
% m =0.5010
% s =0.0177