\documentclass[german]{article} \usepackage{amsmath} % Mathe \usepackage{amssymb} % Symbole \usepackage{amsfonts} % Symbole \usepackage{mathrsfs} % Skritpbuchstaben \usepackage{enumerate} % Listenkonfiguration \usepackage{graphicx} % Bilder einbinden \usepackage[german]{babel} \newtheorem{theorem}{Satz}[section] \newtheorem{proposition}[theorem]{Proposition} \newtheorem{definition}[theorem]{Definition } \newtheorem{bsp}[theorem]{Beispiel} \newenvironment{proof}[1][Beweis]{\noindent\textbf{#1.} }{\hfill $\square$} \newcommand{\E}{\mathscr{E}} \renewcommand{\P}{\mathbb{P}} \newcommand{\K}{\mathbb{K}} \newcommand{\C}{\mathbb{C}} \newcommand{\R}{\mathbb{R}} \newcommand{\Z}{\mathbb{Z}} \newcommand{\N}{\mathbb{N}} \newcommand{\Bild}{\mathrm{Bild}} \newcommand{\Kern}{\mathrm{Bild}} \begin{document} \noindent {\sf Benjamin Debeerst} \hfill { \sf Philipps-Universit\"at Marburg} \\ \noindent {\sf Ausarbeitungen zum Seminar \"uber algebraische Statistik} \bigskip \bigskip {\noindent\LARGE{\bf Relationen bedingter Wahrscheinlichkeiten}} \bigskip %\section{Projektive Geometrie und torische Variet\"aten} \section{Projektive R\"aume und homogene Koordinaten} Sei $V$ ein $\K$-Vektorraum der Dimension $n+1$. Identifiziert man in diesem Vektorraum jeweils die Elemente jedes 1-dimensionalen Unterraums au\ss er der 0, so erh\"alt man einen projektiven Raum $\P(V)$ der Dimension $n$. Es gilt also $$\P(V) := (V \setminus \{ 0\})/\sim ,$$ wobei f\"ur a, b aus V gilt: $$a \sim b \Leftrightarrow \exists \lambda \in \K\setminus\{0\}: a = \lambda \cdot b.$$ Im Fall $V = \K^{n+1}$ schreibt man $\P(V)$ als $\P^n$ und die Elemente aus $\P^n$ in homogenen Koordinaten $(v_0:...:v_n)$. Offenbar ist die Darstellung eines solchen Punktes in homogenen Koordinaten nicht eindeutig, da $$\lambda \cdot (v_0:...:v_n) = (\lambda v_0:...:\lambda v_n) = (v_0:...:v_n), \forall \lambda \in \K\setminus\{0\}$$ Mit der injektiven Abbildung \begin{align*} \pi: \qquad \K^n \; \quad &\longrightarrow \qquad \quad\P^n \\ (a_1,...,a_n) &\longmapsto (1:a_1:...:a_n) \end{align*} kann man $\K^n$ als Teilmenge des $\P^n$ verstehen. Es gilt $\Bild(\pi) = \{a \in \P^n : a_0 \neq 0\}$. Anschaulich erh\"alt man den $\P^n$ indem man den $\K^n$ um eine “unendlich ferne Hyperebene” erweitert; die Punkte $(1:...)$ repr\"asentieren dabei die affinen Punkte, die Punkte $(0:...)$ repr\"asentieren die unendlich fernen Punkte, wobei der hintere Teil der Koordinaten die “Richtung” des unendlich fernen Punktes angibt. \begin{figure} \includegraphics{p1.pdf} \includegraphics{p2.pdf} \caption{Konstruktion des $\P^1$ und des $\P^2$ \"uber $\R$} \label{p1p2} \end{figure} In der Abbildung \ref{p1p2} sind die Konstruktionen des $\P^1$ und des $\P^2$ veranschaulicht. Der Halbkreis im linken Bild ist isomorph zu $\R^1 \cup \{\infty \} \cong \P^1$. Im rechten Bild sieht man die Einbettung von $\R^2$ in $\P(\R^3) = \P^2$. Die Geraden, die die eingezeichnete Ebene schneiden, entsprechen im $\R^2$ ihren Schnittpunkten mit dieser Ebene. Die Geraden, die parallel zur Ebene verlaufen, entsprechen den unendlichen fernen Punkten, genauer sogar dem $\P^1$, denn es gilt $\P^2 \cong \R^2 \cup \P^1$. Interpretiert man die im Bild vertikale Koordinatenachse als die $x_1$-Achse, so sieht man anschaulich, warum die Punkte mit $x_1 = 0$ den unendlich fernen Punkten und die Punkte mit $x_1 = 1$ den affinen Punkten entsprechen: Die Geraden, die parallel zur Ebene verlaufen, werden genau von solchen Vektoren repr\"asentiert, f\"ur die $x_1 = 0$ gilt. Die Wahl von $i=1$ ist hier willk\"urlich, ebenso kann jede beliebige Hyperebene des $\P^n$ als unendlich ferne Hyperebene und das Komplement als $\K^n$ aufgefasst werden. In der Kontruktion des $\P^2$ in Abbildung \ref{p1p2} entspricht dies einer ver\"anderten Wahl der Hyperebene, dessen Schnittpunkte mit den Geraden als affine Punkte aufgefasst werden. Im Fall $n \le 3$ kann man so verschiedene Karten aufzeichnen und auch Schnitte im unendlich Fernen gut visualisieren. Betrachtet man Nullstellenmengen von Polynomen im projektiven Raum, so st\"o\ss t man zun\"achst auf ein Problem der Wohldefiniertheit: F\"ur Polynome $f \in \K[x_0,...,x_n]$ mit einer Nullstelle $a=(a_0,...,a_n)$ gilt in der Regel nicht $f(\lambda \cdot a)=0$; aber es ist $a = \lambda \cdot a$, wenn $a$ ein Punkt im projektiven Raum ist. Dieses Problem kann man durch den \"Ubergang auf homogene Polynome umgehen, d.h. Polynome, die in jedem Monom denselben Grad haben. Davon erzeugte Ideale nennt man homogene Ideale und auf diese Weise kann man analog zum Affinen eine Theorie der projektiven Variet\"aten aufbauen. Mehr \"uber projektive Geometrie und der Theorie der affinen und projektiven Variet\"aten ist in [\ref{alggeo}] zu finden. Im Folgenden soll, falls nicht anders erw\"ahnt, $\C$ als Grundk\"orper vorrausgesetzt werden. \section{Bedingte Wahrscheinlichkeitsverteilungen} Sei $\Omega = [m]$ ein endlicher Ereignisraum, $\E \subset 2^\Omega$ wobei f\"ur alle $I \in \E$ gilt $|I| \ge 2$. $\C[\E]$ bezeichne die {\em Ereignisalgebra}, der Polynomring mit Unbestimmten $p_{i|I}$ f\"ur alle $I \in \E$ und $i \in I$, d.h. eine Unbekannte f\"ur jede elementare bedingte Wahrscheinlichkeit. Es bezeichne weiter $||\E|| = \sum_{I \in \E}|I|$ die Anzahl der Variablen in $\C[\E]$; $p_i$ f\"ur $p_{i|[m]}$, falls $[m] \in \E$. Ein Punkt $(p_1,...,p_m) \in \R_{\ge}^m$ mit $\sum_{i=1}^n p_i = 1$ repr\"asentiert eine Wahrscheinlichkeitsverteilung auf $\Omega$. Gilt $p_j > 0$ f\"ur alle $j$, so ist die bedingte Wahrscheinlichkeit von $i$ gegeben $I \ni i$: $$p_{i|I}= \frac{p_i}{\sum_{j \in I}p_j}.$$ Allgemeiner folgende \begin{definition} \label{bedWvert} Eine bedingte Wahrscheinlichkeitsverteilung f\"ur $\E$ ist ein Punkt $(p_{i|I} : i \in I \in \E) \in \R_{\ge 0}^{||\E ||}$, so dass f\"ur alle $J, K \in \E$ mit $J \subset K$ gilt \begin{enumerate}[(i)] \item $\sum_{i \in J}p_{i|J} = 1$, \item f\"ur alle $i \in J$ gilt $p_{i|K} = p_{i|J} \sum_{j \in J}p_{j|K}$. \end{enumerate} \end{definition} Dies ist die verallgemeinerte Version der obigen Formel, welche man aus der Definition \ref{bedWvert} erh\"alt, wenn man $K$ zu $[m]$ und $J$ zu $I$ spezialisiert und $\sum_{i \in I}p_i \neq 0$ vorraussetzt. Wenn allerdings $\sum_{i \in I}p_i = 0$ gilt, so erf\"ullt der gesamte Wahrscheinlicheitssimplex $\Delta_J := \{ (p_{j|J})_{j \in J} : p_{j|J} \ge 0, \sum_{j \in J}p_{j|J} = 1\}$ diese Definition. \subsection{Eine projektive Sicht von Wahrscheinlichkeit} Ausgehend von Definition \ref{bedWvert} erscheint es naheliegend, nicht einfache Punkte $(p_1,...,p_m) \in \R_{\ge}^m$ mit $\sum_{i=1}^n p_i = 1$ zu betrachten sondern diese Punkte stattdessen als Elemente des $\P^{m-1} = \P(\C^m)$ in homogenen Koordinaten zu verstehen. So eliminiert man die Bedingung $\sum_{i=1}^m p_i = 1$. Den Begriff des Wahrscheinlichkeitssimplexes kann man auf zwei Arten mit diesem komplex-projektiven Raum zusammenf\"uhren: Der offensichtlichste Weg ist die Restriktion, indem man den Wahrscheinlichkeitssimplex $\Delta_{m-1}$ mit dem reellen positiven Teil von $\{ y = (y_1:...:y_m) \in \P^{m-1} : \sum_{i=1}^n y_i \neq 0 \}$ identifiziert. In Abbildung \ref{projSimplex} ist dies f\"ur den Fall $m=3$ illustriert. Hier ist die Hyperebene $V(y_1 + y_2 + y_3)$ die unendlich ferne. \begin{figure}[htbp] \centering \includegraphics[height=2in]{projektiver-simplex.pdf} \caption{projektiver Simplex} \label{projSimplex} \end{figure} Aufgrund der fehlenden algebraischen Struktur erweist sich dies aber als weniger g\"unstig als der alternative Weg, $\P^{m-1}$ mittels der Abbildung \begin{align*} \mu: \quad \quad \P^{m-1} \quad &\longrightarrow \quad \Delta_{m-1} \\ (y_1:...:y_m) &\longmapsto \frac{1}{\sum_i |y_i|}|y_i|e_i \end{align*} surjektiv auf den Wahrscheinlichkeitssimplex $\Delta_{m-1}$ zu projezieren. Auf seinem Bild ist $\mu$ die Identit\"at, somit kann man nun beliebige Punkte des komplex projektiven Raums als Wahrscheinlichkeitsverteilungen interpretieren. So lassen sich nun die Relationen bedingter Wahrscheinlichkeiten mit der Struktur projektiver Variet\"aten beschreiben. \subsection{Homogene bedingte Wahrscheinlichkeit} Die Definition \ref{bedWvert} von bedingter Wahrscheinlichkeit soll im Folgenden so verallgemeinert werden, dass die Bedingung, eine bedingte Wahrscheinlichkeitsverteilung zu sein, mit homogenen Polynomen ausgedr\"uckt werden kann. Damit kann die Menge der bedingten Wahrscheinlichkeitsverteilungen als projektive Variet\"at verstanden werden. Eine bedingte Wahrscheinlichkeitsverteilung wird nun repr\"asentiert durch einen Punkt im kartesischen Produkt projektiver R\"aume. Dieses Produkt besteht aus Faktoren $\P^{|I|-1}$, mit jeweils einem Faktor f\"ur jedes $I \in \E$. Jeder dieser Faktoren $\P^{|I|-1}$ enth\"alt wiederum Punkte in homogenen Koordinaten $(p_{i_0|I}:...:p_{i_{|I|}|I})$. \begin{definition} \label{projbedWkeit} Eine projektive bedingte Wahrscheinlichkeitsverteilung auf $\E$ ist ein Punkt $p = ((p_{i_0|I}:...:p_{i_{|I|}|I}), I \in \E) \in \prod_{I\in\E}\P^{|I|-1}$ so dass f\"ur alle $J, K \in \E$ und $i \in J \subset K$ gilt $$(\sum_{j\in J}p_{j|J})p_{i|K} = p_{i|J}(\sum_{j\in J}p_{j|K})$$ \end{definition} F\"ur wirkliche bedingte Wahrscheinlichkeitsverteilungen ist $\sum_{j\in J}p_{j|J} = 1$ und dann steht im Wesentlichen die Definition \ref{bedWvert} da. \begin{bsp} \normalfont Sei $m = 4$, $\E = \{ 123, 234, 23\}$. W\"ahle $$p = ( (\frac{1}{6}:\frac{2}{6}:\frac{3}{6}), (\frac{2}{9}:\frac{3}{9}:\frac{4}{9}), (\frac{2}{5}:\frac{3}{5}) ) \in \P^2\times\P^2\times\P^1.$$ Nachrechnen zeigt, dass die Gleichungen aus der obigen Definition erf\"ullt sind, z.B. f\"ur $K = 123$, $J = 23$, $i = 2$: \begin{align*} (\sum_{j=2,3}p_{i|23}) \cdot p_{2|123} &= p_{2|23} \cdot (\sum_{j=2,3}p_{i|123})\\ \Leftrightarrow \qquad \qquad 1 \cdot \frac{2}{6} \qquad \quad &= \qquad \frac{2}{5}\cdot(\frac{2}{6} + \frac{3}{6}) \end{align*} Bei selbigem $\E$ kann man auch f\"ur $q = ( (\frac{1}{6}:\frac{2}{6}:\frac{3}{6}), (\frac{2}{9}i:\frac{3}{9}i:\frac{4}{9}i), (-\frac{2}{5}:-\frac{3}{5}) )$ die Korrektheit der obigen Gleichungen nachrechnen. Es gilt $\mu(q)=p$. \end{bsp} Aus der Definition \ref{projbedWkeit} leitet sich das folgende Ideal in der Ereignisalgebra $\C[\E]$ ab: $$J_\E = \langle (\sum_{j\in J}p_{j|J})p_{i|K}-p_{i|J}(\sum_{j\in J}p_{j|K}) : J, K \in \E, i \in J \subset K \rangle.$$ Dieses Ideal enth\"alt alle Polynombedingungen, die ein Punkt $p \in \prod_{I\in\E}\P^{|I|-1}$ erf\"ullen muss, damit er eine projektive bedingte Wahrscheinlichkeitsverteilung ist. Insbesondere erf\"ullt jede wirkliche bedingte Wahrscheinlichkeitsverteilung diese Bedingungen. Folgende Abk\"urzungen sollen noch vereinbart werden: es sei $p_{J|J} := \sum_{j \in J}p_{j|J}$. F\"ur wirkliche Wahrscheinlichkeitsverteilungen gilt nat\"urlich $p_{J|J} = 1$, doch $p_{J|J}$ soll hier als Linearform in $\C[\E]$ verstanden werden. Es sei weiter $\alpha_\E := \prod_{i \in I \in \E}p_{i|I}$, $\beta_\E := \prod_{I\in\E}p_{I|I}$. Die Saturierung eines Ideals $I$ bzgl. eines Polynoms $f$ ist \begin{align*} (I:f^\infty) :=& \langle g \in \C[\E] | \exists n \in \N : f^n g \in I \rangle \\ =& \{ g \in \C[\E] | \exists n \in \N : f^n g \in I \}. %\supsetneq& \{ g \in \C[\E] | g \cdot \langle f\rangle \subset I \} = I:\langle f\rangle \end{align*} F\"ur den Fall $[m] \in \E$ definiere $$I_\E := ( J_\E : (\alpha_\E\beta_\E)^\infty ).$$ Im Falle $[m] \notin \E$, setze $\E' := \E \cup [m]$ und $I_\E := I_{\E'} \cap \C[\E]$. Es gilt $I_\E \supseteq J_\E$. Die Erweiterung des Ideals $J_\E$ auf seine Saturierung verkleinert zun\"achst ggf. die Nullstellenmenge, d.h. es k\"onnten nun Punkte aus der Nullstellenmenge verschwinden, die aber eigentlich eine projektive bedingte Wahrscheinlichkeitsverteilung im Sinne der Definition \ref{projbedWkeit} sind. Doch die Definition von $\alpha_\E$ und $\beta_\E$ sorgt daf\"ur, dass eben nur solche Wahrscheinlichkeitsverteilungen verschwinden, wo Einzelereignise $i$ oder ganze Ereignisse $I$ unm\"oglich sind, und durch Reduzierung von $\E$ und $\Omega$ werden diese dann irrelevant. \section{Eine universelle Gr\"obnerbasis f\"ur bedingte Wahrscheinlichekteisverteilungen} Die universelle Gr\"obnerbasis von $I_\E$ wird aus den Zyklen eines benannten bipartiten Graphen $G(\E)$ hervor gehen. Dieser wird folgenderma\ss en definiert: \begin{description} \item[Ecken:] Eine Ecke $u_I$ f\"ur jedes $I \in \E$ sowie eine Ecke $v_i$ f\"ur jedes $i \in \cup_{I\in\E}I$. \item[Kanten:] Eine gerichtete Ecke $u_I \to v_i$ f\"ur jedes $I \in \E$ und $i \in I$. \item[Kantenbezeichnungen:] Die Ecke $u_I \to v_i$ wird mit der Unbekannten $p_{i|I}$ bezeichnet. \end{description} Dabei soll jeder gerichtete Zyklus $C$ in der ungerichteten Version von $G(\E)$ ein Binom repr\"asentieren: Jede Kantenbenennung erscheint als Faktor im positiven Teil des Binoms, falls seine Kante in Zyklusrichtung zeigt und im negativem Teil, falls entgegengesetzt. \begin{bsp} \normalfont \hfill \begin{enumerate}[(1)] \item Sei $n = 4$ und $\E = \{12, 123, 1234\}$. Der Graph $G(\E)$ ist in Abbildung \ref{graph1} gezeichnet. Betrachtet man den Zyklus $(1234, 3, 123, 1, 1234)$, so erh\"alt man das Binom $p_3p_{1|123}-p_{3|123}p_1$ (bzw. $p_{3|123}p_1-p_3p_{1|123}$). \item Sei $n = 3$ und $\E = \{12, 13, 23, 123\}$. Hier erh\"alt man aus dem \"au\ss eren Zyklus (siehe Abbildung \ref{graph2}) das Binom $p_{1|12}p_{3|13}p_{2|23}-p_{2|12}p_{3|23}p_{1|13}$. \end{enumerate} \end{bsp} \begin{figure}[ht] \centering \includegraphics{graph1.pdf} \caption{Bipariter Graph $G(\E)$ zu $\E = \{12, 123, 1234\}$} \label{graph1} \end{figure} \begin{figure}[ht] \centering \includegraphics{graph2.pdf} \caption{\"Au\ss erer Zyklus des Graphen $G(\E)$ zu $\E = \{12, 13, 23, 123\}$} \label{graph2} \end{figure} Ein Zyklus $C$ hei\ss t \textit{induziert}, falls kein Paar seiner Ecken im urspr\"unglichen Graphen durch eine Kante verbunden ist, die nicht zu $C$ geh\"ort. (``Man kann keine Abk\"urzung nehmen.'') \begin{theorem} \label{uniGB} Die durch den Graphen $G(\E)$ definierten Binome bilden eine universelle Gr\"obnerbasis von $I_\E$. Insbesondere wird $I_\E$ schon von den Binomen aus induzierten Zyklen erzeugt, wobei diese nicht notwendig eine Gr\"obnerbasis bilden. \end{theorem} Um diesen Satz zu zeigen, sind einige Aussagen \"uber torische unimodulare Ideale sowie unimodulare Matritzen n\"otig, die von Sturmfels in [\ref{sturm}] behandelt werden. Dazu: \begin{definition} Die Matrix $A \in \Z^{m\times d}$ definiert das (sogenannte) torische Ideal $$I_A := \langle x^{u^+}-x^{u^-} : u \in \Kern(A) \cap \Z^m \rangle,$$ wobei $u = x^{u^+} - x^{u^-}$ mit $x^{u^+}, x^{u^-} \in \N_0^m$. \end{definition} \begin{definition} Ein torisches Ideal $I_A$ hei\ss t unimodular, falls jede reduzierte Gr\"obnerbasis von $I_A$ ausschlie\ss lich aus quadradfreien Binomen besteht (d.h. es existieren keine Quadrate in den Leittermen jeder Gr\"obnerbasis). In diesem Fall hei\ss t auch die Matrix $A$ unimodular. \end{definition} Ist $G = (U,V,E)$ ein bipartiter Graph, so erh\"alt man ihre Ecken-Kanten-Inzidenzmatrix auf folgende Weise [\ref{unimodular2}]: die Zeilen werden mit den Ecken des Graphen, die Spalten mit den Kanten des Graphen bezeichnet. Ein Eintrag $a_{ij}$ der Matrix soll dann $1$ sein, wenn die Ecke $i$ in der Kante $j$ liegt und sonst $0$. \begin{bsp} \normalfont \label{graphbsp} Man betrachte den Graphen $G$ (siehe Abbildung \ref{eckenkanten}) mit $$V = \{1, 2, 3, 4\}, \quad U = \{ \{1,2\}, \{1,3\}, \{2,4\}, \{1,4\} \}.$$ Dann ist $$A = \begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 1 \end{pmatrix}$$ die Ecken-Kanten-Inzidenzmatrix. \end{bsp} \begin{figure}[hb] \centering \includegraphics{eckenkanten.pdf} \caption{Die Ecken-Kanten-Inzidenzmatrix des Graphen G aus Beispiel \ref{graphbsp}} \label{eckenkanten} \end{figure} In unserem Fall ist $G = G(\E)$ und es gilt: $$U = \{u_I : I \in \E \} \quad \mathrm{sowie} \quad V=\{v_i : i \in \cup_{I\in\E}I\}.$$ Die Zeilen der Ecken-Kanten-Inzidenzmatrix $A$ des Graphen $G(\E)$ werden dann mit den Ecken $u_1,...,u_{|U|},v_1,...,v_{|V|}$ bezeichnet, die Spalten wie gehabt. Die folgende Proposition besagt, dass so konstruierte Matritzen unimodular sind und erlaubt so den Beweis von Satz \ref{uniGB}. \begin{proposition} \label{propunimodular} Die Ecken-Kanten-Inzidenzmatrix $A$ eines bipartiten Graphen $G = (U,V,E)$ ist unimodular, d.h. insbesondere ist $I_A$ ein unimodulares torisches Ideal. Die Zyklus-Binomi des Graphen $G$ bilden eine universelle Gr\"obnerbasis von $I_A$. \end{proposition} Man zeigt nun, dass die dem Graphen $G(\E)$ assoziierten Binome eine Basis des torischen Ideals $I_A$ bilden, wobei $A$ die Ecken-Kanten-Inzidenzmatrix von $G(\E)$ ist. Au\ss erdem zeigt man, dass dieses Ideal mit $I_\E$ \"ubereinstimmt. Diesen Beweis und weitergehende Betrachtungen sind in [\ref{mainpaper}] ausgef\"uhrt, welches Vorlage f\"ur diese Ausarbeitung war. \section{Quellen} \begin{enumerate}[\lbrack 1\rbrack] \item\label{alggeo}\textsc{K. Hulek}: \textit{Elementare Algebraische Geometrie.} Vieweg, 2000. \item\label{mainpaper}\textsc{J. Morton}: \textit{Relations among conditional probabilities}. http://arxiv.org/abs/0808.1149, 8. August 2008. \item\label{unimodular2}\textsc{A. Slavkovic} und \textsc{S. Sullivant}: \textit{The space of compatible full conditionals is a unimodular toric variety.} Journal of Symbolic Computation, 41:196-209, 2006. \item\label{sturm}\textsc{B. Sturmfels}: \textit{Gr\"obner Bases and Convex Polytopes.} American Mathematical Society, Providence, 1996. \end{enumerate} \end{document}