Monday, January 18, 2010

Amazon's biased coin toss problem

I was at CodeMash conference last week. Amazon.com was one of the vendors at the conference. They were recruiting people at the conference. They posted all kinds of brain teaser problems for the attendees to solve. One of the problems drew my attention and I have been obsessed with it for a few days. Here is the problem:

You are given a randomFlip() that returns true 50% of the time. Implements a biasedFlip() that returns true 31.416% of the time using randomFlip().

I have taken probability courses in high school and college. All the probability problems I came across involved calculating probabilities for certain number of coins or dices. The above problem is new to me. I applied all my probability knowledge but got nowhere. So, I turned to google and found this solution. The solution is a bit confusing because it is used to break a three or more way tie, or create a probability distribution other than 50-50. We need to create a probability distribution other than 50-50 for our problem. I was stuck again because I don't understand some of the steps. Again, I turned to Internet. This time, I turned to Dr. Math for help. It is a great site to search for Math solution or ask a question. After getting some clarifications from Dr. Math, I managed to construct the following steps for our problem:

Step 1: The probability for each outcome is 31.416%.

Step 2: The intervals are [0, 0.31416) and [0.31416, 1).

Step 3: Convert 0.31416 to binary decimal.

0.31416 * 2 = 0.62832
0.62832 * 2 = 1.25664
0.25664 * 2 = 0.51328
0.51328 * 2 = 1.02656
0.02656 * 2 = 0.05312
0.05312 * 2 = 0.10624
0.10624 * 2 = 0.21248
0.21248 * 2 = 0.42496
0.42496 * 2 = 0.84992
0.84992 * 2 = 1.69984
0.69984 * 2 = 1.39968
0.39968 * 2 = 0.79936
0.79936 * 2 = 1.59872
0.59872 * 2 = 1.19744
0.19744 * 2 = 0.39488
0.39488 * 2 = 0.78976
0.78976 * 2 = 1.57952

From the above, the binary decimal for 0.31416 is 0.01010000011011001.

Step 4: true = 1; false = 0

Step 5: Call randomFlip() and record each result.

Step 6: Convert the sequence of true and false to a binary decimal according to step 4.

Step 7: Will be illustrated by below code.

The following code illustrates how to create a biased flip program:

public boolean biasedFlip() {
String binaryProbabilityInString = "01010000011011001"; // binary decimal for 0.31416

for (int i=0; i<binaryProbabilityInString.length(); i++) {
boolean isTrue = randomFlip();
if (isTrue && binaryProbabilityInString.charAt(i) == '1') {
continue;
} else if (!isTrue && binaryProbabilityInString.charAt(i) == '0') {
continue;
} else if (!isTrue && binaryProbabilityInString.charAt(i) == '1') {
return true; // when the probability of the toss is < 0.31416
} else if (isTrue && binaryProbabilityInString.charAt(i) == '0') {
return false; // when the probability of the toss is > 0.0.31416
}
}
return true;
}


randomFlip() is trivial and we will skip that. It returns true 50% of the time. Let's assume that true = 1 and false = 0. In biasedFlip(), we loop through each bit of 0.31416. If the randomFlip() returns true (1) and the bit is “1” or randomFlip() returns false (0) and the bit is “0”, we call randomFlip() again. If randomFlip() returns false (0) and the bit is 1, it means the probability of next and future coin flip will be less than 0.31416. For example, if the first two flips return 00 (represents 0.00 in binary decimal form), the decimal value will be less than 0.01 (first two bits of 0.31416). We are sure that the probability of next and future flip will be in [0, 0.31416) interval. So, there is no need for us to flip the coin any further and we are done. On the other hand, if randomFlip() returns true (1) and the bit is 0, it means the probability of next and future coin flip will be greater than 0.31416. For example, if the first flip returns 1 (represents 0.1 in binary decimal form), 0.1 will be greater than 0.01 (first two bits of 0.31416). We are sure that the probability of next and future flip will be in [0.31416, 1) interval. As a result, there is no need for us to flip the coin any further and we are done.

The probability problem is interesting and challenging. I learned a lot by working through the problem. It is a popular interview question asked by companies like Amazon and Facebook but there are not many solutions on the Web. In my opinion, this is a lousy interview question. People who do not work with probability a lot won't come across this kind of problem. However, it is a good programming exercise and I enjoyed it.

Update: I sent an email to the author of "How to Simulate a Biased Coin Toss With a Fair Coin" to get some clarifications on the steps and he updated the article with some examples.

2 comments:

  1. Hi Shih-gian, I think your approach is wrong. If I have understood as well your idea, you basically return true if you find such number that is lower than our probability....
    Suppose that our probability is:
    0.75
    In binary: 0.11 Right?
    Seeing you algorithm you will return true for these numbers: 0.0X with 0.5 of probability
    And
    0.1X, cause 0.11 and 0.10 is true in your algorithm, so... the last number is X because in your algorithm it doesn't matter(Because will be a lower number)
    And we also know that 0.1x has 0.5 of probability...
    So for 0.75 you program will always returns true...

    ReplyDelete
  2. http://www.wikihow.com/Simulate-a-Biased-Coin-Toss-With-a-Fair-Coin
    http://www.wikihow.com/Simulate-a-Fair-Coin-Toss-With-a-Biased-Coin

    these articles are simply written to the point and great

    ReplyDelete