# binary string probability question

• Jun 1st 2008, 04:32 PM
hatsoff
binary string probability question
Hi, all.

Suppose you're given a binary string S, which is $L_S$ digits long. Now, suppose you are looking for a particular binary string T which is $L_T$ digits long, where:

$L_S\geq L_T$

What is the probability, given equal probability 0.5 of each binary digit, that string T will appear within string L?

Thanks!
• Jun 1st 2008, 08:56 PM
mr fantastic
Quote:

Originally Posted by hatsoff
Hi, all.

Suppose you're given a binary string S, which is $L_S$ digits long. Now, suppose you are looking for a particular binary string T which is $L_T$ digits long, where:

$L_S\geq L_T$

What is the probability, given equal probability 0.5 of each binary digit, that string T will appear within string L?

Thanks!

You might (or might not) have some follow-up questions:

Let X be the random variable number of occurrences of T.

Then X follows a binomial distribution where n = $L_S - L_T + 1$ and $p = \left( \frac{1}{2} \right)^{L_{T}}$.

You require Pr(X > 0) .......