Thread Rating:

Poll

11 votes (45.83%)
9 votes (37.5%)
5 votes (20.83%)
2 votes (8.33%)
7 votes (29.16%)
3 votes (12.5%)
4 votes (16.66%)
3 votes (12.5%)
9 votes (37.5%)
7 votes (29.16%)

24 members have voted

teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2160
March 4th, 2021 at 2:19:51 PM permalink
Quote: charliepatrick

I haven't checked the answers yet, but this is what it produced.
I: 1 J: 2 Perms: 157366449604 Profit: 1 Win: 2
I: 1 J: 3 Perms: 144520208820 Profit: 1.988888888888889 Win: 2.988888888888889
I: 1 J: 4 Perms: 132601016340 Profit: 2.966666666666667 Win: 3.966666666666667
I: 1 J: 5 Perms: 121550931645 Profit: 3.933333333333333 Win: 4.933333333333334
I: 1 J: 6 Perms: 111315063717 Profit: 4.888888888888889 Win: 5.888888888888889
I: 1 J: 7 Perms: 101841441273 Profit: 5.833333333333333 Win: 6.833333333333333
I: 1 J: 8 Perms: 93080887185 Profit: 6.766666666666667 Win: 7.766666666666667
I: 1 J: 9 Perms: 84986896995 Profit: 7.688888888888889 Win: 8.68888888888889
I: 1 J: 10 Perms: 77515521435 Profit: 8.6 Win: 9.6
I: 1 J: 11 Perms: 70625252863 Profit: 9.5 Win: 10.5
....
I: 88 J: 89 Perms: 165 Profit: -42.5 Win: 88
I: 88 J: 90 Perms: 45 Profit: -42.477777777777774 Win: 88
I: 88 J: 91 Perms: 9 Profit: -42.46666666666667 Win: 88
I: 88 J: 92 Perms: 1 Profit: -42.46666666666667 Win: 88
I: 89 J: 90 Perms: 45 Profit: -43.48888888888889 Win: 89
I: 89 J: 91 Perms: 9 Profit: -43.477777777777774 Win: 89
I: 89 J: 92 Perms: 1 Profit: -43.477777777777774 Win: 89
I: 90 J: 91 Perms: 9 Profit: -44.48888888888889 Win: 90
I: 90 J: 92 Perms: 1 Profit: -44.48888888888889 Win: 90
I: 91 J: 92 Perms: 1 Profit: -45.5 Win: 91
AvWin: 16.22254798150687
   totalprofit=0;
totalperms=0;
for (i=1; i<=91; i++) {
for (j=i+1; j<=92; j++) {
perms=(100-j)*(99-j)*(98-j)*(97-j)*(96-j)*(95-j)*(94-j)*(93-j)/8/7/6/5/4/3/2;
profit=0;
if (i>1) { for (k=1; k<i; k++) {profit+=k-i;};};
if (j>i+1) { for (k=i+1; k<j; k++) {profit+=k-i;};};
if (j<92) { for (k=j+9; k<=100; k++) {profit+=j-i;};};
profit=profit/90;
outline=" ";
outline+="I: "+i+" ";
outline+="J: "+j+" ";
outline+="Perms: "+perms+" ";
outline+="Profit: "+profit+" ";
win=i; if (profit>0) {win=i+profit;};
outline+="Win: "+win+" ";
outline+="<BR>";
document.write(outline);
totalprofit+=win*perms;
totalperms+=perms;
}; };
average=totalprofit/totalperms;
outline+="AvWin: "+average+" ";
outline+="<BR>";
document.write(outline);



Can you double check these lines?


if (i>1) { for (k=1; k<i; k++) {profit+=k-i;};};
if (j>i+1) { for (k=i+1; k<j; k++) {profit+=k-i;};};
if (j<92) { for (k=j+9; k<=100; k++) {profit+=j-i;};};

Thanks!
Poetry website: www.totallydisconnected.com
charliepatrick
charliepatrick
Joined: Jun 17, 2011
  • Threads: 33
  • Posts: 2341
Thanks for this post from:
teliot
March 4th, 2021 at 2:45:24 PM permalink
Quote: teliot

...double check these lines...

