19 replies to this topic

[Prime]

...

I do have a question about one part of your disproof:

 

 

Spoiler for Question

 

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:
6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.
Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

 

 

If the common denominator for the first six probabilities is 6⁶, why does the equation for P₇ have a denominator of 6⁷?

 

Shouldn't the equation be:

P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁶

(Which equals my attempted answer of about .2536043952903521)

 

If this is right, I would assume that the common denominator would cap at 6⁶ as, eventually, all probabilities would be averages of probabilities with a 6⁶ denominator; including P₁₃₇.

The disproof stands.

Spoiler for Probabilities

In this instance, the sum of the six predecessors of P₇ is a fraction with 6⁶ in the denominator. (That sum is greater than 1.) To get the probability of P₇ that sum must be divided by 6 resulting in 6⁷ 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 by Prime, 15 January 2013 - 06:26 PM.

[BobbyGo]

 

 

Spoiler for Question

 

Let’s figure out the exact probability for P₇ using addition of the fractions, like they taught me at school. The common denominator for the first six probabilities is 6⁶, whereas the numerator of the sum becomes:
6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵. Note, the numerator is modulo 1 with respect to 6.
Thus P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁷.

 

 

If the common denominator for the first six probabilities is 6⁶, why does the equation for P₇ have a denominator of 6⁷?

 

Shouldn't the equation be:

P₇ = (6⁵ + 7*6⁴ + 7²*6³ + 7³*6² + 7⁴*6 + 7⁵)/ 6⁶

(Which equals my attempted answer of about .2536043952903521)

 

If this is right, I would assume that the common denominator would cap at 6⁶ as, eventually, all probabilities would be averages of probabilities with a 6⁶ denominator; including P₁₃₇.

The disproof stands.

Spoiler for Probabilities

In this instance, the sum of the six predecessors of P₇ is a fraction with 6⁶ in the denominator. (That sum is greater than 1.) To get the probability of P₇ that sum must be divided by 6 resulting in 6⁷ 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)

[bonanova]

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.

[bonanova]

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?

 

Spoiler for Since 2/7 holds for large numbers

It is a small number, (where the excursions around 2/7 are largest.)

   

[Prime]

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?

 

Spoiler for Since 2/7 holds for large numbers

It is a small number, (where the excursions around 2/7 are largest.)

   

 

That is a trick question.

Spoiler for two answers

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.

Spoiler for

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 by Prime, 19 January 2013 - 07:35 AM.

[bonanova]

Spoiler for How many times does P(137) execute P?

 
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¹³⁶  ~  10⁴² executions
Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

[Prime]

Spoiler for How many times does P(137) execute P?

 
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¹³⁶  ~  10⁴² executions
Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

I got a similar order; my table of numbers differs though.

Spoiler for Fibonacci?

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¹³⁷. 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⁴⁰

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?

[bonanova]

Spoiler for How many times does P(137) execute P?

 
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¹³⁶  ~  10⁴² executions
Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

I got a similar order; my table of numbers differs though.

Spoiler for Fibonacci?

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¹³⁷. 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⁴⁰

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?

[Prime]

Spoiler for How many times does P(137) execute P?

 
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¹³⁶  ~  10⁴² executions
Assume 1 nanosecond/execution = Gigahertz speed: that's ~ 10²⁵ years ~ 10¹⁵ Universe ages.

The closed form expression 1+6*2^n-1 seems close,

Spoiler for however...

It does not conform to the data in the table. E.g., for n=8, the table shows 763, whereas 1+6*2⁷= 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 by Prime, 20 January 2013 - 04:36 AM.

[bonanova]

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.