A popular question on basic** probability** appearing in **quant job interviews** is the classical **matching problem** described in amusing forms: **hats** in a check-room are mixed and randomly distributed to the guests; a **secretary** has mixed a set of letters and their envelopes. What is the probability that no hat will match the right guest? What is the probability that exactly 3 letters will reach the right destination?

The more classical formulation of the same problem is about seeking for a match among two identical decks of N cards randomly mixed. Being the probability that the card will match (regardless to other possible matchings!), we have

The probability of at least one match is given by

Therefore, in the limit of large N the probability approaches , which is a quite surprisingly result. This result can be used to compute the probability of zero matches which is simply 1 minus the probability of at least one match.

From this simple result the amusing idea to try to compute with a **MonteCarlo**, just as it is usually done for . Here my **Mathematica** code which does the job:

MonteCarloNepero[NN_, L_] := Module[{mean, check, indicatorCount},
indicatorCount = 0;
Do[
check = (# - RandomSample[#]) &@Table[l, {l, 1, L}];
If[FreeQ[check, 0],
indicatorCount = indicatorCount + 1;
];
, {NN}];
mean = indicatorCount/NN;
Return[N[1/mean]];
];

Where NN is the number of MonteCarlo runs and L is the length of the card deck. The convergence in the number of cards is very fast so with L=15 the result is already fair. Far more slow is the convergence in NN… For example we may get

In[2]:= MonteCarloNepero[1000, 15]
Out[2]:= 2.75482
In[3]:= E // N
Out[3]= 2.71828

Not that accurate, but fun.

### Like this:

Like Loading...

*Related*