# Nested Summations

• Aug 29th 2009, 12:33 PM
sevenquid
Nested Summations
Dear all,
I have found a formula for the probability of winning a simple card game, however that formula has a summation nesting depth of 7 (i.e. 8 summations in total) and the computation time is astronomical. Consequently it is not possible, as it presently stands, to find a figure for the probability.

Simpler versions of the formula, with smaller nesting depths, take less time to compute (obviously) but the following should give you an idea of how tough this is for my computer:

• Nesting depth 1 (2 summations): 0.33 seconds
• Nesting depth 2 (3 summations): 7.33 seconds
• Nesting depth 3 (4 summations): ~10 minutes
• ...
• Nesting depth 7 (8 summations): ~1000 years?!?

So I seek to reduce this equation to something practical. I expect this will involve DO LOOPS?

See attached for the formula.

Hope you can help!

Many thanks Mick
• Aug 29th 2009, 10:45 PM
CaptainBlack
Quote:

Originally Posted by sevenquid
Dear all,
I have found a formula for the probability of winning a simple card game, however that formula has a summation nesting depth of 7 (i.e. 8 summations in total) and the computation time is astronomical. Consequently it is not possible, as it presently stands, to find a figure for the probability.

Simpler versions of the formula, with smaller nesting depths, take less time to compute (obviously) but the following should give you an idea of how tough this is for my computer:

• Nesting depth 1 (2 summations): 0.33 seconds
• Nesting depth 2 (3 summations): 7.33 seconds
• Nesting depth 3 (4 summations): ~10 minutes
• ...
• Nesting depth 7 (8 summations): ~1000 years?!?

So I seek to reduce this equation to something practical. I expect this will involve DO LOOPS?

See attached for the formula.

Hope you can help!

Many thanks Mick

I think you had better tell us what it is the calculation is supposed to represent.

CB
• Aug 29th 2009, 11:35 PM
sevenquid
See here: Card Maths Investigation

The formula is for the probability of winning the "Single Suit" version of this game with 8 card guesses. By winning I mean getting all 8 guesses correct. The answer should be around 0.08 or 0.10 at an estimate.
• Sep 1st 2009, 10:59 AM
sevenquid
Update: I reorganised the summations as 8 nested do loops (see attached) which brought the computation time down to a manageable duration, presumably due to much less RAM use. However the result suggests the formula is wrong anyway. Time for a rethink.

Many thanks
• Sep 1st 2009, 12:30 PM
CaptainBlack
Quote:

Originally Posted by sevenquid
Update: I reorganised the summations as 8 nested do loops (see attached) which brought the computation time down to a manageable duration, presumably due to much less RAM use. However the result suggests the formula is wrong anyway. Time for a rethink.

Many thanks

Well simulation says that with optimum play the probability of gettin 8 guesses right is ~=0.099 +/- 0.001 (1 standard error)

CB
• Sep 1st 2009, 01:51 PM
sevenquid
Simulation? What software are you using CaptainBlack?
• Sep 1st 2009, 08:30 PM
CaptainBlack
Quote:

Originally Posted by sevenquid
Simulation? What software are you using CaptainBlack?

Euler, but it can be done just as easily in Matlab or its free clones.

CB
• Sep 2nd 2009, 01:12 AM
sevenquid
wicked. i'll try get hold of matlab. so how do you program it in - can you effectively input the rules of a game into the program and get it to output a probability of winning? i'm a bit new to this stuff you see...
• Sep 2nd 2009, 01:43 AM
CaptainBlack
Quote:

Originally Posted by sevenquid
wicked. i'll try get hold of matlab. so how do you program it in - can you effectively input the rules of a game into the program and get it to output a probability of winning? i'm a bit new to this stuff you see...

You will be effectivly programming it from scratch, the utilities that are provided are random number generators and random permutation generators. From there on you are on your own.

CB