<story><title>Shortest bit sequence that&apos;s never been sent over the Internet (2017)</title><url>https://www.seancassidy.me/whats-the-length-of-shortest-bit-sequence-thats-never-been-sent-over-the-internet.html</url></story><parent_chain></parent_chain><comment><author>panic</author><text>&lt;i&gt;&amp;gt; We&amp;#x27;re looking for a specific sequence, though, not a specific number of heads in a row. We don&amp;#x27;t even know what the sequence is since it hasn&amp;#x27;t been sent yet. Is that a problem? Not at all! We&amp;#x27;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.&lt;/i&gt;&lt;p&gt;Interestingly enough, this isn&amp;#x27;t true!&lt;p&gt;First, let&amp;#x27;s test on a small example: how likely are the substrings &amp;quot;11&amp;quot; and &amp;quot;10&amp;quot; to appear in binary strings of length 3?  Here&amp;#x27;s a table with the matches marked.&lt;p&gt;&lt;pre&gt;&lt;code&gt;        &amp;quot;11&amp;quot; &amp;quot;10&amp;quot;
    000
    001
    010        *
    011   *
    100        *
    101        *
    110   *    *
    111   *
&lt;/code&gt;&lt;/pre&gt;
&amp;quot;10&amp;quot; can appear in four ways, but &amp;quot;11&amp;quot; can only appear in three.  Why is this?&lt;p&gt;Say you&amp;#x27;re scanning through a bit string, looking for &amp;quot;11111&amp;quot;.  You&amp;#x27;ve seen &amp;quot;111&amp;quot; so far -- that&amp;#x27;s three matches.  Now you encounter a &amp;quot;0&amp;quot;.  Your counter resets to zero matches until you see a &amp;quot;1&amp;quot; again.&lt;p&gt;Now say you&amp;#x27;re looking for &amp;quot;00110&amp;quot;.  You&amp;#x27;ve seen &amp;quot;001&amp;quot; so far.  Just like before, you encounter a &amp;quot;0&amp;quot;.  You still need to reset your counter, but this time the &amp;quot;0&amp;quot; may actually be the start of a &lt;i&gt;new&lt;/i&gt; &amp;quot;00110&amp;quot;.  So your counter resets to one, not zero.  This means &amp;quot;00110&amp;quot; matches are easier to find, and happen more frequently!</text></comment>
<story><title>Shortest bit sequence that&apos;s never been sent over the Internet (2017)</title><url>https://www.seancassidy.me/whats-the-length-of-shortest-bit-sequence-thats-never-been-sent-over-the-internet.html</url></story><parent_chain></parent_chain><comment><author>x1798DE</author><text>I like this general approach, but presumably you don&amp;#x27;t want the point where 50% of the sequences have never been transmitted (on average, assuming randomly distributed data), you want the first point where at least 1 hasn&amp;#x27;t been transmitted, so you should be solving for the point where the probability of a sequence of that length not appearing times the number of sequences of that length is equal to 1.&lt;p&gt;That said it&amp;#x27;s a logarithmic scale so the length is probably not that much shorter than the one he came up with.</text></comment>