How to resolve the algorithm Unbias a random generator step by step in the Racket programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Unbias a random generator step by step in the Racket programming language
Table of Contents
Problem Statement
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.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Unbias a random generator step by step in the Racket programming language
Source code in the racket programming language
#lang racket
;; Using boolean #t/#f instead of 1/0
(define ((randN n)) (zero? (random n)))
(define ((unbiased biased))
(let loop () (let ([r (biased)]) (if (eq? r (biased)) (loop) r))))
;; Counts
(define N 1000000)
(for ([n (in-range 3 7)])
(define (try% R) (round (/ (for/sum ([i N]) (if (R) 1 0)) N 1/100)))
(define biased (randN n))
(printf "Count: ~a => Biased: ~a%; Unbiased: ~a%.\n"
n (try% biased) (try% (unbiased biased))))
You may also check:How to resolve the algorithm Unbias a random generator step by step in the Go programming language
You may also check:How to resolve the algorithm Happy numbers step by step in the F# programming language
You may also check:How to resolve the algorithm McNuggets problem step by step in the MACRO-11 programming language
You may also check:How to resolve the algorithm Simple database step by step in the Erlang programming language
You may also check:How to resolve the algorithm Empty program step by step in the Sparkling programming language