Let \(p\) be a probability mass function on \(\mathrm{Fin}\, m = \{ 0, 1, \dots , m-1\} \) with \(m \ge 1\), and write \(F(n) = \sum _{j \lt n} p(j) \in \mathbb {R}_{\ge 0}^{\infty }\) for its cumulative distribution function. Let \(x \in \mathbb {R}_{\ge 0}^{\infty }\) satisfy \(x \lt 1\), and let \(i \in \mathrm{Fin}\, m\). Then the largest index whose cumulative probability does not exceed \(x\) equals \(i\) if and only if

Let \(p\) be a probability mass function on \(\mathrm{Fin}\, m\) with \(m \ge 1\), and let \(n \ge 1\) be an integer. For each \(j \in \mathrm{Fin}\, n\), let \(\varphi (j) \in \mathrm{Fin}\, m\) be the largest index \(k\) whose cumulative probability \(\sum _{\ell \lt k} p(\ell )\) does not exceed \(j/n\); equivalently, \(\varphi \) evaluates the generalized inverse (quantile function) of the cumulative distribution function of \(p\) at the \(n\) equally spaced points \(0, 1/n, \dots , (n-1)/n\). Then for every index \(i \in \mathrm{Fin}\, m\), the fraction of these \(n\) points that \(\varphi \) sends to \(i\) exceeds the true probability \(p(i)\) by at most \(1/n\):

where \(p(i)\) is read as a real number.

Let \(\Omega \) be a finite probability space, and let \(\delta \gt 0\). Then there exist a natural number \(n\) and a map \(\varphi : \mathrm{CoinTape}(n) \to \Omega \) from the length-\(n\) binary strings such that, writing \(\mu _n\) for the uniform probability measure on \(\mathrm{CoinTape}(n)\) (each of the \(2^n\) strings equally likely) and \(\mu \) for the probability measure on \(\Omega \), every subset \(S \subseteq \Omega \) satisfies

Let \(\Omega _X\) and \(\Omega _Y\) be finite probability spaces, and let \(\delta \gt 0\). Give each coin-tape space \(\mathrm{CoinTape}(n)\) the uniform probability measure arising from \(n\) independent fair coin flips (mass \(2^{-n}\) on each string), and give every product space — both \(\Omega _X \times \Omega _Y\) and \(\mathrm{CoinTape}(n_X) \times \mathrm{CoinTape}(n_Y)\) — the corresponding product measure. Then there exist \(n_X, n_Y \in \mathbb {N}\) and maps \(\varphi _X : \mathrm{CoinTape}(n_X) \to \Omega _X\) and \(\varphi _Y : \mathrm{CoinTape}(n_Y) \to \Omega _Y\) such that, writing \(\varphi _X \times \varphi _Y\) for the map \((u,v) \mapsto (\varphi _X(u), \varphi _Y(v))\), every subset \(S \subseteq \Omega _X \times \Omega _Y\) satisfies

Let \(\Omega _X\) and \(\Omega _Y\) be finite probability spaces, let \(X\), \(Y\) be input types and \(\alpha \) an output type, and let \(p\) be a private-coin finite-message protocol over \(\Omega _X\), \(\Omega _Y\) (that is, a deterministic finite-message protocol on the input types \(\Omega _X \times X\) and \(\Omega _Y \times Y\)). For every real tolerance \(\delta \gt 0\), the coin-tape protocol produced from \(p\) and \(\delta \) — the finite-message protocol over \(\mathrm{CoinTape}(n_X) \times X\) and \(\mathrm{CoinTape}(n_Y) \times Y\) obtained by precomposing \(p\) with the inverse-CDF approximating maps — has communication complexity exactly equal to that of \(p\).

Let \(p\) be a private-coin finite-message protocol over input types \(X\), \(Y\) and output type \(\alpha \), whose private randomness for Alice and Bob is drawn from finite probability spaces \(\Omega _X\) and \(\Omega _Y\). Let \(Q : X \to Y \to \alpha \to \mathrm{Prop}\) be a predicate on input–output triples, and let \(\varepsilon \) and \(\delta \) be real numbers with \(\delta \gt 0\). Suppose \(p\) \(\varepsilon \)-satisfies \(Q\); that is, for every input pair \((x, y)\) the probability, over Alice’s and Bob’s private coins \((\omega _x, \omega _y)\), that the output of \(p\) fails to satisfy \(Q\, x\, y\) is at most \(\varepsilon \). Then the protocol obtained by converting \(p\) at tolerance \(\delta \) — replacing the private randomness by fair coin tapes of some lengths \(n_X\) and \(n_Y\) — \((\varepsilon + \delta )\)-satisfies \(Q\).