Czy w Oz będzie kiedyś nieszczęśliwy Tribble?

Oto zabawny problem przyniesiony mi przez studenta. Chociaż pierwotnie było sformułowane w kategoriach wzajemnie anihilujących pocisków wystrzeliwanych w regularnych odstępach przez broń, pomyślałem, że może ci się podobać bardziej spokojna prezentacja.

W nieskończonym płaskim świecie Oz Żółta Ceglana Droga zaczyna się w centrum Szmaragdowego Miasta, odpręża się na wsi i płynie w nieskończoność. Każdego dnia w południe jeden pełen pożądania młody hermafrodytyczny Tribble wyrusza wzdłuż tej drogi z równomiernie wybraną prędkością do jednego kilometra dziennie. Podczas swojej podróży będzie toczył się z tą samą prędkością, nigdy się nie zatrzymując. Ale jeśli kiedykolwiek jeden Tribble wyprzedzi drugiego na drodze, każdy natychmiast rozpozna bratnią duszę i obaj spadną na bok (prawdopodobnie w celu odtworzenia i ostatecznie dostarczenia większej liczby Tribbles z powrotem do domu).

Jak wiecie, takie skojarzenia występują często, ponieważ szansa, że ​​dowolne dwie Tribble przetoczą się z dokładnie taką samą prędkością, wynosi zero. Och, szczęśliwe Tribbles! Ale czy życie jest dla nich dobre?

Jaka jest szansa, że ​​co najmniej jeden Tribble będzie trwał wiecznie, nigdy nie wyprzedzając ani nie wyprzedzając?

Edycja: Wydaje mi się, że pomieszałem pojęcie pozytywnego prawdopodobieństwa i prawdopodobieństwa 1. Stwierdzone tutaj stwierdzenie jest znacznie słabsze, niż się spodziewałem.

Intuicyjnie odpowiedź brzmi 0. Nietrudno to udowodnić

Każdy dany Tribble, z dodatnim prawdopodobieństwem, ostatecznie otrzymuje partnera.

Myślę jednak, że to może nie wystarczyć, aby z pozytywnym prawdopodobieństwem przypuszczać, że każda trójka w końcu dostaje partnera, zgodnie z paradoksem Zenona.

Oto dowód cytowanego oświadczenia. Najpierw zastąpmy problem prostszym alternatywnym sformułowaniem w następujący sposób. Istnieje stos, który zaczyna się pusty. Komputer losuje zmienne losowe w sekwencji niezależnie i równomiernie od [0, 1]. Za każdym razem, gdy wartość jest rysowana, stos zmienia się.

• Jeśli stos jest pusty lub najwyższy element na stosie ma większą wartość, wówczas nowy element jest dodawany z nową wartością. (Utworzono pocisk wolniejszy niż ostatni pocisk lub Tribble wolniejszy niż ostatni Tribble.)
• W przeciwnym razie najwyższy element zostanie usunięty. (Kule lub Tribbles zderzają się.)

(To sformułowanie nie obejmuje zdarzenia pocisku lub Tribble szybciej niż poprzednie, ale jest niszczone, zanim trafi w poprzednie, ale takie zdarzenie pozostawia ten sam stos, więc nie ma to żadnego znaczenia).

Chcę udowodnić, że każdy przedmiot z dużym prawdopodobieństwem zostanie ostatecznie usunięty ze stosu. Możemy założyć bez utraty ogólności, że wartość nigdy nie jest rysowana, ponieważ prawdopodobieństwo, że tak się stanie, wynosi 0. Niech będzie istniejącym przedmiotem, a jego wartość. Niech będzie liczbą elementów powyżej i ich wartości w kolejności, przy czym jest wartością bieżącego najwyższego elementu. Jeśli kolejne wartości które mają zostać narysowane, odpowiednio w przedziale , przedziale i tak dalej do , to$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$ i wszystkie powyższe elementy zostaną usunięte. Prawdopodobieństwo tego zdarzenia to , który jest skończonym iloczynem liczb dodatnich, więc jest dodatni.$(1 - v_k)(1 - v_{k-1})\cdots(1 - v_0)$