Markoff-Ketten

25.06.2015, 10:23

fltzbgn

Auf diesen Beitrag antworten »

Markoff-Ketten

Hallo,

ich beschäftige mich gerade mit unendlichen Labyrinthen und soll mit Hilfe von Markoff-Ketten zeigen, dass diese nicht zu 100% durch Zufall verlassen werden.

Dafür soll ich mir zunächst den endlichen Fall anschauen:
[attach]38534[/attach]
(A=Ausgang, S=Startpunkt)

Das ganze habe ich dann mal (hoffentlich) vereinfacht:
[attach]38535[/attach]

Meine Idee war es dieses Modell zunächst in eine Übergangsmatrix zu packen:

$\begin{eqnarray*} \begin{pmatrix} 1 & \frac{1}{3} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{3} & 0 & 0 & 0 \\ 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 & 0 \\ 0 & 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & \frac{2}{3} & 0 & 1 \\ 0 & 0 & 0 & 0 & \frac{2}{3} & 0\end{pmatrix} \end{eqnarray*}$

Ist dieser Ansatz richtig?

Anschließend soll ich das ganze dann noch berechnen wenn dieses "Labyrinth" aus Bild 1 unendlich wäre. D.h. nach rechts unbegrenzt immer so weiter.

Vielen Dank

25.06.2015, 10:44

HAL 9000

Auf diesen Beitrag antworten »

Skizzen sind ja schön und gut, aber ein wenig Begleittext zum Modell könnte nicht schaden:

Anscheinend wählt man an jedem Verzweigungspunkt des Labyrinths jeden der ausgehenden Pfade mit gleicher Wahrscheinlichkeit. Die Knoten gleicher Tiefe im Labyrinth hast du zu jeweils einem Zustand zusammengefasst, was hier aufgrund der Symmetrie des Labyrinths Sinn macht. A scheint der (absorbierende) Endzustand zu sein.

Die Übergangsmatrix der Zustände hast du als spaltenstochastische Matrix gewählt, d.h. die Spalte kennzeichnet den Ausgangs- und die Zeile den Zielzustand eines Übergangs, Ok (so wie ich es kenne, sind mehr zeilenstochastische Ü-Matrizen üblichen, aber das ist letztlich Geschmackssache).

Zitat:

Original von fltzbgn
soll mit Hilfe von Markoff-Ketten zeigen, dass diese nicht zu 100% durch Zufall verlassen werden.

Verstehe nicht, was diese Formulierung bedeuten soll. unglücklich

unglücklich

25.06.2015, 11:05

fltzbgn

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000
Skizzen sind ja schön und gut, aber ein wenig Begleittext zum Modell könnte nicht schaden:

Anscheinend wählt man an jedem Verzweigungspunkt des Labyrinths jeden der ausgehenden Pfade mit gleicher Wahrscheinlichkeit. Die Knoten gleicher Tiefe im Labyrinth hast du zu jeweils einem Zustand zusammengefasst, was hier aufgrund der Symmetrie des Labyrinths Sinn macht. A scheint der (absorbierende) Endzustand zu sein.

Oh tut mir Leid, wenn das zu unklar war.
Aber so hast du das Modell richtig verstanden Freude

Freude

Zitat:

Original von HAL 9000
Die Übergangsmatrix der Zustände hast du als spaltenstochastische Matrix gewählt, d.h. die Spalte kennzeichnet den Ausgangs- und die Zeile den Zielzustand eines Übergangs, Ok (so wie ich es kenne, sind mehr zeilenstochastische Ü-Matrizen üblichen, aber das ist letztlich Geschmackssache).

Das wusste ich nicht. Dürfte aber doch keinen großen Unterschied machen, richtig?
Bzw. notfalls könnte man die Matrix ja schnell umformen.

Zitat:

Original von HAL 9000

Zitat:

Original von fltzbgn
soll mit Hilfe von Markoff-Ketten zeigen, dass diese nicht zu 100% durch Zufall verlassen werden.

Verstehe nicht, was diese Formulierung bedeuten soll. unglücklich

unglücklich

[/quote]

