From 6e8e590acec6c5e94497f386ad36849f9b4825fc Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Mon, 1 Feb 2021 13:29:17 +0100 Subject: =?UTF-8?q?=C3=9Cbersicht=20algebraische=20Strukturen?= MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit --- buch/chapters/10-vektorenmatrizen/algebren.tex | 35 ++++++ buch/chapters/10-vektorenmatrizen/gruppen.tex | 1 - buch/chapters/10-vektorenmatrizen/images/Makefile | 5 +- .../10-vektorenmatrizen/images/gausszahlen.pdf | Bin 19127 -> 19127 bytes .../10-vektorenmatrizen/images/strukturen.pdf | Bin 0 -> 45336 bytes .../10-vektorenmatrizen/images/strukturen.tex | 122 +++++++++++++++++++++ buch/chapters/10-vektorenmatrizen/linear.tex | 9 +- buch/chapters/10-vektorenmatrizen/ringe.tex | 1 - buch/chapters/10-vektorenmatrizen/strukturen.tex | 10 ++ buch/chapters/80-wahrscheinlichkeit/google.tex | 7 +- .../chapters/80-wahrscheinlichkeit/images/Makefile | 7 +- .../80-wahrscheinlichkeit/images/konvex.pdf | Bin 0 -> 24033 bytes .../80-wahrscheinlichkeit/images/konvex.tex | 75 +++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/markov.tex | 101 ++++++++++++++++- buch/chapters/80-wahrscheinlichkeit/positiv.tex | 14 +++ 16 files changed, 375 insertions(+), 12 deletions(-) create mode 100644 buch/chapters/10-vektorenmatrizen/images/strukturen.pdf create mode 100644 buch/chapters/10-vektorenmatrizen/images/strukturen.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/konvex.tex (limited to 'buch/chapters') diff --git a/buch/chapters/10-vektorenmatrizen/algebren.tex b/buch/chapters/10-vektorenmatrizen/algebren.tex index 6b355ee..9e1d3dc 100644 --- a/buch/chapters/10-vektorenmatrizen/algebren.tex +++ b/buch/chapters/10-vektorenmatrizen/algebren.tex @@ -5,6 +5,41 @@ % \subsection{Algebren \label{buch:grundlagen:subsection:algebren}} +Die Skalar-Multiplikation eines Vektorraums ist in einem Ring nicht +vorhanden. +Die Menge der Matrizen $M_n(\Bbbk)$ ist sowohl ein Ring als auch +ein Vektorraum. +Man nennt eine {\em $\Bbbk$-Algebra} oder {\em Algebra über $\Bbbk$} +ein Ring $A$, der auch eine $\Bbbk$-Vektorraum ist. +Die Multiplikation des Ringes muss dazu mit der Skalarmultiplikation +verträglich sein. +Dazu müssen Assoziativgesetze +\[ +\lambda(\mu a) = (\lambda \mu) a +\qquad\text{und}\qquad +\lambda(ab) = (\lambda a) b +\] +für $a,b\in A$ und $\lambda,\mu\in\Bbbk$ +und eine Regel der Form +\begin{equation} +a(\lambda b) = \lambda (ab) +\label{buch:vektorenmatrizen:eqn:algebrakommutativ} +\end{equation} +gelten. +Die Bedingung \eqref{buch:vektorenmatrizen:eqn:algebrakommutativ} ist +eine Folge der Forderung, dass die Multiplikation +eine lineare Abbildung sein soll. +Dies bedeutet, dass +\begin{equation} +a(\lambda b+\mu c) = \lambda (ab) + \mu (ac), +\label{buch:vektorenmatrizen:eqn:algebralinear} +\end{equation} +woraus +\eqref{buch:vektorenmatrizen:eqn:algebrakommutativ} +für $\mu=0$ folgt. +Die Regel \eqref{buch:vektorenmatrizen:eqn:algebralinear} +beinhaltet aber auch das Distributivgesetz. +$M_n(\Bbbk)$ ist eine Algebra. \subsubsection{Die Algebra der Funktionen $\Bbbk^X$} Sie $X$ eine Menge und $\Bbbk^X$ die Menge aller Funktionen $X\to \Bbbk$. diff --git a/buch/chapters/10-vektorenmatrizen/gruppen.tex b/buch/chapters/10-vektorenmatrizen/gruppen.tex index b4e0982..0ff1004 100644 --- a/buch/chapters/10-vektorenmatrizen/gruppen.tex +++ b/buch/chapters/10-vektorenmatrizen/gruppen.tex @@ -5,7 +5,6 @@ % \subsection{Gruppen \label{buch:grundlagen:subsection:gruppen}} -\rhead{Gruppen} Die kleinste sinnvolle Struktur ist die einer Gruppe. Eine solche besteht aus einer Menge $G$ mit einer Verknüpfung, die additiv diff --git a/buch/chapters/10-vektorenmatrizen/images/Makefile b/buch/chapters/10-vektorenmatrizen/images/Makefile index 779d571..664dff5 100644 --- a/buch/chapters/10-vektorenmatrizen/images/Makefile +++ b/buch/chapters/10-vektorenmatrizen/images/Makefile @@ -3,10 +3,13 @@ # # (c) 2021 Prof Dr Andreas Müller, OST Ostschweizer Fachhochschule # -all: ideale.pdf gausszahlen.pdf +all: ideale.pdf gausszahlen.pdf strukturen.pdf ideale.pdf: ideale.tex pdflatex ideale.tex gausszahlen.pdf: gausszahlen.tex pdflatex gausszahlen.tex + +strukturen.pdf: strukturen.tex + pdflatex strukturen.tex diff --git a/buch/chapters/10-vektorenmatrizen/images/gausszahlen.pdf b/buch/chapters/10-vektorenmatrizen/images/gausszahlen.pdf index b717fa6..181499c 100644 Binary files a/buch/chapters/10-vektorenmatrizen/images/gausszahlen.pdf and b/buch/chapters/10-vektorenmatrizen/images/gausszahlen.pdf differ diff --git a/buch/chapters/10-vektorenmatrizen/images/strukturen.pdf b/buch/chapters/10-vektorenmatrizen/images/strukturen.pdf new file mode 100644 index 0000000..c2d545e Binary files /dev/null and b/buch/chapters/10-vektorenmatrizen/images/strukturen.pdf differ diff --git a/buch/chapters/10-vektorenmatrizen/images/strukturen.tex b/buch/chapters/10-vektorenmatrizen/images/strukturen.tex new file mode 100644 index 0000000..0006699 --- /dev/null +++ b/buch/chapters/10-vektorenmatrizen/images/strukturen.tex @@ -0,0 +1,122 @@ +% +% strukturen.tex -- Bezug der verschiedenen algebraischen Strukturen +% +% (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} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\definecolor{darkgreen}{rgb}{0,0.6,0} + +% assoziative Verknüpfung +\draw[rounded corners=1cm] (-7,-11.5) rectangle (7,7); + +\begin{scope}[yshift=6cm] +\node at (0,0.5) [left] {{\bf assoziative Verknüpfung}:\strut}; +\node at (0,0.5) [right] {$a(bc)=(ab)c\;\forall a,b,c$\strut}; +\node at (0,-0.3) {\small $\mathbb{N}$, $\Sigma^*$}; +\end{scope} + +% Gruppe +\fill[rounded corners=1cm,color=gray!40] (-6.5,-11.0) rectangle (6.5,5.3); +\draw[rounded corners=1cm] (-6.5,-11.0) rectangle (6.5,5.3); + +\begin{scope}[xshift=-3cm,yshift=4.3cm] +\node at (0,0.5) [left] {{\bf Gruppe}:}; +\node at (0,0.5) [right] {neutrales Element $e$:\strut}; +\node at (3.3,0.5) [right] {$eg=ge=g$\strut}; +\node at (5.7,0.5) [right] {$\forall g\in G$\strut}; +\node at (0,0.0) [right] {inverses Element $g^{-1}$:\strut}; +\node at (3.3,0.0) [right] {$gg^{-1}=g^{-1}g=e$\strut}; +\node at (5.7,0.0) [right] {$\forall g\in G$\strut}; +\node at (3,-1) {\small $\mathbb{Z}$, $\operatorname{GL}_n(\mathbb R)$, $S_n$, $A_n$}; +\end{scope} + +% abelsche Gruppe +\fill[rounded corners=0.7cm,color=gray!20] (-6.2,-10.7) rectangle (6.2,2.7); +\draw[rounded corners=0.7cm] (-6.2,-10.7) rectangle (6.2,2.7); +\begin{scope}[yshift=1.5cm] +\node at (0,0.5) [left] {{\bf abelsche Gruppe}:\strut}; +\node at (0,0.5) [right] {$a+b=b+a\;\forall a,b$\strut}; +\node at (0,0.0) {Addition\strut}; + +\node at (0,-1) {\small $\mathbb{Q}^*$, $\operatorname{SO}(2)$, $C_n$ }; +\end{scope} + +\fill[rounded corners=0.5cm,color=white] (-2,-10.5) rectangle (6,-0.5); +\fill[rounded corners=0.5cm,color=blue!20] (-6,-10.0) rectangle (2,0); +%\draw[rounded corners=0.5cm] (-6,-10.0) rectangle (2,0); + +% Vektorraum +\begin{scope}[yshift=-1cm] +\node at (-5.8,0.5) [right] {{\bf Vektorraum}:\strut}; +\node at (-5.8,0.0) [right] {Skalarmultiplikation\strut}; + +\node at (-5.8,-0.5) [right] {$\lambda(a+b)=\lambda a+\lambda b$\strut}; +\node at (-5.8,-1.0) [right] {$(\lambda+\mu)a=\lambda a+\mu a$\strut}; +\node at (-5.8,-1.5) [right] {$\forall\lambda,\mu\in \Bbbk\;\forall a,b\in V$}; + +\node at (-5.8,-2.5) [right] {\small $\mathbb{R}^n$, $\mathbb{C}^n$, $l^2$}; +\end{scope} + +\fill[rounded corners=0.5cm,color=red!40,opacity=0.5] + (-2,-10.5) rectangle (6,-0.5); +\draw[rounded corners=0.5cm] (-2,-10.5) rectangle (6,-0.5); + +\begin{scope}[yshift=-1cm] +\node at (0,0.0) {{\bf Algebra}:\strut}; +\node at (0,-1.0) {$a(\lambda b) = \lambda ab$\strut}; +\node at (0,-1.5) {$\forall a,b\in A, \lambda\in \Bbbk$\strut}; +\node at (0,-3.0) {\small $c_0(\mathbb{R})$}; +\end{scope} + +\begin{scope}[yshift=-1cm] +\node at (5.8,0) [left] {{\bf Ring}:}; +\node at (5.8,-0.5) [left] {Multiplikation}; + +\node at (5.8,-1.0) [left] {$a(b+c)=ab+ac$\strut}; +\node at (5.8,-1.5) [left] {$(a+b)c=ac+bc$\strut}; +\node at (5.8,-2.0) [left] {$\forall a,b,c\in R$\strut}; + +\node at (5.8,-3) [left] {\small $c_0(\mathbb{Z})$, $L^2(\mathbb R)$}; +\end{scope} + +\fill[rounded corners=0.3cm,color=yellow!20,opacity=0.5] + (-1.8,-10.3) rectangle (5.8,-4.5); +\draw[rounded corners=0.3cm] (-1.8,-10.3) rectangle (5.8,-4.5); + +% boundary of blue area +\draw[rounded corners=0.5cm] (-6,-10.0) rectangle (2,0); + +\begin{scope}[yshift=-5cm] +\node at (5.6,0) [left] {{\bf Ring mit Eins}:}; +\node at (5.6,-1) [left] {$1\cdot a= a\cdot 1 = a\forall a\in R$\strut}; +\node at (5.6,-3) [left] {\small $\mathbb{Z}[X]$, $M_n(\mathbb{Z})$}; +\end{scope} + +\begin{scope}[yshift=-5cm] +\node at (0,0) {{\bf Algebra mit Eins}}; +\node at (0,-1.2) {\small $M_n(\mathbb R)$, $C([a,b])$}; +\end{scope} + +\fill[rounded corners=0.1cm,color=darkgreen!20] + (-1.6,-9.8) rectangle (1.6,-6.9); +\draw[rounded corners=0.1cm] (-1.6,-9.8) rectangle (1.6,-6.9); + +\begin{scope}[yshift=-7cm] +\node at (0,-0.3) {{\bf Körper}:\strut}; +\node at (0,-1) {$a\in K\setminus\{0\}\Rightarrow \exists a^{-1}$\strut}; +\node at (0,-2.2) {\small $\mathbb{F}_p$, $\mathbb{R}$, $\mathbb{C}$, $\mathbb{Q}(X)$}; +\end{scope} + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/10-vektorenmatrizen/linear.tex b/buch/chapters/10-vektorenmatrizen/linear.tex index cc1c5b9..0e106c9 100644 --- a/buch/chapters/10-vektorenmatrizen/linear.tex +++ b/buch/chapters/10-vektorenmatrizen/linear.tex @@ -592,7 +592,14 @@ Sie wird auch $C=A^{-1}$ geschrieben. Die Definition der inversen Matrix stellt sicher, dass $AA^{-1}=E$ gilt, daraus folgt aber noch nicht, dass auch $A^{-1}A=E$ ist. -Die Eigenschaften der Matrizenmultiplikation stellen jedoch sicher, +Diese Eigenschaft kann man jedoch wie folgt erhalten. +Sei $C$ die inverse Matrix von $A$, also $AC=E$. +Sei weiter $D$ die inverse Matrix von $C$, also $CD=E$. +Dann ist zunächst $A=AE=A(CD)=(AC)D=ED=D$ und weiter +$CA=CD=E$. +Mit der Bezeichnung $C=A^{-1}$ erhalten wir also auch $A^{-1}A=E$. + +Die Eigenschaften der Matrizenmultiplikation stellen sicher, dass die Menge der invertierbaren Matrizen eine Struktur bilden, die man Gruppe nennt, die in Abschnitt~\ref{buch:grundlagen:subsection:gruppen} genauer untersucht wird. diff --git a/buch/chapters/10-vektorenmatrizen/ringe.tex b/buch/chapters/10-vektorenmatrizen/ringe.tex index 0a8ab1e..42e2a7e 100644 --- a/buch/chapters/10-vektorenmatrizen/ringe.tex +++ b/buch/chapters/10-vektorenmatrizen/ringe.tex @@ -5,7 +5,6 @@ % \subsection{Ringe und Moduln \label{buch:grundlagen:subsection:ringe}} -\rhead{Ringe} Die ganzen Zahlen haben ausser der Addition mit neutralem Element $0$ auch noch eine Multiplikation mit dem neutralen Element $1$. Die Multiplikation ist aber nicht immer invertierbar und zwar diff --git a/buch/chapters/10-vektorenmatrizen/strukturen.tex b/buch/chapters/10-vektorenmatrizen/strukturen.tex index 6ff4f36..a2afa37 100644 --- a/buch/chapters/10-vektorenmatrizen/strukturen.tex +++ b/buch/chapters/10-vektorenmatrizen/strukturen.tex @@ -5,6 +5,15 @@ % \section{Algebraische Strukturen \label{buch:section:algebraische-Strukturen}} +\rhead{Algebraische Strukturen} +\begin{figure} +\centering +\includegraphics[width=\textwidth]{chapters/10-vektorenmatrizen/images/strukturen.pdf} +\caption{Übersicht über die verschiedenen algebraischen Strukturen, die +in Abschnitt~\ref{buch:section:algebraische-Strukturen} zusammengestellt +werden. +\label{buch:vektorenmatrizen:fig:strukturen}} +\end{figure} Im Laufe der Definition der Vektorräume $\Bbbk^n$ und der Operationen für die Matrizen in $M_{m\times n}(\Bbbk)$ haben wir eine ganze Reihe von algebraischen Strukturen kennengelernt. @@ -20,6 +29,7 @@ ein. In diesem Abschnitten sollen diesen sinnvollen Gruppierungen von Eigenschaften Namen gegeben werden. + \input{chapters/10-vektorenmatrizen/gruppen.tex} \input{chapters/10-vektorenmatrizen/ringe.tex} \input{chapters/10-vektorenmatrizen/algebren.tex} 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 new file mode 100644 index 0000000..f77cc62 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/konvex.pdf differ 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 index bbcc95a..f065f76 100644 Binary files a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf and b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf differ 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} -- cgit v1.2.1