# Of strings and substrings: A problem of probability

## Problem

Let $\Sigma=\{a, b\}$. Let $\Sigma^*$ denote the Kleene star of $\Sigma$: \begin{equation*} \Sigma^* = \{\varepsilon, a, b, aa, ab, ba, bb, aaa, aab, \ldots\} \end{equation*} where $\varepsilon$ is the empty string.

Let $y = x_1 x_2 \ldots x_n$ where $x_i\in \Sigma^*$. For every $x_i$, let \begin{align*} P(x_i = baa) &= 1/4 \\ P(x_i = a) &= 1/4 \\ P(x_i = \varepsilon) &= 1/4 \\ P(x_i = aa) &= 1/4 \end{align*} and $P(x_i = \sigma) = 0$ for all other $\sigma \in \Sigma^*$.

Let $y_i$ be the symbol at position $i$ in $y$.

Problem 1: Find $P(y_i = \sigma)$ for $\sigma \in \Sigma_1 = \{a, b\}$.

Problem 2: Find $P(y_i y_{i+1} = \sigma)$ for $\sigma \in \Sigma_2 = \{aa, ab, ba, bb\}$.

Problem 3: Find $P(y_i y_{i+1} \ldots y_{i+k} = \sigma)$ for $\sigma \in \Sigma_{k+1}$.

where $i$ is uniformly distributed in $[1,|y|-k]$, where $|y|$ is the length of $y$.

Furthermore, you may assume $n$ is very large ($n\rightarrow\infty$).

## Solution attempt

Let $P(y_i \prec \sigma)$ for $\sigma \in \Sigma^*$ denote the probability that $y_i$ was produced by $\sigma$: \begin{equation*} P\left(\bigcup_{\sigma \in \Sigma^*}(y_i \prec \sigma)\right) = 1 \end{equation*}

Therefore \begin{align*} P(y_i = a) &= P\left((y_i = a) \cap \bigcup_{\sigma \in \Sigma^*}(y_i \prec \sigma)\right) \\ &= P\left(\bigcup_{\sigma \in \Sigma^*} (y_i = a \cap y_i \prec \sigma)\right) \\ &= \sum_{\sigma \in \Sigma^*} P(y_i = a \cap y_i \prec \sigma) \\ &= \sum_{\sigma \in \Sigma^*} P(y_i = a | y_i \prec \sigma) P(y_i \prec \sigma) \end{align*}

It seems to me that $P(y_i \prec \sigma) \propto P(x_i = \sigma)$.

Hence $P(x_i = \sigma) = 0$ for $\sigma \not\in \{baa, a, \varepsilon, aa\}$.

Therefore, $P(y_i \prec \sigma) = 0$ for $\sigma \not\in \{baa, a, \varepsilon, aa\}$: \begin{align*} P(y_i = a) &= P(y_i = a | y_i \prec baa) P(y_i \prec baa) + P(y_i = a | y_i \prec a) P(y_i \prec a) \\ & \qquad + P(y_i = a | y_i \prec \varepsilon) P(y_i \prec \varepsilon) + P(y_i = a | y_i \prec aa) P(y_i \prec aa) \end{align*}

I think $P(y_i = a | y_i \prec \sigma)$ is the fraction of symbols in $\sigma$ that are $a$: \begin{equation*} P(y_i = a) = 2/3 \cdot P(y_i \prec baa) + P(y_i \prec a) + P(y_i \prec aa) \end{equation*}

It seems to me that $P(y_i \prec \sigma) \propto |\sigma|$ where $|\sigma|$ is the length of $\sigma$. This is because the longer a production is, all else being equal, the greater the probability of any symbol in the string having been produced by that production.

So it seems that $P(y_i \prec \sigma) \propto P(x_i = \sigma)|\sigma|$.

Beyond this, I'm unsure of how to proceed. Am I approaching this problem the right way?

Edit: I have indeed been able to prove that $P(y_i \prec \sigma) \propto P(x_i = \sigma)|\sigma|$. More precisely:

$$P(y_i \prec \sigma) = \frac{\lvert\sigma\rvert P(x=\sigma)}{\sum_{\sigma'}\lvert\sigma'\rvert P(x=\sigma')}$$

I then assume $y_i$ is a random symbol of $\sigma$ (so the probability is proportional to the number of occurrences of $y_i$ in $\sigma$).

## Numerical tests

Here is some code written in Mathematica illustrating the concept:

productions = {{b, a, a}, {a}, {}, {a, a}};
productionProbabilities = {1/4, 1/4, 1/4, 1/4};
n = 1000000;
string = Catenate[
RandomChoice[productionProbabilities -> productions, n]];
trials = 100000;
substringLength = 3;
counts = N[Counts[
Table[
index = RandomInteger[{1, Length[result] - substringLength + 1}];
substring =
Part[result, Range[index, index + substringLength - 1]],
{trials}
]
]/trials]


which in this particular run outputs

<|{a, a, a} -> 0.50071, {b, a, a} -> 0.16862, {a, a, b} ->
0.16545, {a, b, a} -> 0.16522|>

• The thing you describe as a "discrete random variable" does not seem to be anything near what the phrase usually denotes. Instead it looks like you want to talk about a "probability distribution on $\Sigma^*$". But then your talking about a "concatenation of $n$ elements of $X$" still doesn't make sense -- since $X$ is a function from $\Sigma^*$ to $[0,1]$, each of its elements will be an ordered pair of a string and a number -- how do you envisage concatenating such elements? – Henning Makholm Jul 29 '15 at 21:48
• The "Goulden-Jackson cluster method" is a sort of calculus for counting words according to occurrences of subwords that might be useful. See my answer here. – Jair Taylor Jul 29 '15 at 21:50
• Your notation/terminology seems confused, but I suspect you are considering $X$ to be a random variable with values in $\Sigma^*$. Then if $X_1, ..., X_n$ are i.i.d., each with the the same distribution as $X$, one can consider the distribution of the concatenation $Y = X_1...X_n$, and of functions such as $C(x,Y)=$ the number of substring occurrences of $x$ in $Y$, etc. – r.e.s. Jul 29 '15 at 23:23
• I have rewritten the question to make it clearer. – user76284 Jul 30 '15 at 14:12
• There seems to be an assumption here that $y_i$ necessarily exists for all $i$ up to $n$. This is not the case, since one of the $x_i$ has zero length. Perhaps this is related to the vague prescription "You may assume $n$ is very large." Does that mean that the question is actually about the limits of these probabilities as $n\to\infty$? – joriki Jul 31 '15 at 3:25