I've checked a few examples and they look good.
There are 90 possible values for the redrawn ball (I'm assuming it can't be ones you've already got or the one you discarded).
I: 2 J: 3 Perms: 144520208820 Profit: 0.9777777777777777 Win: 2.977777777777778
If the drawn ball is higher than 3 you win 3; only if the new ball drawn in 1 will you not receive 3. The chances of this are 1 in 90 and it loses you 2. So the average is 3 less 2/90. Check.

I: 40 J: 50 Perms: 536878650 Profit: -3.5 Win: 40 T1: -780 T: 39 T1: -735 T: 48 T1: -315 T: 90
From 1 thru 39 you lose 39 thru 1 = -780 (average of -1 and -39 = -20, number of items = 39, total = -780).
From 41 thru 49 you gain 1 thru 9 = +45 (average of 1 and 9 = 5, number of items = 9, total +45.
The remaining 51 to 100 except for the 8 balls already drawn each gain 10. There are 42 os these so total = +420.
420+45-780 = -315. -315/90 = -3.5. Check.
NB I'm only looking at the second problem you posed where the player has a choice of whether to stand or play.
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2160
Thanks for this post from:
charliepatrick
March 4th, 2021 at 2:54:47 PM permalink
Quote: charliepatrick

There are 90 possible values for the redrawn ball (I'm assuming it can't be ones you've already got or the one you discarded).
I: 2 J: 3 Perms: 144520208820 Profit: 0.9777777777777777 Win: 2.977777777777778
If the drawn ball is higher than 3 you win 3; only if the new ball drawn in 1 will you not receive 3. The chances of this are 1 in 90 and it loses you 2. So the average is 3 less 2/90. Check.

I: 40 J: 50 Perms: 536878650 Profit: -3.5 Win: 40 T1: -780 T: 39 T1: -735 T: 48 T1: -315 T: 90
From 1 thru 39 you lose 39 thru 1 = -780 (average of -1 and -39 = -20, number of items = 39, total = -780).
From 41 thru 49 you gain 1 thru 9 = +45 (average of 1 and 9 = 5, number of items = 9, total +45.
The remaining 51 to 100 except for the 8 balls already drawn each gain 10. There are 42 os these so total = +420.
420+45-780 = -315. -315/90 = -3.5. Check.

OK, I see where we differ and what my problem was.

You are only recording the profit if profit > 0. Essentially, you solved the second problem, optimal play, not the first. I re-wrote your code without the line "if profit > 0" in it and we came up with the same answer.

Oh, I see you added a NB above.

Very nice!!!



#include <stdio.h>

int main() {
int i, j, k;
double totalprofit = 0;
double totalperms = 0;
double profit, perms, win, num;

for (i=1; i<=91; i++) {
for (j=i+1; j<=92; j++) {

perms=(100.0-j)*(99-j)*(98-j)*(97-j)*(96-j)*(95-j)*(94-j)*(93-j)/(2.0*3*4*5*6*7*8);

profit=0;
num = 0;

if (i>1) {
for (k=1; k<i; k++) {
profit+=(k-i);
num++;
}
}

if (j>i+1) {
for (k=i+1; k<j; k++) {
profit+=(k-i);
num++;
}
}

if (j<92) {
for (k=j+9; k<=100; k++) {
profit+=(j-i);
num++;
}
}

profit = profit/num;

win = i+profit;


totalprofit += (win*perms);
totalperms += perms;

}
}

printf("%1.6f\n", totalprofit/totalperms);

return 0;
}

$ ./a.exe
16.068182


Last edited by: teliot on Mar 4, 2021
Poetry website: www.totallydisconnected.com
teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2160
Thanks for this post from:
charliepatrick
March 4th, 2021 at 3:06:27 PM permalink

Optimal strategy -- thanks to charliepatrick for the code.

Minimum pair (i,j) with i < j to draw a second ball to replace i.

1, 2
2, 3
3, 4
4, 5
5, 6
6, 7
7, 8
8, 9
9, 10
10, 11
11, 12
12, 13
13, 15
14, 16
15, 17
16, 18
17, 19
18, 21
19, 22
20, 23
21, 25
22, 26
23, 27
24, 29
25, 30
26, 32
27, 33
28, 35
29, 36
30, 38
31, 40
32, 42
33, 43
34, 45
35, 47
36, 49
37, 52
38, 54
39, 56
40, 59
41, 62
42, 65
43, 69
44, 73
45, 79

Return = 16.222548
Poetry website: www.totallydisconnected.com
CrystalMath
CrystalMath
Joined: May 10, 2011
  • Threads: 8
  • Posts: 1892
Thanks for this post from:
teliot
March 4th, 2021 at 3:30:29 PM permalink
Quote: teliot


Optimal strategy -- thanks to charliepatrick for the code.



Got the same thing in Excel. The key to the problem was calculating the average draw value given the two lowest numbers, a and b:
(b*(b-1)/2-a+b*(100-b-8))/90
I heart Crystal Math.
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4684
March 5th, 2021 at 6:41:09 AM permalink
Quote: teliot

So, here is a slightly harder version --

A a keno blower has 100 balls, each numbered 1 through 100. Ten balls are drawn at random and recorded. After the ten balls are drawn, the lowest number recorded out of the 10 balls is then discarded and another ball is drawn from the blower to replace it. You then win $1 multiplied by the lowest of the ten numbers.

What is the expected win, to the nearest cent?



Suppose the lowest number in the 10 drawn is N.
Let K be the second-lowest number drawn.
The expected value of the lowest number after the draw is (probability that the 11th number < K) x (expected value of the 11th number) + (probability that the 11th number > K) x K.

Of the C(100 - N, 9) sets of 9 numbers > N, the lowest number (i.e. the second-lowest number in the original 10) is:
N + 1, with probability C(99 - N, 8) / C(100 - N, 9)
N + 2, with probability C(98 - N, 8) / C(100 - N, 9)
...
91, with probability C(9, 8) / C(100 - N, 9)
92, with probability C(8, 8) / C(100 - N, 9)

The expected value of the lowest number after the redraw is (K - 1) / 99 x (K + 1) / 2 + (100 - K) / 99 x K
= (K (200 - K) - 1) / 198
where K is the second-lowest number in the original 10

If the original lowest number is 10, the expected value is:
C(89, 8) / C(90, 9) x (11 x 189 - 1) / 198
+ C(88, 8) / C(90, 9) x (12 x 188 - 1) / 198
+ C(87, 8) / C(90, 9) x (13 x 187 - 1) / 198
+ ...
+ C(8, 8) / C(90, 9) x (92 x 8 - 1) / 198

This has to be calculated for each possible lowest number from 1 to 91, then multiply by the probability that it is the original lowest number, and sum the values.

teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2160
March 5th, 2021 at 6:44:02 AM permalink
Quote: ThatDonGuy


Suppose the lowest number in the 10 drawn is N.
Let K be the second-lowest number drawn.
The expected value of the lowest number after the draw is (probability that the 11th number < K) x (expected value of the 11th number) + (probability that the 11th number > K) x K.

Of the C(100 - N, 9) sets of 9 numbers > N, the lowest number (i.e. the second-lowest number in the original 10) is:
N + 1, with probability C(99 - N, 8) / C(100 - N, 9)
N + 2, with probability C(98 - N, 8) / C(100 - N, 9)
...
91, with probability C(9, 8) / C(100 - N, 9)
92, with probability C(8, 8) / C(100 - N, 9)

The expected value of the lowest number after the redraw is (K - 1) / 99 x (K + 1) / 2 + (100 - K) / 99 x K
= (K (200 - K) - 1) / 198
where K is the second-lowest number in the original 10

If the original lowest number is 10, the expected value is:
C(89, 8) / C(90, 9) x (11 x 189 - 1) / 198
+ C(88, 8) / C(90, 9) x (12 x 188 - 1) / 198
+ C(87, 8) / C(90, 9) x (13 x 187 - 1) / 198
+ ...
+ C(8, 8) / C(90, 9) x (92 x 8 - 1) / 198

This has to be calculated for each possible lowest number from 1 to 91, then multiply by the probability that it is the original lowest number, and sum the values.

Yes. If you look at some of the spoilers above, you will see an implementation of a slight simplification of this idea to solve the problem. Even more, the strategy problem has also been solved. Great work by charliepatrick.
Last edited by: teliot on Mar 5, 2021
Poetry website: www.totallydisconnected.com
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4684
March 6th, 2021 at 7:48:16 AM permalink
Here is a math solution (well, sort of) to the "slightly harder" problem with the 100 balls:


First, some explanation of my notation:
C(A,B) is the number of combinations of A things taken B at a time
SUM[B=2..92] {...} is the sum of the value within { } for all B from 2 to 92 inclusive; imagine a capital sigma with "B=2" at the bottom and "92" at the top.

Let A and B be the smallest and second-smallest numbers drawn; note that 1 <= A < B <= 92
There are C(100-B, 8) combinations of the C(100, 10) where this is true
If the 11th number < B, it is the lowest number after A is removed; there are B-2 numbers < B excluding A,
so the expected value of the lowest number in this case is (1 + 2 + ... + (B-1) - A) / (B-2) = ((B-1) B - 2A) / (2 (B-2)).
If the 11th number < B, then B is the lowest number after A is removed.
P(11th number < B) = (B - 2) / 90
P(11th number > B) = (92 - B) / 90
The expected value of the lowest number is
1 / C(100, 10) x SUM[B=2..92] {SUM[A=1..B-1] {C(100-B, 8) x (((B - 2) / 90)((B - 1) B - 2A) / (2 (B - 2)) + B (92 - B) / 90)}}
= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {((B - 1) B - 2A) / 180 + 2B (92 - B) / 180}}
= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {(183 B - B^2 - 2A) / 180}}
= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x (SUM[A=1..B-1] {183 B - B^2} - SUM[A=1..B-1] {2A})}
= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x ((B - 1)(183 B - B^2) - 2 (B - 1) B / 2)}
= SUM[B=2..92] {(183 B^2 - B^3 - 182 B) C(100-B, 8)} / (180 C(100, 10))

Okay, I needed a computer to calculate the sum, but it turns out to be 707 / 44.

teliot
teliot
Joined: Oct 19, 2009
  • Threads: 39
  • Posts: 2160
March 6th, 2021 at 7:54:07 AM permalink
Quote: ThatDonGuy

Here is a math solution (well, sort of) to the "slightly harder" problem with the 100 balls:



First, some explanation of my notation:
C(A,B) is the number of combinations of A things taken B at a time
SUM[B=2..92] {...} is the sum of the value within { } for all B from 2 to 92 inclusive; imagine a capital sigma with "B=2" at the bottom and "92" at the top.

Let A and B be the smallest and second-smallest numbers drawn; note that 1 <= A < B <= 92
There are C(100-B, 8) combinations of the C(100, 10) where this is true
If the 11th number < B, it is the lowest number after A is removed; there are B-2 numbers < B excluding A,
so the expected value of the lowest number in this case is (1 + 2 + ... + (B-1) - A) / (B-2) = ((B-1) B - 2A) / (2 (B-2)).
If the 11th number < B, then B is the lowest number after A is removed.
P(11th number < B) = (B - 2) / 90
P(11th number > B) = (92 - B) / 90
The expected value of the lowest number is
1 / C(100, 10) x SUM[B=2..92] {SUM[A=1..B-1] {C(100-B, 8) x (((B - 2) / 90)((B - 1) B - 2A) / (2 (B - 2)) + B (92 - B) / 90)}}
= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {((B - 1) B - 2A) / 180 + 2B (92 - B) / 180}}
= 1 / C(100, 10) x SUM[B=2..92] {C(100-B, 8) x SUM[A=1..B-1] {(183 B - B^2 - 2A) / 180}}
= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x (SUM[A=1..B-1] {183 B - B^2} - SUM[A=1..B-1] {2A})}
= 1 / (180 C(100, 10)) x SUM[B=2..92] {C(100-B, 8) x ((B - 1)(183 B - B^2) - 2 (B - 1) B / 2)}
= SUM[B=2..92] {(183 B^2 - B^3 - 182 B) C(100-B, 8)} / (180 C(100, 10))

Okay, I needed a computer to calculate the sum, but it turns out to be 707 / 44.

What I love most about this is that you reduced the fraction ... the rest of us just got the decimal expansion. :) Nice!
Poetry website: www.totallydisconnected.com
ThatDonGuy
ThatDonGuy
Joined: Jun 22, 2011
  • Threads: 98
  • Posts: 4684
March 6th, 2021 at 8:09:40 PM permalink
Quote: teliot


Optimal strategy -- thanks to charliepatrick for the code.

Minimum pair (i,j) with i < j to draw a second ball to replace i.

1, 2
2, 3
3, 4
4, 5
5, 6
6, 7
7, 8
8, 9
9, 10
10, 11
11, 12
12, 13
13, 15
14, 16
15, 17
16, 18
17, 19
18, 21
19, 22
20, 23
21, 25
22, 26
23, 27
24, 29
25, 30
26, 32
27, 33
28, 35
29, 36
30, 38
31, 40
32, 42
33, 43
34, 45
35, 47
36, 49
37, 52
38, 54
39, 56
40, 59
41, 62
42, 65
43, 69
44, 73
45, 79

Return = 16.222548



I get 45,293,117,053,521 / 2,791,985,396,200, which is 16.222547981507

The strategy is to draw when A < (183 B - B^2) / 182, where A and B are the smallest and second-smallest numbers.
This is equivalent to B > 183/2 - sqrt(183^2 / 4 - 182 A) for B < 183/2.
It appears to match the above list of pairs.


  • Jump to: