7.7 Jane Street interview question

[ethanjl]

Seen part of this posted in another thread but mine had it a bit more in depth:

1) What would you pay to play a game where you receive what ever number is on a rolled die in dollars (so if you roll a 6, you receive $6)?
2) What if you can re-roll it if you don't like the number? If you can re-roll twice?
3) Write a program that calculates the expected value of this game with n re-rolls and s sides to the die.
4) Can you make the space with respect to n sub-linear?

I'm a bit curious if there is a closed expression for EV(n,s)... couldn't seem to figure it out on the spot.

 

[chiadam]

Here is a program I just wrote for Matlab to do this. I am JUST getting started Matlab, so I'm sure there are many ways to tighten up my code, but here it is.

clear
rolls = 4; % mutable
sides = 9; % mutable
sideposs = 1:sides;
middle = mean(sideposs);
expe(1) = middle;
for i = 2:rolls
for j = 1:sides
if sideposs(j) > expe(i-1)
flag(j) = 1;
else
flag(j) = 0;
end
end
newroll(i) = mean(flag.*sideposs)*sides/sum(flag);
prob(i) = mean(flag);
expe(i) = expe(i-1)*(1-prob(i))+newroll(i)*prob(i);
end
disp(expe');

 

[Karth]

Sorry for the thread revival -- I'd like to present what I believe is a slightly cleaner solution:

Let T[n, k] denote the maximum expected return possible if we have n rolls remaining after our next roll and we decide to continue rolling if we see a value <= k. Note that 1 <= k <= s.

The following dynamic program does the trick:

T[n, k] = (1 - k / s) * (k + 1 + s) / 2 + k / s * max_{X = 1, 2, ..., s} T[n - 1, X]

The base cases can be filled in easily from part (2) -- too lazy to write these out, but if somebody asks, I can write these down.

To see why this dynamic program holds, note that there are two possibilities: either the die shows <= k or > k. The latter probability is (1 - k / s). If this is the case, then the expected value of the die is (k + 1 + s) / 2. If the die shows <= k, then we must roll again according to our policy -- so we have n - 1 rolls left. We want to maximize our expected value, so we take the maximum over T[n - 1, 0], T[n - 1, 1], ...

We can perform the calculations with O(s) space. Allocate an array with s variables, which represent the values T[1, 0] through T[1, s - 1]. Fill these in with the base case variables. Compute T[2, 0 through s - 1] via the dynamic program and write over the same array with the s variables. Doing this repeatedly yields T[n, 0 through s - 1]. Taking the maximum over this array yields the solution. The total time taken is O(n*s).