This is a story about counter-intuitive probabilities and how a small bit of doubt turned out to be very justified.
It begins with the game
To Court the King (German:
Um Krone und Kragen ). It is a nice game with dice and cards, where you start with a few dice, and use your dice rolls to buy additional cards, which give you extra dice or special powers to modify the dice that you rolled. You can actually roll your dice many times, but every time, you have to set aside at least one die, which you can no longer change or reroll, until eventually all dice have been set aside.
A few years ago, I have played this game a lot, both online (on
yucata.de) as well as in real life. It soon became apparent that it is almost always better to go for the cards that give you an extra die, instead of those that let you modify the dice. Intuitively, this is because every additional die allows you to re-roll your dice once more.
I concluded that if I have a certain number of dice (say,
n), and I want to have a sum as high as possible at the end, then it may make sense to reroll as many dice as possible, setting aside only those showing a 6 (because that is the best you can get) or, if there is no dice showing a 6, then a single die with the best score. Besides for small number of dice (2 or 3), where even a 4 or 5 is worth keeping, this seemed to be a simple, obvious and correct strategy to maximize the expected outcome of this simplified game.
It is definitely simple and obvious. But some doubt that it was correct remained. Having one more die still in the game (i.e. not set aside) definitely improves your expected score, because you can reroll the dice more often. How large is this advantage? What if it ever exceeds 6 then it would make sense to reroll a 6. The thought was strange, but I could not dismiss it.
So I did what one does these days if one has a question: I
posed it on the mathematics site of StackExchange. That was January 2015, and nothing happened.
I tried to answer it myself a month later, or at least work towards at an answer, and did that by brute force. Using a
library for probabilistic calculations for Haskell I could write
some code that simply calculated the various expected values of
n dice for up to
n = 9 (beyond that, my unoptimized code would take too long):
1: 3.50000 (+3.50000)
2: 8.23611 (+4.73611)
3: 13.42490 (+5.18879)
4: 18.84364 (+5.41874)
5: 24.43605 (+5.59241)
6: 30.15198 (+5.71592)
7: 35.95216 (+5.80018)
8: 41.80969 (+5.85753)
9: 47.70676 (+5.89707)
Note that this calculation, although printed as floating point numbers, is performed using fractions of unbounded integers, so there are no rounding issues that could skew the result.
The result supported the hypothesis that there is no point in rolling a 6 again: The value of an additional die grows and approaches 6 from beyond, but judging from these number is never going to reach it.
Then again nothing happened. Until 14 month later, when some
Byron Schmuland came along, found this an interesting puzzle, and set out a 500 point bounty to whoever solved this problem. This attracted a bit attention, and a few not very successful attempts at solving this. Eventually it reached twitter, where
Roman Cheplyaka linked to it.
Coincidally a day later some
joriki came along, and he had a very good idea: Why not make our life easier and think about dice with less sides, and look at 3 instead of 6. This way, and using a more efficient implementation (but still properly using rationals), he could do a similar calculation for up to 50 dice. And it was very lucky that he went to 50, and not just 25, because up to 27, the results were very much as expected, approaching value of +3 from below. But then it surpassed +3 and became +3.000000008463403.
In other words: If you have roll 28 dice, and you have exactly two dice showing a 3, then it gives you better expected score if you set aside only one 3, and not both of them. The advantage is minuscule, but that does not matter it is there.
From then on, the results behaved strangely. Between 28 and 34, the additional value was larger than 3. Then, from 35 on again lower than 2. It oscillated. Something similar could be observed when the game is played with coins.
Eventually, joriki improved his code and applied enough tricks so that he could
solve it also for the 6-sided die: The difference of the expected value of 198 dice and having 199 dice is larger than 6 (by
10 21...)!
The optimizations that allowed him to calculate these numbers in a reasonable amount of time unfortunately was to assume that my original hypothesis (never rerolling a 6 is optimal), which held until
n < 199. But this meant that for
n > 199, the code did not yield correct results.
What is the rationale of the story? Don t trust common sense when it comes to statistics; don t judge a sequence just from a few initial numbers; if you have an interesting question, post it online and wait for 16 months.
github-backup is an attempt to take something I don't like --
github's centralization of what should be a decentralized techology -- and
find a constrictive way to make it at least meet my baseline requirements
for centralized systems. Namely that when they go away, I don't lose data.
So, it was written partly with my ArchiveTeam hat on.
A recent bug filed on it,
Backup fails for repositories unavailable due to DMCA takedown
made me happy, because it shows github-backup behaving more or less as
intended, although perhaps not in the optimal way.
By the way, this is the only one of my projects that uses github for issue
tracking. Intentionally ironically.
It was my second real Haskell program (after git-annex)
and so also served as a good exercise in applying what
I'd learned about writing Haskell up to that point.
Next: twenty years of free software -- part 9 small projects
I had my strong doubts as to whether the shipment would be allowed through customs, and was happily surprised by a smiling Graham today before noon. He handed me a smallish box that arrived to his office, containing...
For those who care about kdepim (kmail, kontact, korganizer, etc)
Last week, I posted about 
.
Debian LTS
This was my twenty-fourth month that I did some work for the 
Here is my monthly update covering a large part of what I have been doing in the free software world (
It s rare to be in a position to be able to publicly announce you re looking for a new job, but as the opportunity is currently available to me I feel I should take advantage of it. That s especially true given the fact I ll be at 
I've just released version 1.3.0 of 