diff options
Diffstat (limited to 'vorlesungen/slides/8/markov')
| -rw-r--r-- | vorlesungen/slides/8/markov/google.tex | 123 | ||||
| -rw-r--r-- | vorlesungen/slides/8/markov/irreduzibel.tex | 136 | ||||
| -rw-r--r-- | vorlesungen/slides/8/markov/markov.tex | 111 | ||||
| -rw-r--r-- | vorlesungen/slides/8/markov/pf.tex | 53 | ||||
| -rw-r--r-- | vorlesungen/slides/8/markov/stationaer.tex | 57 |
5 files changed, 480 insertions, 0 deletions
diff --git a/vorlesungen/slides/8/markov/google.tex b/vorlesungen/slides/8/markov/google.tex new file mode 100644 index 0000000..d1ec31d --- /dev/null +++ b/vorlesungen/slides/8/markov/google.tex @@ -0,0 +1,123 @@ +% +% google.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\frametitle{Google-Matrix} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.4} +\coordinate (A) at (0,0); +\coordinate (B) at (0:\r); +\coordinate (C) at (60:\r); +\coordinate (D) at (120:\r); +\coordinate (E) at (180:\r); + +\foreach \a in {2,...,5}{ + \fill[color=white] ({60*(\a-2)}:\r) circle[radius=0.2]; + \draw ({60*(\a-2)}:\r) circle[radius=0.2]; + \node at ({60*(\a-2)}:\r) {$\a$}; +} +\fill[color=white] (A) circle[radius=0.2]; +\draw (A) circle[radius=0.2]; +\node at (A) {$1$}; + +{\color<6>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (B); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (A) -- (C); +} + +{\color<7>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) -- (C); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (B) to[out=-150,in=-30] (E); +} + +{\color<8>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-90,in=30] (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (C) to[out=-30,in=90] (B); +} + +{\color<9>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (C); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (D) -- (E); +} + +{\color<10>{red} + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) -- (A); + \draw[->,shorten >= 0.2cm,shorten <= 0.2cm] (E) to[out=90,in=-150] (D); +} + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\renewcommand{\arraystretch}{1.1} +\uncover<5->{ +\begin{align*} +H&=\begin{pmatrix} +\uncover<6->{0 } + &\uncover<7->{0 } + &\uncover<8->{{\color<8>{red}\frac{1}{2}}} + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ +\uncover<6->{{\color<6>{red}\frac{1}{2}}} + &\uncover<7->{0 } + &\uncover<8->{{\color<8>{red}\frac{1}{2}}} + &\uncover<9->{0 } + &\uncover<10->{0 }\\ +\uncover<6->{{\color<6>{red}\frac{1}{2}}} + &\uncover<7->{{\color<7>{red}\frac{1}{2}}} + &\uncover<8->{0 } + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{0 }\\ +\uncover<6->{0 } + &\uncover<7->{0 } + &\uncover<8->{0 } + &\uncover<9->{0 } + &\uncover<10->{{\color<10>{red}\frac{1}{2}}}\\ +\uncover<6->{0 } + &\uncover<7->{{\color<7>{red}\frac{1}{2}}} + &\uncover<8->{0 } + &\uncover<9->{{\color<9>{red}\frac{1}{3}}} + &\uncover<10->{0 } +\end{pmatrix} +\\ +\uncover<11->{ +h_{ij} +&= +\frac{1}{\text{Anzahl Links ausgehend von $j$}} +} +\end{align*}} +\end{column} +\begin{column}{0.48\textwidth} +\begin{block}{Aufgabe} +Bestimme die Wahrscheinlichkeit $p(i)$, mit der sich ein Surfer +auf der Website $i$ befindet +\end{block} +\uncover<2->{ +\begin{block}{Navigation} +$p(i) = P(i,\text{vor Navigation})$, +\uncover<3->{$p'(i)=P(i,\text{nach Navigation})$} +\uncover<4->{ +\[ +p'(i) = \sum_{j=1}^n h_{ij} p(j) +\]} +\end{block}} +\vspace{-15pt} +\begin{block}{Freier Wille} +\vspace{-12pt} +\[ +G = \alpha H + (1-\alpha)\frac{UU^t}{n} +\] +Google-Matrix +\end{block} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/irreduzibel.tex b/vorlesungen/slides/8/markov/irreduzibel.tex new file mode 100644 index 0000000..87e90e4 --- /dev/null +++ b/vorlesungen/slides/8/markov/irreduzibel.tex @@ -0,0 +1,136 @@ +% +% irreduzibel.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Irreduzible Markovkette} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] +\def\r{2} +\coordinate (A) at ({\r*cos(0*60)},{\r*sin(0*60)}); +\coordinate (B) at ({\r*cos(1*60)},{\r*sin(1*60)}); +\coordinate (C) at ({\r*cos(2*60)},{\r*sin(2*60)}); +\coordinate (D) at ({\r*cos(3*60)},{\r*sin(3*60)}); +\coordinate (E) at ({\r*cos(4*60)},{\r*sin(4*60)}); +\coordinate (F) at ({\r*cos(5*60)},{\r*sin(5*60)}); + +\uncover<-2>{ +\draw (A) -- (B); +\draw (A) -- (C); +\draw (A) -- (D); +\draw (A) -- (E); +\draw (A) -- (F); + +\draw (B) -- (A); +\draw (B) -- (C); +\draw (B) -- (D); +\draw (B) -- (E); +\draw (B) -- (F); + +\draw (C) -- (A); +\draw (C) -- (B); +\draw (C) -- (D); +\draw (C) -- (E); +\draw (C) -- (F); + +\draw (D) -- (A); +\draw (D) -- (B); +\draw (D) -- (C); +\draw (D) -- (E); +\draw (D) -- (F); + +\draw (E) -- (A); +\draw (E) -- (B); +\draw (E) -- (C); +\draw (E) -- (D); +\draw (E) -- (F); + +\draw (F) -- (A); +\draw (F) -- (B); +\draw (F) -- (C); +\draw (F) -- (D); +\draw (F) -- (E); +} + +\uncover<3->{ + +\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] (A) to[out=90,in=-30] (B); +\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] (A) -- (C); +\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) -- (A); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] (B) to[out=150,in=30] (C); +\draw[->,color=black!20,shorten >= 0.15cm,line width=3pt] (B) to[out=-90,in=-150,distance=1cm] (B); +\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) to[out=-60,in=180] (A); +\draw[->,color=black!50,shorten >= 0.15cm,line width=3pt] (C) -- (B); + +\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] + (D) to[out=-90,in=150] (E); +\draw[->,color=black!30,shorten >= 0.15cm,line width=3pt] + (E) -- (D); +\draw[->,color=black!70,shorten >= 0.15cm,line width=3pt] + (E) to[out=-30,in=-150] (F); +\draw[->,color=black!40,shorten >= 0.15cm,line width=3pt] + (F) -- (E); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] + (F) to[out=120,in=0] (D); +\draw[->,color=black!60,shorten >= 0.15cm,line width=3pt] + (D) -- (F); +} + +\fill[color=white] (A) circle[radius=0.2]; +\fill[color=white] (B) circle[radius=0.2]; +\fill[color=white] (C) circle[radius=0.2]; +\fill[color=white] (D) circle[radius=0.2]; +\fill[color=white] (E) circle[radius=0.2]; +\fill[color=white] (F) circle[radius=0.2]; + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; +\draw (F) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; +\node at (F) {$6$}; + +\end{tikzpicture} +\end{center} +\uncover<2->{% +\begin{block}{Irreduzibel} +Graph zusammenhängend $\Rightarrow$ +Keine Zerlegung in Teilgraphen möglich +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<3->{% +\begin{block}{Reduzibel} +Die Zustandsmenge zerfällt in zwei disjunkte Teilmengen $V=V_1\cup V_2$ +und es gibt keine Übergängen zwischen den Mengen: +\uncover<4->{% +\begin{align*} +P +&= +\begin{pmatrix*}[l] +0 &0.2&0.5& & & \\ +0.3&0.2&0.5& & & \\ +0.7&0.6&0 & & & \\ + & & &0 &0.3&0.4\\ + & & &0.4&0 &0.6\\ + & & &0.6&0.7&0 +\end{pmatrix*} +\end{align*}}% +\uncover<5->{% +$P$ zerfällt in zwei Blöcke die unabhängig voneinander analysiert werden können +} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/markov.tex b/vorlesungen/slides/8/markov/markov.tex new file mode 100644 index 0000000..e92ff0f --- /dev/null +++ b/vorlesungen/slides/8/markov/markov.tex @@ -0,0 +1,111 @@ +% +% markov.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\bgroup +\setlength{\abovedisplayskip}{5pt} +\setlength{\belowdisplayskip}{5pt} +\begin{frame}[t] +\frametitle{Markovketten} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{center} +\begin{tikzpicture}[>=latex,thick] + +\def\r{2.2} + +\coordinate (A) at ({\r*cos(0*72)},{\r*sin(0*72)}); +\coordinate (B) at ({\r*cos(1*72)},{\r*sin(1*72)}); +\coordinate (C) at ({\r*cos(2*72)},{\r*sin(2*72)}); +\coordinate (D) at ({\r*cos(3*72)},{\r*sin(3*72)}); +\coordinate (E) at ({\r*cos(4*72)},{\r*sin(4*72)}); + +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!40] + (A) -- (C); +\draw[color=white,line width=8pt] (B) -- (D); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!80] + (B) -- (D); + +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!60] + (A) -- (B); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black!20] + (B) -- (C); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (C) -- (D); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (D) -- (E); +\draw[->,shorten >= 0.1cm,shorten <= 0.1cm,line width=4pt,color=black] + (E) -- (A); + +\fill[color=white] (A) circle[radius=0.2]; +\fill[color=white] (B) circle[radius=0.2]; +\fill[color=white] (C) circle[radius=0.2]; +\fill[color=white] (D) circle[radius=0.2]; +\fill[color=white] (E) circle[radius=0.2]; + +\draw (A) circle[radius=0.2]; +\draw (B) circle[radius=0.2]; +\draw (C) circle[radius=0.2]; +\draw (D) circle[radius=0.2]; +\draw (E) circle[radius=0.2]; + +\node at (A) {$1$}; +\node at (B) {$2$}; +\node at (C) {$3$}; +\node at (D) {$4$}; +\node at (E) {$5$}; + +\node at ($0.5*(A)+0.5*(B)-(0.1,0.1)$) [above right] {$\scriptstyle 0.6$}; +\node at ($0.5*(B)+0.5*(C)+(0.05,-0.07)$) [above left] {$\scriptstyle 0.2$}; +\node at ($0.5*(C)+0.5*(D)+(0.05,0)$) [left] {$\scriptstyle 1$}; +\node at ($0.5*(D)+0.5*(E)$) [below] {$\scriptstyle 1$}; +\node at ($0.5*(E)+0.5*(A)+(-0.1,0.1)$) [below right] {$\scriptstyle 1$}; +\node at ($0.6*(A)+0.4*(C)$) [above] {$\scriptstyle 0.4$}; +\node at ($0.4*(B)+0.6*(D)$) [left] {$\scriptstyle 0.8$}; + +\end{tikzpicture} +\end{center} +\vspace{-10pt} +\uncover<7->{% +\begin{block}{Verteilung} +\begin{itemize} +\item<8-> +Welche stationäre Verteilung auf den Knoten stellt sich ein? +\item<9-> +$P(i)=?$ +\end{itemize} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<2->{% +\begin{block}{\strut\mbox{Übergang\only<3->{s-/Wahrscheinlichkeit}smatrix}} +$P_{ij} = P(i | j)$, Wahrscheinlichkeit, in den Zustand $i$ überzugehen, +\begin{align*} +P +&= +\begin{pmatrix} + & & & &1\phantom{.0}\\ +0.6& & & & \\ +0.4&0.2& & & \\ + &0.8&1\phantom{.0}& & \\ + & & &1\phantom{.0}& +\end{pmatrix} +\end{align*} +\end{block}} +\vspace{-10pt} +\uncover<4->{% +\begin{block}{Eigenschaften} +\begin{itemize} +\item<5-> $P_{ij}\ge 0\;\forall i,j$ +\item<6-> Spaltensumme: +\( +\displaystyle +\sum_{i=1}^n P_{ij} = 1\;\forall j +\) +\end{itemize} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/pf.tex b/vorlesungen/slides/8/markov/pf.tex new file mode 100644 index 0000000..da2ef2b --- /dev/null +++ b/vorlesungen/slides/8/markov/pf.tex @@ -0,0 +1,53 @@ +% +% pf.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Perron-Frobenius-Theorie} +\vspace{-20pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Positive Matrizen und Vektoren} +$P\in M_{m\times n}(\mathbb{R})$ +\begin{itemize} +\item<2-> +$P$ heisst positiv, $P>0$, wenn $p_{ij}>0\;\forall i,j$ +\item<3-> +$P\ge 0$, wenn $p_{ij}\ge 0\;\forall i,j$ +\end{itemize} +\end{block} +\uncover<4->{% +\begin{block}{Beispiele} +\begin{itemize} +\item<5-> +Adjazenzmatrix $A(G)$ +\item<6-> +Gradmatrix $D(G)$ +\item<7-> +Wahrscheinlichkeitsmatrizen +\end{itemize} +\end{block}} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<8->{% +\begin{block}{Satz} +Es gibt einen positiven Eigenvektor $p$ von $P$ zum Eigenwert $1$ +\end{block}} +\uncover<9->{% +\begin{block}{Satz} +$P$ irreduzible Matrix, $P\ge 0$, hat einen Eigenvektor $p$, $p\ge 0$, +zum Eigenwert $1$ +\end{block}} +\uncover<10->{% +\begin{block}{Potenzmethode} +Falls $P\ge 0$ einen eindeutigen Eigenvektor $p$ hat\uncover<11->{, +dann konveriert die rekursiv definierte Folge +\[ +p_{n+1}=\frac{Pp_n}{\|Pp_n\|}, p_0 \ge 0, p_0\ne 0 +\]}% +\uncover<12->{$\displaystyle\lim_{n\to\infty} p_n = p$} +\end{block}} +\end{column} +\end{columns} +\end{frame} diff --git a/vorlesungen/slides/8/markov/stationaer.tex b/vorlesungen/slides/8/markov/stationaer.tex new file mode 100644 index 0000000..92fab16 --- /dev/null +++ b/vorlesungen/slides/8/markov/stationaer.tex @@ -0,0 +1,57 @@ +% +% stationaer.tex +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\begin{frame}[t] +\frametitle{Stationäre Verteilung} +%\vspace{-15pt} +\begin{columns}[t,onlytextwidth] +\begin{column}{0.48\textwidth} +\begin{block}{Zeitentwicklung} +\begin{itemize} +\item<2-> +$P$ eine Wahrscheinlichkeitsmatrix +\item<3-> +$p_0\in\mathbb{R}^n$ Verteilung zur Zeit $t=0$ bekannt +\item<4-> +$p_k\in\mathbb{R}^n$ Verteilung zur Zeit $t=k$ +\end{itemize} +\uncover<5->{% +Entwicklungsgesetz +\begin{align*} +P(i,t=k) +&= +\sum_{j=1}^n P_{ij} P(j,t=k-1) +\\ +\uncover<6->{ +p_k &= Pp_{k-1} +} +\end{align*}} +\end{block} +\end{column} +\begin{column}{0.48\textwidth} +\uncover<7->{% +\begin{block}{Stationär} +Bedingung: $p_{k\mathstrut} = p_{k-1}$ +\uncover<8->{ +\begin{align*} +\Rightarrow +Pp &= p +\end{align*}}\uncover<9->{% +Eigenvektor zum Eigenwert $1$} +\end{block}} +\uncover<10->{% +\begin{block}{Fragen} +\begin{enumerate} +\item<11-> +Gibt es eine stationäre Verteilung? +\item<12-> +Gibt es einen Eigenvektor mit Einträgen $\ge 0$? +\item<13-> +Gibt es mehr als eine Verteilung? +\end{enumerate} +\end{block}} +\end{column} +\end{columns} +\end{frame} |