Aufgabe 4

Die Einfahrt zu einem Parkhaus bietet vor der Schranke Platz für maximal drei wartende Autos. Sind diese drei Plätze besetzt, so kann ein ankommendes Auto nicht von der Straße in die Einfahrt zum Parkhaus einbiegen, sondern muss weiterfahren (siehe Abbildung).

Abbildung 1

Die Entwicklung der Wartschlange vor der Schranke kann durch einen stochastischen Prozess beschrieben werden. Dieser stochastische Prozess besitzt die vier Zustände:

$Z_0:$ kein Auto steht in der Einfahrt bis $Z_3:$ drei Autos stehen in der Einfahrt.

Es wird angenommen, dass maximal ein Auto pro Minute in die Einfahrt zum Parkhaus einbiegt und auch maximal ein Auto pro Minute die Schranke passieren und in das Parkhaus fahren kann ("Schranke öffnet").
Wenn in der Einfahrt mindestens ein Platz frei ist, beträgt die Wahrscheinlichkeit für das Einbiegen eines Autos in die Einfahrt in jeder Minute stets $p_1= 0,3.$ Vereinfachend wird angenommen, dass sich unabhängig von der bisherigen Wartezeit die Schranke in jeder Minute mit der Wahrscheinlichkeit $p_2=0,6$ öffnet, sodass ein Auto ins Parkhaus fahren kann. Ein Auto, das in die Einfahrt biegt, kann nicht in derselben Minute weiter ins Parkhaus fahren.

Angenommen der Prozess befindet sich im Zustand $Z_3.$ Der Prozess verbleibt in diesem Zustand,

... wenn ein Auto ins Parkhaus fährt ("Schranke öffnet") und gleichzeitig ein neues Auto ankommt,

... wenn kein Auto aus der Warteschlange ins Parkhaus fahren kann ("Schranke geschlossen").

Der Prozess befindet sich im Zustand $Z_3.$

$\,$

(1)

Gib die fehlenden Wahrscheinlichkeiten im Baumdiagramm an.

Abbildung 2

$A:$

ein Auto biegt in die Einfahrt ein

$\overline{A}:$

kein Auto biegt in die Einfahrt ein

(4 Punkte)

$\,$

(2)

Leite her:
Die Wahrscheinlichkeit, dass der Prozess in der nächsten Minute im Zustand $Z_3$ bleibt, beträgt $p=0,58.$

(3 Punkte)

$\,$

Die Wahrscheinlichkeit für die Veränderung des Prozesses von einer Minute zur nächsten wird vollständig beschrieben durch die Übergangsmatrix $U.$

$U= ...$

Matrix anzeigen

$\,$

(3)

Leite die in der zweiten Spalte der Matrix $U$ angegebenen Wahrscheinlichkeiten her.

(6 Punkte)

Zu einem bestimmten Zeitpunkt steht kein Auto in der Einfahrt.

$\,$

(1)

Bestimme die Wahrscheinlichkeit,

$\text{(i)}$

dass nach $10$ Minuten drei Autos in der Einfahrt stehen,

$\text{(ii)}$

dass nach fünf Minuten weniger als zwei Autos in der Einfahrt stehen,

$\text{(iii)}$

dass in den nächsten drei Minuten zu keinem Zeitpunkt ein Auto in der Einfahrt steht.

(11 Punkte)

$\,$

(2)

Untersuche, ausgehend von der Startverteilung $\overrightarrow{x_0} = \pmatrix{1\\0\\0\\0}$ die langfristige Entwicklung der Wahrscheinlichkeitsverteilung und entscheide begründet, ob der Bereich für wartende Autos vergrößert werden soll.

(5 Punkte)

Ein stochastischer Prozess mit den Zuständen $Z_0$ bis $Z_2$ und der Übergangswahrscheinlichkeit $k$ mit $0\leq k \leq 0,5$ in benachbarte Zustände wird durch folgende Übergangsmatrix $M_k$ dargestellt:

$M_k = \pmatrix{1-k & k &0 \\ k &1-2k & k \\ 0& k & 1-k}$

$\,$

(1)

Eine Matrix ist doppeltstochastisch genau dann, wenn Zeilen- und Spaltensummen jeweils $1$ betragen und alle Elemente der Matrix zwischen $0$ und $1$ liegen.
Damit handelt es sich bei $M_k$ um eine doppeltstochastische Matrix.
Prüfe für $k =0,4\,,$ ob $(M_{0,4})^2$ ebenfalls eine doppeltstochastische Matrix ist.

(5 Punkte)

$\,$

(2)

Zeige:
Es existiert eine Wahrscheinlichkeitsverteilung $\overrightarrow{x},$ so dass $M_k \cdot \overrightarrow{x} = \overrightarrow{x}$ gilt.
Gib diese Wahrscheinlichkeitsverteilung an.

(6 Punkte)

(1)

Abb. 1: Wahrscheinlichkeiten

$\,$

(2)

Wenn der Prozess im Zustand $Z_3$ ist, bleibt er in der nächsten Minute in diesem Zustand, wenn

