Here is a solution to the gambling problem posed in this weeks Riddler by Ollie. The problem can be found here in full:
You and I stumble across a 100-sided die in our local game shop. We know we need to have this die — there is no question about it — but we’re not quite sure what to do with it. So we devise a simple game: We keep rolling our new purchase until one roll shows a number smaller than the one before. Suppose I give you a dollar every time you roll. How much money do you expect to win?
Extra credit: What happens to the amount of money as the number of sides increases?
The key, for me, to this problem was thinking about all the branches that occur after the first roll.
Rolling a 99 on the first roll would mean there are 98 branches below that require further exploration — only rolling another 99 or 100 would end the game.
The branches that come from rolling the highest number in a four sided die case. Determining the average number of points in this case isn’t immediately obvious
However rolling a 1 on the first roll would mean there are 0 branches that require further exploration — no number on the die is smaller than that. Therefore rolling a 1 means you are expected to get 0 more points.
The branches that come from rolling the lowest number in a four sided die case. Determining that your payout is 2 is evident
Extending this thought rolling a 2 would mean that there is one branch that extends the game — rolling a one. Therefore we know the expected reward for rolling a two is the chance that the game extends (1/100) times the sum of one (because you get to roll again) and the average of the expected values of all smaller numbers (just the ev(1), which is 0).
Generalizing this we get:
For a one hundred sided die you can see that the point values you can expect to get after the initial roll increase as the number you roll increases
Using this we would get the expected value for all sides on the die and average them — followed by adding two because we get a point for the first roll and the last roll, regardless of their value.
Again this is easy to generalize for variously sized dice, giving us the equation:
Giving us the answers of payout(100) = 2.73and as s approaches infinity the payout approaches e, Euler’s number
Edit 1/20/17: So I guess this answer is wrong. Since this model proved similar to my testing (done by just playing the game using rand()) I suspect something is up with my interpretation of the games rules
All code written in python 3.5:
import matplotlib.pyplot as plt
#Finding expected payout
results = []
for num_sides in range(10,500):
ev = [0]
for i in range(1,num_sides):
ev.append((len(ev)/num_sides)*(sum(ev)/len(ev)+1))
results.append(2+sum(ev)/len(ev))
#Plotting
plt.plot([range(10,500)],[results],'ro')
plt.title('an impromptu gambling problem')
plt.ylabel('Expected Payout')
plt.xlabel('Number of Sides')
plt.show()
