Amplification pour les algorithmes randomisés

Question

J'essaie de montrer que l'amplification fonctionne pour des algorithmes randomisés et pour des algorithmes d'approximation randomisés.

---

Amplification pour les algorithmes randomisés:
Étant donné un algorithme randomisé avec la complexité du temps $ f (n) $ et probabilité d'erreur $ frac {1} {4} $, Montrez qu'il existe un algorithme qui résout le même problème, mais avec $ O Left (f Left (n droite) log Left ( frac {1} { varepsilon} droite) droite) $ temps d'exécution et probabilité d'erreur de $ varepsilon $, pour une donnée $ varepsilon> 0 $.

J'ai réussi à montrer cette exécution de l'algorithme original $ k $ fois, et en choisissant par majorité votent la réponse. Utilisant Chernoff multiplicatif lié (Ce que j'ai aussi prouvé), j'ai montré $ k geq o Left (ln Left ( frac {1} { varepsilon} droite) droite) $ nous donne les résultats requis.

---

Maintenant, j'essaie de faire de même pour les algorithmes d'approximation.

Amplification pour les algorithmes d'approximation randomisés:
Étant donné un algorithme d'approximation randomisé qui renvoie un $ varepsilon $-Additive-Approximation avec une probabilité de $ frac {3} {4} $, avec complexité du temps d'exécution de $ f gauche (n droite) $, montre qu'il existe un algorithme qui renvoie un $ varepsilon $-Additive-Approximation avec une probabilité de $ $ Delta $, pour le même problème, mais avec $ O Left (f Left (n droite) log Left ( frac {1} { delta} droite) droite) $ le temps d'exécution, pour une donnée $ delta> 0 $.

La première chose qui me vient à l'esprit est d'utiliser une approche similaire à celle précédente - exécutez l'algorithme d'origine $ k $ fois, mais cette fois au lieu d'utiliser le vote majoritaire, renvoyez la moyenne.

Je dois trouver un peu $ k geq o Left (ln Left ( frac {1} { delta} droite) droite) $ tel que dollars droite] < delta $.

J'ai essayé d'utiliser l'inégalité du triangle, puis d'utiliser Union Bound, mais cela ne me conduit pas à pouvoir utiliser Cheroff. Afin d'utiliser Cheroff, j'ai pensé à définir une variable aléatoire d'indicateur pour chaque exécution de l'algorithme d'origine, indiquant si le résultat - $ X_ {i} $ est mauvais (c'est-à-dire si $ gauche | x_ {i} -opt droite |> varepsilon $), mais c'est là que je suis coincé.

Apprécierait toute aide. Merci!