# Calculating the probability that all possible length $r$ subwords exists in a string, with or without overlaps allowed

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.

• 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". Commented Apr 6, 2014 at 18:20
• @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. Commented Apr 7, 2014 at 4:01

• 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. Commented Apr 7, 2014 at 7:28