# Counting the expected number of strings with a given contiguous substring.

Question:

Let a random bit string $x$ of length $n$ be given.

What is the expected number of bit strings $w$ of length $2n$ that contain $x$ as a contiguous substring?

What I know:

For any bit string $x$ of length $n$, the total number of length $2n$ bit strings $w$ that contain $x$ as a contiguous substring is between $2^n$ and $(n+1) \cdot 2^n$. The exact number may depend on the string $x$ that you pick.

To the point:

Is the expected number $\Theta(2^n)$, or $\Theta(n \cdot 2^n)$, or something in between?

• @TravisJ Any upper bounds or lower bounds are helpful. The best upper bound that I have is $(n+1) \cdot 2^n$. – Michael Wehar Aug 5 '15 at 15:51
• Sorry, I made a mistake. The $2^{n}(n+1)$ is the same bound I get. – TravisJ Aug 5 '15 at 16:03
• You can subtract 1 for avoiding double counting of the string contains x twice. – Sungjin Kim Aug 5 '15 at 19:12
• I think the problem should be "total number of bit strings w of length 2n..." – Sungjin Kim Aug 5 '15 at 19:13
• I see, so you are considering for all possible x. – Sungjin Kim Aug 5 '15 at 22:18

The expected number is $\Theta(n\, 2^n)$. The OP observes that this is an upper bound, so we need to show it is a lower bound.

In one sentence, the proof is: $x$ probably doesn't overlap itself, so you can only fit $O(1)$ copies of $x$ into any one $2n$-long string, so the occurrences of $x$ as substrings must be distributed over lots of $2n$-long strings.

Here are more details; I'm going to ignore some ceilings and floors for simplicity. Fix an $n$-long string $x$; let $s(x)$ denote the smallest "shift amount" $s$ such that $x$ "overlaps" with itself at a shift of $s$; that is, the $(n-s)$-prefix of $x$ agrees with the $(n-s)$-suffix of $x$. (Set $s(x)=n$ if no such shift amount exists.) Then a $2n$-long string can only contain $1+n/s(x)$ copies of $x$.

The total number of $n$-long strings $x$ with $s(x)\le k$ is at most $2^1+2^2+\cdots+2^{k}<2^{k+1}$. So the probability that $s(x)<n/2$ is $O(2^{-n/2})$. Thus, with probability at least $1-O(2^{-n/2})$, the maximum number of occurrences of $x$ in any $2n$-long string is at most $1+n/(n/2)=3$.

Finally, the total number of pairs $(w,i)$ such that $w$ is a $2n$-long string, in which $x$ occurs as a substring at position $i$, is $(n+1)2^n$. The previous paragraph shows that these occurrences of $x$ as substrings are spread out: with probability at least $1-O(2^{-n/2})$, $x$ occurs in at least $(n+1)2^n /3$ of the words $w$. Hence the expectation, taken over $x$, of the number of words $w$ containing $x$, is at least $$(1-O(2^{-n/2}))(n+1)2^n /3= \Omega(n\, 2^n)$$ as required.

• This is awesome! Thank you very much Tad. :) – Michael Wehar Aug 6 '15 at 14:40
• Just to let you know, I was working on a state complexity problem in automata theory. This combinatorial question turned out to be related. Your answer helped us make a little bit of progress. :) – Michael Wehar Aug 6 '15 at 14:47
• But, really, it helped me better understand how to deal with counting problems that involve contiguous substrings. – Michael Wehar Aug 6 '15 at 14:48
• My initial thought was to try to get an exact expression using the Goulden-Jackson cluster method, but it seems hard to compute the precise probabilities of various overlap structures. But you kindly only asked for a $\Theta$! – Tad Aug 6 '15 at 21:51
• Thanks for the pointer to the Goulden-Jackson cluster method. It is arrestingly described by John Noonan and Doron Zeilberger as "replace the hard-to-count set of 'good guys' by the weighted count of the much larger set of pairs (arbitrary-guy, arbitrary-subset-of-his-sins), where the weight is (-1) to the power of the cardinality of the subset of his sins"; see math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/gj.html for the paper and software. – András Salamon Aug 7 '15 at 9:19