A Probability Trick Question

I heard an interesting trick question recently: “Given a function that returns a random integer between 1 and 6, use it to write a function that returns a random integer between 1 and 7.”

I quickly came up with a solution that works, but isn’t optimal in one sense. The idea is to use the given Random16() function to generate three binary 0 or 1s (0 if Random16 is 1, 2, or 3 — 1 if Random16 is 4, 5, 6) then use those to construct a 3-bit number in the range 1-8. If the result is 8, try again, otherwise return the result.

I coded up the algorithm using C# to make sure it worked (it did).

probabilitytrickquestion

One advantage of my mini-algorithm is that it can be easily adapted to just about any similar problem. A disadvantage is that there’s a very clever way to solve the problem that uses only two calls to Random16() instead of the three calls required by my approach. Interesting problem.

public static int Random16()  // given
{
  return rnd.Next(1, 7); // [1, 7) = [1, 6]
}
public static int Random17()
{
  // use given Random16 to generate a 3-bit number [1,8]
  // toss out an 8 result
  while (true)  // until a valid result
  {
    int result = 1;
    for (int bit = 0; bit < 3; ++bit)
    {
      int r16 = Random16();  // 1-3 = "0", 4-6 = "1"
      if (r16 >= 4)   // "1" bit
        result += (int)Math.Pow(2, bit); 
    }
    if (result <= 7)
      return result;
  }
}
This entry was posted in Miscellaneous. Bookmark the permalink.

2 Responses to A Probability Trick Question

  1. Two calls to the given randomizer produces 36 distinct outcomes.

    If we consistently discard one outcome, we are left with 35 combinations which can be be thought of as 7 groups of 5.

    Determining which group of 5 to index produces the desired random7() function, This is completed with only 2 calls (97% of the time) to random6().

    Note, we work zero-relative, to keep the math simple. Here’s the java code:

    import java.util.Random;
    

/* Created by davidqkleinberg on 10/27/16.
 */
    

public class McCaffreyRandomizer {
    
 private static Random rand = new Random();
    
 public static void main(String[] args) {
    
 for (int i=0; i ” + random06;
    
 System.out.println(str);
    
 }
    
 }
    
 }
    
 private static int random05(){

    return rand.nextInt(6); // 6 possible values, zero relative
 i.e., 0-5
    }
    
}


Comments are closed.