Let \(p\) be a public-coin finite-message protocol over shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), and let \(x \in X\), \(y \in Y\), and \(\omega \in \Omega \). Then the randomized execution of \(p\) on inputs \(x\) and \(y\) with shared randomness \(\omega \) agrees with the deterministic execution of \(p\) on Alice’s effective input \((\omega , x)\) and Bob’s effective input \((\omega , y)\):

Let \(\Omega \) be a probability space, and let \(p\) be a public-coin finite-message protocol with shared randomness in \(\Omega \), private inputs from \(X\) and \(Y\), and outputs in \(\alpha \). For every function \(f : X \to Y \to \alpha \) and every real number \(\varepsilon \), the assertion that \(p\) \(\varepsilon \)-computes \(f\) coincides with the assertion that \(p\) \(\varepsilon \)-satisfies the predicate \((x, y, a) \mapsto (a = f\, x\, y)\); that is, the two propositions are equal.

Let \(p\) be a public-coin finite-message protocol with shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), and let \(q\) be the binary public-coin protocol obtained from \(p\) by encoding each finite-alphabet message as a string of bits. Then for every pair of private inputs \(x \in X\) and \(y \in Y\) and every shared random string \(\omega \in \Omega \), the two protocols produce the same output when executed on those inputs with that randomness: the randomized execution of \(q\) on \(x\), \(y\), \(\omega \) equals the randomized execution of \(p\) on \(x\), \(y\), \(\omega \).

Let \(\Omega \) be a shared-randomness space and let \(p\) be a public-coin finite-message protocol with Alice’s private input in \(X\), Bob’s in \(Y\), and output in \(\alpha \); that is, a deterministic finite-message protocol whose effective input types are \(\Omega \times X\) for Alice and \(\Omega \times Y\) for Bob, in which each message is an element of an arbitrary finite nonempty type \(\beta \) costing \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits. Then the binary public-coin protocol obtained from \(p\) by encoding every \(\beta \)-valued message as \(\lceil \log _2 \left\lvert \beta \right\rvert \rceil \) bits has communication complexity exactly equal to that of \(p\).

Let \(\Omega \) be a shared-randomness space, let \(X\) and \(Y\) be the private input sets of the two players, and let \(\alpha \) be an output type. Let \(p\) be a binary public-coin protocol over these types, that is, a deterministic protocol whose players receive inputs in \(\Omega \times X\) and \(\Omega \times Y\). Embedding \(p\) into the finite-message framework—by treating each Boolean message as a message drawn from the two-element type—and then running the result yields the same output as running \(p\) directly: for every private input \(x \in X\), every private input \(y \in Y\), and every shared random string \(\omega \in \Omega \), the finite-message embedding of \(p\), executed on the paired inputs \((\omega , x)\) and \((\omega , y)\), returns the same value in \(\alpha \) as \(p\) executed on those same paired inputs.

Let \(\Omega \) be a shared-randomness space, let \(X\) and \(Y\) be the private input sets of Alice and Bob, let \(\alpha \) be an output type, and let \(p\) be a binary public-coin protocol over shared randomness \(\Omega \) with these private inputs and this output — that is, a deterministic protocol whose players branch on Boolean messages, with Alice reading \(\Omega \times X\) and Bob reading \(\Omega \times Y\). Embedding \(p\) into the finite-message framework by regarding each Boolean message as an element of the two-element type \(\mathrm{Bool}\) yields a finite-message protocol whose worst-case communication complexity equals the worst-case communication complexity of \(p\).

For every public-coin protocol \(p\) over shared-randomness space \(\Omega \), private input sets \(X\) and \(Y\), and output type \(\alpha \), there exists a public-coin finite-message protocol \(P\) over the same data that computes exactly the same output under randomized execution and has the same communication complexity. Precisely, \(\mathrm{rrun}(P, x, y, \omega ) = \mathrm{rrun}(p, x, y, \omega )\) for all private inputs \(x \in X\), \(y \in Y\) and every shared random string \(\omega \in \Omega \), and the communication complexity of \(P\) equals that of \(p\).