Oglądałem wykład MIT na temat Skip List. Ogólnie rozumiem materiał, ale jedno. Co to jest „z dużym prawdopodobieństwem”? Naprawdę nie rozumiem. Widziałem notatki z wykładów , ale nadal ich nie rozumiem.
Po prostu powiedział: „Zdarzenie $ E $ występuje z dużym prawdopodobieństwem (whp), jeśli dla dowolnego $ \ alpha \ geq1 $ istnieje odpowiedni dobór stałych, dla których $ E $ występuje z prawdopodobieństwem co najmniej 1 $ – O (1 / n ^ \ alpha) $ „.
Coś z Algorytmist.com też nie pomogło.
Co to jest $ \ alpha $ i ile wynosi $ 1 – O (1 / n ^ \ alpha) $? Niezrozumienie tej rzeczy sprawia, że jestem zdezorientowany analizą, dlaczego „Z dużym prawdopodobieństwem każde wyszukiwanie na liście pominiętych elementów $ n $ kosztuje $ O (\ lg n) $”.
Komentarze
- Zwróć uwagę, że algorytmy losowe i probabilistyczne to nie to samo .
Odpowiedź
Zdarzenie ma miejsce z dużym prawdopodobieństwem w odniesieniu do parametru $ n $, jeśli zachodzi z prawdopodobieństwem $ p_n $ i $ \ lim_ {n \ to \ infty} p_n = 1 $. Zwykle parametr $ n $ jest jasny z kontekstu. W tym przypadku, na przykład, jest to prawdopodobnie liczba elementów na liście.
Definicja „z dużym prawdopodobieństwem” w notatkach do wykładu jest jeszcze bardziej szczegółowa, określając, jak szybko $ p_n $ powinno się zbierać do $ 1 $: zdarzenie ma miejsce z dużym prawdopodobieństwem, jeśli zachodzi z prawdopodobieństwem $ p_n \ geq C / n ^ \ alpha $ dla jakiegoś $ C, \ alpha > 0 $. Na przykład, jeśli wybierzesz liczbę losową z $ \ {0, \ ldots, n \} $, to jest ona niezerowa z dużym prawdopodobieństwem, ponieważ prawdopodobieństwo, że jest różna od zera, wynosi 1-1 / (n + 1) \ geq 1-1 / n $ (czyli w tym przypadku $ C = \ alpha = 1 $).
Komentarze
- Kryterium limitu to zwany także " prawie na pewno ". Widziałem " wysokie prawdopodobieństwo " używane głównie w odniesieniu do prawdopodobieństw zbliżających się do prawdopodobieństwa o wartości wykładniczej.
- Kiedy ja patrz " whp " jest to zwykle synonimem " prawie na pewno ", a kiedy go używam (bez definiowania go), zawsze mam na myśli znaczenie. Ale ogólnie " whp " może oznaczać albo zbliżanie się do 1, zbliżanie się do 1 wielomianowo szybko lub zbliżanie się do 1 wykładniczo szybko. Jeśli używasz go w którymkolwiek z tych drugich, pamiętaj, aby zdefiniować go wyraźnie.
- Naprawdę ' d dzwonisz do $ p_n = 1 – \ frac { 1} {\ log ^ * n} $ " z dużym prawdopodobieństwem "? 😉 Ale tak: aby być bezpiecznym, w każdym przypadku określ, co masz na myśli w swoim kontekście.
- Co to jest standardowe odniesienie (np. Podręczniki), które formalnie definiują WHP? Próbowałem napisać artykuł o WHP w Wikipedii en.wikipedia.org/wiki/With_high_probability , ale zasugerowano usunięcie go, ponieważ nie ma źródeł, więc jestem szukanie źródeł ..
- Możesz sprawdzić standardowe podręczniki złożoności i algorytmów. Ale nawet jeśli znajdziesz odniesienie, ' jest tylko tym konkretnym podręcznikiem ' używanym terminem. ' prawdopodobnie najlepiej jest po prostu jednoznacznie zdefiniować ją jako powszechną definicję bez żadnego konkretnego " dowodu ".