18 replies to this topic

[superprismatic]

Spoiler for had thought...

this was an expected value problem with the expected number of rolls needed to get all six numbers equal to the sum of the expected number of rolls needed to get each new number. The average number of rolls to roll a new number being the inverse of the probability to roll a new number. So 14.7?

Please explain further.  I can't parse this in any sensible way.

[phil1882]

Spoiler for

you have a 100% chance of rolling a number 1-6 with 1 dice.

you have 5/6 of a chance of rolling a new number with the next dice.

you have 4/6 of a chance of rolling a new number with the next dice.

and so on.

so the number of dice required is 6/6 +6/5 +6/4 +6/3 +6/2 +6/1 = 14.7

[Prime]

Spoiler for had thought...

this was an expected value problem with the expected number of rolls needed to get all six numbers equal to the sum of the expected number of rolls needed to get each new number. The average number of rolls to roll a new number being the inverse of the probability to roll a new number. So 14.7?

 

 

Yes. Simple concept that cuts thru all the computational complexity.

This concept, does not apply to the question in the OP. The problem called for finding the minimum number of rolls (or dice) to get a winning bet. A winning bet is one, where your probability of winning is better than 0.5. It is not the same concept as average number of rolls (dice) required to get to the objective.

A simple example:

If you roll repeatedly a fair dice, then any given number, say "1", will occur on average once in six rolls. However, if I bet on "1" coming up just after 4 rolls or sooner, I am going to come out ahead. (Same as rolling 4 dice and betting that at least one of them will roll "1".)

P = 1 - (5/6)⁴ = 0.5177

 

The answer to the problem as stated is like Sp and myself have found. I have another equation, which is not recursive, but encompasses all variations. It yields the same result. I'll make a separate post for it.

 

But of course you still get a winning bet with 14.7 rolls. Your winning chance is better than 60%, but it is not the minimum number of rolls.

Edited by Prime, 26 January 2013 - 05:31 AM.

[Prime]

The bottom line, the ultimate truth for calculation of a probability is the number of all variations that meet your criteria divided by the number of all possible variations.

 

Spoiler for TOTAL VARIATIONS

Note, m dice and m consecutive rolls are the same thing for the purposes of this problem.

The number of all possible variations for m dice is 6^m.
The number of variations where all 6 numbers show is more difficult to express. The simplest I came up with is an exponential function with 6 terms. I find it by induction.
Let f(k) be an expression for the number of variations, in which all k different numbers (die faces) are present after rolling m dice. (Exactly k, no more, no less.)
f(1) = 1^m = 1;
f(2) = 2^m - ₂C₁*f(1); (subtracting all variations of less than 2 different numbers.)
f(3) = 3^m- ₃C₂*f(2) - ₃C₁;
..... and so on...
f(6) = 6^m- ₆C₅*f(5) - ₆C₄*f(4) - ₆C₃*f(3) - ₆C₂*f(2) - ₆C₁

After substitution and simplification, we get:
f(6) = 6^m- 6*5^m + 15*4^m - 20*3^m + 15*2^m - 6. (If I did not mess up anywhere.)

Dividing that by 6^m and trying different m-s, I come up with the same results as with the recursive formula from my earlier post.
#rolls   Probability
6 ....... 0.015432
7 ....... 0.054012
8 ....... 0.114026
9 ....... 0.189043
10 ..... 0.271812
11 ..... 0.356206
12 ..... 0.437816
13 ..... 0.513858
14 ..... 0.582845
15 ..... 0.644213
16 ..... 0.698004

It is possible, a simpler and better expression for all k numbers showing in m trials exists in math literature. Alas, I don’t read literature. Though, I’d be interested to know if someone finds something on the subject.

To sum up: Ask for 13 dice and you should have a slight winning chance. For the gamblers who are convinced it is 14.7 rolls, I can give slight handicap and bet on 14.

[bonanova]

Prime, that analysis is convincing. Consider the following as well.

I wonder, in light of your betting on "1" appearing in just four die rolls

means we should be looking at median outcomes rather than average.

 

Spoiler for Translating the OP into math

Since dice rolls are independent, rolling m dice once and one die m times

will give indistinguishable results.

 

OP thus asks:

 

On average, how many rolls of a single die are required to get all six results?

Betting on a smaller number loses, on average; a greater number gives a win.

 

The "waiting time" to expect a particular result [measured in actual time, or (more often) in number of trials]

is simply the reciprocal of the probability of obtaining the result in unit time, or in a single trial.

In the present case the reciprocal probabilities for the 1st, 2nd, 3rd, ..., 6th distinct value to appear are, trivially,

 

6/6, 6/5, 6/4, 6/3, 6/2, and 6/1, which sum to 14.7 trials.

 

The partial sums of this sequence, with obvious interpretations, are:

 

1, 2.2, 3.7, 5.7, 8.7,  14.7.

 

Since simulation is the method de rigueuer, and I avoid complicated formulas when possible, I love simulations,

I simulated a million rolls of 100 dice [to ensure all six face values would be obtained.]

 

I counted into each 100-vector string of values until I encountered

1, then 2, then 3, then 4, then 5, and finally 6 distinct die values.

This models rolling a die multiple times until these result are obtained.

 

I then averaged the counts.

 

Here are the results:

 

1 2.20138 3.70155 5.69817 8.70078 14.70568

 