... sich die Schranke öffnet, sodass ein Auto in das Parkhaus fahren kann und ein neues Auto in die Einfahrt einbiegt.
... sich die Schranke nicht öffnet, sodass kein Auto in das Parkhaus fahren und auch kein neues in die Einfahrt einbiegen kann.

Mit den beiden Pfadregeln ergibt sich mit Hilfe des Baumdiagramms:

$p = 0,58$

Vollständige Lösung anzeigen

$\,$

(3)

Die Einträge in der zweiten Spalte der Matrix beschreiben die Übergangswahrscheinlichkeiten des Prozesses, wenn sich der Prozess im Zustand $Z_1$ befindet. Im Sachzusammenhang bedeutet dies, dass sich zu diesem Zeitpunkt ein wartendes Auto in der Einfahrt befindet.

$\boldsymbol{u_{12} = 0,42}$

$u_{12}$ beschreibt die Übergangswahrscheinlichkeit des Prozesses von $Z_1$ nach $Z_0.$
Von $Z_1$ nach $Z_0$ kann der Prozess nur übergehen, wenn die Schranke sich öffnet, sodass das wartende Auto in das Parkhaus fahren kann $(p_2= 0,6)$ und gleichzeitig kein neues Auto in die Einfahrt einbiegt $(p_3= 1-p_1 = 0,7).$ Mit der Pfadmultiplikationsregel ergibt sich:
$u_{12} = 0,6\cdot 0,7 = 0,42$

$\boldsymbol{u_{22}=0,46}$

$u_{22}$ beschreibt die Wahrscheinlichkeit dafür, dass der Prozess im Zustand $Z_1$ verbleibt.
Dies kann in zwei Fällen eintreten:

Die Schranke öffnet sich, sodass das wartende Auto in das Parkhaus fahren kann $(p_2 = 0,6)$ und gleichzeitig fährt ein neues Auto in die Einfahrt $(p_1 = 0,3).$
Die Schranke bleibt geschlossen, sodass das wartende Auto in der Einfahrt verbleibt $(p_4 = 1-p_2 =0,4)$ und gleichzeitig biegt kein neues Auto in die Einfahrt ein $(p_3 = 0,7).$

Mit den Pfadregeln folgt also:

$u_{22} = ...$

Vollständige Lösung anzeigen

$\boldsymbol{u_{32}=0,12}$

$u_{32}$ beschreibt die Wahrscheinlichkeit dafür, dass der Prozess vom Zustand $Z_1$ in den Zustand $Z_2$ übergeht.
Dies kann nur dann passieren, wenn sich die Schranke nicht öffnet, sodass das wartende Auto in der Einfahrt verbleibt $(p_4 = 0,4)$ und in derselben Minute ein neues Auto in die Einfahrt einbiegt $(p_1 = 0,3).$ Mit der Pfadmultiplikationsregel folgt also:
$u_{32} = 0,4\cdot 0,3 = 0,12$

$\boldsymbol{u_{42}=0}$

$u_{42}$ beschreibt die Wahrscheinlichkeit dafür, dass der Prozess vom Zustand $Z_1$ in den Zustand $Z_3$ übergeht.
Damit sich nach einer Minute drei Autos in der Einfahrt befinden müssten mindestens zwei neue Autos gleichzeitig in die Einfahrt einbiegen. Dies ist laut Aufgabenstellung allerdings ausgeschlossen. Daher ist es nicht möglich, dass der Prozess von $Z_1$ innerhalb eines Zeitschrittes direkt in $Z_3$ übergeht. Die Wahrscheinlichkeit ist daher $u_{42} = 0.$

(1)

$\blacktriangleright$ Wahrscheinlichkeiten bestimmen

Der Prozess befindet sich im Zustand $Z_0.$ Die Startverteilung ist also durch den Vektor $\overrightarrow{x}_0 = \pmatrix{1\\0\\0\\0}$ gegeben.
Die Übergangswahrscheinlichkeiten nach $n$ Minuten werden durch $U^n$ beschrieben. Die Wahrscheinlichkeitsverteilung nach $n$ Minuten ergibt sich also durch $U^n \cdot \overrightarrow{x}_0.$ Mit deinem CAS ergibt sich jeweils:

$\text{i}$

$U^{10}\cdot \pmatrix{1\\0\\0\\0} \approx \pmatrix{0,5137\\0,3622\\0,0982\\0,0259}$

Vollständige Lösung anzeigen

Nach $10$ Minuten befinden sich mit einer Wahrscheinlichkeit von ca. $2,59\,\%$ drei Autos in der Einfahrt.

$\text{ii}$

$U^{10}\cdot \pmatrix{1\\0\\0\\0} \approx \pmatrix{0,5413\\0,3639\\0,0806\\0,0141}$

Vollständige Lösung anzeigen

Nach $5$ Minuten befinden sich mit einer Wahrscheinlichkeit von ca. $0,5413+0,3639 = 90,52\,\%$ weniger als zwei Autos in der Einfahrt.

$\text{iii}$

