## Coin Flip

30 May

I had occasion to write a little routine called CoinFlip:

```
```**function** CoinFlip: Boolean;
**begin**
Result := Random > 0.5;
**end**;

I don’t know why I found it mildly amusing. And I bet someone will tell me that it is slightly biased in one direction. Because it is. Anyway, thought you all might enjoy it, too.

[...] Nick Hodges » Blog Archive » Coin Flip [...]

May 30th, 2010 at 8:27 pm[...] Nick Hodges » Blog Archive » Coin Flip [...]

May 30th, 2010 at 8:27 pmShouldn’t that be ">=" instead of ">" ?

May 30th, 2010 at 8:52 pm2 points :

May 30th, 2010 at 11:09 pm- Randomize is missing

- there is a lot of chance that the randomized number will be greater than 0.5

@Stephane

Why call Randomize in a CoinFlip function like this? It doesn’t belong there. It is fits a LOT better in the initialization section of the unit.

Yes it’s try that the number will be greater than 0.5, it’s about 50% chance. Actually, I believe it’s actually more likely that is WON’T be greater. (But just slightly)

May 31st, 2010 at 5:45 amA better way of doing a coinflip is :

Result := Random > Random;

It will have no bias or at least a two times better bias.

May 31st, 2010 at 6:01 amI’m guessing this function was used to determine what next Delphi version targets first, Win64 or x-platform.

May 31st, 2010 at 6:19 amMust have been a previous version:

{code}

May 31st, 2010 at 7:19 amfunction Make64BitCompiler: Boolean;

begin

Result := Random > 32;

end;

{code}

My suggestion:

function CoinFlip: Boolean;

May 31st, 2010 at 9:08 ambegin

Result := Boolean(Random(2));

end;

This year, a true computational random number generator was made that relies on quantum physics. In case somebody wants to know more, see here:

http://arxiv.org/PS_cache/arxiv/pdf/0911/0911.3427v2.pdf

May 31st, 2010 at 10:40 amMight as well pull from multiple sources & try to increase the illusion of randomness.

function coinflip : Boolean;

Var

May 31st, 2010 at 10:48 amI : Int64;

Begin

If TStopwatch.IsHighResolution Then

Begin

QueryPerformanceCounter(I)

Result := Boolean(I And 1) XOR Boolean( GetTickCount And 1) XOR Random(2);

End

Else

Result := Boolean( GetTickCount And 1) XOR Random(2);

End;

Sorry, Xor Random(2) Should be XOR Boolean(Random(2))

May 31st, 2010 at 10:49 amInteresting that if you run something like:

Randomize;

x := 0;

for I := 0 to 100000000 do

if CoinFlip then

x := x + 1

else

x := x - 1;

showMessage(IntToStr(x));

You can end up with outputs of +/- 30,000 - I believe such distributions are correct, but it seems wrong to deviate so far from 0

May 31st, 2010 at 3:24 pmHere’s a fun question: If you were able to get a sequence of consecutive outputs from CoinFlip, how long would that sequence have to be before you were able to correctly predict the next output of CoinFlip?

May 31st, 2010 at 4:31 pmThe correct answer is on average 32 outputs. If CoinFlip is implemented in such way that it is indistinguishable from a true random generator up to the 32nd output (but still based on System.Random), you need exactly 32 outputs.

The proof is straight forward. RandSeed is a 32 bit integer, and Random uses an IMUL and an INC to advance it from one value to another. Let R0 be the set of RandSeed values that correspond to a CoinFlip = False and R1 be the set of RandSeed values that correspond to a CoinFlip = True, and give R00, R01, R10, R11, R000… etc corresponding definitions recursively. Clearly, if CoinFlip is unbiased there are exactly 2^31 elements in R0 and R1 each. If the second output is still unbiased, there are exactly 2^30 values in R00, R01, R10, R11 each, etc. When you get to the 32nd output there is only a single element left in the set, which can be found with a O(2^32) effort.

June 1st, 2010 at 12:28 amIn order to unbias the randomizer, Julian Bucknall recently posted a nice trick that I’ve got bookmarked ever since :

http://blog.boyet.com/blog/blog/unbiased-tosses-from-a-biased-coin/

Quote :

Use tosses in pairs. If the first toss of a pair comes up heads and the second tails, call the result of the pair heads. If the first comes up tails and the second heads, call it tails. If both tosses produce the same result (heads/heads or tails/tails), ignore that pair, and start over.

In mathematical terms, we assume that all the individual flips are independent. So if the probability of getting heads is p and the probability of getting tails is q, where p + q = 1, then the probability of heads followed by tails is exactly the same as the reverse result, namely pq. Since we ignore all other pairs of tosses, it means that the overall "coin pair toss" is unbiased. Note that the algorithm doesn’t require you to know what the probabilities are (though obviously if it’s a two-headed coin, you’ll never get any unbiased tosses!).

June 1st, 2010 at 2:35 amThe more time I spend investigating the quantum realm leads me to believe that bias is an unavoidable part of any experiement. Bias may well be a fundamental property of the universe itself, allowing existance itself.

June 1st, 2010 at 2:54 amhttp://xkcd.com/221/

I’ve finally managed to port this to Delphi!

function GetRandomNumber:Integer;

June 1st, 2010 at 4:51 pmbegin

Result := 4; // chosen by fair dice roll.

// guaranteed to be random.

end;

@Patrick van Logchem

June 7th, 2010 at 1:07 amThe problem is that the coin pair toss analogy only works for independent outcomes. You can’t assume Random=0.5 is exactly as probable as Random>=0.5 followed by Random<0.5, because you know for a fact that each Random output is a function of the prior. They are not independent.