Also bei endlichen Labyrinthen ist es ja so, dass wenn man durch Zufall weitergeht (je 1/3) man trotzdem irgendwann am Ausgang ankommt. Egal wie groß das Labyrinth ist (da endlich). Auch wenn es Jahre dauert, die Wahrscheinlichkeit das Labyrinth zu verlassen beträgt 1.
Bei unendlichen Labyrinthen ist das jedoch anders. Die Wahrscheinlichkeit besteht zwar, dass man das Labyrinth per Zufall verlässt, beträgt aber nicht 1 (sondern?).
So zumindest die Theorie. Tue mich schwer das so umzusetzen.
Vielleicht kann man da ja irgendwas mit dem Grenzwert machen? verwirrt

verwirrt

Vielen Dank schonmal für deine Hilfe.

25.06.2015, 13:49

Gani

Auf diesen Beitrag antworten »

Wie ich das verstanden habe, du hast die Wahrscheinlichkeit, den Labyrinth am ersten "Zug" zu verlassen, gleich 1/3. Sonst geht man in die Tiefe und kommt fast nicht raus.
Sei p die gesuchte Wahrscheinlichkeit.
p ist sicher mehr als 1/3, aber wie viel?
Nachdem du in die Tiefe 1 gehst, hast du immer noch eine Chance, zurückzugehen, es ist gleich 1/3. Und dann könntest du rausgehen mit der Wahrscheinlichkeit 1/9.
D.h. Nach erstem Zug in die Tiefe gehst du am dritten Zug raus mit Wahrscheinlichkeit 1/9.
Wenn du vom Anfang anschaust, ist p jetzt > 1/3 + 1/9 + 1/9. (Es gibt zwei Möglichkeite, in die Tiefe zu gehen).
Analog hast du 4 Möglichkeiten in die Tiefe 2 zu gehen, alle geben uns 1/27, dass wir rauskommen.
Also, p = 1/3 + 2/9 + 4/27 + ... + 2^n/3^(n+1) + o(crap),
Wobei o(crap) habe ich als sehr kleine Werte definiert, die keinen Einfluss haben.
Dann gilt $\begin{eqnarray*} \sum\limits_{k=1}^{\infty} \frac{1}{3}(\frac{2}{3})^{k} \end{eqnarray*}$ konvergiert, da 2/3 < 1 ist.
Die Frage ist nun, ob diese Summe weniger als 1 ist. Und ich habe keine Lust, das zu berechnen.

P.S. unter crap habe ich gemeint, dass es immer Möglichkeit gibt, etwas willkürliches zu tun und nur dann zurückzukommen und den Labyrinth zu verlassen. Nun ist es so, dass je mehr Schritte man dafür braucht, desto weniger Wahrscheinlichkeit dafür entsteht, dass man diesen Weg benutzt.

Jetzt verstehe ich, dass die Folge eigentlich anderes aussiehet, weiß aber nicht, wie genau. Es soll zwar viel weniger sein, denn ich habe nicht die Wahrscheinlichkeit gezählt, dass man eigentlich den Weg in die Tiefe nimmt. Auf jeden Fall ist es so, dass wenn mein p konvergiert gegen C < 1, dann ist es in der Wirklichkeit noch besser konvergent.

25.06.2015, 15:58

HAL 9000

Auf diesen Beitrag antworten »

Es sieht so aus, dass die Wahrscheinlichkeit, in endlicher Zeit am Ausgang anzukommen, im unendlichen Labyrinth gleich 1/2 ist - der Nachweis ist allerdings etwas vertrackt. Komischerweise kann man >1/2 sehr einfach nachweisen.

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

Ok, ein möglicher Zugang:

Sei $\begin{align*} p \end{align*}$ die Wahrscheinlichkeit, von irgendeinem Punkt im Baum nach endlicher Zeit wieder an einen Punkt "vor" diesem Ausgangspunkt zu gelangen. Auf den Startpunkt $\begin{align*} S \end{align*}$ bezogen wäre das die Wahrscheinlichkeit nach $\begin{align*} A \end{align*}$ zu gelangen - also das, was wir suchen.

Dann gilt rekursiv:

$\begin{align*} p = \frac{1}{3} + \frac{2}{3}p^2\qquad (*) \end{align*}$

Begründung: Mit Wkt 1/3 geht man nach direkt im ersten Schritt "links" und ist am Ziel. In allen anderen Fällen, also mit Wkt 2/3 geht man erstmal nach rechts. Von diesem Punkt aus gelangt man mit Wkt $\begin{align*} p \end{align*}$ an den eigentlichen Ausgangspunkt zurück, und von dort ja wieder mit Wkt p zum Zielpunkt. Also ist $\begin{align*} \frac{2}{3}\cdot p\cdot p \end{align*}$ die gesuchte Rückkehrwahrscheinlichkeit in diesem "rechten" Pfad.

