An interview question: About Probability

Question

An interview question:

Given a function f(x) that 1/4 times returns 0, 3/4 times returns 1. Write a function g(x) using f(x) that 1/2 times returns 0, 1/2 times returns 1.

My implementation is:

function g(x) = {     if (f(x) == 0){ // 1/4          var s = f(x)          if( s == 1) {// 3/4 * 1/4             return s  //   3/16         } else {             g(x)         }      } else { // 3/4             var k = f(x)             if( k == 0) {// 1/4 * 3/4                 return k // 3/16              }  else {                 g(x)             }            } } 

Am I right? What's your solution?(you can use any language)

Answer 1

If you call f(x) twice in a row, the following outcomes are possible (assuming that successive calls to f(x) are independent, identically distributed trials):

00 (probability 1/4 * 1/4) 01 (probability 1/4 * 3/4)   10 (probability 3/4 * 1/4)   11 (probability 3/4 * 3/4) 

01 and 10 occur with equal probability. So iterate until you get one of those cases, then return 0 or 1 appropriately:

do   a=f(x); b=f(x); while (a == b);  return a; 

It might be tempting to call f(x) only once per iteration and keep track of the two most recent values, but that won't work. Suppose the very first roll is 1, with probability 3/4. You'd loop until the first 0, then return 1 (with probability 3/4).

Answer 2

The problem with your algorithm is that it repeats itself with high probability. My code:

function g(x) = {     var s = f(x) + f(x) + f(x);      // s = 0, probability:  1/64     // s = 1, probability:  9/64     // s = 2, probability: 27/64     // s = 3, probability: 27/64     if (s == 2) return 0;     if (s == 3) return 1;      return g(x); // probability to go into recursion = 10/64, with only 1 additional f(x) calculation } 

I've measured average number of times f(x) was calculated for your algorithm and for mine. For yours f(x) was calculated around 5.3 times per one g(x) calculation. With my algorithm this number reduced to around 3.5. The same is true for other answers so far since they are actually the same algorithm as you said.

P.S.: your definition doesn't mention 'random' at the moment, but probably it is assumed. See my other answer.