diff options
Diffstat (limited to 'buch/chapters/80-wahrscheinlichkeit')
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/google.tex | 7 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/Makefile | 7 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf | bin | 0 -> 24033 bytes | |||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/konvex.tex | 75 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf | bin | 120558 -> 120558 bytes | |||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/markov.tex | 101 | ||||
| -rw-r--r-- | buch/chapters/80-wahrscheinlichkeit/positiv.tex | 14 |
7 files changed, 196 insertions, 8 deletions
diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index c1318fe..42cd0a1 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -401,9 +401,9 @@ A \] vereinfacht werden. -\begin{definition} +\begin{definition}[Google-Matrix] Die Matrix -\[ +\begin{equation} G = \alpha H @@ -416,7 +416,8 @@ G \alpha H + (1-\alpha)qU^t -\] +\label{buch:wahrscheinlichkeit:eqn:google-matrix} +\end{equation} heisst die {\em Google-Matrix}. \index{Google-Matrix}% diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 8042eb1..24c0631 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -4,7 +4,8 @@ # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschulen # all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \ - positiv.pdf positiv.jpg diffusion.png diffusion.pdf + positiv.pdf positiv.jpg diffusion.png diffusion.pdf \ + konvex.pdf # Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg @@ -53,3 +54,7 @@ dreieck.pdf: dreieck.tex drei.inc drei.inc: dreieck.m octave dreieck.m + +# Konvex +konvex.pdf: konvex.tex + pdflatex konvex.tex diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf Binary files differnew file mode 100644 index 0000000..f77cc62 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex new file mode 100644 index 0000000..05bbc60 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/konvex.tex @@ -0,0 +1,75 @@ +% +% konvex.tex -- template for standalon tikz images +% +% (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule +% +\documentclass[tikz]{standalone} +\usepackage{amsmath} +\usepackage{times} +\usepackage{txfonts} +\usepackage{pgfplots} +\usepackage{csvsimple} +\usetikzlibrary{arrows,intersections,math,calc,hobby} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1{ + \fill[color=white] #1 circle[radius=0.05]; + \draw #1 circle[radius=0.05]; +} + +\begin{scope}[xshift=-3cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,5); +\coordinate (B) at (3,2); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\begin{scope} +\clip (-2,0) rectangle (4,6); +\draw[color=red!40,line width=0.4pt] ($2*(B)-(A)$) -- ($2*(A)-(B)$); +\end{scope} +\draw[color=red,line width=1.5pt] (A) -- (B); +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\node at (O) [below left] {$O$}; +\node at (A) [above right] {$A$}; +\node at (B) [above right] {$B$}; +\node at ($0.5*(A)$) [left] {$\vec{a}$}; +\node at ($0.5*(B)$) [below right] {$\vec{b}$}; +\fill[color=white] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.6*(A)+0.4*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.6*(A)+0.4*(B)$) [above right] {$t\vec{a}+(1-t)\vec{b}$}; +\end{scope} + +\begin{scope}[xshift=4cm] +\coordinate (O) at (0,0); +\coordinate (A) at (-1,3); +\coordinate (B) at (2,5); +\coordinate (C) at (4,1); +\draw[->] (O) -- (A); +\draw[->] (O) -- (B); +\draw[->] (O) -- (C); +\fill[color=red!50,opacity=0.5] (A) -- (B) -- (C) -- cycle; +\draw[color=red,line width=1.5pt,opacity=0.7] (A) -- (B) -- (C) -- cycle; +\punkt{(O)} +\punkt{(A)} +\punkt{(B)} +\punkt{(C)} +\node at (O) [below left] {$O$}; +\node at (A) [left] {$P_1$}; +\node at (B) [above] {$P_2$}; +\node at (C) [right] {$P_3$}; +\node at ($0.5*(A)$) [left] {$\vec{p}_1$}; +\node at ($0.3*(B)$) [right] {$\vec{p}_2$}; +\node at ($0.5*(C)$) [below] {$\vec{p}_3$}; +\fill[color=white] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\draw[color=red] ($0.5*(C)+0.3*(A)+0.2*(B)$) circle[radius=0.05]; +\node[color=red] at ($0.5*(C)+0.3*(A)+0.2*(B)$) [above] {$\displaystyle\sum_{t=1}^3 t_i\vec{p}_i$}; +\end{scope} + + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf Binary files differindex bbcc95a..f065f76 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf +++ b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 0d77926..9df7e89 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -439,6 +439,17 @@ Das Problem, die stationären Verteilungen von $T$ zu finden, ist auf die Untermatrizen $T_i$ reduziert worden. \subsubsection{Die konvexe Menge der stationären Verteilungen} +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/konvex.pdf} +\caption{Die Konvexe Kombination von Vektoren $\vec{p}_1,\dots,\vec{p}_n$ ist +eine Summe der Form $\sum_{i=1}^n t_i\vec{p}_i$ wobei die $t_i\ge 0$ +sind mit $\sum_{i=1}^nt_i=1$. +Für zwei Punkte bilden die konvexen Kombinationen die Verbindungsstrecke +zwischen den Punkten, für drei Punkte in drei Dimensionen spannen die +konvexen Kombinationen ein Dreieck auf. +\label{buch:wahrscheinlichkeit:fig:konvex}} +\end{figure} Die stationären Verteilungen \[ \operatorname{Stat}(T) @@ -674,6 +685,7 @@ E&R\\ \right). \] Die Matrix $R$ beschreibt die Wahrscheinlichkeiten, mit denen man +ausgehend von einem transienten Zustand in einem bestimmten absorbierenden Zustand landet. Die Matrix $Q$ beschreibt die Übergänge, bevor dies passiert. Die Potenzen von $T$ sind @@ -698,7 +710,7 @@ E&R+RQ+RQ^2 \\ \end{array} \right), \; -\dots +\dots, \; T^k = @@ -740,9 +752,90 @@ Wenn der Prozess genau im Schritt $k$ zum ersten Mal Zustand $i$ ankommt, dann ist $E(k)$ die mittlere Wartezeit. Der Prozess verbringt also zunächst $k-1$ Schritte in transienten Zuständen, bevor er in einen absorbierenden Zustand wechselt. -Die Wahrscheinlichkeit ausgehend vom transjenten Zustand $j$ in -genau $k$ Schritten im absorbierenden Zustand zu landen ist -das Matrix-Element $(i,j)$ der Matrix $RQ^{k-1}$. + +Wir brauchen die Wahrscheinlichkeit für einen Entwicklung des Zustandes +ausgehend vom Zustand $j$, die nach $k-1$ Schritten im Zustand $l$ +landet, von wo er in den absorbierenden Zustand wechselt. +Diese Wahrscheinlichkeit ist +\[ +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) += +\sum_{i_1,\dots,i_{k-2}} +r_{il} q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j} +\] +Von den Pfaden, die zur Zeit $k-1$ im Zustand $l$ ankommen gibt es +aber auch einige, die nicht absorbiert werden. +Für die Berechnung der Wartezeit möchten wir nur die Wahrscheinlichkeit +innerhalb der Menge der Pfade, die auch tatsächlich absorbiert werden, +das ist die bedingte Wahrscheinlichkeit +\begin{equation} +\begin{aligned} +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j|X_k=i) +&= +\frac{ +P(X_k = i\wedge X_{k-1} = l \wedge X_0=j) +}{ +P(X_k=i) +} +\\ +&= +\sum_{i_1,\dots,i_{k-2}} +q_{li_{k-2}} q_{i_{k-2}i_{k-3}}\dots q_{i_2i_1} q_{i_1j}. +\end{aligned} +\label{buch:wahrscheinlichkeit:eqn:ankunftswahrscheinlichkeit} +\end{equation} +Auf der rechten Seite steht das Matrixelement $(l,j)$ von $Q^{k-1}$. + +% XXX Differenz + +Für die Berechnung der erwarteten Zeit ist müssen wir die +Wahrscheinlichkeit mit $k$ multiplizieren und summieren: +\begin{align} +E(k) +&= +\sum_{k=0}^\infty +k( +q^{(k)}_{lj} +- +q^{(k-1)}_{lj} +) +\notag +\\ +&= +\dots ++ +(k+1)( +q^{(k)}_{lj} +- +q^{(k+1)}_{lj} +) ++ +k( +q^{(k-1)}_{lj} +- +q^{(k)}_{lj} +) ++ +\dots +\label{buch:wahrscheinlichkeit:eqn:telescope} +\\ +&= +\dots ++ +q^{(k-1)}_{lj} ++ +\dots += +\sum_{k} q^{(k)}_{lj}. +\notag +\end{align} +In zwei benachbarten Termen in +\eqref{buch:wahrscheinlichkeit:eqn:telescope} +heben sich die Summanden $kq^{(k)}_{lj}$ weg, man spricht von +einer teleskopischen Reihe. +Die verbleibenden Terme sind genau die Matrixelemente der Fundamentalmatrix $N$. +Die Fundamentalmatrix enthält also im Eintrag $(l,j)$ die Wartezeit +bis zur Absorption über den Zustand $l$. \subsubsection{Wartezeit} % XXX Mittlere Zeit bis zu einem bestimmten Zustand diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index c49ffd6..9f8f38f 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -689,6 +689,18 @@ Dann gibt es einen positiven Eigenvektor zum Eigenwert $\varrho(A)$, mit geometrischer und algebraischer Vielfachheit $1$. \end{satz} +\begin{beispiel} +In der Google-Matrix mit freiem Willen +nach +\eqref{buch:wahrscheinlichkeit:eqn:google-matrix} +enthält den Term $((1-\alpha)/N)UU^t$. +Die Matrix $UU^t$ ist eine Matrix aus lauter Einsen, der Term +ist also für $\alpha < 1$ eine positive Matrix. +Die Google-Matrix ist daher eine positive Matrix. +Nach dem Satz von Perron-Frobenius ist die Grenzverteilung +eindeutig bestimmt. +\end{beispiel} + Der Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} von Perron-Frobenius kann auf primitive Matrizen verallgemeinert werden. @@ -704,4 +716,6 @@ und er hat geometrische und algebraische Vielfachheit $1$. Nach Voraussetzung gibt es ein $n$ derart, dass $A^n>0$. Für $A^n$ gelten die Resultate von Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius}. + +XXX TODO \end{proof} |