FOB

I purchased a book from the Google eBookstore today. Boy, I'll never do that again…

I've looking for fantasy to read on an upcoming trip, so I Googled "all-time best fantasy" just now. I carefully inspected eight different lists: specifically all the relevant lists in the first page of search results. Of those eight lists, six were trash. Here's a meta-review…

Here's the deal—I've trusted Blizzard Entertainment. Enough trust to invest $15/month of my money, and more recently $30/month, for a year. More importantly, enough to invest many, many hours of my time. Blizzard, meanwhile, hasn't done a single thing that I've noticed to earn that trust. It's time for me to stop now…

While doing some research for an upcoming paper, I came upon a 2008 blog post describing a special case of the following interesting problem:

Given an alphabet of n symbols, construct a uniformly-selected sequence of m of these symbols, with the sequence containing no duplicate symbols.

[Updated 2009/12/14] The difficulty arises when both m and n are large. The obvious method is a rejection method: repeatedly pick a random symbol from the alphabet and check whether you've picked it already. If not, append it to your target number. The problem is that the duplicate check seems to require log m time even if you code it cleverly, giving an asymptotic performance of O(m log m). Hash tables can help some, but ultimately you're going to waste a lot of time checking for the unlikely case that you've generated a duplicate.

There were various solutions given in the comments, but none of them were optimal. A spoiler follows…

I've been a huge fan of The Onion, the satirical newspaper originally published by the University of Wisconsin, for about 15 years now. I've purchased their books and audiobooks, downloaded their videocasts to my TiVO, etc.

That ended tonight…

I won a poker tournament last night. It wasn't a big tournament: 20 people playing at an American Legion Hall in North Portland, with the rake mostly going to charity. $20 buy-in, with payouts of $225/$125/$75. By the time I bought a round of drinks and threw in some charity money, I came home with about $150…

Here's the answers to antonyms:

1. antonym :: synonym
2. arcane :: mundane
3. aristocratic :: plebian
4. coerce :: entreat
5. embrace :: abjure
6. exacerbate :: ameliorate
7. exotic :: quotidian
8. sostenuto :: staccato
9. reduce :: oxidize
10. materialize :: dematerialize

Explanations available on request.

I keep wanting to blog about my latest tiny piece of software, but I keep having one more bug or feature.

So instead, I've cooked up this little word game. Tell me what you think of it…

I was playing in a D&D game with my boy last Sunday, and someone brought up the question of how likely a character was to have an 18 stat. Of course the rest of the session was a loss for me, as I sat there trying to do the math with pencil, paper, and a four-function calculator.

D&D has six stats, each a number between 3 and 18. The character roll-up rules we are playing specify that each stat will be obtained by rolling four dice and taking the top three.

About 9% of D&D characters will have an 18 stat. The answer is explained here.

So as I said, we're rolling six stats for D&D, where each stat is determined by rolling four six-sided dice and taking the top three…

The probability of getting at least one 18 in six rolls is computed in the usual way. Call the probability of getting 18 in a single roll p. The probability that a given roll is not an 18 is (1 - p). To not roll an 18, all six rolls must independently be not 18s, so we can multiply their probabilities to get the probability (1 - p)**6 that no 18 was rolled. We want the probability that 18 was rolled, so we take the complement 1 - (1 - p)**6 .

Computing p is also straightforward. Consider an ordered roll of four six-sided dice. There are thus 6**4 = 1296 possible rolls. Of these, there is exactly one in which all four dice are sixes, which will give a roll where the top three are 18. The only other way this can happen is if three of the four dice are sixes, and the fourth is less than six. There are five ways a die can be less than six, and there are four different dice this could happen to, so there are 4×5 = 20 possible rolls with this property. Thus, the overall probability p that a given roll is an 18 is (1 + 20)/1296 = 7/432, which is very close to 1/62.

We thus have an overall probability of about 1 - (1 - 1/62)**6 = 1 -(61/62)**6 that a given character will have an 18 stat. But this isn't too convenient to calculate with pencil, paper, and four-function calculator. So we back up a step and note that (61/62)**6 can be approximated by (1 - 6/62 - 15/62**2-…) using the binomial theorem. The displayed terms of this expression are straightforward, and could be done pencil-and-paper: a calculator gives 0.8993, very close to the value of 0.9070 given by the explicit exponential.

There's our answer: about 10% of D&D characters will have an 18 stat. To check this, I hand-rolled 15 characters, and got two with 18 stats. Then I computer-rolled 100000 characters, and got 9425/100000 with about two significant figures of repeatability. The true answer using Nickle as an arbitrary-precision full-function calculator without the approximations done above is (1-(1-21/1296)**6) = 606876045137999/6499837226778624, or about 9.337%. Thus, experiment and theory seem to agree, and we go away happy.