Réduire le hasard nécessaire à Turing Machine

Question

Je lis un article lié aux algorithmes de streaming nommés "Les algorithmes de streaming de tourniquet pourraient tout aussi bien être esquissés linéaires" par Yi Li, Huy Nguyen et David Woodruff,

À un moment donné, ils ont un algorithme aléatoire (utilise une bande de bits aléatoires) qui a résolu un problème sur $ mathbb z_ {| m |} ^ {n} = {- m, .., m } ^ n $ réussit avec probabilité 1- delta $

Ils veulent réduire le nombre de bits nécessaires à l'aléatoire utilisé par cet algorithme en utilisant via l'instruction suivante:

Théorème 9: Soit un problème de résolution d'automate randomisé p sur $ mathbb z_ {| m |} ^ {n} $ avec une probabilité de défaillance au plus $ delta $. Il y a un automate ranomisé B qui n'a besoin que de choisir uniformément au hasard l'une de $ o ( delta ^ {- 2} nlogm) $ déterministes de a et résout p sur $ mathbb z_ {| m |} ^ {n} $ avec une probabilité de défaillance au plus 2 $ delta $

Preuve: Soit $ a_1, a_2, .., a_ {o (n delta ^ {- 2} logm)} $ soyez des tirages indépendants d'automates déterministes choisis par B.

Correction d'une entrée $ x in mathbb z_ {| m |} ^ {n} $.

Soit $ p_a (x) $ la fraction de l'automate parmi $ a_1, a_2, ..,> a_ {o (n delta ^ {- 2} logm)} $ qui résout le problème p correctement sur x et $ p_b (x ) $ Soyez la probabilité que B résout P sur x correctement.

Par une liée de cheroff, nous avons que $ pr {| p_a (x) -p_b (x) | geq delta } leq exp (-o (nlogm)) <(2m + 1) ^ {- 2n} $.

Prenant une union liée sur tous les choix de $ x in mathbb z_ {| m |} ^ {n} $, nous avons $ pr {| p_a (x) -p_b (x) | geq delta pour Tous x }> 0 $.

Par conséquent, il existe un ensemble de $ a_1, a_2, .., a_ {o (n delta> ^ {- 2} logm)} $ tel que $ | p_a (x) -p_b (x) | leq delta $ pour tout $ x in> mathbb z_ {| m |} ^ {n} $. L'automate B échantillonne simplement à l'on aléatoire à partir de cet ensemble d'automates déterministes

J'ai du mal à comprendre certaines parties de la preuve:

La variable aléatoire $ p_a (x) $ devrait être le montant de $ a_i $ qui réussit divisé par le montant de leur b échantillonné?

Si tel est le cas que par le faible de la probabilité totale, il est facile de voir cela:

$ p_b (x) = sum_ {i} p [b choisir a_i] p [b succeeds on x | b choisir 'a_i] = sum_ {i} frac {1} {o ( delta ^ {- 2} nlogm)} p [a_i succeets on x] = p_a (x) $

où la dernière décision vient du fait que chaque instance $ a_i $ est déterministe, donc c'est 1 pour le succès ou 0 pour l'échec.

Donc, l'ensemble $ | p_a (x) -p_b (x) | $ qu'ils utilisent est en fait 0

Je comprends de la fin de la preuve que $ | p_a (x) -p_b (x) | $ devrait-il représenter comment représenter la distance entre le succès de A au succès de B mais n'a pas pu voir comment cela se produit.

De plus, je n'ai pas compris l'utilisation de Chernoff comme ils l'ont fait.