Shortest bit sequence that's never been sent over the Internet (2017)
<i>> We're looking for a specific sequence, though, not a specific number of heads in a row. We don't even know what the sequence is since it hasn't been sent yet. Is that a problem? Not at all! We're looking for some sequence of length n, and given that both 0 and 1 are equally likely, the sequence 00110 is equally likely as 11111.</i><p>Interestingly enough, this isn't true!<p>First, let's test on a small example: how likely are the substrings "11" and "10" to appear in binary strings of length 3?  Here's a table with the matches marked.<p><pre><code>        "11" "10"
    000
    001
    010        *
    011   *
    100        *
    101        *
    110   *    *
    111   *
</code></pre>
"10" can appear in four ways, but "11" can only appear in three.  Why is this?<p>Say you're scanning through a bit string, looking for "11111".  You've seen "111" so far -- that's three matches.  Now you encounter a "0".  Your counter resets to zero matches until you see a "1" again.<p>Now say you're looking for "00110".  You've seen "001" so far.  Just like before, you encounter a "0".  You still need to reset your counter, but this time the "0" may actually be the start of a <i>new</i> "00110".  So your counter resets to one, not zero.  This means "00110" matches are easier to find, and happen more frequently!