wu :: forums
« wu :: forums - Biasing a fair coin »
Welcome, Guest. Please Login or Register.
Nov 21st, 2024, 1:36am

RIDDLES SITE WRITE MATH! Home Home Help Help Search Search Members Members Login Login Register Register
   wu :: forums
   riddles
   cs (Moderators: ThudnBlunder, Eigenray, towr, Grimbal, william wu, SMQ, Icarus)
   Biasing a fair coin		 « Previous topic | Next topic »
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print
   Author  Topic: Biasing a fair coin  (Read 10719 times)
birbal
Full Member
***





   


Gender: male
 Posts: 250
Biasing a fair coin  
« on: Apr 13th, 2011, 12:13pm »		 Quote Quote Modify Modify
Given a function for a fair coin, write a function for a biased coin that returns heads 1/n times (n is a param).
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: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #1 on: Apr 13th, 2011, 1:16pm »		 Quote Quote Modify Modify
Create a random number by concatenating random bits; ri = 1 if ith throw is tails, 0 otherwise..  
If SUMi=1..m ri/2i >= 1/n return tails, if 1/2m + SUMi=1..m ri/2i <= 1/n return heads, and otherwise throw the coin to determine rm+1
« Last Edit: Apr 13th, 2011, 1:23pm by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member
***





   


Gender: male
 Posts: 250
Re: Biasing a fair coin  
« Reply #2 on: Apr 13th, 2011, 10:48pm »		 Quote Quote Modify Modify
I was thinking a bit different solution. flip the coin k times ( where k is the minimum number of bits required to represent n in binary form). if ith flip is head, make ith bit 1, 0 otherwise. Let the new number formed is x, then
if(x == n-1)
     return head;
if(x >= n)
     repeat the process;
return tail;
 
IP Logged
The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Biasing a fair coin  
« Reply #3 on: Apr 14th, 2011, 7:43am »		 Quote Quote Modify Modify
Here is a solution I believe is equivalent to towr's solution, but more computer-friendly.
 
// return true with probability 1/n
boolean flip(int n)
{
 // random is random in range 0..(range-1)
 int random=0, range=1;
 while( true ){
   while( range<n ){
     random = random*2 + fairFlip()?1:0;
     range *= 2;
   }
   if( random<n ){
     return random==0;
   } else {
     random -= n;
     range -= n;
   }
 }
}
« Last Edit: Apr 14th, 2011, 7:45am by Grimbal » IP Logged
birbal
Full Member
***





   


Gender: male
 Posts: 250
Re: Biasing a fair coin  
« Reply #4 on: Apr 14th, 2011, 9:05am »		 Quote Quote Modify Modify
@Grimbal - Its almost same as mine solution except for the part that when random >= n, i was discarding and generating random again. Cheesy
IP Logged
The only thing we have to fear is fear itself!
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Biasing a fair coin  
« Reply #5 on: Apr 14th, 2011, 9:34am »		 Quote Quote Modify Modify
Yes.  It is just a bit more stingy with fair flips.
 
I wonder:  If you do:
while( true ){
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
}
 
you get a 'H' with probability 1/3.  Is there a way to extend that to any 1/n?  (i.e. design a sequence of flips that you repeat and gives the wanted probability to get H)?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #6 on: Apr 14th, 2011, 11:45am »		 Quote Quote Modify Modify
Probably
Let's see; 0.101010101010 = 2/3
How about just taking the binary expansion of the fraction?
 
12/13 = 0.111011000100
How does:
while( true ){
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
}  
look for 1/13 chance of H?
 
(Actually, we could just invert it; same diff.)
« Last Edit: Apr 14th, 2011, 11:47am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: Biasing a fair coin  
« Reply #7 on: Dec 29th, 2011, 11:04am »		 Quote Quote Modify Modify
on Apr 14th, 2011, 7:43am, Grimbal wrote:
Here is a solution I believe is equivalent to towr's solution, but more computer-friendly.
 
// return true with probability 1/n
boolean flip(int n)
{
 // random is random in range 0..(range-1)
 int random=0, range=1;
 while( true ){
   while( range<n ){
     random = random*2 + fairFlip()?1:0;
     range *= 2;
   }
   if( random<n ){
     return random==0;
   } else {
     random -= n;
     range -= n;
   }
 }
}

 
if random is not < n the first time, then this code will return false. I don't see random going back to 0 again.
am I missing somthing?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #8 on: Dec 29th, 2011, 12:47pm »		 Quote Quote Modify Modify
Random returns to 0 whenever random=n
 
