Które algorytmy randomizowane mają wykładniczo małe prawdopodobieństwo błędu?

Załóżmy, że algorytm losowy używa $r$ losowych bitów. Najniższe prawdopodobieństwo błędu, jakiego można się spodziewać (nie spełniając deterministycznego algorytmu z błędem 0), wynosi $2^{-\Omega(r)}$ . Które algorytmy losowe osiągają tak minimalne prawdopodobieństwo błędu?

Oto kilka przykładów, które przychodzą na myśl:

Algorytmy próbkowania, np. Gdzie chcemy oszacować rozmiar zestawu, do którego można sprawdzić członkostwo. Jeśli ktoś pobierze losowo równomiernie próbki do sprawdzenia, granica Chernoffa gwarantuje wykładniczo małe prawdopodobieństwo błędu.
Algorytm Karger-Klein-Tarjan do obliczania minimalnego drzewa opinającego. Algorytm wybiera każdą krawędź z prawdopodobieństwem 1/2 i rekurencyjnie znajduje MST w próbce. Można użyć Chernoffa, aby argumentować, że jest wykładniczo nieprawdopodobne, że będzie 2n + 0,1m krawędzi, które są lepsze niż drzewo (tzn. Wolałby je przejąć nad jedną z krawędzi drzewa).

Czy możesz wymyślić inne przykłady?

Zgodnie z odpowiedzią Andrasa poniżej: Rzeczywiście, każdy algorytm wielomianu czasu można przekształcić w wolniejszy algorytm wielomianu z wykładniczo małym prawdopodobieństwem błędu. Skupiam się na algorytmach, które są tak wydajne, jak to możliwe. W szczególności dla dwóch przykładów, które podałem, istnieją deterministyczne algorytmy wielomianowe, które rozwiązują problemy. Zainteresowanie algorytmami losowymi wynika z ich wydajności.

randomized-algorithms Dana Moshkovitz
źródło

Nie jest to kompletna odpowiedź, ale w losowej algebrze liniowej było już trochę pracy. youtube.com/watch?v=VTroCeIqDVc

Baby Dragon

Być może nie można się tego spodziewać , ale z pewnością można mieć nadzieję (wciąż „nie spełniając deterministycznego algorytmu z błędem 0”), że dla wszystkich liczb rzeczywistych

c

$c\hspace{-0.02 in}$ , gdyby

c < 1

$\: c<1 \:$ to jest algorytm

$\hspace{.34 in}$ którego prawdopodobieństwo błędu wynosi

2^{- c \cdot r}

$2^{-\hspace{.01 in}c\cdot r}\hspace{-0.03 in}$ .

$\:$ Uważam, że testowanie tożsamości wielomianowej jest takim problemem.

$\hspace{.49 in}$

@RickyDemer Nie rozumiem twojego komentarza. Zwykły algorytm randomizowany dla PIT zawiera błąd, który nie jest wykładniczy w losowości. Więc co ty mówisz? Mówisz, że może istnieć taki algorytm dla dowolnego problemu z BPP?

Sasho Nikolov,

Teraz zdaję sobie sprawę, że tak naprawdę nie widzę żadnego sposobu pokazania, że PIT jest w klasie, którą opisałem.

$\:$ Z drugiej strony, pozostawienie

wielomianu w

(tj. Pozwolenie, by długość (S) była superliniowa w długości (d)) wystarczyłoby dla lematu Schwartza-Zippela

S

$S$

d

$d$

$\:$ (nieprzerwany ...)

$\;\;\;\;$

Wiele konstrukcji metod probabilitycznych ma takie zachowanie, prawda? Na przykład wybranie losowego zestawu ciągów binarnych i przyjrzenie się ich najbliższej parze - prawdopodobieństwo, że będą dwa ciągi w odległości mniejszej niż

jest bardzo małe. -------------------------------------------------- ----------------------- W duchu odpowiedzi BPP poniżej: Biorąc pod uwagę ekspander o stałym stopniu, z n wierzchołkami i

zaznaczonymi wierzchołkami, prawdopodobieństwo losowego przejścia o długości

do pominięcia zaznaczonego wierzchołka wynosi

n / 4

$n/4$

n / 2

$n/2$

O (t)

$O( t )$

, jeżeli

2^{- Ω (t)}

$2^{-\Omega(t)}$

t = Ω (\log n)

$t = \Omega( \log n)$

Sariel Har-Peled,

Które algorytmy randomizowane mają wykładniczo małe prawdopodobieństwo błędu?

Odpowiedzi: