Wahrscheinlichkeit, sich zu wiederholen

27.08.2019, 01:44

Julietta Grimani

Wahrscheinlichkeit, sich zu wiederholen

Meine Frage:
Hallo,

folgendes Problem. Gegeben sei ein Zeichengenerator, der pro Tag willkürlich aus den 6 Elementen A, B, C, X, Y, Z zehn Zeichenketten von 1 bis 4 Elementen Länge erzeugt, wobei die Elemente beliebig oft vorkommen können und die Reihenfolge eine Rolle spielt. Wie kann man die Wahrscheinlichkeit für die Zeichenkette Nr. X berechnen, dass sie wenigstens schon einmal (vielleicht auch mehrmals) von diesem Zeichengenerator generiert worden ist, sich also wiederholt?

Meine Ideen:
Für die erste Zeichenkette ist sie klarerweise null, ist die Wahrscheinlichkeit für die zweite Zeichenkette, sich zu wiederholen dann 1/(6^1 + 6^2 + 6^3 + 6^4), für die dritte Zeichenkette 2/(6^1 + 6^2 + 6^3 + 6^4) usw.?

27.08.2019, 03:09

Juliette Grimani

Auf diesen Beitrag antworten »

RE: Wahrscheinlichkeit, sich zu wiederholen
Oder doch $\begin{eqnarray*} \left( \frac{1}{6^{1} + 6^{2} + 6^{3} + 6^{4}}\right)^\left({X-1}\right) \end{eqnarray*}$ ? verwirrt

27.08.2019, 05:13

Dopap

Auf diesen Beitrag antworten »

RE: Wahrscheinlichkeit, sich zu wiederholen
Das wird ein wenig schwieriger.
Der Generator G produziert Worte ( Tupel ) von 1 bis 4 Länge. Der Zeichenvorrat beträgt 6 Zeichen. Pro Tag erzeugt er 10 Worte.

Annahme I: jede Wortlänge ist gleichwahrscheinlich 1/4

Annahme II: die Bündelung in Tagen ist ohne Bedeutung.

$\begin{eqnarray*} \Rightarrow \end{eqnarray*}$ Wie groß ist die Wkt, dass er nach einer vorgegebenen Anzahl n von Worten ein Wort direkt im Anschluss wählt, das mindestens schon einmal produziert hat?

Es gibt $\begin{eqnarray*} 6^4=1296 \end{eqnarray*}$ Worte der Länge 4 mit jeweils $\begin{eqnarray*} p_4=\tfrac{1}{5184} \end{eqnarray*}$
Es gibt $\begin{eqnarray*} 6^3= 216 \end{eqnarray*}$ Worte der Länge 3 mit leweils $\begin{eqnarray*} p_3=\tfrac{1}{864} \end{eqnarray*}$
Es gibt $\begin{eqnarray*} 6^2=36 \end{eqnarray*}$ Worte der Länge 2 mit jeweils $\begin{eqnarray*} p_2=\tfrac{1}{144} \end{eqnarray*}$
Es gibt $\begin{eqnarray*} 6^1=6 \end{eqnarray*}$ Worte der Länge 1 mit jeweils $\begin{eqnarray*} p_1=\tfrac{1}{24} \end{eqnarray*}$
------------------------------------------------------------------
Es gibt 1554 Worte

ich stopp hier mal, da es spät ist und unklar ist, ob du es so gemeint hast oder eher so,
dass jedes Wort gleichwahrscheinlich mit $\begin{eqnarray*} p_w=\tfrac {1}{1554} \end{eqnarray*}$ auftritt ?
-----------------------------------------------
Eine andere Frage wäre, ob ein Text der Länge n ein bestimmtes Wort bei $\begin{eqnarray*} p_w=\tfrac {1}{1554} \end{eqnarray*}$ mindestens einmal enthält?

27.08.2019, 09:12

HAL 9000

Auf diesen Beitrag antworten »

Es ist in der Tat das erste, was hier mal zu klären ist, ob das Auswürfeln der Worte gemäß

Zitat:

Original von Dopap
jede Wortlänge ist gleichwahrscheinlich 1/4

oder doch

Zitat:

Original von Dopap
oder eher so, dass jedes Wort gleichwahrscheinlich mit $\begin{eqnarray*} p_w=\tfrac {1}{1554} \end{eqnarray*}$ auftritt ?

erfolgt. Der Problembeschreibung ist das nicht zu entnehmen, den Termen unter "Meine Ideen" nach soll es wohl eher das letztgenannte Modell sein? Ich gehe im folgenden mal davon aus, es handelt sich daher um eine diskrete Gleichverteilung auf den $\begin{eqnarray*} n=6^4+6^3+6^2+6^1=1554 \end{eqnarray*}$ möglichen Zeichenketten.

Die Formulierung "Zeichenkette Nr.X" verwirrt einigermaßen: Das hat jetzt nichts mit Element X zu tun, welches in den Zeichenketten vorkommen kann, oder?

Bei unabhängigem Auswürfeln ist die Wahrscheinlichkeit, im $\begin{eqnarray*} k \end{eqnarray*}$ -ten Versuch eine der $\begin{eqnarray*} (k-1) \end{eqnarray*}$ bisherigen Zeichenketten zu treffen gleich $\begin{eqnarray*} 1-\left(1-\frac{1}{n}\right)^{k-1} \end{eqnarray*}$ . Das ist wohlgemerkt die absolute Wahrscheinlichkeit, d.h., bei Unkenntnis der $\begin{eqnarray*} (k-1) \end{eqnarray*}$ bisher ausgewürfelten Zeichenketten.

Ist diese jedoch bekannt, d.h., man will die entsprechend bedingte Wahrscheinlichkeit dieses Ereignisses unter Kenntnis der Vorgeschichte berechnen, dann ist diese schlicht gleich $\begin{eqnarray*} \frac{m}{n} \end{eqnarray*}$ , wobei $\begin{eqnarray*} m \end{eqnarray*}$ die Anzahl unterschiedlicher Zeichenketten in der Vorgeschichte der $\begin{eqnarray*} (k-1) \end{eqnarray*}$ Zeichenketten ist (für $\begin{eqnarray*} k\geq 2 \end{eqnarray*}$ sind da sämtliche Werte $\begin{eqnarray*} 1\leq m\leq \min(k-1,n) \end{eqnarray*}$ denkbar).

27.08.2019, 12:09

Dopap

Auf diesen Beitrag antworten »

RE: Wahrscheinlichkeit, sich zu wiederholen
Dopap, manchmal muss man auch nur lesen :

Zitat:

Original von Juliette Grimani
Oder doch $\begin{eqnarray*} \left( \frac{1}{6^{1} + 6^{2} + 6^{3} + 6^{4}}\right)^\left({X-1}\right) \end{eqnarray*}$ ? verwirrt

deutet auf gleichverteilte Worte und $\begin{eqnarray*} X-1 \end{eqnarray*}$ auf Anzahl der bisherigen Versuche hin $\begin{eqnarray*} \Rightarrow \end{eqnarray*}$

bei Unkenntnis des bisherigen Textes ist $\begin{eqnarray*} P=1-\left(\frac{1553}{1554}\right)^{X-1} \end{eqnarray*}$ , dass das X-te Wort schon mindestens 1 mal vorhanden ist.

27.08.2019, 12:25

Juliette Grimani

Auf diesen Beitrag antworten »

Danke für eure Antworten. Ich meinte es so, wie HAL 9000 es im letzten Absatz seines Beitrags aufgefasst hat. Es soll also die Wahrscheinlichkeit im k-ten Versuch (bei mir: Nr. X, sorry für die Terminologie) bei Kenntnis der bisherigen Ergebnisse (nennen wir es das Protokoll), eine schon im Protokoll enthaltene Zeichenkette zu treffen, also sich zu wiederholen, berechnet werden.

Noch eine Frage:

Nehmen wir an, ich weiß nichts über die Wahrscheinlichkeit, mit der der Generator die einzelnen Zeichenketten erzeugt, ich habe nur das Protokoll.

Sehe ich es richtig, dass ich die Wiederholungschance im k-ten-Versuch = $\begin{eqnarray*} \frac{m}{n} \end{eqnarray*}$ , also die Anzahl der bisher im Protokoll gelisteten verschiedenen Zeichenketten durch die Anzahl der möglichen Zeichenketten, berechnen kann und indirekt aus dem Protokoll ein vages Bild der Wahrscheinlichkeitsverteilung, mit der der Generator diese Zeichenketten erzeugt, erhalte, wenn die Anzahl der bisherigen Versuche groß genug ist?

Beispiel:
Ich lasse den Generator eine Million Zeichenketten erzeugen und stelle anhand des Protokolls fest, dass die eine Million Ergebnisse auf nur hundert verschiedene Zeichenketten entfällt. Kann ich dann für den einemillionundersten Versuch nicht nur sagen, dass die Wahrscheinlichkeit, sich zu wiederholen, $\begin{eqnarray*} \frac{100}{1554} \end{eqnarray*}$ ist, sondern darüber hinausgehende Aussagen zur Wahrscheinlichkeit, mit der der Generator diese Zeichenketten erzeugt, treffen?

27.08.2019, 15:32

HAL 9000

Auf diesen Beitrag antworten »

Ausgehend von einer Gleichverteilung kann man bestimmen, wie die Verteilung der zufälligen Anzahl $\begin{eqnarray*} M_k \end{eqnarray*}$ verschiedener Zeichenketten nach einer gewissen Anzahl $\begin{eqnarray*} k \end{eqnarray*}$ von Versuchen aussieht; bei $\begin{eqnarray*} k=1\,000\,000 \end{eqnarray*}$ dürfte die sich überwiegende auf das Maximum 1554 konzentrieren und nur noch "Spurenelemente" auf niedrigere Werte entfallen. Augenzwinkern

Exakt geht das übrigens so: Es sind $\begin{eqnarray*} P(M_1=1)=1 \end{eqnarray*}$ und $\begin{eqnarray*} P(M_1=m)=0 \end{eqnarray*}$ für $\begin{eqnarray*} m\neq 1 \end{eqnarray*}$ die Startwerte. Für $\begin{eqnarray*} k>1 \end{eqnarray*}$ gilt dann die Rekursion

$\begin{eqnarray*} P(M_k=m) = \frac{m}{n}P(M_{k-1}=m) + \left(1-\frac{m-1}{n}\right)P(M_{k-1}=m-1) \end{eqnarray*}$ für $\begin{eqnarray*} m=1,\ldots,\min(k,n) \end{eqnarray*}$

Wenn du also tatsächlich nur $\begin{eqnarray*} m=100 \end{eqnarray*}$ bei $\begin{eqnarray*} k=1\,000\,000 \end{eqnarray*}$ beobachtest, dann ist mit an Sicherheit grenzender Wahrscheinlichkeit davon auszugehen, dass hier keine Gleichverteilung auf den 1554 vorliegt. Aber welche das ist, das ist allein aus dem beobachteten $\begin{eqnarray*} m \end{eqnarray*}$ kaum rekonstruierbar - schon eher aus der Gesamtstatistik der $\begin{eqnarray*} k \end{eqnarray*}$ Einzelwerte, d.h. deren relative Häufigkeiten sind wie üblich die Schätzwerte für die Verteilungswahrscheinlichkeiten.

27.08.2019, 18:39

Dopap

Auf diesen Beitrag antworten »

mmh... so ist doch eine Normalverteilung mit beispielsweise $\begin{eqnarray*} \sigma = 10 \end{eqnarray*}$ vorstellbar.

Bei 100 =|Stichprobenmenge| verschiedenen Worten sind dann die seltensten Worte ca. $\begin{eqnarray*} 5 \sigma =50 \end{eqnarray*}$ vom häufigsten Wort entfernt und die 1 Mio Versuche haben bisher ( noch ) nicht mehr getroffene Worte produziert.

Das wahrscheinlichste $\begin{eqnarray*} \sigma \end{eqnarray*}$ müsste doch unter der Prämisse einer Normalverteilung berechenbar sein?

27.08.2019, 19:34

Juliette Grimani

Auf diesen Beitrag antworten »

RE: Wahrscheinlichkeit, sich zu wiederholen
Ich verstehe noch nicht ganz, wie bei hohen k-Werten die Abschätzung der Wahrscheinlichkeitsverteilung, mit der der Generator Zeichenketten erzeugt, aus m, also der Anzahl der bisher im Protokoll gelisteten verschiedenen Zeichenketten, die Berechnung der Wiederholungswahrscheinlichkeit beeinflusst. Anders gesagt: Gilt $\begin{eqnarray*} \frac{m}{n} \end{eqnarray*}$ nur für die Annahme, dass die Erzeugungswahrscheinlichkeit gleichverteilt ist? Wie ändert die Annahme, dass es sich nicht mehr um eine Gleichverteilung handelt, die Berechnung der Wiederholungswahrscheinlichkeit?

Wie ist überdies der Zusammenhang zwischen k und n, um eine Abschätzung aus m (gemessen an n) treffen zu können, ob der Generator jede Zeichenkette mit gleicher Wahrscheinlichkeit produziert oder sicher nicht mehr? Anders formuliert: Wie hoch muss k im Verhältnis zu n ausfallen, damit die aus der Betrachtung von m im Verhältnis zu n sich aufdrängende Annahme, es handle sich gar nicht mehr um eine gleichverteilte Erzeugungswahrscheinlichkeit, sicher nicht falsch ist?

27.08.2019, 20:53

HAL 9000

Auf diesen Beitrag antworten »

Wenn wir keine Gleichverteilung haben, sondern stattdessen irgendeine diskrete Verteilung $\begin{eqnarray*} p_1,\ldots,p_n \end{eqnarray*}$ auf den $\begin{eqnarray*} n \end{eqnarray*}$ Werten $\begin{eqnarray*} x_1,\ldots,x_n \end{eqnarray*}$ , dann ist die bedingte Wahrscheinlichkeit offensichtlich gleich $\begin{eqnarray*} \sum_{i\in V} p_i \end{eqnarray*}$ , dabei ist $\begin{eqnarray*} V \end{eqnarray*}$ die Menge (!) der Indizes $\begin{eqnarray*} i \end{eqnarray*}$ aller derjenigen $\begin{eqnarray*} x_i \end{eqnarray*}$ , die in der $\begin{eqnarray*} (k-1) \end{eqnarray*}$ -Vergangenheit bisher mindestens einmal aufgetreten sind - die Beschreibung ist komplizierter als der Sachverhalt an sich. smile

27.08.2019, 21:54

Juliette Grimani

Auf diesen Beitrag antworten »

Danke. Aber das setzt doch voraus, dass ich die diskrete Verteilung genau kenne, oder?

Meine Frage ist jedoch folgende:

Wenn ich einen Generator habe, von dem ich

a) weiß, wie lange er bisher gelaufen ist, also wie viele Zeichenketten er produziert hat (k),
b) auch weiß, dass er darauf programmiert ist, aus einem Zeichenvorrat von 6 verschiedenen Zeichen auf sonst nicht näher spezifizierte Weise Zeichenketten zu erzeugen, die eine Länge von 1 bis 4 Zeichen haben, wobei er diese Zeichen beliebig oft verwenden darf und die Reihenfolge der Zeichen eine Rolle spielt,
c) daher auch die Anzahl prinzipiell möglicher Zeichenketten n ermitteln kann,
d) zudem die Ergebnisse der Laufzeit k genau kenne (das Protokoll),
e) in diesem Protokoll die Anzahl m der unterschiedlichen Zeichenketten feststellen kann (die maximal = k für k < n ist),

und dann wissen will, wie hoch die Wahrscheinlichkeit ist, mit dem nächsten Versuch k+1 eine Zeichenkette zu erzeugen,
die schon wenigstens einmal vorgekommen ist, kann ich das, wenn ich annehme (aber nicht weiß), dass die Zeichenketten mit
gleicher Wahrscheinlichkeit erzeugt werden, mittels $\begin{eqnarray*} \frac{m}{n} \end{eqnarray*}$ berechnen.

Stelle ich aber nun im Protokoll bei sehr hohen k-Werten fest, dass m im Verhältnis zu n auffallend gering ist, muss ich doch annehmen,
dass keine Gleichverteilung für die Erzeugung der Zeichenketten vorliegt (ohne sie genau zu kennen). Was tue ich jetzt, um die Wahrscheinlichkeit, mit dem nächsten Versuch (k+1) eine Zeichenkette zu erzeugen, die schon wenigstens einmal vorgekommen ist, zu berechnen? Was sind sinnvolle Annahmen für die diskrete Verteilung, wenn ich nur das Protokoll habe? Ab welchen k-Werten im Verhältnis zu n ist das überhaupt sinnvoll? Bis zu welchen Werten fahre ich immer noch besser mit der Annahme, dass ich eine Gleichverteilung habe, also mit der Berechnung für die Wiederholungswahrscheinlichkeit durch $\begin{eqnarray*} \frac{m}{n} \end{eqnarray*}$ ?

28.08.2019, 08:10

HAL 9000

Auf diesen Beitrag antworten »

Ein hübsches Bombardement von Fragen, für die es aber leider keine zufrieden stellende Antwort geben kann.

Wenn man so gar nichts weiß über die Verteilung $\begin{eqnarray*} p_1,\ldots,p_n \end{eqnarray*}$ , kann es darauf schwerlich eine vernünftige Antwort geben: Wie soll man die Wahrscheinlichkeiten $\begin{eqnarray*} p_i \end{eqnarray*}$ derjenigen $\begin{eqnarray*} i \end{eqnarray*}$ schätzen, die in der gesamten vorherigen Historie nie aufgetreten sind? Und die sind ja entscheidend für diese Prognose!

