Aufgabe:
Die Deutsche Post unterhält eine Filiale mit einem Service-Schalter, vor dem sich täglich lange
Schlangen bilden. Ein einziger Mitarbeiter ist dort für die Kundenabfertigung zuständig. Aus baulich
bedingten Gründen können maximal n Kunden in der Schlange stehen. In jedem Zeitschritt fertigt der Mitarbeiter den vordersten Kunden der Schlange mit „Abfertigungswahrscheinlichkeit“ a ab, der Kunde geht dann nach Hause. Mit Wahrscheinlichkeit 1 −a hingegen bleibt der Kunde in der Schlange und der Mitarbeiter beschäftigt sich weiterhin mit ihm. Außerdem trifft unabhängig davon in jedem Zeitschritt mit „Kundenwahrscheinlichkeit“ k ein neuer Kunde ein.
Dieser stellt sich ans Ende der Schlange. Allerdings ist Folgendes zu beachten:
Ein frisch eingetroffener Kunde verlässt die Filiale direkt wieder, wenn in der Schlange bereits n Kunden stehen und der vorderste Kunde nicht abgefertigt wird. Der Übergang von n nach n hat also die Wahrscheinlichkeit ka+ (1− a).
Bei leerer Schlange kommt ein neuer Kunde direkt dran: Wird abgefertigt, dann verlässt er
sofort wieder die Filiale. Ist die Schlange leer und kommt kein neuer Kunde, wird trivialerweise
nicht abgefertigt. Der Übergang von 0 nach 0 hat also die Wahrscheinlichkeit ka+ (1−k)
Wir modellieren die Warteschlange als Markov-Kette mit den Zuständen 0,1,...,n, wobei Zustand
i ausdrückt, dass genau i Kunden in der Schlange stehen. Wir nehmen im Folgenden an, dass
0< a <1 und 0< k <1 gilt.
a) Skizziere den Graphen der Markov-Kette für n= 4 und beschrifte die Kanten mit den Übergangswahrscheinlichkeiten.
Hinweis:Benutze die Abkürzungen L:=a(1−k) sowie R:= (1−a)k.
b) Wir wollen wissen, wie viele Kunden im Erwartungswert (d.h. „durchschnittlich“) in der Schlange
stehen. Dazu benötigen wir zunächst die Grenzverteilung.
i) Begründe, warum die Markov-Kette (für jedes n∈N) ergodisch ist.
Fazit:Grenzverteilung und stationäre Verteilung stimmen überein!
ii) Berechne (näherungsweise) die stationäre Verteilung für n=4, a=1/3 und k=1/4 mithilfe eines Matrixrechners.
iii) Sei μ= (μ0,μ1,...,μn) die stationäre Verteilung der Kette für allgemeine n,a,k. Zeige durch Induktion
Für alle i∈{0,1,...,n} gilt μi = \( (\frac{R}{L})^{i} \) ·μ0.
Hinweis: Sei 0< i < n.
Stelle zunächst eine Gleichung für μi in Abhängigkeit von μi−1,μi und μi+1auf.
iv) Bestimme μ0. Benutze, dass μ eine Verteilung ist, d. h. dass \( \sum\limits_{i=0}^{n}{μi = 1 } \) gilt.
v) Berechne die erwartete Anzahl \( \sum\limits_{i=0}^{n}{i * μi } \) der Kunden in der Warteschlange für
die stationäre Verteilung μ.
Hinweis: Du darfst ohne Beweis verwenden: Für α ungleich 1 und m∈N gilt: \( \sum\limits_{j=0}^{m}{j * α ^{j}} \) = \( \frac{mα^{m+2} - (m +1) α^{m+1} + α}{(α-1)²} \)
c) Diskutiere das Ergebnis aus b) v) für den Fall n→ ∞. Unterscheide dabei die Fälle a > k, a=k und a < k
Hinweis: Ohne ernsthaften Ansatz einer Begründung werden auch für korrekte Lösungen stets 0 Punkte vergeben
Problem/Ansatz:
Also wir wissen, dass der Pfeil von n zu sich selbst mit ka + (1-a) beschriftet werden soll und der von 0 zu 0 mit ka + (1-k). Wie sieht es mit den anderen aus? Sind die dann alle mit jeweils mit
1-a, a, 0
k (1-k), 1-k(1-a)-a(1-k), a (1-k)
0, k, 1-k
zu beschriften?
