




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.




Module Module1
    Dim random As New Random()
 
    Function RandN(n As Integer) As Boolean
        Return random.Next(0, n) = 0
    End Function
 
    Function Unbiased(n As Integer) As Boolean
        Dim flip1 As Boolean
        Dim flip2 As Boolean
 
        Do
            flip1 = RandN(n)
            flip2 = RandN(n)
        Loop While flip1 = flip2
 
        Return flip1
    End Function
 
    Sub Main()
        For n = 3 To 6
            Dim biasedZero = 0
            Dim biasedOne = 0
            Dim unbiasedZero = 0
            Dim unbiasedOne = 0
            For i = 1 To 100000
                If RandN(n) Then
                    biasedOne += 1
                Else
                    biasedZero += 1
                End If
                If Unbiased(n) Then
                    unbiasedOne += 1
                Else
                    unbiasedZero += 1
                End If
            Next
 
            Console.WriteLine("(N = {0}):".PadRight(17) + "# of 0" + vbTab + "# of 1" + vbTab + "% of 0" + vbTab + "% of 1", n)
            Console.WriteLine("(Biased: {0}):".PadRight(15) + "{0}" + vbTab + "{1}" + vbTab + "{2}" + vbTab + "{3}", biasedZero, biasedOne, biasedZero / 1000, biasedOne / 1000)
            Console.WriteLine("(UnBiased: {0}):".PadRight(15) + "{0}" + vbTab + "{1}" + vbTab + "{2}" + vbTab + "{3}", unbiasedZero, unbiasedOne, unbiasedZero / 1000, unbiasedOne / 1000)
        Next
    End Sub
 
End Module