From ac5d5a9f18fb6b3ef494ae51734feabed701a1f3 Mon Sep 17 00:00:00 2001 From: =?UTF-8?q?Andreas=20M=C3=BCller?= Date: Sat, 11 Sep 2021 13:35:10 +0200 Subject: chapter 9 --- buch/chapters/70-graphen/beschreibung.tex | 2 +- buch/chapters/70-graphen/waerme.tex | 179 +++++++++++++------- buch/chapters/70-graphen/wavelets.tex | 53 +++--- buch/chapters/80-wahrscheinlichkeit/chapter.tex | 8 +- buch/chapters/80-wahrscheinlichkeit/google.tex | 155 +++++++++++------- buch/chapters/80-wahrscheinlichkeit/markov.tex | 198 ++++++++++++++--------- buch/chapters/80-wahrscheinlichkeit/parrondo.tex | 74 +++++---- buch/chapters/80-wahrscheinlichkeit/positiv.tex | 185 +++++++++++++-------- buch/chapters/90-crypto/chapter.tex | 4 +- buch/chapters/references.bib | 32 ++++ 10 files changed, 573 insertions(+), 317 deletions(-) (limited to 'buch') diff --git a/buch/chapters/70-graphen/beschreibung.tex b/buch/chapters/70-graphen/beschreibung.tex index 918594d..af934e4 100644 --- a/buch/chapters/70-graphen/beschreibung.tex +++ b/buch/chapters/70-graphen/beschreibung.tex @@ -193,7 +193,7 @@ a_{i\!j} 1&\qquad (j,i) \in E\\ 0&\qquad \text{sonst.} \end{cases} -\label{buch:graphen:eqn:adjazenzmatrix} +\label{buch:graphen:eqn:adjazenzmatrixgerichtet} \end{equation} Die Matrix $A(G)$ hat also genau dann einen nicht verschwindenden Matrixeintrag in Zeile $i$ und Spalte $j$, wenn es eine Verbindung diff --git a/buch/chapters/70-graphen/waerme.tex b/buch/chapters/70-graphen/waerme.tex index e7fc023..bfeff74 100644 --- a/buch/chapters/70-graphen/waerme.tex +++ b/buch/chapters/70-graphen/waerme.tex @@ -5,10 +5,11 @@ % \section{Wärmeleitung auf einem Graphen \label{buch:section:waermeleitung-auf-einem-graphen}} -Die Vektoren, auf denen die Laplace-Matrix operiert, können betrachtet -werden als Funktionen, die jedem Knoten einen Wert zuordnen. +Die Vektoren, auf denen die Laplace-Matrix operiert, können +als Funktionen betrachtet werden, die jedem Knoten einen Wert zuordnen. Eine mögliche physikalische Interpretation davon ist die Temperaturverteilung auf dem Graphen. +\index{Temperaturverteilung}% Die Kanten zwischen den Knoten erlauben der Wärmeenergie, von einem Knoten zu einem anderen zu fliessen. Je grösser die Temperaturdifferenz zwischen zwei Knoten ist, desto @@ -29,7 +30,7 @@ d_iT_i \biggr) \] Der Term auf der rechten Seite ist genau die Wirkung der -Laplace-Matrix auf dem Vektor $T$ der Temperaturen: +Laplace-Matrix $L=L(G)$ auf dem Vektor $T$ der Temperaturen: \begin{equation} \frac{dT}{dt} = @@ -38,6 +39,7 @@ Laplace-Matrix auf dem Vektor $T$ der Temperaturen: \end{equation} Der Wärmefluss, der durch die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} beschrieben +\index{Wärmeleitungsgleichung}% wird, codiert ebenfalls wesentliche Informationen über den Graphen. Je mehr Kanten es zwischen verschiedenen Teilen eines Graphen gibt, desto schneller findet der Wärmeaustausch zwischen diesen Teilen @@ -50,6 +52,7 @@ Die Lösungen der Wärmeleitungsgleichung liefern also Informationen Die Wärmeleitungsgleichung~\eqref{buch:graphen:eqn:waermeleitung} ist eine lineare Differentialgleichung mit konstanten Koeffizienten, die mit der Matrixexponentialfunktion gelöst werden. +\index{Matrixexponentialfunktion}% Die Lösung ist \[ f(t) = e^{-\kappa Lt}f(0). @@ -58,93 +61,131 @@ f(t) = e^{-\kappa Lt}f(0). Die Berechnung der Lösung mit der Matrixexponentialreihe ist ziemlich ineffizient, da grosse Matrizenprodukte berechnet werden müssen. Da die Matrix $L$ symmetrisch ist, gibt es eine Basis aus -orthonormierten Eigenvektoren und die Eigenwerte sind reell. -Wir bezeichnen die Eigenvektoren mit $f_1,\dots,f_n$ und die +orthonormierten Eigenvektoren und die zugehörigen Eigenwerte sind reell. +Wir bezeichnen die Eigenvektoren mit $\chi_1,\dots,\chi_n$ und die zugehörigen Eigenwerte mit $\lambda_i$. -Die Funktion $f_i(t)= e^{-\kappa\lambda_it}f_i$ ist dann eine Lösung +Die Funktion $\chi_i(t)= e^{-\kappa\lambda_it}\chi_i$ ist dann eine Lösung der Wärmeleitungsgleichung, denn die beiden Seiten -\begin{align*} -\frac{d}{dt}f_i(t) +\begin{equation} +\begin{aligned} +\text{linke Seite:}&& +\frac{d}{dt}\chi_i(t) &= --\kappa\lambda_ie^{-\kappa\lambda_it}f_i +-\kappa\lambda_ie^{-\kappa\lambda_it}\chi_i = --\kappa\lambda_i f_i(t) +-\kappa\lambda_i \chi_i(t) \\ --\kappa Lf_i(t) +\text{rechte Seite:}&& +-\kappa L\chi_i(t) &= --\kappa e^{-\kappa\lambda_it} Lf_i +-\kappa e^{-\kappa\lambda_it} L\chi_i = --\kappa e^{-\kappa\lambda_it} \lambda_i f_i +-\kappa e^{-\kappa\lambda_it} \lambda_i \chi_i = --\kappa \lambda_i f_i(t) -\end{align*} +-\kappa \lambda_i \chi_i(t) +\end{aligned} +\end{equation} von \eqref{buch:graphen:eqn:waermeleitung} stimmen überein. Eine Lösung der Wärmeleitungsgleichung zu einer beliebigen Anfangstemperaturverteilung $f$ kann durch Linearkombination aus -den Lösungen $f_i(t)$ zusammengesetzt werden. -Dazu ist nötig, $f$ aus den Vektoren $f_i$ linear zu kombinieren. -Da aber die $f_i$ orthonormiert sind, ist dies besonders einfach, +den Lösungen $\chi_i(t)$ zusammengesetzt werden. +Dazu ist nötig, $f$ aus den Vektoren $\chi_i$ linear zu kombinieren. +Da aber die $\chi_i$ orthonormiert sind, ist dies besonders einfach, die Koeffizienten sind die Skalarprodukte mit den Eigenvektoren: \[ -f=\sum_{i=1}^n \langle f_i,f\rangle f_i. +f=\sum_{i=1}^n \langle \chi_i,f\rangle \chi_i. \] -Daraus kann man die allgmeine Lösungsformel +Daraus kann man die allgemeine Lösungsformel \begin{equation} f(t) = -\sum_{i=1}^n \langle f_i,f\rangle f_i(t) +\sum_{i=1}^n \langle \chi_i,f\rangle \chi_i(t) = -\sum_{i=1}^n \langle f_i,f\rangle e^{-\kappa\lambda_i t}f_i +\sum_{i=1}^n \langle \chi_i,f\rangle e^{-\kappa\lambda_i t}\chi_i \label{buch:graphen:eqn:eigloesung} \end{equation} ableiten. -\subsection{Beispiel: Ein zyklischer Graph} +\subsection{Beispiel: Ein zyklischer Graph +\label{buch:graphen:subsection:zyklischer-graph}} \begin{figure} \centering \includegraphics{chapters/70-graphen/images/kreis.pdf} -\caption{Beispiel Graph zur Illustration der verschiedenen Basen auf einem +\caption{Beispielgraph zur Illustration der verschiedenen Basen auf einem Graphen. \label{buch:graphen:fig:kreis}} \end{figure} Wir illustrieren die im folgenden entwickelte Theorie an dem Beispielgraphen von Abbildung~\ref{buch:graphen:fig:kreis}. -Besonders interessant sind die folgenden Funktionen: +Für jedes $k=0,\dots,n-1$ ist der Vektor mit den Komponenten \[ -\left. -\begin{aligned} -s_m(k) +\chi_k(l) = e^{2\pi ikl/n}, \quad l=1,\dots,n +\] +ein Eigenvektor der Laplace-Matrix zum Eigenwert +$\lambda_k=4\sin^2\frac{\pi k}{n}$. +Tatsächlich ist +\begin{align*} +(L\chi_k)(l) &= -\sin\frac{2\pi mk}{n} +-\chi_k(l-1) ++ +2\chi_k(l) +- +\chi_k(l+1) \\ -c_m(k) &= -\cos\frac{2\pi mk}{n} -\end{aligned} -\; -\right\} -\quad -\Rightarrow -\quad -e_m(k) +-e^{2\pi ik(l-1)/n} ++ +2e^{2\pi ikl/n} +- +e^{2\pi ik(l+1)/n} +\\ +&= +(-e^{-2\pi ik/n}+2-e^{2\pi ik/n})e^{2\pi ikl/n} +\\ +&= +-(e^{2\pi ik/2n}-e^{-2\pi ik/2n})^2 \chi_k(l) +\\ +&= +- +\biggl( +\frac{e^{2\pi ik/2n}-e^{-2\pi ik/2n}}{2i} +\biggr)^2 +(2i)^2 \chi_k(l) +\\ +&= +4\sin^2\frac{\pi k}n \chi_k(l) +\end{align*} + +Natürlich sind auch Real- und Imaginärteil Eigenvektoren: +\[ +\begin{aligned} +s_k(l) +&= +\sin\frac{2\pi kl}{n} = -e^{2\pi imk/n} +\Im \chi_k(l) +\\ +c_k(l) +&= +\cos\frac{2\pi kl}{n} = -c_m(k) + is_m(k). +\Re\chi_k(l) +\end{aligned} \] Das Skalarprodukt dieser Funktionen ist \[ -\langle e_m, e_{m'}\rangle +\langle \chi_m, \chi_{m'}\rangle = \frac1n -\sum_{k=1}^n -\overline{e^{2\pi i km/n}} -e^{2\pi ikm'/n} +\sum_{l=1}^n +\overline{e^{2\pi i ml/n}} +e^{2\pi im'l/n} = \frac1n -\sum_{k=1}^n -e^{\frac{2\pi i}{n}(m'-m)k} +\sum_{l=1}^n +e^{\frac{2\pi i}{n}(m'-m)l} = \delta_{mm'} \] @@ -157,21 +198,9 @@ c_0, c_1,s_1,c_2,s_2,\dots c_{\frac{n}2-1},c_{\frac{n}2-1},c_{\frac{n}2} \] eine orthonormierte Basis. - -Die Laplace-Matrix kann mit der folgenden Definition zu einer linearen -Abbildung auf Funktionen auf dem Graphen gemacht werden. -Sei $f\colon V\to \mathbb{R}$ und $L$ die Laplace-Matrix mit -Matrixelementen $l_{vv'}$ wobei $v,v'\in V$ ist. -Dann definieren wir die Funktion $Lf$ durch -\[ -(Lf)(v) -= -\sum_{v'\in V} l_{vv'}f(v'). -\] - \subsection{Standardbasis und Eigenbasis \label{buch:subsection:standardbasis-und-eigenbasis}} -Die einfachste Basis, aus der siche Funktionen auf dem Graphen linear +Die einfachste Basis, aus der sich Funktionen auf dem Graphen linear kombinieren lassen, ist die Standardbasis. Sie hat für jeden Knoten $v$ des Graphen eine Basisfunktion mit den Werten \[ @@ -180,5 +209,37 @@ e_v\colon V\to\mathbb R:v'\mapsto \begin{cases} 0\qquad&\text{sonst.} \end{cases} \] +Sie zeichnet sich dadurch aus, dass sie perfekt lokalisiert ist. +Im Gegensatz dazu zeigt das Beispiel von +Abschnitt~\ref{buch:graphen:subsection:zyklischer-graph}, dass +die Eigenfunktionen von $L(G)$ typischerweise delokalisiert sind. +Im Beispiel hat $\chi_k(l)$ überall auf dem Graphen den gleichen +Betrag. +Die ``Frequenz'' einer Eigenfunktion dagegen ist exakt bestimmt. + +\subsection{Fourier-Theorie auf einem Graphen} +Die Eigenfunktionen der Laplace-Matrix auf einem Graphen erlauben +also, das Wärmeleitungsproblem auf dem Graphen auf ganz ähnliche +Art zu lösen, wie die Fourier-Theorie das Wärmeleitungsproblem auf +$\mathbb{R}$ oder auf einem Intervall löst. +Es ist daher angemessen, die Entwicklung einer Funktion +$f\colon G\to\mathbb{C}$ nach den Eigenvektoren $\chi_k$ +als Fourier-Transformation zu bezeichnen und die Koeffizienten +\( +c_k = \langle \chi_k, f\rangle +\) +als die Fourier-Koeffizienten. +Grundlegende Eigenschaften der Fourier-Transformation stehen damit +auch für die Analyse von Funktionen auf einem Graphen zur Verfügung. +Es fehlen allerdings Eigenschaften, die mit zusätzlicher Struktur +auf dem Definitionsbereich zusammenhängen. +Die Faltung zum Beispiel setzt eine Rechenoperation auf dem +Definitionsbereich voraus, welche natürlich in einem Graphen nicht erwartet +werden kann. +Im Beispiel von Abschnitt~\ref{buch:graphen:subsection:zyklischer-graph} +lässt sich eine solche Struktur finden, die Knoten des Graphen können +als die Elemente einer zyklischen Gruppe betrachtet werden. +Daraus lassen sich die bekannten Faltungsformeln der diskreten +Fourier-Transformation ableiten. diff --git a/buch/chapters/70-graphen/wavelets.tex b/buch/chapters/70-graphen/wavelets.tex index 2b9f29b..b11af3f 100644 --- a/buch/chapters/70-graphen/wavelets.tex +++ b/buch/chapters/70-graphen/wavelets.tex @@ -73,20 +73,21 @@ Standardbasisvektor mit Hilfe der Lösungsformel~\eqref{buch:graphen:eqn:eigloesung} gefunden werden. Aus physikalischen Gründen ist aber offensichtlich, dass die -Wärmeenergie Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$ -in der Nähe des Knoten $i$ konzentriert ist. -Dies ist aber aus der expliziten Formel +Wärmeenergie der Fundamentallösungen $F_i(t)$ für kurze Zeiten $t$ +in der Nähe des Knotens $i$ konzentriert ist. +Dies ist aber aus der Fourier-Entwicklung \begin{equation} F_i(t) = -\sum_{j=1}^n \langle f_j,e_i\rangle e^{-\kappa \lambda_i t} f_j +\sum_{j=1}^n \langle \chi_j,e_i\rangle e^{-\kappa \lambda_i t} \chi_j = \sum_{j=1}^n \overline{f}_{ji} e^{-\kappa \lambda_i t}, \label{buch:graphen:eqn:fundamentalgraph} \end{equation} nicht unmittelbar erkennbar. -Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph} ablesen, +Man kann aber aus~\eqref{buch:graphen:eqn:fundamentalgraph} +wenigstens ablesen, dass für zunehmende Zeit die hohen Frequenzen sehr schnell gedämpft werden. Die hohen Frequenzen erzeugen also den scharfen Peak für Zeiten nahe @@ -115,7 +116,7 @@ Die Darstellung im Frequenzraum und in der Zeit sind also extreme Darstellungen, entweder Frequenzlokalisierung oder zeitliche Lokalisierung ermöglichen, sich aber gegenseitig ausschliessen. -\subsubsection{Dilatation} +\subsubsection{Dilatation im Frequenzraum, spektrale Dilatation} Eine Wavelet-Basis für die $L^2$-Funktionen auf $\mathbb{R}$ erlaubt eine Funktion auf $\mathbb{R}$ auf eine Art zu analysieren, die eine ungenaue zeitliche Lokalisierung bei entsprechend ungenauer @@ -140,7 +141,7 @@ Graphen gibt es keine Rechtfertigung für diese spezielle Wahl von Streckungsfaktoren mehr. Es stellt sich daher die Frage, ob man für eine beliebige Menge \( -T= \{ t_1,t_2,\dots\} \} +T= \{ t_1,t_2,\dots\} \) von Streckungsfaktoren eine Familie von Funktionen $\chi_j$ zu finden derart, dass man sich die $\chi_j$ in einem gewissen Sinn als aus @@ -164,14 +165,14 @@ Menge von reellen Zahlen ohne innere algebraische Struktur ist. \centering \includegraphics{chapters/70-graphen/images/gh.pdf} \caption{Lokalisierungsfunktion $g(\lambda)$ für die Dilatation (links). -Die Dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren +Die dilatierten Funktionen $g_i=\tilde{D}_{1/a_i}g$ lokalisieren die Frequenzen jeweils um die Frequenzen $a_i$ im Frequenzraum. Der Konstante Vektor ist vollständig delokalisiert, die Funktion $h$ in der rechten Abbildung entfernt die hohen Frequenzen und liefert Funktionen, -die in der Umgebung eines Knotens wie die Konstante Funktion aussehen. +die in der Umgebung eines Knotens wie die konstante Funktion aussehen. \label{buch:graphs:fig:lokalisierung}} \end{figure} -Das Mutter-Wavelet einer Wavelet-Analyse zeichnet definiert, in welchem Mass +Das Mutter-Wavelet einer Wavelet-Analyse definiert, in welchem Mass sich Funktionen im Orts- und im Frequenzraum lokalisieren lassen. Die Standardbasis der Funktionen auf einem Graphen repräsentieren die perfekte örtliche Lokalisierung, Eigenbasis der Laplace-Matrix $L$ repräsentiert @@ -181,8 +182,8 @@ $\lambda\to\infty$ rasch abfällt mit einem Maximum irgendwo dazwischen (Abbildung~\ref{buch:graphs:fig:lokalisierung}). Sie kann als eine Lokalisierungsfunktion im Frequenzraum betrachtet werden. -Die Matrix $g(L)$ bildet entfernt aus einer Funktion die ganz hohen und -die ganz tiefen Frequenz, lokalisiert also die Funktionen im Frequenzraum. +Die Matrix $g(L)$ entfernt die ganz hohen und die ganz tiefen Frequenz +aus einer Funktion, lokalisiert also die Funktionen im Frequenzraum. Die Standardbasisvektoren werden dabei zu Funktionen, die nicht mehr nur auf einem Knoten von $0$ verschieden sind, aber immer noch einigermassen auf dem Graphen lokalisiert sind. @@ -191,7 +192,7 @@ $\lambda_0 < \lambda_1\le \dots\le \lambda_n$ der Laplace-Matrix von Interesse. Die Matrix $g(L)$ kann mit Hilfe der Spektraltheorie berechnet werden, -was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren von +was im vorliegenden Fall naheliegend ist, weil ja die Eigenvektoren der Laplace-Matrix bereits bekannt sind. Die Matrix $\chi^t$ bildet die Standardbasisvektoren in die Eigenbasis-Vektoren ab, also in eine Zerlegung im Frequenzraum ab, @@ -211,7 +212,7 @@ g(\lambda_0)&0&\dots&0\\ \label{buch:graphen:eqn:mutterwavelet} \end{equation} -\subsubsection{Dilatation} +\subsubsection{Spektrale Dilatation der Mutterwavelets} Die Dilatation um $a$ im Ortsraum wird zu einer Dilatation um $1/a$ im Frequenzraum. Statt also nach einer echten Dilatation der Spaltenvektoren in $g(L)$ @@ -266,12 +267,20 @@ h(L) + \sum_{i}g_i(L)=I gelten würde. Nach der Spektraltheorie gilt das nur, wenn für alle Eigenwerte $\lambda_k$, $k=1,\dots,n$ -\[ +\begin{equation} h(\lambda_k) + \sum_ig(a_i\lambda_k)=1 -\] +\label{buch:graphen:eqn:summegh} +\end{equation} gilt. -Für beliebige Funktionen $g$ und $h$ kann man nicht davon ausgehen, -aber man kann erwarten. + +Allerdings kann man im Allgemeinen nicht erwarten, +dass \ref{buch:graphen:eqn:summegh} für +beliebige Funktionen $g$ und $h$ gilt. +Da es aber nur auf die Werte auf den Eigenwerten ankommt, +muss nur sichergestellt sein, dass +die linke Seite von \eqref{buch:graphen:eqn:summegh} +nicht verschwindet. +Dies garantiert, dass die Wavelet-Entwicklung umkehrbar ist. Man muss daher zusätzlich verlangen, dass \[ h(\lambda_k) + \sum_{i} g(a_i\lambda_k) > 0 @@ -301,7 +310,7 @@ B\|v\|^2 Die Zahlen $A$ und $B$ heissen die {\em Frame-Konstanten} des Frames. \end{definition} -Die oben gefundenen Vektoren, die Spalten Vektoren von $h(L)$ und $g_i(L)$ +Die oben gefundenen Vektoren, die Spaltenvektoren von $h(L)$ und $g_i(L)$, bilden daher ein Frame. Die Frame-Konstanten kann man unmittelbar ausrechnen. Der mittlere Term von \eqref{buch:graphen:eqn:frame} ist @@ -318,12 +327,14 @@ h(\lambda)^2 + \sum_i g_i(\lambda)^2 \] abgeschätzt werden kann. Die Frame-Konstanten sind daher -\begin{align*} +\[ +\begin{aligned} A&=\min_{k} f(\lambda_k) & &\text{und}& B&=\max_{k} f(\lambda_k). -\end{align*} +\end{aligned} +\] Die Konstruktion hat also ein Frame für die Funktionen auf dem Graphen etabliert, die viele Eigenschaften einer Multiskalenanalyse in diese wesentlich weniger symmetrische Situation rettet. diff --git a/buch/chapters/80-wahrscheinlichkeit/chapter.tex b/buch/chapters/80-wahrscheinlichkeit/chapter.tex index 85b6d8c..270c44a 100644 --- a/buch/chapters/80-wahrscheinlichkeit/chapter.tex +++ b/buch/chapters/80-wahrscheinlichkeit/chapter.tex @@ -12,8 +12,8 @@ jedem Vektor einen neuen Vektor zuordnet. Es ist daher nicht abwegig zu erwarten, dass sich die Zeitentwicklung eines vom Zufall beeinflussten Systems, welches sich in mehreren verschiedenen Zuständen befinden kann, ebenfalls mit Hilfe -von Matrizen beschreiben lässt. -Eine solche Beschreiben ermöglicht leicht Verteilungen, +von Matrizen modellieren lässt. +Eine solche Beschreibung ermöglicht Verteilungen, Erwartungswerte und stationäre Zustände zu ermitteln. Im Abschnitt~\ref{buch:section:google-matrix} wird an Hand der Google @@ -22,6 +22,10 @@ auf eine Matrix führt. Abschnitt~\ref{buch:section:diskrete-markov-ketten} stellt dann die abstrakte mathematische Theorie der Markov-Ketten dar und behandelt einige wichtige Eigenschaften von Wahrscheinlichkeitsmatrizen. +Sie folgen aus den Eigenschaften positiver Matrizen und Vektoren, +die die Theorie von Perron und Frobenius in +Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} +beweist. Es stellt sich heraus, dass thermodynamische Quantensysteme sehr gut mit solchen Matrizen beschrieben werden können, zum Beispiel kann man einfache Formen von Laser auf diese Art behandeln. diff --git a/buch/chapters/80-wahrscheinlichkeit/google.tex b/buch/chapters/80-wahrscheinlichkeit/google.tex index ca78b3d..c9d0d8c 100644 --- a/buch/chapters/80-wahrscheinlichkeit/google.tex +++ b/buch/chapters/80-wahrscheinlichkeit/google.tex @@ -8,6 +8,7 @@ \rhead{Google-Matrix} Das Internet besteht aus einer grossen Zahl von Websites, etwa 400~Millionen aktiven Websites, jede besteht aus vielen einzelnen Seiten. +\index{Internet}% Es ist daher angemessen von $N\approx 10^9$ verschiedenen Seiten auszugehen. Eine natürliche Sprache umfasst dagegen nur einige 100000 bis Millionen von Wörtern. @@ -17,21 +18,23 @@ Die Zahl der Wörter, die auf den $N$ Seiten vorkommen können, ist also viel kleiner als die Zahl der zur Verfügung stehenden Wörter. Ein einzelnes Wort wird daher notwendigerweise auf einer grossen Zahl von Seiten vorkommen. -Eine Suche nach einem bestimmten Wort wird also in der überwiegenden Zahl +Eine Suche nach einem bestimmten Wort wird in der überwiegenden Zahl der Fälle derart viele Treffer zurückgeben, dass das Suchresultat nur dann nützlich sein kann, wenn eine zusätzliche Informationsquelle -ermöglicht, die Treffer in eine sinnvolle Ordnung zu bringem. +ermöglicht, die Treffer in eine sinnvolle Ordnung zu bringen. Genau dieses Problem stellte sich den vielen traditionellen Suchmaschienen in der ersten grossen Boomphase des Internets. -Traditionelle Informatione-Retrieval-Systeme operieren auf einem relativ +Traditionelle Information-Retrieval-Systeme operieren auf einem relativ +\index{Information-Retrieval}% kleinen Dokumentbestand und gehen davon aus, dass bereits wenige, spezifische Wörter nur in einem kleinen Teil des Dokumentbestandes vorkommen und damit eine übersichtliche Treffermenge ergeben. -Die Einengung der Treffermenge dank der Suche nach spezifischer Menge +Die Einengung der Treffermenge dank der Suche nach einzelnen Wörtern bedeutet aber auch, dass nach Synonymen oder alternative Formen eines Wortes separat gesucht werden muss, was die Übersichtlichkeit wieder zerstört. +\index{Treffermenge}% % % Ein Modell für Webseitenbesucher @@ -45,34 +48,35 @@ zerstört. \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. +Selbst das kombinierte Vorkommen von Wörtern oder Begriffen alleine reicht +nicht aus, um die Seiten zum Beispiel einem Fachgebiet zuzuordnen. Dazu muss eine externe Informationsquelle angezapft werden. Bei traditionellen Dokumenten liefert der Kontext, in dem ein Dokument erfasst wurde, solche ergänzenden Informationen. Eine Publikation in einem Fachjournal ordnet einen Text einem Fachgebiet zu. Im World-Wide-Web liefert die Link-Struktur diesen Kontext. -Dokumente zu ähnlichen Themen werden bevorzugt untereinander verlinkt -sein. +\index{Link}% +Dokumente zu ähnlichen oder verwandten Themen werden bevorzugt +untereinander verlinkt sein. Gesucht ist jetzt also ein Modell, welches objektiv die Linkstruktur -bewertet und daraus eine Rangordnung der passenden Wörter ableitet. +bewertet und daraus eine Rangordnung der Suchresultate ableitet. Die Linkstruktur kann natürlich als gerichteter Graph betrachtet und -mit Hilfe der Matrix~\eqref{buch:graphen:eqn:linkmatrix} -beschrieben werden. +mit Hilfe der Adjazenzmatrix~\eqref{buch:graphen:eqn:adjazenzmatrixgerichtet} +\index{Adjazenzmatrix}% +eines gerichteten Graphen beschrieben werden. Dies trägt jedoch der Anzahl der Wahlmöglichkeiten nicht Rechnung. -Eine Website mit nur einem Link auf die Seite $j$ hat mehr Gewicht -als eine Seite mit vielen Links, unter denen der Link auf die Seite $j$ -einer von vielen ist. -Im Beispiel-Inter der Abbildung~\ref{buch:figure:modellinternet} -signalisiert die Seite $t$ mit nur einem Link auf die Seite $8$ +Eine Website mit nur einem Link auf die Seite $j$ gibt der Seite $j$ +mehr Gewicht als eine Seite mit vielen Links, unter denen der Link +auf die Seite $j$ einer von Vielen ist. +Im Beispiel-Internet der Abbildung~\ref{buch:figure:modellinternet} +signalisiert die Seite $6$ mit nur einem Link auf die Seite $8$ viel deutlicher, dass $8$ eine wichtige Seite ist, also die die Seite $5$ tut, die auch noch zwei andere Links enthält. Wir können diesen Unterschied berücksichtigen, indem wir zu einem Wahrscheinlichkeitsmodell übergehen, was wir im folgenden Abschnitt tun werden. - % % Wahrscheinlichkeitsinterpretation % @@ -104,7 +108,9 @@ lange Zeit ungefähr nach den gleichen Dingen suchen und sich daher auf die gleiche Weise auf den verschiedenen Seiten verteilen und dass insbesondere die Verteilung stationär ist, dass also $P(S_i) = P(S'_i)$ gilt. +\index{Suchmaschine}% Suchmaschinen wie Google gehen davon aus, dass alle Besucher ungefähr +\index{Google}% die gleichen Suchprioritäten haben, so dass es sich lohnt, die Suchresultate nach der Wahrscheinlichkeit $P(S_i)$ zu ordnen und dem Suchenden die wahrscheinlichsten Dokumente als erste zu zeigen. @@ -113,19 +119,19 @@ wahrscheinlichsten Dokumente als erste zu zeigen. Um einen Zusammenhang zwischen $P(S_i)$ und $P(S'_j)$ herzustellen, muss die Navigation entlang der Links modelliert werden. Die naheliegende Wahrscheinlichkeitsinterpretation ist die bedingte -Wahrscheinlichkeit $P(S'_j|S_i)$ dass der Besucher auf der Seite $j$ +Wahrscheinlichkeit $P(S'_j\mid S_i)$ dass der Besucher auf der Seite $j$ landet, nachdem er auf der Seite $i$ die Linknavigation verwendet hat. Wenn es keinen Link zwischen den Seiten $i$ und $j$ gibt, dann ist diese -Navigation natürlich nicht möglich und es folgt $P(S'_j|S_i)=0$. -Falls es einen Link gibt, ist $P(S'_j|S_i)\ge 0$. +Navigation natürlich nicht möglich und es folgt $P(S'_j\mid S_i)=0$. +Falls es einen Link gibt, ist $P(S'_j\mid S_i)\ge 0$. A priori wissen wir nicht, wie wahrscheinlich es ist, dass der Besucher dem Link auf die Seite $j$ folgt, normalerweise werden nicht alle Links mit gleicher Wahrscheinlichkeit verwendet. -Wir nehmen daher zusätzlich an, dass alle Links gleich wahrscheinlich +Wir nehmen daher vereinfachend an, dass alle Links gleich wahrscheinlich sind. -Die Seite $i$ enthält $n_i$ Links, also ist die Wahrscheinlichkeit, -auf einer von $i$ aus verlinkten Seite $j$ zu landen $P(S'_j|S_i) = 1/n_i$. +Enthält die Seite $i$ genau $n_i$ Links, dann ist die Wahrscheinlichkeit, +auf einer von $i$ aus verlinkten Seite $j$ zu landen, $P(S'_j\mid S_i) = 1/n_i$. \subsubsection{Totale Wahrscheinlichkeit} Der Satz von der totalen Wahrscheinlichkeit ermöglicht, einen Zusammenhang @@ -136,13 +142,16 @@ Es gilt \begin{equation} P(S'_j) = -P(S'j|S_1) P(S_1) +P(S'j\mid S_1) P(S_1) + -P(S'j|S_2) P(S_2) +P(S'j\mid S_2) P(S_2) + \dots + -P(S'j|S_N) P(S_N). +P(S'j\mid S_N) P(S_N) += +\sum_{i=1}^N P(S_j'\mid S_i)P(S_i) +. \label{buch:google:eqn:totalewahrscheinlichkeit} \end{equation} Dies kann in Matrix- und Vektorform übersichtlicher geschrieben werden. @@ -170,18 +179,21 @@ P(S'_N) \end{pmatrix} \] zusammen. -Die bedingten Wahrscheinlichkeiten $h_{ji}=P(S'_j|S_i)$ sind mit zwei Indizes -beschrieben, sie bilden daher in natürlicher Weise eine Matrix -\[ +Die bedingten Wahrscheinlichkeiten $h_{ji}=P(S'_j\mid S_i)$ sind mit zwei Indizes +beschrieben, sie bilden daher in natürlicher Weise die sogenannte +{\em Link-Matrix} +\index{Link-Matrix}% +\begin{equation} H = \begin{pmatrix} -P(S'_1|S_1)&P(S'_1|S_2)&\dots &P(S'_1|S_N)\\ -P(S'_2|S_1)&P(S'_2|S_2)&\dots &P(S'_2|S_N)\\ +P(S'_1\mid S_1)&P(S'_1\mid S_2)&\dots &P(S'_1\mid S_N)\\ +P(S'_2\mid S_1)&P(S'_2\mid S_2)&\dots &P(S'_2\mid S_N)\\ \vdots &\vdots &\ddots&\vdots \\ -P(S'_N|S_1)&P(S'_N|S_2)&\dots &P(S'_N|S_N) +P(S'_N\mid S_1)&P(S'_N\mid S_2)&\dots &P(S'_N\mid S_N) \end{pmatrix}. -\] +\label{buch:google:eqn:linkmatrix} +\end{equation} Die Formel~\eqref{buch:google:eqn:totalewahrscheinlichkeit} wird dann zur Formel für das Produkt Matrix mal Vektor: \[ @@ -189,7 +201,7 @@ Formel für das Produkt Matrix mal Vektor: = \sum_{i=1}^N h_{ji} p_i = -\sum_{i=1}^N P(S'_j|S_i) P(S_i) +\sum_{i=1}^N P(S'_j\mid S_i) P(S_i) = p'_j \qquad\Rightarrow\qquad @@ -217,13 +229,26 @@ H = \end{equation} \qedhere \end{beispiel} - +Die Link-Matrix kann aus der Adjazenzmatrix des gerichteten Graphen +bestimmt werden. +Dazu ist zu beachten, dass jede Spalte durch die Anzahl der Einsen +in dieser Spalte zu teilen ist. +Ein Zeilenvektor, der die Zahl der Einsen enthält, entsteht durch +Multiplikation mit einem Zeilenvektor $U^t$ aus lauter Einsen. +Mit dem Hadamard-Produkt ist dann die Link-Matrix durch +\[ +H += +(U(U^tA(G))^{\odot(-1)})\odot A(G) +\] +gegeben, wobei $(U^tA(G))^{\odot(-1)}$ die Inverse bezüglich des +Hadamard-Produktes ist. % % Freier Wille % \subsection{``Freier Wille'' \label{buch:subsection:freier-wille}} -Das Modell in +Das in Abschnitt~\eqref{buch:subsection:wahrscheinlichkeitsinterpretation} beschriebene Modell geht unter anderem davon aus, dass der Benutzer ausschliesslich die Navigation entlang der Links verwendet. @@ -245,38 +270,39 @@ Wir bezeichnen das Ereignis, dass der Benutzer nicht die Link-Navigation verwendet mit $F$ für ``freier Wille'', obwohl es so etwas natürlich nicht gibt. Die Wahrscheinlichkeit, auf der Seite $S'_j$ zu landen, setzt sich jetzt -aus den zwei Fällen $F$ und $\overline{F}$ zusammen, für die erneut der +aus den zwei Fällen $F$ und $\smash{\overline{F}}$ zusammen, für die erneut der Satz von der totalen Wahrscheinlichkeit den Zusammenhang \[ P(S'_j) = -P(S'_j|\overline{F}) P(\overline{F}) +P(S'_j\mid \overline{F}) P(\overline{F}) + -P(S'_j|F) P(F) +P(S'_j\mid F) P(F) \] +liefert. Die Wahrscheinlichkeit $\alpha = P(F)$, mit der der Benutzer den -``freiene Willen'' bemüht, kann experimentell durch Studien ermittelt +``freien Willen'' bemüht, kann experimentell durch Studien ermittelt werden, die das Benutzerverhalten beobachten. -Die Wahrscheinlichkeit $P(S'_j|\overline{F})$ entsteht dadurch, dass +Die Wahrscheinlichkeit $P(S'_j\mid \overline{F})$ entsteht dadurch, dass der Benutzer der Linknavigation folgt, sie entspricht also der früher -berechnenten Wahrscheinlichkeit +berechneten Wahrscheinlichkeit \[ -P(S'_j|\overline{F}) = \sum_{i=1}^N P(S'_j|S_i) P(S_i). +P(S'_j\mid \overline{F}) = \sum_{i=1}^N P(S'_j\mid S_i) P(S_i). \] oder in Vektorform \[ -(P(S'_j|\overline{F}))_{j=1,\dots,n} +(P(S'_j\mid \overline{F}))_{j=1,\dots,n} = Hp. \] -Über die spontane Besuchswahrscheinlichkeit $P(S'_j|F)$ wissen wir +Über die spontane Besuchswahrscheinlichkeit $P(S'_j\mid F)$ wissen wir nichts. Eine erste Annahme könnte sein, dass jede Seite gleich wahrscheinlich -ist, dass also $P(S'_j|F)=1/N$. +ist, dass also $P(S'_j\mid F)=1/N$. Alternativ könnte man auch eine Wahrscheinlichkeitsverteilung -$q_j = P(S'_j|F)$ experimentell zu ermitteln versuchen. +$q_j = P(S'_j\mid F)$ experimentell zu ermitteln versuchen. Unter der Annahme, dass alle Seitenbesuche im Falle $F$ auf Grund eines Sucheresultats einer Suchmaschine erfolgen, könnte die Suchmaschine den Vektor $q$ aus ihrer eigenen Suchstatistik ermitteln. @@ -286,7 +312,7 @@ Das erweiterte Modell kann also durch P(S'_j) = \sum_{i=1}^N -\alpha P(S'_j|S_i) P(S_i) +\alpha P(S'_j\mid S_i) P(S_i) + (1-\alpha) q_j \qquad\Rightarrow\qquad @@ -309,7 +335,7 @@ Wir streben daher an, die Formel~\eqref{buch:google:eqn:composed} ebenfalls in die Form $p=Gp$ mit einer neuen Matrix $G$ zu bringen. Die Matrixform von -\label{buch:google:eqn:composed} +\eqref{buch:google:eqn:composed} zeigt, dass sich die gesuchte Matrix $G$ zusammensetzt aus dem Summanden $\alpha H$ und einem weiteren Summanden $A$ mit der Eigenschaft, dass $Ap = q$ für jeden beliebigen Wahrscheinlichkeitsvektor $p$. @@ -384,8 +410,10 @@ heisst die \index{Google-Matrix}% \end{definition} -Die Google-Matrix wurde von Sergei Brin und Larry Page -in dem Artikel \cite{BRIN1998107} als Basis der Suchmaschine +Die Google-Matrix wurde von Sergey Brin und Larry Page +\index{Brin, Sergey}% +\index{Page, Larry}% +in dem Artikel \cite{BRIN1998107} als Grundlage der Suchmaschine Google beschrieben. Sie war die Basis für den Erfolg von Google und wird dem Prinzip nach auch heute noch zur Rangierung der Suchresultate verwendet. @@ -406,6 +434,8 @@ ansehen. Die Kundenwebsite wird daher in den Suchresultaten weiter oben gezeigt. Das Problem rührt natürlich daher, dass alle Links als gleichermassen aussagekräftig betrachtet werden. +Solche Websites werden heutzutage von der Berechnung der Google-Matrix +ausgeschlossen. Die aktuell verwendete Variante der Google-Matrix ist natürlich ein Betriebsgeheimnis der Firma Google. @@ -417,7 +447,7 @@ Betriebsgeheimnis der Firma Google. \label{buch:subsection:wahrscheinlichkeitsverteilung}} Die Google-Matrix $G$ selbst interessiert weniger als die Wahrscheinlichkeitsverteilung $p$. -Ziel dieses Abschnittes, ist den Vektor $p$ zu berechnen. +Ziel dieses Abschnittes ist, den Vektor $p$ zu berechnen. \subsubsection{Stationäre Verteilung} Die Einträge $P(S_i)$ des Vektors $p$ geben die Wahrscheinlichkeit an, mit @@ -445,14 +475,17 @@ Gp = p. $p$ ist also ein Eigenvektor der Matrix $G$ zum Eigenwert $1$. Für ein sehr kleines Netzwerk wie im oben dargestellten Beispiel ist es -einfach, mit verbreiteten numerischen Algorithmen alle Eigenwerte und +einfach, mit gängigen numerischen Algorithmen alle Eigenwerte und Eigenvektoren zu finden. Benötigt wird allerdings nur der Eigenvektor zum Eigenwert $1$. \begin{beispiel} -Ein Eigenvektor zum Eigenwert $1$ der Matrix $G$, die aus der Matrix $H$ +Octave +\index{Octave} +findet den folgenden Eigenvektor zum Eigenwert $1$ der Matrix $G$, +die aus der Matrix $H$ von \eqref{buch:google:eqn:linkmatrixbeispiel} -und dem Vektor $q=\frac18u$ und $\alpha=0.9$ gebildet wurde, ist +und dem Vektor $q=\frac18U$ und $\alpha=0.9$ gebildet wurde: \[ p_0=\begin{pmatrix} 0.20100\\ @@ -491,10 +524,14 @@ erhält man die Wahrscheinlichkeitsverteilung $p$. \subsubsection{Potenzverfahren} -Die üblichen Algorithmen wie der Francis-Algorithmus zur Bestimmung -von Eigenwerten und Eigenvektoren ist für grosse Matrizen nicht praktikabel. +Die üblichen Algorithmen wie der von den meisten Softwarepaketen +verwendete Francis-Algorithmus \cite{francis:watkins_paper,buch:watkins} +\index{Francis-Algorithmus}% +zur Bestimmung von Eigenwerten +und Eigenvektoren ist für grosse Matrizen nicht praktikabel. Da aber $1$ der betragsgrösste Eigenwert ist, kann sehr oft ein zugehöriger Eigenvektor mit der nachfolgend beschriebenen {\em Potenzmethode} +\index{Potenzmethode}% gefunden werden. Sei $A$ eine $n\times n$-Matrix, der Einfachheit halber nehmen wir an, @@ -535,8 +572,8 @@ a_n\biggl(\frac{\lambda_n}{\lambda_1}\biggr)^k v_n. \] Da alle Brüche Betrag $<1$ haben, konvergiert die rechte Seite für $k\to\infty$ gegeben den ersten Summanden. -Durch wiederholte Anwendung von $A/\lambda_1$ auf einen (fast) belieibigen -Startvektor $v$ erhält man also eine Folge von Vektoren, die gegen eine +Durch wiederholte Anwendung von $A/\lambda_1$ auf einen (fast) beliebigen +Startvektor $v$ erhält man also eine Folge von Vektoren, die gegen einen Eigenvektor zum Eigenwert $\lambda_1$ konvergiert. Numerische Ungenauigkeiten können bewirken, dass die Iteration mit der diff --git a/buch/chapters/80-wahrscheinlichkeit/markov.tex b/buch/chapters/80-wahrscheinlichkeit/markov.tex index 0485714..1e30010 100644 --- a/buch/chapters/80-wahrscheinlichkeit/markov.tex +++ b/buch/chapters/80-wahrscheinlichkeit/markov.tex @@ -18,7 +18,10 @@ werden. % \subsection{Markov-Eigenschaft} % XXX Notation, Zustände, Übergangswahrscheinlichkeit -Ein stochastischer Prozess ist eine Familie von Zustandsvariablen +Ein stochastischer Prozess ist eine Familie von Zufallsvariablen +\index{stochastischer Prozess}% +\index{Prozess, stochastisch}% +\index{Zufallsvariable}% $X_t$ mit Werten in einer Menge $\mathcal{S}$ von Zuständen. Der Parameter $t$ wird üblicherweise als die Zeit interpretiert, er kann beliebige reelle Werte oder diskrete Werte annahmen, im letzten @@ -36,6 +39,7 @@ Zustands $s\in\mathcal{S}$ zu einem späteren Zeitpunkt $t_1>t_0$ zu studieren. Das Ereignis $\{X_t = x\}$ kann man sich als abhängig von der Vorgeschichte vorstellen. +\index{Vorgeschichte}% Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse \[ \{X_0=x_0\}, @@ -47,7 +51,7 @@ Die Vorgeschichte besteht dabei aus dem Eintreten gewisser Ereignisse zu früheren Zeiten $t_0s$ bestimmen das +Die Wahrscheinlichkeiten $P(X_t=x\mid X_s=y)$ mit $t>s$ bestimmen das zeitliche Verhalten der Wahrscheinlichkeiten vollständig. Wir schreiben daher auch \[ p_{xy}(t, s) = -P(X_t = x|X_s=y) +P(X_t = x\mid X_s=y) \] für die sogenannte {\em transiente Übergangswahrscheinlichkeit}. +\index{transiente Übergangswahrscheinlichkeit}% Für eine endliche Menge von Zuständen, können die transienten Übergangswahrscheinlichkeiten auch als zeitabhängige quadratische Matrix $P(s,t)$ geschrieben werden, deren @@ -105,13 +111,14 @@ mit den Zuständen $x,y\in\mathcal{S}$ indiziert sind. \subsubsection{Die Chapman-Kolmogorov-Gleichung} % XXX Chapman-Kolmogorov-Gleichung +\index{Chapman-Kolmogorov-Gleichung}% Man beachte, dass in der Definition der Markov-Eigenschaft keine Voraussetzungen darüber gemacht werden, wie nahe am Zeitpunkt $t$ der letzte Zeitpunkt $t_n$ der Vorgeschichte liegt. Die transienten Übergangswahrscheinlichkeiten $p_{xy}(s,t)$ werden aber im allgemeinen davon abhängen, wie weit in der Vergangenheit der Zeitpunkt $s0$ ist. Damit ist die Perron-Frobenius-Theorie von @@ -263,6 +264,7 @@ Abschnitt~\ref{buch:section:positive-vektoren-und-matrizen} anwendbar. Ein Eigenvektor zum Eigenwert $1$ kann mit Hilfe des Gauss-Algorithmus +\index{Gauss-Algorithmus}% gefunden werden: \begin{align*} \begin{tabular}{|>{$}c<{$}>{$}c<{$}>{$}c<{$}|} @@ -301,7 +303,7 @@ Daraus liest man einen möglichen Lösungsvektor mit den Komponenten $5$, $2$ und $6$ ab. Wir suchen aber einen Eigenvektor, der als Wahrscheinlichkeitsverteilung dienen kann. -Dazu müssen sich die Komponente zu $1$ summieren, was man durch normieren +Dazu müssen sich die Komponenten zu $1$ summieren, was man durch Normieren in der $l^1$-Norm erreichen kann: \begin{equation} p @@ -344,11 +346,13 @@ nach \begin{align*} P(Y=+1) &= -P(Y=+1|K\equiv 0) \cdot P(K\equiv 0) +P(Y=+1\mid K\equiv 0) \cdot P(K\equiv 0) + -P(Y=+1|K\equiv 1) \cdot P(K\equiv 1) +P(Y=+1\mid K\equiv 1) \cdot P(K\equiv 1) +\\ +&\qquad + -P(Y=+1|K\equiv 2) \cdot P(K\equiv 2) +P(Y=+1\mid K\equiv 2) \cdot P(K\equiv 2) \\ &= \frac{1}{10}\cdot\frac{5}{13} @@ -368,11 +372,13 @@ P(Y=+1|K\equiv 2) \cdot P(K\equiv 2) \\ P(Y=-1) &= -P(Y=-1|K\equiv 0) \cdot P(K\equiv 0) +P(Y=-1\mid K\equiv 0) \cdot P(K\equiv 0) + -P(Y=-1|K\equiv 1) \cdot P(K\equiv 1) +P(Y=-1\mid K\equiv 1) \cdot P(K\equiv 1) +\\ +&\qquad + -P(Y=-1|K\equiv 2) \cdot P(K\equiv 2) +P(Y=-1\mid K\equiv 2) \cdot P(K\equiv 2) \\ &= \frac{9}{10}\cdot\frac{5}{13} @@ -479,9 +485,9 @@ G\odot F = \begin{pmatrix} Nach der früher dafür gefundenen Formel ist \begin{align*} \begin{pmatrix} -E(Y|K\equiv 0)& -E(Y|K\equiv 1)& -E(Y|K\equiv 2) +E(Y\mid K\equiv 0)& +E(Y\mid K\equiv 1)& +E(Y\mid K\equiv 2) \end{pmatrix} &= U^t (G\odot \tilde{B}) @@ -710,10 +716,10 @@ A=\begin{pmatrix} \subsubsection{Das Spiel $C$} In jeder Durchführung des Spiels wird mit einem Münzwurf entschieden, ob Spiel $A$ oder Spiel $B$ gespielt werden soll. -Mit je Wahrscheinlichkeit $\frac12$ werden also die Übergansmatrizen +Mit Wahrscheinlichkeit je $\frac12$ werden also die Übergansmatrizen $A$ oder $B$ verwendet: \[ -P(K\equiv i|K\equiv j) +P(K\equiv i\mid K\equiv j) = A\cdot P(\text{Münzwurf Kopf}) + diff --git a/buch/chapters/80-wahrscheinlichkeit/positiv.tex b/buch/chapters/80-wahrscheinlichkeit/positiv.tex index 9f8f38f..159d6d3 100644 --- a/buch/chapters/80-wahrscheinlichkeit/positiv.tex +++ b/buch/chapters/80-wahrscheinlichkeit/positiv.tex @@ -7,15 +7,18 @@ \label{buch:section:positive-vektoren-und-matrizen}} \rhead{Positive Vektoren und Matrizen} Die Google-Matrix und die Matrizen, die wir in Markov-Ketten angetroffen +\index{Google-Matrix}% haben, zeichnen sich dadurch aus, dass alle ihre Einträge positiv oder mindestens nicht negativ sind. Die Perron-Frobenius-Theorie, die in diesem Abschnitt entwickelt +\index{Perron-Frobenius-Theorie}% werden soll, zeigt, dass Positivität einer Matrix nützliche Konsequenzen für Eigenwerte und Eigenvektoren hat. -Das wichtigste Resultat ist die Tatsache, dass postive Matrizen immer +Das wichtigste Resultat ist die Tatsache, dass positive Matrizen immer einen einzigen einfachen Eigenwert mit Betrag $\varrho(A)$ haben, -was zum Beispiel die Konvergenz des Pagerank-Algorithmus garantiert. -Dies wird im Satz von Perron-Frobenius in +was zum Beispiel die Konvergenz des PageRank-Algorithmus garantiert. +Dies wird im Satz~\ref{buch:wahrscheinlichkeit:satz:perron-frobenius} +von Perron-Frobenius in Abschnitt~\ref{buch:subsection:der-satz-von-perron-frobenius} erklärt. @@ -42,6 +45,8 @@ seine Komponenten nicht negativ sind: $v_i\ge 0\forall i$. Geometrisch kann man sich die Menge der positven Vektoren in zwei Dimensionen als die Punkte des ersten Quadranten oder in drei Dimensionen als die +\index{Quadrant}% +\index{Oktant}% Vektoren im ersten Oktanten vorstellen. Aus der Positivität eines Vektors lässt sich jetzt eine Vergleichsrelation @@ -62,9 +67,9 @@ Die Definition funktionieren analog auch für Matrizen: \begin{definition} Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em positiv}, -wenn alle ihre Einträge $a_{ij}$ positiv sind: $a_{ij}>0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ positiv sind: $a_{i\!j}>0\forall i,j$. Eine Matrix $A\in M_{m\times n}(\mathbb{R})$ heisst {\em nichtnegativ}, -wenn alle ihre Einträge $a_{ij}$ nichtnegativ sind: $a_{ij}\ge 0\forall i,j$. +wenn alle ihre Einträge $a_{i\!j}$ nichtnegativ sind: $a_{i\!j}\ge 0\forall i,j$. \index{positive Matrix}% \index{nichtnegative Matrix}% Man schreibt $A>B$ bzw.~$A\ge B$ wenn $A-B>0$ bzw.~$A-B\ge 0$. @@ -133,7 +138,7 @@ Die Zyklen-Zerlegung einer Permutationsmatrix zeigt, welche Unterräume von $\mathbb{R}^n$ die iterierten Bilder eines Standardbasisvektors aufspannen. Diese sind invariante Unterräume der Matrix. -Das im Beispiel illustrierte Phänomen findet dann nur in invarianten +Das im Beispiel illustrierte Phänomen findet nur in invarianten Unterräumen statt. \begin{beispiel} @@ -151,7 +156,7 @@ A=\begin{pmatrix} \end{equation} besteht aus zwei $3\times 3$-Blöcken. Die beiden Unterräume $V_1=\langle e_1,e_2,e_3\rangle$ -und $V_2=\langle e_4,e_5,e_6\rangle$ sind daher invariante +und $V_2=\langle e_4,e_5,e_6\rangle$ sind invariante Unterräume von $A$ und damit auch von $A^n$. Die Potenzen haben daher auch die gleich Blockstruktur. Insbesondere sind zwar die Blöcke von $A^n$ für $n>1$ positive @@ -161,6 +166,7 @@ Teilmatrizen, aber die Matrix $A^n$ ist für alle $n$ nicht positiv. \begin{definition} Eine nichtnegative Matrix mit der Eigenschaft, dass $A^n>0$ für ein genügend grosses $n$, heisst {\em primitiv}. +\index{primitive Matrix}% \end{definition} Die Matrix $A$ von \eqref{buch:wahrscheinlichkeit:eqn:diffusion} @@ -200,6 +206,7 @@ hinaus. \begin{satz}[Trenntrick] \label{buch:wahrscheinlichkeit:satz:trenntrick} +\index{Trenntrick}% Sind $u$ und $v$ nichtnegative Vektoren und $u>v$, dann gibt es eine positive Zahl $\varepsilon>0$ derart, dass $u\ge (1+\varepsilon)v$. @@ -214,7 +221,7 @@ Wir betrachten die Zahl = \max_{v_i\ne 0} \frac{u_i}{v_i}. \] -Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>0$. +Wegen $u>v$ sind die Quotienten auf der rechten Seite alle $>1$. Da nur endlich viele Quotienten miteinander verglichen werden, ist daher auch $\vartheta >1$. Es folgt $u\ge \vartheta v$. @@ -244,6 +251,7 @@ $Au>Av$ (siehe auch Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick}) \begin{satz}[Vergleichstrick] \label{buch:wahrscheinlichkeit:satz:vergleichstrick} +\index{Vergleichstrick}% Sei $A$ eine positive Matrix und seinen $u$ und $v$ Vektoren mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$ (siehe auch Abbildung~\ref{buch:wahrscheinlichkeit:fig:vergleich}). @@ -251,8 +259,8 @@ mit $u\ge v$ und $u\ne v$, dann ist $Au > Av$ \begin{proof}[Beweis] Wir schreiben $d=u-v$, nach Voraussetzung ist $d\ne 0$. -Der Satz besagt dann, dass aus $d\ge 0$ folgt, dass $Ad>0$, dies -müssen wir beweisen. +Der Satz besagt dann, dass aus $d\ge 0$ folgt, dass $Ad>0$. +Dies müssen wir beweisen. Die Ungleichung $Ad>0$ besagt, dass alle Komponenten von $Ad$ positiv sind. @@ -261,16 +269,16 @@ Um dies nachzuweisen, berechnen wir (Ad)_i = \sum_{j=1}^n -a_{ij} +a_{i\!j} d_j. \label{buch:wahrscheinlichkeit:eqn:Adpositiv} \end{equation} -Alle Terme $a_{ij}>0$, weil $A$ positiv ist, und mindestens eine -der Komponenten $d_j>0$, weil $d\ne 0$. +Alle Koeffizienten $a_{i\!j}$ sind $>0$, weil $A$ positiv ist. +Mindestens eine der Komponenten $d_j$ ist $>0$, weil $d\ne 0$. Insbesondere sind alle Terme der Summe $\ge 0$, woraus wir bereits schliessen können, dass $(Ad)_i\ge 0$ sein muss. Die Komponente $d_j>0$ liefert einen positiven Beitrag -$a_{ij}d_j>0$ +$a_{i\!j}d_j>0$ zur Summe~\eqref{buch:wahrscheinlichkeit:eqn:Adpositiv}, also ist $(Ad)_i>0$. \end{proof} @@ -284,8 +292,8 @@ Ist $A$ eine positive Matrix und $u\ge 0$ mit $u\ne 0$, dann ist $Au>0$. \end{korollar} -Eine positive Matrix macht also aus nicht verschwindenden -und nicht negativen Vektoren positive Vektoren. +Eine positive Matrix macht also aus nicht verschwindenden, +nicht negativen Vektoren positive Vektoren. % % Die verallgemeinerte Dreiecksungleichung @@ -331,30 +339,38 @@ eines gemeinsamen Einheitsvektors $c$ sind: $u_i=|u_i|c$ \begin{proof}[Beweis] Die Aussage kann mit vollständiger Induktion bewiesen werden. -Die Induktionsverankerung ist der Fall $n=2$ gegeben durch die +Die Induktionsverankerung ist der Fall $n=2$, gegeben durch die gewöhnliche Dreiecksungleichung. Wir nehmen daher jetzt an, die Aussage sei für $n$ bereits bewiesen, -wir müssen sie dann für $n+1$ beweisen. +wir müssen sie für $n+1$ beweisen. Die Summe von $n+1$ Vektoren kann man $u=u_1+\dots+u_n$ und $v=u_{n+1}$ aufteilen. -Es gilt dann +Es gilt nach der gewöhnlichen Dreiecksungleichung, dass \[ |u+v| = |u_1+\dots+u_n+u_{n+1}| +\le +|u_1+\dots+u_n|+|u_{n+1}| \] -und +mit Gleichheit genau dann, wenn $u_1+\dots+u_n$ und $u_{n+1}$ +linear abhängig sind. +Nach Induktionsannahme gilt ausserdem \[ -|u_1+\dots+u_n| = |u_1|+\dots+|u_n|. +|u_1+\dots+u_n| \le |u_1|+\dots+|u_n| \] -Aus der Induktionsannahme folgt dann, dass die Vektoren $u_1,\dots,u_n$ +mit Gleichheit genau dann, wenn die Vektoren $u_1,\dots,u_n$ positive Vielfache eines Einheitsvektors $u$ sind, $u_i=|u_i|c$. Es ist dann \[ -u=u_1+\dots+u_n = \biggl(\sum_{i=1}^n |u_i|\biggr). +u=u_1+\dots+u_n += +\biggl(\sum_{i=1}^n |u_i|c\biggr) += +\biggl(\sum_{i=1}^n |u_i|\biggr)c. \] -Aus der gewöhnlichen Dreiecksungleichung, angewendet auf $u$ und $v$ +Da $|u+v|=|u|+|v|$ genau dann gilt, wenn $u$ und $v$ linear abhängig sind, folgt jetzt, dass $v$ ebenfalls ein nichtnegatives Vielfaches von $c$ ist. Damit ist der Induktionsschritt vollzogen. \end{proof} @@ -380,7 +396,7 @@ Die motiviert den nachstehenden geometrischen Beweis des Satzes. \begin{proof}[Beweis] Wer stellen uns die komplexen Zahlen $u_i$ als Vektoren in der -zweidimensionalen Gaussschen Ebene vor. +zweidimensionalen Gauss\-schen Ebene vor. Dann ist die Aussage nichts anderes als ein Spezialfall von Satz~\ref{buch:wahrscheinlichkeit:satz:verallgemeinerte-dreiecksungleichung} für den zweidimensionalen reellen Vektorraum $\mathbb{C}$. @@ -396,8 +412,8 @@ Wir sind an den Eigenwerten und Eigenvektoren einer positiven oder primitiven Matrix interessiert. Nach Definition des Spektralradius $\varrho(A)$ muss es einen Eigenvektor zu einem Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$ geben, -aber a priori wissen wir nicht, ob es einen reellen Eigenwert vom -Betrag $\varrho(A)$ gibt, und ob der Eigenvektor dazu reell ist. +aber a priori wissen wir nicht, ob es einen reellen Eigenvektor zum +Eigenwert $\varrho(A)$ gibt. \begin{figure} \centering @@ -415,14 +431,16 @@ Iteriert man dies (Abbildung~\ref{buch:wahrscheinlichkeit:figure:positiv}), wird die Bildmenge immer enger, bis sie nur ein sehr enger Kegel um die Richtung des Eigenvektors ist. Tatsächlich kann man aus dieser Idee auch einen topologischen -Beweis des untenstehenden Satzes von Perron-Frobenius konstruieren. +Beweis des untenstehenden Satzes von Perron-Frobenius konstruieren +(\cite{skript:pftopo} und +\cite{skript:hilbertmetric}). Er beruht darauf, dass eine Abbildung, die Distanzen verkleinert, einen Fixpunkt hat. Die Konstruktion einer geeigneten Metrik ist allerdings eher kompliziert, weshalb wir im Beweise der nachstehenden Aussagen den konventionellen Weg wählen. -Wir beginnen damit zu zeigen, dass für positive Matrizen $A$, +Wir beginnen damit zu zeigen, dass für positive Matrizen $A$ nichtnegative Eigenvektoren zu Eigenwerten $\lambda\ne 0$ automatisch positiv sind. Ausserdem müssen die zugehörigen Eigenwerte sogar positiv sein. @@ -444,6 +462,14 @@ alle Komponenten von $\lambda u$ positiv sein. Das ist nur möglich, wenn $\lambda > 0$. \end{proof} +Wenn $v$ ein Eigenvektor von $A$ ist, dann ist auch jedes Vielfache +davon ein Eigenvektor, insbesondere können einzelne Komponenten +des Vektors $v$ auch negativ sein. +Der folgende Satz zeigt aber, dass man der Vektor aus den Beträgen +von der Komponenten von $v$ ebenfalls ein Eigenvektor zum +gleichen Eigenwert ist. +Insbesondere gibt es immer einen nichtnegativen Eigenvektor. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:positivereigenvektor} Sei $A$ eine positive Matrix und $v$ ein Eigenvektor von $A$ zu einem @@ -457,12 +483,12 @@ Es gilt natürlich auch, dass \[ (Au)_i = -\sum_{j=1}^n a_{ij}u_j +\sum_{j=1}^n a_{i\!j}u_j = -\sum_{j=1}^n |a_{ij}v_j| +\sum_{j=1}^n |a_{i\!j}v_j| \ge \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = |(Av)_i| @@ -490,22 +516,26 @@ können wir jetzt eine Zahl $\vartheta>1$ finden derart, dass A^2 u \ge \vartheta \varrho(A) Au \] ist. -Durch weitere Anwendung von $A$ findet man -\begin{align*} +Durch wiederholte Anwendung von $A$ findet man +\begin{align} A^3 u & \ge (\vartheta \varrho(A))^2 Au +\notag \\ &\phantom{0}\vdots +\notag \\ A^{k+1} u & \ge (\vartheta \varrho(A))^{k} Au -\end{align*} -Daraus kann man jetzt die Norm abschätzen: +\label{buch:pf:eqn:ak+1} +\end{align} +Aus $|A^{k+1}u| \le \|A^k\|\,|Ak|$ und +\eqref{buch:pf:eqn:ak+1} kann man jetzt die Norm von $A^k$ abschätzen: \[ \begin{aligned} -\| A^{k}\|\, |Au| +\| A^{k}\|\cdot |Au| &\ge -\| A^{k+1}u\| +| A^{k+1}u| \ge -(\vartheta\varrho(A))^{k} |Au| +(\vartheta\varrho(A))^{k}\, |Au| && \Rightarrow & @@ -518,8 +548,11 @@ Daraus kann man jetzt die Norm abschätzen: \lim_{k\to\infty} \|A^k\|^{\frac{1}{k}} &\ge \vartheta\varrho(A) \\ -&&&\Rightarrow& -\varrho(A)&\ge \vartheta\varrho(A) +&&&&\|\phantom{00}& +\\ +&&&%\Rightarrow& +& +\varrho(A)&\ge \vartheta\varrho(A). \end{aligned} \] Wegen $\vartheta>1$ ist dies aber gar nicht möglich. @@ -527,6 +560,10 @@ Dieser Widerspruch zeigt, dass $u=v$ sein muss, insbesondere ist $v$ ein nichtnegativer Eigenvektor. \end{proof} +Die Potenzmethode funktioniert nur, wenn kein anderer Eigenwert +den Betrag $\varrho(A)$ hat. +Der folgende Satz garantiert dies. + \begin{satz} Sei $A$ eine positive Matrix und $v$ ein Eigenvektor zu einem Eigenwert $\lambda$ mit Betrag $|\lambda|=\varrho(A)$. @@ -541,24 +578,22 @@ Aus der Eigenvektorgleichung für $u$ folgt \begin{equation} Au = \varrho(A) u \quad\Rightarrow\quad -\sum_{j=1}^n a_{ij}|v_j| = \varrho(A) |v_i|. +\sum_{j=1}^n a_{i\!j}|v_j| = \varrho(A) |v_i|. \label{buch:wahrscheinlichkeit:eqn:pev1} \end{equation} Anderseits ist $v$ ein Eigenvektor zum Eigenwert $\lambda$, also gilt \[ -\sum_{j=1}^n a_{ij}v_j = \lambda v_i. +\sum_{j=1}^n a_{i\!j}v_j = \lambda v_i. \] Der Betrag davon ist \begin{equation} \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = |\lambda v_i| = -\varrho(A) |v_i| -= -\varrho |v_i|. +\varrho(A) |v_i|. \label{buch:wahrscheinlichkeit:eqn:pev2} \end{equation} Die beiden Gleichungen @@ -566,28 +601,35 @@ Die beiden Gleichungen und \eqref{buch:wahrscheinlichkeit:eqn:pev2} zusammen ergeben die Gleichung -\[ +\begin{equation} \biggl| -\sum_{j=1}^n a_{ij}v_j +\sum_{j=1}^n a_{i\!j}v_j \biggr| = -\sum_{j=1}^n a_{ij}|v_j|. -\] +\sum_{j=1}^n a_{i\!j}|v_j|. +\label{buch:pf:eqn:gleich} +\end{equation} Nach der verallgemeinerten Dreiecksungleichung Satz~\ref{buch:subsection:verallgemeinerte-dreiecksungleichung} -folgt jetzt, dass es eine komplexe Zahl $c$ vom Betrag $1$ gibt derart, +folgt jetzt aus der Gleichheit in~\eqref{buch:pf:eqn:gleich}, +dass es eine komplexe Zahl $c$ vom Betrag $1$ gibt derart, dass $v_j = |v_j|c=u_jc$. -Insbesondere ist $v=cu$ und damit ist +Insbesondere ist $v=cu$. +Damit kann man jetzt $\lambda$ berechnen, es ist \[ \lambda v = Av = Acu = c Au = c\varrho(A) u = \varrho(A) v, \] woraus $\lambda=\varrho(A)$ folgt. \end{proof} +In Anwendungen wollen wir schliessen, dass die Grenzverteilung +eindeutig ist, dazu ist notwendig, dass der Eigenraum des +Eigenwertes $\varrho(A)$ eindimensional ist. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:geometrischeinfach} -Der Eigenraum einer positiven Matrix $A$ zum Eigenwert $\varrho(A)$ ist -eindimensional. +Der Eigenraum $E_{\varrho(A)}(A)$ einer positiven Matrix $A$ +zum Eigenwert $\varrho(A)$ ist eindimensional. \end{satz} \begin{proof}[Beweis] @@ -613,7 +655,7 @@ A(u-cv) \] Der Vektor auf der rechten Seite hat mindestens eine verschwindende Komponente. -Der Vektor auf der linken Seite ist nach Vergleichstrick +Der Vektor auf der linken Seite ist nach dem Vergleichstrick Satz~\ref{buch:wahrscheinlichkeit:satz:vergleichstrick} \[ A(u-cv) > 0, @@ -623,14 +665,20 @@ Dieser Widerspruch zeigt, dass die Annahme, es gäbe einen von $u$ linear unabhängigen Eigenvektor zum Eigenwert $\varrho(A)$ nicht haltbar ist. \end{proof} +Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach} garantiert, +dass der Eigenwert einfach ist. +Es ist aber immer noch möglich, dass die algebraische Vielfachheit +von $\varrho(A) >1$ ist, dass also $\dim\mathcal{E}_{\varrho(A)}(A)>1$ +ist. +Dies ist jedoch nicht der Fall. + \begin{satz} \label{buch:wahrscheinlichkeit:satz:algebraischeinfach} -Der verallgemeinerte Eigenraum zum Eigenwert $\varrho(A)$ einer -positiven Matrix $A$ ist eindimensional. +Sei $A$ eine positive Matrix und $p^t$ ein positiver Eigenvektor +der Matrix $A^t$ zum Eigenwert $\varrho(A^t)=\varrho(A)$. Ist $u$ der Eigenvektor von $A$ zum Eigenwert $\varrho(A)$ nach -Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach} -und $p^t$ der entsprechende Eigenvektor $A^t$, dann -ist +Satz~\ref{buch:wahrscheinlichkeit:satz:geometrischeinfach}, +dann ist \[ \mathbb{R}^n = @@ -643,6 +691,8 @@ ist \ker p \] eine Zerlegung in invariante Unterräume von $A$. +Insbesondere ist der verallgemeinerte Eigenraum $\mathcal{E}_{\varrho(A)}(A)$ +von $A$ eindimensional. \end{satz} \begin{proof}[Beweis] @@ -652,7 +702,8 @@ Insbesondere ist $u\not\in\ker p$ Es ist klar, dass $A\langle u\rangle = \langle Au\rangle = \langle u\rangle$ ein invarianter Unterraum ist. -Für einen Vektor $x\in\mathbb{R}^n$ mit $px=0$ erfüllt das Bild $Ax$ +Für einen Vektor $x\in\mathbb{R}^n$ mit $px=0$, also $x\in\ker p$, +erfüllt das Bild $Ax$ die Gleichung \[ p(Ax)=(pA)x=(A^tp^t)^tx= \varrho(A)(p^t)^tx @@ -666,8 +717,8 @@ $\ker p$ ist $(n-1)$-dimensional, $\langle u\rangle$ ist eindimensional und $u$ ist nicht in $\ker p$ enthalten. Folglich spannen $\langle u\rangle$ und $\ker p$ den ganzen Raum auf. -Gäbe es einen weitern linear unabhängigen Vektor im verallgemeinerten -Eigenraum von $\mathcal{E}_{\varrho(A)}$, dann müsste es auch einen +Gäbe es einen weiteren linear unabhängigen Vektor im verallgemeinerten +Eigenraum $\mathcal{E}_{\varrho(A)}(A)$, dann müsste es auch einen solchen Vektor in $\ker p$ geben. Da $\ker p$ invariant ist, müsste es also auch einen weiteren Eigenvektor $u_2$ zum Eigenwert $\varrho(A)$ in $\ker p$ geben. @@ -712,10 +763,10 @@ Dann ist $\varrho(A)$ der einzige Eigenwert vom Betrag $\varrho(A)$ und er hat geometrische und algebraische Vielfachheit $1$. \end{satz} -\begin{proof}[Beweis] +\begin{proof}[Beweisansatz] 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 +Man kann zeigen, dass die Eigenvektoren von $A^n$ auch +Eigenvektoren von $A$ sind. \end{proof} diff --git a/buch/chapters/90-crypto/chapter.tex b/buch/chapters/90-crypto/chapter.tex index d2fcbbf..56086af 100644 --- a/buch/chapters/90-crypto/chapter.tex +++ b/buch/chapters/90-crypto/chapter.tex @@ -5,9 +5,9 @@ % (c) 2020 Prof Dr Andreas Müller, Hochschule Rapperswil % % !TeX spellcheck = de_CH -\chapter{Anwendungen in Kryptographie und Codierungstheorie +\chapter{Anwendungen in Kryptographie \label{buch:chapter:kryptographie}} -\lhead{Kryptographie und Codierungstheorie} +\lhead{Kryptographie} \rhead{} Die algebraische Theorie der endlichen Körper hat sich als besonders nützliche herausgestellt in der Krypographie. diff --git a/buch/chapters/references.bib b/buch/chapters/references.bib index fb88d09..979f985 100644 --- a/buch/chapters/references.bib +++ b/buch/chapters/references.bib @@ -162,3 +162,35 @@ abstract = "In this paper, we present Google, a prototype of a large-scale searc year = 2011, language = {english} } + +@article{francis:watkins_paper, + ISSN = {00029890, 19300972}, + URL = {http://www.jstor.org/stable/10.4169/amer.math.monthly.118.05.387}, + author = {David S. Watkins}, + journal = {The American Mathematical Monthly}, + number = {5}, + pages = {387--403}, + publisher = {Mathematical Association of America}, + title = {Francis’ Algorithm}, + volume = {118}, + year = {2011} +} + +@article{skript:pftopo, + author = { Geon H. Ghoe }, + journal = { Communications of the Korean Mathematical Society }, + volume = {9}, + number = {3}, + pages = {565--570}, + year = {1994} +} + +@article{skript:hilbertmetric, + author = { Elon Kohlberg and John W. Pratt }, + title = {The contraction mapping approach to the Perron-Frobenius theory: why Hilbert's metric? }, + journal = {Mathematics of Operations Research}, + year = {1982}, + volume = {7}, + number = {2}, + pages = {192--210} +} -- cgit v1.2.1