Quais algoritmos aleatórios têm probabilidade de erro exponencialmente pequena?

Suponha que um algoritmo aleatório use bits aleatórios. A menor probabilidade de erro que se pode esperar (ficando aquém de um algoritmo determinístico com erro 0) é . Quais algoritmos aleatórios atingem uma probabilidade mínima de erro? $r$ $2^{-\Omega(r)}$

Alguns exemplos que vêm à mente são:

Algoritmos de amostragem, por exemplo, onde se deseja estimar o tamanho de um conjunto para o qual se pode verificar a associação. Se uma amostra uniformemente aleatória dos elementos a serem verificados, o limite de Chernoff garante uma probabilidade de erro exponencialmente pequena.
O algoritmo de Karger-Klein-Tarjan para calcular a árvore de abrangência mínima. O algoritmo escolhe cada extremidade com probabilidade 1/2 e encontra recursivamente o MST na amostra. Pode-se usar Chernoff para argumentar que é exponencialmente improvável que existam 2n + 0,1m de arestas melhores do que a árvore (ou seja, preferimos levá-las sobre uma das arestas).

Você pode pensar em outros exemplos?

Seguindo a resposta de Andras abaixo: De fato, todo algoritmo de tempo polinomial pode ser convertido em um algoritmo de tempo polinomial mais lento , com probabilidade de erro exponencialmente pequena. Meu foco é em algoritmos que sejam tão eficientes quanto possível. Em particular, para os dois exemplos que dei, há algoritmos determinísticos de tempo polinomial que resolvem os problemas. O interesse nos algoritmos randomizados é devido à sua eficiência.

randomized-algorithms Dana Moshkovitz
fonte

Não é uma resposta completa, mas houve algum trabalho em álgebra linear numérica aleatória. youtube.com/watch?v=VTroCeIqDVc

Baby Dragon

Talvez não se possa esperar , mas certamente pode esperar (ainda "aquém de um algoritmo determinístico com erro 0") que, para todos os números reais,

c

$c\hspace{-0.02 in}$ , E se

c < 1

$\: c<1 \:$ então existe um algoritmo

$\hspace{.34 in}$ cuja probabilidade de erro é

2^{- c \cdot r}

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

$\:$ Acredito que o teste de identidade polinomial é um problema.

$\hspace{.49 in}$

@RickyDemer Não entendo o seu comentário. O algoritmo aleatório usual para PIT tem erro que não é exponencial na aleatoriedade. Então o que você está dizendo? Você está dizendo que pode existir esse algoritmo para qualquer problema de BPP?

Sasho Nikolov

Agora percebo que não vejo realmente nenhuma maneira de mostrar que o PIT está na classe que descrevi.

$\:$ Por outro lado, deixar

ser super polinomial em

(ou seja, deixar comprimento (S) ser superlinear em comprimento (d)) seria suficiente para o lema de Schwartz-Zippel

S

$S$

d

$d$

$\:$ (contínuo ...)

$\;\;\;\;$

Muitas construções de métodos probabilsíticos têm esse comportamento, não? Por exemplo, escolhendo um conjunto aleatório de cadeias binárias e olhando para o par mais próximo - a probabilidade de haver duas cadeias de distância menor que

é muito pequena. -------------------------------------------------- ----------------------- No espírito da resposta BPP abaixo: Dado um expansor de grau constante, com n vértices e

vértices marcados, o A probabilidade de uma caminhada aleatória de comprimento

perder um vértice marcado é

, se

n / 4

$n/4$

n / 2

$n/2$

O (t)

$O( t )$

2^{- Ω (t)}

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

t = Ω (\log n)

$t = \Omega( \log n)$

Sariel Har-Peled,

Respostas:

Impagliazzo e Zuckerman provaram (FOCS'89, veja aqui ) que, se um algoritmo BPP usar bits aleatórios para atingir uma probabilidade de correção de pelo menos 2/3, aplicando percursos aleatórios em gráficos de expansão, isso poderá ser aprimorado para uma probabilidade de correção de , usando bits aleatórios. ( Nota: embora os autores usem a constante específica 2/3 no resumo, ela pode ser substituída por qualquer outra constante maior que 1/2.) $r$ $1-2^{-k}$ $O(r+k)$

Se tomarmos , isto significa que qualquer algoritmo BPP que alcança uma probabilidade de erro constante , usando bits aleatórios, pode ser (não-trivialmente) melhorou a ter probabilidade de erro . Assim, (a menos que eu tenha entendido mal alguma coisa), a probabilidade de erro de é alcançável para todos os problemas no BPP. $k=r$ $< 1/2$ $r$ $2^{-\Omega(r)}$ $\leq 2^{-\Omega(r)}$

Andras Farago
fonte

O problema com essas técnicas de amplificação é que elas diminuem a velocidade do algoritmo. O novo algoritmo pode usar apenas O (r) bits aleatórios, mas seu tempo de execução é r vezes (tempo de execução original). Se r é, digamos, pelo menos linear no tamanho de entrada n (o que geralmente é), você apenas diminuiu a velocidade do algoritmo por um fator n. Isso não é algo que a maioria algorithmists seria de cerca de feliz ...

Dana Moshkovitz

Não sei se é isso que você está procurando, mas está relacionado:

Suponha que eu queira encontrar um aleatório $k$ número primo de 4 bits. O algoritmo usual é escolher um aleatório (ímpar) $k$ de bits inteiros e execute o teste de primalidade de Miller-Rabin para $t$ rondas nele e repita até que um provável primo seja encontrado. Qual é a probabilidade de esse procedimento retornar um número composto? Chame essa probabilidade $p_{k,t}$ .

A análise padrão do teste de primalidade de Miller-Rabin mostra que $t$ rodadas fornece uma probabilidade de falha de no máximo $4^{-t}$ . Isso, junto com o teorema do número primo, implica

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

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

No entanto, estamos executando o teste de Miller-Rabin em entradas aleatórias, para que possamos usar uma garantia de erro de caso médio. Temos uma ligação muito melhor. Em particular, para $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)}.$ That is to say, we get an exponentially-small failure probability with only one repetition of the test!

See Erdös and Pomerance (1986), Kim and Pomerance (1989), and Dåmgard, Landrock, and Pomerance (1993) for more details.

This is not a decision problem and the amount of randomness used is $O(k^2)$ bits (although I suspect this can be easily reduced to $O(k)$ ). However, it's an interesting example where we get exponentially-small failure probability naturally.

Thomas supports Monica
fonte