Quels algorithmes randomisés ont une probabilité d'erreur exponentiellement faible?

Supposons qu'un algorithme randomisé utilise $r$ bits aléatoires. La plus faible probabilité d'erreur à laquelle on puisse s'attendre (en deçà d'un algorithme déterministe avec 0 erreur) est de $2^{-\Omega(r)}$ . Quels algorithmes randomisés atteignent une telle probabilité d'erreur minimale?

Voici quelques exemples qui me viennent à l'esprit:

Algorithmes d'échantillonnage, par exemple, où l'on veut estimer la taille d'un ensemble pour lequel on peut vérifier l'appartenance. Si l'on échantillonne uniformément au hasard les éléments à vérifier, la borne de Chernoff garantit une probabilité d'erreur exponentiellement petite.
L'algorithme de Karger-Klein-Tarjan pour calculer l'arbre couvrant minimum. L'algorithme sélectionne chaque front avec une probabilité 1/2 et trouve récursivement le MST dans l'échantillon. On peut utiliser Chernoff pour affirmer qu'il est exponentiellement improbable qu'il y ait 2n + 0,1 m de bords meilleurs que l'arbre (c'est-à-dire que l'on préfère les prendre sur l'un des bords de l'arbre).

Pouvez-vous penser à d'autres exemples?

Suivant la réponse d'Andras ci-dessous: En effet, chaque algorithme de temps polynomial peut être converti en un algorithme de temps polynomial plus lent avec une probabilité d'erreur exponentiellement petite. Je me concentre sur des algorithmes aussi efficaces que possible. En particulier, pour les deux exemples que j'ai donnés, il existe des algorithmes de temps polynomiaux déterministes qui résolvent les problèmes. L'intérêt pour les algorithmes randomisés est dû à leur efficacité.

randomized-algorithms Dana Moshkovitz
la source

Pas une réponse complète, mais il y a eu quelques travaux en algèbre linéaire aléatoire. youtube.com/watch?v=VTroCeIqDVc

Baby Dragon

On ne peut peut-être pas s'y attendre , mais on peut certainement espérer (toujours "en deçà d'un algorithme déterministe avec 0 erreur") que pour tous les nombres réels

c

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

c < 1

$\: c<1 \:$ alors il y a un algorithme

$\hspace{.34 in}$ dont la probabilité d'erreur est de

2^{- c \cdot r}

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

$\:$ Je crois que le test d'identité polynomiale est un tel problème.

$\hspace{.49 in}$

@RickyDemer Je ne comprends pas votre commentaire. L'algorithme randomisé habituel pour PIT a une erreur qui n'est pas exponentielle dans le caractère aléatoire. Alors, que dites-vous? Êtes-vous en train de dire qu'il peut exister un tel algorithme pour tout problème de BPP?

Sasho Nikolov

Je me rends compte maintenant que je ne vois vraiment aucun moyen de montrer que PIT est dans la classe que j'ai décrite.

$\:$ D'un autre côté, laisser

être super-polynomial en

(c'est-à-dire laisser la longueur (S) être super- linéaire en longueur (d)) suffirait pour le lemme de Schwartz-Zippel

S

$S$

d

$d$

$\:$ (a continué ...)

$\;\;\;\;$

De nombreuses constructions de méthodes probabilsitiques ont un tel comportement, non? Par exemple, choisir un ensemble aléatoire de chaînes binaires et regarder leur paire la plus proche - la probabilité qu'il y ait deux chaînes à une distance inférieure à

est très faible. -------------------------------------------------- ----------------------- Dans l'esprit de la réponse BPP ci-dessous: Étant donné un expanseur à degré constant, avec n sommets et

sommets marqués, le la probabilité qu'une marche aléatoire de longueur

manque un sommet marqué est de

, si

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

Réponses:

Impagliazzo et Zuckerman ont prouvé (FOCS'89, voir ici ) que si un algorithme BPP utilise bits aléatoires pour atteindre une probabilité d'exactitude d'au moins 2/3, puis, en appliquant des marches aléatoires sur des graphiques d'expansion, cela peut être amélioré en une probabilité d'exactitude de , en utilisant bits aléatoires. ( Remarque: bien que les auteurs utilisent la constante spécifique 2/3 dans l'abstrait, elle peut être remplacée par toute autre constante supérieure à 1/2.) $r$ $1-2^{-k}$ $O(r+k)$

Si l' on prend , cela signifie que tout algorithme BPP qui permet d' obtenir une probabilité d'erreur constante , en utilisant des bits aléatoires, peut être (non triviale) améliorée pour avoir la probabilité d'erreur . Ainsi, (sauf si j'ai mal compris quelque chose), la probabilité d'erreur est réalisable pour chaque problème dans BPP. $k=r$ $< 1/2$ $r$ $2^{-\Omega(r)}$ $\leq 2^{-\Omega(r)}$

Andras Farago
la source

Le problème avec de telles techniques d'amplification est qu'elles ralentissent l'algorithme. Le nouvel algorithme ne peut utiliser que O (r) bits aléatoires, mais son temps d'exécution est r fois (temps d'exécution d'origine). Si r est, par exemple, au moins linéaire dans la taille d'entrée n (ce qui est généralement le cas), vous venez de ralentir l'algorithme d'un facteur n. Ce n'est pas quelque chose dont la plupart des algorithmistes se réjouiraient ...

Dana Moshkovitz

Je ne suis pas sûr que ce soit ce que vous recherchez, mais c'est lié:

Supposons que je veuille trouver un nombre premier aléatoire à bits. L'algorithme habituel consiste à choisir un entier aléatoire (impair) bits et à exécuter le test de primalité de Miller-Rabin pour tours dessus et à répéter jusqu'à ce qu'un nombre probable probable soit trouvé. Quelle est la probabilité que cette procédure renvoie un nombre composite? Appelons cette probabilité . $k$ $k$ $t$ $p_{k,t}$

L'analyse standard du test de primalité de Miller-Rabin montre que les rounds donnent une probabilité d'échec d'au plus . Ceci, avec le théorème des nombres premiers, implique $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)}.$

Voir Erdös et Pomerance (1986) , Kim et Pomerance (1989) et Dåmgard, Landrock et Pomerance (1993) pour plus de détails.

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

Thomas soutient Monica
la source