bonanova 84 Posted January 14, 2013 Report Share Posted January 14, 2013 If I repeatedly throw a fair 6-sided die, what is the probability that the running total will at one point equal 137? Quote Link to post Share on other sites

0 Solution Prime 15 Posted January 14, 2013 Solution Report Share Posted January 14, 2013 It seems to stand the reason... Since with each roll we add with equal probability between 1 and 6 to the running sum, the average step is 3.5. Then the probability would be 1/3.5 just like Bushindo calculated. I'll try for exact formula later. 1 Quote Link to post Share on other sites

0 bushindo 14 Posted January 14, 2013 Report Share Posted January 14, 2013 If I repeatedly throw a fair 6-sided die, what is the probability that the running total will at one point equal 137? With some recursive code, I get 0.2857143 1 Quote Link to post Share on other sites

0 CaptainEd 26 Posted January 14, 2013 Report Share Posted January 14, 2013 (edited) 2 / 7 Edited January 14, 2013 by CaptainEd 1 Quote Link to post Share on other sites

0 BobbyGo 7 Posted January 14, 2013 Report Share Posted January 14, 2013 I got an anwer of 0.2536043somethingsomethingmorenumbers Quote Link to post Share on other sites

0 bonanova 84 Posted January 15, 2013 Author Report Share Posted January 15, 2013 Bushindo has seven decimal places; the Captain has it exactly, if surprisingly; and Prime has the insight. A triple tag team solution! Good job all. So who gets the "solved" tag .... ? The nod goes to Prime's explanation. Quote Link to post Share on other sites

0 Prime 15 Posted January 15, 2013 Report Share Posted January 15, 2013 Thanks Bonanova. My explanation does look sound. But now, after I have taken some time to reflect, I must disprove and disown my solution. Sure, the fraction that we found here is good for everyday gambling needs, but it is not the exact probability. I suspect, Bushindo’s method would have produced the exact answer, had it not succumbed to rounding error. Any number may or may not be an intermediate running total in this experiment. But there is one exception - zero! Zero running total will occur with 100% probability right before the very first roll. Consequently, the probabilities for the first six numbers (1, 2, 3, 4, 5, and 6) to become intermediate totals are: P_{1}_{}= 1/6; P_{2}_{}= (1+1/6)/6 = 7/6^{2}; P_{3} = (1+1/6+7/6^{2})/6 = 7^{2}/6^{3}; And in the like manner, P_{4}_{}= 7^{3}/6^{4}; P_{5} = 7^{4}/6^{5}; P_{6} = 7^{5}/6^{6}; Note, all the above probabilities are different from 2/7. First four are smaller, and the last two are higher. From that point on we must change the method for probability calculation. Since a running total n can be obtained by a single roll from 6 preceding totals, P_{n} = (P_{n-1} + P_{n-2} + P_{n-3} + P_{n-4} + P_{n-5} + P_{n-6})/6. Note, for P_{n} = 2/7, the sum of its six predecessors must be equal 12/7. Let’s figure out the exact probability for P_{7 }using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6^{6}, whereas the numerator of the sum becomes: 6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5}. Note, the numerator is modulo 1 with respect to 6. Thus P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{7}. For P_{8} we add up P_{2} through P_{7} and divide it by 6. To bring P_{2} through P_{6} fractions to the common denominator of 6^{7}, we must multiply their numerators by various powers of 6. Whereas the numerator of P_{7} remains modulo 1 with respect to 6 and so will the numerator of P_{8}. Thus by induction we know that the exact fraction for P_{137} has 6^{137 }in its denominator and a very big who knows what in the numerator, which is modulo 1 with respect to 6, however. The numerator of that fraction is not divisible by 2 and its denominator is not divisible by 7. Therefore, it cannot be exactly equal to 2/7. That big fraction cannot be simplified at all - the numerator and denominator have no common factors. Whoever finds the numerator - will have solved the problem. In Excel spreadsheet, the probabilities for intermediate totals oscillated around 2/7, until the application ran out of precision having reached 15 digits past decimal point at the intermediate total of 108. Quote Link to post Share on other sites

0 CaptainEd 26 Posted January 15, 2013 Report Share Posted January 15, 2013 Prime, your "disproof" notwithstanding, we should congratulate you on your insight that has identified the limit towards which any experiment to 137 should tend (IMH and Naive Opinion). I'm interested to understand about Bushindo's recursive code. My contribution was only to respond to Bushindo's numeric result, as it matches the cyclic stream of digits I learned in childhood. Quote Link to post Share on other sites

