生肖迷宫吧 关注:827贴子:12,975
  • 4回复贴,共1

IBM ponder this 2011 09

只看楼主收藏回复

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.


1楼2012-08-10 20:01回复
    官方答案是
    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?


    2楼2012-08-10 20:03
    回复
      考虑到答案比较难懂,我把我的理解贴出来供参考,不一定正确。有兴趣的可以编程验证一下。


      3楼2012-08-10 20:05
      回复
        1 对于随机的6进制数列(dice)转换成随机的2进制数列(bit)。
        先从最简单的1位6进制看起。
        6=4+2=2^2+2
        因此它有4/6的可能是转换为2个bit.
        还有2/6的可能是转换为1个bit.
        也就是:
        1-0
        2-1
        3-00
        4-01
        5-10
        6-11
        然后要达到最高的效率,可以把多位一起转换,位数越多转换效率越高。因此如果数列已经输出完成,转换效率最高的办法就是将整个数列一起转换。
        在看一个2位dice的例子
        36=32+4=2^5+2^2
        也就是说有32/36的可能转换为5位的Bit,4/36的可能转换为2位的bit.
        2 从2到6的转换也是一样的,唯一不同的是因为2的n次方不能整除6,所以有可能出现6的0次方,也就是一个dice都转换不出来
        举个6bit的例子
        64= 6^2+ 4*6^1 +4*6^0
        也就是36/64的可能2个dice
        24/64的可能1个dice
        4/64的可能0个dice
        


        4楼2012-08-10 20:23
        收起回复