3 ms·
> This means "00110" matches are easier to find, and happen more frequently! They do not happen more frequently in a random bit stream. You are absolutely and
by bhouston 9y ago
> This means "00110" matches are easier to find, and happen more frequently!
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.
- panic 9y agoYou'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 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.
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]
- deleted 9y ago[deleted]