Thursday, December 02, 2004

The Moving Bar Method

Dear Roy:

Ah, my young padawan, this does bring back memories of those days in CRC. I am now no more than a glorified computer salesman, much abused by business partners, customers, managers, and so-called subordinates; so it is with some pleasure that I'm able to flex my intellectual muscles and recall brighter days. Thank you for the opportunity.

I guess the quickest way to explain my solution to the loaded dice problem is to just dive into a simple example straightaways. So here goes: for two honest six-sided die, how many combinations will result in a five being rolled? The answer, if you build a table and start counting, is four combinations. But how about if you don't build a table? Is there another way?

Here's my suggestion for getting that figure. Numbers in brackets indicate the number on the face of the die; numbers not in brackets are the relative probability. (Again, I'm not sure if that's the proper term; but you know what I mean.)


Die 1 Die 2
1 - [6]
1 - [5]
[1] - 1 1 - [4]---------1 x 1 = 1
[2] - 1 1 - [3] 1 x 1 = 1
[3] - 1 1 - [2] 1 x 1 = 1
[4] - 1 1 - [1]---------1 x 1 = 1
[5] - 1 Sum = 4
[6] - 1


That's four combinations, or a relative probability of four. Translating this to actual probability, we divide four by 36, the total number of combinations (6x6), to give us 0.111....

What I'm trying to do here is get the intersection of the two dice so that the faces equal five. I get the product of the probability (or relative probability) of those intersections and add them up, and I get four possible combinations. You can extend this to all the other possible combinations of numbers for two dice: keep die 1 stationary, and just move die 2 across, looking for the intersections, and adding up the products. You'll see that you actually generate the relative probability table, or RTP, for two honest six-sided dice.


[2] - 1 [8] - 5
[3] - 2 [9] - 4
[4] - 3 [10]- 3
[5] - 4 [11]- 2
[6] - 5 [12]- 1
[7] - 6


What about the case for three honest six-sided dice? You should consider the two dice to be an 11-sided die ranging from 2 to 12, but whose RTP follows that given above. Then, you match that against the RTP of the remaining die.

Example: what is the relative probability of churning out a 10 from throwing three honest six-sided die?


Die 1 Die 2

[2] - 1
[3] - 2
[4] - 3 1 - [6]---------3 x 1 = 3
[5] - 4 1 - [5] 4 x 1 = 4
[6] - 5 1 - [4] 5 x 1 = 5
[7] - 6 1 - [3] 6 x 1 = 6
[8] - 5 1 - [2] 5 x 1 = 5
[9] - 4 1 - [1]---------4 x 1 = 4
[10]- 3 Sum = 27
[11]- 2
[12]- 1


That's a relative probability of 27; actual probability is 27 divided by 216 (6x6x6), or 0.125.

I call this my "moving bar" technique, because I am essentially moving one RTP across another in order to get the sum of their products.

The case for loaded dice follows much the same technique, except that the RTPs of the dice have essentially been tampered with and no longer start out with relative probabilities of one.

It's quite funny how I came across this method. Ten years ago, this started out as a simple problem of how to generate probability tables for three or more dice. I was beating my head against the wall, and a flash of insight: I could actually generate the new table by moving a "bar" across the old probability table. But in my mind, this was a "physical" measuring bar, six numbers wide, with which I summed up all the numbers inside. I didn't know why it worked; it just did. I was happy at the result, and I set it aside.

Last year, this was one of the problems that I submitted to the ACM ICPC. However, to make it interesting, I started thinking about odd-shaped dice, ones that were not cubes. How would that work out? I modified my thinking to alter the size of the measuring bar to fit the number of sides of the die; again, it worked, though I didn't know why. Unfortunately, the problem was shelved because the other judges thought it was too easy to generate the tables in brute force fashion.

Finally, this year, I thought of modifying the problem to include loaded dice. But how did the measuring bar fit into all this? There seemed to be no way, and I resigned myself to just applying the solution in brute force fashion. The problem must have been percolating in my mind, because, attending Mass one day, I had another flash of insight. The solution is what you see here.

I hope that with this description the Python program should start to make sense. I'm simply padding the RPT for the first die with zeroes at both ends so as to give my "moving bar" (the RPT of the second die) room to maneuver. That way, I don't have to build any special cases. Perhaps there is a better approach; if so, I would like to see it. But I am pretty pleased at the cleverness of the method.

Let me know what you think.


Sincerely,

Dominique

2 comments:

  1. This is very very clever. If I figured it correctly, if you have n number of s-sided dice, the brute force method will require O(s^n) multiplications. Your method would be on the order of (n^2)(s^2).

    The trick of converting the results of two dice into one bigger die is key. I wonder how many contestants can come up with this algorithm (and implement it!) in a couple of hours. I suppose it is a matter of exposing them to a lot of different problems and approaches to solving problems so that they can recognize which ones are appropriate quickly.

    Hm, have you considered coaching one of the ACM teams? I hear that UA&P did pretty respectably this year.

    ReplyDelete
  2. Thanks, Roy. Glad you like it. I wasn't too sure how to express it in Big-O notation.

    He he, now that I'm leaving IBM, maybe I'll train a team from the province instead.

    ReplyDelete