For example take n=3, and the first two times fairFlip() return 1, then random=3 at the if statement, 3 get's subtracted. Then if the next round the first two times fairFlip() returns zero, then we get at the if statement with random=0 and return true.
In general for n=3 we have (11)*00=>true, and (11)*01=>false and (11)*10=>false
IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
birbal
Full Member
***





   


Gender: male
 Posts: 250
Re: Biasing a fair coin  
« Reply #9 on: Dec 29th, 2011, 11:36pm »		 Quote Quote Modify Modify
on Apr 14th, 2011, 11:45am, towr wrote:
Probably
Let's see; 0.101010101010 = 2/3
How about just taking the binary expansion of the fraction?
 
12/13 = 0.111011000100
How does:
while( true ){
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
    if( fairFlip() ) return 'H';
}  
look for 1/13 chance of H?
 
(Actually, we could just invert it; same diff.)

Will  it work for the non recurring fractions ?
for example, if i want 'H' with 1/8 probability then function should be  
1/8 = 0.001
while( true ){
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'T';
    if( fairFlip() ) return 'H';
}
But here, probability of 'H' is 1/7 as a sequence of 000 would mean repeat in this case. Am i missing something ?
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: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #10 on: Dec 30th, 2011, 8:46am »		 Quote Quote Modify Modify
There's always a repeating part for a fraction for 1/8 you have repeating 0s after 0.001 (in binary).  The repeating part is what is reflected in the while. If you have a non-repeated part it can be handled before the loop.
« Last Edit: Dec 30th, 2011, 8:49am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: Biasing a fair coin  
« Reply #11 on: Dec 30th, 2011, 10:04am »		 Quote Quote Modify Modify
on Dec 29th, 2011, 12:47pm, towr wrote:
Random returns to 0 whenever random=n
 
For example take n=3, and the first two times fairFlip() return 1, then random=3 at the if statement, 3 get's subtracted. Then if the next round the first two times fairFlip() returns zero, then we get at the if statement with random=0 and return true.
In general for n=3 we have (11)*00=>true, and (11)*01=>false and (11)*10=>false

 
but lets say n=6; and say random = 7 and range is 8, then the new random and range are 1 & 2 respectively.  
 
now if the new random <6 it will return false, because we know it isn't 0.
 
does this still gives 1/6 probability of returning true?  
 
may be it does, because probability of hitting n is 1/n and when it hits n we go back to 0.
 
how is this different from just resetting to 0 if random >= n always?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #12 on: Dec 30th, 2011, 11:55am »		 Quote Quote Modify Modify
It's different because you use the bits more efficiently. It gives the same answer, but for slightly less work.
 
It's like if you had a die and want to simulate a coin, you could say 1=head, 2=tails, 3,4,5,6=repeat, or you could do odd=heads, even=tails, you'll get the same answer with the same probability, but in the latter case you don't waste time. You don't save quite as much time here, but you save some.
 
for n=6
000 = true
001 = false
010 = false
011 = false
100 = false
101 = false
110 => 0
  000 => true
  001 => false
  010 => false
  011 => false
111 => 1
  100 => false
  101 => false
  110 => 0
  111 => 1
etc
 
In this case you save 1 bit each round, because you reuse what's left after the previous round. So you only need two instead of three flips each additional round.
So instead of an average of 4 bits, you need an average of 3 2/3 to get the answer (if I calculated that correctly), that's 8 1/3 % faster.
« Last Edit: Dec 30th, 2011, 11:58am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
krishnav
Newbie
*





   


Posts: 12
Re: Biasing a fair coin  
« Reply #13 on: Dec 31st, 2011, 10:56am »		 Quote Quote Modify Modify
consider this:
n = 9; so range is 16; if we generate random=10 the first time, we make random=1 and range = 7; so in one more flip range will be more than n, but random is guaranteed to be < n and isn't 0, so we return false. this means if we get 10, 11 or 12 the first time, we'll return false in the next round no matter what. isn't it?
IP Logged
towr
wu::riddles Moderator
Uberpuzzler
*****



Some people are average, some are just mean.

   


Gender: male
 Posts: 13730
Re: Biasing a fair coin  
« Reply #14 on: Jan 1st, 2012, 6:11am »		 Quote Quote Modify Modify
Yes, but if you generate 9, 13 or 15 the first time round, you might return true.
 
