Upper bound on the probability of a subsequence in a string Given a random sequence $S$ over a discrete alphabet $\mathcal{A}$, such that $|\mathcal{A}| = n$, and $P(S_i=a) = \frac{1}{n},\ \forall a \in \mathcal{A}$, what is the probability that a smaller sequence $R$ of length $|R| = k$ (s.t. $k < |S|$) occurs at least one time in $S$?
I know that this probability depends on the subsequence considered. For example, for an alphabet $\{A, T, C, G\}$, in a sequence $S$ of 100 characters, the sequence $AAAAAA$ has a probability of $\approx 0.018$ of occurring, while the sequence $ACGTAG$ of same length has a higher probability of occurring ($\approx 0.022$).
This previous answer on StackExchange gives a way of computing this probability for a given sequence using Markov Chains:
https://stats.stackexchange.com/a/362638/281902
However, what I'm looking for is an upper bound for the probability of any given subsequence of size $k$ to appear in a larger string of size $l$. Is there any way to compute this using anything other than simulation?
 A: (Esentially copied from this answer.)
Let $m$ be the length of the full sequence $S$ (indexed from $i=1$), while $k$ is the length of the subsequence $R$.
Let $Z_i=1$ ($i=1,2 \cdots m-k+1$) if the subsequence appears starting at position $i$, $0$ otherwise. Let $X=\sum Z_i$ be the total number of occurrences.
Then  $$E[X]= \sum E[Z_i] = \sum P(Z_i=1)= (m-k+1) n^{-k}$$
But by Markov inequality
$$P(X\ge1) \le E[X]$$
Hence the probability that any given subsequence $R$ appears is bounded by
$$ P(X\ge1) \le \frac{m-k+1}{n^{k}} \tag 1$$
In your example, this gives $\frac{95}{4096}=0.0231933$ - which (perhaps surprinsingly) looks quite tight.

Incidentally: If we assume that the variables $Z_i$ are independent  we'd get
$$P(X\ge 1) = 1-\prod P(Z_i=0)=1-(1-n^{-k})^{m-k+1} \tag2$$
(but , of course, the assumption is false and the equality does not hold).
Now,  for large $m$ the first order term is the bound given in $(1)$. It's not clear for me if one could assert that $(2)$ also works as a bound (I guess not). In the example above, it gives $0.0229292$.
