Probabilidade de letras ocorrerem em ordem em uma sequência

Suponhamos que temos um alfabeto contendo $m+1$ símbolos, $\{a, b, c, d, e,..., \$\}$ , em que $p = \Pr(a) = \Pr(b) =\cdots$ e $\Pr(\$) = 1 - (\Pr(a)+\Pr(b)+\cdots)=1-mp$ .

Para uma sequência aleatória de comprimento $n$ , qual é a probabilidade de as letras ${a, b, c, ...}$ (não incluir $\$$ ) ocorrerem em ordem (não necessariamente consecutivamente)? Em outras palavras, a cadeia tem comprimento $n$ e satisfaz a expressão regular $*a*b*c*\cdots$ .

Alguns esclarecimentos:

Eu só preciso que as letras apareçam em algum momento. Portanto, o $acbc$ está ok porque contém $abc$ nessa ordem.

Eu preciso que todas as $m$ letras apareçam em ordem.

Cartas podem ser repetidas.

Essa expressão regular representa uma cadeia de Markov em estados correspondentes a um estado inicial e a cada uma das letras. É feita uma transição de para , de para , ... e da penúltima letra para a última, sempre com probabilidade . Caso contrário, o estado permanece o mesmo. O estado final é um estado absorvente: quando atingido, todas as letras são observadas em sequência.s s um um b $m+1$$s$$s$$a$$a$$b$$p$

Em termos dos estados , a matriz de transição é$(s, a, b, \ldots)$

$$\mathbb{P}_m = \pmatrix{1-p & p & 0 &\cdots & 0\\ 0 & 1-p & p &\cdots & 0 \\ \vdots & 0 & \ddots & p & \vdots \\ 0 & \cdots & 0 &1-p & p\\ 0 & 0 & \cdots & 0 & 1 }$$

Técnicas algébricas lineares padrão (a forma normal de da Jordânia e sua matriz de mudança de base são simples e esparsas, tornando isso bastante fácil) estabelecem que para a última entrada na primeira linha do poder da matriz é n≥m P n $\mathbb{P}_m$$n\ge m$$\mathbb{P}_m^n$

$$\mathbb{P}_m^n(1,m+1) = p^m \sum_{i=0}^{n-m} \binom{m-1+i}{m-1}(1-p)^i.$$

Essa é a chance de atingir o estado de absorção a partir do estado inicial após transições: responde à pergunta. Se desejar, ele pode ser expresso em "forma fechada" em termos de uma função Hipergeométrica como$n$

$$\mathbb{P}_m^n(1,m+1) =1-p^m \binom{n}{m-1} (1-p)^{-m+n+1} \, _2F_1(1,n+1;n+2-m;1-p).$$

A soma tem uma agradável interpretação combinatória. Seja a posição em que a última letra ocorre pela primeira vez. É precedido por uma sequência (possivelmente vazia) de não s, cada uma com uma chance de de ocorrer; então um com uma chance de ocorrer; então uma sequência (possivelmente não vazia) de não- s, etc. Há nos quais colocar a primeira aparição de um , depois a primeira aparição de a depois disso, etc. Assim - incluindo a primeira aparição da última letra na posição - a probabilidade éa 1 - p a p b ( m - 1 + $m+i$$a$$1-p$$a$$p$$b$ abm+i ( m-1+$\binom{m-1+i}{m-1}$$a$$b$$m+i$m+0m+(n-m$\binom{m-1+i}{m-1}p^m(1-p)^k$ . Isso fornece um termo da soma. Assim, a soma divide as seqüências de acordo com o local onde a última letra ocorre pela primeira vez, que pode estar em qualquer lugar da posição a essas são obviamente desarticuladas - e acrescenta suas probabilidades.$m+0$$m+(n-m)$

Como um exemplo simples para esclarecer a interpretação, suponha e considere . Existem quatro sequências de três símbolos, cada um de probabilidade , e três outras sequências de probabilidade , na qual os símbolos e aparecem na seguinte ordem:n = 3 p 3 p 2 ( 1 - 2 p ) um $m=2$$n=3$$p^3$$p^2(1-2p)$$a$$b$

$$aab, aba, abb, bab; ab\$,a\$b, $ab.$$

A chance, portanto, é

$$4p^3 + 3p^2(1-2p) = 3p^2 - 2p^3 = p^2(3-2p) = p^2(1 + 2(1-p)) = \mathbb{P}_2^3(1,3).$$

A interpretação combinatória é que a expressão regular ^ab(com na posição ) ocorre com probabilidade ; e , com na posição , ocorre de duas maneiras como e , cada uma com probabilidade .2 p 2 b 3 p 2 ( 1 - p $b$$2$$p^2$^[^a]*a[^b]*b$b$$3$^a[^b]b^[^a]ab$p^2(1-p)$

Por "As letras podem ser repetidas", você quer dizer que abbc é uma string válida? Eles 'aparecem em ordem'?

Caso contrário, parece ser a resposta para mim. é a probabilidade de que em um determinado espaço de caracteres não exista essa combinação, você a estende a todos os espaços possíveis de caracteres 1 - p m m n - m + 1 $1 - (1-p^m)^{n-m+1}$$1-p^m$$m$$n-m+1$$m$

Se sim, você tem um limite inferior