Amplificazione per algoritmi randomizzati

Question

Sto cercando di mostrare opere di amplificazione per algoritmi randomizzati e per algoritmi di approssimazione randomizzati.

---

Amplificazione per algoritmi randomizzati:
Dato un algoritmo randomizzato con complessità del tempo $ f (n) $ e probabilità di errore $ frac {1} {4} $, mostra che c'è un algoritmo che risolve lo stesso problema, ma con $ O left (f left (n a destra) log left ( frac {1} { Varepsilon} a destra) a destra) $ tempo di esecuzione e probabilità di errore di $ Varepsilon $, per una data $ Varepsilon> 0 $.

Sono riuscito a mostrare questo funzionamento dell'algoritmo originale $ k $ i tempi e la scelta per maggioranza votano la risposta. Usando Canno di Chernoff moltiplicativo (Che ho anche dimostrato), ho mostrato $ k geq o left (ln left ( frac {1} { Varepsilon} a destra) a destra) $ ci dà i risultati richiesti.

---

Ora sto cercando di fare lo stesso per gli algoritmi di approssimazione.

Amplificazione per algoritmi di approssimazione randomizzati:
Dato un algoritmo di approssimazione randomizzato che restituisce un $ Varepsilon $-approssimazione additiva con una probabilità di $ frac {3} {4} $, con la complessità del tempo di runtime di $ f left (n a destra) $, mostra che c'è un algoritmo che restituisce un $ Varepsilon $-approssimazione additiva con una probabilità di $ 1- Delta $, per lo stesso problema, ma con $ O left (f left (n a destra) log left ( frac {1} { delta} a destra) a destra) $ tempo di esecuzione, per un dato $ Delta> 0 $.

La prima cosa che mi viene in mente è usare un approccio simile a quello prima - eseguire l'algoritmo originale $ k $ I tempi, ma questa volta invece di usare il voto a maggioranza, restituiscono la media.

Devo trovare un po 'un $ k geq o left (ln left ( frac {1} { delta} a destra) a destra) $ tale che $ mathbb {p} left [ Left | opt- frac {1} {k} underset {i = 1} { overset {k} { sum}} x_ {i} destra |> Varepsilon a destra] < delta $.

Ho provato a usare la disuguaglianza del triangolo, quindi usando Union Bound, ma questo non mi ha portato a poter usare Chernoff. Per usare Chernoff, ho pensato di definire una variabile casuale indicatore per ogni esecuzione dell'algoritmo originale, affermando se il risultato - $ X_ {i} $ è cattivo (cioè, se $ Left | x_ {i} -opt a destra |> Varepsilon $), ma è qui che rimango bloccato.

Apprezzerei qualsiasi aiuto. Grazie!