Probablility of string containing letters in order Suppose we have an alphabet containing $m+1$ symbols, $\{a, b, c, d, e,..., \$\}$, where $p = \Pr(a) = \Pr(b) =\cdots$, and $\Pr(\$) = 1 - (\Pr(a)+\Pr(b)+\cdots)=1-mp$.
For a random string of length $n$, what is the probability that the letters ${a, b, c, ...}$ (not including $\$$), occur in order (not necessarily consecutively)?  In other words, the string is of length n and satisfies the regular expression $*a*b*c*\cdots$.
Some clarifications:
I just need the letters to appear in order sometime.  So acbc is ok because it contains $abc$ in that order.
I do need all m letters to appear in order.
Letters can be repeated.
 A: Let's start answering a slightly different question. Given a random sequence of  symbols, $x_1,x_2,\ldots\in\{a,b,\ldots,z,\$\}$, where I let $z$ denote the $m$th and last letter in the alphabet, let $q_k$ denote the likelihood that $k$ is the first location for which $x_1\ldots x_k\sim*a*b*\cdots*z$.
Obviously, the likelihood $P_n$ that a random string of length $n$ contains the letters $a,b,\ldots,z$ in order, i.e. matches $*a*b*\cdots*z*$, is $P_n=\sum_{k\le n} q_k$.
We can describe $x_1\ldots x_k\sim *a*b*\cdots*z$ uniquely by selecting the first possible location of $a$, of $b$, etc. That corresponds to a string $[\hat{}a]^*a[\hat{}b]^*b\ldots[\hat{}z]^*z$ where $[\hat{}a]^*$ means an arbitrary number of characters that are not $a$, etc.
This gives us a set of $m-1$ locations amongst the first $k-1$ positions of the string for the first occurrence of the $m-1$ letters, which can be selected in ${k-1\choose m-1}$ different ways, plus position $k$ position for $z$. Each of these $m$ occurrences has probability $p$ of being $a, b, \ldots, z$ respectively. the remaining $k-m$ positions can be anything except the upcoming letter and so each have probability $1-p$. This makes
$$
q_k={k-1\choose m-1} p^m (1-p)^{k-m}.
$$
The probability $P_n=\sum_{k=m}^n q_n$ that the letters may be found in order in a string of length $n$ is then
$$
P_n=\sum_{k=m}^n {k-1\choose m-1} p^m (1-p)^{k-m}.
$$
Trying to simplify this (using Maple) gives an expression in terms of hypergeometric series, which doesn't add anything since the hypergeometric series is defined as such a sum.
