From 4c0bd6f788ee36619671c7301a1fa4520bffd438 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Tue, 9 Feb 2021 20:44:05 +0100 Subject: Illustrationen Markov-Ketten --- buch/chapters/30-endlichekoerper/wurzeln.tex | 16 ++- buch/chapters/80-wahrscheinlichkeit/google.tex | 105 +++++++++---------- .../chapters/80-wahrscheinlichkeit/images/Makefile | 15 ++- .../80-wahrscheinlichkeit/images/internet.pdf | Bin 0 -> 10681 bytes .../80-wahrscheinlichkeit/images/internet.tex | 58 +++++++++++ .../80-wahrscheinlichkeit/images/markov.pdf | Bin 0 -> 28921 bytes .../80-wahrscheinlichkeit/images/markov.tex | 99 ++++++++++++++++++ .../80-wahrscheinlichkeit/images/markov2.pdf | Bin 0 -> 31027 bytes .../80-wahrscheinlichkeit/images/markov2.tex | 113 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/markov3.pdf | Bin 0 -> 30437 bytes .../80-wahrscheinlichkeit/images/markov3.tex | 113 +++++++++++++++++++++ .../80-wahrscheinlichkeit/images/vergleich.pdf | Bin 120558 -> 120558 bytes buch/chapters/80-wahrscheinlichkeit/markov.tex | 42 +++++++- 13 files changed, 501 insertions(+), 60 deletions(-) create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/internet.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/internet.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov2.tex create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf create mode 100644 buch/chapters/80-wahrscheinlichkeit/images/markov3.tex (limited to 'buch/chapters') diff --git a/buch/chapters/30-endlichekoerper/wurzeln.tex b/buch/chapters/30-endlichekoerper/wurzeln.tex index 2cbd004..3be5d60 100644 --- a/buch/chapters/30-endlichekoerper/wurzeln.tex +++ b/buch/chapters/30-endlichekoerper/wurzeln.tex @@ -784,6 +784,9 @@ Jetzt muss der Quotient $f:r_0$ berechnet werden: & & & &6\rlap{$\mathstrut=r_1$}& & & & & & & & \end{array} \] +Da der Rest $r_1\in\mathbb{F}_7^*$ liegt, gibt die nächste Division +natürlich den Rest $0$ und der letzte nicht verschwindende Rest ist +$r_{1}=6$: \[ \arraycolsep=1.4pt \begin{array}{rcrcrcrcr} @@ -794,13 +797,16 @@ Jetzt muss der Quotient $f:r_0$ berechnet werden: & &0\rlap{$\mathstrut=r_2$}& & & & & & \end{array} \] -Die nächste Division ergibt natürlich den Rest $0$ und -der letzte nicht verschwindende Rest ist $r_{1}=6$. +Damit ist der euklidische Algorithmus abgeschlossen. -Durch Ausmultiplizieren der Matrizen können wir jetzt auch die -Faktoren $a$ und $b$ finden. +Durch Ausmultiplizieren der Matrizen $Q(-q_i)$ können wir jetzt auch die +Faktoren $s$ und $t$ finden. \begin{align*} -Q&= Q(q_2)Q(q_1)Q(q_0) +Q=\begin{pmatrix} +s&t\\ +*&* +\end{pmatrix} +&= Q(q_2)Q(q_1)Q(q_0) = \begin{pmatrix}0&1\\1&-q_2\end{pmatrix} \begin{pmatrix}0&1\\1&-q_1\end{pmatrix} diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index 42cd0a1..3616760 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -6,57 +6,6 @@ \section{Google-Matrix \label{buch:section:google-matrix}} \rhead{Google-Matrix} - -% -% Ein Modell für Webseitenbesucher -% -\subsection{Ein Modell für Webseitenbesucher -\label{buch:subsection:modell-fuer-webseitenbesucher}} -\begin{figure} -\centering -\begin{tikzpicture}[>=latex,thick] -\foreach \x in {0,3,6,9}{ - \foreach \y in {0,3}{ - \fill[color=white] ({\x},{\y}) circle[radius=0.3]; - \draw ({\x},{\y}) circle[radius=0.3]; - } -} -\node at (0,3) {$1$}; -\node at (0,0) {$2$}; -\node at (3,3) {$3$}; -\node at (3,0) {$4$}; -\node at (6,3) {$5$}; -\node at (6,0) {$6$}; -\node at (9,3) {$7$}; -\node at (9,0) {$8$}; -% 1 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0); -% 2 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0); -% 3 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0); -% 4 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0); -% 5 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0); -% 6 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0); -% 7 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0); -% 8 -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0); -\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3); -\end{tikzpicture} -\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix. -\label{buch:figure:modellinternet}} -\end{figure} Das Internet besteht aus einer grossen Zahl von Websites, etwa 400~Millionen aktiven Websites, jede besteht aus vielen einzelnen Seiten. Es ist daher angemessen von $N\approx 10^9$ verschiedenen Seiten auszugehen. @@ -84,6 +33,58 @@ bedeutet aber auch, dass nach Synonymen oder alternative Formen eines Wortes separat gesucht werden muss, was die Übersichtlichkeit wieder zerstört. +% +% Ein Modell für Webseitenbesucher +% +\subsection{Ein Modell für Webseitenbesucher +\label{buch:subsection:modell-fuer-webseitenbesucher}} +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/internet.pdf} +%\begin{tikzpicture}[>=latex,thick] +%\foreach \x in {0,3,6,9}{ +% \foreach \y in {0,3}{ +% \fill[color=white] ({\x},{\y}) circle[radius=0.3]; +% \draw ({\x},{\y}) circle[radius=0.3]; +% } +%} +%\node at (0,3) {$1$}; +%\node at (0,0) {$2$}; +%\node at (3,3) {$3$}; +%\node at (3,0) {$4$}; +%\node at (6,3) {$5$}; +%\node at (6,0) {$6$}; +%\node at (9,3) {$7$}; +%\node at (9,0) {$8$}; +%% 1 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0); +%% 2 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0); +%% 3 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0); +%% 4 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0); +%% 5 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0); +%% 6 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0); +%% 7 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0); +%% 8 +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0); +%\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3); +%\end{tikzpicture} +\caption{Modell-Internet als Beispiel für die Link-Matrix und die Google-Matrix. +\label{buch:figure:modellinternet}} +\end{figure} + Das kombinierte Vorkommen von Wörtern oder Begriffen alleine kann also nicht ausreichen, um die Seiten zum Beispiel einem Fachgebiet zuzuordnen. Dazu muss eine externe Informationsquelle angezapft werden. @@ -389,7 +390,7 @@ Im Fall $q=\frac1NU$ kann dies zu \[ A = -\frac1N uU^t +\frac1N UU^t = \frac1N \begin{pmatrix} diff --git a/buch/chapters/80-wahrscheinlichkeit/images/Makefile b/buch/chapters/80-wahrscheinlichkeit/images/Makefile index 24c0631..b04f6ff 100644 --- a/buch/chapters/80-wahrscheinlichkeit/images/Makefile +++ b/buch/chapters/80-wahrscheinlichkeit/images/Makefile @@ -5,7 +5,7 @@ # all: dreieck.pdf trenn.pdf vergleich.pdf vergleich.jpg \ positiv.pdf positiv.jpg diffusion.png diffusion.pdf \ - konvex.pdf + konvex.pdf internet.pdf markov.pdf markov2.pdf markov3.pdf # Visualisierung diffusion in einer primitiven Matrix diffusion.pdf: diffusion.tex diffusion.jpg @@ -58,3 +58,16 @@ drei.inc: dreieck.m # Konvex konvex.pdf: konvex.tex pdflatex konvex.tex + +internet.pdf: internet.tex + pdflatex internet.tex + +markov.pdf: markov.tex + pdflatex markov.tex + +markov2.pdf: markov2.tex + pdflatex markov2.tex + +markov3.pdf: markov3.tex + pdflatex markov3.tex + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf new file mode 100644 index 0000000..12eaf1e Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/internet.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/internet.tex b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex new file mode 100644 index 0000000..1b384ad --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/internet.tex @@ -0,0 +1,58 @@ +% +% internet.tex -- Modellinternet +% +% (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] + +\foreach \x in {0,3,6,9}{ + \foreach \y in {0,3}{ + \fill[color=white] ({\x},{\y}) circle[radius=0.3]; + \draw ({\x},{\y}) circle[radius=0.3]; + } +} +\node at (0,3) {$1$}; +\node at (0,0) {$2$}; +\node at (3,3) {$3$}; +\node at (3,0) {$4$}; +\node at (6,3) {$5$}; +\node at (6,0) {$6$}; +\node at (9,3) {$7$}; +\node at (9,0) {$8$}; +% 1 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (3,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,3) -- (0,0); +% 2 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (0,0) to[out=-20,in=-160] (3,0); +% 3 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (6,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,3) -- (0,0); +% 4 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) -- (6,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (3,0) to[out=160,in=20] (0,0); +% 5 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (9,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,3) -- (6,0); +% 6 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (6,0) to[out=20,in=160] (9,0); +% 7 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) .. controls (7.5,4) .. (6,4) -- (3,4) .. controls (1.5,4) .. (0,3); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,3) to[out=-110,in=110] (9,0); +% 8 +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=-160,in=-20] (6,0); +\draw[->,shorten >= 0.3cm, shorten <= 0.3cm] (9,0) to[out=70,in=-70] (9,3); + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf new file mode 100644 index 0000000..fba9489 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex new file mode 100644 index 0000000..72f3b85 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov.tex @@ -0,0 +1,99 @@ +% +% markov2.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} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-6.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \punkt{({#1*\xs},{-2*\ys})}{#2}{2} + \punkt{({#1*\xs},{-3*\ys})}{#2}{3} + \punkt{({#1*\xs},{-4*\ys})}{#2}{4} + \fill[color=#2] ({#1*\xs},{-5*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-5*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-6*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,2,3,4,6}{ + \foreach \y in {1,2,3,4,6}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-6.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-6.5*\ys}) -- ({5*\xs+0.7},{-6.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-6.5*\ys-0.05}) + -- + ({\x*\xs},{-6.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-6.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-6.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-6.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-6.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-6.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-6.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf new file mode 100644 index 0000000..d534c8f Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov2.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex new file mode 100644 index 0000000..c2fab2e --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov2.tex @@ -0,0 +1,113 @@ +% +% markov.tex -- Illustration markov-Kette +% +% (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] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-8.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \punkt{({#1*\xs},{-2*\ys})}{#2}{2} + \fill[color=#2] ({#1*\xs},{-3*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-3*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-4*\ys})}{#2}{7} + \punkt{({#1*\xs},{-5*\ys})}{#2}{8} + \punkt{({#1*\xs},{-6*\ys})}{#2}{9} + \fill[color=#2] ({#1*\xs},{-7*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-7*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-8*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,2,4}{ + \foreach \y in {1,2,4}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } + \foreach \x in {5,6,8}{ + \foreach \y in {5,6,8}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-8.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-8.5*\ys}) -- ({5*\xs+0.7},{-8.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-8.5*\ys-0.05}) + -- + ({\x*\xs},{-8.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-8.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-8.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-8.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-8.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-8.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-8.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf new file mode 100644 index 0000000..61f4fe7 Binary files /dev/null and b/buch/chapters/80-wahrscheinlichkeit/images/markov3.pdf differ diff --git a/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex new file mode 100644 index 0000000..0b99ef3 --- /dev/null +++ b/buch/chapters/80-wahrscheinlichkeit/images/markov3.tex @@ -0,0 +1,113 @@ +% +% markov2.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} +\begin{document} +\def\skala{1} +\begin{tikzpicture}[>=latex,thick,scale=\skala] + +\def\punkt#1#2#3{ + \fill[color=white] #1 circle[radius=0.10]; + \fill[color=#2] #1 circle[radius=0.13]; + \node[color=white] at #1 {$\scriptstyle #3$}; +} + +\def\xs{2.5} +\def\ys{1} + +\fill[color=blue!20] + (-0.5,{-3.3*\ys}) rectangle ({5*\xs+0.5},{-0.7*\ys}); + +\foreach \x in {0,...,5}{ + \draw[color=red,line width=0.5pt] + ({\x*\xs},{-0.7*\ys}) -- ({\x*\xs},{-7.5*\ys}); +} + +\def\dotradius{0.04} + +\def\dotrow#1#2{ + \punkt{({#1*\xs},{-1*\ys})}{#2}{1} + \fill[color=#2] ({#1*\xs},{-2*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-2*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-3*\ys})}{#2}{7} + \punkt{({#1*\xs},{-4*\ys})}{#2}{8} + \punkt{({#1*\xs},{-5*\ys})}{#2}{9} + \fill[color=#2] ({#1*\xs},{-6*\ys-0.3}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys-0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys+0.15}) circle[radius=\dotradius]; + \fill[color=#2] ({#1*\xs},{-6*\ys+0.3}) circle[radius=\dotradius]; + \punkt{({#1*\xs},{-7*\ys})}{#2}{s} +} + +\def\fan#1#2{ + \foreach \x in {1,3}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2,line width=2pt] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\x*\ys}); + } + \foreach \x in {4,5,7}{ + \foreach \y in {1,3,4,5,7}{ + \draw[->,shorten >= 2mm,shorten <= 2mm,color=#2] + ({#1*\xs},{-\x*\ys}) + -- + ({(#1+1)*\xs},{-\y*\ys}); + } + } +} + +\begin{scope} +\clip (-0.5,{-7.5*\ys}) rectangle ({5*\xs+0.5},-0.5); +\fan{-1}{gray} +\fan{0}{gray} +\fan{1}{gray} +\fan{2}{black} +\fan{3}{gray} +\fan{4}{gray} +\fan{5}{gray} +\end{scope} + +\dotrow{0}{gray} +\dotrow{1}{gray} +\dotrow{2}{black} +\dotrow{3}{black} +\dotrow{4}{gray} +\dotrow{5}{gray} + +\def\ty{-0.5} +\node[color=gray] at ({0.5*\xs},{\ty*\ys}) {$T(n-1,n-2)$}; +\node[color=gray] at ({1.5*\xs},{\ty*\ys}) {$T(n,n-1)$}; +\node[color=black] at ({2.5*\xs},{\ty*\ys}) {$T(n+1,n)$}; +\node[color=gray] at ({3.5*\xs},{\ty*\ys}) {$T(n+2,n+1)$}; +\node[color=gray] at ({4.5*\xs},{\ty*\ys}) {$T(n+3,n+2)$}; + +\draw[->,color=red] (-0.7,{-7.5*\ys}) -- ({5*\xs+0.7},{-7.5*\ys}) coordinate[label={$t$}]; + +\foreach \x in {0,...,5}{ + \draw[color=red] + ({\x*\xs},{-7.5*\ys-0.05}) + -- + ({\x*\xs},{-7.5*\ys+0.05}); +} +\node[color=red] at ({0*\xs},{-7.5*\ys}) [below] {$n-2\mathstrut$}; +\node[color=red] at ({1*\xs},{-7.5*\ys}) [below] {$n-1\mathstrut$}; +\node[color=red] at ({2*\xs},{-7.5*\ys}) [below] {$n\mathstrut$}; +\node[color=red] at ({3*\xs},{-7.5*\ys}) [below] {$n+1\mathstrut$}; +\node[color=red] at ({4*\xs},{-7.5*\ys}) [below] {$n+2\mathstrut$}; +\node[color=red] at ({5*\xs},{-7.5*\ys}) [below] {$n+3\mathstrut$}; + +\end{tikzpicture} +\end{document} + diff --git a/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf b/buch/chapters/80-wahrscheinlichkeit/images/vergleich.pdf index f065f76..c6173ce 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 9df7e89..0485714 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -171,6 +171,9 @@ heisst die {\em Pfadwahrscheinlichkeit} für genannten Pfad. \index{Pfadwahrscheinlichkeit}% \end{definition} +% +% Diskrete Markov-Kette +% \subsection{Diskrete Markov-Kette} % XXX Diskrete Zeit, Endliche Zustandsmenge Die Markov-Eigenschaft besagt, dass man keine Information verliert, @@ -195,9 +198,18 @@ P(X_{n+1}=x_{n+1}|X_n=x_n) hat. \end{definition} +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/markov.pdf} +\caption{Diskrete Markovkette mit Zuständen $\mathcal{S}=\{1,2,3,\dots,s\}$ +und Übergangsmatrizen $T(n+1,n)$. +\label{buch:wahrscheinlichkeit:fig:diskretemarkovkette}} +\end{figure} + Die transienten Übergangswahrscheinlichkeiten zwischen aufeinanderfolgenden Zeitpunkten stellen jetzt die vollständige Information über die -zeitliche Entwicklung dar. +zeitliche Entwicklung dar +(Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette}). Aus der Matrix \[ T(n+1,n) @@ -384,12 +396,28 @@ kommunizieren. \index{irreduzible Markov-Kette} \end{definition} +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/markov2.pdf} +\caption{Diese Markov-Kette zerfällt in verschiedene irreduzible +Markov-Ketten, dere Zustandsmengen nicht miteinander kommunizieren. +Solche Markov-Ketten können unabhängig voneinander studiert werden. +\label{buch:wahrscheinlichkeit:fig:markovzerfall}} +\end{figure} + Die Bedingung der Irreduzibilität ist gleichbedeutend damit, dass für genügend grosses $n$ alle Matrixelemente von $T^n$ positiv sind. Solche Matrizen nennt man positiv, in Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} wird gezeigt, dass positive Matrizen immer eine eindeutige stationäre Verteilung haben. +In Abbildung~\ref{buch:wahrscheinlichkeit:fig:markovzerfall} +ist eine reduzible Markov-Kette dargestellt, die Zustandsmenge +zerfällt in zwei Teilmengen von Zuständen, die nicht miteinander +kommunizieren. +Ein irreduzible Markov-Kette liegt vor, wenn sich ähnlich wie +in Abbildung~\ref{buch:wahrscheinlichkeit:fig:diskretemarkovkette} +jeder Zustand von jedem anderen aus erreichen lässt. Wenn sich der Vektorraum $\mathbb{R}^n$ in zwei unter $T$ invariante Unterräme zerlegen lässt, dann hat nach Wahl von Basen in den Unterräumen @@ -671,7 +699,17 @@ Nicht absorbierende Zustände heissen {\em transient} \index{transienter Zustand}% \end{definition} -Eine Markov-Kette kann mehrere absorbierende Zustände haben. +\begin{figure} +\centering +\includegraphics{chapters/80-wahrscheinlichkeit/images/markov3.pdf} +\caption{Markov-Kette mit absorbierenden Zuständen (blau hinterlegt). +Erreicht die Markov-Kette einen absorbierenden Zustand, dann verbleibt +sie für alle zukünftigen Zustände in diesem Zustand. +\label{buch:wahrscheinlichkeit:fig:abs}} +\end{figure} + +Eine Markov-Kette kann mehrere absorbierende Zustände haben, wie in +Abbildung~\ref{buch:wahrscheinlichkeit:fig:abs} dargestellt. Indem man die absorbierenden Zustände zuerst auflistet, bekommt die Übergangsmatrix die Form \[ -- cgit v1.2.1