## It *has* to happen!

hippy
Posts: 4031
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

### Re: It *has* to happen!

drgeoff wrote:
Mon Feb 12, 2018 10:49 pm
If you have a 6 sided dice the chance of any two rolls (no matter how many other rolls between them) being the same is 1 in 6. Same probability theory applies to your 2"24 sided dice in the RPi factory.
Good point. A 1 in 6 chance of being the same as previous for dice, a 1 in 16777216 of the Pi's being the same.

And also a 5 in 6 chance of it not being the same, a 16777215 in 16777216 chance of not being the same for a pi. So if P = 16777215/16777216 then having two Pi's the probability of not being the same is P, three Pi's P*P, for four P*P*P etc, P^(N-1)

When the probability of not having two the same is 0.5, the probability of having two the same is also 0.5 ... so we need to find N from P^(N-1) = 0.5

When I brute force try that with a lump of Python code the number of P's needed to get that down to 0.5 the number I come up with is 11 million or so.

The numbers are sound though for a dice with P=5/6, that it determines I'd have to roll four times to get another the same as the first.

If the answer is around 4096, I'm not sure where I'm going wrong, in the theory or my coding.

RaTTuS
Posts: 10123
Joined: Tue Nov 29, 2011 11:12 am
Location: North West UK

### Re: It *has* to happen!

my more math inclined friends say he square approximation comes out as 4096 ... and the more accurate result is 4823 +/- 1 or so

...edit
Just ran the full calculation, I get > 0.5 probability of a collision at 4822. or 4823 as counting from 0 ...
Last edited by RaTTuS on Wed Feb 14, 2018 4:24 pm, edited 1 time in total.
How To ask Questions :- http://www.catb.org/esr/faqs/smart-questions.html
WARNING - some parts of this post may be erroneous YMMV

1QC43qbL5FySu2Pi51vGqKqxy3UiJgukSX
Covfefe

jojopi
Posts: 3043
Joined: Tue Oct 11, 2011 8:38 pm

### Re: It *has* to happen!

hippy wrote:
Wed Feb 14, 2018 2:42 pm
And also a 5 in 6 chance of it not being the same, a 16777215 in 16777216 chance of not being the same for a pi. So if P = 16777215/16777216 then having two Pi's the probability of not being the same is P, three Pi's P*P, for four P*P*P etc, P^(N-1)
With each additional selection there is one fewer choice left that will not collide any previous one. So it is (16777216/16777216) * (16777215/16777216) * (16777214/16777216) * (16777213/16777216) * …

(Fun facts: 4096 gives a no-collision probability around 0.6065, or 1/sqrt(e). 4823 is almost exactly sqrt(16777216 * ln(4)).)

hippy
Posts: 4031
Joined: Fri Sep 09, 2011 10:34 pm
Location: UK

### Re: It *has* to happen!

jojopi wrote:
Wed Feb 14, 2018 4:22 pm
With each additional selection there is one fewer choice left that will not collide any previous one.
Bingo. Many thanks. I now make it 4823 +/-1 also.

1881 is 10% chance of having two the same
2737 is 20%
3108 is 25%
4823 is 50%
6821 is 75%
8790 is 90%
12430 is 99%
15223 is 99.9%
17578 is 99.99%

Return to “Off topic discussion”