geno3141: please take a look at this problem and see if you can help:

1 die is tossed 11 times in a row. What is the probability that all 6 faces will turn up at least once?. Thanks a lot for any help.

Guest Feb 29, 2016

#2**0 **

The EXACT probability is: 236,922,840 / 665,127,936 =~ 35.62%.

Your task, you mathematicians, is to find out how these numbers are arrived at!!.

Guest Mar 1, 2016

#5**0 **

I'm pleased to see that my Monte-Carlo simulation result ( http://web2.0calc.com/questions/rolling-a-single-die#r5 ) is very close to the exact value. I have still to figure out the logic behind the exact result though!

.

Alan
Mar 1, 2016

#6**+10 **

Hi Alan and guests

,

I can explain the Monte-Carlo simulation result

The probability of getting at least one of each number is equal to

1-P(not getting one of the numbers)

I am going to try and determine the probability of not getting one of the numbers.

A) Now the prob of not getting any individual number in 11 tosses would be \((\frac{5}{6})^{11}\)

so the prob of not getting a 1 or a 2 or a 3....or a 6 would be

\(6*(\frac{5}{6})^{11}\)

B) Trouble is, there is a lot of double counting here.

For instance, if there were no sixes and no 2s that would be counted twice instead of just once.

There are 6C2 = 15 ways that 2 numbers can be NOT thrown and for each the probability will be \((\frac{4}{6})^{11}\)

The probability that there are two numbers missing is

\(15*(\frac{4}{6})^{11}\)

This probability must be subtracted.

C) Now what about if there are 3 numbers missing Lets say 1,2,and 3 are all not thrown.

Well in A this combination got counted 3 times. 1+2+3 In be it got subtracted 3 times -[12]-[23]-[13]

So now it needs to be added back in again. There are 6C3=20 ways that three numbers can be selected and the probability of getting one combination any of them is (3/6)^6 So the probability of thrre numbers all missing will be

\(20*(\frac{3}{6})^{11}\)

D) Now what if there are 4 numbers missing. Lets say a 1,2,3, and 4 are all not thrown.

In A this combination was added 4 times.

In B it was subtracted 4C2 = 6 times

In C it was added 4C3 = 4 times

so altogether it has been added 4-6+4=2 times so we must subtract it once

There are 6C4 = 15 different combinations of 4 numbers. So we need to subtract

\(15*(\frac{2}{6})^{11}\)

E) What if there are 5 numbers missing Lets say 1,2,3,4,5, are all not thrown.

In A this combination was added 5 times.

In B it was Subtracted 5C2=10 times

In C it was added 5C3 = 10times

In D it was subtracted 5C4=5 times

5-10+10-5=0 So we need to add it 1 time.

There are 6 combinations of 5 numbers so we need to add

\(6*(\frac{1}{6})^{11}\)

So what do we have

\(\mbox{P(not all numbers are thrown)}=6*(\frac{5}{6})^{11} -15*(\frac{4}{6})^{11}+20*(\frac{3}{6})^{11}-15*(\frac{2}{6})^{11}+6*(\frac{1}{6})^{11} \)

= 0.643793581390032

P(all the numbers are thrown at least once) = 1-0.643793581390032 = 0.356206418609968

----------------------------------------------------

Now can someone please fill me in on these Monte Carlo simulations I should i just google it ://

Melody
Mar 1, 2016

#11**+5 **

Can you guys figure out this very simple solution to this problem?

11! * [3+19/80] / 6^11 =0.35620641860996799268404206675812.............etc.!!!!!!!!!!!!!!!.

Guest Mar 1, 2016

#12**+10 **

You asked about the Monte-Carlo simulation method Melody.

Here’s the logic behind my Monte-Carlo simulation of this problem:

- Initialise a tally counter (call it n) to zero. n = 0.
- Generate a set of 11 integers chosen randomly from the integers 1 to 6.
- Check to see if all six occur at least once.
- If they do, increment the tally counter by 1 (n = n+1). If they don’t, don’t increment the counter.
- Perform steps 2 to 4, N times (steps 2 to 4 are known as a trial, so we perform N trials).
- Calculate the fraction n/N. This is the fraction of times that all six digits occurred in randomly generated sets of eleven.

If N is large this fraction approximates the requested probability. Because it is based on the use of a finite number of random numbers the result cannot be taken as exact. Indeed if you plot the ratio n/N as a function of N you will see fluctuations. When N is small these fluctuations are relatively large, but as N gets bigger the fluctuations become relatively smaller (see the figure below for an example set of 100 trials). The accuracy of Monte-Carlo simulations tends to be proportional to the square root of N. For this problem it takes about 100 trials to get one decimal place of accuracy. To get two decimal places (an increase in accuracy of a factor of 10) we need 100 times more trials (i.e. we need 10000 trials), and to get three decimal places of accuracy we need 100 times more again, namely a million trials).

It’s a brute force and ignorance approach, but usually relatively simple to implement. In reality it is used when there is no known analytical method (a common situation in more complicated cases in science and engineering). Here there is an analytical solution, as you have so brilliantly shown, but, for me, the Monte-Carlo approach was quicker and required less brain-ache!!

.

Alan
Mar 2, 2016

#13**0 **

Thanks Alan that makes good sense.

I suppose your just run it with our own software?

Why is it called a Monte Carlo simulation?

Here is a formalization of my answer.

This was presented by a member on another forum.

I also received help with my other answer but I understand it perfectly.

Melody
Mar 2, 2016

#14**+5 **

Melody, the term Monte-Carlo, was invented during WW2 (though the technique itself is much older). Here's an extract from the Wikipedia article:

*A colleague of von Neumann and Ulam, Nicholas Metropolis, suggested using the name Monte Carlo, which refers to the Monte Carlo Casino in Monaco where Ulam's uncle would borrow money from relatives to gamble*

The technique was used at los Alamos by John von Neumann, Stanislaw Ulam and Nicholas Metropolis.

Alan
Mar 2, 2016

#15**+5 **

Your logic is excellent, Melody.

This helps to explain the formula referenced here.

\(\displaystyle \sum \limits_{i=0}^{N-1} *(-1)^i*\binom{N}{i}* (N-i)^k\\ \text {Current problem}\\ \displaystyle \sum \limits_{i=0}^{10} *(-1)^i*\binom{N}{i}* (N-i)^{11} = 129230640 \)

This formula is a modification of the formula to generate Stirling numbers of the second kind.

\(\displaystyle \text{Sterling number -2}^{nd} {~type:~} \dfrac{1}{N!}\sum \limits_{i=0}^{N-1} *(-1)^i*\binom{N}{i}* (N-i)^{k}\)

The modification is to multiply by N!.

Wolfram input

StirlingS2[11, 6] = 179487

Multiplying by 6! Returns value above.

StirlingS2[11, 6]*6! = 129320640

Stirling numbers of the second kind generate solutions to bąll and box distributions where the bąlls are unique and the boxes are identical.

This die rolling problem is equivalent to a bąll (die roll) and box (die face) problem where **both the bąlls and boxes are unique**, requiring an increase in the counts of solutions by a factor of 6!

General form:

\(\dfrac{11!}{(B_1!)*(B_2!)*(B_3!)*(B_4!)*( B_5!)* (B_6!)} = \text{unique distributions}\\ \text{where } {B_1+B_2+B_3+ B_4+ B_5+B_6 =11} \text{ with } {B_i} \ne 0 \)

Expanded this by using a generating function for polynomials

[g^y - 1]^6 (The minus 1 correlates to having no empty box).

The general polynomial expansion is

\(g^{(6y)} - \binom{6}{1}g^{(5y)} + \binom{6}{2}g^{(4y)} - \binom{6}{3}g^{(3y)} + \binom{6}{4}g^{(2y)} - \binom{6}{5}{g(y)} + 1\)

\(\text{Now in terms of }~ y^{11} \text{ for the 11 rolls of the die.}\)

\(\left(\dfrac{6^{11}}{11!}\right) + 6 \left(\dfrac{5^{11}}{11!}\right) + 15 \left(\dfrac{4^{11}}{11!}\right) + 20 \left(\dfrac{3^{11}}{11!}\right) + 15 \left(\dfrac{2^{11}}{11!}\right) +6\left(\dfrac{1^{11}}{11!}\right) \)

\(\text{Factor out the } \left(\dfrac{1}{11!}\right)\\ \left(\dfrac{1}{11!}\right) [(6^{11} - 6(5^{11}) + 15(4^{11}) - 20(3^{11}) + 15(2^{11}) - 6(1^{11})]\\ = \left(\dfrac{1}{11!}\right) \left(129230640\right) \\ \)

Note the similarity to the modification of the sterling number formula, where (6!) is factored out.

\(\dfrac{129230640}{11^6} = 0.0.3562064186099 \\ \text { (Probability of rolling at least one of each number (1-6) for 11 rolls of a fair die)} \)

------------

A Markov matrix may also be used to solve this type of problem.

Nauseated
Mar 2, 2016

#16**+5 **

**Errata:**

Corrected to indicate exponent in term of general expansion

\( - \binom{6}{5}g^{(y)} + 1 \)

Corrected odd term subtraction

\(\left(\dfrac{6^{11}}{11!}\right) - 6 \left(\dfrac{5^{11}}{11!}\right) + 15 \left(\dfrac{4^{11}}{11!}\right) - 20 \left(\dfrac{3^{11}}{11!}\right) + 15 \left(\dfrac{2^{11}}{11!}\right) -6\left(\dfrac{1^{11}}{11!}\right)\)

------------

Wolfram alpha link for

Sum[Binomial[6, i] (-1)^i (6 - i)^11, {i, 0, 10}]

.

Nauseated
Mar 2, 2016

#17**0 **

Thanks very much Alan for the explanation and history of the Monte-Carlo simulation technique.

Thanks also Nauseated for your simplification explanation and for your reference to that older great post. :)

Melody
Mar 6, 2016

#18**0 **

BERTIE (or anyone who *really* understands) Please can you help here:

Different (but realted ) Question:

I have six bottomless jars of lollies. They are Red, Green, blue, yellow, orange and black respecitvely.

I want to randomly choose 2 lollies. How many combintions are in the sameple space and what is the probability that one is red and one is green.

I am told it is appropriate to use the stars and bars method for a question like this

https://www.youtube.com/watch?v=5hF59P8tmQc

so there are (2+6-1)C2 possible combinations. 7C2 = 21

I just want one of those so the probability is 1/21

Now I want to toss 2 identical dice. and I want to know what is the probability of tossing a 2 and a 3

For a question like this it is normal to drawn a 6 by 6 grid. There are 36 possible outcomes but there are 2 ways that I can get a 2 and a 3. So the prob of throwing a 2 and a 3 is 2 /36 = 1/18

NOW why are these questions done differently.

6 colours all equally likely to be chosen I chose 2 of them

6 numbers all equally likely to be chosen I chose (roll) 2 of them.

To me the questions seem Identical but I am assued that they are not.

My question is WHY ARE THEY DIFFERENT ?????

Can anyone to try and explain this to me, I just don't get it.

I'd be very grateful if anyone could get the difference through to me.

Melody
Mar 6, 2016