Dice Game

[ChromePony]

This could probably go in the probability forum, but theres way too much philosophy around here and not enough math so lets give it a shot.

A friend of mine posed this to me after he was asked it on a job interview, heres the game, its pretty simple.

You roll a fair 6 sided die and are given an amount of money equal to the number you roll, 1=$1 2=$2...etc. The caveat is that if you wish to reroll you may, but would then be stuck with whatever you get the second time.

The question is, how much would you be willing to pay to play this game? read: what is the EV
(this is what he was asked to figure out on the spot)

A slightly less trival extension, what if you get up to 6 rolls, meaning you can choose to reroll 5 times before you are stuck with the 6th.
(he was given this as 'homework')

Finally and most interestingly, how about generalizing it for n rolls...just for kicks

[durron597]

Clearly if you get a 1-3 you should reroll and if you get a 4-6 you should keep. If the game was played with only one roll the $EV is 3.5. Thus the EV of this game is:

1/6 * (4) + 1/6 * (5) + 1/6 * (6) + 1/2 * (3.5) = $4.25

[ChromePony]

[ QUOTE ]
Clearly if you get a 1-3 you should reroll and if you get a 4-6 you should keep. If the game was played with only one roll the $EV is 3.5. Thus the EV of this game is:

1/6 * (4) + 1/6 * (5) + 1/6 * (6) + 1/2 * (3.5) = $4.25


[/ QUOTE ]

Very nice, but thats the easy part. I'm guessing most people who hang out around here could get that pretty quick, I'm more interested in the n-generalization since I have an answer but its not all that elegant, wondering if someone can come up with a better approach.

[durron597]

Well, I thought about it for awhile. The answer is definitely 5 - 3/(2^n), though I'm having trouble proving it. I'll think about it some more.

[Moozh]

If you had infinite rolls, wouldn't you expect to end up with a 6?

[durron597]

[ QUOTE ]
If you had infinite rolls, wouldn't you expect to end up with a 6?

[/ QUOTE ]

But you don't have infinite rolls. You have a certain number of rolls and then you stop.

Hm. Maybe my optimal strategy is not, in fact, optimal. If you have 20 rolls left and you roll a 5, my strategy says stop. That is clearly wrong, but it's where my answer comes from.

[Jordan Olsommer]

Can the general solution even be expressed mathematically? It seems like it requires a conditional ("if current roll is < EV of replacing, replace. Lather, rinse, repeat."). It could be easily done as a recursive function, though.

FWIW, According to my calculations, for n=20 rolls you should replace anything lower than a six for the first 15 rolls, then take a 5 or 6 for rolls 16-18, then 4, 5, or 6 on roll 19, and of course whatever you can get on roll 20.

[Jordan Olsommer]

I still don't know how to collapse it down to a simple mathematical statement*, but this will do it if you have a python interpreter handy (n = max number of rolls you're allowed)

<font class="small">Code:</font><hr /><pre>
import math

def EV(n):
if n==1:
return 3.5
else:
ev_replace = EV(n-1)
threshold = math.floor(ev_replace)
ev_keep = (21 - (((threshold)*(threshold+1))/2))/6
ev = (threshold / 6)*(ev_replace) + ev_keep
return ev
</pre><hr />

Here are the results for the first 20 values of n:

3.5
4.25
4.66666666667
4.94444444444
5.12962962963
5.27469135802
5.39557613169
5.49631344307
5.58026120256
5.6502176688
5.708514724
5.75709560333
5.79757966944
5.8313163912
5.859430326
5.882858605
5.90238217084
5.91865180903
5.93220984086

and here's what your EV is if you are given 100 rolls

5.99999997385

*edit: Duh. It was staring me right in the face, but it's really ugly, and I don't like being stared at by things that are ugly, so that's probably why I didn't include it before. It's just a recursive function with a couple floors thrown in, same as in the code snippet

F(1) = 3.5
F(n) = ( floor( F(n-1) ) * F(n-1) ) / 6 + ( 21 - ( floor( F(n-1) )* (floor ( F(n-1) + 1)) / 2 ) ) / 6

I'm quite sure I have the wrong number of parens in there, but oh well.

[Jordan Olsommer]

And since the max edit time is up on my last post, and because the recursive function I included at the end looks like a keyboard barf, I made it look perty:

[BruceZ]

[ QUOTE ]
You roll a fair 6 sided die and are given an amount of money equal to the number you roll, 1=$1 2=$2...etc. The caveat is that if you wish to reroll you may, but would then be stuck with whatever you get the second time.

The question is, how much would you be willing to pay to play this game? read: what is the EV

[/ QUOTE ]

The average for 1 die is 3.5, so keep 4,5,6 (avg = 5) and roll 1,2,3 again. The EV is

(1/2)*5 + (1/2)*3.5 = $4.25 for 2 dice.


[ QUOTE ]
A slightly less trival extension, what if you get up to 6 rolls, meaning you can choose to reroll 5 times before you are stuck with the 6th.

[/ QUOTE ]


EV(n) = EV for n rolls.
Work backward from 2 remaining rolls.
Since EV(2) = 4.25, keep 5+ (avg = 5.5) and roll 1,2,3,4:

2 rolls left, keep 5+, EV(3) = (1/3)*5.5 + (2/3)*4.25 = 4 + 2/3

3 rolls left, keep 5+, EV(4) = (1/3)*5.5 + (2/3)*(4 2/3) = 4 + 17/18

4 rolls left, keep 5+, EV(5) = (1/3)*5.5 + (2/3)*(4 + 17/18) = 5 + 7/54

5 rolls left, keep 6, EV(6) = (1/6)*6 + (5/6)*(5 + 7/54) = 5 + 84/325 =~ $5.27 for 6 dice.


[ QUOTE ]
Finally and most interestingly, how about generalizing it for n rolls...just for kicks

[/ QUOTE ]

For n &gt; 6, EV(n) = (1/6)*6 + (5/6)*EV(n-1)

recursion: EV(n) = 1 + (5/6)*EV(n-1)

EV(6) = 5.27
EV(7) = 1 + (5/6)*5.27
EV(8) = 1 + 5/6 + (5/6)^2 * 5.27
EV(9) = 1 + 5/6 + (5/6)^2 + (5/6)^3 * 5.27
...
EV(n) = sum [i = 0 to n-7](5/6)^i + (5/6)^(n-6) * 5.27

from finite sum geometric series:

EV(n) = [1 - (5/6)^(n-6)]/(1 - 5/6) + (5/6)^(n-6) * 5.27

EV(n) = 6 - 6*(5/6)^(n-6) + 5.27 * (5/6)^(n-6)

EV(n) = 6 - 0.73*(5/6)^(n-6), for n &gt; 6 dice.