Unbias a random generator: Difference between revisions
m (Use more math!) |
(→Tcl: Added implementation) |
||
Line 52: | Line 52: | ||
Biased(6) = Stats(count1=167561, count0=832439, percent=16.7561) |
Biased(6) = Stats(count1=167561, count0=832439, percent=16.7561) |
||
Unbiased = Stats(count1=499963, count0=500037, percent=49.996299999999998)</pre> |
Unbiased = Stats(count1=499963, count0=500037, percent=49.996299999999998)</pre> |
||
=={{header|Tcl}}== |
|||
<lang tcl># 1,0 random generator factory with 1 appearing 1/N'th of the time |
|||
proc randN n {expr {rand()*$n < 1}} |
|||
# uses a biased generator of 1 or 0, to create an unbiased one |
|||
proc unbiased {biased} { |
|||
while 1 { |
|||
if {[set a [eval $biased]] != [eval $biased]} {return $a} |
|||
} |
|||
} |
|||
for {set n 3} {$n <= 6} {incr n} { |
|||
set biased [list randN $n] |
|||
for {set i 0;array set c {0 0 1 0}} {$i < 1000000} {incr i} { |
|||
incr c([eval $biased]) |
|||
} |
|||
puts [format " biased %d => #0=%d #1=%d ratio=%.2f%%" $n $c(0) $c(1) \ |
|||
[expr {100.*$c(1)/$i}]] |
|||
for {set i 0;array set c {0 0 1 0}} {$i < 1000000} {incr i} { |
|||
incr c([unbiased $biased]) |
|||
} |
|||
puts [format "unbiased %d => #0=%d #1=%d ratio=%.2f%%" $n $c(0) $c(1) \ |
|||
[expr {100.*$c(1)/$i}]] |
|||
}</lang> |
|||
Sample output: |
|||
<pre> |
|||
biased 3 => #0=667076 #1=332924 ratio=33.29% |
|||
unbiased 3 => #0=500263 #1=499737 ratio=49.97% |
|||
biased 4 => #0=750470 #1=249530 ratio=24.95% |
|||
unbiased 4 => #0=500644 #1=499356 ratio=49.94% |
|||
biased 5 => #0=800243 #1=199757 ratio=19.98% |
|||
unbiased 5 => #0=500878 #1=499122 ratio=49.91% |
|||
biased 6 => #0=833623 #1=166377 ratio=16.64% |
|||
unbiased 6 => #0=500518 #1=499482 ratio=49.95% |
|||
</pre> |
Revision as of 13:24, 22 February 2011
Given a weighted one bit generator of random numbers where the probability of a one occuring, , is not the same as , the probability of a zero occuring. The probability of the occurrence of a one followed by a zero is , which is the same as the probability of a zero followed by a one: .
Task Details
- Use your languages 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).
Python
<lang python>from __future__ import print_function import random
def randN(N):
" 1,0 random generator factory with 1 appearing 1/N'th of the time" choose = [1] + [0] * (N-1) def rand(): return random.choice( rand.choose ) rand.choose = choose return rand
def unbiased(biased):
'uses a biased() generator of 1 or 0, to create an unbiased one' this, that = biased(), biased() while this == that: # Loop until 10 or 01 this, that = biased(), biased() return this # return the first
if __name__ == '__main__':
from collections import namedtuple
Stats = namedtuple('Stats', 'count1 count0 percent')
for N in range(3, 7): biased = randN(N) v = [biased() for x in range(1000000)] v1, v0 = v.count(1), v.count(0) print ( "Biased(%i) = %r" % (N, Stats(v1, v0, 100. * v1/(v1 + v0))) )
v = [unbiased(biased) for x in range(1000000)] v1, v0 = v.count(1), v.count(0) print ( " Unbiased = %r" % (Stats(v1, v0, 100. * v1/(v1 + v0)), ) )</lang>
Sample output
Biased(3) = Stats(count1=331800, count0=668200, percent=33.18) Unbiased = Stats(count1=499740, count0=500260, percent=49.973999999999997) Biased(4) = Stats(count1=249770, count0=750230, percent=24.977) Unbiased = Stats(count1=499707, count0=500293, percent=49.970700000000001) Biased(5) = Stats(count1=199764, count0=800236, percent=19.976400000000002) Unbiased = Stats(count1=499456, count0=500544, percent=49.945599999999999) Biased(6) = Stats(count1=167561, count0=832439, percent=16.7561) Unbiased = Stats(count1=499963, count0=500037, percent=49.996299999999998)
Tcl
<lang tcl># 1,0 random generator factory with 1 appearing 1/N'th of the time proc randN n {expr {rand()*$n < 1}}
- uses a biased generator of 1 or 0, to create an unbiased one
proc unbiased {biased} {
while 1 {
if {[set a [eval $biased]] != [eval $biased]} {return $a}
}
}
for {set n 3} {$n <= 6} {incr n} {
set biased [list randN $n] for {set i 0;array set c {0 0 1 0}} {$i < 1000000} {incr i} {
incr c([eval $biased])
} puts [format " biased %d => #0=%d #1=%d ratio=%.2f%%" $n $c(0) $c(1) \
[expr {100.*$c(1)/$i}]]
for {set i 0;array set c {0 0 1 0}} {$i < 1000000} {incr i} {
incr c([unbiased $biased])
} puts [format "unbiased %d => #0=%d #1=%d ratio=%.2f%%" $n $c(0) $c(1) \
[expr {100.*$c(1)/$i}]] }</lang> Sample output:
biased 3 => #0=667076 #1=332924 ratio=33.29% unbiased 3 => #0=500263 #1=499737 ratio=49.97% biased 4 => #0=750470 #1=249530 ratio=24.95% unbiased 4 => #0=500644 #1=499356 ratio=49.94% biased 5 => #0=800243 #1=199757 ratio=19.98% unbiased 5 => #0=500878 #1=499122 ratio=49.91% biased 6 => #0=833623 #1=166377 ratio=16.64% unbiased 6 => #0=500518 #1=499482 ratio=49.95%