UE Stochastic Processes - Midterm Test - SS 2005

From StatWiki
Jump to: navigation, search

SP UE - Midterm Test / Sommersemester 2005

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
$values
[1] -1.000000e+00+0.000000e+00i  1.000000e+00+0.000000e+00i
[3]  9.344364e-07+1.618503e-06i  9.344364e-07-1.618503e-06i
[5] -1.868873e-06+0.000000e+00i

$vectors
              [,1]          [,2]                        [,3]
[1,]  0.3218072+0i -0.3218072+0i -6.172134e-01-0.000000e+00i
[2,]  0.6033885+0i -0.6033885+0i  7.715167e-01+0.000000e+00i
[3,]  0.0804518+0i -0.0804518+0i -1.543033e-01+0.000000e+00i
[4,] -0.4022590+0i -0.4022590+0i -7.209333e-07-1.248702e-06i
[5,] -0.6033885+0i -0.6033885+0i  7.209333e-07+1.248702e-06i
                            [,4]             [,5]
[1,] -6.172134e-01+0.000000e+00i -6.172134e-01+0i
[2,]  7.715167e-01+0.000000e+00i  7.715167e-01+0i
[3,] -1.543033e-01-0.000000e+00i -1.543033e-01+0i
[4,] -7.209333e-07+1.248702e-06i  1.441867e-06+0i
[5,]  7.209333e-07-1.248702e-06i -1.441867e-06+0i

> # p</pre>

(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 \,
REngine.php: > rpdf<-'/var/www/localhost/htdocs/StatWiki/Rfiles/R/9555495912086ada8b75074f81407862ea10649f_%i.pdf'
> rpdfno<-0
> rhtml<-''
> rfiles<-'/var/www/localhost/htdocs/StatWiki/Rfiles/R/'
> source('/var/www/localhost/htdocs/StatWiki/Rfiles/R/@.R')
> rout<-'text'
> cat('<!--- Start of program --->\n')
<!--- Start of program --->
> .5 * max(combn(5,2,function(x){ sum(abs(p[x[1],] - p[x[2],])) }))
Error in FUN(x[a], ...) : object 'p' not found
Calls: combn -> FUN
Execution halted
in
 
.5 * max(combn(5,2,function(x){ sum(abs(p[x[1],] - p[x[2],])) }))

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 \,