0 BobbyGo 7 Posted January 15, 2013 Report Share Posted January 15, 2013 Thanks Bonanova. My explanation does look sound. But now, after I have taken some time to reflect, I must disprove and disown my solution. Sure, the fraction that we found here is good for everyday gambling needs, but it is not the exact probability. I suspect, Bushindo’s method would have produced the exact answer, had it not succumbed to rounding error. Any number may or may not be an intermediate running total in this experiment. But there is one exception - zero! Zero running total will occur with 100% probability right before the very first roll. Consequently, the probabilities for the first six numbers (1, 2, 3, 4, 5, and 6) to become intermediate totals are: P_{1}= 1/6; P_{2}_{}= (1+1/6)/6 = 7/6^{2}; P_{3} = (1+1/6+7/6^{2})/6 = 7^{2}/6^{3}; And in the like manner, P_{4}_{}= 7^{3}/6^{4}; P_{5} = 7^{4}/6^{5}; P_{6} = 7^{5}/6^{6}; Note, all the above probabilities are different from 2/7. First four are smaller, and the last two are higher. From that point on we must change the method for probability calculation. Since a running total n can be obtained by a single roll from 6 preceding totals, P_{n} = (P_{n-1} + P_{n-2} + P_{n-3} + P_{n-4} + P_{n-5} + P_{n-6})/6. Note, for P_{n} = 2/7, the sum of its six predecessors must be equal 12/7. Let’s figure out the exact probability for P_{7 }using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6^{6}, whereas the numerator of the sum becomes: 6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5}. Note, the numerator is modulo 1 with respect to 6. Thus P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{7}. For P_{8} we add up P_{2} through P_{7} and divide it by 6. To bring P_{2} through P_{6} fractions to the common denominator of 6^{7}, we must multiply their numerators by various powers of 6. Whereas the numerator of P_{7} remains modulo 1 with respect to 6 and so will the numerator of P_{8}. Thus by induction we know that the exact fraction for P_{137} has 6^{137 }in its denominator and a very big who knows what in the numerator, which is modulo 1 with respect to 6, however. The numerator of that fraction is not divisible by 2 and its denominator is not divisible by 7. Therefore, it cannot be exactly equal to 2/7. That big fraction cannot be simplified at all - the numerator and denominator have no common factors. Whoever finds the numerator - will have solved the problem. In Excel spreadsheet, the probabilities for intermediate totals oscillated around 2/7, until the application ran out of precision having reached 15 digits past decimal point at the intermediate total of 108. I'm glad I wasn't too far off in my thinking. I had a similar approach, but only considered 131 - 136 when trying to calculate the odds for 137. I had wrongly assumed each number 131 - 136 would have an equal likelyhood of being hit irrespective of of the likelyhood of any of the previous numbers. I do have a question about one part of your disproof: Let’s figure out the exact probability for P_{7 }using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6^{6}, whereas the numerator of the sum becomes: 6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5}. Note, the numerator is modulo 1 with respect to 6. Thus P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{7}. If the common denominator for the first six probabilities is 6^{6}, why does the equation for P_{7} have a denominator of 6^{7}? Shouldn't the equation be: P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{6} (Which equals my attempted answer of about .2536043952903521) If this is right, I would assume that the common denominator would cap at 6^{6} as, eventually, all probabilities would be averages of probabilities with a 6^{6} denominator; including P_{137}. Quote Link to post Share on other sites

0 bushindo 14 Posted January 15, 2013 Report Share Posted January 15, 2013 Prime, your "disproof" notwithstanding, we should congratulate you on your insight that has identified the limit towards which any experiment to 137 should tend (IMH and Naive Opinion). I'm interested to understand about Bushindo's recursive code. My contribution was only to respond to Bushindo's numeric result, as it matches the cyclic stream of digits I learned in childhood. Here is the recursive code I used. The logic behind it is already described by Prime's excellent and insightful analysis. Let P(N) be the probability that the total sum would eventually fall on number N. This code sets P(0) = 1, P( N ) = 0 for negative N, and then iterates recursively using a known formula as described in the following code function P( N ) { if( N == 0 ) { return( 1 ) } else if( N < 0 ) { return( 0 ) } else { A = 1/6*( P( N - 1 ) + P( N - 2 ) + P( N - 3 ) + P( N - 4 ) + P( N - 5 ) + P( N - 6 ) ) return( A ) } } Quote Link to post Share on other sites

