In der Theorie der Warteschlangen kann man ein ziemlich cooles und allgemein weniger bekanntes Paradoxon finden, dass auf den ersten Blick im harten Konflikt zur intuitiven Erwartung steht, sich aber mit einem kleinem Zusatz glücklicherweise schnell auflöst. Im Englischen wird das Paradoxon auch gerne als Hitchhiker’s Paradox (Anhalter-Paradoxon) bezeichnet, im Buch “Queueing Systems” von Kleinrock, wo ich es zum ersten Mal gesehen habe, läuft es unter dem Namen Hippie Paradoxon. Persönlich bevorzuge ich den Namen Zustandsparadoxon, weil das Paradoxon, obwohl durch Wartezeiten gut verdeutlicht, viel grundlegender als das ist. Es tritt bei jedem System auf, welches in verschiedene Zustände wechselt.
Angenommen man installiert eine Lichtschranke an einer Straße und misst kontinuierlich den zeitlichen Abstand zwischen den vorbeifahrenden Autos. Nach einer Phase der Beobachtung kennt man den mittleren zeitlichen Abstand zwischen zwei Autos recht genau, sagen wir 60 Sekunden. So lange dauert es, bis nach dem Vorbeifahren eines Autos das nächste Auto durchfährt. Es ist natürlich nur ein Mittelwert – manchmal ist der Abstand länger, manchmal kürzer. Aber im Mittel beträgt diese Zeit 60 Sekunden.
Angenommen man geht zu einem zufälligen Zeitpunkt an diese Straße. Wie lange muss man im Mittel warten, bis ein Auto vorbeifährt? Bei echter Zufälligkeit scheint die Antwort 30 Sekunden unvermeidbar. Um im Mittel weniger als 30 Sekunden zu warten, müsste man sich schon in irgendeiner Weise mit dem Verkehr abstimmen. Man könnte etwa, sobald man gehört hat, wie ein Auto vorbeifährt, eine gewisse Zeit warten und erst dann an die Straße gehen. So könnte man die mittlere Wartezeit drücken.
Umgekehrt könnte man sich natürlich mit dem Verkehr auch so abstimmen, dass die Wartezeit im Mittel mehr als 30 Sekunden beträgt. Wieso man das wollte sei dahingestellt, aber es wäre machbar. Ganz ohne Abstimmung jedoch, also bei echter Zufälligkeit, wird man im Mittel wohl 30 Sekunden warten müssen bis das nächste Auto kommt. Alles andere wäre ohne eine Form der Abstimmung mit dem Verkehr ein ziemlich seltsames Resultat.
Zum Glück muss man nicht raten. Ein Experiment bringt Klarheit. Man geht zufällig an die Straße und hält die Zeit bis zum nächsten Auto fest. Das wiederholt man zehntausend Mal und berechnet dann den Mittelwert. Die mittlere Wartezeit wäre … Trommelwirbel … 40 Sekunden. Nicht 30 Sekunden, sondern länger. Das gilt ganz allgemein. Geschehen zwei Ereignisse im Mittel mit den Zeitabständen T, dann wäre bei zufälliger Ankunft die Wartezeit bis zum nächsten Ereignis immer größer als T/2.
Das steht auf den ersten Blick auf sehr deutlichem Kriegsfuß mit der Intuition. Beispiel Verkehrslücken. Das Paradoxon sichert zu, dass die Verkehrslücke, die man bei Anfahren an eine Kreuzung bekommt, im Mittel größer ist die mittlere Verkehrslücke zwischen den Autos (etwa gemessen vom Helikopter aus). Und der verbliebene, zum Einfahren nutzbare Teil der Verkehrslücke, die man bei Anfahren vorfindet, wird im Mittel größer sein als die Hälfte der mittleren Verkehrslücke im System. Klingt ein bisschen wie Magie.
Die Erklärung ist sehr einfach: Die Stichprobe ist nicht so fair, wie sie erst scheint. Größere Lücken nehmen einen größeren Anteil der Straße ein. Und somit trifft man auch eher auf solche, wenn man zufällig an die Straße anfährt. Vom Helikopter aus lassen sich die Lücken kontinuierlich messen und man kann so den wahren Mittelwert der Lückengröße ermitteln. Beim zufälligen Anfahren werden jedoch große Lücke bevorzugt selektiert. Das ist der zentrale Punkt. Man kommt bei Messung mittels Anfahren also zu einem anderen, größeren Mittelwert. Entsprechend bleibt zum Einfahren auch mehr als die Hälfte der wahren mittleren Lücke im System, da man die Hälfte einer größeren Lücke zur Verfügung hat.
Ähnlich ist es mit dem zeitlichen Abstand der Autos. Wenn man zufällig an die oben beschriebene Straße tritt, wird man im Mittel dann ankommen, wenn die Lücke zwischen den Autos größer als 60 Sekunden ist. Solche Lücken nehmen anteilig schlicht mehr Raum. Entsprechend wird die mittlere Wartezeit bis zum nächsten Auto größer als 30 Sekunden sein. Die mittlere Wartezeit von 40 Sekunden war also kein Widerspruch zur Zufälligkeit, sondern ein sehr logisches Resultat.
Die Mathematik dahinter ist “relativ schmerzfrei”. Gegeben ein System mit den Zuständen 1, 2, 3 … Die Wahrscheinlichkeit, dass das System nach Beendigung eines Zustands auf Zustand k wechselt, sei pk. Die Dauer von Zustand k sei tk. Die mittlere Dauer T eines Zustands ist E(T) = [Summe über k] pk*tk. Es werden N Zustände beobachtet. Die gesamte vergangene Zeit ist N*E(T). Die Zeit in Zustand k ist N*pk*tk. Der Anteil der Zeit, den das System in Zustand k verbringt, ist also qk = pk*tk/E(T). Das entspricht auch der Wahrscheinlichkeit, das System bei zufälliger Messung in Zustand k vorzufinden. Die mittlere Dauer eines zufällig vorgefundenen Zustands ist E(T’) = [Summe über k] qk. Eingesetzt erhält man:
E(T’) = [Summe über k] pk*tk² / [Summe über k] pk*tk
E(T’) = E(T²) / E(T)
Wobei E(T²) der Erwartungswerts der quadratischen Dauer* eines Zustands ist. Mit der Varianz s² (Standardabweichung s) lässt sich das noch sehr deutlich vereinfachen. Eine zentrale Gleichung der Mathematik von Wahrscheinlichkeiten ist s² = E(T²) – E(T)². Es ist somit E(T’) = E(T)+s²/E(T). Die mittlere verbliebene Zeit im vorgefundenen Zustand E(V), das entspricht der mittleren Wartezeit bis zum nächsten Zustandswechsel, ist die Hälfte der Dauer des vorgefundenen Zustands, also E(V) = (1/2)*E(T’). Somit:
E(V) = (1/2)*(E(T) + s²/E(T)) > (1/2)*E(T)
Damit ist gezeigt: In jedem System mit von null verschiedener Varianz ist die verbliebene Zeit im angetroffenen Zustand im Mittel größer als die Hälfte der mittleren Dauer der Zustände. Mal zwei gerechnet kann man es auch einfacher formulieren, wobei aber der Bezug zur Wartezeit verloren geht: Der vorgefundene Zustand ist im Mittel länger als die mittlere Dauer eines Zustands im System. Das ist eine sehr grundlegende Feststellung. Es gilt für jedes System mit einem Mittelwert E(T) kleiner als unendlich und einer Varianz ungleich Null (also eigentlich alle realen Systeme).
Das Paradoxon ist nicht nur intellektuell spannend, sondern auch für praktische Zwecke ziemlich nützlich. In der Theorie der Warteschlangen wird das Ergebnis verwendet, um M/M/1 Warteschlangen (Ankunftszeiten und Servicezeiten exponentialverteilt) auf M/G/1 (Ankunftszeiten exponentialverteilt, Servicezeiten beliebig verteilt) zu verallgemeinern. Das Paradoxon erlaubt also, die strikte Annahme exponentialverteilter Servicezeiten fallen zu lassen und stattdessen mit einer beliebigen Verteilung mit Mittelwert m und Standardabweichung s zu arbeiten. Das wiederum führt zu sehr nützlichen Ergebnissen, mit denen man relativ leicht die mittlere Wartezeit, die mittlere Länge einer Schlange, etc … in Abhängigkeit von der Ankunftsrate von Kunden berechnen kann.
* Noch eine Anmerkung zu E(T²). E(T) ist der Erwartungswert der Dauer. Man misst n-Mal die Dauer und berechnet dann über E(T) = (1/n)*(T1+T2+T3+…+Tn) den gewöhnlichen Mittelwert / Erwartungswert. E(T²) ist der Erwartungswert der quadratischen Dauer. Man misst n-Mal die Dauer, quadriert diese jeweils und berechnet den Mittelwert dieser Quadrate E(T²) = (1/n)*(T1²+T2²+T3²+…+Tn²). Wieso sollte das sinnvoll sein? Beispiel Gasmechanik. Jedes Teilchen in einem Gas fliegt mit einer gewissen Geschwindigkeit v umher. Die kinetische Energie des Teilchens ist K = (1/2)*m*v². Was ist die mittlere kinetische Energie eines Teilchens? Naheliegend ist der folgende Ansatz: Man misst alle Geschwindigkeiten, berechnet die mittlere Geschwindigkeit E(V) und sagt E(K) = (1/2)*m*E(V)². Das Ergebnis wäre aber falsch. Für die mittlere kinetische Energie kann man nicht einfach die mittlere Geschwindigkeit quadrieren. Man müsste die Geschwindigkeiten messen, das Ergebnis jeder Einzelmessung quadrieren und den Mittelwert dieser Quadrate berechnen, also E(V²). Die korrekte mittlere kinetische Energie ist E(K) = (1/2)*m*E(V²). Es gilt in jedem System mit Varianz ungleich Null: E(V²) > E(V)². Mit dem ersten Ansatz hätte man die mittlere kinetische Energie, und somit etwa die Temperatur des Gases, unterschätzt.

