Shortest bit sequence that's never been sent over the Internet (2017)

Re:Shortest bit sequence that's never been sent over the Int... by daveFNbuck on Thursday April 19, 2018 @11:14AM (#16876588)

I wrote a quick Python snippet to compute the probabilities for all sequences of length 3 over 20 flips:

  [(x, sum(1 for i in range(2**20) if x in '{:020b}'.format(i)) / 2.0**20) for x in map('{:03b}'.format, range(8))]

The output shows a 79% chance for "000" and a 91% chance for "010". "000" and "111" are actually the least likely substrings, with "010" and "101" in second place.

Furthermore, "001" has a 97% chance of occurring. It's pretty easy to see why "001" is so much more likely than the others. Unless your string perfectly alternates 0s and 1s, you're going to get repeating pairs. What happens after you get a "00"? If there's ever a 1 again, there were at least two 0s before it.

So you're almost guaranteed a "001" after "00", unless it's near the very end of the string. You only have a 50% chance of getting "000" from these though. A 1 completely resets the search for "000", but a 0 keeps the search alive for "001".

[ Parent | on HN ]

Re:Shortest bit sequence that's never been sent over the Int... by zwischenzug on Thursday April 19, 2018 @12:19PM (#16877164)

Again: that looks for whether that sequence is in each tested string, which is a different problem.

It tests if 'x' is 'in', rather than the number of times it is seen.

[ Parent | on HN ]

Re:Shortest bit sequence that's never been sent over the Int... by daveFNbuck on Thursday April 19, 2018 @08:57PM (#16881385)

But the question being tested is whether a given string is in the bits that have been transferred over the internet. The number of times it is seen is not what we're talking about here.

[ Parent | on HN ]