




P

1




{\displaystyle P_{1}}







P

0




{\displaystyle P_{0}}







P

1




{\displaystyle P_{1}}







P

0




{\displaystyle P_{0}}







P

0




{\displaystyle P_{0}}







P

1




{\displaystyle P_{1}}




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


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 Von Neumann debiasing, first described in a 1951 paper.




using System;
 
namespace Unbias
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            // Demonstrate.
            for (int n = 3; n <= 6; n++)
            {
                int biasedZero = 0, biasedOne = 0, unbiasedZero = 0, unbiasedOne = 0;
                for (int i = 0; i < 100000; i++)
                {
                    if (randN(n))
                        biasedOne++;
                    else
                        biasedZero++;
                    if (Unbiased(n))
                        unbiasedOne++;
                    else
                        unbiasedZero++;
                }
 
                Console.WriteLine("(N = {0}):".PadRight(17) + "# of 0\t# of 1\t% of 0\t% of 1", n);
                Console.WriteLine("Biased:".PadRight(15) + "{0}\t{1}\t{2}\t{3}",
                                  biasedZero, biasedOne,
                                  biasedZero/1000, biasedOne/1000);
                Console.WriteLine("Unbiased:".PadRight(15) + "{0}\t{1}\t{2}\t{3}",
                                  unbiasedZero, unbiasedOne,
                                  unbiasedZero/1000, unbiasedOne/1000);
            }
        }
 
        private static bool Unbiased(int n)
        {
            bool flip1, flip2;
 
            /* Flip twice, and check if the values are the same.
             * If so, flip again. Otherwise, return the value of the first flip. */
 
            do
            {
                flip1 = randN(n);
                flip2 = randN(n);
            } while (flip1 == flip2);
 
            return flip1;
        }
 
        private static readonly Random random = new Random();
 
        private static bool randN(int n)
        {
            // Has an 1/n chance of returning 1. Otherwise it returns 0.
            return random.Next(0, n) == 0;
        }
    }
}