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 <[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
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 [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.
