1
$\begingroup$

The question can be described in the following way:

Suppose I have a finite language $\mathcal{L}$ over alphabet $\Sigma$.

I have a string that is composed of a concatenated series of $n$ instances of $w_i$ chosen randomly(uniformly, independently) from $\mathcal{L}$. I want to find the number of non-overlapping occurrences of another word $W$ over the same alphabet, in that string. Non-overlapping means that occurrences must have distinct positions ("11" occurs once in "111").

Are there standard tools to handle this? It is a bit similar to type 2 binominal distribution, but not exactly the same.

In my case, I have $$\mathcal{L}=\{a,ab\}$$
And $$W=aba$$

Thanks!

$\endgroup$
1
  • $\begingroup$ While not sure it is applied in a general setting, I think that sites.math.rutgers.edu/~zeilberg/gj.html is relevant to the problem (extension of Goulden Jackson method by John NOONAN and Doron ZEILBERGER . $\endgroup$ Commented Dec 5, 2019 at 18:57

1 Answer 1

2
$\begingroup$

I'm not sure about the general case, but your particular one is relatively easy.

Let $r$ be a word composed of $n$ instances of $u:=a$ and $v:=ab$ chosen randomly.

We notice that each non-overlapping occurrence of $W$ in $r$ starts with an instance of $v$, unless this instance comes immediately after an odd number of other instances of $v$ or ends $r$. It follows that if we decompose $r$ into copies of $u$, $vu$, $vv$, and possibly a single $v$ at the very end (notice that such a decomposition is unique), then the number non-overlapping occurrences of $W$ in $r$ equals the total number of $vu$ and $vv$ in the decomposition.

From the probabilistic perspective, each $u$ (or $v$ at the end) appears in the decomposition with probability $\frac{1}2$, while the probability of each of $vu$ and $vv$ is $\frac{1}{4}$. At the same time, $u$ and $v$ contribute $1$ to the number of instances (i.e., towards $n$), while $vu$ and $vv$ contribute $2$ here.

It follows that the probability $p_{n,k}$ to observe exactly $k$ non-overlapping occurrences of $W$ in $r$ equals the coefficient of $x^ny^k$ in $$ \sum_{i=0}^{\infty} (\frac{1}{2}x+\frac{1}{4}x^2y+\frac{1}{4}x^2y)^i (1+\frac{1}{2}x) = \frac{1+\frac{1}{2}x}{1-\frac{1}{2}x-\frac{1}{2}x^2y},$$ where the powers of $x$ account for the number of instances of $u,v$ in $r$, while the powers of $y$ account for the number of non-overlapping occurrences of $W$.

Extracting the coefficient of $y^k$, we get that that $p_{n,k}$ equals the coefficient of $x^n$ in $$\frac{1+\frac{1}{2}x}{1-\frac{1}{2}x}\left(\frac{\frac{1}{2}x^2}{1-\frac{1}{2}x}\right)^k,$$ which further implies that \begin{split} p_{n,k} &=\frac{1}{2^k}\left(-\frac{1}{2}\right)^{n-2k}\binom{-(k+1)}{n-2k}+\frac{1}{2^{k+1}}\left(-\frac{1}{2}\right)^{n-2k-1}\binom{-(k+1)}{n-2k-1}\\ &=\frac{1}{2^{n-k}}\binom{n-k}{n-2k}+\frac{1}{2^{n-k}}\binom{n-k-1}{n-2k-1}\\ &=\frac{1}{2^{n-k}}\binom{n-k}{k}\frac{2n-3k}{n-k}. \end{split}

$\endgroup$

You must log in to answer this question.

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