0 Prime 15 Posted January 15, 2013 Report Share Posted January 15, 2013 (edited) ... I do have a question about one part of your disproof: Let’s figure out the exact probability for P_{7 }using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6^{6}, whereas the numerator of the sum becomes: 6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5}. Note, the numerator is modulo 1 with respect to 6. Thus P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{7}. If the common denominator for the first six probabilities is 6^{6}, why does the equation for P_{7} have a denominator of 6^{7}? Shouldn't the equation be: P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{6} (Which equals my attempted answer of about .2536043952903521) If this is right, I would assume that the common denominator would cap at 6^{6} as, eventually, all probabilities would be averages of probabilities with a 6^{6} denominator; including P_{137}. The disproof stands. In this instance, the sum of the six predecessors of P_{7} is a fraction with 6^{6} in the denominator. (That sum is greater than 1.) To get the probability of P_{7} that sum must be divided by 6 resulting in 6^{7} in the denominator. (I made a shortcut. Instead of dividing individual probability of each predecessor by 6, I added them together, then divided by 6.) I speculated, Bushindo's code could be something similar to the inductive step in my disproof. This problem runs deeper than it appeared at the first glance. However, our tag team solution is practical. It must be exact for any intermediate sum past infinity. And 137, as it turns out, is a hefty step towards the infinity. Edited January 15, 2013 by Prime Quote Link to post Share on other sites

0 BobbyGo 7 Posted January 15, 2013 Report Share Posted January 15, 2013 Let’s figure out the exact probability for P_{7 }using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6^{6}, whereas the numerator of the sum becomes: 6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5}. Note, the numerator is modulo 1 with respect to 6. Thus P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{7}. If the common denominator for the first six probabilities is 6^{6}, why does the equation for P_{7} have a denominator of 6^{7}? Shouldn't the equation be: P_{7} = (6^{5} + 7*6^{4} + 7^{2}*6^{3} + 7^{3}*6^{2} + 7^{4}*6 + 7^{5})/ 6^{6} (Which equals my attempted answer of about .2536043952903521) If this is right, I would assume that the common denominator would cap at 6^{6} as, eventually, all probabilities would be averages of probabilities with a 6^{6} denominator; including P_{137}. The disproof stands. In this instance, the sum of the six predecessors of P_{7} is a fraction with 6^{6} in the denominator. (That sum is greater than 1.) To get the probability of P_{7} that sum must be divided by 6 resulting in 6^{7} in the denominator. (I made a shortcut. Instead of dividing individual probability of each predecessor by 6, I added them together, then divided by 6.) I speculated, Bushindo's code could be something similar to the inductive step in my disproof. This problem runs deeper than it appeared at the first glance. However, our tag team solution is practical. It must be exact for any intermediate sum past infinity. And 137, as it turns out, is a hefty step towards the infinity. I see where I went wrong. Somehow, I thought you were dividing the sum of the numerators by 6 and multiplying the denominator by 6. When I did mine, I worked the numerators first and then divided by the denominator to get a decimal number; opposed to your cleaner method of just multiplying the denominator and leaving it in fractal form. If that makes any sense whatsoever. I'm at work and it's hard to concentrate. (That's my excuse and I'm sticking to it) Quote Link to post Share on other sites

0 bonanova 84 Posted January 16, 2013 Author Report Share Posted January 16, 2013 I see where I went wrong. Somehow, I thought you were dividing the sum of the numerators by 6 and multiplying the denominator by 6. When I did mine, I worked the numerators first and then divided by the denominator to get a decimal number; opposed to your cleaner method of just multiplying the denominator and leaving it in fractal form. If that makes any sense whatsoever. I'm at work and it's hard to concentrate. (That's my excuse and I'm sticking to it) I'll believe your story. But as I recall before retirement, being at work actually incented me to concentrate on something else. Quote Link to post Share on other sites

0 bonanova 84 Posted January 19, 2013 Author Report Share Posted January 19, 2013 Prime, your analysis lays the groundwork for a great trivia question: If I repeatedly roll a fair six-sided die, what number has the greatest probability of occurring in the sequence of running totals? It is a small number, (where the excursions around 2/7 are largest.) Quote Link to post Share on other sites

