Home » Basic probability » Matching
Category Archives: Matching
Card matchings
Given two decks of \(n\) cards what is the probability that at least one of a pair of cards matches ?
Imagine the two decks of cards lined up, consider the event \(A_i\) to be that the \(i\)-th cards in the two decks match.
- Compute \[ \mathbf{P}(\bigcup_{i=1}^n A_i)\].
- (**)compute \[ \lim_{n\rightarrow \infty} ( \mathbf{P}( \bigcup_{i=1}^n A_i )\]
Stuffing Envelopes
You write a stack of thank you cards for people who gave you presents for your birthday. You address all of the envelopes but before you can stuff them you are called away. A friend tying to help you see the stack of cards and stuffs them in the envelops. Unfortunately they did not realize that each card was personalized and just stick them in the envelops randomly. Assuming there were \(n\) cards and \(n\) envelops, let \(X_{n}\) be the number of cards in the correct envelope.
- Find \(\mathbf{E} (X_n)\).
- Show that the variance of \(X_n\) is the same as \(\mathbf{E} (X_n)\).
- Is there any common distribution which has the above statistics ?
- (**) Show that
\[ \lim_{n\rightarrow \infty} \mathbf{P}(X_n =m) = \frac{1}{e\, m!}\]
The matching problem
There are \(n\) letters addressed to \(n\) eople at different addresses. The \(n\) addresses are typed on \(n\) envelopes. A disgruntled secretary shuffles the letters and puts them in the envelopes in random order, one letter per envelope.
- Find the probability that at least one letter is put in a correctly addressed envelope. [Hint: use the inclusion-exclusion formula.]
- What is the probability approximately, for large \(n\) ?
[ For example, the needed inclusion-exclusion formula is given in Problem 12, p. 31 in Pitman]
You will also need to know the number of elements in the set
\[ \{ (i_1,i_2,\cdots, i_k) : 1 \leq i_1 < i_2 < \cdots < i_k\leq n\} \]
which is discussed here.
