On Friday, March 18, 2011 1:47:45 PM UTC-4, Gene wrote: > > On Mar 17, 10:24 am, saurabh agrawal <saura...@gmail.com> 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 algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.