Wird es jemals einen unglücklichen Tribble in Oz geben?

Hier ist ein amüsantes Problem, das mir ein Student gebracht hat. Obwohl es ursprünglich so formuliert war, dass Kugeln, die von einer Waffe in regelmäßigen Abständen abgefeuert wurden, sich gegenseitig vernichtet haben, dachte ich, Sie könnten eine friedlichere Präsentation genießen.

In der unendlichen flachen Welt von Oz beginnt die Yellow Brick Road im Zentrum der Smaragdstadt, windet sich über die Landschaft und verläuft für immer, ohne sich selbst zu überqueren. Jeden Mittag rollt ein lustvoller junger zwittriger Tribble mit einer gleichmäßig zufällig gewählten Geschwindigkeit von bis zu einem Kilometer pro Tag von seinem Ursprung auf dieser Straße. Während der gesamten Fahrt rollt es mit der gleichen Geschwindigkeit und hört nie auf. Aber wenn jemals ein Tribble einen anderen auf der Straße überholt, erkennt jeder sofort seinen Seelenverwandten und die beiden fallen zur Seite (vermutlich, um sich zu reproduzieren und schließlich mehr Tribbles nach Hause zu bringen).

Wie Sie wissen, treten solche Paarungen häufig auf, da die Wahrscheinlichkeit, dass zwei Tribbles mit genau derselben Geschwindigkeit rollen, null ist. Oh, glückliche Tribbles! Aber ist das Leben für sie alle garantiert gut?

Wie groß ist die Chance, dass mindestens ein Tribble für immer anhält, niemals überholt oder überholt wird?

probability stochastic-processes puzzle whuber
quelle

Geht das davon aus, dass Tribbles zu einem bestimmten Zeitpunkt zu reisen begannen (so dass es Tribble Nr. 1 gab) und seitdem für immer weitermachen und die Wahrscheinlichkeit über diese unendliche Zeitspanne berechnet werden sollte?

Amöbe sagt Reinstate Monica

@amoeba Wenn Sie feststellen, dass es einen Unterschied macht anzunehmen, dass es einen bestimmten Startzeitpunkt gibt, wäre es sehr interessant, diesen Unterschied zu analysieren.

whuber

math.stackexchange.com/questions/1526292/colliding-bullets

Alex R.

Tribbles in Oz? Deine fiktiven Universen scheinen ein bisschen durcheinander zu sein.

Kodiologist

@Kodio Beide Universen sind dafür bekannt, dass sie sich mit anderen Universen überschneiden :-).

whuber

Antworten:

Edit: Ich habe anscheinend die Vorstellung von positiver Wahrscheinlichkeit und Wahrscheinlichkeit 1 vertauscht. Die Aussage, die hier bewiesen wurde, ist viel schwächer als ich gehofft hatte.

Intuitiv lautet die Antwort 0. Es ist nicht schwer, das zu beweisen

Jeder gegebene Tribble bekommt mit positiver Wahrscheinlichkeit irgendwann einen Partner.

Aber ich denke, dies könnte nicht ausreichen, um dies mit positiver Wahrscheinlichkeit zu implizieren, jedes Tribble nach Zenos Paradoxon irgendwann einen Partner bekommt.

Hier ist ein Beweis für die zitierte Aussage. Ersetzen wir zunächst das Problem durch eine einfachere alternative Formulierung wie folgt. Es gibt einen Stapel, der leer beginnt. Ein Computer zeichnet Zufallsvariablen nacheinander unabhängig und gleichmäßig aus [0, 1]. Jedes Mal, wenn ein Wert gezogen wird, ändert sich der Stapel.

Wenn der Stapel leer ist oder das oberste Element auf dem Stapel einen höheren Wert hat, wird ein neues Element mit dem neuen Wert hinzugefügt. (Eine Kugel, die langsamer als die letzte Kugel ist, oder ein Tribble, der langsamer als die letzte Tribble ist, wurde erstellt.)
Andernfalls wird das oberste Element entfernt. (Die Kugeln oder Tribbles kollidieren.)

(Diese Formulierung enthält nicht das Ereignis, dass eine Kugel oder ein Tribble schneller als die vorherige erstellt wird, aber dann zerstört wird, bevor es die vorherige trifft, aber ein solches Ereignis lässt den Stapel gleich, so dass es keine Konsequenzen hat.)

$1$ $I_0$ $v_0$ $k$ $I_0$ $v_1,\; v_2,\; …,\; v_k$ $v_k$ $k + 1$ $(v_k, 1)$ $(v_{k-1}, 1)$ $(v_0, 1)$ $I_0$ $(1 - v_k)(1 - v_{k-1})\cdots(1 - v_0)$

Kodiologist
quelle