"Here is the wisdom. Let him that hath understanding count the number of the wild beast: for it is the number of a game; and its number is three-score and six."Suppose you're in a casino playing roulette, and that you can only bet on Black or Red. The roulette wheel has 18 red numbers, 18 black ones, and a green zero. If you bet on a color and a number of that color comes up, you win the size of your bet, but if another number comes up, you lose your bet. You can't bet on zero, so whenever the zero comes up, the casino wins everything.
Now into the casino walks the devil himself and gives you an offer. If you lend him your soul, you may ask for the exact number of red numbers, black numbers, and zeros in the next $N$ rounds, for any one number $N$. The devil will then look into the future and tell you the answer.
But there's a catch (what did you expect, bargaining with the devil?). Once you know those three numbers, it will turn out that whatever you do in the following $N$ rounds, the roulette ball will bounce in a way that gives you maximal bad luck.
Suppose for instance that you ask for seven rounds and the devil tells you there will be three red numbers, three black, and one zero. If you wait for the last of those seven rounds, hoping to then double your stack when you know the outcome, then that's going to be when the zero comes up. But if you start betting on one color, then sure enough the other color will come up (and the zero will still be left).
Notice though that "bad luck" doesn't necessarily mean you lose in the current round. It means that the outcome will be what's worst for you overall. If you bet 10 out of 100 chips on black when there's a black number and a zero left, you will win (because otherwise you would double your stack in the last round).
Notice though that "bad luck" doesn't necessarily mean you lose in the current round. It means that the outcome will be what's worst for you overall. If you bet 10 out of 100 chips on black when there's a black number and a zero left, you will win (because otherwise you would double your stack in the last round).
Let's decide what the rules are and what we're trying to optimize. We start the game with a bankroll that we can think of as a large stack of chips, say a million. We assume that at any time we can bet any fraction of what we have, like one third of our stack, even though a million isn't divisible by 3. We can't buy more chips during the game, so the amount we have at each round is a limit on how much we can bet. We're trying to finish with as much as possible after the $N$ rounds, and the payoff of the game is our final bankroll measured in units of the initial stack.
We can choose the number $N$ as we please, and the number of red, black, and zeros in the next $N$ rounds will be determined by the randomness of the roulette wheel with no supernatural intervention by the devil. If there are $N$ zeros, we can't win anything (so the payoff is 1 as we never make a bet), and if there are $N$ red or $N$ black numbers, we can double our stack $N$ times ending up on $2^N$, so it's not that interesting to ask about best- or worst-case scenarios for this stage.
Next, knowing $N$ and the number of red, black, and zeros, we are assuming a worst-case (also known as adversarial) scenario. We can imagine that the croupier gives the devil a set of $N$ cards of the colors red, black and green with the given distribution, and that we play against the devil. In each of $N$ rounds we make a bet, after which the devil plays one of the cards to decide the outcome. That card is then removed, and we play until the cards are exhausted. This stage of the game involves no probability. It's a two-person game of perfect information like chess.
How to bet
A first observation is that unless there are only zeros, we can always win something. Suppose for instance that $N=6$ and that there are five zeros and one red. That's a pretty bad outcome, but still, if we have a stack of 63 chips, we can make that 64 by the double-until-you-win strategy: First we bet 1 chip on Red. If we win we're done and there are only zeros left, so suppose we lose. The devil has now spent one of the zeros, and in the next round we bet 2 on Red. Again if we win we're done, so assume we lose. Then we bet 4 in the next round and so on. In the penultimate round we have 48 chips and bet 16. If we lose again, the devil has spent the last zero and we must win in the last round.
Here's a challenge that you might want to try before reading on: Suppose $N=5$ and you're told that there will be 3 red and 2 black numbers. If you start out with 100 chips, how can you make sure to get more than 300? And if instead there are 3 red numbers and 2 zeros, how can you double your stack?
Spoiler alert, I'm about to tell you how to bet optimally! First let's change the game in a way that doesn't actually matter, but that simplifies the analysis. Instead of green cards for the zeros, let's make them wild cards (wild beasts?) that are red on one side and black on the other, so that when playing such a card, the devil can choose between counting it as red or as black.
As long as we only bet on one color, that's going to be just as good for the devil, since he can choose the other color. And it doesn't make much sense in the original setting for us to place a bet on red and another bet on black, since it will be at least as good to cancel chips bet on red against chips bet on black and only bet the difference on one of the colors. But with the red/black wild cards instead of the green ones, we can assume that we always bet everything we have, and that we only choose how much of our current bankroll to bet on red and how much to bet on black.
As long as we only bet on one color, that's going to be just as good for the devil, since he can choose the other color. And it doesn't make much sense in the original setting for us to place a bet on red and another bet on black, since it will be at least as good to cancel chips bet on red against chips bet on black and only bet the difference on one of the colors. But with the red/black wild cards instead of the green ones, we can assume that we always bet everything we have, and that we only choose how much of our current bankroll to bet on red and how much to bet on black.
Now we can use a method described by Peter Winkler (in a red/black setting without zeros) in his wonderful paper Games People Don't Play. His attempt to trace that problem to its origin seems to have reached the so-called grapevine (Update: It's actually discussed on pages 6-7 of these notes by Thomas Cover from 1974, which are cited in a different section of Peter Winkler's paper!). Suppose for instance that $N=10$ and that you learn that there's going to be 5 red, 3 black, and 2 zeros. Using the red/black wild cards, this means that whatever the devil does, in the end there will be 10 cards on the table of which 5, 6, or 7 will have a red side face up, and 3, 4, or 5 will be black. The total number of sequences of red/black that satisfy that constraint, like for instance R-B-B-B-R-R-B-R-R-R and B-B-R-R-R-R-B-R-R-R, turns out to be (using binomial coefficients)
\[\binom{10}3 + \binom{10}4 + \binom{10}5 = 120 + 210 + 252 = 582.\]
So we hire 582 gnomes to do the betting for us. Each gnome is assigned one of the R-B-sequences and a bag of money. Their task is to bet everything they have in each round on their own particular sequence. Clearly one of them will win whatever the devil does, and the one who wins will double their money 10 times, resulting in a payoff of 1024 times what they started with. If we distribute our initial bankroll evenly between the 582 gnomes, that means we can guarantee a final payoff of \[ \frac{1024}{582} \approx 1.759.\]
To see how to actually bet (in the first round say), let's find out how many gnomes will bet on red in the first round and how many will bet on black. It turns out (again summing some binomial coefficients) that of the 582 valid R-B-sequences, 336 start with an R and 246 start with a B. Consequently, 336 of our gnomes will bet on Red in the first round and 246 will bet on Black. To emulate this in the original game, we cancel the 246 bets on Black against equally many bets on Red, and in the end place $336 - 246 = 90$ out of every 582 chips on Red. So your first move is to bet a fraction of \[\frac{90}{582} = \frac{15}{97} \approx 0.155\] of your bankroll on Red.
After the first round, all the losing gnomes are out of the game, and we make the same calculation again for the second round, now using only the remaining gnomes/R-B-sequences.
Not only does this guarantee a payoff of, in this case, 1024/582, but it's also best possible. It turns out that whatever strategy we use can be emulated by a set of gnomes, and that the only thing we can vary is how we distribute our chips between them from the beginning. The devil will always let the poorest of our gnomes win, so the best we can do is to give them the same amount.
To see how to actually bet (in the first round say), let's find out how many gnomes will bet on red in the first round and how many will bet on black. It turns out (again summing some binomial coefficients) that of the 582 valid R-B-sequences, 336 start with an R and 246 start with a B. Consequently, 336 of our gnomes will bet on Red in the first round and 246 will bet on Black. To emulate this in the original game, we cancel the 246 bets on Black against equally many bets on Red, and in the end place $336 - 246 = 90$ out of every 582 chips on Red. So your first move is to bet a fraction of \[\frac{90}{582} = \frac{15}{97} \approx 0.155\] of your bankroll on Red.
After the first round, all the losing gnomes are out of the game, and we make the same calculation again for the second round, now using only the remaining gnomes/R-B-sequences.
Not only does this guarantee a payoff of, in this case, 1024/582, but it's also best possible. It turns out that whatever strategy we use can be emulated by a set of gnomes, and that the only thing we can vary is how we distribute our chips between them from the beginning. The devil will always let the poorest of our gnomes win, so the best we can do is to give them the same amount.
Payoff as a surprise
The payoff of $1024/582$ in our example can be interpreted as the inverse of a probability. The number 582 was the number of ways we can have 3, 4, or 5 Black in a sequence of Red-Black of length 10, so the probability of that happening if the sequence was decided by fair coin flips (or a roulette without zero) is \[\frac{582}{1024}.\]
In general, our payoff with $r$ red numbers, $b$ black numbers, and $z$ zeros is the inverse of the probability that a sequence of length $r+b+z$ of Red/Black generated by a roulette without zeros (let's call that a fair roulette) has at least $r$ Red and at least $b$ Black. The inverse of the probability is what we might call the surprise of an event - it's larger the more unexpected that event is (I'm not sure if there's an established name for the reciprocal of a probability, but it's sort of the same thing as the so-called odds). So our payoff is always the surprise of the hypothetical event that a fair roulette played for the same number of rounds would yield an outcome (in terms of number of red/black) consistent with the one we have (in the sense that the devil could use his wild cards to get the same red/black distribution as the fair roulette).
Let's look at another example: Suppose we give the devil a standard pack of 26 red cards, 26 black, and two jokers (to use as wild cards). What's our payoff going to be?
We can compute that as the surprise of the event that a fair roulette, played 54 times, would yield somewhere from 26 to 28 red numbers (a red/black distribution of 26-28, 27-27 or 28-26). Again the binomial coefficients give us the answer: The payoff is going to be
\[\frac{2^{54}}{\binom{54}{26}+\binom{54}{27}+\binom{54}{28}} \approx 3.159,\] reflecting the fact that the probability of 26, 27 or 28 red is roughly one in 3.159.
By the way, the Chernoff bound
By the way (that's how in academia we signal that we're about to say something important), the connection also goes the other way: We can use the devil's roulette to establish that certain events are extremely unlikely. Suppose for instance that you flip a coin a million times and the outcome is heads a little more than 505,000 times and tails not even 495,000 times. Is that normal? Or imagine that we're looking at whatever statistical data and asking whether deviations from what we expect can be explained by good-old 50-50 randomness or not. Even though the "expected" number of heads with a fair coin would be 500,000, surely we don't expect exactly that number. Should we be suspicious because we're off by 0.5%?
Let's play Devil's Roulette and give the devil 505,000 red and 495,000 wild cards. Since the wild cards can represent both red and black, this distribution represents every outcome with 505,000 or more Red. And let's consistently bet, throughout the game, 1% of our current bankroll on Red. This isn't the optimal strategy, but it's good enough.
If the devil plays sensibly, we'll win 505,000 times and lose 495,000 times. Every time we win, our bankroll increases by a factor $1.01$, and every time we lose, it decreases by a factor $0.99$. No matter in which order this happens, we end up with a payoff of
\[ 1.01^{505,000} \cdot 0.99^{495,000} \geq 5\cdot 10^{21}.\] We didn't even play optimally, and yet we secured a payoff of fifty round trips to Alpha Centauri measured in millimeters, or almost the weight of the earth in tonnes (wait, the latter somehow feels less impressive than the former!?).
This means that the probability of getting 505,000 or more heads in a sequence of a million fair coin flips is at most 1 in $5\cdot 10^{21}$. So yes, we should probably be suspicious.
This sort of inequality is known in probability theory by various combinations of the names Bernstein, Chernoff, Hoeffding, and Azuma. I dare say that thinking about it in terms of roulette is a slight improvement on the standard proofs. There's a parameter that needs to be optimized, but in our setting that's just what fraction to bet in every round.
As a sanity check on the method, if instead we give the devil 500,500 red and 499,500 wild cards, the best we can do with a strategy of betting a constant fraction turns out to be around 1.65 times the money. This gives no new information, since we already know that the probability of more Red than Black is at most 50%. And indeed, being off by 500 from the mean here is not very unlikely.
How to choose $N$: Maximum expected surprise
If it wasn't for the zero, the analysis would be simple: The larger the value of $N$, the more we would tend to win. If $N=100$ for example, we would end up with on average 101 times our initial bankroll. It seems that the analysis would be quite complicated, since if the devil gets 58 red cards and 42 black ones, say, then our payoff is the inverse of the probability of 58 red and 42 black in 100 rounds of roulette-without-zero, and that's just one term in an enormous sum. But the probability of this scenario exactly cancels what we win, so in the end we're summing 101 terms, each of which is equal to 1!
This insight can be summarized in the following theorem:
Anyway, when there are zeros, it turns out we shouldn't pick $N$ too large. If $N$ is large, then most likely the number of red, black, and zeros will be relatively close to their expected values of $\frac{18N}{37}$, $\frac{18N}{37}$ and $\frac{N}{37}$ respectively.
The probability that $N$ rounds of a roulette wheel without a zero would yield at least $\frac{18N}{37}$ red numbers and at the same time at least $\frac{18N}{37}$ black ones is going to be very close to 100% when $N$ is large. Since our payoff is the reciprocal of this, we will most likely finish with only a microscopic amount more than what we started with.
It's true that we might win a fortune if we're lucky, so to establish rigorously that the average payoff tends to 1 as $N$ tends to infinity will require a careful argument and some calculation. So let's not do that here.
The expected payoff for a given $N$ is, in a sense, how surprised we expect to be by the outcome of $N$ rounds of roulette (well, by a fair roulette being consistent with it in terms of the wild cards). If there are too few rounds, too few things can happen for anything to be surprising, but if there are too many, then most of the time each color will appear with about its expected frequency.
It's fairly easy to let the computer calculate the average payoff for various values of $N$.
\[
\begin{array}{cc}
N & \text{Payoff} \\
1 & 1.97 \\
2 & 2.91 \\
3 & 3.81 \\
4 & 4.69 \\
5 & 5.52 \\
6 & 6.33 \\
7 & 7.11 \\
8 & 7.85 \\
9 & 8.58 \\
10 & 9.27 \\
\end{array}
\]
So far so good. I said before that if there aren't any zeros, the average payoff is $N+1$, and these numbers seem to reflect that, being a little smaller due to the possibility of zeros.
And when we take the calculation a little further, we reach a peak average payoff at $N=66$, after which it decreases. At $N=311$, it's again down to less than 10 times the initial bankroll.
\[
\begin{array}{cc}
N & \text{Payoff} \\
\vdots & \vdots \\
61 & 22.6204 \\
62 & 22.6403 \\
63 & 22.6558 \\
64 & 22.6668 \\
65 & 22.6737 \\
66 & 22.6765 \\
67 & 22.6755 \\
68 & 22.6707 \\
69 & 22.6624 \\
70 & 22.6506 \\
\vdots & \vdots \\
311 & 9.977 \\
\vdots & \vdots \\
\end{array}
\]
Number of the beast
The number 666 is mentioned in the Bible (Revelation 13:18) and is traditionally associated with the devil, but also with roulette. The sum of all the numbers on the roulette wheel is 666, and its inventor François Blanc is said to have made a deal with the devil to obtain the secrets of the game. There is (of course!) a Numberphile video about this!
So 666 has to do with Antichrist and gambling and sin. But the number 66 is pretty badass too in a more modern way. It's associated with the Wild West and getting kicks from jazz music. Dangerous stuff.
And whenever you play roulette with the devil, play exactly 66 times!
The payoff of $1024/582$ in our example can be interpreted as the inverse of a probability. The number 582 was the number of ways we can have 3, 4, or 5 Black in a sequence of Red-Black of length 10, so the probability of that happening if the sequence was decided by fair coin flips (or a roulette without zero) is \[\frac{582}{1024}.\]
In general, our payoff with $r$ red numbers, $b$ black numbers, and $z$ zeros is the inverse of the probability that a sequence of length $r+b+z$ of Red/Black generated by a roulette without zeros (let's call that a fair roulette) has at least $r$ Red and at least $b$ Black. The inverse of the probability is what we might call the surprise of an event - it's larger the more unexpected that event is (I'm not sure if there's an established name for the reciprocal of a probability, but it's sort of the same thing as the so-called odds). So our payoff is always the surprise of the hypothetical event that a fair roulette played for the same number of rounds would yield an outcome (in terms of number of red/black) consistent with the one we have (in the sense that the devil could use his wild cards to get the same red/black distribution as the fair roulette).
Let's look at another example: Suppose we give the devil a standard pack of 26 red cards, 26 black, and two jokers (to use as wild cards). What's our payoff going to be?
We can compute that as the surprise of the event that a fair roulette, played 54 times, would yield somewhere from 26 to 28 red numbers (a red/black distribution of 26-28, 27-27 or 28-26). Again the binomial coefficients give us the answer: The payoff is going to be
\[\frac{2^{54}}{\binom{54}{26}+\binom{54}{27}+\binom{54}{28}} \approx 3.159,\] reflecting the fact that the probability of 26, 27 or 28 red is roughly one in 3.159.
By the way, the Chernoff bound
By the way (that's how in academia we signal that we're about to say something important), the connection also goes the other way: We can use the devil's roulette to establish that certain events are extremely unlikely. Suppose for instance that you flip a coin a million times and the outcome is heads a little more than 505,000 times and tails not even 495,000 times. Is that normal? Or imagine that we're looking at whatever statistical data and asking whether deviations from what we expect can be explained by good-old 50-50 randomness or not. Even though the "expected" number of heads with a fair coin would be 500,000, surely we don't expect exactly that number. Should we be suspicious because we're off by 0.5%?
Let's play Devil's Roulette and give the devil 505,000 red and 495,000 wild cards. Since the wild cards can represent both red and black, this distribution represents every outcome with 505,000 or more Red. And let's consistently bet, throughout the game, 1% of our current bankroll on Red. This isn't the optimal strategy, but it's good enough.
If the devil plays sensibly, we'll win 505,000 times and lose 495,000 times. Every time we win, our bankroll increases by a factor $1.01$, and every time we lose, it decreases by a factor $0.99$. No matter in which order this happens, we end up with a payoff of
\[ 1.01^{505,000} \cdot 0.99^{495,000} \geq 5\cdot 10^{21}.\] We didn't even play optimally, and yet we secured a payoff of fifty round trips to Alpha Centauri measured in millimeters, or almost the weight of the earth in tonnes (wait, the latter somehow feels less impressive than the former!?).
This means that the probability of getting 505,000 or more heads in a sequence of a million fair coin flips is at most 1 in $5\cdot 10^{21}$. So yes, we should probably be suspicious.
This sort of inequality is known in probability theory by various combinations of the names Bernstein, Chernoff, Hoeffding, and Azuma. I dare say that thinking about it in terms of roulette is a slight improvement on the standard proofs. There's a parameter that needs to be optimized, but in our setting that's just what fraction to bet in every round.
As a sanity check on the method, if instead we give the devil 500,500 red and 499,500 wild cards, the best we can do with a strategy of betting a constant fraction turns out to be around 1.65 times the money. This gives no new information, since we already know that the probability of more Red than Black is at most 50%. And indeed, being off by 500 from the mean here is not very unlikely.
How to choose $N$: Maximum expected surprise
If it wasn't for the zero, the analysis would be simple: The larger the value of $N$, the more we would tend to win. If $N=100$ for example, we would end up with on average 101 times our initial bankroll. It seems that the analysis would be quite complicated, since if the devil gets 58 red cards and 42 black ones, say, then our payoff is the inverse of the probability of 58 red and 42 black in 100 rounds of roulette-without-zero, and that's just one term in an enormous sum. But the probability of this scenario exactly cancels what we win, so in the end we're summing 101 terms, each of which is equal to 1!
This insight can be summarized in the following theorem:
The expected surprise of any random variable is its number of possible outcomes.The surprise of an event is also equal to the expected number of times you have to try again until the same thing happens. For instance, if you repeatedly flip a coin, the expected number of times until you get the same outcome again as the first time is 2, even if the coin is biased. Or maybe it's 3...?
Anyway, when there are zeros, it turns out we shouldn't pick $N$ too large. If $N$ is large, then most likely the number of red, black, and zeros will be relatively close to their expected values of $\frac{18N}{37}$, $\frac{18N}{37}$ and $\frac{N}{37}$ respectively.
The probability that $N$ rounds of a roulette wheel without a zero would yield at least $\frac{18N}{37}$ red numbers and at the same time at least $\frac{18N}{37}$ black ones is going to be very close to 100% when $N$ is large. Since our payoff is the reciprocal of this, we will most likely finish with only a microscopic amount more than what we started with.
It's true that we might win a fortune if we're lucky, so to establish rigorously that the average payoff tends to 1 as $N$ tends to infinity will require a careful argument and some calculation. So let's not do that here.
The expected payoff for a given $N$ is, in a sense, how surprised we expect to be by the outcome of $N$ rounds of roulette (well, by a fair roulette being consistent with it in terms of the wild cards). If there are too few rounds, too few things can happen for anything to be surprising, but if there are too many, then most of the time each color will appear with about its expected frequency.
It's fairly easy to let the computer calculate the average payoff for various values of $N$.
\[
\begin{array}{cc}
N & \text{Payoff} \\
1 & 1.97 \\
2 & 2.91 \\
3 & 3.81 \\
4 & 4.69 \\
5 & 5.52 \\
6 & 6.33 \\
7 & 7.11 \\
8 & 7.85 \\
9 & 8.58 \\
10 & 9.27 \\
\end{array}
\]
So far so good. I said before that if there aren't any zeros, the average payoff is $N+1$, and these numbers seem to reflect that, being a little smaller due to the possibility of zeros.
And when we take the calculation a little further, we reach a peak average payoff at $N=66$, after which it decreases. At $N=311$, it's again down to less than 10 times the initial bankroll.
\[
\begin{array}{cc}
N & \text{Payoff} \\
\vdots & \vdots \\
61 & 22.6204 \\
62 & 22.6403 \\
63 & 22.6558 \\
64 & 22.6668 \\
65 & 22.6737 \\
66 & 22.6765 \\
67 & 22.6755 \\
68 & 22.6707 \\
69 & 22.6624 \\
70 & 22.6506 \\
\vdots & \vdots \\
311 & 9.977 \\
\vdots & \vdots \\
\end{array}
\]
Number of the beast
The number 666 is mentioned in the Bible (Revelation 13:18) and is traditionally associated with the devil, but also with roulette. The sum of all the numbers on the roulette wheel is 666, and its inventor François Blanc is said to have made a deal with the devil to obtain the secrets of the game. There is (of course!) a Numberphile video about this!
So 666 has to do with Antichrist and gambling and sin. But the number 66 is pretty badass too in a more modern way. It's associated with the Wild West and getting kicks from jazz music. Dangerous stuff.
And whenever you play roulette with the devil, play exactly 66 times!
No comments:
Post a Comment