# The Grey Labyrinth is a collection of puzzles, riddles, mind games, paradoxes and other intellectually challenging diversions. Related topics: puzzle games, logic puzzles, lateral thinking puzzles, philosophy, mind benders, brain teasers, word problems, conundrums, 3d puzzles, spatial reasoning, intelligence tests, mathematical diversions, paradoxes, physics problems, reasoning, math, science.

Author Message
Chuck
Daedalian Member

 Posted: Sat Sep 01, 2012 4:13 pm    Post subject: 1 If I start with a score of zero and start rolling an ordinary six sided die, adding the rolls to my score until the score is a prime number, what is my expected average score? That is, if I get a 2, 3, or 5 on the first roll then I'm done after one roll. If I roll 6,3,6,2 then my score is 17. After 100 million or so computer simulations the average is hovering around 8½, in the 8.499+ to 8.500+ range. But it can't be exactly 8½, can it?
Zag
Tired of his old title

 Posted: Sat Sep 01, 2012 4:43 pm    Post subject: 2 It definitely is not going to converge on a nice, round number. I suspect that it's just a coincidence that it is converging on something so close to one. The reason it won't is that primes don't make a predictable pattern, so there's no chance of terms that cancel away when you extend an infinite series. I'll bet that in your sample, the highest you've ever reached is in the thousands, but there is always going to be a tiny chance that your game will extend into huge numbers. At that point, prime numbers become wildly unpredictable.
Thok
Oh, foe, the cursed teeth!

 Posted: Sat Sep 01, 2012 4:43 pm    Post subject: 3 It's probably not anything interesting. Out of curiosity, what's the distribution of the stopping prime? This would be a good debug check as well, since there's a small but nontrivial chance of integer overflow issues, depending on how the language you are using handles large numbers.
Chuck
Daedalian Member

 Posted: Sat Sep 01, 2012 5:07 pm    Post subject: 4 I didn't put in a stopping point since the probability of a really high score seemed negligible. Of the 270 million simulations I ran, the highest score was 307. I didn't track the distributions. I probably should have.
Chuck
Daedalian Member

 Posted: Sat Sep 01, 2012 9:15 pm    Post subject: 5 Rolling until I get a square gives an average of about 24.78 and a high of 3136 in 50 million simulations. That's not very interesting.
Elethiomel
Daedalian Member

 Posted: Sat Sep 01, 2012 9:22 pm    Post subject: 6 The medians might be more interesting. At least if you want to turn it into a betting game.
Thok
Oh, foe, the cursed teeth!

 Posted: Sat Sep 01, 2012 10:47 pm    Post subject: 7 It occurs to me that once can do an estimate for what the mean should be. You've got roughly a (5/6)^(n-1)*(1/6) chance of stopping at the nth prime (assuming because of the dice rolls you have a 1/6 chance of hitting a given number: this isn't true but it's not a horrible first estimate), and the nth prime is roughly n/ln(n). Wolfram Alpha claims that sum (5/6)^(n-1)*(n/6ln(n)) converges and estimates it as approximately a bit over 3. If I do the same logic for n^2, Wolfram Alpha suggests the sum is around 66. (Also as long as you do something growing slower than exponential growth, that should converge.)
Chuck
Daedalian Member

 Posted: Sat Sep 01, 2012 11:47 pm    Post subject: 8 I think I have a 2/7 chance of hitting any given number. Simulation confirms this.
Thok
Oh, foe, the cursed teeth!

Posted: Sun Sep 02, 2012 12:01 am    Post subject: 9

 Chuck wrote: I think I have a 2/7 chance of hitting any given number. Simulation confirms this.

I'd believe that.

That doesn't change the statement about convergence, since the series in question are now (5/7)^(n-1)*2n/7ln(n) and (5/7)^(n-1)*(2n^2/7), and the same convergence test still works. For squares that gives the much better estimate of 21, and for primes it gives and estimate of a bit around 3,15 once I fix up my indexing to make sense. I know a bunch of my assumptions are wrong (I'm using a not great estimate of the nth prime, and the chances of hitting are not independent for the smaller numbers, since they are so close together), but these numbers are close.
Chuck
Daedalian Member

 Posted: Sun Sep 02, 2012 12:39 am    Post subject: 10 The median for primes is 5. This isn't surprising since more than half the scores will be 2, 3, or 5. The mode is also 5.
esme
^^^^-- is female! Get the pronouns right

 Posted: Tue Sep 04, 2012 9:18 am    Post subject: 11 1) You should do your simulations with dice with fewer sides. 2) The probability argument will give very good results if you do exact calculations for primes up to, say, 11 and *then* use the probability argument (with 2/7) for the rest. For example, there isn't a probability of 2/7 to hit 2, which shifts the average upwards. 3) How do you know that 24.78 is not interesting?_________________Mundus vult decipi, ergo decipiatur.
Chuck
Daedalian Member

 Posted: Tue Sep 04, 2012 2:22 pm    Post subject: 12 I tried using various sized dice and pairs of dice but none of the results looked any more interesting that 24.78 which I know isn't interesting because I'm not interested in it. I also tried using powers of two instead of primes but the program produced a wide range of averages and eventually hung up because it missed too many low powers of two and it takes a lot of die rolls to reach high ones.
