5 ms·
> 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.
by panic 8y ago
> 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.
Interestingly enough, this isn't true!
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.
"11" "10"
000
001
010 *
011 *
100 *
101 *
110 * *
111 *
"10" can appear in four ways, but "11" can only appear in three. Why is this?
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.
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 new "00110". So your counter resets to one, not zero. This means "00110" matches are easier to find, and happen more frequently!
- bigiain 8y agoAnother possible detail this misses - I learnt about De Bruijn sequences from Samy Kamkar here: http://samy.pl/opensesame/ http://samy.pl/opensesame/ (scroll about 1/3rd way down to the "(U) The OpenSesame Attack" section for the bits relevant to this discussion...) You don't need to enumerate every n-bit sequence, you just need to enumerate a (shorter - by 62% in Samy's 12 bit case) sequence that contains all the n-bit sequences.
- saagarjha 8y agoInterestingly, there was an old USAMTS problem that had De Bruijn sequences in it, though I wasn't aware of it at the time: http://www.usamts.org/Tests/Problems_25_1.pdf http://www.usamts.org/Tests/Problems_25_1.pdf
- gumby 8y agoThis is the heart of the Boyer-Moore string searching algorithm too.
- acobster 8y agoWow, how surprising and, in a strange way, kind of beautiful! Thanks for this.
- comex 8y agoWow. That's really nonintuitive to me. Like the Monty Hall problem: you have something that's obviously an irrelevant detail that can't affect the probability… except… somehow it does.
- plopilop 8y agoThere are problems that I find even more counterintuitive than Monty Hall, such as the sister's paradox. Your neighbours has two children, one of which is a girl. What is the probability of the other child to be a girl? A. One may say 1/2, but actually, using basic Bayes theorem: P(2 girls | at least 1 girl) = P(2 girls AND 1 at least girl) / P(at least 1 girl) = (1/4) / (3/4) = 1/3. I think this problem is actually equivalent to the Monty Hall problem. But it can get much weirder. Your neighbour has 2 children, one is a girl. You know the other child is born on a Sunday, what is the probability that this other child is a girl? A. Similarly, counting all possible cases, one does not get 1/2 or 1/3, but rather 13/27.
- cjslep 8y agoYou are horribly butchering Bayes' Theorem. Both your examples are incorrect because your two events ('2 girls' and 'at least 1 girl') are not oberved independently of one another, which is a necessary condition to using Bayes' Theorem with a valid result. Great tool but wrong job.
- plopilop 8y agoWhat? Bayes' theorem does not require anything about the events, even more so it is useful when the events are not independent. If events are independent, Bayes' theorem has no usefulness. https://en.wikipedia.org/wiki/Bayes%27_theorem#Statement_of_theorem https://en.wikipedia.org/wiki/Bayes%27_theorem#Statement_of_... Edit: however now that I look into it, I should rather have used "conditional probabilities" name rather than Bayes'. I always mix both of them, my bad.
- kqr 8y agoIn the first case, I guess what's happening is that when we pick two people randomly with uniform distribution, we expect, with equal probability, any combination of boys and girls: MM MF FF FM. When we observe a girl, we can exclude the case of two boys, so the remaining cases to consider are MF FF FM, where obviously only 1/3 of the cases is two girls. So I guess what makes this counterintuitive is that we think of the example as independent variables actually affecting each other, but what happens is really that we're drawing from a collection without replacement, and obviously the mix of the collection is going to change as we do so. This should apply also on a humankind, world-wide scale: if you have met three women in a row, the fourth person you meet is more likely to be a man. Gambler's fallacy! Or just drawing without replacement. A roulette table is drawing with replacement. :)
- trowftd 8y agoAren't you miscounting though? 111 contains the 11 sequence twice.
- jstanley 8y agoBut you're trying to find a bit-substring of length 2 that is least likely to have been transmitted. If the bit strings of length 3 are chosen uniformly, 11 is less likely to appear than 10.
- panic 8y agoSure, but the question is "how likely" not "how many times". Counting the expected number of times is a much easier problem because you can use the linearity of expectation.
- azernik 8y agoWhich is probably the key intuition here - the expected number of matches is exactly the same, but because you can have more matches for the purely-repeated sequence in the same string the total number of strings containing those matches is smaller.
- bhouston 8y agoYou are totally right. He is incorrect.
- FRex 8y agoThis is (almost) how Knuth–Morris–Pratt string search algorithm works: https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93P...
- hnuser1234 8y agoDoes this still apply when your search space is on the order of thousands of petabytes, and the smallest unseen sequences are, according to the linked post, around 75 bits?
- deleted 8y ago[deleted]
- zwischenzug 8y agoYou've answered a different question: How likely are the substrings "11" and "10" to appear in binary strings of length 3? rather than: Is the sequence of '111' as equally likely to appear as '010' given that 1s and 0s are equally likely to appear?
- zwischenzug 8y agoReminds me of a question an old tutor used to ask potential thesis candidates: If I throw two dice, what's the probability I throw at least one six?
- pure-awesome 8y agoAm I being stupid, or is the answer 11/36? I.e., slightly less than 1/3? Out of 36 possible throws of a pair of dice, 10 of them have a single six and 1 more has both sixes.
- tomsmeding 8y agoSeems correct. The probability of at least one 6 is one minus the probability that both aren't a 6, which is 5/6 * 5/6 = 25/36; so the result is (36-25)/36 = 11/36.
- rtkwe 8y agoWhy wouldn't it just be the probability of either rolling at least one 6 which would be 1/6 + 1/6 = 1/3? Genuinely curious, I was never super good at probability calculations. edit: clarification of problem.
- Retric 8y agoPicture two coins and 2 flips and count the H's there (2x2) = 4 options and ((2x2) x 1/2 x 2(flips)) = 4 Heads. HH, HT, TH, TT However, if you count the sequences with at least one H there are (4-1) = 3 with at least 1 H (HH, HT, HT) as the HH eats up 2 H's. Now, Picture 3 sided dice, that's (3x3) = 9 options. You will see ((3x3) x 1/3 x 2(flips)) = 6 2's. 00, 01, 02, 10, 11, 12, 20, 21, 22 However if you count there are (6 - 1) = 5 sequences with at least one 2 you get 02, 12, 20, 21, 22 as the 22 eats up an extra 2. Now, what do you think happens with an N sided dice? What if N is 6. PS: This seems less clear as I added more info...
- improv32 8y agoI'm reminded of constructing DFAs that represent regular expressions for class.
- panic 8y agoYeah, you can see finite automata explicitly used in the PDF that's linked in the article itself: https://www.cs.cornell.edu/~ginsparg/physics/INFO295/mh.pdf https://www.cs.cornell.edu/~ginsparg/physics/INFO295/mh.pdf
- deleted 8y ago[deleted]
- bhouston 8y 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 8y 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 8y ago[deleted]
- deleted 8y ago[deleted]
- deleted 8y ago[deleted]
- anonlastname 8y agoYes, google "penney ante"