Brutomolecule: hacking biological defences (Part I)

Probability Level 5

$\underline{\text{Breach-times: randomly guessing finite sequences.}}$

Fix a finite alphabet, $\Sigma$ , with $|\Sigma|>1$ , such as $\Sigma=\{G,C,A,T\}$ or $\{H,T\}$ or $\{a,b,c,\ldots,z\}$ or the ascii-characters, etc. Let $s\in\{H,T\}^{<\omega}$ be a finite sequence . Consider now a fictional universe. In this universe biological organisms guard access to their cells via gateways. These gateways operate like a finite automata and require input of the right key, $s$ . To enter the key, a steady stream of molecules encoding letters in $\Sigma$ are fed in one at a time. The automata is built such that as long as the input-sequence is a strict initial segment of $s$ , the gateway remains in a passive expecting mode. Should one letter be wrong, the input string of molecules is destroyed ( rejected ) including the bad letter, and the input sequence starts from scratch with the next incoming molecules. If, on the other hand, the sequence, $s$ , is achieved, the gateway transitions to an accepted state and access to the cell is granted.

Enter now the Brutomolecule , a life-form trying to access organisms in distant solar systems. It is an entity, which sends signals into the far reaches of the universe and tries to breach any organisms it encounters by inducing and transmitting a stead stream of randomised molecules $X=X_{0}X_{1}X_{2}\ldots\in\Sigma^{\omega}$ . Given any fixed organism, let $T_{s}(X)$ or simply $T_{s}$ denote the breaching time : the ‘time’ it takes to gain entrance through a gateway with key $s\in\Sigma^{<\omega}$ . Working with the above definitions, here are some simple examples with the alphabet $\Sigma=\{G,C,A,T\}$ and the key $s=TTG$ :

if $X=\overline{TTG}HTTTTG\ldots$ , then $T_{s}=3$ ;
if $X=TTT\overline{TTG}GTTTTG\ldots$ , then $T_{s}=6$ .
if $X=GGGGG\overline{TTG}TT\ldots$ , then $T_{s}=8$ ;

Here is a more involved example demonstrating the mercilessness of rejection. Let $s=TATTATTT$ :

if $X=GGGGTATTTATTATTTGGGG\overline{TATTATTT}GA\ldots$ , then $T_{s}=29$ .

Note, that it does not hold, that $T_{s}=17$ , since the highlighted subsequence $GGGGTATT\overline{TATTATTT}GA\ldots$ is never inputted into the gateway. This in turn is the case, as the sequence $GGGG\overline{TATTT}ATTATTTGA\ldots$ , which overlaps with the first occurrence of $s$ , is rejected upon the 9th letter and not the 8th, meaning that the subsequent sequence inputted does not come from $TATTATTTGA\ldots$ but rather $ATTATTTGA\ldots$ .

This example demonstrates, that in general $T_{s}\not\equiv$ the time it takes for the first occurrence of $s$ as a subsequence of $X$ .

Finally, to describe the Brutomolecule , we need to describe how exactly its randomised stream of molecules is built up. The sequence $X_{0}, X_{1},\ldots$ constitute iid (independent identically distributed) $\Sigma$ -valued random variables with $\mathbb{P}[X_{n}=\alpha]=p(\alpha)$ for all $\alpha\in\Sigma$ , where $p:\Sigma\longrightarrow[0,1]$ is a fixed distribution, which the Brutomolecule determines. And again, $X$ denotes the corresponding infinite sequence $X:=X_{0}X_{1}X_{2}\ldots\in\Sigma^{\omega}$ .

Task. Determine a general expression for $\mathbb{E}[T_{s}]$ for $s\in\Sigma^{<\omega}$ and enter its value under the setup $\Sigma=\{H,T\}$ with distribution $p(H)=\frac{1}{3}$ , $p(T)=\frac{2}{3}$ and for $s=TTHTHHT$ .

Problem continues in Part II .

This problem is sort of motivated by brilliant.org ’s exercise but takes things in a completely different direction.

The answer is 328.3125.

1 solution

R Mathe
Jun 3, 2018

For any finite sequence $t\in\Sigma^{<\omega}$ let $p(t):=\mathbb{P}[X\supset t]$ the probability that the random sequence $X$ starts with $t$ . Given the distribution of the $X_{n}$ , it is easy to see that $p(t)=\prod_{i<|t|}p(t(i))$ .

Now fix $s\in\{H,T\}^{<\omega}$ . Given any fixed value $X=x\in\Sigma^{\omega}$ there are $|s|+1$ mutually exclusive possibilities:

Case $n$ , with $0\leq n<|s|$ : $x\supseteq s\vert n$ and $x\nsupseteq s\vert(n+1)$ . This case occurs with probability $\mathbb{P}[X\supseteq s\vert n]-\mathbb{P}[X\supseteq s\vert (n+1)]=p(s\vert n)-p(s\vert (n+1))$ .
Case $|s|$ : $x\supseteq s$ . This case occurs with probability $\mathbb{P}[X\supseteq s]=p(s)$ .

Under case $n<|s|$ , the input is rejected at position $n+1$ and the sequence $B_{\leftarrow}^{n+1}x$ awaits being inputted, where $B$ is the backwards-shift operator, so $T_{s}(x)=n+1+T_{s}(B_{\leftarrow}^{n+1}x)$ . Under case $n=|s|$ , the first $|s|$ molecules are accepted, so $T_{s}(x)=|s|$ .

It follows that

$\begin{array}{c}[mc]{rcl} \mathbb{E}[T_{s}] &= &\sum_{n<|s|}\mathbb{P}[\text{Case \$n\$}]\cdot\mathbb{E}[T_{s}\mid\text{Case \$n\$}] +\mathbb{P}[\text{Case \$|s|\$}]\cdot\mathbb{E}[T_{s}\mid\text{Case \$|s|\$}]\\ &= &\sum_{n<|s|}(p(s\vert n)-p(s\vert (n+1)))\cdot(n+1+\mathbb{E}[T_{s}(B_{\leftarrow}^{n+1}(X))\mid\text{Case \$n\$}]) +p(s)\cdot|s|\\ \end{array}$

Since the $X_{n}$ are iid, it follows that the process $X$ is memoryless and, in terms of its distribution, shift-invariant. Thus $\mathbb{E}[T_{s}(B_{\leftarrow}^{n+1}(X))\mid\text{Case \$n\$}]=\mathbb{E}[T_{s}(B_{\leftarrow}^{n+1}(X))]=\mathbb{E}[T_{s}(X)]=\mathbb{E}[T_{s}]$ . This yields

$\begin{array}{c}[mc]{rcl} \mathbb{E}[T_{s}] &= &p(s)\cdot|s|+\sum_{n<|s|}(p(s\vert n)-p(s\vert (n+1)))\cdot(n+1+\mathbb{E}[T_{s}])\\ &= &p(s)|s|+\sum_{n<|s|}np(s\vert n)-(n+1)p(s\vert (n+1)) +\sum_{n<|s|}p(s\vert n) +\sum_{n<|s|}(p(s\vert n)-p(s\vert (n+1)))\mathbb{E}[T_{s}]\\ &= &p(s)|s|+0p(s\vert 0)-|s|p(s\vert |s|) +\sum_{n<|s|}p(s\vert n) +(p(s\vert 0)-p(s\vert |s|))\mathbb{E}[T_{s}]\\ &= &\sum_{n<|s|}p(s\vert n)+(1-p(s))\mathbb{E}[T_{s}]\\ \end{array}$

Rearranging yields the general expression:

$\mathbb{E}[T_{s}] = \dfrac{\sum_{n<|s|}p(s\vert n)}{p(s)}$

With the concrete inputs, one has under the setup $\Sigma=\{H,T\}$ with distribution $p(H)=\frac{1}{3}$ , $p(T)=\frac{2}{3}$ and for $s=TTHTHHT$ :

pH=1/3;
pT=2/3;
ps = [pT,pT,pH,pT,pH,pH,pT]; % s=TTHTHHT
c = cumprod([1,ps]);
ExT = sum(c(1:end-1))/c(end);
disp(ExT); % —> expected time is 328.3125

Brutomolecule: hacking biological defences (Part I)

The answer is 328.3125.

1 solution

0 pending reports