Wahrscheinlichkeit, dass Buchstaben in einer Reihenfolge in einer Zeichenfolge vorkommen

8

m+1{a,b,c,d,e,...,$}p=Pr(a)=Pr(b)=Pr($)=1(Pr(a)+Pr(b)+)=1mp

Wie groß ist bei einer zufälligen Zeichenfolge der Länge die Wahrscheinlichkeit, dass die Buchstaben (ohne ) in der angegebenen Reihenfolge (nicht unbedingt nacheinander) auftreten? Mit anderen Worten, die Zeichenfolge hat die Länge und erfüllt den regulären Ausdruck .na,b,c,...$nabc

Einige Klarstellungen:

Ich brauche nur die Buchstaben, um irgendwann in der richtigen Reihenfolge zu erscheinen. So ist ok , weil es enthält in dieser Reihenfolge.acbcabc

Ich brauche alle Buchstaben, um in der richtigen Reihenfolge zu erscheinen.m

Buchstaben können wiederholt werden.

Andrew W.
quelle

Antworten:

11

Dieser reguläre Ausdruck repräsentiert eine Markov-Kette in Zuständen, die einem Startzustand und jedem der Buchstaben entsprechen. Ein Übergang erfolgt von nach , von nach , ... und vom vorletzten Buchstaben zum letzten, immer mit der Wahrscheinlichkeit . Ansonsten bleibt der Zustand gleich. Der Endzustand ist ein absorbierender Zustand: Wenn er erreicht wurde, wurden alle Buchstaben nacheinander beobachtet.m+1ssaabp

In Bezug auf die Zustände ist die Übergangsmatrix(s,a,b,)

Pm=(1pp0001pp00p001pp0001)

Standardmäßige lineare algebraische Techniken (die jordanische Normalform von und ihre Änderung der Basismatrix sind einfach und spärlich, was dies ziemlich einfach macht) legen fest, dass für der letzte Eintrag in der ersten Zeile des Matrixleistung istPmnmPmn

Pmn(1,m+1)=pmi=0nm(m1+im1)(1p)i.

Dies ist die Chance, nach Übergängen vom Startzustand aus den absorbierenden Zustand zu erreichen : Sie beantwortet die Frage. Wenn Sie möchten, kann es in "geschlossener Form" in Form einer hypergeometrischen Funktion als ausgedrückt werdenn

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

Die Summe hat eine angenehme kombinatorische Interpretation. Sei die Position, an der der letzte Buchstabe zuerst auftritt. Es wird durch eine (möglicherweise leere) Folge von nicht - voraus s, jeweils mit einer Chance auftritt; dann ein mit einer Chance auftritt; dann eine (möglicherweise nicht leere) Folge von Nicht- usw. Es gibt Stellen, an denen das erste Auftreten eines und dann das erste Auftreten von platziert werden kann a danach usw. Somit ist - einschließlich des ersten Auftretens des letzten Buchstabens in Position - die Wahrscheinlichkeitm+ia1papb(m1+im1)abm+i(m1+im1)pm(1p)k . Dies ergibt einen Term der Summe. Somit zerlegt die Summe die Sequenzen danach, wo der letzte Buchstabe zuerst auftritt, was irgendwo von Position bis liegen kann - diese sind offensichtlich disjunkt - und addiert ihre Wahrscheinlichkeiten.m+0m+(nm)

Nehmen Sie als einfaches Beispiel zur Verdeutlichung der Interpretation und betrachten Sie . Es gibt vier Folgen von drei Symbolen mit der Wahrscheinlichkeit und drei weitere Folgen der Wahrscheinlichkeit , in denen die Symbole und der Reihe nach erscheinen:m=2n=3p3p2(12p)ab

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

Die Chance ist also

4p3+3p2(12p)=3p22p3=p2(32p)=p2(1+2(1p))=P23(1,3).

Die kombinatorische Interpretation ist, dass der reguläre Ausdruck ^ab(mit in Position ) mit der Wahrscheinlichkeit auftritt ; und mit in Position tritt es auf zwei Arten als und mit der Wahrscheinlichkeit .b2p2^[^a]*a[^b]*bb3^a[^b]b^[^a]abp2(1p)

whuber
quelle
0

Mit "Buchstaben können wiederholt werden" meinen Sie, dass abbc eine gültige Zeichenfolge ist? Sie erscheinen in der richtigen Reihenfolge?

Wenn nicht, scheint die Antwort für mich zu sein. ist die Wahrscheinlichkeit, dass es in einem gegebenen Raum von Zeichen keine solche Kombination gibt, dann erweitern Sie sie auf alle möglichen Räume von Zeichen1(1pm)nm+11pmmnm+1m

Wenn ja, dann haben Sie eine Untergrenze

gsmafra
quelle
Diese Formel stimmt nicht mit der vollständigen Aufzählung von Fällen überein, in denen und klein sind, daher kann sie im Allgemeinen nicht korrekt sein. mn
whuber