3 ms·
Note: I'm going to use bit strings rather than bit sequences. Given a total of B = 3.4067 x 10^22 bits sent over the internet, I don't think there is any reaso
by tzs 9y ago
Note: I'm going to use bit strings rather than bit sequences.
Given a total of B = 3.4067 x 10^22 bits sent over the internet, I don't think there is any reasonable way to say for sure what the length of the smallest string that has never been sent is, but we can say that there is definitely a 75 bit string that has never been sent.
Take all of the internet transmissions, and concatenate them, giving a string S of B bits.
Every string that has been transmitted is a substring of S.
There are at most B substrings of length n in S, and hence at most B distinct strings of length n that have been transmitted.
If we pick n such that 2^n > B, there must be at least one string of length n that has not been transmitted. 2^n > B whenever n >= 75.
Hence, if the value of B is correct, then there must be a 75 bit string that has never been sent.
- evanb 9y agoIf you concatenate to get S you may introduce substrings that have never been themselves transmitted, though of course I agree that every sequence that has been transmitted is a substring of S.
- cup-of-tea 9y agoYeah which means 74 is an upper bound on the length of bit sequence which might have been transmitted already.
- ghayes 9y agoThis reasoning seems to better match the question as it was originally posed.
- pelario 9y agoNeat! 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.