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

12

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?

Whuber
źródło
1
Czy to zakłada, że ​​Tribbles zaczął podróżować w określonym punkcie czasowym (tak, że był Tribble # 1) i kontynuował odtąd wieczność, a prawdopodobieństwo powinno być obliczane w tym nieskończonym przedziale czasu?
ameba mówi Przywróć Monikę
1
@amoeba Jeśli okaże się, że jest różnica w założeniu, że był określony czas rozpoczęcia, bardzo interesująca byłaby analiza tej różnicy.
whuber
1
Tribbles w Oz? Twoje fikcyjne wszechświaty wydają się trochę pomieszane.
Kodiolog,
3
@Kodio Oba wszechświaty są dobrze znane z przecinania się innych wszechświatów :-).
whuber

Odpowiedzi:

2

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 , to1I0v0kI0v1,v2,,vkvkk+1(vk,1)(vk1,1)(v0,1)I0 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.(1vk)(1vk1)(1v0)

Kodiolog
źródło