Statistische Informationsverarbeitung - Übung 4

From StatWiki
Jump to: navigation, search

Angabe: Media:StatInfMCMCue4.pdf

Beispiel 8 - Kolmogorov-Chapman equations

Zeigen Sie, dass die (m+n)\,-Schritt Übergangsmatrix P^{(n+m)}\, einer stationären Markovkette mit diskretem Wertebereich \chi\, durch P^{(n+m)} = P^{(n)} P^{(m)}\, (Matrixmultiplikation) gilt, d.h. beweisen Sie

p^{(n+m)}_{ij} = \sum_{k \in \chi} p^{(n)}_{ik}  p^{(m)}_{kj} \,
Hinweise

(a)  p^{(n+m)}_{ij} = P(X_{n+m} = j| X_0=i) = \sum_{k \in \chi} P(X_{n+m}=j,X_m=k|X_0=i) 

(b) Zeigen Sie \frac{ P(X_{n+m} =j, X_n=k, X_0=i) }{ P(X_0 = i) } =  P(X_n=k|X_0=i) P(X_{n+m}=j|X_n=k,X_0=i) 

(c)  P(X_{n+m}=j|X_m=i) = P(X_n=j|X_0=i) \, (stationär/zeit-homogen!)
Georg's Lösung


\begin{align}
p_{ij}^{(n+m)} & = P(X_{n+m}=j| X_0 = i) \\
& = \sum_k{P(X_{n+m} = j, X_n = k | X_0 = i)} \\
& = \sum_k{P(X_n = k | X_0 = i) P(X_{n+m} = j | X_n = k, X_0 = i)} \\
& = \sum_k{P(X_n = k | X_0 = i) P(X_{n+m} = j | X_n = k)} \\
& = \sum_k{P(X_n = k | X_0 = i) P(X_m = j | X_0 = k)} \\
& = \sum_k{p_{ik}^{(n)}p_{kj}^{(m)}}
\end{align}


wobei Schritt 3 gilt weil


\begin{align}
\frac{P\left(X_{n+m} = j, X_n = k, X_0 = i\right)}
     {P\left(X_0 = i\right)}
& =
\frac{P\left(X_{n+m} = j, X_n = k, X_0 = i\right)}
     {P\left(X_0 = i\right)}
\frac{P\left(X_n = k, X_0 = i\right)}
     {P\left(X_n = k, X_0 = i\right)} \\
& =
\frac{P\left(X_{n+m} = j, X_n = k, X_0 = i\right)}
    {P\left(X_n = k, X_0 = i\right)}
\frac{P\left(X_n = k, X_0 = i\right)}
     {P\left(X_0 = i\right)} \\
& =
P\left(X_{n+m} = j | X_n = k, X_0 = i\right)
P\left(X_{n} = k | X_0 = i\right)
\end{align}
 

und Schritt 4 aus der Markov Eigenschaft und (c) folgt.
Markus' Teillösung

P(A) = P(X_{n+m}=j), P(B)=P(X_n=k), P(C) = P(X_0=i) \,

(a) ist daher \frac{P(A \cap B \cap C)}{P(C)}\,

P(A \cap B \cap C) = P(A | (B \cap C)) P(B \cap C) \, nach dem Satz von Bayes

P(B|C) = \frac{P(B \cap C)}{P(C)} \,

\frac{P(A \cap B \cap C)}{P(C)} = \frac{P(A | (B \cap C)) P(B \cap C)}{P(C)} = P(A | (B \cap C)) P(B|C) \,

Stationäre Verteilung vom Ehrenfest Modell

Wir betrachten N\, Moleküle, die auf die Behälter A\, und B\, aufgeteilt sind. Zu jedem Zeitschritt wird eines von den N\, Molekülen zufällig (gleichmäßig) ausgewählt und in den jeweils anderen Behälter gegeben. Bezeichne X_n\, die Anzahl der Moleküle im Behälter A\, zum Zeitpunkt n\,. X_n\, ist dann eine Markovkette mit Wertebereich \chi = \{0,1,\ldots,N\}\,.

9 (a)

Schreiben Sie die Übergangsmatrix P\, für allgemeines N\, an. Berechnen Sie dazu erst P(X_{n+1} = i + 1 | X_n = i)\, und P(X_{n+1} = i - 1 | X_n = i)\,.

P = 
\begin{bmatrix}
 0      & 1      & 0       & 0       & \ldots & \ldots & \ldots & 0 \\
 1/N    & 0      & (N-1)/N & 0       & \ldots & \ldots & \ldots & 0 \\
 0      & 2/N    & 0       & (N-2)/N & \ldots & \ldots & \ldots & 0 \\
 0      & \ldots & \ldots  & \ldots  & \ldots & \ldots & \ldots & 0 \\
 0      & \ldots & \ldots  & \ldots  & \ldots & (N-1)/N    & 0      & 1/N \\
 0      & \ldots & \ldots  & \ldots  & \ldots & 0      & 1      & 0
\end{bmatrix}
\,

mit Spalten und Zeilen von 0,1,\ldots,N\,.

Kann auch als 


  \begin{matrix}
  p_{i,i}  & = & 0 & \, & 0 \le i \le N \\
  p_{0,1}  & = & 1 & \, & 0 \le i \le N \\
  p_{N,N-1}& = & 1 & \, & 0 \le i \le N \\
  p_{i,i-1}& = & i/N & \, & 1 \le i \le N-1 \\
  p_{i,i+1}& = & (N-1)/N, & \, & 1 \le i \le N-1 
  \end{matrix}

9 (b)

Berechnen Sie die stationäre Verteilung \vec{\pi} = (\pi_0,\pi_1,\pi_2,\pi_3)\, für N = 3 \,.

 \pi \cdot P = \pi\,
 
 \begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} 
 \cdot
 \begin{pmatrix} 
0 & 1 & 0 & 0 \\
1/3 & 0 & 2/3 & 0 \\
0 & 2/3 & 0 & 1/3 \\
0 & 0 & 1 & 0 \\
\end{pmatrix} 
=
\begin{pmatrix} x_1 & x_2 & x_3 & x_4 \end{pmatrix} 


Wenn man aus multipliziert bekommt man

\pi = \begin{pmatrix} \frac{1}{8} & \frac{3}{8} & \frac{3}{8} & \frac{1}{8}\end{pmatrix} \,


  \begin{array}{rcl}
   \frac 1 3 x_2 & = & x1 \\
   x_1 + \frac 2 3 x_3 & =& x_2 \\
   \frac 2 3  x_2 + x_4 &=& x_3 \\
   \frac 1 3  x_3 &=& x_4 \\
   x_1 + x_2 + x_3 + x_4 &=& 1
  \end{array}
 
 
Zum lösen brauch ich noch die letzte Nebenbedingung, dass die stationäre Verteilung auf 1 summiert.
Hier ein paar Eigenwert Experimente die aber mit meinem nicht zusammen passen.

> p = matrix(c(0,1,0,0,1/3,0,2/3,0,0,2/3,0,1/3,0,0,1,0),byrow=T,nrow=4)
> p
          [,1]      [,2]      [,3]      [,4]
[1,] 0.0000000 1.0000000 0.0000000 0.0000000
[2,] 0.3333333 0.0000000 0.6666667 0.0000000
[3,] 0.0000000 0.6666667 0.0000000 0.3333333
[4,] 0.0000000 0.0000000 1.0000000 0.0000000
>  eigen(t(p))
$values
[1] -1.0000000  1.0000000  0.3333333 -0.3333333

$vectors
           [,1]       [,2] [,3] [,4]
[1,]  0.2236068 -0.2236068 -0.5  0.5
[2,] -0.6708204 -0.6708204 -0.5 -0.5
[3,]  0.6708204 -0.6708204  0.5 -0.5
[4,] -0.2236068 -0.2236068  0.5  0.5

>  pi=c(1/8,3/8,3/8,1/8)</pre>
 
 Siehe auch de:Ehrenfest-Modell