add additional paper

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}