Trouble with Inclusion-Exclusion (Multiplication Theorem)

71 Views Asked by At

$A_i$ is one event out of $n$.

$$P\left(\bigcap_{i=1}^n A_i\right) = P(A_1)P(A_2|A_1) \dotsb P(A_n|A_1A_2...A_{n-1})$$

I have trouble with this theorem (I am not sure what its name is, so the title might be wrong). It makes sense intuitively if the events are dependent to multiply them this way. But once I try to apply it to a problem I fail miserably.

I can't always calculate the intermediate steps $P(A_1|A_2)$.

An example where I couldn't:

A family has 8 dogs (named from 1 to 8). Each dog has his own sleeping spot named after him (1 to 8). What is the probabilty that no dog sleeps in his own spot this night? Assuming they pick the sleeping spots randomly.

In this case event $A_1$ would be that dog 1 doesn't sleep in his spot.

$P(A_1)$ is clear to me, it must be $\frac 7 8$. Or the permutations where dog 1 is not sleeping in his place $7*7!$ divided by all $8!$. After that I am lost.

1

There are 1 best solutions below

2
On BEST ANSWER

I call that thing the product rule. But I think it is more commonly known as the chain rule.


As for the example, that's not quite the approach you want to take. It is easier compute the complementary probability. Let $\bar A$ be the event that no dog sleeps in his spot. Notice that the complement is $A =\{\text{at least one dog sleeps in his spot}\}$. Let $A_i$ be the event that the dog $i$ sleeps in his spot $i$. Then $$P(\bar A) = 1-P(A) = 1-P(A_1\cup A_2\cup\dotsb\cup A_7\cup A_8)$$ At this step is where you want to use inclusion-exclusion.