lostdummy
Daedalian Member

Posted: Tue Oct 02, 2012 9:40 am    Post subject: 13

 Chuck wrote: But it can't be exactly 8½, can it?

No, it is not exactly 8.5 - actually, it is 'exactly' 8.49974269792726...

Formula to exactly solve this:
p(0)=1
p(n) = sum (i=1..6) isEnd(n-i)? 0: p(n-i)*1/6
avg = sum (i=1..x) isEnd(i)? p(i)*i : 0

Where:
- 'isEnd' test end condition (isPrime, isSquare...)
- 'x' is how far you want to sum , in theory infinity, in practice 1000 was ok
- '6' is chance with regular die, can change to '20' for 20 sided die
- 'avg' is result: expected average score

Yesterday when I saw this problem I also made simulation, but then I tried to find if I can do exact calculation, and it turns out its doable.

First step was to exactly calculate probability that any number would be hit by rolling dice and adding values (this is independent of primes or squares).
Easiest approach was to say that p(n) 'probability to hit n' is based on previous probabilities: chance to hit number before it, times chance to hit 'n' from that number in one die roll, or:
p(n) = sum (i=1..6) p(n-i)*1/6

Since someone above linked wolfram, I tried this formula, and it works:
f(n)=(f(n-1)+f(n-2)+f(n-3)+f(n-4)+f(n-5)+f(n-6))/6, f(0)=1, f(-1)=0, f(-2)=0, f(-3)=0, f(-4)=0, f(-5)=0, f(-6)=0

I checked with simulation, and numbers match exactly ... when there is no stopping. But when goal is to stop on some condition (prime, square..), it changes a bit, since there is zero chance that you will get to 8 from 5 in one die roll if stop condition was prime. So formula changes to:
p(n) = sum (i=1..6) isPrime(n-i)? 0: p(n-i)*1/6

This give correct probabilities for all numbers. Final step was easy, sum all primes multiplied by chance they will be 'hit':
avg = sum (i=1..x) isPrime(i)? p(i)*i : 0

Above 'x' is how far you want to iterate. For primes, x=700 is good enough for all digits precision in double (~15 digits). Number of iteration (ie how far to sum to achieve 15 digit precision) will change with different isEnd conditions, but in general, for this to converge, endnumbers should not increase by more than 1.4 (7/5) - since probability to hit any number approaches ~2/7, chance to miss all previous numbers is multiples of 5/7. It means squares should be valid end condition, and even any other power like cubes ( n^20 etc) , but for example 2^n is not converging.

I'll try this for squares, since its easy to adapt for different conditions and different dice - and it returns exact result, fast.

*EDIT*
avg= 8.49974269792726 for primes
avg=24.7791748313978 for squares
avg=222.52066078979 for cubes
Chuck
Daedalian Member

 Posted: Wed Oct 03, 2012 5:39 am    Post subject: 14 I didn't really think it would be exactly 8½, but that would have been interesting. It really gets interesting when stopping on a power of 2.
lostdummy
Daedalian Member

 Posted: Wed Oct 03, 2012 9:11 am    Post subject: 15 It is probably hard to find setup that result in integer number, let alone power of 2 integer number ;p Initially what I found interesting in this problem was not result, but how to get to result. Anyway, we can consider as separate problem : " find setup (end condition, die size) that result in integer value, preferably in power of 2" ;p
lostdummy
Daedalian Member

 Posted: Wed Oct 03, 2012 9:36 am    Post subject: 16 And ... I found one ;p If you use 7-sided die, and end condition is that number is divisible by 4, then average expected value is 16. There are few similar solutions with 3-sided and 7-sided dice, and end condition is numbers divisible by 2^n . It is interesting that it only works with those dice size ( if I do not count impossible dice sizes). *EDIT* In fact, I find that any combination of these will result in power of 2 result: - die size of 2^a-1 , a>=2 - end condition of 2^b, b>=1 And it appears on wiki that only real dice with '2^n-1' size are 3-sided and 7-sided. BTW, that same end condition (divisible by X) have many combinations of die and X that result in integer value - its only 2^n results that are rare. I also tried few other types of 'end conditions', but had no luck in even finding integer results. One that come close is "use 8-sided die, and finish when last digit in current sum is 1" - that result in average sum value of 40.0000001... not exactly integer, but close.
 Display posts from previous: All Posts1 Day7 Days2 Weeks1 Month3 Months6 Months1 Year by All usersChuckElethiomelesmelostdummyThokZag Oldest FirstNewest First
 All times are GMT Page 1 of 1

 Jump to: Select a forum Puzzles and Games----------------Grey Labyrinth PuzzlesVisitor Submitted PuzzlesVisitor GamesMafia Games Miscellaneous----------------Off-TopicVisitor Submitted NewsScience, Art, and CulturePoll Tournaments Administration----------------Grey Labyrinth NewsFeature Requests / Site Problems
You cannot post new topics in this forum
You can reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum