Affen an Schreibmaschine, Erwartungswert Stoppzeit für erscheinen eines Wortes, Martingale

06.05.2016, 14:56

Guppi12

Affen an Schreibmaschine, Erwartungswert Stoppzeit für erscheinen eines Wortes, Martingale

Hallo,

es geht um eine Aufgabe, wo mir meine Intution etwas anderes sagt, als meine Berechnung. Ich wollte fragen, ob jemand meine Intuition zurechtrücken kann:

Folgendes ist die Aufgabe: Wir haben einen Affen, der an einer Schreibmaschine zufällige (i.i.d) Buchstaben eintippt (ich denke, das Setting sollte bekannt sein). Dann haben wir eine Stoppzeit $\begin{eqnarray*} T \end{eqnarray*}$ , die angibt, wann das erste mal das Wort ABRACADABRA eingetippt wurde.

Als Erwarungswert habe ich $\begin{eqnarray*} \mathbb E[T] = 26^{11}+26^4+26 \end{eqnarray*}$ .

Wie ich darauf gekommen bin, zeigt aber, dass das nicht unabhängig von dem Wort ist. Ein Wort mit $\begin{eqnarray*} 11 \end{eqnarray*}$ paarweise verschiedenen Buchstaben wird früher erwartet, als ABRACADABRA, nämlich bereits nach $\begin{eqnarray*} 26^{11} \end{eqnarray*}$ Runden. Das geht komplett gegen meine Intuition, denn bei diesem Wort könnte ja zum Beispiel das folgende auftreten: Wir haben bereits ABRACA geschrieben. Jetzt kommt aber als nächstes kein D, sondern ein B. Bei paarweise verschiedenen Buchstaben müssten wir jetzt von vorne Anfangen, denn das A könnte bei p.w. verschiedenen Buchstaben ja nicht der Anfangsbuchstabe sein. Bei unserem Wort aber können wir immerhin noch das letzte A verwenden und sind nach dem Auftreten von B immerhin schon wieder bei AB. Nach meiner Intuition sollte daher das Wort ABRACADABRA früher erwartet werden, als eines mit p.w. verschiedenen Buchstaben. Kann mir da jemand auf die Sprünge helfen?

Hier die Lösung der Aufgabe: Wir machen ein Glücksspiel aus der Situation. Jedes Eintippen eines Buchstaben ist eine Runde, in jeder Runde kommt ein Spieler an den Tisch und setzt 1€ darauf, dass der erste Buchstabe von ABRACADABRA eingetippt wird. Verliert er, verlässt er den Tisch, gewinnt er, bekommt er das 26-fache seines Einsatzes und setzt alles darauf, dass der zweite Buchstabe von ABRACADABRA eingetippt wird. Das geht so weiter, bis er verliert oder bis das ganze Wort einmal eingetippt wurde. Dabei kommt in jeder Runde ein Spieler dazu, egal, ob andere Spieler den Tisch schon verlassen haben oder noch dabei sind.

Sei dann $\begin{eqnarray*} X_t \end{eqnarray*}$ des Gesamtverlust der Bank nach der Runde $\begin{eqnarray*} t \end{eqnarray*}$ . Offenbar ist $\begin{eqnarray*} (X_t)_{t\in\mathbb N} \end{eqnarray*}$ ein Martingal. Weiter gilt $\begin{eqnarray*} X_T = 26^{11}+26^4+26-T \end{eqnarray*}$ , denn zu diesem Zeitpunkt sind genau $\begin{eqnarray*} T \end{eqnarray*}$ Spieler ins Spiel eingestiegen, die der Bank alle 1€ gezahlt haben. Der Verlust der Bank ist zu diesem Zeitpunkt genau $\begin{eqnarray*} 26^{11}+26^4+26 \end{eqnarray*}$ , denn ein Spieler hat das volle Wort gewonnen, ein Spieler hat mit ABRA gewonnen und einer nur mit A. Alle anderen Spieler haben alle ihre Gewinne wieder an die Bank zurückgezahlt.

Eine Variante des Optional Sampling Theorem sagt uns nun, dass $\begin{eqnarray*} 0=\mathbb E[X_0] = \mathbb E[X_T] \end{eqnarray*}$ , woraus die Behauptung folgt.
(Die Variante, die ich meine, setzt $\begin{eqnarray*} \mathbb E[T]<\infty \end{eqnarray*}$ und $\begin{eqnarray*} |X_{t+1}-X_t|\leq K \end{eqnarray*}$ für alle $\begin{eqnarray*} t \end{eqnarray*}$ und ein festes $\begin{eqnarray*} K \end{eqnarray*}$ voraus, was sich beides recht leicht zeigen lässt.)

06.05.2016, 15:41

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Guppi12
Wir machen ein Glücksspiel aus der Situation. Jedes Eintippen eines Buchstaben ist eine Runde, in jeder Runde kommt ein Spieler an den Tisch und setzt 1€ darauf, dass der erste Buchstabe von ABRACADABRA eingetippt wird. Verliert er, verlässt er den Tisch, gewinnt er, bekommt er das 26-fache seines Einsatzes und setzt alles darauf, dass der zweite Buchstabe von ABRACADABRA eingetippt wird. Das geht so weiter, bis er verliert oder bis das ganze Wort einmal eingetippt wurde. Dabei kommt in jeder Runde ein Spieler dazu, egal, ob andere Spieler den Tisch schon verlassen haben oder noch dabei sind.