Dummerweise hat (*) zwei Lösungen, $\begin{align*} p=\frac{1}{2} \end{align*}$ und $\begin{align*} p=1 \end{align*}$ . Es gilt also noch $\begin{align*} p=1 \end{align*}$ auszuschließen, um $\begin{align*} p=\frac{1}{2} \end{align*}$ zu beweisen.

25.06.2015, 17:40

fltzbgn

Auf diesen Beitrag antworten »

Zitat:

Original von Gani
Dann gilt $\begin{eqnarray*} \sum\limits_{k=1}^{\infty} \frac{1}{3}(\frac{2}{3})^{k} \end{eqnarray*}$ konvergiert, da 2/3 < 1 ist.
Die Frage ist nun, ob diese Summe weniger als 1 ist. Und ich habe keine Lust, das zu berechnen.

Also ich komme auf $\begin{eqnarray*} \frac{2}{3} \end{eqnarray*}$ , wenn ich die Summe berechne.
Das hört sich doch gar nicht so schlecht an, oder?

Zitat:

Original von Gani
Jetzt verstehe ich, dass die Folge eigentlich anderes aussiehet, weiß aber nicht, wie genau. Es soll zwar viel weniger sein, denn ich habe nicht die Wahrscheinlichkeit gezählt, dass man eigentlich den Weg in die Tiefe nimmt. Auf jeden Fall ist es so, dass wenn mein p konvergiert gegen C < 1, dann ist es in der Wirklichkeit noch besser konvergent.

Aber meinst du jetzt, dass das obige Ergebnis doch falsch ist?
Ich fand deine Argumentation nämlich recht schlüssig. Freude

Freude

Zitat:

Original von HAL 9000
Begründung: Mit Wkt 1/3 geht man nach direkt im ersten Schritt "links" und ist am Ziel. In allen anderen Fällen, also mit Wkt 2/3 geht man erstmal nach rechts. Von diesem Punkt aus gelangt man mit Wkt $\begin{align*} p \end{align*}$ an den eigentlichen Ausgangspunkt zurück, und von dort ja wieder mit Wkt p zum Zielpunkt. Also ist $\begin{align*} \frac{2}{3}\cdot p\cdot p \end{align*}$ die gesuchte Rückkehrwahrscheinlichkeit in diesem "rechten" Pfad.

Mh, ich weiß nicht ob ich dir gerade so ganz folgen kann. verwirrt

verwirrt

Oder ist das was du berechnet hast jetzt wirklich nur die Wahrscheinlichkeit, dass man wieder an die Ausgangspostion gelangt bzw. eine Position davor?

MfG

Anzeige

25.06.2015, 17:45

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von fltzbgn
Oder ist das was du berechnet hast jetzt wirklich nur die Wahrscheinlichkeit, dass man ~~wieder~~ an die ~~Ausgangspostion gelangt bzw. eine~~ Position davor?

Wie ich geschrieben hatte.

25.06.2015, 18:57

Gani

Auf diesen Beitrag antworten »

Zitat:

Original von HAL 9000

Dann gilt rekursiv:

$\begin{align*} p = \frac{1}{3} + \frac{2}{3}p^2\qquad (*) \end{align*}$
...
Dummerweise hat (*) zwei Lösungen, $\begin{align*} p=\frac{1}{2} \end{align*}$ und $\begin{align*} p=1 \end{align*}$ . Es gilt also noch $\begin{align*} p=1 \end{align*}$ auszuschließen, um $\begin{align*} p=\frac{1}{2} \end{align*}$ zu beweisen.

Also, was du sagst ist, dass wenn das Labyrinth unendlich gross ist, dann ist die Wahrscheinlichkeit, einen Schritt zurück zu machen gleich groß der Wahrscheinlichkeit, das zu tun, wenn man einen Schritt weiter ist. Aber ist es wahr?
Eigentlich schon.
Wenn man nicht sehen kann, was vorher passiert ist, dann sieht alles genau gleich aus von Position 1, wie von der Position 2, mit Position 2 um eins tiefer als die erste. Und das ist genau deswegen wahr, weil das Labyrinth unendlich ist.
Also, Wahrscheinlichkeit, einen Schritt zurück zu machen (egal wann) ist die Lösung von deiner Gleichung. Das Problem ist aber nun, dass es sein könnte, dass man immer einen Schritt zurück macht. Oder nicht, wie ich das verstehe, deine Annahme ist nicht hinreichend für die feste Aussage, obwohl du alle Eingabe benutzt hast (Labyrinth ist unendlich, es gibt 2 Optionen - einen Schritt in die Tiefe oder Richtung Ausgang zu machen).

Aber was passiert, wenn man sagt, dass dein p genau gleich anderem p sein muss:

1/3 steht dafür, dass man gleich den richtigen Weg nimmt, 2/3 * 1/3 * p dafür, dass man zuerst falschen Schritt, dann richtigen macht, und das gleiche Problem bekommt, 4/9 * p^{3} dafür, dass man zwei falsche Schritte macht, dann zwei Schritte in Richtung Ausgang macht.
$\begin{eqnarray*} p = \frac{1}{3} + \frac{4}{9}p^{3} + \frac{2}{3}*\frac{1}{3}*p \end{eqnarray*}$
Es gibt drei Lösungen, wir interessieren uns nur für 0.5 und 1.
Das bedeutet, dass egal wie tief man geht, es ist immer entweder 1/2 oder 1. (Oder beide zusammen?)

25.06.2015, 19:05

HAL 9000

Auf diesen Beitrag antworten »

Zitat:

Original von Gani
Also, was du sagst ist, dass wenn das Labyrinth unendlich gross ist, dann ist die Wahrscheinlichkeit, einen Schritt zurück zu machen gleich groß der Wahrscheinlichkeit, das zu tun, wenn man einen Schritt weiter ist. Aber ist es wahr?

So wie du es formuliert hast: Gewiss nicht.

Ich hab mir nicht solche Mühe mit der Begründung gegeben, dass du sie derart verbal verwurstelt sinnentstellst. unglücklich

unglücklich

Zitat:

Original von Gani
Aber was passiert, wenn man sagt, dass dein p genau gleich anderem p sein muss:
$\begin{eqnarray*} p = \frac{1}{3} + \frac{2}{3}p^{2} + \frac{4}{9}p^{3} \end{eqnarray*}$ ,

Unfug! Meine Gleichung leitet sich aus den beiden Fällen ab, die es ausgehend von einem Feld und in einem Schritt nur gibt: Tiefer in den Baum hinein (2/3) oder heraus (1/3). Weitere Fälle und damit Summanden gibt es in diesem Ansatz nicht!!!

Das vorteilhafte des unendlichen Baumes (im Gegensatz zum endlichen) ist sein Selbstähnlichkeit: An jedem Verzweigungsknoten sieht der davon abgehende Baum (in die Tiefe) genau so aus wie der Ausgangsbaum - genau das habe ich in dieser Gleichung genutzt.

25.06.2015, 19:11

Gani

Auf diesen Beitrag antworten »

sorry, habe falsch verstanden, bitte sehe meine neue Antwort Ups

Ups

25.06.2015, 19:17

HAL 9000

Auf diesen Beitrag antworten »

Auch nicht besser: Anscheinend willst du dich bemühen, alle falschen Wege einzeln abzuklappern - das wird dir so nicht gelingen.

25.06.2015, 19:21

Gani

Auf diesen Beitrag antworten »

Ich habe das gleiche bekommen, damit wollte ich nur mir selbst zeigen, dass du recht hast. Aber ja, ich habe nichts neues geschrieben...

25.06.2015, 19:43

Gani

Auf diesen Beitrag antworten »

habe gleich ein kurzes Programm auf C++ geschrieben und ich denke mir, dass die Frage auch umformuliert werden kann - terminiert das Programm? Im Allgemeinen ist die Antwort unbestimmt, vielleicht ist sie auch hier unentschieden?

Hier ist das:
[attach]38542[/attach]

25.06.2015, 19:52

HAL 9000

Auf diesen Beitrag antworten »

Simulieren ist eine Möglichkeit. Eine andere ist, direkt die Aufenthaltswahrscheinlichkeit $\begin{align*} p_n(k) \end{align*}$ in Baumtiefe $\begin{align*} k \end{align*}$ nach genau $\begin{align*} n \end{align*}$ Schritten zu bestimmen:

Dabei kennzeichen $\begin{align*} k=0 \end{align*}$ den Ausgang A, $\begin{align*} k=1 \end{align*}$ den Startpunkt S und $\begin{align*} k>1 \end{align*}$ dann die tieferen Baumknoten. Dann gelten die Startwerte (nach n=0 Schritten):

$\begin{align*} p_0(1)=1 \end{align*}$ und $\begin{align*} p_0(k)=0 \end{align*}$ sonst (d.h. für $\begin{align*} k=0 \end{align*}$ sowie $\begin{align*} k\geq 2 \end{align*}$ )

Für $\begin{align*} n\geq 1 \end{align*}$ gilt dann

$\begin{align*} p_n(0) = p_{n-1}(0) + \frac{p_{n-1}(1)}{3} \end{align*}$

$\begin{align*} p_n(1) = \frac{1}{3} p_{n-1}(2) \end{align*}$

$\begin{align*} p_n(k) = \frac{2p_{n-1}(k-1)+p_{n-1}(k+1)}{3} \end{align*}$ für $\begin{align*} k\geq 2 \end{align*}$

Das lässt sich schnell programmieren, und man erkennt sehr schön, wie sich die Absorptionswahrscheinlichkeit $\begin{align*} p_n(0) \end{align*}$ für wachsende n dem Wert $\begin{align*} \frac{1}{2} \end{align*}$ nähert - was natürlich streng genommen kein exakter Beweis für eine Konvergenz gegen $\begin{align*} \frac{1}{2} \end{align*}$ ist.

Im Prinzip ist das die algorithmische Umsetzung der Berechnung von $\begin{align*} P^n\cdot p_0 \end{align*}$ mit Startverteilungsvektor $\begin{align*} p_0=(0,1,0,0,\ldots)^T \end{align*}$ und Übergangsmatrix $\begin{align*} P \end{align*}$ wie hier

Zitat:

Original von fltzbgn
$\begin{eqnarray*} \begin{pmatrix} 1 & \frac{1}{3} & 0 & 0 & 0 & 0 \\ 0 & 0 & \frac{1}{3} & 0 & 0 & 0 \\ 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 & 0 \\ 0 & 0 & \frac{2}{3} & 0 & \frac{1}{3} & 0 \\ 0 & 0 & 0 & \frac{2}{3} & 0 & 1 \\ 0 & 0 & 0 & 0 & \frac{2}{3} & 0\end{pmatrix} \end{eqnarray*}$

nur statt wie hier endlich dann in der unendlichen Ausführung. Für festes $\begin{align*} n \end{align*}$ muss man natürlich nur $\begin{align*} 0\leq k\leq n+1 \end{align*}$ betrachten, denn es ist ja logischerweise $\begin{align*} p_n(k)=0 \end{align*}$ für $\begin{align*} k\geq n+2 \end{align*}$ .

26.06.2015, 08:44

Huggy

Auf diesen Beitrag antworten »

Das Problem ist identisch zu einem 1-dimensionalen Random Walk, bei dem man mit Wahrscheinlichkeit 2/3 nach rechts geht und mit Wahrscheinlichkeit 1/3 nach links. Den kann man auch allgemeiner mit einer Wahrscheinlichkeit $\begin{eqnarray*} r \ (0 < r < 1) \end{eqnarray*}$ nach rechts zu gehen behandeln, wenn man mal die trivialen Fälle $\begin{eqnarray*} r = 0 \end{eqnarray*}$ und $\begin{eqnarray*} r = 1 \end{eqnarray*}$ weglässt. Die sich für $\begin{eqnarray*} p \end{eqnarray*}$ aufgrund der Selbstähnlichkeit ergebende Gleichung ist dann:

$\begin{eqnarray*} p=(1-r)+rp^2 \end{eqnarray*}$

Diese hat die beiden Lösungen:

$\begin{eqnarray*} p_1=1 \quad p_2=\frac {1-r}{r} \end{eqnarray*}$

Bei $\begin{eqnarray*} r<1/2 \end{eqnarray*}$ kommt $\begin{eqnarray*} p_2 \end{eqnarray*}$ nicht in Frage, da dann $\begin{eqnarray*} p_2 >1 \end{eqnarray*}$ . Bei $\begin{eqnarray*} r=1/2 \end{eqnarray*}$ ist $\begin{eqnarray*} p_1=p_2=1 \end{eqnarray*}$ . Bei $\begin{eqnarray*} r>1/2 \end{eqnarray*}$ kommen im Prinzip beide Lösungen in Frage. Intuitiv würde man meinen, das dann $\begin{eqnarray*} p_2 \end{eqnarray*}$ die "richtige" Lösung ist. Aber stimmt das auch? HAL hat sich da recht vorsichtig ausgedrückt.

Meiner Meinung nach kann man die Frage nach der "richtigen" Lösung nur beantworten, wenn man zuerst die Problemstellung präzisiert. Wie soll den die gesuchte Wahrscheinlichkeit $\begin{eqnarray*} p \end{eqnarray*}$ für unendlich viele Punkte und unendliche vielen Schritte definiert sein? Man kann das über einen Grenzprozess präzisieren. Man betrachtet erst mal endliche viele Punkte, also $\begin{eqnarray*} N \end{eqnarray*}$ Punkte mit $\begin{eqnarray*} N \geq 2 \end{eqnarray*}$ , und endliche viele Schritte, maximal $\begin{eqnarray*} t \end{eqnarray*}$ Schritte. Dafür sei die Wahrscheinlichkeit innerhalb der maximal $\begin{eqnarray*} t \end{eqnarray*}$ Schritte den Punkt $\begin{eqnarray*} A \end{eqnarray*}$ irgendwann zu erreichen mit $\begin{eqnarray*} p_N(t) \end{eqnarray*}$ bezeichnet. Es gibt jetzt 2 Möglichkeiten $\begin{eqnarray*} p \end{eqnarray*}$ über einen Grenzprozess zu definieren:

$\begin{eqnarray*} (A) \quad p=\lim_{N \to \infty}\lim_{t \to \infty}p_N(t) \end{eqnarray*}$

$\begin{eqnarray*} (B) \quad p=\lim_{t \to \infty}\lim_{N \to \infty}p_N(t) \end{eqnarray*}$

Bei (A) muss man noch definieren, was bei endlichem $\begin{eqnarray*} N \end{eqnarray*}$ am rechten Ende passiert. Definiert man das rechte Ende als reflektierend, führt (A) zu $\begin{eqnarray*} p = p_1=1 \end{eqnarray*}$ . Definiert man das rechte Ende als absorbierend, führt (A) zu $\begin{eqnarray*} p = p_2 \end{eqnarray*}$ .

(B) führt zu $\begin{eqnarray*} p = p_2 \end{eqnarray*}$ . Es braucht hier keine Definition für das rechte Ende, da man bei festem $\begin{eqnarray*} t \end{eqnarray*}$ und genügend großem $\begin{eqnarray*} N \end{eqnarray*}$ das rechte Ende eh nicht erreichen kann.

26.06.2015, 09:07

HAL 9000

Auf diesen Beitrag antworten »

Beim unendlichen Graphen geht es natürlich nicht um (A), sondern um $\begin{align*} (B) \end{align*}$ . Wobei man nicht unbedingt $\begin{align*} \lim_{N\to\infty} p_N(t) \end{align*}$ betrachten muss, man kann auch direkt mit $\begin{align*} p_{\infty}(t) \end{align*}$ arbeiten (siehe mein letzter Beitrag).

26.06.2015, 09:18

Huggy

Auf diesen Beitrag antworten »

Ich würde auch (B) als die natürlichere Interpretation betrachten. Aber so defintiv wie du, sehe ich das nicht. Schließlich stand ja bei dem Fragesteller:

Zitat:

Original von fltzbgn
ich beschäftige mich gerade mit unendlichen Labyrinthen und soll mit Hilfe von Markoff-Ketten zeigen, dass diese nicht zu 100% durch Zufall verlassen werden.

Dafür soll ich mir zunächst den endlichen Fall anschauen:

Und dieser endliche Fall ist doch ein endliches N, führt also zu (A).

26.06.2015, 09:58

fltzbgn

Auf diesen Beitrag antworten »

Erstmal ein großes Dankeschön für eure ganzen Antworten, und dass ihr euch so sehr damit beschäftigt habt. Freude

Freude

Leider habe ich solangsam den Faden verloren und auf ein wirkliches Ergebnis kommt ihr ja auch nicht.
Meine Übergangsmatrix ist dann im unendlichen Fall nicht wirklich zu gebrauchen, oder?

Beschäftigen sich eure Ansätze denn eigentlichen mit den Markoff-Ketten? Diese habe ich nämlich noch nicht ganz verstanden, da ich neu in dem Thema bin.

MfG

26.06.2015, 12:58

Huggy

Auf diesen Beitrag antworten »

Tut mir Leid, dass ich durch meine Einmischung mehr Verwirrung als Aufklärung geschaffen habe. Da sich HAL aber geraume Zeit nicht gemeldet hat, gebe ich eine weitere Antwort.

Zitat:

Original von fltzbgn
und auf ein wirkliches Ergebnis kommt ihr ja auch nicht.

Wir sind doch auf ganz exakte Ergebnisse gekommen.

Zitat:

Meine Übergangsmatrix ist dann im unendlichen Fall nicht wirklich zu gebrauchen, oder?

Deine Matrix bezieht sich auf $\begin{eqnarray*} N = 6 \end{eqnarray*}$ Punkte bei reflektierender Randbedingung am rechten Ende. Wenn man sie $\begin{eqnarray*} t \end{eqnarray*}$ mal auf den Anfangsvektor anwendet, kann man mit meinen Bezeichnungen aus dem Ergebnisvektor $\begin{eqnarray*} p_6(t) \end{eqnarray*}$ ablesen. Man sieht dann, wie das mit wachsendem $\begin{eqnarray*} t \end{eqnarray*}$ gegen $\begin{eqnarray*} 1 \end{eqnarray*}$ konvergiert. Will man mehr Punkte betrachten, braucht man eine entsprechend größere Übergangsmatrix. Das macht es unübersichtlich, Ergebnisse für unendlich viele Punkte zu bekommen.

Zitat:

Beschäftigen sich eure Ansätze denn eigentlichen mit den Markoff-Ketten?

Deshalb haben wir auch andere Hilfsmittel, wie die Selbstähnlichkeit, betrachtet.

26.06.2015, 13:09

HAL 9000

Auf diesen Beitrag antworten »

@Huggy

Ich bin für kein "entweder/oder", sondern für ein "und", was die Helfer hier betrifft. Insbesondere dein Beitrag heute 8:44 ist eine enorme Bereicherung der Diskussion, deshalb sind Entschuldigungen jeglicher Art schlicht unnötig. Augenzwinkern

Augenzwinkern

26.06.2015, 13:14

fltzbgn

Auf diesen Beitrag antworten »

Zitat:

Original von Huggy

Zitat:

Original von fltzbgn
und auf ein wirkliches Ergebnis kommt ihr ja auch nicht.

Wir sind doch auf ganz exakte Ergebnisse gekommen.

Ok tut mir leid, wie gesagt konnte ich euch am Ende nicht mehr ganz folgen. verwirrt

verwirrt

Aber dann ist die Wahrscheinlichkeit für den unendlichen Fall $\begin{eqnarray*} \frac{1}{2} \end{eqnarray*}$ , richtig?

Leider habe ich aber immer noch nicht ganz verstanden, wie ich von meine Übergangsmatrix auf die Wahrscheinlichkeit $\begin{eqnarray*} 1 \end{eqnarray*}$ komme.

MfG

26.06.2015, 13:16

Huggy

Auf diesen Beitrag antworten »

@HAL

Jetzt räkele ich mich mit stolz geschwellter Brust auf meinem Stuhl. Doch trotz deines Lobs bleibt die Tatsache, dass der Fragesteller jetzt deutlich verwirrt ist. Auch wertvolle Beiträge können Verwirrung stiften.

26.06.2015, 13:46

Huggy

Auf diesen Beitrag antworten »

Zitat:

Original von fltzbgn
Leider habe ich aber immer noch nicht ganz verstanden, wie ich von meine Übergangsmatrix auf die Wahrscheinlichkeit $\begin{eqnarray*} 1 \end{eqnarray*}$ komme.

Experimentell/numerisch kannst du dir das doch anschauen, indem du deinen Rechner die Übergangsmatrix wiederholt auf den Startvektor anwenden lässt. Mein Rechner spukt für $\begin{eqnarray*} t = 1, 10, 100, 1000 \end{eqnarray*}$ folgendes aus:

0,333333
0,471625
0,778415
0,999962

Analytisch bekommt man den Grenzwert anders einfacher.

26.06.2015, 17:05

fltzbgn

Auf diesen Beitrag antworten »

Alles klar, ich schaue mir nochmal alles genau an und hoffe, dass ich dann auch alles verstanden habe smile

smile

Das mit der Übergangsmatrix macht jetzt auf jeden Fall schonmal Sinn für mich.

Vielen Dank nochmal an alle für die Hilfe Wink

Wink

LG

1

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »