Markov-Kette < Wahrscheinlichkeitstheorie < Stochastik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Sei [mm] \ell=\IN, L=\{1,...,\ell \} [/mm] und
[mm] S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall k\in\{1,...,\ell-1\}\}
[/mm]
Für [mm] x\in \{0,1\}^L [/mm] und für [mm] r\in [/mm] L sei [mm] x^{(r)}\in \{0,1\}^L [/mm] wie folgt definiert:
[mm] x_k^{(r)}=\begin{cases} 1-x_k, & \mbox{falls } k=r \\ x_k, & \mbox{sonst } \end{cases}.
[/mm]
Offensichtlich ist 0 [mm] =(0,...,0)\in [/mm] S. Die zeitlich homogene Markov-Kette [mm] X=(X_n)_{n\ge 0} [/mm] wird wie folgt definiert: Die Kette startet in 0. Ist die Kette gegenwärtig im Zustand [mm] x\in [/mm] S, dann wird zunächst ein uniform zufälliger Index [mm] r\in [/mm] L gewählt. Ist [mm] x^{(r)}\in [/mm] S, dann springt die Kette von x nach [mm] x^{(r)}, [/mm] andernfalls verbleibt die Kette in x.
(a) Bestimme S für [mm] \ell [/mm] =1, [mm] \ell [/mm] =2, [mm] \ell [/mm] =3.
(b) Bestimme allgemein |S|.
(c) Bestimme die Übergangsmatrix K für [mm] \ell [/mm] =1, [mm] \ell =2,\ell [/mm] =3.
(d) Bestimme allgemein die Einträge der Übergangsmatrix K außerhalb der Diagonale.
(e) Es sei [mm] \vi=\bruch{1}{|S|}(1,...,1)\in [0,1]^S. [/mm] Zeige [mm] \vi K=\vi [/mm] |
Hallo zusammen,
zu a) [mm] \ell =1\Rightarrow L=\{1\}
[/mm]
Also
[mm] S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall \;k\in\{1,0\}\}
[/mm]
d.h. [mm] x_1=0 [/mm] ?
[mm] \ell=2 \Rightarrow L=\{1,2\}
[/mm]
Also
[mm] S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall k\in\{1\}\}
[/mm]
Ich habe nun alle möglichen Tupel der Länge 2 betrachet mit 0,1 Einträge
Sei [mm] x_1=(0,1), [/mm] dann kann [mm] x_2=(1,0) [/mm] oder [mm] x_2=(0,0), [/mm] sodass
[mm] x_1x_2=0 [/mm] erfüllt ist.
Sei [mm] x_1=(1,0), [/mm] dann kann [mm] x_2=(0,1) [/mm] oder [mm] x_2=(0,0), [/mm] sodass [mm] x_1x_2=0 [/mm] erfüllt ist
Sei [mm] x_1=(0,0), [/mm] dann kann [mm] x_2=(1,0) [/mm] oder [mm] x_2=(0,1) [/mm] oder [mm] x_2=(1,1), [/mm] sodass
...erfüllt ist
Sei [mm] x_1=(1,1), [/mm] dann kann nur [mm] x_2=(0,0), [/mm] sodass die Bedingung erfüllt wird.
Was sind nun die Elemente von S? Alle die aufgezählten 2-Tupeln?
[mm] \ell =3\Rightarrow L=\{1,2,3\}
[/mm]
[mm] S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall k\in\{1, 2\}\}
[/mm]
Nun wäre ich wie folgt vorangegangen wie für [mm] \ell [/mm] =2. Nun für alle Tupel der Länge 3 betrachtet:
[mm] x_1=(0,1,0)\Rightarrow x_2=(1,0,1)\vee x_2=(1,0,0)\vee x_2=(0,0,0)\vee x_2=(0,0,1)
[/mm]
[mm] x_1=(0,0,1)\Rightarrow x_2=(1,1,0)\vee x_2=(0,0,0)\vee x_2=(1,0,0)\vee x_2=(0,1,0)
[/mm]
[mm] \vdots
[/mm]
Stimmt es soweit? Kann mir jemand weiterhelfen? Danke!
|
|
| |
|
Hallo,
> zu a) [mm]\ell =1\Rightarrow L=\{1\}[/mm]
> Also
>
> [mm]S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall \;k\in\{1,0\}\}[/mm]
Nein. Die Menge $k [mm] \in \{1,...,l-1\}$ [/mm] ganz hinten in der Definition von $S$ ist nun leer. D.h. die Definition lautet für $l = 1$ nur:
$S = [mm] \{x = (x_1) \in \{0,1\}\}$, [/mm] d.h. $S = [mm] \{0,1\}$.
[/mm]
> [mm]\ell=2 \Rightarrow L=\{1,2\}[/mm]
> Also
> [mm]S=\{x=(x_k)_{k\in L}\in \{0,1\}^L:x_kx_{k+1}=0 \;\forall k\in\{1\}\}[/mm]
>
> Ich habe nun alle möglichen Tupel der Länge 2 betrachet
> mit 0,1 Einträge
> Sei [mm]x_1=(0,1),[/mm] dann kann [mm]x_2=(1,0)[/mm] oder [mm]x_2=(0,0),[/mm] sodass
> [mm]x_1x_2=0[/mm] erfüllt ist.
> Sei [mm]x_1=(1,0),[/mm] dann kann [mm]x_2=(0,1)[/mm] oder [mm]x_2=(0,0),[/mm] sodass
> [mm]x_1x_2=0[/mm] erfüllt ist
>
> Sei [mm]x_1=(0,0),[/mm] dann kann [mm]x_2=(1,0)[/mm] oder [mm]x_2=(0,1)[/mm] oder
> [mm]x_2=(1,1),[/mm] sodass
> ...erfüllt ist
>
> Sei [mm]x_1=(1,1),[/mm] dann kann nur [mm]x_2=(0,0),[/mm] sodass die
> Bedingung erfüllt wird.
>
> Was sind nun die Elemente von S? Alle die aufgezählten
> 2-Tupeln?
Ja, aber auch hier hast du es nicht ganz richtig gemacht. Die Menge $S$ selbst besteht einfach nur aus 2-Tupeln, nicht jedes Element [mm] $x_1,x_2$ [/mm] ist ein 2-Tupel.
Mit $l = 1$ lautet die Definition von $S$:
$S = [mm] \{x = (x_1,x_2) \in \{0,1\}^2: x_1 \cdot x_2 = 0\}$
[/mm]
d.h. suche alle 2-Tupel $x = [mm] (x_1,x_2)$, [/mm] wo [mm] $x_1,x_2$ [/mm] jeweils 0 oder 1 sind und [mm] $x_1\cdot x_2 [/mm] = 0$ (d.h. [mm] $x_1 [/mm] = 0$ oder [mm] $x_2 [/mm] = 0$). Ich komme da auf:
$S = [mm] \{(0,0),(0,1),(1,0)\}$.
[/mm]
> [mm]\ell =3\Rightarrow L=\{1,2,3\}[/mm]
Hier entsprechend:
$S = [mm] \{x = (x_1,x_2,x_3)\in \{0,1\}^3: x_1 \cdot x_2 = 0, x_2 \cdot x_3 = 0\}$.
[/mm]
Was sind hier alle möglichen Elemente?
Viele Grüße,
Stefan
|
|
|
| |
|
Vielen Dank Stefan.
Eine Frage: für [mm] \ell [/mm] = 2: Ist (1,1) nicht auch in S enthalten?
für [mm] \ell [/mm] =3: [mm] S=\{(0,0,0), (0,0,1), (0,1,0), (1,0,0), (1,1,0), (0,1,1),(1,0,1),(1,1,1)\}.
[/mm]
|
|
|
| |
|
zu meine Frage vorher: Hat sich geklärt.
zu [mm] \ell [/mm] =3: [mm] S=\{(0,0,0),(1,0,0),(0,1,0),(0,0,1),(1,0,1)\}.
[/mm]
zu b) ist Fibonacco-Folge.
Wie bestimme ich davon nun die Übergangsmatrizen? ich wäre für jeden Tipp dankbar.
|
|
|
| |
|
Hallo,
> zu [mm]\ell[/mm] =3: [mm]S=\{(0,0,0),(1,0,0),(0,1,0),(0,0,1),(1,0,1)\}.[/mm]
Das sieht in Ordnung aus.
> zu b) ist Fibonacco-Folge.
Das kann sein.
Ich vermute aber, dass in der Aufgabe auch ein Beweis dafür verlangt wird.
Evtl. geht es mit Induktion.
> Wie bestimme ich davon nun die Übergangsmatrizen? ich
> wäre für jeden Tipp dankbar.
Für l = 1:
Mögliche Zustände sind $x = 0,1$, d.h. deine Übergangsmatrix muss folgende Gestalt haben:
$P = [mm] \begin{pmatrix}p_{00} & p_{01}\\
p_{10} & p_{11}\end{pmatrix}$
[/mm]
wobei [mm] $p_{ij}$ [/mm] die WS angibt, von $i$ nach $j$ zu kommen.
In der Aufgabe steht, dass in jedem Schritt (aktueller Zustand $x$) ein Index $r [mm] \in \{1,...,l\}$ [/mm] ausgewählt wird.
Bei $l = 1$ wird also immer $r = 1$ ausgewählt.
Dann wird [mm] $x^{(r)}$ [/mm] angeschaut, wobei bei dir
[mm] $x_k^{(r)} [/mm] = [mm] \begin{cases}
1 - x_k, & k = r\\
x_k, & k = r
\end{cases}$.
[/mm]
Wie sieht bei dir also [mm] $x^{(r)}$ [/mm] aus, wenn $r = 1$? Ist das wieder in $S$? Springt die Kette also zu [mm] $x^{(r)}$ [/mm] oder bleibt sie in $x$ ?
Viele Grüße,
Stefan
|
|
|
| |
|
für [mm] \ell=1: [/mm] r=1 also
[mm] x_1^{(1)}=1-x_1, [/mm] also [mm] x_1^{(1)} [/mm] liegt wieder in S, da [mm] x_1\in \{0,1 \}.
[/mm]
für [mm] \ell=2\Rightarrow r\in \{1,2\}. [/mm] Sei r=1, dann
[mm] x_1^{(1)}=1-x_1 [/mm] und [mm] x_2^{(1)}=x_2 [/mm] also
Sei r=2, dann
[mm] x_1^{(2)}=x_1 [/mm] und [mm] x_2^{(2)}=1-x_2
[/mm]
und für [mm] \ell =3\Rightarrow r\in\{1,2,3\} [/mm] Sei r=1, dann
[mm] x_1^{(1)}=1-x_1\wedge x_2^{(1)}=x_2 \wedge x_3^{(1)}=1-x_3
[/mm]
Sei r=2, dann
[mm] x_1^{(2)}=x_1\wedge x_2^{(2)}=1-x_2\wedge x_3^{(2)}=x_3
[/mm]
Sei r=3, dann
[mm] x_1^{(3)}=x_1\wedge x_2^{(3)}=x_2\wedge x_3^{(3)}=1-x_3 [/mm]
Stimmt das?
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:20 Mi 19.12.2018 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
