Random Integers Random Bits

  • + 0 comments

    interesting problem; fairly straightforward once you think about it for a bit. some hints that may prove helpful if you're stuck:

    [spoiler]

    1) use [1,a] for the range instead of [a,b]:

    f([a+1,b]) = (f([1,b])*b-f([1,a])*a)/(b-a) due to the linearity of expected value/probability

    2) find the ev/prob for each i-bit subset of the range (ie numbers between 2^i and 2^(i+1)) separately and then linearly combine them at the end. this way the same algorithm can be used for both parts of the problems - just multiply each prob by i to convert from probability to the expected number of bits or divide to go in the opposite direction

    3) the range spanned by the most significant bit (msb) can be written as a linear combination of i-bit ranges (with prefix bits)

    [/spoiler]