Ersetzt man z.B. alle $\begin{eqnarray*} p_i \end{eqnarray*}$ in der Formel in meinem vorigen Beitrag durch deren Schätzungen "relative Häufigkeit in der bisherigen Historie", so kommt man zu dem wenig brauchbaren Resultat, dass mit Wahrscheinlichkeit 1 kein neues Wort im nächsten Versuch herauskommt. Jetzt könnte man noch versuchen, andere Schätzungen für die $\begin{eqnarray*} p_i \end{eqnarray*}$ zu versuchen, etwa auf Bayesscher Grundlage mit a-priori-Gleichverteilung und basierend auf der Historie, aber das ist alles ziemlich willkürlich.

28.08.2019, 14:28

Juliette Grimani

Auf diesen Beitrag antworten »

Vielen Dank für deine Mühen.

Dass $\begin{eqnarray*} \sum\limits_{i\in V}^{} p_{i} \end{eqnarray*}$ bei aus dem Protokoll ermittelten relativen Häufigkeiten der dort gelisteten Elemente als Wahrscheinlichkeitswerte eingesetzt immer 1 ergibt, also die wenig befriedigende Prognose lautet, dass nichts Neues unter der Sonne zu erwarten ist, ist mir jetzt klar.

Ein kleine "Bombe" noch ... smile

Zitat:

Wenn du also tatsächlich nur m=100 bei k=1000000 beobachtest, dann ist mit an Sicherheit grenzender Wahrscheinlichkeit davon auszugehen, dass hier keine Gleichverteilung auf den 1554 vorliegt.

Wie berechnet man diesen Zusammenhang von $\begin{eqnarray*} m \end{eqnarray*}$ , $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ , um zu dieser Aussage zu kommen?
Oder ist das einfach eine vernünftige Annahme im weitesten Sinne, die ich natürlich teilte, ohne sie weiter begründen zu können als psychologisch?

28.08.2019, 15:19

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Juliette Grimani
Wie berechnet man diesen Zusammenhang von $\begin{eqnarray*} m \end{eqnarray*}$ , $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ , um zu dieser Aussage zu kommen?

Mangelhaft, wie genau du die Beiträge liest, denn genau das habe ich oben doch detailliert beschrieben:

Zitat:

Original von HAL 9000
Ausgehend von einer Gleichverteilung kann man bestimmen, wie die Verteilung der zufälligen Anzahl $\begin{eqnarray*} M_k \end{eqnarray*}$ verschiedener Zeichenketten nach einer gewissen Anzahl $\begin{eqnarray*} k \end{eqnarray*}$ von Versuchen aussieht; [...]

Exakt geht das übrigens so: Es sind $\begin{eqnarray*} P(M_1=1)=1 \end{eqnarray*}$ und $\begin{eqnarray*} P(M_1=m)=0 \end{eqnarray*}$ für $\begin{eqnarray*} m\neq 1 \end{eqnarray*}$ die Startwerte. Für $\begin{eqnarray*} k>1 \end{eqnarray*}$ gilt dann die Rekursion

$\begin{eqnarray*} P(M_k=m) = \frac{m}{n}P(M_{k-1}=m) + \left(1-\frac{m-1}{n}\right)P(M_{k-1}=m-1) \end{eqnarray*}$ für $\begin{eqnarray*} m=1,\ldots,\min(k,n) \end{eqnarray*}$

Nun rechne es aus für $\begin{eqnarray*} n=1554 \end{eqnarray*}$ und $\begin{eqnarray*} k=1\,000\,000 \end{eqnarray*}$ !!!

EDIT: Ich hab es jetzt tatsächlich mal durchgerechnet, leider erstmal nur mit dem ungenauen "double"-Datentyp. Das Ergebnis für $\begin{eqnarray*} k=1\,000\,000 \end{eqnarray*}$ ist

$\begin{eqnarray*} P(M_k = m) < 10^{-300} \end{eqnarray*}$ für alle $\begin{eqnarray*} m=1,\ldots,1552 \end{eqnarray*}$
$\begin{eqnarray*} P(M_k = 1553) \approx 4.3\cdot 10^{-277} \end{eqnarray*}$

Der ganze "Rest" verbleibt für 1554, d.h. $\begin{eqnarray*} P(M_k=1554)\approx 1 \end{eqnarray*}$ stimmt sogar noch, wenn man auf 276 Nachkommastellen rundet - das meinte ich oben mit "Spurenelementen". Augenzwinkern

Bei $\begin{eqnarray*} k=10\,000 \end{eqnarray*}$ sieht es noch ganz anders aus.

Neue Frage »

Antworten »

Wahrscheinlichkeit, sich zu wiederholen

Verwandte Themen