Unbias a random generator: Difference between revisions
Content added Content deleted
(Added PicoLisp) |
(Clarify how to unbias using mathematical properties, rm draft status (no problems for a long time)) |
||
Line 1: | Line 1: | ||
⚫ | {{task}}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 \times P_0</math>. This is the same as the probability of a zero followed by a one: <math>P_0 \times P_1</math>. |
||
{{draft task}} |
|||
⚫ | |||
The probability of the occurrence of a one followed by a zero is <math>P_1 \times P_0</math>, which is the same as the probability of a zero followed by a one: <math>P_0 \times P_1</math>. |
|||
'''Task Details''' |
'''Task Details''' |
||
* Use your |
* 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. |
* 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). |
* For N over its range, generate and show counts of the outputs of randN and unbiased(randN). |
||
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. |
|||
=={{header|J}}== |
=={{header|J}}== |
||