Nick Hodges

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.

19 Responses to “Coin Flip”

  1. 1
    Does the Cisco Flip UltraHD camcorder have time-lapse? | 2Studio.net Says:

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

  2. 2
    Does the Cisco Flip UltraHD camcorder have time-lapse? | 2Studio.net Says:

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

  3. 3
    Rob McDonell Says:

    Shouldn’t that be ">=" instead of ">" ?

  4. 4
    Stephane Wierzbicki Says:

    2 points :
    - Randomize is missing
    - there is a lot of chance that the randomized number will be greater than 0.5

  5. 5
    Ken Bourassa Says:

    @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)

  6. 6
    Patrick vd Pieterman Says:

    A better way of doing a coinflip is :

    Result := Random > Random;

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

  7. 7
    Pratt Says:

    I’m guessing this function was used to determine what next Delphi version targets first, Win64 or x-platform.

  8. 8
    Uwe Raabe Says:

    Must have been a previous version:

    {code}
    function Make64BitCompiler: Boolean;
    begin
    Result := Random > 32;
    end;
    {code}

  9. 9
    Stefan Glienke Says:

    My suggestion:

    function CoinFlip: Boolean;
    begin
    Result := Boolean(Random(2));
    end;

  10. 10
    Maël Hörz Says:

    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

  11. 11
    Xepol Says:

    Might as well pull from multiple sources & try to increase the illusion of randomness.

    function coinflip : Boolean;

    Var
    I : 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;

  12. 12
    Xepol Says:

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

  13. 13
    Alister Christie Says:

    Interesting 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

  14. 14
    Henrick Says:

    Here’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?

  15. 15
    Henrick Says:

    The 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.

  16. 16
    Patrick van Logchem Says:

    In 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!).

  17. 17
    Xepol Says:

    The 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.

  18. 18
    Wouter Says:

    http://xkcd.com/221/

    I’ve finally managed to port this to Delphi!

    function GetRandomNumber:Integer;
    begin
    Result := 4; // chosen by fair dice roll.
    // guaranteed to be random.
    end;

  19. 19
    Henrick Says:

    @Patrick van Logchem
    The 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.

© 2014 Nick Hodges | Entries (RSS) and Comments (RSS)

Your Index Web Directorywordpress logo
Close