On the other hand, all six values appear more than half the time in 13 rolls of a die.

[Prime]

You throw m fair six-sided dice and bet that all numbers from 1 to 6 will show at least once.
What is the smallest value of m that gives you a winning bet on average?

That's the OP. A computer, or real life simulation of this simply and economically stated probability problem must be simple and straightforward.

I look at it as a gambling game, where I can bet $1 on the outcome.

 

Spoiler for the game

Roll 13 dice. If they have all 6 numbers -- add one for me, if not -- one for you. Do it 100,000 times and see who wins.

The correct answer to the problem in OP is 13. That's the minimum number of dice that gives better than 1/2 winning chance.

Average number of trials for getting the result R of probability P is 1/P. Probability of getting R after 1/P trials is not equal to 1/2. For a large 1/P that probability tends to 1 - 1/e.

Example: it takes on average 6 rolls of a fair die to roll "1". Probability of rolling "1" in 6 trials (or earlier) is 1 - (5/6)⁶ = 0.6651 (almost 2/3).

Edited by Prime, 26 January 2013 - 10:34 AM.

[bushindo]

Prime, that analysis is convincing. Consider the following as well.
I wonder, in light of your betting on "1" appearing in just four die rolls
means we should be looking at median outcomes rather than average.

Spoiler for Translating the OP into math

Since dice rolls are independent, rolling m dice once and one die m times
will give indistinguishable results.

OP thus asks:

On average, how many rolls of a single die are required to get all six results?
Betting on a smaller number loses, on average; a greater number gives a win.

The "waiting time" to expect a particular result [measured in actual time, or (more often) in number of trials]
is simply the reciprocal of the probability of obtaining the result in unit time, or in a single trial.
In the present case the reciprocal probabilities for the 1st, 2nd, 3rd, ..., 6th distinct value to appear are, trivially,

1, 2.2, 3.7, 5.7, 8.7, 1 2.20138 3.70155 5.69817 8.70078 14.70568

On the other hand, all six values appear more than half the time in 13 rolls of a die.

I agree with the note about median. I think the problem here is that the OP and post 14 (see blue-colored part in spoiler above) are conflating the median and the average (or mean) in the interpretation of the winning condition

Spoiler for

Let's adopt Bonanova's convention and reframe the OP as a problem of rolling a single die N times. Let P( N ) be the probability that all 6 numbers cummulatively show up *on precisely* the N-th roll (i.e., the winning condition is *first* satisfied on the N-th roll). The OP and the post 14 poses actually two different problems

1) OP: What is smallest value of N that gives you a winning bet on average? I think a reasonable interpretation of this is that what is the smallest N such that the cumulative probability of winning is above .5. In mathematical notations, we are looking for the median M, which is defined as the smallest M such that

 

2) Post 14: On average, how many rolls of a single die are required to get all six results?
This definitely asks for the expected value of the number of rolls required to get 6 different numbers. In mathematical notation, we are looking for the average A


The key here is that for this puzzle, the median is roughly 13, while the mean is roughly 14.7.

[Prime]

The statement of the problem is unambiguous. It requires finding the smallest number of dice for the winning bet  on average (not the average).

Bonanova is a Grandmaster of stating problems. If he wanted us to find the average number of rolls before you get all 6 numbers, he would say so (in a better way.)

Spoiler for On the other hand...

Misidentifying Expected Value or average number of trials with probability of 1/2 is a typical error. I have seen it many times, well aware of it, yet once in a while have a lapse of judgment and make the same mistake.

I have followed this forum for years, especially Bonanova’s puzzles, my favorites in part for the witty, elegant, and accurate formulation of problems. In my experience, if you think Bonanova has made a mistake in stating his puzzle, read the conditions again and think it over. Just the other day I used presumption of Bonanova’s infallibility in formulating conditions as a clue to solving his other puzzle: http://brainden.com/...igits/?p=327600
When it comes to solving complex problems, Bonanova, however seldom, still can make a mistake, like the rest of us.

So bring out Champaign. And let us not despoil the celebration of this rare joyous occasion by any unwarranted attempts to obfuscate the clear and precise statement of the problem with any median vs. average, or other irrelevant discussions.

In defense of Bonanova’s wonderful talent and skill in formulating problems, and his right to make a mistake once in a while, and in the interest of the truth in gambling:
THE ANSWER IS 13! (Exclamation sign - not a factorial.)

Edited by Prime, 26 January 2013 - 10:26 PM.

[bonanova]

I brought up the idea of median, since the distribution is skewed and I needed a way for both 13 and 14.7 to have significance. Bushindo stated exactly, and clearly, why it suggested itself. Prime explained well why and how wait times and <p> = .5 are different conditions. I've thought about it for a day now and I haven't decided for sure how a puzzle like this one might be worded in order to require finding a skewed median. but i think it could make an interesting puzzle. For sure, the wording would need to be precise.

For this puzzle, I had in mind the cute 14.7 calculation. But I didn't word the OP to ask for it. I was surprised to confirm by simulation that 13 is the answer, as I worded it. Prime is way too kind to say a mistake on my part is anything close to a noteworthy event. But it is clear that (using his example) since betting on a "1" in four rolls wins, wait time (six rolls) isn't the answer for an even bet.

Well guys, I enjoyed this puzzle too. Thanks for teaching me something.

Footnote: sorry plainglazed, the solution post goes now to SP!