Tupelmenge durch Kontraktionsabbildung bestimmen

16.06.2019, 15:31

Stein029

Tupelmenge durch Kontraktionsabbildung bestimmen

Meine Frage:
Hallo zusammen,
ich möchte einen Beweis zu einem Thema in der Stochastik nachvollziehen, dabei verstehe ich einen Teil des Beweises nicht so richtig. Es geht um die Verteilung der Länge der längsten Glückssträhne, z.b. beim Setzen auf Impair im Roulette-Spiel. $\begin{eqnarray*} X_{1},....,X_{n} \end{eqnarray*}$ sind unabhängig und es ist
$\begin{eqnarray*} \mathbb P(X_{j}=1)=p=1-P(X_{j}=-1) \end{eqnarray*}$ , $\begin{eqnarray*} j \geq 1 \end{eqnarray*}$

In dem Teil des Beweises, den ich nicht so richtig folgen kann, geht es um die Ermittlung der Wahrscheinlichkeitssumme folgender Schnitte:
$\begin{eqnarray*} \sum\limits_{1\leq i_{1}<...<i_{r}\leq n-k+1}^{} \mathbb P (A_{i1} \cap ...\cap A_{ir}) \end{eqnarray*}$

Die Ereignisse sind dabei als Serie von mindestens $\begin{eqnarray*} k \end{eqnarray*}$ direkt aufeinander folgender Treffer beginnend im j-ten Versuch definiert:
$\begin{eqnarray*} A_{j}:=\{X_{j-1}=-1, X_{j}=1,..., X_{j+k-1}=1 \} , j=2,...,n-k+1 \end{eqnarray*}$ und $\begin{eqnarray*} A_{1}:=\{ X_{1}=1,..., X_{k}=1 \} \end{eqnarray*}$

Für den Fall $\begin{eqnarray*} i_{s+1} -i_{s}\geq k +1 \end{eqnarray*}$ sind die Ereignisse stochastisch unabhängig, sodass die Wahrscheinlichkeit für $\begin{eqnarray*} \mathbb P (A_{i1} \cap ...\cap A_{ir}) \end{eqnarray*}$ gleich $\begin{eqnarray*} q^{r} *p_{kr} \end{eqnarray*}$ bzw. $\begin{eqnarray*} q^{r-1} *p_{kr} \end{eqnarray*}$ sind, je nachdem ob $\begin{eqnarray*} i_{1} \geq 2 \end{eqnarray*}$ oder $\begin{eqnarray*} i_{1} = 1 \end{eqnarray*}$ ist.

Nun zur eigentlichen Frage:
Die Anzahl der r-tupel $\begin{eqnarray*} (i_{1},..., i_{r}) \end{eqnarray*}$ mit $\begin{eqnarray*} 2\leq i_{1} < ... < i_{r} \leq n-k+1 \end{eqnarray*}$ und $\begin{eqnarray*} i_{s+1} -i_{s}\geq k +1 \end{eqnarray*}$ soll für jedes $\begin{eqnarray*} s=1,...,r-1 \end{eqnarray*}$ gleich dem Binominalkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r \end{pmatrix} \end{eqnarray*}$ sein, da die Menge dieser Tupel durch die Kontraktionsabbildung $\begin{eqnarray*} j_{v} := i_{v}-(v-1)k \end{eqnarray*}$ mit $\begin{eqnarray*} v=1,...r \end{eqnarray*}$ bijektiv auf die Menge aller Tupel $\begin{eqnarray*} (j_{1},..., j_{r}) \end{eqnarray*}$ mit $\begin{eqnarray*} 2\leq i_{1} < ... < i_{r} \leq n-k*r+1 \end{eqnarray*}$ abgebildet wird.
In Gleicherweise ist die Anzahl der r-Tupel $\begin{eqnarray*} (i_{1},..., i_{r}) \end{eqnarray*}$ mit $\begin{eqnarray*} 1 = i_{1} < ... < i_{r} \leq n-k+1 \end{eqnarray*}$ und $\begin{eqnarray*} i_{s+1} -i_{s}\geq k +1 \end{eqnarray*}$ gleich dem Binominalkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r-1 \end{pmatrix} \end{eqnarray*}$

Meine Ideen:
Ich verstehe hier leider nicht wie die Kontraktionsabbildung definiert ist und wie der Autor hier auf diese Abbildungsvorschrift gekommen ist und voraussetzt, dass diese bijektiv sei.
Mir würde schon helfen, wenn mir jemand erklären könnte wie die Abbildungsvorschrift $\begin{eqnarray*} j_{v} := i_{v}-(v-1)k \end{eqnarray*}$ zu verstehen ist und wie der Autor darauf gekommen ist.

Zugleich kann ich nicht nachvollziehen wie der Autor hier auf die angegebenen Binominalkoeffizienten gekommen ist.

Könnt ihr mir helfen diesen Beweis nachzuvollziehen? Ich bin euch für jede Hilfe dankbar!

17.06.2019, 09:54

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Stein029
Ich verstehe hier leider nicht wie die Kontraktionsabbildung definiert ist und wie der Autor hier auf diese Abbildungsvorschrift gekommen ist und voraussetzt, dass diese bijektiv sei.

Salopp gesagt:

Im aufsteigend geordneten $\begin{eqnarray*} i \end{eqnarray*}$ -Tupel soll ja zwischen zwei aufeinander folgenden Einträgen immer eine Lücke der Mindestgröße $\begin{eqnarray*} k+1 \end{eqnarray*}$ vorhanden sein. Tupelanzahlformeln (basierend auf dem Binomialkoeffizienten) kennt man aber nur für "normale" aufsteigend geordnete Tupel (das wäre hier dann das $\begin{eqnarray*} j \end{eqnarray*}$ -Tupel) d.h. dort hat man nur eine Lücke der Mindestgröße 1.

Und genauso konstruiert man nun die Abbildung von $\begin{eqnarray*} i \end{eqnarray*}$ - nach $\begin{eqnarray*} j \end{eqnarray*}$ -Tupel: Man verkürzt jede der $\begin{eqnarray*} (r-1) \end{eqnarray*}$ Lücken um den Betrag $\begin{eqnarray*} k \end{eqnarray*}$ , d.h.,

$\begin{eqnarray*} j_1 = i_1 \end{eqnarray*}$
$\begin{eqnarray*} j_2 = i_2-k \end{eqnarray*}$ , dann wird aus Bedingung $\begin{eqnarray*} i_2-i_1\geq k+1 \end{eqnarray*}$ die Bedingung $\begin{eqnarray*} j_2-j_1\geq 1 \end{eqnarray*}$
$\begin{eqnarray*} j_3 = i_3-2k \end{eqnarray*}$ , dann wird aus Bedingung $\begin{eqnarray*} i_3-i_2\geq k+1 \end{eqnarray*}$ die Bedingung $\begin{eqnarray*} j_3-j_2\geq 1 \end{eqnarray*}$
....
$\begin{eqnarray*} j_r = i_r - (r-1)k \end{eqnarray*}$ , dann wird aus Bedingung $\begin{eqnarray*} i_r-i_{r-1}\geq k+1 \end{eqnarray*}$ die Bedingung $\begin{eqnarray*} j_r-j_{r-1}\geq 1 \end{eqnarray*}$ .

Und genau das ist es, was du als Kontraktionsabbildung bezeichnest. Anschließend muss man sich nur noch Gedanken um den Wertebereich der Tupel machen, dazu betrachtet man sich den letzten Eintrag:

$\begin{eqnarray*} i_r\leq n-k+1 \end{eqnarray*}$ bedeutet $\begin{eqnarray*} j_r=i_r-(r-1)k\leq n-k+1-(r-1)k = n-rk+1 \end{eqnarray*}$ .

18.06.2019, 15:53

Math_2017

Auf diesen Beitrag antworten »

18.06.2019, 16:02

Stein029

Auf diesen Beitrag antworten »

Vielen Dank. Damit kann ich nun den Beweis auch an dieser Stelle nachvollziehen.
Eine Kleinigkeit hätte ich aber noch:

Dass der Autor nun auf die Binominalkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r \end{pmatrix} \end{eqnarray*}$ und $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r-1 \end{pmatrix} \end{eqnarray*}$ kommt, müsste doch daran liegen, dass er nun bei den j-Tupeln eine Obergrenze bei n-kr+1 konstruiert hat. Da aber $\begin{eqnarray*} (j_{1},..., j_{r}) \end{eqnarray*}$ mit $\begin{eqnarray*} 2\leq j_{1} < ... < j_{r} \leq n-k*r+1 \end{eqnarray*}$ minimal bei 2 beginnt, existiert also eine Menge von n-kr verschiedenen Objekten aus denen ich eben r verschiedene Objekte „ziehen möchte", also gilt $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r \end{pmatrix} \end{eqnarray*}$ . Ich hoffe, das ist soweit richtig.
Wie kommt der Autor aber im anderen Fall auf den Binominalkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r-1 \end{pmatrix} \end{eqnarray*}$ ? Liegt es daran, dass man bei eins beginnt (und somit das erste Ereignis aus dem Tupel fix ist) und daher nur noch (r-1) verschiedene Ereignisse im Tupel gesucht sind? Somit würde ja wiederum aus einer Menge von n-kr verschiedenen Objekten gezogen werden, da das erste Objekt bzw. Ereignis bereits fest ist und somit wieder aus der Menge $\begin{eqnarray*} 2\leq j_{1} < ... < j_{r} \leq n-k*r+1 \end{eqnarray*}$ die übrigen Möglichkeiten gesucht werden.

Ist meine Erklärung soweit richtig?

18.06.2019, 16:15

HAL 9000

Auf diesen Beitrag antworten »

Du meinst vermutlich das hier:

Zitat:

Original von Stein029
In Gleicherweise ist die Anzahl der r-Tupel $\begin{eqnarray*} (i_{1},..., i_{r}) \end{eqnarray*}$ mit $\begin{eqnarray*} 1 = i_{1} < ... < i_{r} \leq n-k+1 \end{eqnarray*}$ und $\begin{eqnarray*} i_{s+1} -i_{s}\geq k +1 \end{eqnarray*}$ gleich dem Binominalkoeffizienten $\begin{eqnarray*} \begin{pmatrix} n-kr \\ r-1 \end{pmatrix} \end{eqnarray*}$

Es ist $\begin{eqnarray*} i_1=1 \end{eqnarray*}$ fest, das können wir aus dem Spiel nehmen, außerdem ist $\begin{eqnarray*} i_2\geq i_1+k+1=k+2 \end{eqnarray*}$ . Hier nimmt man nun eine modifizierte Abbildung

$\begin{eqnarray*} j_v = i_{v+1}-vk-1 \end{eqnarray*}$ für $\begin{eqnarray*} v=1,\ldots,r-1 \end{eqnarray*}$ ,

damit entspricht das der Anzahl der streng monoton aufsteigend geordneten $\begin{eqnarray*} j \end{eqnarray*}$ -Tupel vom Umfang $\begin{eqnarray*} (r-1) \end{eqnarray*}$ aus $\begin{eqnarray*} \{1,\ldots,n-rk\} \end{eqnarray*}$ , letzteres wegen $\begin{eqnarray*} j_{r-1}=i_r-(r-1)k-1\leq n-k+1-(r-1)k-1=n-rk \end{eqnarray*}$ .

21.06.2019, 13:33

Stein029

Auf diesen Beitrag antworten »

Danke HAL 9000. Nun konnte ich diesen Beweis auch gut nachvollziehen.

Jetzt habe ich aber noch zum gleichen Thema, aber einen anderen Beweis, noch eine Frage. Daher hatte ich gedacht, dass ich besser hier nochmal nachfrage, anstatt ein neues Thema aufzumachen.
Hierbei geht es nämlich um die Monotonie von $\begin{eqnarray*} \mathbb P_{p}(R_{n}\geq k) \end{eqnarray*}$ in $\begin{eqnarray*} p \end{eqnarray*}$ ( $\begin{eqnarray*} R_{n} \end{eqnarray*}$ ist die Länge der längsten Serie direkt aufeinander folgender Treffer in einer Bernoulli-Kette der Länge n mit Trefferwahrscheinlichkeit p).

Der Satz sagt aus, dass die Überschreitungswahrscheinlichkeit $\begin{eqnarray*} \mathbb P_{p}(R_{n}\geq k) \end{eqnarray*}$ unter den gleichen Voraussetzungen wie zuvor bei festem $\begin{eqnarray*} n \end{eqnarray*}$ und $\begin{eqnarray*} k \end{eqnarray*}$ monoton wächst. Die Idee des Beweises ist ein sogenanntes Kopplungsargument. Dabei wird argumentiert, dass man die Zufallsvariablen $\begin{eqnarray*} X_{1},...,X_{n} \end{eqnarray*}$ als Funktionen von stochastisch unabhängigen und je im Einheitsintervall $\begin{eqnarray*} (0,1) \end{eqnarray*}$ gleichverteilten Zufallsvariablen $\begin{eqnarray*} U_{1},...,U_{n} \end{eqnarray*}$ schreibt, indem man $\begin{eqnarray*} X_{j}(w):=2\cdot 1 \{U_{j}(w)\leq p \} - 1 \end{eqnarray*}$ mit $\begin{eqnarray*} \omega \in \Omega \end{eqnarray*}$ und $\begin{eqnarray*} j=1,...,n \end{eqnarray*}$ setzt. $\begin{eqnarray*} U_{1},...,U_{n} \end{eqnarray*}$ sind dabei auf einem nicht weiter spezifizierten Grundraum $\begin{eqnarray*} \Omega \end{eqnarray*}$ definiert.
Daraus folgt dass die $\begin{eqnarray*} X_{1},...,X_{n} \end{eqnarray*}$ stochastisch unabhängig und identisch verteilt sind und wegen $\begin{eqnarray*} \mathbb P(U_{j}\leq p) =p \end{eqnarray*}$ soll $\begin{eqnarray*} \mathbb P(X_{j} = 1) =p=1-P(X_{j} =-1) \end{eqnarray*}$ gelten, sodass die im vorherigen Satz zugrunde liegende Annahme vorliegt.
Die Ungleichung $\begin{eqnarray*} p_{1} < p_{2} \end{eqnarray*}$ wirkt sich dabei dahingehend aus, dass $\begin{eqnarray*} 1\{U_{j}(w)\leq p_{1} \} \leq 1\{U_{j}(w)\leq p_{2} \} \end{eqnarray*}$ gilt und somit beim Übergang von $\begin{eqnarray*} p_{1} \end{eqnarray*}$ zu $\begin{eqnarray*} p_{2} \end{eqnarray*}$ gewisse Werte $\begin{eqnarray*} X_{j}(w) \end{eqnarray*}$ von $\begin{eqnarray*} -1 \end{eqnarray*}$ nach $\begin{eqnarray*} +1 \end{eqnarray*}$ wechseln können, was zur Folge hat, dass der von $\begin{eqnarray*} X_{1}(w),...,X_{n}(w) \end{eqnarray*}$ abhängende Wert von $\begin{eqnarray*} R_{n} \end{eqnarray*}$ nur größer werden kann.

Das ist der skizzenhafte Beweis.

Da ich mit solchen Kopplungsargumenten noch nie gearbeitet habe, habe ich hierbei so meine Probleme. Vor allem das Setzen von $\begin{eqnarray*} X_{j}(w):=2\cdot 1 \{U_{j}(w)\leq p \} - 1 \end{eqnarray*}$ kann ich nicht so ganz nachvollziehen. Ich weiß, dass entweder 2*1*1-1= 1 oder 2*1*0-1=-1 zu erwarten ist und somit hier ein Trick eingebaut wurde. Aber wann erhält man nun für $\begin{eqnarray*} \{U_{j}(w)\leq p \} \end{eqnarray*}$ den Wert 0 oder 1?
Und wieso folgt aus $\begin{eqnarray*} \mathbb P(U_{j}\leq p) =p \end{eqnarray*}$ dann die Annahme $\begin{eqnarray*} \mathbb P(X_{j} = 1) =p=1-P(X_{j} =-1) \end{eqnarray*}$ ? Bzw. wieso gilt das überhaupt?
Kann man diese Folgerungen nicht formal noch etwas verständlicher aufschreiben? Ich habe irgendwie das Gefühl, dass hier ein Schritt zum Nachvollziehen ausgelassen wurde.

Vielleicht kennst du dich mit solchen Kopplungsargumenten ja auch aus und könntest mir diesen Beweis auch noch etwas näher bringen. Ich würde mich jedenfalls sehr über Hilfe freuen! Diese zusätzlich konstruierte Zufallsvariable bringt mich doch ziemlich durcheinander.

23.06.2019, 20:11

Stein029

Auf diesen Beitrag antworten »

Hallo HAL 3000,
ich will gar nicht unhöflich erscheinen, dass ich noch mal nachfrage, aber ich bin mir nicht sicher, ob die Frage nun doch ein wenig untergegangen ist.

Ich wäre jedenfalls immer noch sehr an Hilfe interessiert.

Mir würde es schon sehr helfen, wenn man mir den Anfang des Beweises ein wenig erklären könnte, da ich diese Verteilung nicht nachvollziehen kann.

Zitat:

Original von Stein029
Dabei wird argumentiert, dass man die Zufallsvariablen $\begin{eqnarray*} X_{1},...,X_{n} \end{eqnarray*}$ als Funktionen von stochastisch unabhängigen und je im Einheitsintervall $\begin{eqnarray*} (0,1) \end{eqnarray*}$ gleichverteilten Zufallsvariablen $\begin{eqnarray*} U_{1},...,U_{n} \end{eqnarray*}$ schreibt, indem man $\begin{eqnarray*} X_{j}(w):=2\cdot 1 \{U_{j}(w)\leq p \} - 1 \end{eqnarray*}$ mit $\begin{eqnarray*} \omega \in \Omega \end{eqnarray*}$ und $\begin{eqnarray*} j=1,...,n \end{eqnarray*}$ setzt.

Könntest du mir hierbei noch mal helfen? Falls nicht, dann wäre es natürlich auch nicht schlimm. Ich möchte hier gar nicht drängeln und dich schon gar nicht mit meiner Nachfrage verärgern. So oder so schon mal vielen Dank und Entschuldigung der Nachfrage!
Viele Grüße!

24.06.2019, 10:15

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Stein029
Vor allem das Setzen von $\begin{eqnarray*} X_{j}(w):=2\cdot 1 \{U_{j}(w)\leq p \} - 1 \end{eqnarray*}$ kann ich nicht so ganz nachvollziehen.

Das ist nur die technische Umsetzung der stetigen Werte $\begin{eqnarray*} U_j(\omega)\in (0,1) \end{eqnarray*}$ in die diskreten $\begin{eqnarray*} X_j(\omega)\in\{-1,+1\} \end{eqnarray*}$ , so dass das mit den Wahrscheinlichkeiten "stimmt":

Alle Werte des ersteren mit $\begin{eqnarray*} \leq p \end{eqnarray*}$ werden in +1 transformiert (geschieht mit Wahrscheinlichkeit $\begin{eqnarray*} p \end{eqnarray*}$ wegen der stetigen Gleichverteilung der $\begin{eqnarray*} U_j \end{eqnarray*}$ ), die anderen mit $\begin{eqnarray*} >p \end{eqnarray*}$ entsprechend in -1 (geschieht mit Wahrscheinlichkeit $\begin{eqnarray*} 1-p \end{eqnarray*}$ ).

Steckt also nichts weiter dahinter. Diese Transformation garantiert zudem folgende Monotonie:

Gilt $\begin{eqnarray*} X_{j,p_1}(\omega)=1 \end{eqnarray*}$ für festes $\begin{eqnarray*} \omega \end{eqnarray*}$ sowie $\begin{eqnarray*} p_1 \end{eqnarray*}$ , so gilt für dasselbe $\begin{eqnarray*} \omega \end{eqnarray*}$ sowie $\begin{eqnarray*} p_2 \end{eqnarray*}$ mit der Eigenschaft $\begin{eqnarray*} p_1\leq p_2 \end{eqnarray*}$ erst recht $\begin{eqnarray*} X_{j,p_2}(\omega)=1 \end{eqnarray*}$ . (Ich hab jetzt mal diese Wahrscheinlichkeitsschwelle $\begin{eqnarray*} p \end{eqnarray*}$ bewusst als Index drangehängt, um die Abhängigkeit von diesem Parameter zu verdeutlichen.) Das bedeutet, dass jede 1er-Kette der Länge $\begin{eqnarray*} k \end{eqnarray*}$ für Parameter $\begin{eqnarray*} p_1 \end{eqnarray*}$ auf jeden Fall eine 1er-Kette der Mindestlänge $\begin{eqnarray*} k \end{eqnarray*}$ für Parameter $\begin{eqnarray*} p_2 \end{eqnarray*}$ ist, ggfs. ist die Kette sogar noch etwas länger. Somit ist $\begin{eqnarray*} P_{p_1}\left(R_n\geq k\right)\leq P_{p_2}\left(R_n\geq k\right) \end{eqnarray*}$ .

Das ist die Grundidee hinter diesem bei dir "Kopplungsargument" genannten Vorgehensweise. Ich hoffe, ich konnte es etwas verständlicher machen.

27.06.2019, 16:34

Stein029

Auf diesen Beitrag antworten »

Hallo HAL 9000,

ich möchte mich noch für deine Hilfe bedanken. Es hatte zwar etwas gedauert, aber ich konnte den Beweis dann doch gut nachvollziehen smile

27.06.2019, 16:36

Stein029

Auf diesen Beitrag antworten »

Zitat:

Original von Stein029
Hallo HAL 3000

Ist mir jetzt erst aufgefallen Hammer

27.06.2019, 17:01

HAL 9000

Auf diesen Beitrag antworten »

War mir gar nicht aufgefallen ... HAL 3000 ist wahrscheinlich der "Rest" von HAL 9000, nachdem ihm Dave Bowman 2/3 der Speichermodule entfernt hat. Big Laugh

Neue Frage »

Antworten »

Tupelmenge durch Kontraktionsabbildung bestimmen

Verwandte Themen