Editing Communication complexity (section)

=== Public coins versus private coins ===

Creating random protocols becomes easier when both parties have access to the same random string, known as a shared string protocol. However, even in cases where the two parties do not share a random string, it is still possible to use private string protocols with only a small communication cost.  Any shared string random protocol using any number of random string can be simulated by a private string protocol that uses an extra ''O(log n)'' bits.

Intuitively, we can find some set of strings that has enough randomness in it to run the random protocol with only a small increase in error.  This set can be shared beforehand, and instead of drawing a random string, Alice and Bob need only agree on which string to choose from the shared set. This set is small enough that the choice can be communicated efficiently. A formal proof follows.

Consider some random protocol ''P'' with a maximum error rate of 0.1. Let <math>R</math> be <math>100n</math> strings of length ''n'', numbered <math>r_1, r_2, \dots, r_{100n}</math>. Given such an <math>R</math>, define a new protocol <math>P'_R</math> which randomly picks some <math>r_i</math> and then runs ''P'' using <math>r_i</math> as the shared random string. It takes ''O''(log&nbsp;100''n'') = ''O''(log&nbsp;''n'') bits to communicate the choice of <math>r_i</math>.

Let us define <math>p(x,y)</math> and <math>p'_R(x,y)</math> to be the probabilities that <math>P</math> and <math>P'_R</math>  compute the correct value for the input <math>(x,y)</math>.

For a fixed <math>(x,y)</math>, we can use [[Hoeffding's inequality]] to get the following equation:

:<math>\Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] \leq 2 \exp(-2(0.1)^2 \cdot 100n) < 2^{-2n}</math>

Thus when we don't have <math>(x,y)</math> fixed:

:<math>\Pr_R[\exists (x,y):\ |p'_R(x,y) - p(x,y)| \geq 0.1] \leq \sum_{(x,y)} \Pr_R[|p'_R(x,y) - p(x,y)| \geq 0.1] < \sum_{(x,y)} 2^{-2n} = 1</math>

The last equality above holds because there are <math>2^{2n}</math> different pairs <math>(x,y)</math>. Since the probability does not equal 1, there is some <math>R_0</math> so that for all <math>(x,y)</math>:

:<math>|p'_{R_0}(x,y) - p(x,y)| < 0.1</math>

Since <math>P</math> has at most 0.1 error probability, <math>P'_{R_0}</math> can have at most 0.2 error probability.