Lillianna Andersen

Answered

2022-07-10

We throw a die a number of times. We let ${Y}_{k}$ be the number of different faces that came up after $k$ throws. Now we want $P[{Y}_{k}\le 5]$.

According to the answer sheet, we use the principle of inclusion-exclusion here to arrive at the following answer:

$P({Y}_{k}\le 5)={\textstyle (}\genfrac{}{}{0ex}{}{6}{5}{\textstyle )}(\frac{5}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{4}{\textstyle )}(\frac{4}{6}{)}^{k}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{3}{\textstyle )}(\frac{3}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{2}{\textstyle )}(\frac{2}{6}{)}^{k}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{1}{\textstyle )}(\frac{1}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{0}{\textstyle )}(\frac{0}{6}{)}^{k}$ (which I believe to be equal to) $P({Y}_{k}\le 5)=P({Y}_{k}=5)-P({Y}_{k}=4)+P({Y}_{k}=3)-P({Y}_{k}=2)+P({Y}_{k}=1)-P({Y}_{k}=0)$

But I just can't wrap my head around how the principle of inclusion-exclusion was exactly used here. My first thought was that it has something to do with the fact that if we see 5 faces, we've also seen at least 4 faces, etc. so that $[{Y}_{k}\le 4]$ is a subset of $[{Y}_{k}\le 5]$. I've tried to manually calculate (using the principle of inclusion-exclusion) $P({Y}_{k}=1\cup {Y}_{k}=2\cup {Y}_{k}=3\cup {Y}_{k}=4\cup {Y}_{k}=5)$ but I don't arrive at the same answer. So far I haven't come to a good intuitive understanding yet, it would be great if someone could help me grasp this.

According to the answer sheet, we use the principle of inclusion-exclusion here to arrive at the following answer:

$P({Y}_{k}\le 5)={\textstyle (}\genfrac{}{}{0ex}{}{6}{5}{\textstyle )}(\frac{5}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{4}{\textstyle )}(\frac{4}{6}{)}^{k}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{3}{\textstyle )}(\frac{3}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{2}{\textstyle )}(\frac{2}{6}{)}^{k}+{\textstyle (}\genfrac{}{}{0ex}{}{6}{1}{\textstyle )}(\frac{1}{6}{)}^{k}-{\textstyle (}\genfrac{}{}{0ex}{}{6}{0}{\textstyle )}(\frac{0}{6}{)}^{k}$ (which I believe to be equal to) $P({Y}_{k}\le 5)=P({Y}_{k}=5)-P({Y}_{k}=4)+P({Y}_{k}=3)-P({Y}_{k}=2)+P({Y}_{k}=1)-P({Y}_{k}=0)$

But I just can't wrap my head around how the principle of inclusion-exclusion was exactly used here. My first thought was that it has something to do with the fact that if we see 5 faces, we've also seen at least 4 faces, etc. so that $[{Y}_{k}\le 4]$ is a subset of $[{Y}_{k}\le 5]$. I've tried to manually calculate (using the principle of inclusion-exclusion) $P({Y}_{k}=1\cup {Y}_{k}=2\cup {Y}_{k}=3\cup {Y}_{k}=4\cup {Y}_{k}=5)$ but I don't arrive at the same answer. So far I haven't come to a good intuitive understanding yet, it would be great if someone could help me grasp this.

Answer & Explanation

Leslie Rollins

Expert

2022-07-11Added 25 answers

Let ${E}_{i}$ be the event that face number $i$ does not appear, for each $i=1,2,\dots ,6$. Then event $\{{Y}_{k}\le 5\}$ is the same as the event that at least one ${E}_{i}$ occurs, i.e. that at least one face is missing. Therefore, using the principle of inclusion exclusion, and the symmetry of the problem,

