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.

Improve this question
$\endgroup$
2
  • 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
    Commented Apr 6, 2014 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
    Commented Apr 7, 2014 at 4:01

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Apr 7, 2014 at 7:13
  • $\begingroup$ Yes. But do you need an exact expression or just some asymptotics? $\endgroup$
    – Bjørn Kjos-Hanssen
    Commented Apr 7, 2014 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
    Commented Apr 7, 2014 at 7:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .