Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

We are given two strings $S=a_1 a_2 \dots a_L$ and $T=b_1 b_2 \dots b_l$ on some alphabet.

The string $S$ is cut into substrings, such that for each $a_i$ in $S$, there's a probability $p_i$ that a cut is made after $a_i$. For example, $S$ may be cut into the substrings:

$$S_1 = a_1 a_2a_3, \hspace{5 mm} S_2 = a_4 a_5, \hspace{5 mm} S_3 = a_6 a_7...a_L $$

which means that $S$ was cut after $a_3$ and after $a_5$. The probability of this is

$$(1-p_1)(1-p_2)p_3(1-p_4)p_5(1-p_6)...(1-p_{L-1})$$

After cutting $S$, what's the expected count of occurrences of $T$ in the resulting substrings?

I need an algorithm that computes this expected count.

More precisely, the input is the strings $S$ and $T$, and the probabilities $p_i$ for each character in $S$. The output is the expected number of occurrences of $T$ in the resulting substrings of $S$. Is there an efficient algorithm for this problem?

share|improve this question
2  
Sure. Just find all occurrences of T in S, calculate the survival probability for each occurrence (just multiply the corresponding $(1-p_i)$) and add them up. You also seem to be a bit confused because the probability of the cut you posted as an example is not $p_3p_5$ but rather $(1-p_1)(1-p_2)p_3(1-p_4)p_5(1-p_6)\dots(1-p_{L-1})$. –  fedja Feb 16 '13 at 3:47
    
@fedja I fixed the mistake in the probability of my example. But I think the solution is not that simple. Are you sure your solution still applies if different occurrences of $T$ in $S$ overlap? –  becko Feb 16 '13 at 4:01
    
Certainly. You see, the expectation is additive no matter what. Of course, we count all occurrences of T in all pieces here. –  fedja Feb 16 '13 at 4:05

1 Answer 1

up vote 1 down vote accepted

Fedja's comment is correct; see linearity of expectation (which doesn't require independence).

share|improve this answer

Your Answer

 
discard

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.