13 lines
1.3 KiB
Text
13 lines
1.3 KiB
Text
Given a weighted one bit generator of random numbers where the probability of a one occuring, <math>P_1</math>, is not the same as <math>P_0</math>, the probability of a zero occuring, the probability of the occurrence of a one followed by a zero is <math>P_1</math> × <math>P_0</math>. This is the same as the probability of a zero followed by a one: <math>P_0</math> × <math>P_1</math>.
|
||
|
||
|
||
;Task details:
|
||
* Use your language's random number generator to create a function/method/subroutine/... '''randN''' that returns a one or a zero, but with one occurring, on average, 1 out of N times, where N is an integer from the range 3 to 6 inclusive.
|
||
* Create a function '''unbiased''' that uses only randN as its source of randomness to become an unbiased generator of random ones and zeroes.
|
||
* For N over its range, generate and show counts of the outputs of randN and unbiased(randN).
|
||
|
||
<br>
|
||
The actual unbiasing should be done by generating two numbers at a time from randN and only returning a 1 or 0 if they are different. As long as you always return the first number or always return the second number, the probabilities discussed above should take over the biased probability of randN.
|
||
|
||
This task is an implementation of [http://en.wikipedia.org/wiki/Randomness_extractor#Von_Neumann_extractor Von Neumann debiasing], first described in a 1951 paper.
|
||
<br><br>
|