Laut Aufgabenstellung kann kein Auto in derselben Minute in die Einfahrt einbiegen und direkt weiter durch die Schranke in das Parkhaus fahren. Soll sich also zu keinem Zeitpunkt ein Auto in der Einfahrt befinden, darf drei Minuten lang kein Auto in die Einfahrt einbiegen. Mit der Pfadmultiplikationsregel folgt:

$0,7\cdot 0,7\cdot 0,7 = 0,343$

Mit einer Wahrscheinlichkeit von $34,3\,\%$ steht in den nächsten drei Minuten zu keinem Zeitpunkt ein Auto in der Einfahrt.

$\,$

(2)

Mit dem CAS ergibt sich:

$\begin{array}[t]{rll} U^{100}\cdot \pmatrix{1\\0\\0\\0}&\approx \pmatrix{0,5059\\0,3614\\0,1032\\0,0295} \\[10pt] U^{1.000}\cdot \pmatrix{1\\0\\0\\0}&\approx \pmatrix{0,5059\\0,3614\\0,1032\\0,0295} \\[10pt] \end{array}$

Vollständige Lösung anzeigen

Es gilt also:

$\lim\limits_{n\to\infty} U^n\cdot ...$

Vollständige Lösung anzeigen

Langfristig ist die Wahrscheinlichkeitsverteilung bei einer Startverteilung von $\pmatrix{1\\0\\0\\0}$ also durch den Vektor $\pmatrix{0,5059\\0,3614\\0,1032\\0,0295}$ gegeben.

Langfristig befinden sich nur mit einer Wahrscheinlichkeit von ca. $3\,\%$ drei Autos in der Einfahrt, sodass kein neues Auto mehr in die Einfahrt einbiegen kann.
Ich würde den Bereich für die wartenden Autos daher nicht vergrößern.

(1)

Für $k=0,4$ sieht die Matrix wie folgt aus:

$M_{0,4} = \pmatrix{0,6& 0,4 & 0 \\ 0,4 & 0,2 & 0,4 \\ 0 & 0,4 & 0,6}$

$...=\pmatrix{0,52 & 0,32 & 0,16 \\ 0,32 & 0,36 & 0,32 \\ 0,16 & 0,32 & 0,52}$

Vollständige Lösung anzeigen

Alle Einträge der Matrix liegen zwischen $0$ und $1.$ Alle Zeilensummen betragen $1,$ genauso wie alle Spaltensummen. Die Matrix $\left(M_{0,4}\right)^2$ ist also doppeltstochastisch.

$\,$

(2)

Mit $\overrightarrow{x} = \pmatrix{x_1\\x_2\\x_3}$ ergibt sich folgende Gleichung:

$\pmatrix{1-k&k&0 \\k&1-2k & k \\ 0&k &1-k} \cdot ...$

Vollständige Lösung anzeigen

Da $\overrightarrow{x}$ eine Wahrscheinlichkeitsverteilung ist, muss $x_1 +x_2 +x_3 = 1$ sein.

Für $k=0$ handelt es sich bei $M_{0}$ um die Einheitsmatrix $I_3$ , deren Bedonderheit gerade die Eingenschaft ist, dass für jeden beliebigen Vektor $\overrightarrow{u}$ der Dimension $3$ gilt:

$I\cdot \overrightarrow{u} = \overrightarrow{u}.$

Für $k=0$ existiert ein solcher Verteilungsvektor also. Es handelt sich dabei um jeden Vektor $\overrightarrow{x} = \pmatrix{x_1\\x_2\\x_3}$ mit $x_1+x_2+x_3 = 1.$

Für $0\lt k\leq 0,5$ ergibt sich folgendes Gleichungssystem:

Gleichungen anzeigen

Aus $\text{II}$ folgt:

$x_1 = x_2$

Vollständige Lösung anzeigen

Aus $\text{IIII}$ folgt:

$x_3 = x_2$

Vollständige Lösung anzeigen

Einsetzen der beiden Ergebnisse in $\text{I}$ ergibt:

$x_2 = \frac{1}{3}$

Vollständige Lösung anzeigen

Es ist also $x_1 =x_2 =x_3 = \frac{1}{3}.$ Probe:

$\frac{1}{3}= \frac{1}{3}$

Vollständige Lösung anzeigen

Diese Aussage ist wahr, also löst $x_1 =x_2 =x_3 = \frac{1}{3}$ das Gleichungssystem. Es existiert also ein Verteilungsvektor $\overrightarrow{x}$ mit $M_k\cdot \overrightarrow{x} = \overrightarrow{x}.$ Dieser lautet $\overrightarrow{x} = \pmatrix{\frac{1}{3} \\ \frac{1}{3} \\ \frac{1}{3}}.$

		von:	$Z_0$	$Z_1$	$Z_2$	$Z_3$
	$Z_0$		$\begin{pmatrix}0,7 & 0,42 & 0 & 0\\[2pt]0,3&0,46&0,42&0\\[2pt]0&0,12&0,46&0,42\\[2pt] 0 & 0 & 0,12 & 0,58\end{pmatrix}$
nach:	$Z_1$	$U=$
	$Z_2$
	$Z_3$