Thursday 29 March 2012

Dice and Tables

I have been thinking again about the problem of indexing up to 400 elements in some kind of random table. In a previous post I mentioned that this was all possible using various computer methods. The main motivation here is thinking about how to do this at the table with just a bag of dice, and for the method to be unbiased, so that every entry has the same chance of being selected by the dice as any other.

Ideally, we want to:
  1. use the standard polyhedral dice: d4, d6, d8, d10, d12, d20;
  2. minimise re-rolling dice as much as possible;
  3. not have any more dice involved than necessary.
All of this, mathematically, leads to thoughts of "best" algorithms, and "best" processes. In any mathematical investigation, we very rarely are able to jump from ideals and assumptions to the final answer. This time is no different, but there is hope I think that something can be done which is both easy to use and simple to understand (mathematically).

The first insight which was really helped is the idea that indexing X elements in tables is the same as rolling a dX, where X is any positive integer. Imagine that you take X square pieces of paper, write the numbers from 1 up to X on them, and paste them to a board. Throw a dart blindly at the board and you randomly select a number - which, for all intents and purposes is the same as rolling a dX.

Take the numbers down off a board now and try to arrange them into a table, or into a series of tables. Here comes the IF:
If we can arrange the X squares into a series of good* tables, then we can index X elements easily.
A consequence of all of this is that those good tables could just as easily contain the numbers from 1 to X written on them. So rolling a dX and rolling to get one of those X elements add up to the same thing, more or less (in maths terms, I think we could safely say that the two things were homomorphic).

And this was my big thought on the topic so far (well, one of them at least): it makes as much sense to see how we can simulate a dX using the standard polyhedral dice as it does to think about organising X elements into tables.

In future posts, simulating dX with the standard polyhedral dice! And how this ties in to random tables.

*in the sense of the three criteria from earlier in the post

No comments:

Post a Comment