0
$\begingroup$

What might happen if when using a random number generator, if a particular run is not so random, you "help it out" a little bit? For example, if we use a random number generator to simulate $10,000$ fair coin tosses. Normally we wont get $5,000$ of each possible outcome so there are actually $2$ related questions here:

1) When is the "best" time to force it to "even steven", towards the end of the run or when one outcome strays a set amount away from the other (but with a minimum percentage of flips so we are not correcting super early on like after the 1st, 2nd, 3rd flips.... For example, we can say that maybe after $10$% of the target # of flips (in this case that would be $1000$ flips), perhaps if either heads or tails is more than $510$ ($51$%), we would then force a few more of the other outcome to help balance it out.

2) What might this "correction" do to the "randomness"? Might it introduce some other bias? I assume any bias would be closely related to how and when the correction is made. For example, if we wait until the very end to correct for too may tails, we will artificially introduce a long string of heads so is there any algorithm to do something like this fairly?

You can assume the reason for asking this is I already have a program written that uses the random number generator and I want to instead force it to be $5000$ of each outcome so I am wondering when and how to do that. It is much simpler to just force this than to rewrite the code to solve a problem some other way.

Also I suspect someone will answer something like "just do $100,000$ or even $1,000,000$ coin flips and then you wont have to "help it out". My concern about that is these $10,000$ random numbers are being used in a path walking program which gets slow when more than about $10,000$ flips are used.

$\endgroup$
1
$\begingroup$

Suppose you are aiming to do $2n$ tosses ending up with $n$ heads and $n$ tails, and so far you have seen $h$ heads and $t$ tails

Then the probability that the next toss is heads should be $\dfrac{n-h}{2n-h-t}$ and you can write your program to simulate this

This is make all the ${ 2n \choose n}$ possible patterns of heads and tails equally likely, avoiding some of the issues you discuss

$\endgroup$
  • $\begingroup$ So what would be a reasonable algorithm to "fix" this? I am seeing about $5050$ of one and $4950$ of the other on average (a rough average). Should I check every $1000$ flips and do the correction then, thus having $10$ corrections for $10,000$ flips? $\endgroup$ – David May 14 '16 at 12:14
  • 1
    $\begingroup$ I would apply the algorithm at every step: start with $h=0$ and $t=0$; if your pseudo-random number generator gives some value $X$ in $[0,1)$ at each step, call it heads when $X \lt \frac {n-h}{2n-h-t}$ and add $1$ to $h$, and call it tails otherwise and add $1$ to $t$; then repeat; stop when $h+t=2n$. $\endgroup$ – Henry May 14 '16 at 12:19
  • $\begingroup$ Ok I used a variation of your correction algorithm. I check every $1$% of the flips and do the correction there. Also when I get at or past $99.7$% of the flips, I check every flip and correct so heads and tails are evenly occurring. This way, for $10,000$ flips, I seem to always get $5,000$ of each. I didn't want to do the correction at each step cuz then it seems it will just go back and forth H,T,H,T... and that is not random. With my algorithm, I give it some leeway to do things like runs of heads or tails and then just correct every $1$% of the rolls to get it back on track. $\endgroup$ – David May 14 '16 at 13:21
  • $\begingroup$ Here is something interesting. For my $10,000$ random flips, I put a counter in my program to check how many times a manual adjustment of H or T is done and it is surprisingly high (to me). It happens about $774$ times on average for $10,000$ coin flips and that is only checking after each $100$ coin flips and at each flip at or after $9970$. Each manual addition of a H or T counts as $1$ adjustment. So what I am saying is about $774$ of the coin flips (out of $10,000$) on average are not really random, they are a "manual correction". $\endgroup$ – David May 14 '16 at 13:23
  • $\begingroup$ There very likely exists a better "correction algorithm" than my simple one cuz imagine a block of $100$ random numbers having an exceptionally high number of heads such as $70$. What will happen after that block is my program will insert $20$ tails into the pattern and then take away $20$ what would have been random numbers from the next block. This will likely no cause problems for someone that just needs an identical # of heads and tails but WILL cause problems for someone doing other types of random checks like runs of Hs and Ts. The artificial run will likely skew those results. $\endgroup$ – David May 14 '16 at 13:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.