Comment by munificent | Hacker News Reader

Comment by munificent | Hacker News Reader

I love that they put so much work into trying to solve this when there is an equally trivially simple mechanical solution that works just as well and easily scales up to any number of users:

1. Put consecutive numbered tiles in an opaque bag.

2. Each person reaches in and blindly grabs a tile.

3. Play proceeds in the order of tiles.

You can think of dice rolling as simple random sampling with replacement. It's naturally good at generating combinations. Drawing from a bag is random sampling without replacement. It's naturally good at generating permutations.

Using a system that generates combinations to generate uniformly distributed random permutations is a super fun mathematical exercise and I'm sure this brought plenty of joy to the authors. But if you're just trying to design a physical mechanism to generate permutations, it'll be an easier starting point if you do sampling without replacement.

In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it is:

1. Choose an arbitrary ordering for the players.

2. For each player, roll a die. If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.

3. Play proceeds in the order of values each player rolled.

You'll probably want to use d20 or some dice with a large number of faces relative to the number of players in order to minimize collisions and re-rolling.

I'm not 100% certain, but I believe this will generate an unbiased ordering where the order of players in step 1 has no effect on the resulting order determined in step 3.

It's worth noting that they primarily pursue this as a pleasurable puzzle, not for any practical payoff to the problem of player primacy:

>We both understood that this was really a "solution looking for a problem" (there are plenty of perfectly acceptable ways to quickly determine who might go first in a game), but mathematically, wouldn't it be great if a set of dice could be created [...]

Did you plan that phenomenal "p" alliteration?

There might be a slick method to prove your final approach works to generate a uniformly random permutation. First, it's easy to prove if the number of players, n, equals the number of sides of the die, m. Because a random permutation is characterized as the first player equally likely to land in any spot, along with the permutation among the remaining n-1 players into the remaining n-1 slots being uniformly random. If n=m, then the first player's number that they pick determines where they end up in the permutation. And by induction, the remaining players pick a permutation uniformly from the remaining slots. The base case of n=m=1 is immediate.

Now the slick proof for the case m > n is to add m-n extra "dummy" players. They get to pick after the n players have picked. By the above argument, we get a uniformly random permutation of the m total players, including the dummy players. But when we remove any subset of players from a uniformly random permutation -- in this case, the dummy players -- we are left with a uniformly random permutation on the rest.

Surprised no one has mentioned this, but the lexically-canonical version of this uses straws of different length.

https://en.wiktionary.org/wiki/draw_straws

https://en.wiktionary.org/wiki/draw_the_short_straw

> In fact, if you do want to generate permutations with dice, a simple (but laborious) way to do it...in a single roll

A single die of <#players>! sides. 4 players = 24 sided die, each side has an order permutation. Impractical, but doable. Excepting for all the other arbitrary requirements.

This is all an elaborate exercise borne of someone's idle time, so it's best not to put too much into it. They already did that work.

> If the value rolled is the same as any value rolled by a previous player, re-roll. Continue to re-roll until a unique value is rolled.

This gives an advantage to earlier players because it gives them "first dibs" on higher numbers. In the extreme, if the first player rolls the highest number, no one can subsequently beat them no matter what they roll.

This is also true for lower numbers. It evens out so each player is equally likely to end up with each number.

Right. I should have realized this because the protocol is equivalent to selection without replacement, which of course it fair. My mistake.

If you consider n players and an n-sided die, you'll see this isn't true in that case. The first player has an exactly equal chance to be first, second, ..., last.

We'll need a way to decide who goes first when deciding who goes first!

I know just the protocol for that!

> to generate permutations with dice, a simple (but laborious) way to do it is

Of course, the article rules this out, and requires a single roll.

I can vaguely imagine a system where what the authors describe will come in handy. Let's say you have a group of n distributed agents that collaborate over multiple rounds, and they need to establish a fair order of precedence for each consecutive round. Let's say each agent issues a message each round, and a "counter" decides the order that those messages resolve.

In that case, you can (pre-)assign each agent a pseudorandom go-first die. They can tag their messages with the results of their go-first die, and the counter can now resolve the messages in a fair order.

If you publish the PRNG seeds for all agents, so that every agent has it, they can all be counters. This means that every agent will resolve the messages in a deterministic order every round, and over all the rounds, the processing will be fair. Seems like a useful property.

It might still be if interest from a computational viewpoint. For instance what if you need to compute a fair and random ordering for many many elements of a set? Then the dice method is more parallelizable than the bag method.

The limitation is getting the entropy. Where do you get that from in parallel?

Well, I think your second example has problems (already noted by others), but also: get out of here with your sensible and boring practicalities! This is a great article and a worthy quest!

Reply on news.ycombinator.com