Sei dann $\begin{eqnarray*} X_t \end{eqnarray*}$ des Gesamtverlust der Bank nach der Runde $\begin{eqnarray*} t \end{eqnarray*}$ . Offenbar ist $\begin{eqnarray*} (X_t)_{t\in\mathbb N} \end{eqnarray*}$ ein Martingal. Weiter gilt $\begin{eqnarray*} X_T = 26^{11}+26^4+26-T \end{eqnarray*}$ , denn zu diesem Zeitpunkt sind genau $\begin{eqnarray*} T \end{eqnarray*}$ Spieler ins Spiel eingestiegen, die der Bank alle 1€ gezahlt haben. Der Verlust der Bank ist zu diesem Zeitpunkt genau $\begin{eqnarray*} 26^{11}+26^4+26 \end{eqnarray*}$ , denn ein Spieler hat das volle Wort gewonnen, ein Spieler hat mit ABRA gewonnen und einer nur mit A. Alle anderen Spieler haben alle ihre Gewinne wieder an die Bank zurückgezahlt.

Eine Variante des Optional Sampling Theorem sagt uns nun, dass $\begin{eqnarray*} 0=\mathbb E[X_0] = \mathbb E[X_T] \end{eqnarray*}$ , woraus die Behauptung folgt.

Clever! Kannte ich noch nicht, allerdimgs bin ich auf dem Teilgebiet auch nicht so firm.

---------------

Zitat:

Original von Guppi12
Ein Wort mit $\begin{eqnarray*} 11 \end{eqnarray*}$ paarweise verschiedenen Buchstaben wird früher erwartet, als ABRACADABRA, nämlich bereits nach $\begin{eqnarray*} 26^{11} \end{eqnarray*}$ Runden. Das geht komplett gegen meine Intuition, denn bei diesem Wort könnte ja zum Beispiel das folgende auftreten: Wir haben bereits ABRACA geschrieben. Jetzt kommt aber als nächstes kein D, sondern ein B. Bei paarweise verschiedenen Buchstaben müssten wir jetzt von vorne Anfangen, denn das A könnte bei p.w. verschiedenen Buchstaben ja nicht der Anfangsbuchstabe sein. Bei unserem Wort aber können wir immerhin noch das letzte A verwenden und sind nach dem Auftreten von B immerhin schon wieder bei AB. Nach meiner Intuition sollte daher das Wort ABRACADABRA früher erwartet werden, als eines mit p.w. verschiedenen Buchstaben. Kann mir da jemand auf die Sprünge helfen?

Ich versuche es mal mit einem eher konventionellen Zugang an einem total abgerüsteten Beispiel zu verdeutlichen: Nur zwei Buchstaben A,B und Wörtern der Länge 2.

Wort AA: In einer Sequenz der Länge $\begin{align*} n \end{align*}$ kommt AA nicht vor, wenn die A nur immer isoliert voneinander vorkommen. Es gibt $\begin{align*} \sum_{k=0}^{\left\lfloor \frac{n+1}{2}\right\rfloor} \binom{n+1-k}{k} \end{align*}$ solche Sequenzen.

Wort AB: In einer Sequenz der Länge $\begin{align*} n \end{align*}$ kommt AB nicht vor, wenn es nur einen B-Block beliebiger Länge, gefolgt von einem A-Block gibt (beide dürfen Länge Null haben), es gibt nur $\begin{align*} n+1 \end{align*}$ solche Sequenzen.

Für $\begin{align*} n\geq 3 \end{align*}$ gilt nun aber $\begin{align*} \sum_{k=0}^{\left\lfloor \frac{n+1}{2}\right\rfloor} \binom{n+1-k}{k} > \sum_{k=0}^1 \binom{n+1-k}{k} = 1+n \end{align*}$ , womit AA in der Sequenz mit geringerer Wahrscheinlichkeit vorkommt als AB, und das für jedes feste $\begin{align*} n \end{align*}$ . Damit muss die durchschnittliche Stoppzeit bis zum Erreichen von AA größer sein als für AB.

06.05.2016, 16:07

Guppi12

Auf diesen Beitrag antworten »

Ah ok. Da spielt also noch ein anderer Effekt mit herein. Bei deinem Beispiel haben wir jetzt zwar nicht mehr den Effekt dabei, der eigentlich in die andere Richtung gehen müsste, als die Rechnung belegt, nämlich, dass wir beim Wort ABRACADABRA bei einem Fehlschlag eventuell das Ende eines Fehlschlags als Anfang eines Erfolges verwenden können; das geht bei AA ja nicht.

Dafür sieht man an dem Beispiel aber gut, dass ein Wort mit unterschiedlichen Buchstaben noch von einem ganz anderen Effekt profitiert, der mir garnicht aufgefallen war und der den anderen Effekt anscheinend deutlich überwiegt. Damit ergibt das nun einen Sinn.

Recht herzlichen Dank smile

Neue Frage »

Antworten »

Affen an Schreibmaschine, Erwartungswert Stoppzeit für erscheinen eines Wortes, Martingale

Verwandte Themen