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