Forum:  Stochastik und Statistik
Thema: Dyck-Pfade: Wahrscheinlichkeit für Stoppzeit
Themen-Übersicht
Tino11
Aktiv
Dabei seit: 02.11.2019
Mitteilungen: 69
Aus:
Themenstart: 2020-06-01 12:03

Hallo,

ich brauche dringend eure Hilfe bei der folgenden Aufgabe:



Meine Frage ist, wie man auf $2C_{n-1}$ kommt? Könnte mir das jemand erklären?


Kitaktus
Senior
Dabei seit: 11.09.2008
Mitteilungen: 6443
Aus: Niedersachsen
Beitrag No.1, eingetragen 2020-06-01 13:16

1. Fallunterscheidung, ob der erste Schritt +1 oder -1 ist.
2a. Im Fall "+1" folgt ein Dyck-Pfad der Länge 2n-2 von (1,1) nach (2n-1,1).
2b. Im Fall "-1" ...
3. Für den letzte Schritt gibt es nur eine Möglichkeit.

Tipp: Setze vor und nach 2C_{n-1} ein Dollarzeichen, dann sieht es schöner aus: $2C_{n-1}$.


Conny42
Senior
Dabei seit: 25.07.2018
Mitteilungen: 131
Aus:
Beitrag No.2, eingetragen 2020-06-01 13:17

Huhu Tino,

ist $S_1 = 1$, so muss auch $S_{2n-1}=1$ (und $S_n=0$) gelten, damit $\tau = 2n$ erfüllt ist.
Was kannst du über die Anzahl der Pfade sagen, die in $S_1=1$ starten, in $S_{2n-1}=1$ enden und die sich dazwischen immer oberhalb der $x$-Achse befinden, also für die $S_k > 0$ für alle $k=1,...,2n-1$ gilt?
Und dann gibt es natürlich auch noch den Fall, dass $S_1=-1$ gilt...

Liebe Grüße,
Conny  

[Die Antwort wurde vor Beitrag No.1 begonnen.]


Tino11
Aktiv
Dabei seit: 02.11.2019
Mitteilungen: 69
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2020-06-01 14:44

Hallo Conny,

ich würde sagen, dass es gibt immer $n-1$ Pfade, die in $S_1=1$ starten, in $S_{2n-1}$ enden und sich dazwischen immer oberhalb der x-Achse befinden. Das Gleiche würde für den Fall gelten, wenn man in $S_1=-1$ startet. Kommt man somit auf $2C_{n-1}$?

Viele Grüße,
Tino


Conny42
Senior
Dabei seit: 25.07.2018
Mitteilungen: 131
Aus:
Beitrag No.4, eingetragen 2020-06-02 00:11

Huhu Tino,

2020-06-01 14:44 - Tino11 in Beitrag No. 3 schreibt:

ich würde sagen, dass es gibt immer $n-1$ Pfade, die in $S_1=1$ starten, in $S_{2n-1}$ enden und sich dazwischen immer oberhalb der x-Achse befinden.


es sind $C_{n-1}$ Pfade, die in $S_1=1$ starten und in $S_{2n-1}=1$ enden und für die $S_k > 0$ für alle $k=1,...,2n-1$ gilt, das folgt direkt durch Verschiebung der Pfade daraus, dass die Catalan-Zahl $C_{n-1}$ gerade die Anzahl der Dyck-Pfade der Länge $2(n-1)$ ist.


Das Gleiche würde für den Fall gelten, wenn man in $S_1=-1$ startet. Kommt man somit auf $2C_{n-1}$?

Genau, aus Symmetriegründen sind es ebenfalls $C_{n-1}$ Pfade, die in $S_1=-1$ starten, in $S_{2n-1} = -1$ enden und für die $S_k < 0$ für alle $k=1,...,2n-1$ gilt und somit kommt man insgesamt auf $2C_{n-1}$ Pfade.
Und da jeder Pfad die Wahrscheinlichkeit $2^{-2n}$ besitzt, kommst du auf die angegebene Wahrscheinlichkeit.

Liebe Grüße,
Conny




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=247782=100
Druckdatum: 2020-08-06 11:31