De Montmort's Matching Problem strategy

Question

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.

Answer 1

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.

Answer 2

There are many ways of solving this. I will explain two solution ways. In all, the definition of the event you are interested is crucial. Lets define the event $A$ as the event of any card its position and value.

We are either looking for a direct calculation of $P(A\ge1)$ or of $P(A\ge1)= 1-P(A=0)$.

The direct calculation is as follows:

You have $n$ cards. Using counting, the deck has $n!$ sorting arrangements, but in only $(n-1)!$ of those arrangements one card matches its position with its value. This means that the probability of this happening equals: $\frac{(n-1)!}{n!}= \frac{1}{n}$. We can define that the probability of success of one card equals to $\frac{1}{n}$, therefore the probability of failure (a card not matching its position and value equals) to $1-\frac{1}{n}$. Given that we have a deck of cards, we can have one card matching and it could be any of the n cards in the deck, or it could be two cards matching and any two of the deck...or three and any three of the deck...or $n$ cards. This is nothing more than a binomial distribution as follows: $$P(A\ge1)=\sum_{k=1}^n{\binom{n}{k}(\frac{1}{n})^{k}(1-\frac{1}{n})^{n-k}}$$ The second solution is much easier: As stated before, the probability of a card matching equals $\frac{1}{n}$ and of no matching $1-\frac{1}{n}$. In this case we are searching for the probability of $P(A=0)$, this means that after n-successive draws no card is matching. $$P(A=0)=(\frac{1}{n})^0(1-\frac{1}{n})^n=(1-\frac{1}{n})^n$$ $$P(A\ge1)=1-P(A=0)=1-(1-\frac{1}{n})^n=1-(1+\frac{-1}{n})^n=1-\frac{1}{e}$$ for large n. You can also use inclusion and exclusion principle to solve this, but...this also works and is shorter.

Answer 3

One way of solving above problem: Using Inclusion and Exclusion..

Let Aj(i.e., j is subset of A) be the event, "jth card matches" (jth card in the deck is numbered as j)

P(A1UA2U...AN) probability of at least one card matches

From the naïve def of probability: all permutations are equally likely P(A subset j) = 1/n for all the cards labelled j.

Note: here j is not involved wrt to n.

From Symmetry : P(A1 intersection A2) = (n-2)!/n! = 1/n(n-1)!

By Continuing same way of symmetry: P(A1 intersection A2 intersect AK) = (n-k)!/n!

Let's start applying inclusion & exclusion: Add P(Aj) taking alternate way of subtract n choose 2, sum up n choose 3

start add up fist n (i.e.,) n.1/n - n(n-1)/2! . 1/n(n-1) + n(n-1)(n-2)/3! . 1/n(n-1)(n-2) - ... so on

left with this = 1 - 1/2!+1/3!-1/4!+ ...+(-1)^n 1/n!

Looks ugly but it will remember Taylor series for e to the X. Approximately = 1-1/e

Reference: https://www.youtube.com/watch?v=LZ5Wergp_PA&list=PL2SOU6wwxB0uwwH80KTQ6ht66KWxbzTIo&index=3&pbjreload=101