Re:Shortest bit sequence that's never been sent over the Int...
by panic on Thursday April 19, 2018 @05:24AM
(#16874472)
You're right, I didn't word that very clearly. I meant "more strings contain this substring", not "this substring occurs more times total" (which, as you say, would be the usual meaning of "matches happen more frequently").
Why care about strings containing a particular substring versus total number of occurrences? The article referenced this PDF: https://www.cs.cornell.edu/~ginsparg/physics/INFO295/mh.pdf, which is about how many coin flips it takes to see a run of N heads. That's really what the argument in the second half of my post is about, but it applies to the "how many strings contain this substring" problem too, and that one seemed simpler to draw a table for.
They do not happen more frequently in a random bit stream. You are absolutely and completely wrong about this.
They only happen more frequently if you switch the problem from counting occurances to counting bitstreams that contain these occurrences.
The reason this is is because the sequence 111 contains two substrings of 11. Thus if this happens in a bitstream and you are counting bitstreams you only get a count of 1. Where as with the counting frequency you would still get two.
This will occur any time a sequence can be overlapped with itself.