0 Prime 15 Posted January 19, 2013 Report Share Posted January 19, 2013 (edited) Prime, your analysis lays the groundwork for a great trivia question: If I repeatedly roll a fair six-sided die, what number has the greatest probability of occurring in the sequence of running totals? It is a small number, (where the excursions around 2/7 are largest.) That is a trick question. The correct answer is the running sum of zero has a probability of 1 (or 100%). It happens at the beginning of the experiment, right before the first roll. I guess that’s why Bonanova branded the question as “trivia” rather than math. (I nearly fell into the trap.) The next highest probability is that of the running total 6. It is approximately 0.36. Another math question for computer programmers is lurking in this thread. It has to do with Bushindo’s recursive code: ....... Here is the recursive code I used. The logic behind it is already described by Prime's excellent and insightful analysis. Let P(N) be the probability that the total sum would eventually fall on number N. This code sets P(0) = 1, P( N ) = 0 for negative N, and then iterates recursively using a known formula as described in the following code function P( N ) { if( N == 0 ) { return( 1 ) } else if( N < 0 ) { return( 0 ) } else { A = 1/6*( P( N - 1 ) + P( N - 2 ) + P( N - 3 ) + P( N - 4 ) + P( N - 5 ) + P( N - 6 ) ) return( A ) } } This computer program calculates the exact probability, until it uses up the allotted precision. And it is most economical in terms of code. However, it may not be so as far as execution time is concerned. Most of the running totals are re-calculated multiple times. Function P(n) calls itself 6 times for all n > 0. The math question is: How many times the recursive function P(n) will be called for P(137)? Edited January 19, 2013 by Prime Quote Link to post Share on other sites

0 bonanova 84 Posted January 19, 2013 Author Report Share Posted January 19, 2013 Exponentially large number; hard to imagine P (137) was calculated in our Universe. Some values of N, number of executions of P, and the value of P(N) 0 1 1 1 7 0.1666666667 2 13 0.1944444444 3 25 0.2268518519 4 49 0.2646604938 5 97 0.3087705761 6 193 0.3602323388 <== max 7 385 0.2536043953 8 763 0.2680940167 9 1513 0.2803689454 10 3001 0.289288461 11 5953 0.2933931222 12 11809 0.2908302133 13 23425 0.2792631923 14 46465 0.2835396585 15 92167 0.2861139321 16 182821 0.2870714299 17 362641 0.2867019247 18 719329 0.2855867251 19 1426849 0.2847128105 20 2830273 0.2856210802 2/7 = 0.2857142857142 .... The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^{(N-1)} ^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....} } ^{It gets multiplied by ~ 1 thousand for every increment of 10 in N. } ^{Check the numbers for P(0), P(9), P(19).} For P(137) that's 1 + 6 x 2^{136} ~ 10^{42} executions Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10^{25} years ~ 10^{15} Universe ages. Quote Link to post Share on other sites

0 Prime 15 Posted January 19, 2013 Report Share Posted January 19, 2013 Exponentially large number; hard to imagine P (137) was calculated in our Universe. Some values of N, number of executions of P, and the value of P(N) 0 1 1 1 7 0.1666666667 2 13 0.1944444444 3 25 0.2268518519 4 49 0.2646604938 5 97 0.3087705761 6 193 0.3602323388 <== max 7 385 0.2536043953 8 763 0.2680940167 9 1513 0.2803689454 10 3001 0.289288461 11 5953 0.2933931222 12 11809 0.2908302133 13 23425 0.2792631923 14 46465 0.2835396585 15 92167 0.2861139321 16 182821 0.2870714299 17 362641 0.2867019247 18 719329 0.2855867251 19 1426849 0.2847128105 20 2830273 0.2856210802 2/7 = 0.2857142857142 .... The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^{(N-1)}^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....} }^{It gets multiplied by ~ 1 thousand for every increment of 10 in N. }^{Check the numbers for P(0), P(9), P(19).}For P(137) that's 1 + 6 x 2^{136} ~ 10^{42} executions Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10^{25} years ~ 10^{15} Universe ages. I got a similar order; my table of numbers differs though. At first glance, it may appear the number of executions of P(n) could be represented as a tree, where each branch splits into 6 more branches below. Thus at the bottom level, the number of nodes would be 6^{137}. Add to that all the nodes from the above levels, and you get a very large number. In reality, the number is a lot smaller than that. P(136) is called only once - from P(137). P(135) is called twice: from P(137) and P(136). P(134) is called 4 times: from P(137), P(136), and from the two instances of P(135). And so on. The number of executions for each P(n) is a kind of 6-term Fibonacci sequence (I don’t know if there is an official name for it.) Each next number is obtained by adding up six of its predecessors. The table for n, P(n) and the total number of executions is as following: 137 ...... 1 .................. 1 136 ...... 1 .................. 2 135 ...... 2 .................. 4 134 ...... 4 .................. 8 133 ...... 8 .................. 16 132 .... 16 .................. 32 131 ..... 32 ................. 64 130 ..... 63 ................. 127 129 .... 125 ................ 252 128 .... 248 ................ 500 127 ... 492 ................. 992 126 .... 976 ................. 1968 125 ... 1936 ................. 3904 124 ... 3840 ................. 7744 123 .. 7617 .................. 15361 ............................................................ 1 ...... 1.48159*10^{40 ........ }2.98791*10^{40} I am not including the terminal nodes P(0), P(-1),...,P(-5), where the exponential sequence changes. I think, I can see a closed-expression form for this sequence.Closed-expression form, anyone? Quote Link to post Share on other sites

