[Math] De Montmort’s Matching Problem strategy

combinatoricsderangementsdiscrete mathematicsprobability theory

Context: Introduction to Probability – Hwang and Blitzstein Pg. 24. Example 1.6.4 de Montmort's matching problem.
The problem states: Consider a well shuffled deck of n cards labeled 1 through n. You flip over the cards one by one, saying the numbers 1 through n as you do so. You win the game if, at some point, the number you say aloud is the same as the number on the number on the card being flipped over (for example, if the 7th card in the deck has the label 7). What is the probability of winning?

My Questions:

Part 1: The problem does not state that the player keeps playing the game even after they win the game. The solution uses the inclusion-exclusion principle to calculate the probability of winning. For this, the authors calculate the probability of event $A_i$ that the $i$-th flipped card has the number $i$ on it, then the probability that $A_i \cap A_j$ occur and so on and string them together using inclusion-exclusion. Why is $A_i \cap A_j$ important at all? would not the game end as soon as $A_i$ occurs?

Part 2: Here is my approach to calculate the solution, and I would like to understand what is wrong with it (and in-case nothing is wrong then how to develop it further):
$P(\text{win}) = P(\text{win on 1st card}) + P(\text{win on 2nd card}) + … + P(\text{win on the n-th card}) = \cup_{\forall i} P(A_i | \cap_{\forall j<i} A(j))$

In the above equation I assume that winning on the 1st card is disjoint with winning on the second card and so on.

Best Answer

The probability is simply $1$ - P(no derangements). Your assumption that winning on the first card is disjoint from winning on the second card is correct. However, your method of 'inclusion and exclusion' is false (The idea is correct). We only need to have one match out of all $n$ cards, but it is acceptable to have more than $1$ match .

Your method of counting overcounts since you don't consider the state of cards that don't match. (For example, in your case of P(win on 1), your probability suggests that P(win on 2) also exists. Similarly, in your P(win on 2), P(win on 1) also exists. In other words, your vastly overcounting).

Thus, the correct probability of winning (using PIE) is:

P(win) = P(win on 1st) x P(miss all others)
        +p(win on 2nd) x P(miss all others)
        +p(win on 3rd) x P(miss all others)
        .....
        +p(win on 1 and 2) x P(miss all others)
        + and so forth (selectively pick the numbers and locations of cards we 
                    get and miss)

You'll find that this method will take a long time. There are going to be $2^n - 1$ total places you could place the wins on. It would take even longer to find out the total number you'll need to miss.

It would be best to read about derangements.

Related Question