4
$\begingroup$

Here's a question from my probability textbook:

A die is thrown until every face has turned up at least once. Show that on average $14{7\over{10}}$ throws will be required.

The easy way to do this is$$1 + {1\over{5\over6}} + {1\over{4\over6}} + {1\over{3\over6}} + {1\over{2\over6}} + {1\over{1\over6}} = 14 {7\over{10}}.$$However, this is the solution in the back of my book:

If the die be thrown $n$ times the number of ways is $6^n$.

Among which ace will be missing in $5^n$, ace and deuce in $4^n$, and so on. Hence the number of ways in which no face will be missing is$$6^n - 6(5^n) + 15(4^n) - 20(3^n) + 15(2^n) - 6(1^n);$$and the chance of this is$$1 - 6\left({5\over6}\right)^n + 15\left({4\over6}\right)^n - 20\left({3\over6}\right)^n + 15\left({2\over6}\right)^n - 6\left({1\over6}\right)^n;$$or if $f_n$ be the chance of failing in $n$ throws to turn every face$$f_n = 6\left({5\over6}\right)^n - 15\left({4\over6}\right)^n + 20\left({3\over6}\right)^n - 15\left({2\over6}\right)^n + 6\left({1\over6}\right)^n.$$(Note that this reduces to unity if $n = 1, 2, 3, 4, 5$.)

I completely follow the solution up to this point. But it's the next claim that I do not follow at all:

Hence success will be attained on an average in $s$ trials where$$s = 1 + f_1 + f_2 + \ldots$$

Why is this claim true? I don't see it. Any help would be well-appreciated. For the record, if we assume that claim then I can complete the problem:$$s = 1 + f_1 + f_2 + \ldots = 1 + {{6\left({5\over6}\right)}\over{1 - {5\over6}}} - {{15\left({4\over6}\right)}\over{1 - {4\over6}}} + {{20\left({3\over6}\right)}\over{1 - {3\over6}}} - {{15\left({2\over6}\right)}\over{1 - {2\over6}}} + {{6\left({1\over6}\right)}\over{1 - {1\over6}}} = 1 + 30 - 30 + 20 - {{15}\over2} + {6\over5} = 14{7\over{10}},$$as desired.

So really, I have two questions:

  1. Why is the claim that success will be attained on an average in $1 + f_1 + f_2 + \ldots$ trials true (from what follows before in the chronological order of the solution, rather than that the calculation obviously happens to give the desired result)? Can someone walk me step by step with how the book came up with that?
  2. What's the precise relationship between the solution I found (the easy way) and the solution in the back of my book (the hard way)? How are they in essence the same at some level?

Update: The bounty is about to expire, but nobody has given a clear answer to my satisfaction yet. I just want to understand what's going on, but all the comments and answers so far just muddy the waters further by overcomplicating without giving a clear explanation.

$\endgroup$
4
  • 2
    $\begingroup$ For a probability distribution supported on the non-negative integers, we have $E[X]=\sum_n P(X>n)$. $\endgroup$ Commented Oct 5, 2021 at 10:31
  • $\begingroup$ BTW 1: The counting used (" the number of ways in which no face will be missing is") relates to the Stirling numbers of the second kind BTW 2: your approach is by far more elegant and powerful $\endgroup$ Commented Oct 7, 2021 at 14:48
  • $\begingroup$ For information, this is a quite famous problem known as coupon collector's problem. (Wikipedia provides the same solution as yours.) $\endgroup$ Commented Oct 7, 2021 at 15:10
  • $\begingroup$ en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle $\endgroup$ Commented Oct 12, 2021 at 18:37

3 Answers 3

Reset to default
4
$\begingroup$

Your book is just using the well-known formula, sometimes called the layer-cake formula: $$ E[X]=P(X>0)+P(X>1)+P(X>2)+\dots $$ which is valid whenever $X$ is a random nonnegative integer. Their $f_k$ is just $P(X>k)$. In case you are unfamiliar, I gave a proof here.

Your method is completely unrelated to the book's method. Your method is more intuitive, and is less direct.

$\endgroup$
2
  • $\begingroup$ somehow I find the equivalent formula $E[X]=P(X\geq 1)+P(X\geq 2)+\cdots$ more pleasing to the eye. $\endgroup$ Commented Oct 11, 2021 at 23:05
  • $\begingroup$ @Mike Earnest Curious as to your thoughts/feedback on the answer I gave. $\endgroup$ Commented Oct 17, 2021 at 10:58
1
$\begingroup$

I understand the difference in these solutions as follows: Whereas your solution can be understood as adding up the expected number of throws to see a new side of the die until we have seen all sides, the solution in the textbook asks for each throw how likely it is we need to do it. We certainly need to make a first throw to see all sides come up once which explains the $1$. We will then have to make a second throw only if we have not seen all sides yet, so 1 throw with the probability $f_1$, hence we add $1 \cdot f_1$ to our $s$ and so forth..

$\endgroup$
0
$\begingroup$

Here's the explanation I came up with, after thinking about this for a week and not feeling satisfied by the given answers.

We want to show that if on average we attain success in $s$ trials, then$$s = 1 + f_1 + f_2 + f_3 + \ldots,$$where $f_n$ denotes the chance of failing in the first $n$ trials.

Let $g_1$ be the chance of succeeding at the first trial; and after the first has failed, $g_2$ be then the chance of succeeding at the second trial; and after the first and second have both failed, $g_3$ be then the chance of succeeding at the third trial, and so forth. We have$$s = g_1 + 2f_1g_2 + 3f_2g_3 + 4f_3g_4 + \ldots$$However, $g_n = 1 - {{f_n}\over{f_{n-1}}}$ for all $n$, so$$s = 1 + 2f_1 + 3f_2 + 4f_3 + \ldots - (f_1 + 2f_2 + 3f_3 + \ldots) = 1 + f_2 + f_2 + f_3 + \ldots,$$as desired.

$\endgroup$
0

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.