Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have an unknown string S of length n. I have to given small string A1 and A2. Supposed that I know the probability of S.contains(A1) = true (which mean A1 appears in S at least once) and S.contains (A2) = true.

How do we compute the probability of S.contains(A1) && S.contains(A2)?

The general problem: Compute the probability P[S.contains(A1) && S.contains(A2) && ... && S.contains(An)] when we know P[S.contains(A1)], P[S.contains(A2)], ..., P[S.contains(An)]

Thank you

Update: We can compute P[S.contains(x) == true] in which x is an arbitrary string.

share|cite|improve this question

I guess if intersection of A1 and A2 is 0, then you should simply multiply the Pr(A1) and Pr(A2). or if you know probability of S.contains(A1) or S.contains(A2) you can simply subtract it from P(S.contains(A1) + p(S.contains(A2))

share|cite|improve this answer
What do you mean by intersection of A1 and A2? For example, if A1 = '101' && A2 = '000', then if you mean the intersection is the part X that either is prefix of A1 and postfix of A2 or prefix of A2 and postfix of A1, then this case the intersection is blank. Then in case n = 5, we have P(S.contains(A1)) > 0, P(S.contains(A2) > 0 but P(S.contains(A1) && S.contains(A2)) = 0 – Loi.Luu Sep 6 '13 at 8:37
I know nothing more than the given assumption :) – Loi.Luu Sep 6 '13 at 8:40
So what if we have A and B do not intersect? – Loi.Luu Sep 9 '13 at 2:27

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.