Consider a random string of length $n<\infty$ where each digit can be between 0-9 with equal probability and a substring of length $k<n$ consisting of only zeros.

What is the probability of observing at least two occurrences of the substring?

Assumption: The same digit can be used in more than one substring. For example: Let the substring we are looking for be "$0000$". We observe somewhere in the string:


and we will count this as two occurrences as

$\ldots 598\color{red}{0000}0723\ldots$ and $\ldots 5980\color{red}{0000}723\ldots$

My attempts at a solution: With $k=4$:

1) Instead of looking at it directly I have tried finding \begin{align} P(\text{"}0000\text{"} \text{ occurring }\geq 2) &= 1-P(\text{"}0000\text{"} \text{ occurring }<2)\\ &=1- P( \text{"}0000\text{"} \text{ not occuring}, \text{"}0000\text{"} \text{ occuring once}) \end{align} but as the occurrences overlap I'm not sure how to continue.

2) Consider a Markov chain with state probabilities \begin{align} p_{i,0} &= 0.9, \quad i=0,1,2,\ldots \\ p_{i,i+1} &= 0.1, \quad i= 1,2,\ldots \end{align} This is then the counting of the number of consecutive zeros. Finding the expected number of visits in state 4 and up I thought could lead me somewhere but a visit in state 5 implies a visit in state 4 so it would ... add one occurrence and not two.

  • $\begingroup$ I cannot think of an explicit way of calculating it. Is it even possible? And if not: what changes could be made to the setup so we could calculate the probabilities? $\endgroup$ – Therkel Sep 11 '14 at 20:58

This sounds like a job for the Goulden-Jackson cluster method. Doron Zeilberger and John Noonan have a gem of a paper (and Maple programs) about it. In short, this method takes a collection of "bad" words over a finite alphabet and efficiently produces a two-variable generating function for words of various lengths containing specified numbers of bad words. In other words, if $s$ is the variable representing the lengths of strings and $t$ is the variable representing the numbers of bad words and $f$ is the generating function, then the coefficient of $s^mt^n$ in $f$ gives the number of strings of length $m$ that have exactly $n$ bad words. These generating functions always turn out to be rational.

In your example, you want to calculate the probability of selecting a string of length $n$ from the alphabet with ten letters $\{0,\dots,9\}$ containing at least two occurrences of $0000$. In the method, this corresponds to the ten-letter alphabet with a single bad word $0000$. Zeilberger and Noonan's Maple program gives the corresponding generating function $$f(s,t)=-{\frac {{s}^{3}t-{s}^{3}+{s}^{2}t-{s}^{2}+st-s-1}{9\,t{s}^{4}-9\,{s}^ {4}+9\,{s}^{3}t-9\,{s}^{3}+9\,{s}^{2}t-9\,{s}^{2}-st-9\,s+1}} $$ To compute the probability of selecting such a string, you would need to compute the number of strings of length $n$ with absolutely no bad words, i.e. $[s^nt^0]f(s,t)=[s^n]f(s,0)$, and the number of strings of length $n$ with exactly one bad word, i.e. $[s^nt^1]f(s,t)=[s^n]\partial_t f(s,t)_{|t=0}$. Granted, computing these coefficients will take some work, but I think the problem is very do-able from this stage.

  • $\begingroup$ This is excellent and exactly what I was looking for. $\endgroup$ – Therkel Oct 9 '14 at 9:38

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.