Markov Ketten < Stochastik < Hochschule < Mathe < Vorhilfe
|
Hallo liebe Matheraum-User,
ich habe folgendes Problem mit der Aufgabe:
Sei G = (V,E) ein Graph mit |V| = n und dessen maximaler Grad
[mm] \Delta [/mm] = [mm] \Delta [/mm] (G) ist. Q sei eine Menge mit q Farben.
Ein gültige Färbung der Knoten von G mit den Farben aus Q, bzw. eine
q-Färbung, ist eine Belegung f: V [mm] \to [/mm] Q so, dass f(u) [mm] \not= [/mm] f(v) für
jedes (u,v) [mm] \in [/mm] E. Solch eine Färbung existiert immer, wenn [mm] q\ge\Delta [/mm] + 1
gilt.
Betrachte die Markov Kette, dessen Zustandsraum die Menge von allen
q-Färbungen von G sind und dessen Transitionswahrscheinlichkeit von
Zustand [mm] X_t [/mm] wie folgt gegeben ist:
1.) Wähle einen Knoten v [mm] \in [/mm] V so wie eine Farbe c [mm] \in [/mm] Q zufällig aus.
2.) Wenn die gewählte Farbe c "legal" für v ist, dann färbe v mit c und lasse
[mm] X_{t+1} [/mm] die resultierende Färbung sein. Sonst [mm] X_{t+1} [/mm] := [mm] X_{t}
[/mm]
Dies nennt man auch den Gibbs sampler.
(a) Schreibe die Transitionsmatrix für die Markov Kette auf.
(b) Zeige, dass die Kette aperiodisch ist.
(c) Zeige, dass die Kette irreduzibel ist, wenn q [mm] \ge \Delta [/mm] + 2 ist.
(d) Angenommen q [mm] \ge \Delta [/mm] + 2, finde die stationäre Verteilung.
Ich habe überhaupt keine Ahnung dazu und komme damit auch nicht zurecht.
Auch in der Literatur, die für diese VL empfohlen wurde, steht nichts drin.
Ich hoffe, ihr könnte mir helfen.
Gruß
Thomas
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
www.matheplanet.com
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
!!
![[kleeblatt]](/images/smileys/kleeblatt.gif "[kleeblatt]"){kind=small}
.
