Limite superior da probabilidade de uma subsequência em uma string

Question

Dada uma sequência aleatória $S$ sobre um alfabeto discreto $\mathcal{A}$, de tal modo que $|\mathcal{A}| = n$, e $P(S_i=a) = \frac{1}{n},\ \forall a \in \mathcal{A}$, qual é a probabilidade de que uma sequência menor $R$ de comprimento $|R| = k$ (st $k < |S|$) ocorre pelo menos uma vez em $S$?

Eu sei que essa probabilidade depende da subsequência considerada. Por exemplo, para um alfabeto$\{A, T, C, G\}$, em uma sequência $S$ de 100 caracteres, a sequência $AAAAAA$ tem uma probabilidade de $\approx 0.018$ de ocorrer, enquanto a sequência $ACGTAG$ de mesmo comprimento tem uma maior probabilidade de ocorrer ($\approx 0.022$)

Esta resposta anterior no StackExchange fornece uma maneira de calcular essa probabilidade para uma determinada sequência usando Cadeias de Markov:

https://stats.stackexchange.com/a/362638/281902

No entanto, o que estou procurando é um limite superior para a probabilidade de qualquer subsequência de tamanho$k$ para aparecer em uma sequência maior de tamanho $l$. Existe alguma maneira de calcular isso usando algo diferente de simulação?

Answer 1

(Essencialmente copiado desta resposta .)

Deixei $m$ seja o comprimento da sequência completa $S$ (indexado de $i=1$), enquanto $k$ é o comprimento da subsequência $R$.

Deixei $Z_i=1$ ($i=1,2 \cdots m-k+1$) se a subsequência aparecer começando na posição $i$, $0$de outra forma. Deixei$X=\sum Z_i$ ser o número total de ocorrências.

Então $$E[X]= \sum E[Z_i] = \sum P(Z_i=1)= (m-k+1) n^{-k}$$

Mas pela desigualdade de Markov

$$P(X\ge1) \le E[X]$$

Daí a probabilidade de que qualquer subseqüência dada $R$ aparece é limitado por

$$ P(X\ge1) \le \frac{m-k+1}{n^{k}} \tag 1$$

No seu exemplo, isso dá $\frac{95}{4096}=0.0231933$ - que (talvez surpreendentemente) parece bastante apertado.

---

A propósito: se assumirmos que as variáveis $Z_i$ são independentes nós obteríamos

$$P(X\ge 1) = 1-\prod P(Z_i=0)=1-(1-n^{-k})^{m-k+1} \tag2$$(mas, é claro, a suposição é falsa e a igualdade não é válida). Agora, para grande$m$ o termo de primeira ordem é o limite dado em $(1)$. Não está claro para mim se alguém poderia afirmar que$(2)$também funciona como um limite (acho que não). No exemplo acima, dá$0.0229292$.