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:

(defun biased (n) (if (zerop (random n)) 0 1))

(defun unbiased (n)
    (loop with x do
      (if (/= (setf x (biased n)) (biased n))
	    (return x))))

(loop for n from 3 to 6 do
      (let ((u (loop repeat 10000 collect (unbiased n)))
	    (b (loop repeat 10000 collect (biased n))))
	(format t "~a: unbiased ~d biased ~d~%" n (count 0 u) (count 0 b))))