On Saturday, March 19, 2011 6:07:44 AM UTC-4, cegprakash wrote: > > @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 <gene.r...@gmail.com> wrote: > > On Friday, March 18, 2011 1:47:45 PM UTC-4, Gene wrote: > > > > > On Mar 17, 10:24 am, saurabh agrawal <saur...@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
I'm not sure what you're asking I gave unfair-coin-toss above. It's just a function that returns 1 with probability 60% and zero otherwise, just as the OP gave in the problem. Here's the code one more time: (defun unfair-coin-toss () (if (< (random 1.0) 0.6) 1 0)) Maybe you don't know lisp. In C this would be something roughly like: int unfair_coin_toss() { return rand() < (int)(0.6 * RAND_MAX) ? 1 : 0; } Then I defined fair-coin-toss to return 1 with probability 50% by calling unfair-coin-toss. It uses the binomial distribution and rejection as I explained above. Then I tested the lisp code and find it seems to work. What additional question do you have? -- 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.