Author |
Topic: F1 F2 (Read 1214 times) |
|
ic10503
Junior Member
Gender: 
Posts: 57
|
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.
|
|
 IP Logged |
|
|
|
SMQ
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 2084
|
 |
Re: F1 F2
« Reply #1 on: Aug 19th, 2008, 11:21am » |
 Quote  Modify
|
I believe this is a well-known result:
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;
}
--SMQ
|
|
IP Logged |
--SMQ
|
|
|
kaka
Newbie
Gender:
Posts: 24
|
|
Re: F1 F2
« Reply #2 on: Apr 5th, 2010, 10:31pm » |
Quote Modify
|
sorry to pull out an old topic. Someone plz explain this. could not get the logic 
|
|
IP Logged |
|
|
|
malchar
Junior Member
Gender:
Posts: 54
|
|
Re: F1 F2
« Reply #3 on: Apr 6th, 2010, 12:12am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: F1 F2
« Reply #4 on: Jul 27th, 2010, 6:08am » |
Quote Modify
|
on Apr 5th, 2010, 10:31pm, 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
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: F1 F2
« Reply #5 on: Jul 27th, 2010, 6:21am » |
Quote Modify
|
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.
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: F1 F2
« Reply #6 on: Jul 27th, 2010, 6:38am » |
Quote Modify
|
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
|
| « Last Edit: Jul 27th, 2010, 6:56am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: F1 F2
« Reply #7 on: Jul 27th, 2010, 7:33am » |
Quote Modify
|
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));
}
} |
|
|
| « Last Edit: Jul 27th, 2010, 7:38am by towr » |
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: F1 F2
« Reply #8 on: Jul 28th, 2010, 8:46am » |
Quote Modify
|
If fp() returns 1 with probability p,
you can implement fq() as:
fq() =
- if q=p then return fp()
- if q<p and fp()=0 then return 0 else return fq/p()
- if q>p and fp()=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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print