\documentclass[unbewertet]{agisuebung} \date{18.~November 2024} %\newcommand{\deadlineDate}{Mittwoch, 06.~November 2024, 12:15~Uhr} \newcommand{\exerciseNum}{1} \usepackage{multicol} \DeclareMathOperator{\preorder}{preorder} \DeclareMathOperator{\inorder}{inorder} \DeclareMathOperator{\postorder}{postorder} \DeclareMathOperator{\CH}{CH} % # # # # # # # # # # # # # # # # # # # # # # # # # # \begin{document} % # # # # # # # # # # # # # # # # # % # # # # # # # # # # # # # # # # # # # # # # # # # # % ### aufgabe \begin{aufgabe}[Hausdorff und Fréchet] % ------------------------------------------------ Gegeben sind drei Polygonzüge $P=(p_1,\ldots, p_n)$ und $Q=(q_1,\ldots, q_m)$ und $Q'=(q_m,\ldots,q_1)$. Beweisen oder widerlegen Sie die folgenden Aussagen. \begin{teilaufgabe} \item $d_\text{fr\'echet}(P,Q)\ge d_\text{hdorff}(P,Q)$ \item $d_\text{hdorff}(P,Q)=d_\text{hdorff}(P,Q')$ \item $d_\text{hdorff}(Q,Q')=0$ \item $d_\text{fr\'echet}(P,Q)=d_\text{fr\'echet}(P,Q')$ \item $d_\text{fr\'echet}(Q,Q')=0$ \end{teilaufgabe} \begin{loesung} \begin{teilaufgabe} \item Das Punktepaar, welches $d_\text{fr\'echet}$ minimiert, ist auch für $d_\text{hdorff}$ valide. \item $d_\text{hdorff}(P,Q)=d_\text{hdorff}(P,Q')$: \textbf{richtig}, da Reihenfolge egal ist \item $d_\text{hdorff}(Q,Q')=0$: \textbf{richtig}, da Polygonzügen direkt übereinander liegen \item $d_\text{fr\'echet}(P,Q)=d_\text{fr\'echet}(P,Q')$: \textbf{falsch}, betrachte die Anfangs- und Endpunkte \item $d_\text{fr\'echet}(Q,Q')=0$: \textbf{falsch}, da Startknoten nicht Distanz $0$ haben \end{teilaufgabe} \end{loesung} \end{aufgabe} \begin{aufgabe}[Markow Studenten] \newcommand{\study}{\ensuremath{\mathtt{Study}}} \newcommand{\party}{\ensuremath{\mathtt{Party}}} \newcommand{\sleep}{\ensuremath{\mathtt{Sleep}}} \newcommand{\st}{\ensuremath{\mathtt{St}}} \renewcommand{\sl}{\ensuremath{\mathtt{Sl}}} \newcommand{\pa}{\ensuremath{\mathtt{Pa}}} %Recall that a Markov chain is a sequence of random variables that has the \emph{Markov property}. %\begin{equation*} %\Pr[X_{n+1}\ |\ X_n=x_n,X_{n-1}=x_{n-1},\ldots,X_1=x_1]\ =\ \Pr[X_{n+1}\ |\ X_n=x_n\ ] %\end{equation*} Betrachten wir einen Studenten, der sich zu jedem Zeitpunkt in einem der Zustände aus \( Z = \{\study, \party, \sleep\} \) befindet. Die Übergangswahrscheinlichkeiten sind wie folgt. \begin{multicols}{2} \[P[X_{n+1}=\study\ |\ X_n=\study] = 0,\!3\] \[P[X_{n+1}=\party\ |\ X_n=\study] = 0,\!5\] \[P[X_{n+1}=\sleep\ |\ X_n=\study] = 0,\!2\] \[P[X_{n+1}=\study\ |\ X_n=\party] = 0,\!0\] \[P[X_{n+1}=\party\ |\ X_n=\party] = 0,\!5\] \[P[X_{n+1}=\sleep\ |\ X_n=\party] = 0,\!5\] \[P[X_{n+1}=\study\ |\ X_n=\sleep] = 0,\!3\] \[P[X_{n+1}=\party\ |\ X_n=\sleep] = 0,\!3\] \[P[X_{n+1}=\sleep\ |\ X_n=\sleep] = 0,\!4\] \end{multicols} %a probability distribution for $X_1$, and a single probability distribution $P[X_{n+1}|X_n]$ that holds for all $n\geq 1$. \begin{teilaufgabe} \item Zeichnen Sie das Zustandsübergangsdiagramm mit einem Knoten für jeden Zustand und Pfeilen, die die Übergangswahrscheinlichkeiten anzeigen. \item Ihnen wird vielleicht auffallen, dass unabhängig von der Anfangsverteilung ($P[X_1]$) die Wahrscheinlichkeitsverteilung für spätere Zeitschritte immer zur gleichen Verteilung konvergiert, wenn genügend Zeit vergeht. Dies gilt nicht für alle möglichen Markow-Ketten, aber für diese spezielle Kette ist es tatsächlich wahr: Unabhängig von $P[X_1]$ konvergiert die Wahrscheinlichkeitsverteilung $P[X_n]$ für $n\rightarrow \infty$. Diese Grenzverteilung wird als \emph{stationäre Verteilung} bezeichnet, definiert als eine Wahrscheinlichkeitsverteilung, bei der gilt: $P[X_{n+1}] = P[X_n]$ für eine bestimmte Markow-Kette. Berechnen Sie die stationäre Verteilung für die gegebene Markow-Kette und geben exakte Werte an. \end{teilaufgabe} \begin{loesung} \begin{teilaufgabe} \item~\\ \begin{center} \begin{tikzpicture} \draw (0,0)node[rectangle,draw](study){\study{}} (4,0)node[rectangle,draw](sleep){\sleep{}} (2,3)node[rectangle,draw](party){\party{}}; \draw [->, bend left=15] (study) to node[lab]{$0.5$} (party);\draw [->, bend left=15] (study) to node[lab]{$0.2$} (sleep);\draw [->, loop below] (study) to node[lab,anchor=north]{$0.3$} (study); \draw [->, loop above] (party) to node[lab]{$0.5$} (party);\draw [->, bend left=15] (party) to node[lab]{$0.5$} (sleep);\draw [->, bend left=15] (party) to node[lab]{$0.0$} (study); \draw [->, bend left=15] (sleep) to node[lab]{$0.3$} (party);\draw [->, loop below] (sleep) to node[lab,anchor=north]{$0.4$} (sleep);\draw [->, bend left=15] (sleep) to node[lab]{$0.3$} (study); \end{tikzpicture} \end{center} \item Damit eine Verteilung \emph{stationär} ist, muss $Pr[X_i=x] = Pr[X_{i-1}=x]$ gelten -- eine einfache Grenzwertbetrachtung für $n \to \infty$ reicht nicht. Wir erhalten also ein lineares Gleichungssystem in den drei Variablen $Pr[X=\textrm{Study}]$, $Pr[X=\textrm{Sleep}]$ und $Pr[X=\textrm{Party}]$ -- oder kürzer \st{}-udy, \sl{}-eep und \pa{}-rty. ``Die Wahrscheinlichkeit für \pa{} entspricht der Wahrscheinlichkeit, dass vorher \pa{} galt multipliziert mit der Übergangswahrscheinlichkeit von \pa{} nach \pa{} plus...'' \begin{align} \pa{} &= \pa{} \cdot Pr[\pa\mid\pa] + \sl\cdot Pr[\pa\mid\sl] + \st\cdot PR[\pa\mid\st]\\ \sl{} &= \pa{} \cdot Pr[\sl\mid\pa] + \sl\cdot Pr[\sl\mid\sl] + \st\cdot PR[\sl\mid\st]\\ \st{} &= \pa{} \cdot Pr[\st\mid\pa] + \sl\cdot Pr[\st\mid\sl] + \st\cdot PR[\st\mid\st]\\ 1 &= \pa+\sl+\st \end{align} Oder mit Werten: \begin{align} \pa{} &= 0.5 ~\pa + 0.3 ~\sl + 0.5 ~\st\\ \sl{} &= 0.5 ~\pa + 0.4 ~\sl + 0.2 ~\st\\ \st{} &= 0.0 ~\pa + 0.3 ~\sl + 0.3 ~\st\\ 1 &= \pa+\sl+\st \end{align} Auflösen, Umformen und Einsetzen ergibt: \begin{tabular}{l|p{.2\textwidth}|p{.7\textwidth}} (a) & aus (7) & $0.7 \st = 0.3\sl \Rightarrow \st = \frac{3}{7} \sl$\\ \hline (b) & (a) in (8) einsetzen & { \vspace{-1cm} \begin{align*} 1 &=\pa + \st + \sl\\ \Rightarrow \pa &= 1 - \st - \sl = 1 - \frac{3}{7}\sl - \sl = 1 - \frac{10}{7}\sl \end{align*}\vspace{-0.5cm}}\\ \hline (c) & (a) und (b) in (5) einsetzen & { \vspace{-1cm} \begin{align*} \pa &= 0.5\pa + 0.3\sl + 0.5 \st\\ \Rightarrow 1 - \frac{10}{7}\sl &= \frac{1}{2} (1 - \frac{10}{7}\sl) + \frac{3}{10}\sl + \frac{1}{2}\cdot \frac{3}{7}\sl\\ \frac{1}{2} &= (\frac{100}{70} - \frac{50}{70} + \frac{21}{70} + \frac{15}{70})\sl = \frac{86}{70}\sl\\ &\Rightarrow \sl = \frac{1}{2}\cdot\frac{70}{86}=\frac{35}{86} \end{align*}\vspace{-0.5cm}}\\ \hline & (c) in (a) & {\[ \st = \frac{3}{7}\sl = \frac{3}{7} \cdot\frac{35}{86} = \frac{15}{86}\]}\\ \hline & (c) in (b) & {\[ \pa = 1 - \frac{10}{7}\sl = 1 - \frac{10}{7}\cdot\frac{35}{86} = 1 - \frac{50}{86} = \frac{36}{86}\]} \end{tabular} \end{teilaufgabe} \end{loesung} \end{aufgabe} \begin{aufgabe}[Im Gefängnis (nur zu Besuch)] Wir betrachten nun das bekannte Brettspiel Monopoly, bei dem die Spieler auf einem Kreis von 40 Spielfeldern reisen (oder sich möglicherweise "`im Gefängnis"' befinden); siehe Abbildung~\ref{fig:monopoly}(a) für eine Version des Spielbretts. Im Verlauf des Spiels können die Spieler Felder kaufen und tauschen, um später durch "`Miete"', die von anderen Spielern gezahlt wird, die auf diesen Feldern landen, Geld zu verdienen. Das bedeutet, dass Felder, auf denen die Spieler mit höherer Wahrscheinlichkeit landen, wertvoller sind. Wir möchten die Bewegung eines Spielers auf dem Brett als Markow-Kette modellieren, um die stationäre Verteilung einfach berechnen zu können: Wenn das Spiel unendlich lange dauert, wie hoch ist die Wahrscheinlichkeit, dass ein Spieler auf jedem Feld landet? Diese Information ist nützlich, um Kaufentscheidungen im Spiel zu treffen. In Abbildung~\ref{fig:monopoly}(b) ist die stationäre Verteilung einer Version von Monopoly dargestellt, die auf diese Weise berechnet wurde. Modellieren Sie eine einfache Version davon, wie ein Spieler während des Spiels das Brett umrundet, als Markow-Kette (eine Beschreibung in Worten genügt). Was sind die Zustände und Übergangswahrscheinlichkeiten? Erforschen Sie anschließend erweiterte Regeln und integrieren Sie einige davon in Ihr Modell, z.B.: ins Gefängnis kommen, aus dem Gefängnis herauskommen und Ereigniskarten. \begin{figure}[h!] \centering \begin{tabular}{p{.45\textwidth}p{.45\textwidth}} \begin{center}\includegraphics[width=.32\textwidth]{figures/monopoly} \end{center}& \begin{center}\includegraphics[width=.32\textwidth]{figures/distribution} \end{center}\\ \end{tabular} \caption{(a) Eine Spielbrett von Monopoly. (b) Die stationäre Verteilung unter Berücksichtigung der Ereigniskarten ist farbcodiert, wobei rot eine niedrige Wahrscheinlichkeit und grün eine hohe Wahrscheinlichkeit darstellt. Zusätzlich gibt es eine Wahrscheinlichkeit von 5,5\%, im Gefängnis zu sein.} \label{fig:monopoly} \end{figure} \begin{loesung} \paragraph{Ein-Wurf-Teilmodell} Es gibt einen Zustand je Feld und von jedem Feld zu dessen Nachfolgern Kanten entsprechend der möglichen Würfelergebnisse ($2,\dots,12$). Die Übergangswahrscheinlichkeit für jede Kante entsprecht der Wahrscheinlichkeit, die Augenzahl die der entsprechenden Distanz entspricht auch zu würfeln. Damit lässt sich ein einfaches Wandern um das Board modellieren, noch ohne Gefängnis und Chance-Karten. \paragraph{Go-To-Jail} Eines der Felder (Nr. $30$, wenn Start $0$ ist) verzichtet auf die oben beschriebenen Kanten und führt mit Wahrscheinlichkeit $1$ direkt ins Gefängnis. \paragraph{Rauswürfeln} Das Gefängniss (analog Feld $10$) bekommt vier Zustände: ``Besuch'', ``Null Züge drin'', ``Ein Zug drin'' und ``Zwei Züge drin''. Alle Ereignisse (Karten, Felder, Päsche, etc.) die den Spieler ins Gefängnis schicken führen entsprechend zu ``Null Züge drin''. Von jedem der ``X Züge drin'' Felder gibt es eine Kante zum entsprechend nächsten Feld für jeden Pasch und eine Kante die alle Nicht-Pasch Ergebnisse zusammenfast und zum Feld ``X+1 Züge drin'' führt. Nach ``Zwei Züge drin'' kommt man sicher frei, kann also mit Wahrscheinlichkeit $1$ zu ``Besuch'' wechseln. \paragraph{3x Pasch-Regel} Kopiere dazu das oben beschriebene Modell (bis auf die Gefängniszustände) zwei mal. Entferne in den Kopien die Pasch-Kanten und füge stattdessen die Kanten zwischen den Kopien wieder ein. Es gibt dann eine ``Kein Pasch''- Kopie, eine ``Zwei Pasch''-Kopie und eine ``Drei Pasch''-Kopie. In der ``Drei Pasch''-Kopie führt jeder weitere Pasch mit Wahrscheinlichkeit $1$ ins Gefängnis. \paragraph{Chance Karten} für die Ereignis- und Gemeinschaftsfelder gibt es nun zusätzliche Übergänge für ``Gehe direkt zu Straße X''-Karten. Die Übergangswahrscheinlichkeit entspricht der Wahrscheinlichkeit, diese Karte auch zu ziehen. Entsprechend gibt es dann auch Kanten direkt ins Gefängnis. \paragraph{Get-out-of-Jail Karten} Um das Inventar des Spielers darzustellen nehmen wir erneut drei Kopien des kompletten oben beschriebenen Modells, um die drei Möglichkeiten darzustellen: nämlich ob der Spieler $0,1$ oder $2$ Freikarten hat. Entsprechend gibt es dann Kanten mit Wahrscheinlichkeit $1$, die aus den ``Drin''-Feldern der Kopie $X$ in die ``Besuch''-Felder der Kopie $X-1$ führen. \end{loesung} \end{aufgabe} % # # # # # # # # # # # # # # # # # # # # # # # # # # \end{document} % # # # # # # # # # # # # # # # # # # % # # # # # # # # # # # # # # # # # # # # # # # # # #