4.2: Overcounting
- Page ID
- 130492
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)
( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\id}{\mathrm{id}}\)
\( \newcommand{\Span}{\mathrm{span}}\)
\( \newcommand{\kernel}{\mathrm{null}\,}\)
\( \newcommand{\range}{\mathrm{range}\,}\)
\( \newcommand{\RealPart}{\mathrm{Re}}\)
\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)
\( \newcommand{\Argument}{\mathrm{Arg}}\)
\( \newcommand{\norm}[1]{\| #1 \|}\)
\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)
\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)In this section, we will explore a common fallacy that occurs while counting. Allow us to consider (and critique!) the following solution:
Poker dice is played by simultaneously rolling 5 fair six-sided dice. Find the probability that we obtain one pair.
Note: By one pair, we mean that the dice have denominations \(a, a, b, c, d\) where \(a, b, c\) and \(d\) are all distinct. For instance, the following are examples of one pair: \( (2, 1, 2, 3, 5 ) \) and \( ( 6, 2, 1, 5, 5 ) \). Meanwhile, the outcomes \( (2, 1, 2, 3, 2 ) \) and \( (2, 2, 1, 1, 1) \) do not meet the conditions of being one pair.
Solution
As usual, we apply our counting framework. Let \( A = \{ \text{we obtain one pair} \} \) and let \(S\) be the set of all outcomes where an outcome is an ordered 5-tuple. That is, an outcome looks like \( ( \_\_, \_\_, \_\_, \_\_, \_\_ ) \). Notice there is no reason to believe that a certain ordered 5-tuple is more likely that another ordered 5-tuple and so \(S\) is indeed a simple sample space. Clearly, \( |S| = 6^5 \). All that remains is to compute \( |E| \). To do this, we proceed in steps:
- We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so.
- We now must select a value of \(b\) that is different from \(a\). There are \( \binom{5}{1} \) ways to do so.
- We now must select a value of \(c\) that is different from \(a\) and \(b\). There are \( \binom{4}{1} \) ways to do so.
- We now must select a value of \(d\) that is different from \(a, b\) and \(c\). There are \( \binom{3}{1} \) ways to do so.
- Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1~ 1!} \) ways to do so.
Hence \( |A| = \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} \).
Putting everything together, we obtain
\[ P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \nonumber \]
Does the above solution seem correct? If not, then can you explain what is wrong?
- Answer
-
It turns out the answer above is incorrect! How do we know this? Observe that \[ P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \times \binom{5}{1} \times \binom{4}{1} \times \binom{3}{1} \times \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \approx 2.78 \nonumber \] and so clearly something is wrong since for any event \(A\) of sample space \(S\), we proved that \( P(A) \leq 1 \).
We will now explore what is wrong in our solution and why.
An overcount is when any distinct outcome has been incorrectly counted as multiple distinct outcomes.
The above example and definition raises two questions:
- How can we recognize if an overcount has occurred?
- If an overcount has occurred, then is there anything we can do to fix our answer?
We first answer question 1 by providing a recipe to check for overcounting.
- After writing down the steps for computing the cardinality of some event, go through your steps and fix an actual outcome which we will denote by \(s_1\).
- Now go through the steps again and change your choice on at least one step. Call the resulting outcome \(s_2\).
- If for some change in choice, \(s_1 = s_2 \), then you have overcounted. If for all possible changes in your selection for \(s_2\), \(s_1 \neq s_2 \), then we have not overcounted.
Allow us to apply the recipe to our poker dice question discussed above. We do so by creating a chart:
| Steps | \(s_1\) | \(s_2\) |
|---|---|---|
| 1) We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so. | ||
| 2) We now must select a value of \(b\) that is different from \(a\). There are \( \binom{5}{1} \) ways to do so. | ||
| 3) We now must select a value of \(c\) that is different from \(a\) and \(b\). There are \( \binom{4}{1} \) ways to do so. | ||
| 4) We now must select a value of \(d\) that is different from \(a, b\) and \(c\). There are \( \binom{3}{1} \) ways to do so. | ||
| 5) Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1!~ 1!} \) ways to do so. |
We will now go through our steps and fix an outcome for \(s_1\). Let us suppose we come up with the following choices:
| Steps | \(s_1\) | \(s_2\) |
|---|---|---|
| 1) We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so. | 4, 4 | |
| 2) We now must select a value of \(b\) that is different from \(a\). There are \( \binom{5}{1} \) ways to do so. | 3 | |
| 3) We now must select a value of \(c\) that is different from \(a\) and \(b\). There are \( \binom{4}{1} \) ways to do so. | 1 | |
| 4) We now must select a value of \(d\) that is different from \(a, b\) and \(c\). There are \( \binom{3}{1} \) ways to do so. | 2 | |
| 5) Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1!~ 1!} \) ways to do so. | (4, 2, 1, 4, 3) |
Here, \(s_1 = (4, 2, 1, 4, 3) \). To complete our recipe, we check if there is a way to change our choice on at least one step that will result in generating \(s_1 \) again. If there is a way to do so, then we have overcounted. Let us change our choice on steps 2, 3, and 4.
| Steps | \(s_1\) | \(s_2\) |
|---|---|---|
| 1) We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so. | 4, 4 | 4,4 |
| 2) We now must select a value of \(b\) that is different from \(a\). There are \( \binom{5}{1} \) ways to do so. | 3 | 1 |
| 3) We now must select a value of \(c\) that is different from \(a\) and \(b\). There are \( \binom{4}{1} \) ways to do so. | 1 | 2 |
| 4) We now must select a value of \(d\) that is different from \(a, b\) and \(c\). There are \( \binom{3}{1} \) ways to do so. | 2 | 3 |
| 5) Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1!~ 1!} \) ways to do so. | (4, 2, 1, 4, 3) | (4, 2, 1, 4, 3) |
Here \(s_2 = (4, 2, 1, 4, 3) \). Since \(s_1 = s_2 \), then we have overcounted. This leads to our second question. How do we fix an overcount?
To fix an overcount, you may simply divide by the number of ways you have overcounted.
To use Method 1, we have to understand how did we overcount? Looking back at our steps, we see that the order in which we select \(b, c\) and \(d\) does not matter since their arrangement can yield the same outcome. How many ways can we arrange\(b, c\) and \(d\)? There are 3! ways to do so. Hence, all we have to do is divide \( |A| \) by 3! to obtain the correct answer.
\[ P(A) = \frac{|A|}{|S|} = \frac{ \Bigg[ \binom{6}{1} \binom{5}{1} \binom{4}{1} \binom{3}{1} \frac{5!}{2! ~ 1! ~ 1~ 1!} \Bigg] / 3! }{6^5} \approx 0.4630 \nonumber \]
To fix an overcount, redo the counting process and condense the steps so that the overcount no longer occurs in the first place.
Consider the follow revision in our counting process:
| Old Steps | New Steps |
|---|---|
| 1) We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so. | 1) We first choose a value of \(a\). That is, we must select the denomination to be repeated. There are \( \binom{6}{1} \) ways to do so. |
| 2) We now must select a value of \(b\) that is different from \(a\). There are \( \binom{5}{1} \) ways to do so. | 2) We now select the values of \(b, c\) and \(d\). There are \( \binom{5}{3} \) ways to do so. |
| 3) We now must select a value of \(c\) that is different from \(a\) and \(b\). There are \( \binom{4}{1} \) ways to do so. | |
| 4) We now must select a value of \(d\) that is different from \(a, b\) and \(c\). There are \( \binom{3}{1} \) ways to do so. | |
| 5) Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1!~ 1!} \) ways to do so. | 3) Finally, we must impose an ordering on \(a, a, b, c, d \). There are \( \frac{5!}{2! ~ 1! ~ 1!~ 1!} \) ways to do so. |
\[ P(A) = \frac{|A|}{|S|} = \frac{ \binom{6}{1} \binom{5}{3} \frac{5!}{2! ~ 1! ~ 1!~ 1!} }{6^5} \approx 0.4630 \nonumber \]
Notice how steps 2, 3 and 4 under the old method have now been collapsed into one step in the new method.