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

dist_seat
convergence_seat

Advertisements
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: