3
$\begingroup$

Let $S$ be a length $L$ string, where each character in the string is chosen with uniform random probability over an alphabet with $q$ characters. For example, a binary string would imply $q = 2$, a ternary string would imply $q = 3$, and so forth.

What is the probability of having all possible instances of a length $r < L$ subword (for example "DEF" would be an $r = 3$ subword of "ABCDEFG") in the string $L$ under conditions where: (1) partially overlapping subwords (for example "BCD" and "CDE" in "ABCDEFG") are allowed to count as two separate independent instances of subwords, (2) only one of two or more overlapping subwords are allowed to count as an independent instance of a subword?

To clarify a possible point of confusion for (2), we need to address the case where we have a chain of subwords - for example "ABC", "CDE", "EFG", "FGH" for the string "ABCDEFGH". Here, we are allowed to discard any subword or set of subwords we choose until no two subwords overlap. The remaining instances can then be counted as independent subwords. So, perhaps more reasonably, for (2) we can ask for the "existence" of a decision-based pruning procedure such that, after pruning, we have all possible instances of length $r$ subwords in the string $S$ of length $L$ over a $q$-ary alphabet.

$\endgroup$
  • 3
    $\begingroup$ People voting to close might like to tell us the answer if it is so easy. @AClockTicks: delete the first appearance of the word "binary". $\endgroup$ – Brendan McKay Apr 6 '14 at 18:20
  • $\begingroup$ @BrendanMcKay Sorry for the typo, it should now be fixed. Also, thanks in general for your comment - this ended up being tricky for me to work out and I feel relieved to know at least one other person doesn't think the problem is trivial. $\endgroup$ – AClockTicks Apr 7 '14 at 4:01
3
$\begingroup$

The version with overlaps allowed was studied in:

On words containing all short subwords

Ioan Tomescu http://dl.acm.org/citation.cfm?id=276278

$\endgroup$
  • $\begingroup$ From the paper (researchgate.net/publication/…) I don't think there's going to be a reasonable analytic expression for the exact probability for (1). Scenario (2) seems hopeless. Do you agree with this? $\endgroup$ – AClockTicks Apr 7 '14 at 7:13
  • $\begingroup$ Yes. But do you need an exact expression or just some asymptotics? $\endgroup$ – Bjørn Kjos-Hanssen Apr 7 '14 at 7:21
  • $\begingroup$ Let's scratch (2) because its too hard. But for (1) I was hoping for either an exact expression OR some approximate expression that works well for strings with $L \geq 10$ and $q \geq 2$ or so. I'm less interested in asymptotics, but that's not to say I didn't appreciate the paper. $\endgroup$ – AClockTicks Apr 7 '14 at 7:28

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.