views:

924

answers:

10

Right now i have

return 'Heads' if Math.random() < 0.5

Is there a better way to do this?

Thanks

edit: please ignore the return value and "better" means exact 50-50 probability.

A: 

Try

return 'Heads' if Math.random() * 100 mod 2 = 0

I don't really know what language you are using but if the random number is dividable by two then it is heads if it is not then it is tails.

Nick Berardi
This actually may not work. The left-most bits of some RNG's are more random than the right-most bits.
S.Lott
If you use such technique, make sure that random() is as random on the lower-order bits as it is on higher-order bits. See the notes on rand(3) linux.die.net/man/3/rand
Stephan202
this is why I used mod 2 because 98 is just as valid as 52 and just as valid as 02. Because then tend to favor certain numbers, or ranges of numbers, but if you use mod 2 you should get a pretty even break between even and odd.
Nick Berardi
The point is you may not get an even break between even and odd. The lowest-order bit may not be random.
S.Lott
All of this is based only on the randomness of the least-significant-bit, and reduces to more or less "give me a random number which is either 0 or 1". Everything else is almost superfluous.
sykora
S. Lott: That depends on the RNG. Some have low-quality low-order bits, some have low-quality high-order bits, some allow for use of all their bits. But a good PRNG in a language/framework shouldn't even return the weak bits to a program using it. See for example Java's Random class which uses an LCG (horrible generator by today's standards) but only uses 32 of its 48 bits.
Joey
+10  A: 

there's always the dead simple

coin = rand(1);

in many scripting languages this will give you a random int between 0 and your arg, so passing 1 gives you 0 or 1 (heads or tails).

jess
Does this guarentee that the proabability is 50%?
kunjaan
I don't think you can ever guarantee that.
ChristianLinnell
Tal Pressman said that I can get "an exact 50-50 chance". Is that false?
kunjaan
You can easily write such a function/method that returns a random number up to a specified integer that it won't introduce any further bias (see Java's java.util.Random.nextInt(int) for an example). The underlying (P)RNG has to have a uniform distribution but essentially all PRNGs in use, even the bad ones, satisfy this (we have come a long way since RANDU in this respect). And if the generator isn't uniform there is nothing you can do to get an exact 50 % chance from it so that always has to be an assumption.
Joey
A: 

Try differentiating between odd and even numbers. Also, return an enumeration value (or a boolean), rather than a string.

The Dissonant
+4  A: 

What you have is the way I would do it. If 0.0 <= Math.random() < 1.0, as is standard, then (Math.random() < 0.5) is going to give you heads when Math.random() is between 0.0 and 0.4999..., and tails when it's between 0.5 and 0.999... That's as fair a coin flip as you can get.

Of course I'm assuming a good implementation of Math.random().

Bill the Lizard
will <= make any difference?
kunjaan
Yes, <= would make a slight bias in favor of one side or the other (whichever you assign, in this case heads). 0.0 - 0.5 is a slightly larger range than 0.5000001 - 0.9999999.
Bill the Lizard
Remember inaccuracies when dealing with comparisons and floats.
strager
@strager: That's not an issue here. We're not comparing two computed values for equality. Either the random value will be less than 0.5 or it won't. (Hey! This is actually one situation where that 50/50 argument holds up! :) http://www.schneier.com/blog/archives/2009/05/mathematical_il.html)
Bill the Lizard
A: 

why don't you write a little method that loops over this a million or so times while keeping track of the heads\tails count? that should give you an idea of how well it works

joe90210
Well-meaning, and I dislike giving out -1s, but this is a bad idea. The probability of flipping 1,000,000 coins and getting exactly 500,000 heads is extremely small. The standard deviation of the # of coin flips in an ensemble of N unbiased coin flips total is sqrt(N/4). (See http://en.wikipedia.org/wiki/Bernoulli_distribution and properties of variance) You cannot, in general, test for small biases of random number generators empirically.
Jason S
+7  A: 

Numerical Recipes in C says not to trust the built in random number generators when it matters. You could probably implement the algorithm shown in the book as the function ran1(), which it claims passes all known statistical tests of randomness (in 1992) for less than around 108 calls.

