5
$\begingroup$

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?

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

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.

$\endgroup$
  • $\begingroup$ This is awesome! Thank you very much Tad. :) $\endgroup$ – Michael Wehar Aug 6 '15 at 14:40
  • $\begingroup$ 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. :) $\endgroup$ – Michael Wehar Aug 6 '15 at 14:47
  • $\begingroup$ But, really, it helped me better understand how to deal with counting problems that involve contiguous substrings. $\endgroup$ – Michael Wehar Aug 6 '15 at 14:48
  • 2
    $\begingroup$ 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$! $\endgroup$ – Tad Aug 6 '15 at 21:51
  • 1
    $\begingroup$ 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. $\endgroup$ – András Salamon Aug 7 '15 at 9:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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