Ponder This Challenge - September 2011 - Bits to dice and back

Ponder This Challenge:

The challenge this month is based on a suggestion we received from Vladimir Sedach (thanks!).

A computer program, named 6to2, gets a sequence of purely random independent and fair dice tosses and outputs a sequence of uniformly and independent bits. It generates as many output bits as it can from the dice inputs -- as long as it can ensure that the output is indeed completely random.

The problem is that our program actually gets its input from a similar program named 2to6, which generates random dice tosses from random bits.

Our question is: What is the efficiency of the above process? Starting from 27 bits, converting them to dice tosses, and then back to bits, how many bits will we get on average?

Please specify the result with at least 4 digits accuracy after the decimal point.

We will post the names of those who submit a correct, original solution! If you don't want your name posted then please include such a statement in your submission!

We invite visitors to our website to submit an elegant solution. Send your submission to the ponder@il.ibm.com.

If you have any problems you think we might enjoy, please send them in. All replies should be sent to: ponder@il.ibm.com

Solution

• Click here to view the solution

  2to6 can be viewed as a process that receives an integer and generates several dice throws.

  Since 227 is not divisible by 6, we cannot guarantee that 2to6 will generate even a single die toss.

  Given a number n and an upper bound N on its value, the best we can do is the following:

  1. If N is zero then exit.
  2. Throw away e=N(mod 6) cases.
  3. Generate a die from (n-e) (mod 6).
  4. Set n = floor(n/6) and N=(N-e)/6 and return to step 1

  From 27 bits (N=227), we get a distribution of zero to ten dice tosses.

  Repeating a similar algorithm for the 6to2 case on the result produces between zero and 25 bits.

  Computing the expected value of the combined process results in ~23.99978 bits.

  Can you explain the extraordinary closeness of the above result to an integer?

Solvers

• Jan Braunisch (09/01/2011 06:31 PM EDT)
• Gergely Pataki (09/01/2011 09:09 PM EDT)
• Shilei Zang (09/01/2011 11:55 PM EDT)
• János Kramár (09/02/2011 03:24 AM EDT)
• Pei Wu (09/02/2011 04:04 AM EDT)
• Georgios Papoutsis (09/02/2011 04:32 AM EDT)
• Michael Brand (09/02/2011 05:15 AM EDT)
• Joseph DeVincentis (09/02/2011 10:38 AM EDT)
• Jan Fricke (09/02/2011 11:01 AM EDT)
• Arthur Breitman (09/02/2011 11:26 AM EDT)
• Avishalom Shalit (09/02/2011 12:36 PM EDT)
• Frederik Kaster (09/02/2011 02:19 PM EDT)
• Joe Fendel (09/02/2011 02:38 PM EDT)
• Dan Dima (09/03/2011 04:37 AM EDT)
• Jason Crease (09/04/2011 01:03 PM EDT)
• William Heller (09/04/2011 05:25 PM EDT)
• Kipp Johnson (09/05/2011 12:38 AM EDT)
• Itsik Horovitz (09/05/2011 07:00 AM EDT)
• Luke Pebody (09/05/2011 01:54 PM EDT)
• Jonathan Campbell (09/05/2011 05:52 PM EDT)
• Thomas Pensyl (09/06/2011 12:30 AM EDT)
• Lu Wang (09/06/2011 06:32 AM EDT)
• Dave Dodson & Don Dodson (09/06/2011 04:21 PM EDT)
• Dave Blackston (09/06/2011 07:07 PM EDT)
• Regis Vert (09/07/2011 09:25 AM EDT)
• Amos Guler (09/07/2011 11:26 AM EDT)
• Adam Daire (09/07/2011 01:54 PM EDT)
• Hamidreza Bidar (09/08/2011 06:58 AM EDT)
• Chris Kuklewicz (09/08/2011 11:33 AM EDT)
• Ken Bateman (09/08/2011 05:22 PM EDT)
• William Mantzel (09/08/2011 07:01 PM EDT)
• Ed Catmur (09/09/2011 07:37 PM EDT)
• Erick Wong (09/09/2011 07:39 PM EDT)
• Peter Gerritson (09/09/2011 10:09 PM EDT)
• Andreas Razen and Radu-Alexandru Todor (09/10/2011 09:47 AM EDT)
• Clive Tong (09/10/2011 02:42 PM EDT)
• Leon Smith (09/12/2011 10:33 AM EDT)
• Chris Marks (09/12/2011 10:59 AM EDT)
• Liubing Yu (09/13/2011 12:01 AM EDT)
• Erik Hostens (09/13/2011 07:24 AM EDT)
• David Friedman (09/14/2011 04:07 PM EDT)
• Phil Benamy (09/16/2011 12:09 PM EDT)
• Stefan Sec Zehl (09/16/2011 12:48 PM EDT)
• Wenxun Huang (09/17/2011 02:52 AM EDT)
• James Aaronson (09/18/2011 10:05 AM EDT)
• Danny Antonetti (09/19/2011 05:09 AM EDT)
• Leif Jensen (09/20/2011 09:32 AM EDT)
• Neil Fernandez (09/22/2011 08:06 AM EDT)
• Andrew Buchanan (09/22/2011 02:19 AM EDT)
• Piet Orye (09/22/2011 02:26 PM EDT)
• Ehud Schreiber (09/27/2011 11:07 AM EDT)
• J. Eric Ivancich (09/28/2011 05:10 PM EDT)
• Colm Bhandal (09/30/2011 12:32 PM EDT)
• Ilya Khivrich (09/30/2011 12:32 PM EDT)
• Jeff Steele (10/01/2011 12:58 AM EDT)