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,

Impagliazzo i Zuckerman udowodnili (FOCS'89, patrz tutaj ), że jeśli algorytm BPP używa $r$ $1-2^{-k}$ $O(r+k)$

$k=r$ $< 1/2$ $r$ $2^{-\Omega(r)}$ $\leq 2^{-\Omega(r)}$

— Andras Farago
źródło

Problem z takimi technikami wzmocnienia polega na tym, że spowalniają algorytm. Nowy algorytm może wykorzystywać tylko losowe bity O (r), ale jego czas działania to r razy (pierwotny czas działania). Jeśli r ma, powiedzmy, co najmniej liniowy rozmiar wejściowy n (którym zwykle jest), po prostu spowolniłeś algorytm o współczynnik n. To nie jest coś, z czego większość algorytmów byłaby zadowolona ...

— Dana Moshkovitz

Nie jestem pewien, czy tego właśnie szukasz, ale jest to powiązane:

$k$ $k$ $t$ $p_{k,t}$

$t$ $4^{-t}$

p_{k, t} \leq O (k \cdot 4^{- t}) .

$p_{k,t} \leq O(k\cdot 4^{-t}).$

$t=1$

p_{k, 1} \leq {2)}^{- (1 - o (1)) \frac{k \ln \ln k}{\ln k}} \leq {2)}^{- \tilde{Ω} (k)} .

$p_{k,1} \leq 2^{-(1-o(1))\frac{k \ln\ln k}{\ln k}} \leq 2^{-\tilde\Omega(k)}.$ Innymi słowy, otrzymujemy wykładniczo małe prawdopodobieństwo awarii przy tylko jednym powtórzeniu testu!

Zobacz Erdös and Pomerance (1986) , Kim and Pomerance (1989) oraz Dåmgard, Landrock i Pomerance (1993), aby uzyskać więcej informacji.

$O(k^2)$ $O(k)$

— Thomas wspiera Monikę
źródło