Statement

Let y₀, y₁, y₂,… be a sequence of random unsigned 32 bit integers
(i.e. 0 $\leq$ y_i $\leq$ 2³², every value equally likely).

For the sequence xi the following recursion is given:
x₀ = 0 and
x_i = x_i-1 | y_i-1, for i $\leq$ 0. ( | is the bitwise-OR operator)
It can be seen that eventually there will be an index N such that x_i = 2³² -1 (a bit-pattern of all ones) for all i $\leq$ N.

Find the expected value of N.
Give your answer rounded to 10 digits after the decimal point.

Solution

To solve this problem I used, as usual, DP as top-down approach with memoization.

The DP dictionary will be indexed by a tuple consisting of the number of tries left and the number of bits still in 0.

The base cases are:

• remaining tries > 0 and bits in 0 = 0: Then I already have all bits in 1 so it doesn't count, thus the probability is 0.
• remaining tries = 0 and bits in 0 > 0: I have no or operations left to do, so I couldn't complete it, thus the probability is 0.
• remaining tries = 0 and bits in 0 = 0: I have all bits in 1 and finished with the or operations, so this is a good case, probability of 1.

If what we are dealing with is not one of the base cases and it's not stored in the DP dictionary then we calculate the probability of finishing with all bits in 1 using exactly remaining tries or operations. This will calculate the probabilities by using the probabilities stored in the DP.

In order to calculate the result we use the function that retrieves the probability of fulfilling all the bits in exactly i or operations to calculate the weight of that i in the total(this is done by multiplying i to that probaility), we add up the sum for i from 1 to 50, and we get the correct result.

factorial = {0:1}
for i in range(1, 33):
    factorial[i] = factorial[i-1] * i
 
bits = 32
 
comb = lambda n, k: factorial[n] // (factorial[k] * factorial[n-k])
 
dp = {
    (0, 0) : 1
}
 
def get_value(*args):
    if args in dp:
        return dp[args]
 
    length, rem = args
    if length > 0 and rem == 0:
        return 0
    if length == 0 and rem > 0:
        return 0
    result = 0
    for i in range(bits+1):
        for overlooked in range(max(0, i-rem), min(i, bits-rem)+1):
            result += get_value(length-1, rem-i+overlooked) * ((comb(bits-rem, overlooked) * comb(rem, i-overlooked) / (2 ** bits)))
 
    dp[args] = result
    return result
 
iters = 50
 
if __name__ == '__main__':
    result = 0
    for i in range(1, iters+1):
        result += get_value(i, bits) * i
    print("The result is:", result)

The Python file is available for download here.