0 bonanova 84 Posted January 20, 2013 Author Report Share Posted January 20, 2013 Exponentially large number; hard to imagine P (137) was calculated in our Universe. Some values of N, number of executions of P, and the value of P(N) 0 1 1 1 7 0.1666666667 2 13 0.1944444444 3 25 0.2268518519 4 49 0.2646604938 5 97 0.3087705761 6 193 0.3602323388 <== max 7 385 0.2536043953 8 763 0.2680940167 9 1513 0.2803689454 10 3001 0.289288461 11 5953 0.2933931222 12 11809 0.2908302133 13 23425 0.2792631923 14 46465 0.2835396585 15 92167 0.2861139321 16 182821 0.2870714299 17 362641 0.2867019247 18 719329 0.2855867251 19 1426849 0.2847128105 20 2830273 0.2856210802 2/7 = 0.2857142857142 .... The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^{(N-1)}^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....} }^{It gets multiplied by ~ 1 thousand for every increment of 10 in N. }^{Check the numbers for P(0), P(9), P(19).}For P(137) that's 1 + 6 x 2^{136} ~ 10^{42} executions Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10^{25} years ~ 10^{15} Universe ages.I got a similar order; my table of numbers differs though.At first glance, it may appear the number of executions of P(n) could be represented as a tree, where each branch splits into 6 more branches below. Thus at the bottom level, the number of nodes would be 6^{137}. Add to that all the nodes from the above levels, and you get a very large number. In reality, the number is a lot smaller than that. P(136) is called only once - from P(137). P(135) is called twice: from P(137) and P(136). P(134) is called 4 times: from P(137), P(136), and from the two instances of P(135). And so on. The number of executions for each P(n) is a kind of 6-term Fibonacci sequence (I dont know if there is an official name for it.) Each next number is obtained by adding up six of its predecessors. The table for n, P(n) and the total number of executions is as following: 137 ...... 1 .................. 1 136 ...... 1 .................. 2 135 ...... 2 .................. 4 134 ...... 4 .................. 8 133 ...... 8 .................. 16 132 .... 16 .................. 32 131 ..... 32 ................. 64 130 ..... 63 ................. 127 129 .... 125 ................ 252 128 .... 248 ................ 500 127 ... 492 ................. 992 126 .... 976 ................. 1968 125 ... 1936 ................. 3904 124 ... 3840 ................. 7744 123 .. 7617 .................. 15361 ............................................................ 1 ...... 1.48159*10^{40 ........ }2.98791*10^{40} I am not including the terminal nodes P(0), P(-1),...,P(-5), where the exponential sequence changes. I think, I can see a closed-expression form for this sequence.Closed-expression form, anyone? The given closed form shows an understandable accounting of the required executions, as N increases from zero. The execution count includes: 1. One, for the initial execution, which directly returns 1, if N is zero 2. Additional executions, in Sets of six, comprising executions of the entire formula, when N is not zero. 3. The doubling of the number of Sets, as N increments, owing to recalculation of previous results. 4. The total, which is simply 1 plus 6 times the partial sum of the powers of 2. Are you asking for a different closed form; one that gathers multiply-calculated results into 137 groups, then sums those numbers? Perhaps making those tables for a few smaller values of N will suggest the form of that expression.Programming question: could execution time be drastically reduced, by storing previously calculated values of P and calling them from a table if needed again? Quote Link to post Share on other sites