$\begin{array}{rl}P({Y}_{k}\le 5)& =P\left(\bigcup _{i=1}^{6}{E}_{i}\right)\\ & =\sum _{r=1}^{6}(-1{)}^{r+1}{\textstyle (}\genfrac{}{}{0ex}{}{6}{r}{\textstyle )}P({E}_{1}\cap {E}_{2}\cap \cdots \cap {E}_{r})\\ & =\sum _{r=1}^{6}(-1{)}^{r+1}{\textstyle (}\genfrac{}{}{0ex}{}{6}{r}{\textstyle )}{\left(\frac{6-r}{6}\right)}^{k}.\end{array}$

This is where the equality you were given comes from.

$\begin{array}{rl}P({Y}_{k}\le 5)& =P\left(\bigcup _{i=1}^{6}{E}_{i}\right)\\ & =\sum _{r=1}^{6}(-1{)}^{r+1}{\textstyle (}\genfrac{}{}{0ex}{}{6}{r}{\textstyle )}P({E}_{1}\cap {E}_{2}\cap \cdots \cap {E}_{r})\\ & =\sum _{r=1}^{6}(-1{)}^{r+1}{\textstyle (}\genfrac{}{}{0ex}{}{6}{r}{\textstyle )}{\left(\frac{6-r}{6}\right)}^{k}.\end{array}$

This is where the equality you were given comes from.

Janessa Olson

Expert

2022-07-12Added 2 answers

No, you are misinterpreting. The equation you have is

$\begin{array}{}\text{(1)}& \mathbb{P}(|F|\le 5)=\sum _{|A|=5}\mathbb{P}(F\subseteq A)-\sum _{|A|=4}\mathbb{P}(F\subseteq A)+\sum _{|A|=3}\mathbb{P}(F\subseteq A)-\sum _{|A|=2}\mathbb{P}(F\subseteq A)+\sum _{|A|=1}\mathbb{P}(F\subseteq A)-\sum _{|A|=0}\mathbb{P}(F\subseteq A)\end{array}$

where $F$ is the set of faces that show up, and $A\subseteq \{1,2,3,4,5,6\}$ is a subset of faces in each sum.

Expanding a little more, we have 6 events "only 1,2,3,4,5 are allowed", "only 1,2,3,4,6 are allowed", ..., "only 2,3,4,5,6 are allowed", or equivalently, the six events are "1 does not show up", "2 does not show up", ..., "6 does not show up". $|F|\le 5$ is the union of these events, and intersecting $k$ of these events is precisely reducing the allowable faces to 6-$k$. So inclusion-exclusion gives

$\mathbb{P}(|F|\le 5)=\sum _{\text{possible}1\text{-intersection}}\mathbb{P}(event)-\sum _{\text{possible}2\text{-intersection}}\mathbb{P}(event)+\dots $

which is equation (1).

$\begin{array}{}\text{(1)}& \mathbb{P}(|F|\le 5)=\sum _{|A|=5}\mathbb{P}(F\subseteq A)-\sum _{|A|=4}\mathbb{P}(F\subseteq A)+\sum _{|A|=3}\mathbb{P}(F\subseteq A)-\sum _{|A|=2}\mathbb{P}(F\subseteq A)+\sum _{|A|=1}\mathbb{P}(F\subseteq A)-\sum _{|A|=0}\mathbb{P}(F\subseteq A)\end{array}$

where $F$ is the set of faces that show up, and $A\subseteq \{1,2,3,4,5,6\}$ is a subset of faces in each sum.

Expanding a little more, we have 6 events "only 1,2,3,4,5 are allowed", "only 1,2,3,4,6 are allowed", ..., "only 2,3,4,5,6 are allowed", or equivalently, the six events are "1 does not show up", "2 does not show up", ..., "6 does not show up". $|F|\le 5$ is the union of these events, and intersecting $k$ of these events is precisely reducing the allowable faces to 6-$k$. So inclusion-exclusion gives

$\mathbb{P}(|F|\le 5)=\sum _{\text{possible}1\text{-intersection}}\mathbb{P}(event)-\sum _{\text{possible}2\text{-intersection}}\mathbb{P}(event)+\dots $

which is equation (1).

Most Popular Questions