@gene: can u give the function for unfair_coin_toss so that i can understand what u are doing in fair_coin_toss
On Mar 19, 9:54 am, Gene <[email protected]> wrote: > 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.
