UE Stochastic Processes - Midterm Test - SS 2005

From StatWiki

Jump to: navigation, search

SP UE - Midterm Test / Sommersemester 2005

Contents


Beispiel 1

Eine Markov-Kette sei durch folgende Übergangsmatrix gegeben:

P = \begin{bmatrix} 0 & 0 & 0 & 0.5 & 0.5 \\ 0 & 0 & 0 & 0.4 & 0.6 \\ 0 & 0 & 0 & 0 & 1 \\ 0.8 & 0 & 0.2 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ \end{bmatrix}

Graph

(1) Ist diese Markov-Kette irreduziebel? 

Zustand 2 ist von Zustand 5 aus erreichbar - die Markovkette ist irreduzibel.
Habe es auch im Matlab überprüft. Innerhalb von 3 Schritten kommt man überall hin.

(2) Klassifierziere die Zustände dieses Markov-Prozesses 

Zustände 1, 3, 4, 4, 5 sind alle rekurrent.

(3) Bestimme die Periode für rekurrente Zustände 

Die möglichen Schritte um in den Zustand 4 wieder zu kommen sind: 2, 4, 6, ...
Der grösste gemeinsame Teiler davon ist 2 und somit ist die Periode 2.

Dies gilt auch für die restlichen Zustände der Äquivalenz-Klasse (in diesem Fall für alle anderen
Zustände, da alle rekurrent sind und somit zur selben Äquivalenz-Klasse gehören). 

Es gilt: Die Periode eines Zustands ist gleich der Periode aller anderen Zustände in derselben
Äquivalenz-Klasse.

(4) Berechne die stationäre Verteilung des Prozesses 

 \begin{array}{rcl}
\pi_1 & = & 4/5 \pi_4\\
\pi_2 & = & \pi_5\\
\pi_3 & = & 1/5 \pi_4\\
\pi_4 & = & 1/2 \pi_1 + 2/5 \pi_2 \\
\pi_5 & = & 1/2 \pi_1 + 3/5 \pi_2 + \pi_3 
\end{array}
\,


\begin{array}{rcl} 
1/2 \pi_1 + 2/5 \pi_2 & = & 5/4 \pi_1 \\
2/5 \pi_2 & = & 3/4 \pi_1 \\
8/15 \pi_2 & = & \pi_1 
\end{array}



\begin{array}{rcl} 
\pi_2 & = & 4/15 \pi_2 + 3/5 \pi_2 + \pi_3  \\
\pi_3 & = & 2/15 \pi_2
\end{array} 



\begin{array}{rcl} 
1/5 \pi_4 & = & 2/15 \pi_2  \\
\pi_4 &=& 2/3 \pi_2
\end{array} 


 \frac{8 + 15 + 2 + 10 + 15}{15} \pi_2 = 1 \,
 \pi_2 = 3/10 \,

 \pi = \left(\frac{4}{25}, \frac{3}{10}, \frac{1}{25}, \frac 1 5, \frac{3}{10} \right) \,

Scheinbar ist es so, dass wenn ein Prozess Periode 2 hat, funktioniert das mit den Eigenwerten nicht so richtig.


 p = matrix(c(0,0,0,.5,.5,0,0,0,.4,.6,0,0,0,0,1,.8,0,.2,0,0,0,1,0,0,0),byrow=T,nrow=5)
 e = eigen(t(p))

# v = e$vectors[,which(e$values == 1)]
# library(MASS)
# fractions(v/sum(v))
e
# p
 
#
$values

[1] -1.000000e+00+0.000000e+00i  1.000000e+00+0.000000e+00i
[3] -1.510037e-06+0.000000e+00i  7.550183e-07+1.307716e-06i
[5]  7.550183e-07-1.307716e-06i

$vectors



             [,1]         [,2]             [,3]                        [,4]



[1,] -0.3218072+0i 0.3218072+0i  6.172134e-01+0i -6.172134e-01-0.000000e+00i
[2,] -0.6033885+0i 0.6033885+0i -7.715167e-01+0i  7.715167e-01+0.000000e+00i
[3,] -0.0804518+0i 0.0804518+0i  1.543033e-01+0i -1.543033e-01+0.000000e+00i
[4,]  0.4022590+0i 0.4022590+0i -1.165019e-06+0i -5.825093e-07-1.008925e-06i
[5,]  0.6033885+0i 0.6033885+0i  1.165019e-06+0i  5.825093e-07+1.008925e-06i



                           [,5]



[1,] -6.172134e-01+0.000000e+00i
[2,]  7.715167e-01+0.000000e+00i
[3,] -1.543033e-01-0.000000e+00i
[4,] -5.825093e-07+1.008925e-06i
[5,]  5.825093e-07-1.008925e-06i

(5) Finde den Ergodizitätskoeffizienten 

Durch intensives anschauen kann man auch sehen, das Zeile 3 und 4 bzw. 3 und 5 den maximalen Abstand haben (nämlich 2). 

D.h. \rho_0(P) = \frac 1 2 \left(\frac 4 5 + 1 + \frac 1 5\right) = 1 \,

 
 .5 * max(combn(5,2,function(x){ sum(abs(p[x[1],] - p[x[2],])) }))

#
[1] 1

Beispiel 2

Seien P_1, P_2\, die Übergangsmatrizen ergodischer Ketten. Man zeige, dass der Ergodizitätskoeffizient \rho_0\, submultiplikativ ist, d.h.

\rho_0(P_1, P_2) \le \rho_0(P_1) \rho_0(P_2) \, 

\begin{align}
\rho_0(P_1, P_2) 
& = \frac 1 2 \sup_{i,j} || (\delta_i - \delta_j) P_1 P_2 ||_1 \\
& = \frac 1 2 \sup_{i,j} || (\mu - \nu) P_2 ||_1 \\
& \le \rho_0(P_2) \frac 1 2 \sup_{i,j} || (\mu - \nu) ||_1 \\
& = \rho_0(P_2) \frac 1 2 \sup_{i,j} || (\delta_i - \delta_j) P1 ||_1 \\
& = \rho_0(P_1) \rho_0(P_2) \\
\end{align}

\mu = \delta_i P_1 \,
\nu = \delta_j P_1 \,

Für das kleiner gleich wird die Kontraktionseigenschaft verwendet (siehe UE Stochastic Processes - Beispiel 11)

||(\mu - \nu)P||_1 \le \rho_0(P) ||\mu - \nu||_1 \,
Retrieved from "http://www.eisber.net/StatWiki/index.php/UE_Stochastic_Processes_-_Midterm_Test_-_SS_2005"
Personal tools