0 Prime 15 Posted January 20, 2013 Report Share Posted January 20, 2013 (edited) Exponentially large number; hard to imagine P (137) was calculated in our Universe. Some values of N, number of executions of P, and the value of P(N) 0 1 1 1 7 0.1666666667 2 13 0.1944444444 3 25 0.2268518519 4 49 0.2646604938 5 97 0.3087705761 6 193 0.3602323388 <== max 7 385 0.2536043953 8 763 0.2680940167 9 1513 0.2803689454 10 3001 0.289288461 11 5953 0.2933931222 12 11809 0.2908302133 13 23425 0.2792631923 14 46465 0.2835396585 15 92167 0.2861139321 16 182821 0.2870714299 17 362641 0.2867019247 18 719329 0.2855867251 19 1426849 0.2847128105 20 2830273 0.2856210802 2/7 = 0.2857142857142 .... The formula is seen to be: executions of P to evaluate P(N) = 1 + 6 x 2^{(N-1)}^{It's like 1 + 6 x {0 1 2 4 8 16 32 64 128 256 512 1024 ....} }^{It gets multiplied by ~ 1 thousand for every increment of 10 in N. }^{Check the numbers for P(0), P(9), P(19).}For P(137) that's 1 + 6 x 2^{136} ~ 10^{42} executions Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10^{25} years ~ 10^{15} Universe ages. The closed form expression 1+6*2^{n-1 }seems close, It does not conform to the data in the table. E.g., for n=8, the table shows 763, whereas 1+6*2^{7}= 769. The consequtive entries run off even further from the formula. Yes, each next total in the table is twice its predecessor, but minus the 7th total back. ... The given closed form shows an understandable accounting of the required executions, as N increases from zero. The execution count includes: 1. One, for the initial execution, which directly returns 1, if N is zero 2. Additional executions, in Sets of six, comprising executions of the entire formula, when N is not zero. 3. The doubling of the number of Sets, as N increments, owing to recalculation of previous results. 4. The total, which is simply 1 plus 6 times the partial sum of the powers of 2. Are you asking for a different closed form; one that gathers multiply-calculated results into 137 groups, then sums those numbers? Perhaps making those tables for a few smaller values of N will suggest the form of that expression.Programming question: could execution time be drastically reduced, by storing previously calculated values of P and calling them from a table if needed again? As for programming: Of course, the execution time could be reduced by storing calculated results in an array and taking them from there when available. Recursive code seems most economical and simple, but it is dangerous. For this problem, I would use non-recursive code. Modifying Bushindo's code to store results in array and do itterations instead of recursion we bring execution down to just 137 itterations: Define Array P[143]; P[-5]=P[-4]=P[-3]=P[-2]=P[-1]=0; P[0]=1; FOR N=1 TO 137 P[N]=(P[N-1]+P[N-2]+P[N-3]+P[N-4]+P[N-5]+P[N-6])/6 PRINT P[N]; (Dont' ask me what language it is in.) Execution time notwithstanding, recursive code gives rise to interesting math questions and Fibonacci like series. Edited January 20, 2013 by Prime Quote Link to post Share on other sites

0 bonanova 84 Posted January 21, 2013 Author Report Share Posted January 21, 2013 The given formula 1 + 6 x 2^{(N-1)} indeed discloses the order of magnitude, a reasonable approximation, and an upper bound. Inspecting its divergence from the actual count [i could not compute recursively past N=30 in reasonable time] disclosed: the correction begins with the result from the seventh-preceding result. It increases from that value going forward, exponentially, and always a factor 6, but I could not find a closed form. So a closed form for the total answer remains to be found. But execution efficiency for table look-up was dramatically better: Whereas recursion prohibited going past N ~ 25 in reasonable time [a dinner break], N= 100,000 with table look-up took only 20 seconds. Convergence to the 2/7 value to 10 decimal places was achieved for N ~ 75. Quote Link to post Share on other sites

## Question

## bonanova 84

If I repeatedly throw a fair 6-sided die, what is the probability that the running total will at one point equal 137?

## Link to post

## Share on other sites

## 19 answers to this question

## Recommended Posts

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.