0   0000 T
1   0001 F  
2   0010 F  
3   0011 F
4   0100 F
5   0101 F
6   0110 F
7   0111 F
8   1000 F
 
9   1001 -> 000
  (0)    0000 T
  (1)    0001 F
10   1010 -> 001
  (2)    0010 F
  (3)    0011 F
11   1011 -> 010
  (4)    0100 F
  (5)    0101 F
12   1100 -> 011
  (6)    0110 F
  (7)    0111 F
13   1101 -> 100
  (8)    1000 F
 
  (9)    1001 -> 000
14   1110 -> 101
  (10)    1010 -> 001
  (11)    1011 -> 010
15   1111 -> 110
  (12)    1100 -> 011
  (13)    1101 -> 100
etc
 
For each round, you have a 1 in 9 chance of returning true, and otherwise you go on to the next round.
« Last Edit: Jan 1st, 2012, 6:16am by towr » IP Logged
Wikipedia, Google, Mathworld, Integer sequence DB
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Biasing a fair coin  
« Reply #15 on: Jan 2nd, 2012, 5:08am »		 Quote Quote Modify Modify
on Dec 31st, 2011, 10:56am, krishnav wrote:
consider this:
n = 9; so range is 16; if we generate random=10 the first time, we make random=1 and range = 7; so in one more flip range will be more than n, but random is guaranteed to be < n and isn't 0, so we return false. this means if we get 10, 11 or 12 the first time, we'll return false in the next round no matter what. isn't it?

That's right, in some cases we don't actually need the last fairFlip.
 
Indeed, with n=9, if the first 2 flips return false then true then the random value will be in range 4..7 and the flip function will return false regardless of the 3rd and 4th fairFlip.
 
What happens is that I used a method designed to generate a number in range 0..n-1 and then test if it is 0 to return true with probability 1/n.  We can use fairFlip more sparingly using a method like in replies #5 and #6.
IP Logged
Grimbal
wu::riddles Moderator
Uberpuzzler
*****






   


Gender: male
 Posts: 7527
Re: Biasing a fair coin  
« Reply #16 on: Jan 2nd, 2012, 5:39am »		 Quote Quote Modify Modify
Here is a function that returns true with probability p/q, given a fairFlip function that returns true and false with equal probability.
 
boolean flip(p,q) {
  if( p>=q ) return true; // for safety
  while( true ){
    if( p<=0 ) return false;
    if( 2*p<q ){
 if( fairFlip() ) return false;
 p = 2*p;
    } else {
 if( fairFlip() ) return true;
 p = 2*p - q;
    }
  }
}
 
which can be rewritten:
 
boolean flip(p,q) {
  if( p>=q ) return true;
  while( p>0 ){
    if( fairFlip() ) return 2*p>=q;
    p = (2*p)%q;
  }
  return false;
}
IP Logged
ashmish2
Newbie
*





   


Posts: 12
Re: Biasing a fair coin  
« Reply #17 on: Mar 22nd, 2012, 3:33am »		 Quote Quote Modify Modify
int currentloc = 0;
 
BiasFlip(int n)
//Circular array with all value true (tail) and 1 false  
(head)
 
bool arr[n];
for i = to arr.length()
  arr[i]=true;
arr[rand()%n]= false;
 
for each Fairflip() == Head  
                 currentloc+=2  
                 return arr[currentloc];
for each Fairflip() == Tail
                currentloc--
                return arr[currentloc]
  
« Last Edit: Mar 22nd, 2012, 3:43am by ashmish2 » IP Logged
titan
Newbie
*





   


Posts: 33
Re: Biasing a fair coin  
« Reply #18 on: Oct 18th, 2013, 4:14am »		 Quote Quote Modify Modify
I have nothing new to say. Want to confirm if the following strategy proposed by towr can be regarded as correct and can be used:-
Probably  
Let's see; 0.101010101010 = 2/3  
How about just taking the binary expansion of the fraction?  
 
Quote:

12/13 = 0.111011000100  
How does:  
while( true ){  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'H';  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'H';  
    if( fairFlip() ) return 'H';  
    if( fairFlip() ) return 'H';  
    if( fairFlip() ) return 'T';  
    if( fairFlip() ) return 'H';  
    if( fairFlip() ) return 'H';
IP Logged
Pages: 1  Reply Reply Notify of replies Notify of replies Send Topic Send Topic Print Print

« Previous topic | Next topic »

Powered by YaBB 1 Gold - SP 1.4!
Forum software copyright © 2000-2004 Yet another Bulletin Board