Neat! This analysis is consistent (and more accurate) than the OP; he assumed that the bitstring is random; therefore he arrives to the lower bound. If, somehow

Neat! This analysis is consistent (and more accurate) than the OP; he assumed that the bitstring is random; therefore he arrives to the lower bound. If, somehow we account for the bias in the sequence, we may find a larger n.