How to flip a coin when you haven't got one

1. Discover neither of you wants to decide on a particular thing (which movie you want to see, what kind of food to eat, whether or not you should get divorced, Linux or FreeBSD, etc), because both choices are equally acceptable or both parties are equally indecisive.
2. Get the choices down to two¹.
3. One person mentally assigns a value to each choice and makes a gesture, as if flipping a coin.
4. This is the cue for the other person to "call it in the air" by saying either "heads" or "tails."
5. The first person then announces what the result is.
6. Everyone goes along with the result.²

¹ For more advanced or tricky situations, it is possible to do this with three choices; then you have the options of "heads," "tails," and "sides" (forget the laws of physics, all choices are equally possible for this purpose).

² This is similar to how to cut cake without favoritism.

1. Each person (normally two, but more can take part) picks either the number one or two.
2. Each person holds that many fingers up behind their back.
3. On the word "go", each person pulls their hand from behind their back.
4. The number of fingers are added. If the sum is an even number, it's tails. If an odd number, it's heads.

No matter which number you yourself pick, the second person has an equal chance of making the sum even or odd -- as does the third, fourth, or nth person taking part.

1. Each person picks either heads or tails
2. Click on an arbitrary *

1. Alice and Bob have a decision to make, between a virtually limitless number of options. We'll say they have three: they're deciding whether to go to the park, the river, or the mall.
2. Alice assigns three unrelated words to each of the different options. The park becomes "sneeze", the river becomes "freckle", and the mall becomes "tiger". Alice does not inform Bob of these assignments.
3. Alice then asks, "Tiger, freckle, or sneeze?"
4. Bob picks whichever one happens to strike his fancy, Alice informs him of the corresponding option, and a decision is made.

A biased one is where Heads has some probability p <> 0.5 and Tails has probability 1 - p.

So if you throw it twice in a row, there are four possibilities, Pr(HH) = p^2 and Pr(TT) = (1 - p)^2 being unusable because you don't know what p is, but HT and TH are equiprobable regardless of what p is. So throw it twice and let HT count as Heads and TH counts as Tails.

This only works with someone who either understands probability or trusts you and believes that you understand probability. To anyone else, you could probably explain it till you were blue in the face and not get anywhere.

Of course it doesn't depend on p being other than 0.5, so it works for any coin.

And it doesn't depend on using coins, so it works for any arrangement where you have two probabilities summing to unity. For example, blindly taking a pen out of a drawer containing five blue and three black pens.

Since each person is equally likely to choose any number between 0 and m-1, the sum modulo m of these numbers is also equally likely to be anywhere between 0 and m-1. Note that the randomness of this algorithm is independent of n, the number of people that pick numbers at random. Furthermore, no person can introduce bias (cheating is impossible) because no one knows what the other randomly chosen numbers will be. For example, should I decide that choosing 5 will give me an unfair advantage, 5 added to a random number (everyone else's numbers) is just as random, so I really have no unfair advantage.

If we let m=n, this is a simple coordinator election algorithm (i.e., for choosing who sits shotgun,etc.)

*note that you can represent a range of 1024 numbers on ten fingers if you use a binary representation instead of unary, so we're not limited to m being at most 10.

The way I do it is thus; first I hold up a hand showing the N fingers (you may already spot a limitation with my system).

Now choose one randomly.

Before you all shout, "Charlatan", stop. This is just the seed value.

Now you need a nursery rhyme, some song lyrics or something similar. Sing or speak your song/rhyme, while counting through your fingers. Count a finger per each syllable or maybe word but take care not to count on each beat - this is rather predictable and will ruin an already poor algorithm.

When you reach the end of your little sing-song you will have made your decision.

If you need to flip a coin - that is, make a random yes/no decision - in your mind, use the following procedure:

1. Think of any number with about five digits. The digits shouldn't be too small. No 10001, 12000 or 20001. Also, don't use the same number again for another decision, since you'll already know the result.
   Example: 63194
2. Now add all the digits.
   6 + 3 + 1 + 9 + 4 = 23
3. Repeat step 2 until you have a single-digit number.
   2 + 3 = 5
4. If the resulting number is odd, the answer is yes. If it is even, the answer is no.
   5 is odd -> Yes

There is no way you can know whether a five-digit number will add up to be odd or even (unless the digits are too small). This method has two advantages: You don't need another person to help you, and you don't have to gesticulate. Nobody'll notice if you cast your vote for a random president.

Fordprefect informed me that for this method to work fairly, you need to pick an odd digit (say, 1) and throw out the result if you get it. Otherwise there are 5 odd possibilities and 4 even ones. 0 never happens.

Alice and Bob agree on a hash function H which compresses its input to an N-bit result. H should have a result long enough to prevent a mortal from finding two inputs which hash to the same result. It should also be free of shortcuts for doing so. In other words, it should be a cryptographic hash.

One of the two people picks a random number, hashes it with H(x), and tells y=H(x) to the other party. The recipient of y guesses whether the random input was even or odd. After this, the party who generated the random number reveals this secret number. The recipient can compute H(x) and verify that it equals y, thus, that x is almost certainly the original random number. After this it is obvious to both sides whether the guess was correct.