26
Scripting and Reverse Engineering / Re: Anyone who understands probability....
« on: 2011-12-28 12:47:50 »
Hi there,
I don’t know if it is quicker, but there is a more accurate method to solve this (without explanation, jump to the code).
The maximal number of steps to win a game is 19 (nine defeats, ten victories). This results in these possible positive outcomes (x = victory, o=defeat):
x x x x x x x x x x
x x x x x x x x x x o
x x x x x x x x x x o o
x x x x x x x x x x o o o
…
x x x x x x x x x x o o o o o o o o o
Imagine all outcomes in a tree diagram and it is apparent that some leaves don’t count, because a win or lose situation happened before step 19. So it is not possible to use the binomial coefficient of 19 ([x+o]^19) to calculate the number of outcomes. But I found way to calculate the needed coefficients (if no one has ever done it, which I absolutely don’t believe, they should be called wondersquare coefficients ):
1;
previous number multiplied with a fraction of needed number of wins as numerator and 1 as denominator;
previous number multiplied with a fraction of the previous numerator plus 1 and and the previous denominator plus 1;
previous number multiplied with a fraction of the previous numerator plus 1 and and the previous denominator plus 1;
…;
this is done till the fraction is 2. After that it ends.
Now applying all victory outcomes with the coefficients, where the combination with the least steps are combined with the first coefficient and the combination with the most steps are combined with the last coefficient. The results are summed up.
Oh wow, it’s horrible to read. I think the calculation itself is a lot more self explaining.
Let’s apply it for the first round. Victory = 2/3, Defeat 1/3
First round win probability = 0,9352
Forth round. Victory = 1/4, Defeat = 3/4:
Forth round win probability = 0,0089
First round = 0,9352338272
Second round = 0,5
Third round = 0,0647661728
Forth round = 0,0089032793
Overall probability = 0,0002696426
1 in 3709
I don’t know if it is quicker, but there is a more accurate method to solve this (without explanation, jump to the code).
The maximal number of steps to win a game is 19 (nine defeats, ten victories). This results in these possible positive outcomes (x = victory, o=defeat):
x x x x x x x x x x
x x x x x x x x x x o
x x x x x x x x x x o o
x x x x x x x x x x o o o
…
x x x x x x x x x x o o o o o o o o o
Imagine all outcomes in a tree diagram and it is apparent that some leaves don’t count, because a win or lose situation happened before step 19. So it is not possible to use the binomial coefficient of 19 ([x+o]^19) to calculate the number of outcomes. But I found way to calculate the needed coefficients (if no one has ever done it, which I absolutely don’t believe, they should be called wondersquare coefficients ):
1;
previous number multiplied with a fraction of needed number of wins as numerator and 1 as denominator;
previous number multiplied with a fraction of the previous numerator plus 1 and and the previous denominator plus 1;
previous number multiplied with a fraction of the previous numerator plus 1 and and the previous denominator plus 1;
…;
this is done till the fraction is 2. After that it ends.
Now applying all victory outcomes with the coefficients, where the combination with the least steps are combined with the first coefficient and the combination with the most steps are combined with the last coefficient. The results are summed up.
Oh wow, it’s horrible to read. I think the calculation itself is a lot more self explaining.
Let’s apply it for the first round. Victory = 2/3, Defeat 1/3
Code: [Select]
1
1 * 10/1 = 10
10 * 11/2 = 55
55 * 12/3 = 220
…
5005 * 16/7 = 11440
11440 * 17/8 = 24310
24310 * 18/9 = 48620
1 * (2/3)^10 * (1/3)^0 = 0,0173415299
10 * (2/3)^10 * (1/3)^1 = 0,0578050997
55 * (2/3)^10 * (1/3)^2 = 0,1059760162
220 * (2/3)^10 * (1/3)^3 = 0,1413013549
715 * (2/3)^10 * (1/3)^4 = 0,1530764678
2002 * (2/3)^10 * (1/3)^5 = 0,1428713699
5005 * (2/3)^10 * (1/3)^6 = 0,1190594749
11440 * (2/3)^10 * (1/3)^7 = 0,0907119809
24310 * (2/3)^10 * (1/3)^8 = 0,0642543198
48620 * (2/3)^10 * (1/3)^9 = 0,0428362132
0,0173415299 + 0,0578050997 + 0,1059760162 + 0,1413013549 + 0,1530764678 + 0,1428713699 + 0,1190594749 + 0,0907119809 + 0,0642543198 + 0,0428362132
= 0,9352338272
First round win probability = 0,9352
Forth round. Victory = 1/4, Defeat = 3/4:
Code: [Select]
1 * (1/4)^10 * (3/4)^0 = 9,5367431640625E-007
10 * (1/4)^10 * (3/4)^1 = 7,15255737304688E-006
55 * (1/4)^10 * (3/4)^2 = 2,95042991638184E-005
220 * (1/4)^10 * (3/4)^3 = 8,85128974914551E-005
715 * (1/4)^10 * (3/4)^4 = 0,0002157502
2002 * (1/4)^10 * (3/4)^5 = 0,0004530754
5005 * (1/4)^10 * (3/4)^6 = 0,0008495164
11440 * (1/4)^10 * (3/4)^7 = 0,0014563138
24310 * (1/4)^10 * (3/4)^8 = 0,0023210001
48620 * (1/4)^10 * (3/4)^9 = 0,0034815001
= 0,0089032793
Forth round win probability = 0,0089
First round = 0,9352338272
Second round = 0,5
Third round = 0,0647661728
Forth round = 0,0089032793
Overall probability = 0,0002696426
1 in 3709