Answer: But Who’s Counting?

I’ve done another fantastic job of poorly-defining the problem. I asked for the “best” strategy, which is open to a lot of interpretation. You can play so as the maximize the probability that you get the best possible answer with the digits that come up, or to maximize your expected number at the end of the game, or with some other payoff scheme. I’ll look for an algorithm to maximize your expected number. This means an algorithm such that, if you played the game many times, your average score would be better than any non-equivalent algorithm’s average score with probability that approaches unity as the number of games played approaches infinity. This would roughly correspond to trying to win the game with the greatest possible likelihood, rather than trying to win the grand prize. However, if you were actually playing the game it could in principle be advantageous to tweak the strategy I present below. For example, if the other team adopts the same algorithm, you would always tie. And I hate ties.

Imagine playing the game with two slots and two spins of the wheel. On any given spin, you can get 0 through 9 with equal probability, meaning your expected payoff from a given spin is 4.5. So for this game your strategy is simple. If you get a 0 through 4 on the first roll, you’re likely to do better next time, so drop it in the one’s place. Otherwise, stick it in the tens place.

There are 100 total possible orders of numbers that can come up in this two-turn game. The strategy described above fails only for numbers like 58 and 89 which have the first digit five or greater and the second digit bigger than the first. That’s ten total cases, so in the two-turn game you can play optimally 90% of the time.

The probability distribution for your final outcome is that first digit will be 0 through 4 with probability \frac{1}{20} each, and 5 through 9 with probability \frac{3}{20} each. The expected value of this slot is 5.75. The units place is the same, but the probabilities for those two groups of digits are reversed, and its expected value is 3.25.

Now we understand the game with two plays, we can apply that knowledge to three turns. Suppose you spin the wheel and get a 6. Once you make a decision where to place that 6, you’ll essentially be playing the game with only two slots – a situation we already understand. But since the expected value of the higher slot is 5.75 and 6 is better, we should throw the 6 in the top slot. If you rolled a 4 or 5, it’s between the two expectation values for the slots and should go in the middle. 0 through 3 goes in the one’s place.

Calculating the new expected values for each slot is now more complicated. For the first slot, there’s a \frac{4}{10} chance of filling it with a 6,7,8, or 9 on the first move. If not, it’s the higher slot from a two-slot game. There’s a .6 probability of this happening, and the expected value is 5.75. That makes the expected value for the entire slot .4*7.5 + .6*5.75 = 6.45. For the second slot, a similar calculation yields an expectation value of 4.5 (as it ought to), and for the last slot, 2.55.

For a four-turn game, crank through the same procedure one more time, and again for a five-turn game. You’re aided by a few things. First, there’s a symmetry between high numbers and low numbers, with the axis of symmetry between 4 and 5. That means the expectation value of the middle slot is always 4.5 (if a middle slot exists), and as you go out on either side, complementary slots add to 9.

The expectation values for the slots turn out to be
4-slot game [6.915, 5.285, 3.715, 2.085]
5-slot game [7.2405, 5.8455, 4.5, 3.1545, 1.7595]
You don’t need the last of these to play the game – it just tells you what results you’re likely to get. If you played the game a large number of times employing this algorithm, you would average 78,733.8045 (you would have to play a whole lot of times to get that accurate). I’d pay ten bucks to anyone who wanted to work out what the standard of deviation would be. (combinatorically/analytically, not monte carlo/brute force). I’d pay another ten to see an explicit formula for the case with n slots, rather than the recursive algorithm I’ve got.

So, Nikita’s guess that a 6 should go in the 10,000 spot at any time was a good baseline, but not entirely correct. On the first turn, you should only put a 7, 8, or 9 in the top slot. The second turn is the same as far as that slot goes, but on the third term your standards fall to allow a 6 in there. By the fourth turn, if you still haven’t put something in the first slot you should grab anything 5 or better. If that top slot were still empty on the last turn, you’d just have to take whatever fate handed you.



Tags: , , , ,

Leave a Reply


WordPress.com Logo


Twitter picture


Facebook photo


Google+ photo


Connecting to %s

%d bloggers like this: