2
$\begingroup$

I'm working on a problem, where 4 people enter a room with 100 seats, and each of these four people has their own chair. However, they seat randomly, so with $\mathbb{P}(\mathrm{own \ chair})= \mathbb{P}(\mathrm{chair\ } i ) =\frac{1}{100}$. Now I want to calculate the probability all four people do not sit at their own seats, multiple occupancy being not allowed. In this post, let $A_i$ denote the event that person $i$ is seated in her/his own chair.

I do this as follows: $\mathbb{P}(\mathrm{no \ one \ at \ their \ own \ chair})=\frac{99}{100}\frac{98}{99}\frac{97}{98}\frac{96}{97}=\frac{96}{100}$.

However, as a hint is given, use the inclusion exclusion principle. So using this, I get: $$\mathbb{P}(A_1^C \cap A_2^C \cap A_3^C \cap A_4^C) = \sum_i \mathbb{P}(A_i^C) - \sum_{i<j}\mathbb{P}(A_i^C \cap A_j^C) +\sum_{i<j<k} \mathbb{P}(A_i^C \cap A_j^C \cap A_k^C) - \mathbb{P}(A_1^C \cup A_2^C \cup A_3^C \cup A_4^C)=4\frac{99}{100}-6\frac{99}{100}\frac{98}{99}+4\frac{99}{100}\frac{98}{99}\frac{97}{98}-(1-\frac{1}{100\cdot99\cdot98\cdot97})=\frac{99!/95!+1}{100!/96!}$$

The outcomes are close, but different. I think that what I did with the inclusion-exclusion principle is wrong. Can anyone say what I did wrong, and how I should use the inclusion-exclusion principle to arrive at the right outcome? Thanks in advance.

EDIT: I thought about the problem, and maybe I should use the Inclusion-Exclusion principe for any intersection of events. Because according to my logic, the probability that no one out of 100 people sits at his own spot is $\frac{1}{100}$, which is certainly wrong, if we compare the probability of a K-matching, for example, or maybe more elementary, that the expected number of correctly seated people is 1, which is strange if $\mathbb{P}(\mathrm{at\ least\ one\ correctly\ seated})=\frac{99}{100}$. That this is impossible again needs K-matching implied probabilities.

Working out this edit, I arrive at the following: $$\mathbb{P}(A_1^C \cap A_2^C \cap A_3^C \cap A_4^C) = \sum_i \mathbb{P}(A_i^C) - \sum_{i<j}\mathbb{P}(A_i^C \cap A_j^C) +\sum_{i<j<k} \mathbb{P}(A_i^C \cap A_j^C \cap A_k^C) - \mathbb{P}(A_1^C \cup A_2^C \cup A_3^C \cup A_4^C)$$ Now calculating the terms on the right hand side gives: $$\begin{eqnarray} \sum_i\mathbb{P}(A_i^C) & = & 4\cdot\frac{99}{100}\\ \sum_{i<j}\mathbb{P}(A_i^C\cap A_j^C) & = & 6(\sum_{i=1}^2\mathbb{P}(A_i^C)-\mathbb{P}(A_1^C\cup A_2^C))\\ & = & 6(2\cdot\frac{99}{100}-(1-\frac{1}{99\cdot100}))=6\cdot\frac{9703}{9900}\\ \sum_{i<j<k} \mathbb{P}(A_i^C \cap A_j^C \cap A_k^C) & = & 4\cdot(-3\sum_{i=1}^3\mathbb{P}(A_i^C)+\sum_{i<j}\mathbb{P}(A_i^C\cap A_j^C)+\mathbb{P}(A_1^c\cup A_2^c\cup A_3^C))\\ & = & 4\cdot(-3\cdot\frac{99}{100}+3\cdot\frac{9703}{9900}+(1-\frac{1}{100\cdot99\cdot98}))\\ & \approx & 4\cdot 0.970302\\ \mathbb{P}(A_1^C \cup A_2^C \cup A_3^C \cup A_4^C) & = & 1- \mathbb{P}(A_1 \cap A_2\cap A_3\cap A_4)=1-\frac{1}{100}\cdot\frac{1}{99}\cdot\frac{1}{98}\cdot\frac{1}{97}\\ \mathbb{P}(A_1^C \cap A_2^C \cap A_3^C \cap A_4^C) & = & 4\cdot\frac{99}{100}-6\cdot\frac{9703}{9900}+4\cdot0.970302-(1-\frac{1}{100\cdot99\cdot98\cdot97})\\ & \approx & 0.9606 \end{eqnarray}$$

I think my answer is correct now. Can anyone verify my calculations?

$\endgroup$
  • $\begingroup$ I made an edit, I think I arrive at the correct solution now. Can anyone take a loot at it, from what I did after the 'EDIT', and verify this or tell me what I did wrong? Thanks in advance! $\endgroup$ – Václav Mordvinov Dec 1 '17 at 20:47
  • 1
    $\begingroup$ Your first solution is certainly wrong. Please explain your justification for the factor $\frac{98}{99},$ paying attention to the possibility that the first person may have sat down in the second person's chair. $\endgroup$ – bof Dec 2 '17 at 6:34
  • $\begingroup$ Yes, you're right, that factor cannot be justified. I saw why already after the last edit. $\endgroup$ – Václav Mordvinov Dec 2 '17 at 9:08
1
$\begingroup$

Using the Inclusion-Exclusion Principle as formulated in this answer, let $S(i)$ be the set of arrangements where person $i$ is sitting in their own chair. Then $$ \begin{align} N(j) &=\sum_{|A|=j}\left|\,\bigcap_{i\in A} S(i)\,\right|\\ &=\underbrace{\ \ \ \binom{4}{j}\ \ \ }_{\substack{\text{number of ways to}\\\text{choose the $j$ people}\\\text{sitting in their own seat}}}\underbrace{\binom{100-j}{4-j}(4-j)!}_{\substack{\text{number of ways to}\\\text{seat the remaining}\\\text{$4-j$ people in the}\\\text{remaining $100-j$ seats}}} \end{align} $$ Then the number of ways for no one to sit in their own seat is $$ \begin{align} \sum_{j=0}^4(-1)^{j-0}\binom{j}{0}N(j) &=\sum_{j=0}^4(-1)^j\binom{4}{j}\binom{100-j}{4-j}(4-j)!\\ &=90401673 \end{align} $$ Since the number of ways for them to sit is $\binom{100}{4}4!=94109400$, we get the probability to be $$ \frac{90401673}{94109400}=0.9606 $$ So your computed value looks right.

$\endgroup$
  • $\begingroup$ Many thanks, this is really helpful, also your post you're referring to seems really helpful! $\endgroup$ – Václav Mordvinov Dec 2 '17 at 9:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.