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?
Odpowiedzi:
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ć
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ę.
(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 , to1 I0 v0 k I0 v1,v2,…,vk vk k+1 (vk,1) (vk−1,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.(1−vk)(1−vk−1)⋯(1−v0)
źródło