Hi,(adsbygoogle = window.adsbygoogle || []).push({});

I have the following probability question:

Given a random bit string S of length m, if I take a copy of a proper suffix of S (a suffix of S that is neither equal to S, nor empty), and align it with the start of the string, how many consecutive matches starting from the beginning of the string do I expect to see on average?

For example:

Given

S[1..9] = 101010110

If I take the suffix starting from position 3: S[3..9] = 1010110

and align it with S:

S[1..9] = 101010110

S[3..9] = 1010110

How many consecutive matches on average starting from position 1 do I expect to see?

My guess is that since for each position the probability that a symbol matches another is 1/2, half of the sequence would be matches, but I am not sure of this since this line of thought doesn't take in account the consecutive ordering of the sequence of matches.

Can someone please enlighten me?

Thanks.

**Physics Forums | Science Articles, Homework Help, Discussion**

Join Physics Forums Today!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

# Probability question

**Physics Forums | Science Articles, Homework Help, Discussion**