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:
- 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?
- 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.
Best Answer
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.