The basic idea behind the ran1() algorithm is to add a shuffle to the output of the random number generator to reduce low order serial correlations. They use the Bays-Durham shuffle from section 3.2-3.3 in The Art of Computer Programming Volume 2, but I'd guess you could use the Fisher-Yates shuffle too.

If you need more random values than that, the same document also provides a generator (ran2) that should be good for at least 1017 values (my guess based on a period of 2.3 x 1018). The also provide a function (ran3) that uses a different method to generate random numbers, should linear congruential generators give you some sort of problem.

You can use any of these functions with your < 0.5 test to be more confident that you are getting a uniform distribution.

garethm
I hope that ran1 code isn't from Numerical Recipes, because the Numerical Recipes license (contained in the books and posted on the nrbook.com website) specifically forbids redistribution of any of their source code: http://www.nr.com/licenses/redistribute.html
las3rjock
Good lord, I never saw that before. A book full of code people aren't allowed to use in open source projects... wow.
fenomas
Yes indeed. I have removed my translation. If you need souped up random number generation, you'll need to buy a copy of their book and do the translation yourself.
garethm
The license thing bit us too here. But implementing ran1 or so from there shouldn't be necessary. Heck, for a simple coin flip an LCG suffices and therefore the built-in generator too. Python for example uses the Mersenne Twister which should be good even for simulation uses so the advice from NR isn't entirely correct anymore :)
Joey
that's OK, NR code has occasional bugs (they do have errata thankfully) and is horribly written from a code-style viewpoint (1- and 2-letter variable names). Numerical correctness, which they do well, is only one piece of the puzzle. :/
Jason S
A: 

I can't comment on people's posts because I don't have the reputation, but just an FYI about the whole <= vs. < topic addressed in Bill The Lizard's comment: Because it can be effectively assumed that random is generating any number between 0-1 (which isn't technically the case due to limitations on the size of a floating point number, but is more or less true in practice) there won't be a difference in num <= .5 or num < .5 because the probability of getting any one particular number in any continuous range is 0. IE: P(X=.5) = 0 when X = a random variable between 0 and 1.

David Cooper
Ah, for floating point numbers you're wrong, as .5 is a value that can be exactly represented. So <.5 will have one value less than <=.5 which will yield true. Mathematically you're correct, though, but for floating-point using <=.5 will introduce a bias of around 2^-24 or 2^-53, depending on whether you use single or double :)
Joey
.5 can be exactly represented, and as I stated, I worked under the assumption that the number of values that the computer can represent between 0 and 1 is infinite, in which case the probability of getting any discrete number is 0. I know the assumption isn't technically true due to the limitations of IEEE and only being able to represent numbers down to about 1^-36 or so, but unless you are running hundreds of millions of trials, it's a pretty fair assumption, right?
David Cooper
+5  A: 

a wee homage to xkcd:

string getHeadsOrTails {
        return "heads"; //chosen by fair coin toss,
                        //guaranteed to be random
    }
Bayard Randel
+2  A: 

On a linux system you could read bits in from /dev/random to get "better" random data, but an almost random method like Math.Random() is going to be fine for almost every application you can think of, short of serious cryptography work.

DrStalker
/dev/random will block if you exhaust the entropy pool. Furthermore it is intended as a very low-yield source of unguessable random data (for seeding a cryptographically secure PRNG or generating keys), not as a general-purpose source of random data. Also you can't guarantee a 50 % chance there as generating entirely unbiased entropy is really hard and probably impossible.
Joey
If blocking will be an issue there's always /dev/urandom... but I don't think that offers any advantage over Math.Random().
DrStalker
it's cryptographically secure. But if you want something with crypto you probably don't ponder about coins :)
Joey
/dev/random (or urandom) might be better than time() for seeding the PRNG. But use of /dev/random does extract some entropy from the pool which might be more valuable for use by real crypto applications.
RBerteig
A: 

The only real answer to this question is that you cannot "guarantee" probability. If you think about it, a real coin flip is not guaranteed 50/50 probability, it depends on the coin, the person flipping it, and if the coin is dropped and rolls across the floor. ;)

The point is that it's "random enough". If you're simulating a coin flip then the code you posted is more than fine.

DisgruntledGoat