Suche Formel um die Wahrscheinlichkeit zu berechnen eine Zeichenkette der Länge n in einer größeren Zeichenkette zu find
-
Mal angenommen ich habe eine Zeichenkette der Länge 16 bestehend aus Nullen und einsen.
Bsp:
0001 1010 1011 1101Nun suche ich eine Formel um die Wahrscheinlichkeit zu Berechnen, daß eine andere Zeichenkette der Länge n in obiger Zeichenkette vorkommt.
Bsp. kommt die Zeichenkette "0" der Länge n=1 mit sehr hoher Wahrscheinlichkeit
in obiger Zeichenkette vor.Erhöhe ich diese Zeichenkette aber um n=n+1, so daß ich z.b. nach einer Zeichenkette "01" suche, dann sinkt die Wahrscheinlichkeit diese Zeichenkette in obiger Zeichenkette zu finden.
Je größer die Länge meiner zu findenden Zeichenkette wird, desto unwahrscheinlicher wird es, diese in obiger Zeichenkette zu finen.
Was ich nun suche ist ne Formel um das zu Berechnen.
-
um w'keiten zu berechnen brauchst du eine verteilung. wenn dir diese nicht bekannt ist, dann musst du sie schätzen.
-
Ich dachte da eher an folgendes.
In obigem Beispiel kann eine Ziffer z.b. 2 Zustände einnehmen.
Also 0 oder 1.
Die Wahrscheinlichkeit ist bei einer Ziffer bzw. der Länge 1 also 50 %.
Wenn ich die Länge nun um n=n+1 erhöhe, also die Länge 2 habe, dann habe ich 2^2=4 Möglichkeiten. Die Wahrscheinlichkeit, daß eine Kombination richtig ist, sinkt also auf 25 %.Und das muß jetzt halt nur noch mit der übergeordneten Zeichenkette der Länge 16 verbunden werden.
-
M.E. mußt du das über die umgekehrte Wahrscheinlichkeit berechnen, d.h. 1 - X, wobei X in deinem Fall (bei 2 Zeichen (nur '0' und '1') und einem Text der Länge 16) dann (3/4)^15 wäre (^ als Potenzierung und 15 weil es ja bei einem Text der Länge 16 nur 15 Matches geben kann).
Ergebnis wäre dann konkret: 1 - (3/4)^15 = 1 - 0.0133634 = 0.9866365
(wobei jetzt eine Gleichverteilung von '0' und '1' angenommen wird)Für kürzere Texte ergäbe sich dann:
Länge 2: 1 - (3/4)^1 = 0.25
Länge 3: 1 - (3/4)^2 = 0.4375
Länge 4: 1 - (3/4)^3 = 0.578125
...Für andere Längen 'n' ändert sich dann entsprechend der Wert: statt 3/4 dann allgemein 1-(1/(2^n)) und der Exponent ändert sich dann auch entsprechend der Länge d.h. N-n+1.
-
Mathedau schrieb:
Die Wahrscheinlichkeit ist bei einer Ziffer bzw. der Länge 1 also 50 %..
Nicht zwangsläufig, das ist, was Jover mit der Verteilung meinte.
Wenn die Ziffer "fast immer" 1 ist, hast du z.B. eine Wahrscheinlichkeit von 95%, eine 1 zu bekommen und 5%, eine 0 zu bekommen. Dann wird das Ganze noch etwas komplizierter.
-
pumuckl schrieb:
Mathedau schrieb:
Die Wahrscheinlichkeit ist bei einer Ziffer bzw. der Länge 1 also 50 %..
Nicht zwangsläufig, das ist, was Jover mit der Verteilung meinte.
Wenn die Ziffer "fast immer" 1 ist, hast du z.B. eine Wahrscheinlichkeit von 95%, eine 1 zu bekommen und 5%, eine 0 zu bekommen. Dann wird das Ganze noch etwas komplizierter.Richtig lustig wird es erst, wenn die Wahrscheinlichkeit eine 0 oder 1 zu bekommen auch noch von den vorherigen Ergebnissen abhängt. Hmm, wenn ich gerade nichts besseres zu tun hätte würde ich das sogar der Übung halber selbst mal durchrechnen...
-
Mir erscheint das Problem schon ziemlich schwierig, wenn die 0en und 1en im Basistext unabhängig voneinander mit einer Wahrscheinlichkeit von 50% gezogen werden.
Nehmen wir mal einen Basistext mit 3 Zeichen und einen Suchtext mit 2 Zeichen. Dann gibt es 8 mögliche Basistexte (000, 001, ..., 111). Der Suchtext 00 ist in 3en davon enthalten: 000, 001, 100; der Suchtext 01 ist in 4en enthalten: 001, 101, 010, 011. Die Wahrscheinlichkeit hängt also von der Struktur des Suchtextes ab, nicht nur von der Länge.
-
Th69 schrieb:
M.E. mußt du das über die umgekehrte Wahrscheinlichkeit berechnen, d.h. 1 - X, wobei X in deinem Fall (bei 2 Zeichen (nur '0' und '1') und einem Text der Länge 16) dann (3/4)^15 wäre (^ als Potenzierung und 15 weil es ja bei einem Text der Länge 16 nur 15 Matches geben kann).
Ergebnis wäre dann konkret: 1 - (3/4)^15 = 1 - 0.0133634 = 0.9866365
(wobei jetzt eine Gleichverteilung von '0' und '1' angenommen wird)Für kürzere Texte ergäbe sich dann:
Länge 2: 1 - (3/4)^1 = 0.25
Länge 3: 1 - (3/4)^2 = 0.4375
Länge 4: 1 - (3/4)^3 = 0.578125
...Für andere Längen 'n' ändert sich dann entsprechend der Wert: statt 3/4 dann allgemein 1-(1/(2^n)) und der Exponent ändert sich dann auch entsprechend der Länge d.h. N-n+1.
Danke.
D.h. ich kann das in folgende 2 Formeln zusammenpacken:
A) m = 1 -(1-(2^n))
1 - m^(k-1)
Wobei n die Länge der zu suchenden Zeichenkette
und k die Länge der durchsuchten Zeichenkette ist.Würde der Zeichensatz aber nicht nur aus Nullen und Einsen, sondern noch einem weiteren Zeichen bestehen, dann müßte ich m nicht in der 2. Potenzt, sondern in der 3. Potenz nehmen, richtig?
Das mit der Verteilung leuchtet mir jetzt ebenfalls ein.
-
das ganze kann man auch als 2stufiges zufallsexperiment sehen. in der ersten stufe wird eine folge von "buchstaben" gezogen. diese ist dann i. a. multinomialverteilt.
in der zweiten stufe werden dann aus dieser folge teilketten bestimmter länge gezogen. hier wird es dann kompliziert, da abhängiggeiten auftreten. das additionstheorem von wahrscheinlichkeiten muss hier angewendet werden.