On Friday, March 18, 2011 1:47:45 PM UTC-4, Gene wrote:
>
> On Mar 17, 10:24 am, saurabh agrawal <[email protected]> wrote:
> > Given a function which returns true 60% time and false 40% time.
> >
> > Using this function you have to write a function which returns true 50%
> of
> > the time.
>
> If we call the function N times, then the probability that we'll have
> K true values returned is binomially distributed: B(N, K; 0.6).
>
> So we can get exactly 50% with N=4. Here we have B(4, 2; 0.6) = B(4,
> 3; 0.6) = 216/625. So after 4 calls, if we have 2 trues, return true;
> if we have 3 trues, return false; otherwise try again with 4 new
> calls:
>
> int fair_coin_toss()
> {
> int i, n;
> while (1) {
> for (i = n = 0; i < 4; i++) n += unfair_coin_toss();
> if (n == 2) return 1;
> if (n == 3) return 0;
> }
> }
>
> The down side of the approach is that we are going to waste 1 -
> 2(216/625) = 193/625 = ~1/3 of the calls.
>
Sorry I could not resist coding this up.
(defun unfair-coin-toss ()
(if (< (random 1.0) 0.6) 1 0))
(defun fair-coin-toss ()
(loop (let ((n 0))
(dotimes (i 4)
(incf n (unfair-coin-toss)))
(case n
(2 (return-from fair-coin-toss 1))
(3 (return-from fair-coin-toss 0))))))
;;; Try counting 1's returned by a million calls. Should be around 500,000:
CL-USER> (let ((n 0)) (dotimes (i 1000000 n) (incf n (fair-coin-toss))))
499372
CL-USER> (let ((n 0)) (dotimes (i 1000000 n) (incf n (fair-coin-toss))))
499713
CL-USER> (let ((n 0)) (dotimes (i 1000000 n) (incf n (fair-coin-toss))))
500248
CL-USER> (let ((n 0)) (dotimes (i 1000000 n) (incf n (fair-coin-toss))))
500209
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
