wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> cs >> F1 F2
        
(Message started by: ic10503 on Aug 19^th, 2008, 11:13am)

Title: F1 F2
Post by ic10503 on Aug 19^th, 2008, 11:13am

Given a function F1( ) that returns 0 with 60% probability and 1 with 40% probability.
Now write a function F2( ) that uses F1 and returns 0 and 1 with equal probability (50-50). You cannot use any other function.

Title: Re: F1 F2
Post by SMQ on Aug 19^th, 2008, 11:21am

I believe this is a well-known result:

[hide]Call F1 twice; if you get the same value both times, try again, otherwise return the first (or second) one.

int F2() { int a = F1(); while (a == F1()) a = F1(); return a; }[/hide]
--SMQ

Title: Re: F1 F2
Post by kaka189 on Apr 5^th, 2010, 10:31pm

sorry to pull out an old topic. Someone plz explain this. could not get the logic :(

Title: Re: F1 F2
Post by malchar on Apr 6^th, 2010, 12:12am

Basically, if you use F1 until you get two different results in a row, there's a 50% chance that you got outcome A before the other outcome B, and a 50% chance that B came before A. This works independently of the probability of A or B alone in F1.

Title: Re: F1 F2
Post by birbal on Jul 27^th, 2010, 6:08am

on 04/05/10 at 22:31:42, kaka189 wrote:

sorry to pull out an old topic. Someone plz explain this. could not get the logic :(

An easy way to explain this is :
the possible combinations are
( 0 , 0 ) - which can occur with prob of 0.36
( 1 , 1 ) - which can occur with prob of 0.16
( 1 , 0 ) - which can occur with prob of 0.24
( 1 , 1 ) - which can occur with prob of 0.24

So if i see (1,0) , i return 0
if i see (0,1) , i return 1

Title: Re: F1 F2
Post by birbal on Jul 27^th, 2010, 6:21am

Here F2() is using 48% of the numbers generated by F1(), and just throwing away the rest. Is it possible to somehow use those numbers also ??
for example one possible way can be
if we get
( 0 , 0 ) then (1 , 1), output 1
( 1 , 1 ) then (0 , 0), output 0
here we are using 2*36*0.24 % more numbers.

Title: Re: F1 F2
Post by towr on Jul 27^th, 2010, 6:38am

You can use a lot more of the random numbers, I think there's another thread about it.. But in any case, the scheme isn't too difficult.

01 -> 1
10 -> 0

0001 -> 1
0010 -> 0
1101 -> 1
1110 -> 0

0011 -> 1
1100 -> 0

000001 -> 1
000010 -> 0
111101 -> 1
111110 -> 0

00000001 -> 1
00000010 -> 0
00001101 -> 1
00001110 -> 0
11110001 -> 1
11110010 -> 0
11111101 -> 1
11111110 -> 0

00000011 -> 1
00001100 -> 0
11110011 -> 1
11111100 -> 0

00001111 -> 1
11110000 -> 0

etc

Title: Re: F1 F2
Post by towr on Jul 27^th, 2010, 7:33am

I think the following code should work to achieve this; although there may be better ways (and in any case, it wouldn't be much faster anyway).

pseudo
Code:

int F2()
{
stack st;

while(true)
{
double a = F1();
double b = F1();
if (a != b) return b;

int c = 2;
while(!st.isempty() && st.top()->first==c)
{
if (st.top()->second != b)
return b;
else
{
st.pop();
c*=2;
}
}
st.push(pair(c,b));
}
}

Title: Re: F1 F2
Post by Grimbal on Jul 28^th, 2010, 8:46am

If f_p() returns 1 with probability p,
you can implement f_q() as:
f_q() =
- if q=p then return f_p()
- if q<p and f_p()=0 then return 0 else return f_q/p()
- if q>p and f_p()=1 then return 1 else return f_(q-p)/(1-p)()

So after optimizing tail recursion, you can write:
double F2()
{
double p = 0.6, q = 0.5
while( 1 ){
if( q==p ) return F1();
if( q<p ){
if( F1()==0 ) return 0; else q = q/p;
} else {
if( F1()==1 ) return 1; else q = (q-p)/(1-p);
}
}
}

And there are optimizations possible.