Probabilidade de letras ocorrerem em ordem em uma sequência

8

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

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 abc .

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.

Andrew W
fonte

Respostas:

11

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 pm+1ssaabp

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

Pm=(1pp0001pp00p001pp0001)

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 é nm P n mPmnmPmn

Pmn(1,m+1)=pmi=0nm(m1+im1)(1p)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 comon

Pmn(1,m+1)=1pm(nm1)(1p)m+n+12F1(1,n+1;n+2m;1p).

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 + im+ia1papb abm+i ( m-1+i(m1+im1)abm+im+0m+(n-m)(m1+im1)pm(1p)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+0m+(nm)

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 bm=2n=3p3p2(12p)ab

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

A chance, portanto, é

4p3+3p2(12p)=3p22p3=p2(32p)=p2(1+2(1p))=P23(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 )b2p2^[^a]*a[^b]*bb3^a[^b]b^[^a]abp2(1p)

whuber
fonte
0

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 m1(1pm)nm+11pmmnm+1m

Se sim, você tem um limite inferior

gsmafra
fonte
Essa fórmula não concorda com a enumeração completa de casos quando e são pequenos, portanto, geralmente não pode estar correto. nmn
whuber