AI disclosure
The author used ChatGPT (OpenAI) to discover the main result and assist with literature searches and the preparation and revision of this manuscript. Access was provided through OpenAI’s ChatGPT for Academic Researchers program. For transparency, an earlier draft of this manuscript, written by ChatGPT, is available on the Open Science Framework (OSF). The author reviewed and improved the material incorporated into the manuscript and takes full responsibility for its content.
Introduction
For a finite two-player game with a total relation g g g and question distribution μ \mu μ , let ω ( g , μ ) \omega(g,\mu) ω ( g , μ ) denote its largest winning probability without communication. The classical parallel repetition theorem of Refs. [24 , 16 ] states that, if ω ( g , μ ) < 1 \omega(g,\mu)<1 ω ( g , μ ) < 1 , the largest probability of winning all n n n independent instances ( g n , μ ⊗ n ) (g^n,\mu^{\otimes n}) ( g n , μ ⊗ n ) satisfies
ω ( g n , μ ⊗ n ) ≤ 2 − α n \omega(g^n,\mu^{\otimes n}) \le2^{-\alpha n} ω ( g n , μ ⊗ n ) ≤ 2 − α n
for some constant α = α ( g , μ ) > 0 \alpha=\alpha(g,\mu)>0 α = α ( g , μ ) > 0 . Parallel repetition theorems have diverse applications: they are used to reduce soundness error in two-prover interactive proofs [24 ] and play a central role in hardness-of-approximation results for constraint satisfaction, Clique, and Set Cover [Hås01, Fei98, DS14] for example.
This paper studies how this exponential decay changes when Alice and Bob are allowed to communicate after receiving their question strings. Allowing enough communication eliminates the decay altogether: exchanging the full inputs guarantees success because g g g is total.
The classical theorems already give a partial answer: exponential decay persists when the communication is sufficiently small. Indeed, for a protocol Π n \Pi_n Π n for g n g^n g n communicating at most c n c_n c n bits, guessing its transcript using shared randomness gives a zero-communication strategy whose success probability is at least 2 − c n ⋅ Pr [ Π n succeeds ] 2^{-c_n}\cdot\Pr[\Pi_n\text{ succeeds}] 2 − c n ⋅ Pr [ Π n succeeds ] ; see, e.g., the transcript guessing argument [19 Section 4.1] . The repeated-game value and the preceding classical bound therefore give
Pr μ ⊗ n [ Π n succeeds ] ≤ 2 c n ω ( g n , μ ⊗ n ) ≤ 2 − ( n α − c n ) . \Pr_{\mu^{\otimes n}}[\Pi_n\text{ succeeds}] \le2^{c_n}\omega(g^n,\mu^{\otimes n}) \le2^{-(n\alpha-c_n)}. μ ⊗ n Pr [ Π n succeeds ] ≤ 2 c n ω ( g n , μ ⊗ n ) ≤ 2 − ( n α − c n ) .
Hence, the success probability of the protocol Π n \Pi_n Π n decays exponentially whenever c n ≪ α n c_n\ll\alpha n c n ≪ α n . However, α \alpha α can be very small; α < 1 \alpha<1 α < 1 whenever ω ( g , μ ) > 1 / 2 \omega(g,\mu)>1/2 ω ( g , μ ) > 1/2 ,1 and even the exponent supplied by the current best bound Ref. [16 ] is also less than one. When α < 1 \alpha<1 α < 1 , the condition c n ≪ α n c_n\ll\alpha n c n ≪ α n requires c n / n ≪ 1 c_n/n\ll1 c n / n ≪ 1 , and therefore, the communication allowance obtained by this argument is below one bit per instance. This restriction to less than one bit can be far from optimal: for some functions g g g on m m m -bit inputs and suitable input distributions, the success probability is known to decay exponentially in n n n even with Ω ( n m ) \Omega(nm) Ω ( nm ) bits of communication; see Ref. [23 Corollary 23] .
To fill this gap, this paper investigates the exact communication threshold:
how much communication can be allowed while every protocol still has exponentially small success probability, and how much suffices for success tending to one?
This extends the question addressed by classical parallel repetition, which is recovered when c n = 0 c_n=0 c n = 0 .
This paper determines this exact threshold on the asymptotic rate lim n c n / n \lim_n c_n/n lim n c n / n for every finite total relation g g g and arbitrary input distribution μ \mu μ : it equals IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) , the zero-error value of a quantity called information complexity (see Ref. [4 ] ). Formally, for every δ > 0 \delta>0 δ > 0 , we prove that every two-party protocol Π n \Pi_n Π n having the worst-case cost ∣ Π n ∣ |\Pi_n| ∣ Π n ∣ at most n ( IC μ ( g , 0 ) − δ ) n(\operatorname{IC}_{\mu}(g,0)-\delta) n ( IC μ ( g , 0 ) − δ ) succeeds on ( g n , μ ⊗ n ) (g^n,\mu^{\otimes n}) ( g n , μ ⊗ n ) with probability at most 2 − Ω ( n ) 2^{-\Omega(n)} 2 − Ω ( n ) . Conversely, the compression result of Ref. [4 ] gives protocols Π n \Pi_n Π n with communication cost n ( IC μ ( g , 0 ) + o ( 1 ) ) n(\operatorname{IC}_{\mu}(g,0)+o(1)) n ( IC μ ( g , 0 ) + o ( 1 )) that succeed with probability tending to one. Together, these bounds also determine the exact asymptotic distributional communication complexity of g n g^n g n for every global error ϵ ∈ ( 0 , 1 ) \epsilon\in(0,1) ϵ ∈ ( 0 , 1 ) ; we additionally obtain the corresponding characterization for randomized communication complexity. Our result therefore refines classical parallel repetition by identifying the exact communication threshold below which exponential decay persists. Section 1.1 gives the precise statements and consequences.
Our results and consequences
To state our main result precisely, we first introduce the setting and notation. Let g ⊆ X × Y × A × B g\subseteq\mathcal{X}\times\mathcal{Y}\times\mathcal{A}\times\mathcal{B} g ⊆ X × Y × A × B be a relation on finite sets, where X × Y \mathcal{X}\times\mathcal{Y} X × Y is the set of inputs, and A × B \mathcal{A}\times\mathcal{B} A × B is the set of outputs. (We assume that g g g is total, meaning that a valid output pair exists for every input pair.) Let μ \mu μ be an arbitrary distribution on X × Y \mathcal{X}\times\mathcal{Y} X × Y , and write μ ⊗ n \mu^{\otimes n} μ ⊗ n for its n n n -i.i.d. distribution. We consider general two-party protocols with an arbitrary number of rounds and measure their worst-case communication cost, formally given in Section 2.
Let us also briefly introduce a quantity that plays a crucial role in our result. This quantity, called internal information complexity, is an information-theoretic measure used in communication complexity; see Refs. [4 , 5 , 25 ] . Specifically, our main result uses the zero-error internal information complexity of g g g under the input distribution μ \mu μ , denoted by IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) . The formal definitions are given in Section 2.
Our main result is the following, which is a simplified version of Theorem 3.1; the full statement also gives explicit bounds on the exponent κ \kappa κ .
Theorem 1.1 (Main result). For every 0 ≤ R < IC μ ( g , 0 ) 0\le R<\operatorname{IC}_{\mu}(g,0) 0 ≤ R < IC μ ( g , 0 ) , there exists κ = κ ( g , μ , R ) > 0 \kappa=\kappa(g,\mu,R)>0 κ = κ ( g , μ , R ) > 0 such that, for every n ≥ 1 n\ge1 n ≥ 1 , every protocol Π n \Pi_n Π n for g n g^n g n communicating at most n R nR n R bits satisfies
Pr μ ⊗ n [ Π n succeeds on every coordinate ] ≤ 2 − κ n . \Pr_{\mu^{\otimes n}}[\Pi_n\text{ succeeds on every coordinate}] \le2^{-\kappa n}. μ ⊗ n Pr [ Π n succeeds on every coordinate ] ≤ 2 − κn .
Thus, every communication rate below IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) forces exponentially small success probability, with an exponent independent of the protocol and the number of instances. Consequently, even protocols with success probability 2 − o ( n ) 2^{-o(n)} 2 − o ( n ) require at least n ( IC μ ( g , 0 ) − o ( 1 ) ) n\bigl(\operatorname{IC}_{\mu}(g,0)-o(1)\bigr) n ( IC μ ( g , 0 ) − o ( 1 ) ) bits of worst-case communication. Moreover, at zero communication, our explicit exponent for κ \kappa κ recovers the current best bound of Ref. [16 ] .
Consequences. Theorem 1.1 has several consequences. The first consequence determines the exact asymptotic distributional communication complexity of a finite total relation g g g . For a fixed 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , let D μ ⊗ n , ε ( g n ) D_{\mu^{\otimes n},\varepsilon}(g^n) D μ ⊗ n , ε ( g n ) denote the distributional communication complexity of g n g^n g n under μ ⊗ n \mu^{\otimes n} μ ⊗ n with error at most ε \varepsilon ε ; see § 3 for the formal definition. Theorem 1.1 rules out every fixed rate below IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) , since the success probability eventually falls below 1 − ε 1-\varepsilon 1 − ε . Conversely, applying the compression result of Ref. [4 ] to independent executions of a zero-error protocol achieves every fixed rate above IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) with vanishing overall error. Therefore,
lim n → ∞ D μ ⊗ n , ε ( g n ) n = IC μ ( g , 0 ) . (1) \lim_{n\to\infty}\frac{D_{\mu^{\otimes n},\varepsilon}(g^n)}{n}=\operatorname{IC}_{\mu}(g,0). \tag*{(1)} n → ∞ lim n D μ ⊗ n , ε ( g n ) = IC μ ( g , 0 ) . (1)
Thus, the asymptotic communication rate is independent of the fixed error allowance ε ∈ ( 0 , 1 ) \varepsilon\in(0,1) ε ∈ ( 0 , 1 ) and is determined by the zero-error information complexity. Corollary 8.2 gives the full statement and proof.
Our result also has consequences for randomized communication complexity. Let IC ( g , 0 ) \operatorname{IC}(g,0) IC ( g , 0 ) denote the maximum of IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) over all input distributions μ \mu μ . By definition, for every 0 ≤ R < IC ( g , 0 ) 0\le R<\operatorname{IC}(g,0) 0 ≤ R < IC ( g , 0 ) , there is an input distribution μ \mu μ such that R < IC μ ( g , 0 ) R<\operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) . Thus, applying the main theorem then gives exponential decay of the success probability when inputs are averaged over μ ⊗ n \mu^{\otimes n} μ ⊗ n , which gives the desired exponential decay of success probability on at least one input. See Corollary 8.3 for a formal statement.
Additionally, combining this exponential decay with the upper bound of Ref. [26 ] determines the asymptotic randomized communication rate exactly. For a fixed 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , let R ε ( g n ) R_{\varepsilon}(g^n) R ε ( g n ) denote the randomized communication complexity of g n g^n g n with error at most ε \varepsilon ε , as defined in § 3 . As in the derivation of Equality (1), the implication for the randomized communication rules out every fixed rate below IC ( g , 0 ) \operatorname{IC}(g,0) IC ( g , 0 ) for all sufficiently large n n n . Together with the upper bound [26 ] , this establishes
lim n → ∞ R ε ( g n ) n = IC ( g , 0 ) . \lim_{n\to\infty}\frac{R_{\varepsilon}(g^n)}{n}=\operatorname{IC}(g,0). n → ∞ lim n R ε ( g n ) = IC ( g , 0 ) .
See Corollary 8.4 for the full statement and proof.
Prior works
We compare our results with earlier communication direct-product theorems, strong converses, and characterizations of amortized communication complexity, explaining which communication thresholds were previously known and which are determined by our theorem.
Direct product theorems. We first compare our result with earlier strong2 direct-product theorems [6 , 21 , 7 Yu22, 18 ] in communication complexity. For example, for a Boolean function g g g under an arbitrary input distribution μ \mu μ , Ref. [6 ] proves exponentially small success whenever ∣ Π n ∣ ≥ 2 |\Pi_n| \ge2 ∣ Π n ∣ ≥ 2 and
∣ Π n ∣ ( log ∣ Π n ∣ ) 3 / 2 < c ( D μ ( g , 1 / 3 ) − 2 ) n . |\Pi_n|(\log|\Pi_n|)^{3/2} < c(D_\mu(g,1/3)-2)\sqrt{n}. ∣ Π n ∣ ( log ∣ Π n ∣ ) 3/2 < c ( D μ ( g , 1/3 ) − 2 ) n .
where ∣ Π n ∣ |\Pi_n| ∣ Π n ∣ is the worst-case communication cost of Π n \Pi_n Π n and c > 0 c > 0 c > 0 is a sufficiently small universal constant. More recently, Ref. [18 ] proves stronger results, known as XOR lemmas, and derives corresponding direct-product bounds, with a similar n \sqrt{n} n dependence on the number of instances up to logarithmic factors.
As a prior work using internal information complexity IC μ ( g , 1 / 3 ) \operatorname{IC}_\mu(g,1/3) IC μ ( g , 1/3 ) with error ≤ 1 / 3 \le1/3 ≤ 1/3 , Ref. [7 ] proves exponentially small success probability whenever ∣ Π n ∣ ≥ 2 |\Pi_n| \ge2 ∣ Π n ∣ ≥ 2 and
∣ Π n ∣ log ( ∣ Π n ∣ log ∣ Π n ∣ ) ≤ c n IC μ ( g , 1 / 3 ) , |\Pi_n|\log(|\Pi_n|\log|\Pi_n|) \le cn\operatorname{IC}_\mu(g,1/3), ∣ Π n ∣ log ( ∣ Π n ∣ log ∣ Π n ∣ ) ≤ c n IC μ ( g , 1/3 ) ,
again for a sufficiently small universal constant c > 0 c > 0 c > 0 . Ref. [3 ] also discusses the relation between parallel repetition and information complexity but without communication.
These results do not determine the optimal communication threshold for exponential decay for general tasks. In contrast, Theorem 1.1 establishes exponential decay at every fixed rate below IC μ ( g , 0 ) \operatorname{IC}_\mu(g,0) IC μ ( g , 0 ) for every finite total relation g g g and arbitrary input distribution μ \mu μ , giving the exact threshold for the first time together with the matching upper bound discussed above.
Additionally, combining our theorem with the lower bounds on IC μ ( g , 0 ) \operatorname{IC}_\mu(g,0) IC μ ( g , 0 ) of Refs. [9 , 20 , 8 ] recovers several strong direct-product conclusions. Examples include those for Set Disjointness, Tribes, and Inner Product previously obtained in Refs. [22 , 15 , 23 ] , respectively.
Works from information theory. Our result is also closely related to work in information theory, where such exponential decay of success is studied under the name of exponential strong converses . For a function g g g , Ref. [TVVW17] proves, among other results, that for every fixed δ > 0 \delta> 0 δ > 0 , the success probability of Π n \Pi_n Π n is exponentially small whenever
∣ Π n ∣ ≤ n [ H ( g ( X , Y ) ∣ X ) + H ( g ( X , Y ) ∣ Y ) − δ ] . |\Pi_n| \le n\left[H(g(X,Y)\mid X)+H(g(X,Y)\mid Y)-\delta\right]. ∣ Π n ∣ ≤ n [ H ( g ( X , Y ) ∣ X ) + H ( g ( X , Y ) ∣ Y ) − δ ] .
where ( X , Y ) ∼ μ (X,Y) \sim\mu ( X , Y ) ∼ μ and H ( ⋅ ∣ ⋅ ) H(\cdot\mid\cdot) H ( ⋅ ∣ ⋅ ) denotes conditional entropy. Notably, Ref. [TVVW17] explicitly identifies replacing this entropy threshold by zero-error information complexity IC μ ( g , 0 ) \operatorname{IC}_\mu(g,0) IC μ ( g , 0 ) as the desired strengthening. The function case of Theorem 1.1 achieves this strengthening.
Refs. [TW20, HWS24] provide further close comparisons: they establish exponential strong converses with a fixed number of communication rounds, at the corresponding round-restricted rates. Our result has no restriction on the number of rounds.
Amortized communication complexity. Information complexity also characterizes amortized communication under a per-coordinate error requirement . Ref. [4 ] shows that IC μ ( g , ε ) \operatorname{IC}_\mu(g,\varepsilon) IC μ ( g , ε ) equals the amortized distributional communication complexity when the error probability on each coordinate is at most ε \varepsilon ε . Ref. [5 ] establishes the corresponding characterization of randomized communication in terms of IC ( g , ε ) \operatorname{IC}(g,\varepsilon) IC ( g , ε ) . Under a strict requirement that all coordinates be correct simultaneously, Ref. [26 ] proves that, for every fixed 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , the amortized rate is exactly ( 1 − ε ) IC ( g , 0 ) (1-\varepsilon)\operatorname{IC}(g,0) ( 1 − ε ) IC ( g , 0 ) when communication cost is measured in expectation. For worst-case randomized communication complexity, Ref. [26 ] establishes the bounds
( 1 − ε ) IC ( g , 0 ) ≤ lim inf n → ∞ R ε ( g n ) n ≤ lim sup n → ∞ R ε ( g n ) n ≤ IC ( g , 0 ) . (1-\varepsilon)\operatorname{IC}(g,0) \le\liminf_{n\to\infty}\frac{R_\varepsilon(g^n)}{n} \le\limsup_{n\to\infty}\frac{R_\varepsilon(g^n)}{n} \le\operatorname{IC}(g,0). ( 1 − ε ) IC ( g , 0 ) ≤ n → ∞ lim inf n R ε ( g n ) ≤ n → ∞ lim sup n R ε ( g n ) ≤ IC ( g , 0 ) .
Our result closes this interval at its upper bound and, more strongly, proves exponential decay of success probability at every rate below that value.
Proof techniques and comparison
We briefly outline our proof strategy to prepare for the comparison with prior techniques below; Section 3 gives a detailed proof overview using the terminology and notation introduced in Section 2.
Proof technique. The proof proceeds by contradiction. Fix 0 ≤ R < IC μ ( g , 0 ) 0 \le R < \operatorname{IC}_{\mu}(g,0) 0 ≤ R < IC μ ( g , 0 ) , and suppose that an n n n -instance protocol Π n \Pi_n Π n communicates at most n R nR n R bits and succeeds too often. We will use Π n \Pi_n Π n to construct, for a suitable ε > 0 \varepsilon> 0 ε > 0 , a protocol for g g g with error at most ε \varepsilon ε and information cost strictly below IC μ ( g , ε ) \operatorname{IC}_{\mu}(g,\varepsilon) IC μ ( g , ε ) , contradicting its definition. For this construction, we choose ε > 0 \varepsilon> 0 ε > 0 such that R < IC μ ( g , ε ) R < \operatorname{IC}_{\mu}(g,\varepsilon) R < IC μ ( g , ε ) , which is possible by continuity of IC μ ( g , ε ) \operatorname{IC}_{\mu}(g,\varepsilon) IC μ ( g , ε ) at zero error.
We first construct a single-instance distribution q s i n g l e q_{\mathrm{single}} q single from Π n \Pi_n Π n as follows. Let P Π n P_{\Pi_n} P Π n denote the joint distribution of
( ( X n , Y n ) , ( A n , B n ) , T n ) \left((X^n,Y^n),(A^n,B^n),T_n\right) ( ( X n , Y n ) , ( A n , B n ) , T n )
induced by Π n \Pi_n Π n under μ ⊗ n \mu^{\otimes n} μ ⊗ n . For a suitably chosen set S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] , define the event
W S = ⋂ i ∈ S { ( A i , B i ) ∈ g ( X i , Y i ) } . W_S = \bigcap_{i \in S}\{(A_i,B_i) \in g(X_i,Y_i)\}. W S = i ∈ S ⋂ {( A i , B i ) ∈ g ( X i , Y i )} .
Let us sample the inputs, outputs, and transcript according to the distribution P Π n ( ⋅ ∣ W S ) P_{\Pi_n}(\mathord{\cdot}\mid W_S) P Π n ( ⋅ ∣ W S ) after conditioning on W S W_S W S , and independently choose J ∼ Unif ( [ n ] ) J \sim\operatorname{Unif}([n]) J ∼ Unif ([ n ]) . Let q s i n g l e q_{\mathrm{single}} q single be the resulting joint distribution of ( X , Y , A , B , V ) (X,Y,A,B,V) ( X , Y , A , B , V ) , where
( X , Y , A , B ) = ( X J , Y J , A J , B J ) (X,Y,A,B)=(X_J,Y_J,A_J,B_J) ( X , Y , A , B ) = ( X J , Y J , A J , B J )
and V V V is the auxiliary variable defined in Section 3. The set S S S and the variables retained in V V V are chosen to ensure two guarantees: (i) q s i n g l e [ ( A , B ) ∉ g ( X , Y ) ] ≤ ε / 2 q_{\mathrm{single}}[(A,B) \notin g(X,Y)] \le\varepsilon/2 q single [( A , B ) ∈ / g ( X , Y )] ≤ ε /2 , and (ii) the information value
I q s i n g l e ( X ; V ∣ Y ) + I q s i n g l e ( Y ; V ∣ X ) I_{q_{\mathrm{single}}}(X;V\mid Y)+I_{q_{\mathrm{single}}}(Y;V\mid X) I q single ( X ; V ∣ Y ) + I q single ( Y ; V ∣ X )
is at most R R R plus a small additive loss.
To derive the contradiction from guarantees (i) and (ii), we need corresponding bounds for a protocol on inputs drawn from μ \mu μ . The distribution q s i n g l e q_{\mathrm{single}} q single need not arise from such a protocol: conditioning may change the input marginal, and V V V need not be a valid protocol transcript. To this end, we construct a desired protocol π s i n g l e \pi_{\mathrm{single}} π single using the conditional distributions of q s i n g l e q_{\mathrm{single}} q single , with each message generated using only the sender’s input and the preceding shared information, as follows.
Write V = ( V p u b , V 1 , … , V m ) V=(V_{\mathrm{pub}},V_1,\ldots,V_m) V = ( V pub , V 1 , … , V m ) . On inputs ( X , Y ) ∼ μ (X,Y)\sim\mu ( X , Y ) ∼ μ , the players first sample V p u b V_{\mathrm{pub}} V pub publicly according to q s i n g l e ( V p u b ) q_{\mathrm{single}}(V_{\mathrm{pub}}) q single ( V pub ) , independently of their inputs, and then alternately generate the messages V 1 , … , V m V_1,\ldots,V_m V 1 , … , V m . The resulting joint distribution is
P π s i n g l e ( X , Y , A , B , V ) = μ ( X , Y ) q s i n g l e ( V p u b ) × q s i n g l e ( V 1 ∣ X , V p u b ) q s i n g l e ( V 2 ∣ Y , V p u b , V 1 ) × q s i n g l e ( V 3 ∣ X , V p u b , V 1 , V 2 ) ⋯ × q s i n g l e ( A ∣ X , V ) q s i n g l e ( B ∣ Y , V ) . (2) \begin{aligned}
P_{\pi_{\mathrm{single}}}(X,Y,A,B,V)
={}&\mu(X,Y)\,q_{\mathrm{single}}(V_{\mathrm{pub}})\\
&\times q_{\mathrm{single}}(V_1\mid X,V_{\mathrm{pub}})
q_{\mathrm{single}}(V_2\mid Y,V_{\mathrm{pub}},V_1)\\
&\times q_{\mathrm{single}}(V_3\mid X,V_{\mathrm{pub}},V_1,V_2)\cdots\\
&\times q_{\mathrm{single}}(A\mid X,V)\,q_{\mathrm{single}}(B\mid Y,V). \tag*{(2)}
\end{aligned} P π single ( X , Y , A , B , V ) = μ ( X , Y ) q single ( V pub ) × q single ( V 1 ∣ X , V pub ) q single ( V 2 ∣ Y , V pub , V 1 ) × q single ( V 3 ∣ X , V pub , V 1 , V 2 ) ⋯ × q single ( A ∣ X , V ) q single ( B ∣ Y , V ) . (2)
Each message and output is sampled using only information available to the respective player, so this defines a valid protocol.
We now compare P π s i n g l e P_{\pi_{\mathrm{single}}} P π single with q s i n g l e q_{\mathrm{single}} q single . Write δ = TV ( P π s i n g l e , q s i n g l e ) \delta= \operatorname{TV}(P_{\pi_{\mathrm{single}}}, q_{\mathrm{single}}) δ = TV ( P π single , q single ) . Guarantee (i) then gives
err μ ( π s i n g l e ) = P π s i n g l e [ ( A , B ) ∉ g ( X , Y ) ] ≤ q s i n g l e [ ( A , B ) ∉ g ( X , Y ) ] + δ ≤ ε / 2 + δ . \begin{aligned}
\operatorname{err}_{\mu}(\pi_{\mathrm{single}}) = P_{\pi_{\mathrm{single}}}[(A,B) \notin g(X,Y)] \\
&\le q_{\mathrm{single}}[(A,B) \notin g(X,Y)] + \delta\\
&\le\varepsilon/2 + \delta.
\end{aligned} err μ ( π single ) = P π single [( A , B ) ∈ / g ( X , Y )] ≤ q single [( A , B ) ∈ / g ( X , Y )] + δ ≤ ε /2 + δ .
Using guarantee (ii) and continuity of conditional mutual information, we also obtain
IC μ ( π s i n g l e ) = I P π s i n g l e ( X ; V ∣ Y ) + I P π s i n g l e ( Y ; V ∣ X ) ≤ R + η , \begin{aligned}
\operatorname{IC}_{\mu}(\pi_{\mathrm{single}}) = I_{P_{\pi_{\mathrm{single}}}}(X;V \mid Y) + I_{P_{\pi_{\mathrm{single}}}}(Y;V \mid X) \\
&\le R + \eta,
\end{aligned} IC μ ( π single ) = I P π single ( X ; V ∣ Y ) + I P π single ( Y ; V ∣ X ) ≤ R + η ,
where η ≥ 0 \eta\ge0 η ≥ 0 accounts for both the additive loss in (ii) and the change in the information expression when replacing q s i n g l e q_{\mathrm{single}} q single by P π s i n g l e P_{\pi_{\mathrm{single}}} P π single . We prove that, when Π n \Pi_n Π n succeeds sufficiently often, these losses are small enough to satisfy
δ ≤ ε / 2 , η < IC μ ( g , ε ) − R . \delta\le\varepsilon/2,\qquad\eta< \operatorname{IC}_{\mu}(g,\varepsilon) - R. δ ≤ ε /2 , η < IC μ ( g , ε ) − R .
The resulting protocol therefore has error at most ε \varepsilon ε and information cost strictly below IC μ ( g , ε ) \operatorname{IC}_{\mu}(g,\varepsilon) IC μ ( g , ε ) , giving the desired contradiction.
Comparison to prior work. The above strategy of conditioning on events such as success on selected coordinates, followed by single-coordinate extraction, is an established approach in parallel repetition and communication direct-product proofs; see Refs. [16 , 6 ] for example. In related work on information and communication complexity, Refs. [Yu22, IR24, SY25] obtain intermediate single-instance distributions playing a role similar to q s i n g l e q_{\mathrm{single}} q single through conditioning or decomposition of the original protocol Π n \Pi_n Π n , while controlling their error together with appropriate information quantities. For our contradiction, the extracted distribution q s i n g l e q_{\mathrm{single}} q single must simultaneously have small error and satisfy
I q s i n g l e ( X ; V ∣ Y ) + I q s i n g l e ( Y ; V ∣ X ) ≤ R + o ( 1 ) , I_{q_{\mathrm{single}}}(X;V \mid Y) + I_{q_{\mathrm{single}}}(Y;V \mid X) \le R + o(1), I q single ( X ; V ∣ Y ) + I q single ( Y ; V ∣ X ) ≤ R + o ( 1 ) ,
where the additive loss vanishes as − log ( Pr [ Π n succeeds ] ) / n → 0 -\log(\Pr[\Pi_n\text{ succeeds}])/n \to0 − log ( Pr [ Π n succeeds ]) / n → 0 . For comparison, the corresponding lemma of Ref. [27 ] gives a single-instance information bound of O ( R + 1 ) O(R+1) O ( R + 1 ) when the n n n -instance protocol has information cost at most n R nR n R , without requiring the coefficient of R R R to be one. Our extraction preserves the coefficient one on R R R and incurs only a vanishing additive loss. Prior works have also developed techniques for obtaining valid protocols from conditioned distributions; see Refs. [6 , 7 TW20, 27 ] . Our construction of π s i n g l e \pi_{\mathrm{single}} π single from q s i n g l e q_{\mathrm{single}} q single in (2) uses local conditional distributions, as in Ref. [27 ] .
Organization of the paper
The remainder of the paper is organized as follows.
Section 2 introduces the communication model and information measures and provides preliminary facts.
Section 3 states our main theorem, Theorem 3.1, and gives an overview of its proof.
Sections 4 to 7 prove Theorem 3.1, following the overview in § 4.1 .
Section 8 derives the exact asymptotic communication rates and corresponding strong converses in the distributional and randomized settings from Theorem 3.1.
Appendices A, B, and C provide supplementary results needed for the proof.
Model and information measures
Relations and protocols
Our result compares communication cost for g n g^n g n with the information cost of one copy of g g g . We first specify what it means to solve the relation and then define these two costs.
Let X , Y , A , B \mathcal{X},\mathcal{Y},\mathcal{A},\mathcal{B} X , Y , A , B be nonempty finite sets. Alice receives x ∈ X x \in\mathcal{X} x ∈ X and Bob receives y ∈ Y y \in\mathcal{Y} y ∈ Y . They output a ∈ A a \in\mathcal{A} a ∈ A and b ∈ B b \in\mathcal{B} b ∈ B locally. The relation g ⊆ X × Y × A × B g \subseteq\mathcal{X} \times\mathcal{Y} \times\mathcal{A} \times\mathcal{B} g ⊆ X × Y × A × B is total: for each ( x , y ) (x,y) ( x , y ) , at least one output pair is valid,
g ( x , y ) : = { ( a , b ) : ( x , y , a , b ) ∈ g } ≠ ∅ . g(x,y) := \{(a,b) : (x,y,a,b) \in g\} \ne\varnothing. g ( x , y ) := {( a , b ) : ( x , y , a , b ) ∈ g } = ∅ .
On n n n input pairs, success for g n g^n g n means that ( A i , B i ) ∈ g ( X i , Y i ) (A_i,B_i) \in g(X_i,Y_i) ( A i , B i ) ∈ g ( X i , Y i ) for every i ∈ [ n ] i \in[n] i ∈ [ n ] . We draw ( X 1 , Y 1 ) , … , ( X n , Y n ) (X_1,Y_1),\ldots,(X_n,Y_n) ( X 1 , Y 1 ) , … , ( X n , Y n ) independently from one fixed distribution μ \mu μ on X × Y \mathcal{X} \times\mathcal{Y} X × Y .
We consider finite classical interactive protocols with binary communication. The sender of each bit is determined by the public history, consisting of the transcript and shared randomness. The inputs, Public randomness R p u b R_{\mathrm{pub}} R pub , Alice’s private randomness, and Bob’s private randomness are all mutually independent. Each output depends only on that player’s input, its private randomness, and the public history. All random variables have finite alphabets. The worst-case number of communicated bits in a protocol π \pi π is ∣ π ∣ = Cost w c ( π ) |\pi| = \operatorname{Cost}_{\mathrm{wc}}(\pi) ∣ π ∣ = Cost wc ( π ) .
For a function f : X × Y → Z f : \mathcal{X} \times\mathcal{Y} \to\mathcal{Z} f : X × Y → Z considered for communication complexity applications, we use the relation
g f = { ( x , y , a , b ) : f ( x , y ) = a = b } ⊆ X × Y × Z × Z . g_f = \{(x,y,a,b) : f(x,y) = a = b\} \subseteq\mathcal{X} \times\mathcal{Y} \times\mathcal{Z} \times\mathcal{Z}. g f = {( x , y , a , b ) : f ( x , y ) = a = b } ⊆ X × Y × Z × Z .
Thus both parties must output the value of f f f .
Communication and information measures
In the standard manner, for 0 ≤ ε ≤ 1 0 \le\varepsilon\le1 0 ≤ ε ≤ 1 , define
D μ ⊗ n , ε ( g n ) : = inf Π : Pr μ ⊗ n [ Π fails on some coordinate ] ≤ ε Cost w c ( Π ) , (3) D_{\mu^{\otimes n},\varepsilon}(g^n) := \inf_{\Pi:\Pr_{\mu^{\otimes n}}[\Pi\text{ fails on some coordinate}]\le\varepsilon} \operatorname{Cost}_{\mathrm{wc}}(\Pi), \tag*{(3)} D μ ⊗ n , ε ( g n ) := Π : P r μ ⊗ n [ Π fails on some coordinate ] ≤ ε inf Cost wc ( Π ) , (3)
R ε ( g n ) : = inf Π : max ( x n , y n ) Pr [ Π fails on some coordinate ∣ x n , y n ] ≤ ε Cost w c ( Π ) . (4) R_{\varepsilon}(g^n) := \inf_{\Pi:\max_{(x^n,y^n)}\Pr[\Pi\text{ fails on some coordinate}\mid x^n,y^n]\le\varepsilon} \operatorname{Cost}_{\mathrm{wc}}(\Pi). \tag*{(4)} R ε ( g n ) := Π : m a x ( x n , y n ) P r [ Π fails on some coordinate ∣ x n , y n ] ≤ ε inf Cost wc ( Π ) . (4)
The probability conditional on a fixed input is over the protocol’s randomness.
For a single-instance protocol π \pi π on ( X , Y ) ∼ μ (X,Y) \sim\mu ( X , Y ) ∼ μ , let T T T denote its communicated transcript and let P π P_\pi P π be the joint distribution of its inputs, public randomness R p u b R_{\mathrm{pub}} R pub , transcript, and outputs A B AB A B . Define its error and information cost by
err μ ( π ) = Pr P π [ ( A , B ) ∉ g ( X , Y ) ] , \operatorname{err}_{\mu}(\pi) = \Pr_{P_\pi}[(A,B) \notin g(X,Y)], err μ ( π ) = P π Pr [( A , B ) ∈ / g ( X , Y )] ,
IC μ ( π ) = I P π ( X ; T ∣ Y , R p u b ) + I P π ( Y ; T ∣ X , R p u b ) , (5) \operatorname{IC}_{\mu}(\pi) = I_{P_\pi}(X;T\mid Y,R_{\mathrm{pub}}) + I_{P_\pi}(Y;T\mid X,R_{\mathrm{pub}}), \tag*{(5)} IC μ ( π ) = I P π ( X ; T ∣ Y , R pub ) + I P π ( Y ; T ∣ X , R pub ) , (5)
where I P ( X ; Y ∣ Z ) I_P(X;Y\mid Z) I P ( X ; Y ∣ Z ) is the conditional mutual information under the distribution P P P . We also define
IC μ ( g , ε ) = inf π : err μ ( π ) ≤ ε IC μ ( π ) , err μ ( R ) = inf π : IC μ ( π ) ≤ R err μ ( π ) ( R ≥ 0 ) . (6) \operatorname{IC}_{\mu}(g,\varepsilon) = \inf_{\pi:\operatorname{err}_{\mu}(\pi)\le\varepsilon}\operatorname{IC}_{\mu}(\pi), \qquad\operatorname{err}_{\mu}(R) = \inf_{\pi:\operatorname{IC}_{\mu}(\pi)\le R}\operatorname{err}_{\mu}(\pi) \qquad(R \ge0). \tag*{(6)} IC μ ( g , ε ) = π : err μ ( π ) ≤ ε inf IC μ ( π ) , err μ ( R ) = π : IC μ ( π ) ≤ R inf err μ ( π ) ( R ≥ 0 ) . (6)
For a non-distributional information measure, require the protocol to meet the error bound on every input and take its largest information cost over input distributions:
IC ( g , ε ) = inf π : max ( x , y ) Pr [ π errs ∣ x , y ] ≤ ε max ν IC ν ( π ) . (7) \operatorname{IC}(g,\varepsilon) = \inf_{\pi:\max_{(x,y)}\Pr[\pi\text{ errs}\mid x,y]\le\varepsilon}\max_{\nu}\operatorname{IC}_{\nu}(\pi). \tag*{(7)} IC ( g , ε ) = π : m a x ( x , y ) P r [ π errs ∣ x , y ] ≤ ε inf ν max IC ν ( π ) . (7)
Here ν \nu ν ranges over distributions on X × Y \mathcal{X} \times\mathcal{Y} X × Y .
For the same distribution μ \mu μ , the best success probability without communication and its gap from one are
ω ( g , μ ) = max a : X → A , b : Y → B Pr μ [ ( a ( X ) , b ( Y ) ) ∈ g ( X , Y ) ] , η = 1 − ω ( g , μ ) . (8) \omega(g,\mu) = \max_{\substack{a:\mathcal{X}\to\mathcal{A},\ b:\mathcal{Y}\to\mathcal{B}}} \Pr_{\mu}[(a(X),b(Y)) \in g(X,Y)], \qquad\eta= 1-\omega(g,\mu). \tag*{(8)} ω ( g , μ ) = a : X → A , b : Y → B max μ Pr [( a ( X ) , b ( Y )) ∈ g ( X , Y )] , η = 1 − ω ( g , μ ) . (8)
Probability and string notation
All logarithms are base 2, while ln \ln ln denotes the natural logarithm. We write
L i n = log ( ∣ X ∣ ∣ Y ∣ ) , L o u t = log ( ∣ A ∣ ∣ B ∣ ) , L_{\mathrm{in}} = \log(|\mathcal{X}||\mathcal{Y}|), \qquad L_{\mathrm{out}} = \log(|\mathcal{A}||\mathcal{B}|), L in = log ( ∣ X ∣∣ Y ∣ ) , L out = log ( ∣ A ∣∣ B ∣ ) ,
for the logarithms of the input and output alphabet sizes. The binary entropy is h ( t ) = − t log t − ( 1 − t ) log ( 1 − t ) h(t)=-t\log t-(1-t)\log(1-t) h ( t ) = − t log t − ( 1 − t ) log ( 1 − t ) , with 0 log 0 = 0 0\log0=0 0 log 0 = 0 . For distributions q , P q,P q , P on the same finite set,
D ( q ∥ P ) = ∑ z : q ( z ) > 0 q ( z ) log q ( z ) P ( z ) , TV ( q , P ) = 1 2 ∑ z ∣ q ( z ) − P ( z ) ∣ . D(q\mathbin{\|}P)=\sum_{z:q(z)>0}q(z)\log\frac{q(z)}{P(z)}, \qquad\operatorname{TV}(q,P)=\frac{1}{2}\sum_z|q(z)-P(z)|. D ( q ∥ P ) = z : q ( z ) > 0 ∑ q ( z ) log P ( z ) q ( z ) , TV ( q , P ) = 2 1 z ∑ ∣ q ( z ) − P ( z ) ∣.
Set D ( q ∥ P ) = + ∞ D(q\mathbin{\|}P)=+\infty D ( q ∥ P ) = + ∞ if q ( z ) > 0 = P ( z ) q(z)>0=P(z) q ( z ) > 0 = P ( z ) for some z z z . A distribution written as a subscript on an entropy or information quantity, e.g., H μ ( X ∣ Y ) H_{\mu}(X\mid Y) H μ ( X ∣ Y ) , specifies the probability experiment used.
For input strings X n X^n X n , we use X < i = ( X 1 , … , X i − 1 ) X_{<i}=(X_1,\ldots,X_{i-1}) X < i = ( X 1 , … , X i − 1 ) , X > i = ( X i + 1 , … , X n ) X_{>i}=(X_{i+1},\ldots,X_n) X > i = ( X i + 1 , … , X n ) , and X ≤ i = ( X 1 , … , X i ) X_{\leq i}=(X_1,\ldots,X_i) X ≤ i = ( X 1 , … , X i ) , and analogously for Y n Y^n Y n . Also [ n ] = { 1 , … , n } [n]=\{1,\ldots,n\} [ n ] = { 1 , … , n } .
Probability and information facts
We use the following standard identities and inequalities for finite distributions. For Facts 2.1 and 2.2, see Ref. [11 Chapter 2] ; for Pinsker’s inequality, see Ref. [10 Problem 3.18] .
Fact 2.1. For finite distributions q , P q,P q , P , relative entropy is nonnegative and satisfies the chain rule
D ( q X Y ∥ P X Y ) = D ( q X ∥ P X ) + E x ∼ q X D ( q Y ∣ X = x ∥ P Y ∣ X = x ) . (9) D(q_{XY}\mathbin{\|}P_{XY})=D(q_X\mathbin{\|}P_X)+\mathbb{E}_{x\sim q_X}D(q_{Y\mid X=x}\mathbin{\|}P_{Y\mid X=x}). \tag*{(9)} D ( q X Y ∥ P X Y ) = D ( q X ∥ P X ) + E x ∼ q X D ( q Y ∣ X = x ∥ P Y ∣ X = x ) . (9) If P ( E ) > 0 P(E)>0 P ( E ) > 0 , then D ( P ( ⋅ ∣ E ) ∥ P ) = log ( 1 / P ( E ) ) D(P(\cdot\mid E)\mathbin{\|}P)=\log(1/P(E)) D ( P ( ⋅ ∣ E ) ∥ P ) = log ( 1/ P ( E )) .
Fact 2.2. Conditional mutual information is nonnegative and satisfies
I q ( X ; V ∣ Y ) = E ( x , y ) ∼ q D ( q V ∣ x , y ∥ q V ∣ y ) = H q ( X ∣ Y ) − H q ( X ∣ Y , V ) , I_q(X;V\mid Y)=\mathbb{E}_{(x,y)\sim q}D(q_{V\mid x,y}\mathbin{\|}q_{V\mid y})=H_q(X\mid Y)-H_q(X\mid Y,V), I q ( X ; V ∣ Y ) = E ( x , y ) ∼ q D ( q V ∣ x , y ∥ q V ∣ y ) = H q ( X ∣ Y ) − H q ( X ∣ Y , V ) , I q ( X ; V , W ∣ Y ) = I q ( X ; V ∣ Y ) + I q ( X ; W ∣ Y , V ) . (10) I_q(X;V,W\mid Y)=I_q(X;V\mid Y)+I_q(X;W\mid Y,V). \tag*{(10)} I q ( X ; V , W ∣ Y ) = I q ( X ; V ∣ Y ) + I q ( X ; W ∣ Y , V ) . (10) Applying the same randomized map to two distributions cannot increase their relative entropy or total variation.
Fact 2.3 (Pinsker’s inequality). For finite distributions,
TV ( q , P ) ≤ ln 2 2 D ( q ∥ P ) . \operatorname{TV}(q,P)\leq\sqrt{\frac{\ln2}{2}D(q\mathbin{\|}P)}. TV ( q , P ) ≤ 2 ln 2 D ( q ∥ P ) . For any event F F F , ∣ q ( F ) − P ( F ) ∣ ≤ TV ( q , P ) |q(F)-P(F)|\leq\operatorname{TV}(q,P) ∣ q ( F ) − P ( F ) ∣ ≤ TV ( q , P ) .
The next inequality bounds the change in information cost when two joint distributions are close. Its dependence on the input alphabets does not involve the alphabet of the transcript. The conditional-entropy bound follows from the stronger result in Ref. [1 ] .
Fact 2.4. If TV ( q Z W , P Z W ) ≤ δ ≤ 1 / 2 \operatorname{TV}(q_{ZW}, P_{ZW}) \le\delta\le1/2 TV ( q Z W , P Z W ) ≤ δ ≤ 1/2 , then
∣ H q ( Z ∣ W ) − H P ( Z ∣ W ) ∣ ≤ δ log ∣ Z ∣ + h ( δ ) . (11) \left|H_q(Z \mid W) - H_P(Z \mid W)\right| \le\delta\log|\mathcal{Z}| + h(\delta). \tag*{(11)} ∣ H q ( Z ∣ W ) − H P ( Z ∣ W ) ∣ ≤ δ log ∣ Z ∣ + h ( δ ) . (11) Consequently, if TV ( q X Y H , P X Y H ) ≤ δ ≤ 1 / 2 \operatorname{TV}(q_{XYH}, P_{XYH}) \le\delta\le1/2 TV ( q X Y H , P X Y H ) ≤ δ ≤ 1/2 , then
I q ( X ; H ∣ Y ) + I q ( Y ; H ∣ X ) − I P ( X ; H ∣ Y ) − I P ( Y ; H ∣ X ) ≤ 2 L i n δ + 4 h ( δ ) . (12) \begin{aligned}
&I_q(X; H \mid Y) + I_q(Y; H \mid X) - I_P(X; H \mid Y) - I_P(Y; H \mid X) \\
&\le2L_{\mathrm{in}}\delta+ 4h(\delta). \tag*{(12)}
\end{aligned} I q ( X ; H ∣ Y ) + I q ( Y ; H ∣ X ) − I P ( X ; H ∣ Y ) − I P ( Y ; H ∣ X ) ≤ 2 L in δ + 4 h ( δ ) . (12) The information bound (12) follows by applying the conditional-entropy bound (11) to H ( X ∣ Y ) H(X \mid Y) H ( X ∣ Y ) , H ( X ∣ Y , H ) H(X \mid Y,H) H ( X ∣ Y , H ) , H ( Y ∣ X ) H(Y \mid X) H ( Y ∣ X ) , and H ( Y ∣ X , H ) H(Y \mid X,H) H ( Y ∣ X , H ) .
Protocol facts
We use Proposition 2.5 to lower-bound communication cost by information cost. For the standard comparison between information and communication, see Refs. [4 , 25 ] for example.
Proposition 2.5. For any input distribution ν \nu ν and finite binary protocol π \pi π ,
IC ν ( π ) ≤ Cost w c ( π ) . \operatorname{IC}_{\nu}(\pi) \le\operatorname{Cost}_{\mathrm{wc}}(\pi). IC ν ( π ) ≤ Cost wc ( π ) .
The following fact is used to simplify the explicit exponent. Its proof appears in Appendix A.
Fact 2.6. For 0 ≤ t ≤ 1 0 \le t \le1 0 ≤ t ≤ 1 , the binary entropy satisfies h ( t ) ≤ 3 t h(t) \le3\sqrt{t} h ( t ) ≤ 3 t .
Main result
Our main theorem, Theorem 3.1, is formally stated as follows.
Theorem 3.1 (Exponential strong converse). Fix 0 ≤ R < IC μ ( g , 0 ) 0 \le R < \operatorname{IC}_{\mu}(g,0) 0 ≤ R < IC μ ( g , 0 ) . Then err μ ( R ) > 0 \operatorname{err}_{\mu}(R) > 0 err μ ( R ) > 0 , and every protocol Π n \Pi_n Π n for g n g^n g n with Cost w c ( Π n ) ≤ n R \operatorname{Cost}_{\mathrm{wc}}(\Pi_n) \le nR Cost wc ( Π n ) ≤ n R satisfies
Pr μ ⊗ n [ Π n succeeds on every coordinate ] ≤ 2 − n κ ( R ) . (13) \Pr_{\mu^{\otimes n}}[\Pi_n\ \text{succeeds on every coordinate}] \le2^{-n\kappa(R)}. \tag*{(13)} μ ⊗ n Pr [ Π n succeeds on every coordinate ] ≤ 2 − nκ ( R ) . (13) For R > 0 R > 0 R > 0 , one may take
κ ( R ) = 2 − 28 min { err μ ( R ) 3 L o u t , err μ ( R ) 4 R 2 ( 1 + L i n ) 4 } . (14) \kappa(R) = 2^{-28}\min\left\{\frac{\operatorname{err}_{\mu}(R)^3}{L_{\mathrm{out}}}, \frac{\operatorname{err}_{\mu}(R)^4R^2}{(1+L_{\mathrm{in}})^4}\right\}. \tag*{(14)} κ ( R ) = 2 − 28 min { L out err μ ( R ) 3 , ( 1 + L in ) 4 err μ ( R ) 4 R 2 } . (14) For R = 0 R = 0 R = 0 , one may take
κ ( 0 ) = η 3 128 L o u t , η = 1 − ω ( g , μ ) = err μ ( 0 ) . (15) \kappa(0) = \frac{\eta^3}{128L_{\mathrm{out}}}, \qquad\eta= 1-\omega(g,\mu)=\operatorname{err}_{\mu}(0). \tag*{(15)} κ ( 0 ) = 128 L out η 3 , η = 1 − ω ( g , μ ) = err μ ( 0 ) . (15)
Proof overview
To prove Theorem 3.1, we argue by contradiction. Fix a protocol Π n \Pi_n Π n as in the theorem, let p > 0 p > 0 p > 0 be its success probability under μ ⊗ n \mu^{\otimes n} μ ⊗ n , and set t = log ( 1 / p ) / n t = \log(1/p)/n t = log ( 1/ p ) / n . If t t t is too small, we will obtain a protocol for one instance ( g , μ ) (g,\mu) ( g , μ ) with information cost at most R R R and error strictly below err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) . (We also prove err μ ( R ) > 0 \operatorname{err}_{\mu}(R) > 0 err μ ( R ) > 0 whenever R < IC μ ( g , 0 ) R < \operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) .) This contradicts the definition of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) . Hence t t t must be bounded below, yielding an exponential upper bound on p p p . The construction and the explicit lower bound on t t t are given in Sections 4 to 7.
Below a detailed overview is explained section by section. In brief, we extract a single-instance distribution q s i n g l e q_{\mathrm{single}} q single from the n n n -instance protocol Π n \Pi_n Π n and use this distribution to construct a single-instance protocol π s i n g l e \pi_{\mathrm{single}} π single that contradicts the definition of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) .
Conditioning and selecting a coordinate
We first extract from the n n n -instance protocol Π n \Pi_n Π n a joint distribution q q q of a single input pair ( X , Y ) (X,Y) ( X , Y ) , output pair ( A , B ) (A,B) ( A , B ) , and auxiliary variable V V V . The distribution q q q need not arise from a one-instance protocol. Nevertheless, we define its error by q { ( A , B ) ∉ g ( X , Y ) } q\{(A,B) \notin g(X,Y)\} q {( A , B ) ∈ / g ( X , Y )} and consider the expression I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) I_q(X;V \mid Y) + I_q(Y;V \mid X) I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) , using the same formulas as for a protocol distribution.
We need q q q to have four properties: (P.1) its error is at most ε \varepsilon ε ; (P.2) its input marginal q X Y q_{XY} q X Y is close to μ \mu μ ; (P.3) the information expression above is at most R R R plus a vanishing term; and (P.4) its outputs A B AB A B can be sampled locally given V V V and the respective inputs. These properties control the error and information cost of the protocol constructed in Section 5 and the error of the zero-message protocol constructed in Section 6. Section 4 constructs q q q and proves the required properties. Below we explain the construction of q q q and how those four properties are proved in detail.
Construction of q q q . We begin with the probability distribution induced by Π n \Pi_n Π n . Fix its private and public randomness in a way that the resulting deterministic protocol still succeeds on every coordinate with probability at least p p p . Run this protocol on ( X n , Y n ) ∼ μ ⊗ n (X^n,Y^n) \sim\mu^{\otimes n} ( X n , Y n ) ∼ μ ⊗ n , and denote its transcript and the players’ output strings by T T T , A n A^n A n , B n B^n B n . Let P P P be the joint distribution of these variables and the inputs. For the following explanation, for each i ∈ [ n ] i \in[n] i ∈ [ n ] , let W i W_i W i be the event ( A i , B i ) ∈ g ( X i , Y i ) (A_i,B_i) \in g(X_i,Y_i) ( A i , B i ) ∈ g ( X i , Y i ) that Π n \Pi_n Π n succeeds on coordinate i i i . Thus P ( ⋂ i = 1 n W i ) ≥ p P\left(\bigcap_{i=1}^n W_i\right) \ge p P ( ⋂ i = 1 n W i ) ≥ p .
We now construct an event W S W_S W S conditioned on which the protocol Π n \Pi_n Π n succeeds on each coordinate with probability at least 1 − ε 1-\varepsilon 1 − ε . For this purpose, Section 4 chooses a set S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] and defines W S = ⋂ i ∈ S W i W_S = \bigcap_{i \in S} W_i W S = ⋂ i ∈ S W i . The choice ensures the higher probability of success P ( W i ∣ W S ) ≥ 1 − ε P(W_i \mid W_S) \ge1-\varepsilon P ( W i ∣ W S ) ≥ 1 − ε for every i ∈ [ n ] i \in[n] i ∈ [ n ] , as well as
P ( W S ) ≥ p , ∣ S ∣ ≤ log ( 1 / p ) − log ( 1 − ε ) . (16) P(W_S) \ge p,\qquad|S| \le\frac{\log(1/p)}{-\log(1-\varepsilon)}. \tag*{(16)} P ( W S ) ≥ p , ∣ S ∣ ≤ − log ( 1 − ε ) log ( 1/ p ) . (16)
The bound on probability limits the change caused by conditioning; the bound on size is later used to limit the entropy H ( A S , B S ) H(A_S,B_S) H ( A S , B S ) .
Write Q = P ( ⋅ ∣ W S ) Q = P(\mathord{\cdot} \mid W_S) Q = P ( ⋅ ∣ W S ) and construct the distribution q q q as follows. Under Q Q Q , choose J J J uniformly from [ n ] [n] [ n ] , independently of all the other variables, and define
( X , Y , A , B ) = ( X J , Y J , A J , B J ) , V = ( J , X < J , Y > J , T , A S , B S ) . (X,Y,A,B) = (X_J,Y_J,A_J,B_J),\qquad V = (J,X_{<J},Y_{>J},T,A_S,B_S). ( X , Y , A , B ) = ( X J , Y J , A J , B J ) , V = ( J , X < J , Y > J , T , A S , B S ) .
Finally let q q q be the joint distribution of ( X , Y , A , B , V ) (X,Y,A,B,V) ( X , Y , A , B , V ) , defined based on Q Q Q .
The properties (P.1) to (P.4). We now state the four properties precisely. Properties (P.1) and (P.2) proved in Section 4 are
q { ( A , B ) ∉ g ( X , Y ) } ≤ ε , D ( q X Y ∥ μ ) ≤ t . (17) q\{(A,B) \notin g(X,Y)\} \le\varepsilon,\qquad D(q_{XY}\Vert\mu) \le t. \tag*{(17)} q {( A , B ) ∈ / g ( X , Y )} ≤ ε , D ( q X Y ∥ μ ) ≤ t . (17)
The error bound follows by averaging the conditional success probabilities Q ( W i ) Q(W_i) Q ( W i ) over i i i . The divergence bound, proved in Section 4, controls the change from the input marginal q X Y q_{XY} q X Y to the original distribution μ \mu μ in the subsequent protocol constructions.
Formally the property (P.3) bounds the sum of conditional mutual informations:
I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + t ( 2 + L o u t − log ( 1 − ε ) ) . (18) I_q(X;V \mid Y) + I_q(Y;V \mid X) \le R + t\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right). \tag*{(18)} I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + t ( 2 + − log ( 1 − ε ) L out ) . (18)
As shown in Section 4, this bound follows from the bound for the communication cost ∣ Π n ∣ |\Pi_n| ∣ Π n ∣ , the cost of conditioning on W S W_S W S , and the entropy H ( A S , B S ) . H(A_S,B_S). H ( A S , B S ) . It will bound the information cost of the protocol π \pi π constructed in Section 5 and the sampling error of the zero-message protocol in Section 6.
The property (P.4) indicates local output sampling. For every ( x , y , v ) (x,y,v) ( x , y , v ) with q ( x , y , v ) > 0 q(x,y,v)>0 q ( x , y , v ) > 0 , Section 4 proves
q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) . (19) q(a,b \mid x,y,v) = q(a \mid x,v)q(b \mid y,v). \tag*{(19)} q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) . (19)
The variables retained in V V V make this factorization valid even after conditioning on W S W_S W S . Consequently, Alice can sample from q ( A ∣ x , v ) q(A \mid x,v) q ( A ∣ x , v ) and Bob can independently sample from q ( B ∣ y , v ) q(B \mid y,v) q ( B ∣ y , v ) .
We next need a protocol on an input pair drawn from μ \mu μ whose distribution is close to q q q . Conditioning on W S W_S W S depends on both players’ inputs, so q q q itself need not have a valid protocol transcript. Overcoming this issue, Section 5 constructs a protocol π \pi π on a new input pair ( x , y ) ∼ μ (x,y) \sim\mu ( x , y ) ∼ μ by sampling each message from the appropriate conditional distribution of q q q in the following manner:
The parties publicly choose J = i J=i J = i and sample X < i X_{<i} X < i from q ( X < i ∣ J = i ) q(X_{<i} \mid J=i) q ( X < i ∣ J = i ) , independently of ( x , y ) (x,y) ( x , y ) .
Alice samples Y > i Y_{>i} Y > i from q ( Y > i ∣ X = x , X < i , J = i ) q(Y_{>i} \mid X=x, X_{<i}, J=i) q ( Y > i ∣ X = x , X < i , J = i ) and sends it to Bob.
They then send the messages of T T T , followed by the auxiliary outputs A S , B S A_S,B_S A S , B S , using the conditional distributions of q q q : each sender uses their own input and the preceding messages.
Finally, they sample their outputs separately using the distributions on the right-hand side of (19) .
The central comparison proven in Section 5 is that the joint distribution P π P_\pi P π of ( X , Y , A , B , V ) (X,Y,A,B,V) ( X , Y , A , B , V ) generated by π \pi π satisfies D ( q ∥ P π ) ≤ t D(q\mathbin\Vert P_\pi) \le t D ( q ∥ P π ) ≤ t , even though the input distribution for π \pi π is μ \mu μ . When δ = ( ln 2 ) t / 2 ≤ 1 / 2 \delta= \sqrt{(\ln2)t/2} \le1/2 δ = ( ln 2 ) t /2 ≤ 1/2 , Pinsker’s inequality then bounds the total variation distance between q q q and P π P_\pi P π by δ \delta δ . Thus the error bound for q q q in (17) transfers to π \pi π , while continuity of conditional entropy transfers the information bound in (18) . Explicitly,
err μ ( π ) ≤ ε + δ , IC μ ( π ) ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L i n δ + 4 h ( δ ) . (20) \begin{aligned}
\operatorname{err}_{\mu}(\pi) &\le\varepsilon+\delta,\\
\operatorname{IC}_{\mu}(\pi) &\le I_q(X;V\mid Y)+I_q(Y;V\mid X)+2L_{\mathrm{in}}\delta+4h(\delta). \tag*{(20)}
\end{aligned} err μ ( π ) IC μ ( π ) ≤ ε + δ , ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L in δ + 4 h ( δ ) . (20)
Thus π \pi π has error at most ε + δ \varepsilon+\delta ε + δ and information cost at most R R R plus terms tending to zero as t → 0 t\to0 t → 0 . However, the definition of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) strictly requires information cost at most R R R , so this bound (20) on IC μ ( π ) \operatorname{IC}_{\mu}(\pi) IC μ ( π ) alone does not yield the desired contradiction.
A zero-message protocol (Section 6)
We next construct a zero-message protocol σ \sigma σ , which trivially has information cost zero. Using the zero-information protocol, a public mixture of π \pi π and σ \sigma σ will reduce any excess information cost to meet the budget R R R for R > 0 R>0 R > 0 . For R = 0 R=0 R = 0 , we use σ \sigma σ alone. Section 6 constructs such a protocol σ \sigma σ . The core idea of the construction is that on input ( x , y ) (x,y) ( x , y ) , Alice and Bob use shared randomness to obtain correlated samples V A , V B V_A,V_B V A , V B from q ( V ∣ x ) q(V\mid x) q ( V ∣ x ) and q ( V ∣ y ) q(V\mid y) q ( V ∣ y ) , respectively, without sending messages. Each player then uses the sampled value and their own input to produce an output.
For the error analysis, we consider a sample V ∗ V_* V ∗ from q ( V ∣ x , y ) q(V\mid x,y) q ( V ∣ x , y ) , which the players do not need to compute. Hypothetical outputs using this third sample V ∗ V_* V ∗ have the conditional distribution q ( A , B ∣ x , y ) q(A,B\mid x,y) q ( A , B ∣ x , y ) by the local output condition (19) . Therefore the parties output correctly following the distribution q q q whenever V A = V B = V ∗ V_A=V_B=V_* V A = V B = V ∗ .
We then analyze the error probability of σ \sigma σ . Section 6 bounds the error probability using the two conditional mutual informations in (18) . An intermediate step gives an error bound under inputs drawn from q X Y q_{XY} q X Y . To transfer this to an error bound on μ \mu μ , we apply the input-distribution bound in (17) giving TV ( q X Y , μ ) ≤ δ \operatorname{TV}(q_{XY},\mu)\le\delta TV ( q X Y , μ ) ≤ δ . The resulting bound is
err μ ( σ ) ≤ ε + δ + 2 ( ln 2 ) [ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ] , IC μ ( σ ) = 0. (21) \operatorname{err}_{\mu}(\sigma)\le\varepsilon+\delta+2\sqrt{(\ln2)\left[I_q(X;V\mid Y)+I_q(Y;V\mid X)\right]},\qquad\operatorname{IC}_{\mu}(\sigma)=0. \tag*{(21)} err μ ( σ ) ≤ ε + δ + 2 ( ln 2 ) [ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ] , IC μ ( σ ) = 0. (21)
Completing the contradiction (Section 7)
We now combine the two protocols π \pi π , σ \sigma σ to obtain information cost at most R R R without losing the small-error guarantee when t t t is small. Section 7 gives the combination as follows. If C = IC μ ( π ) ≤ R C = \operatorname{IC}_{\mu}(\pi) \le R C = IC μ ( π ) ≤ R , use π \pi π . If C > R > 0 C > R > 0 C > R > 0 , use a public coin to run π \pi π with probability R / C R/C R / C and σ \sigma σ otherwise. The mixed protocol has information cost R R R . Regarding the error bound, by (18) and the information-cost inequality in (20) , C − R C-R C − R is at most a sum of terms tending to zero with t t t . Hence the probability 1 − R / C ≤ ( C − R ) / R 1-R/C \le(C-R)/R 1 − R / C ≤ ( C − R ) / R of using σ \sigma σ also tends to zero as t → 0 t \to0 t → 0 . Therefore the error of the mixed protocol approaches at most ε \varepsilon ε : the error of π \pi π is at most ε + δ = ε + o ( 1 ) \varepsilon+\delta= \varepsilon+o(1) ε + δ = ε + o ( 1 ) as t → 0 t \to0 t → 0 , and the probability of using σ \sigma σ tends to zero. (If R = 0 R = 0 R = 0 , use σ \sigma σ alone and apply (21) .) In either case, sufficiently small t t t would give information cost at most R R R and error below err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) by choosing sufficiently small ε \varepsilon ε . Section 7 also chooses the parameters explicitly to obtain the exponents in Theorem 3.1.
Consequences (Section 8)
Finally, Section 8 combines our main result with communication upper bounds to determine the asymptotic distributional communication rate. It then uses the zero-error minimax identity to derive the corresponding strong converse and asymptotic rate on randomized communication complexity.
Conditioning and selecting a coordinate
Throughout Section 4, fix a protocol Π n \Pi_n Π n for g n g^n g n that communicates at most n R nR n R bits and succeeds on μ ⊗ n \mu^{\otimes n} μ ⊗ n with probability at least p > 0 p > 0 p > 0 . By fixing its public and private randomness, we may assume that Π n \Pi_n Π n is deterministic while preserving these two bounds.
For each 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 , we construct a distribution q ( X , Y , A , B , V ) q(X,Y,A,B,V) q ( X , Y , A , B , V ) by conditioning on success on the coordinates in S S S and choosing a coordinate J ∈ [ n ] J \in[n] J ∈ [ n ] uniformly, formally given in Construction 4.1. We show that its error q { ( A , B ) ∉ g ( X , Y ) } q\{(A,B) \notin g(X,Y)\} q {( A , B ) ∈ / g ( X , Y )} is at most ε \varepsilon ε and that it satisfies the following bounds:
D ( q X Y ∥ μ ) ≤ log ( 1 / p ) n , (22) D(q_{XY}\mathbin\Vert\mu) \le\frac{\log(1/p)}{n}, \tag*{(22)} D ( q X Y ∥ μ ) ≤ n log ( 1/ p ) , (22)
I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + log ( 1 / p ) n ( 2 + L o u t − log ( 1 − ε ) ) , (23) I_q(X;V \mid Y) + I_q(Y;V \mid X) \le R + \frac{\log(1/p)}{n}\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right), \tag*{(23)} I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + n log ( 1/ p ) ( 2 + − log ( 1 − ε ) L out ) , (23)
q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) . (24) q(a,b \mid x,y,v)=q(a \mid x,v)q(b \mid y,v). \tag*{(24)} q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) . (24)
The distribution q q q need not arise from a protocol on a single input pair: V V V may not be a transcript generated from ( X , Y ) (X,Y) ( X , Y ) .
The following construction fixes the variables used throughout this section.
Construction 4.1 (Definition of q q q ). Run the fixed deterministic protocol Π n \Pi_n Π n on ( X n , Y n ) ∼ μ ⊗ n (X^n,Y^n) \sim\mu^{\otimes n} ( X n , Y n ) ∼ μ ⊗ n . Write T T T for its transcript and A n , B n A^n,B^n A n , B n for its outputs, and let P P P be their joint distribution with X n , Y n X^n,Y^n X n , Y n . For i ∈ [ n ] i \in[n] i ∈ [ n ] and S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] , define
W i = { ( A i , B i ) ∈ g ( X i , Y i ) } , W S = ⋂ i ∈ S W i . W_i=\{(A_i,B_i)\in g(X_i,Y_i)\}, \qquad W_S=\bigcap_{i\in S}W_i. W i = {( A i , B i ) ∈ g ( X i , Y i )} , W S = i ∈ S ⋂ W i .
Next take a set S ⊆ [ n ] S \subseteq[n] S ⊆ [ n ] such that
∣ S ∣ ≤ log ( 1 / p ) − log ( 1 − ε ) , P ( W S ) ≥ p , P ( W i ∣ W S ) ≥ 1 − ε ( i ∈ [ n ] ) |S| \le\frac{\log(1/p)}{-\log(1-\varepsilon)}, \qquad P(W_S)\ge p, \qquad P(W_i\mid W_S)\ge1-\varepsilon\quad(i\in[n]) ∣ S ∣ ≤ − log ( 1 − ε ) log ( 1/ p ) , P ( W S ) ≥ p , P ( W i ∣ W S ) ≥ 1 − ε ( i ∈ [ n ])
Its existence is shown in Lemma 4.1. Fix such a set S S S , put T ‾ = ( T , A S , B S ) \overline{T}=(T,A_S,B_S) T = ( T , A S , B S ) , and let Q = P ( ⋅ ∣ W S ) Q=P(\cdot\mid W_S) Q = P ( ⋅ ∣ W S ) . Choose J J J uniformly from [ n ] [n] [ n ] , independently of the variables under Q Q Q . We define q ( X , Y , A , B , V ) q(X,Y,A,B,V) q ( X , Y , A , B , V ) as the distribution of
X = X J , Y = Y J , A = A J , B = B J , V = ( J , X < J , Y > J , T ‾ ) . (25) \begin{aligned}
X&=X_J, & Y&=Y_J,\\
A&=A_J, & B&=B_J,\\
V&=(J,X_{<J},Y_{>J},\overline{T}). \tag*{(25)}
\end{aligned} X A V = X J , = A J , = ( J , X < J , Y > J , T ) . Y B = Y J , = B J , (25)
The variables on the right-hand side are sampled under Q Q Q .
We first justify the choice of S S S and prove the bounds needed under Q Q Q , including a factorization of probability similar to (24) . We then derive the displayed properties of q q q .
Conditioning on successful coordinates
Lemma 4.1 proves bounds on the size of S S S and the probability Pr ( W S ) \Pr(W_S) Pr ( W S ) while ensuring high conditional success in every coordinate.
Lemma 4.1. Let W 1 , … , W n W_1,\ldots,W_n W 1 , … , W n be the events in Construction 4.1. For every 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 , there is a subset S ⊆ [ n ] S\subseteq[n] S ⊆ [ n ] such that,
∣ S ∣ ≤ log ( 1 / p ) − log ( 1 − ε ) , Pr ( W S ) ≥ p , Pr ( W i ∣ W S ) ≥ 1 − ε ( i ∈ [ n ] ) . (26) |S|\le\frac{\log(1/p)}{-\log(1-\varepsilon)},\qquad\Pr(W_S)\ge p,\qquad\Pr(W_i\mid W_S)\ge1-\varepsilon\quad(i\in[n]). \tag*{(26)} ∣ S ∣ ≤ − log ( 1 − ε ) log ( 1/ p ) , Pr ( W S ) ≥ p , Pr ( W i ∣ W S ) ≥ 1 − ε ( i ∈ [ n ]) . (26)
Proof. Start with S = ∅ S=\varnothing S = ∅ . Whenever an index i ∉ S i\notin S i ∈ / S has Pr ( W i ∣ W S ) < 1 − ε \Pr(W_i\mid W_S)<1-\varepsilon Pr ( W i ∣ W S ) < 1 − ε , add it to S S S . At termination, every coordinate satisfies the conditional success bound in (26) . Throughout this procedure, W S W_S W S contains ⋂ i W i \bigcap_i W_i ⋂ i W i , so Pr ( W S ) ≥ p \Pr(W_S)\ge p Pr ( W S ) ≥ p .
For the upper bound on ∣ S ∣ |S| ∣ S ∣ , each addition multiplies Pr ( W S ) \Pr(W_S) Pr ( W S ) by a factor less than 1 − ε 1-\varepsilon 1 − ε :
Pr ( W S ∩ W i ) = Pr ( W i ∣ W S ) Pr ( W S ) < ( 1 − ε ) Pr ( W S ) . \Pr(W_S\cap W_i)=\Pr(W_i\mid W_S)\Pr(W_S)<(1-\varepsilon)\Pr(W_S). Pr ( W S ∩ W i ) = Pr ( W i ∣ W S ) Pr ( W S ) < ( 1 − ε ) Pr ( W S ) .
Since W S W_S W S always contains ⋂ i ≤ n W i \bigcap_{i\le n}W_i ⋂ i ≤ n W i , when the procedure terminates, we have
p ≤ Pr ( W S ) ≤ ( 1 − ε ) ∣ S ∣ . p\le\Pr(W_S)\le(1-\varepsilon)^{|S|}. p ≤ Pr ( W S ) ≤ ( 1 − ε ) ∣ S ∣ .
Rearranging gives the bound on ∣ S ∣ |S| ∣ S ∣ . □ \square □
The bounds on information quantities. For the set S S S fixed in Construction 4.1, we have Q ( W i ) = P ( W i ∣ W S ) ≥ 1 − ε Q(W_i)=P(W_i\mid W_S)\ge1-\varepsilon Q ( W i ) = P ( W i ∣ W S ) ≥ 1 − ε for every i i i . Let ν = Q X n Y n \nu=Q_{X^nY^n} ν = Q X n Y n . Since the protocol is deterministic, W S W_S W S and all transcript and output variables are determined by ( X n , Y n ) (X^n,Y^n) ( X n , Y n ) . Thus P P P and Q Q Q have the same conditional distribution of these variables given the inputs, and ν \nu ν is μ ⊗ n \mu^{\otimes n} μ ⊗ n conditioned on W S W_S W S . Consequently,
D ( Q ∥ P ) = D ( ν ∥ μ ⊗ n ) = log 1 P ( W S ) ≤ log 1 p . (27) D(Q\mathbin{\|}P)=D(\nu\mathbin{\|}\mu^{\otimes n})=\log\frac{1}{P(W_S)}\le\log\frac{1}{p}. \tag*{(27)} D ( Q ∥ P ) = D ( ν ∥ μ ⊗ n ) = log P ( W S ) 1 ≤ log p 1 . (27)
The original deterministic protocol has worst-case cost at most n R nR n R even when the inputs follow ν \nu ν . Therefore Proposition 2.5 shows that its information cost under the input distribution Q X n Y n Q_{X^nY^n} Q X n Y n is also at most n R nR n R . Appending A S A_S A S and B S B_S B S to T T T , yielding T ‾ = ( A S , B S , T ) \overline{T}=(A_S,B_S,T) T = ( A S , B S , T ) , contributes at most their combined alphabet entropy, which is at most ∣ S ∣ L o u t |S|L_{\mathrm{out}} ∣ S ∣ L out . Hence
I Q ( X n ; T ‾ ∣ Y n ) + I Q ( Y n ; T ‾ ∣ X n ) ≤ n R + ∣ S ∣ L o u t . (28) I_Q(X^n;\overline{T}\mid Y^n)+I_Q(Y^n;\overline{T}\mid X^n)\le nR+|S|L_{\mathrm{out}}. \tag*{(28)} I Q ( X n ; T ∣ Y n ) + I Q ( Y n ; T ∣ X n ) ≤ n R + ∣ S ∣ L out . (28)
Locality of outputs after conditioning. The event W S W_S W S depends on both players’ inputs, so conditioning on it might appear to destroy the locality of their outputs; the output A A A may depend on Bob’s input Y Y Y for example. For coordinate i i i , reveal the selected outputs together with X < i X_{<i} X < i and Y > i Y_{>i} Y > i , and put V i = ( X < i , Y > i , T ‾ ) V_i=(X_{<i},Y_{>i},\overline{T}) V i = ( X < i , Y > i , T ) . Alice’s remaining input is X > i X_{>i} X > i and Bob’s is Y < i Y_{<i} Y < i . The next lemma shows that these parts are conditionally independent in the form needed for the coordinate outputs.
Lemma 4.2. For every i ∈ [ n ] i\in[n] i ∈ [ n ] , the distribution Q Q Q of Construction 4.1 satisfies
Q ( A i , B i ∣ X i , Y i , V i ) = Q ( A i ∣ X i , V i ) Q ( B i ∣ Y i , V i ) (29) Q(A_i,B_i\mid X_i,Y_i,V_i)=Q(A_i\mid X_i,V_i)Q(B_i\mid Y_i,V_i) \tag*{(29)} Q ( A i , B i ∣ X i , Y i , V i ) = Q ( A i ∣ X i , V i ) Q ( B i ∣ Y i , V i ) (29) at every conditioning value of positive Q Q Q -probability.
Proof. If i ∈ S i\in S i ∈ S , then A i A_i A i and B i B_i B i are already determined by V i V_i V i , and the identity follows. Suppose i ∉ S i\notin S i ∈ / S , and fix ( X i , Y i , V i ) = ( x , y , v i ) (X_i,Y_i,V_i)=(x,y,v_i) ( X i , Y i , V i ) = ( x , y , v i ) with positive Q Q Q -probability, where v i = ( x < i , y > i , t ˉ ) v_i=(x_{<i},y_{>i},\bar{t}) v i = ( x < i , y > i , t ˉ ) . The selected outputs A S , B S A_S,B_S A S , B S in t ˉ \bar{t} t ˉ can be viewed as additional messages sent after T T T . For each fixed t ˉ \bar{t} t ˉ , let C A ( t ˉ ) ⊆ X n C_A(\bar{t})\subseteq\mathcal{X}^n C A ( t ˉ ) ⊆ X n be the Alice inputs consistent with her messages and selected outputs, and let C B ( t ˉ ) ⊆ Y n C_B(\bar{t})\subseteq\mathcal{Y}^n C B ( t ˉ ) ⊆ Y n be the analogous Bob inputs. The rectangle property of the deterministic transcript gives
P ( x n , y n , t ˉ ) = μ ⊗ n ( x n , y n ) 1 { x n ∈ C A ( t ˉ ) } 1 { y n ∈ C B ( t ˉ ) } . (30) P(x^n,y^n,\bar{t})=\mu^{\otimes n}(x^n,y^n)1\{x^n\in C_A(\bar{t})\}1\{y^n\in C_B(\bar{t})\}. \tag*{(30)} P ( x n , y n , t ˉ ) = μ ⊗ n ( x n , y n ) 1 { x n ∈ C A ( t ˉ )} 1 { y n ∈ C B ( t ˉ )} . (30)
Write ( a s , b s ) s ∈ S (a_s,b_s)_{s\in S} ( a s , b s ) s ∈ S for the outputs recorded in t ˉ \bar{t} t ˉ . For a possible suffix x > i x_{>i} x > i and prefix y < i y_{<i} y < i , define
F x , v i ( x > i ) = 1 { ( x < i , x , x > i ) ∈ C A ( t ˉ ) } ∏ j > i μ ( x j , y j ) ∏ s ∈ S s > i 1 { ( a s , b s ) ∈ g ( x s , y s ) } , F_{x,v_i}(x_{>i})=1\{(x_{<i},x,x_{>i})\in C_A(\bar{t})\}\prod_{j>i}\mu(x_j,y_j)\prod_{\substack{s\in S\\s>i}}1\{(a_s,b_s)\in g(x_s,y_s)\}, F x , v i ( x > i ) = 1 {( x < i , x , x > i ) ∈ C A ( t ˉ )} j > i ∏ μ ( x j , y j ) s ∈ S s > i ∏ 1 {( a s , b s ) ∈ g ( x s , y s )} ,
G y , v i ( y < i ) = 1 { ( y < i , y , y > i ) ∈ C B ( t ˉ ) } ∏ j < i μ ( x j , y j ) ∏ s ∈ S s < i 1 { ( a s , b s ) ∈ g ( x s , y s ) } . G_{y,v_i}(y_{<i})=1\{(y_{<i},y,y_{>i})\in C_B(\bar{t})\}\prod_{j<i}\mu(x_j,y_j)\prod_{\substack{s\in S\\s<i}}1\{(a_s,b_s)\in g(x_s,y_s)\}. G y , v i ( y < i ) = 1 {( y < i , y , y > i ) ∈ C B ( t ˉ )} j < i ∏ μ ( x j , y j ) s ∈ S s < i ∏ 1 {( a s , b s ) ∈ g ( x s , y s )} .
All y j y_j y j in F x , v i F_{x,v_i} F x , v i and all x j x_j x j in G y , v i G_{y,v_i} G y , v i are fixed by v i v_i v i . Because i ∉ S i\notin S i ∈ / S , no success indicator involves both x x x and y y y . In particular, F x , v i F_{x,v_i} F x , v i does not depend on y y y , and G y , v i G_{y,v_i} G y , v i does not depend on x x x .
The product form of μ ⊗ n \mu^{\otimes n} μ ⊗ n , the rectangle identity (30), and the definition of W S W_S W S now give
P ( X > i = x > i , Y < i = y < i , X i = x , Y i = y , V i = v i , W S ) = μ ( x , y ) F x , v i ( x > i ) G y , v i ( y < i ) . \begin{aligned}
P(X_{>i}=x_{>i},Y_{<i}=y_{<i},X_i=x,Y_i=y,V_i=v_i,W_S)
&=\mu(x,y)F_{x,v_i}(x_{>i})G_{y,v_i}(y_{<i}).
\end{aligned} P ( X > i = x > i , Y < i = y < i , X i = x , Y i = y , V i = v i , W S ) = μ ( x , y ) F x , v i ( x > i ) G y , v i ( y < i ) .
The fixed value ( x , y , v i ) (x,y,v_i) ( x , y , v i ) has positive Q Q Q -probability, so the two sums below are positive. Normalizing the displayed product yields
Q ( x > i , y < i ∣ x , y , v i ) = F x , v i ( x > i ) ∑ x > i ′ F x , v i ( x > i ′ ) G y , v i ( y < i ) ∑ y < i ′ G y , v i ( y < i ′ ) . (31) Q(x_{>i},y_{<i}\mid x,y,v_i)=
\frac{F_{x,v_i}(x_{>i})}{\sum_{x'_{>i}}F_{x,v_i}(x'_{>i})}
\frac{G_{y,v_i}(y_{<i})}{\sum_{y'_{<i}}G_{y,v_i}(y'_{<i})}. \tag*{(31)} Q ( x > i , y < i ∣ x , y , v i ) = ∑ x > i ′ F x , v i ( x > i ′ ) F x , v i ( x > i ) ∑ y < i ′ G y , v i ( y < i ′ ) G y , v i ( y < i ) . (31)
The first factor is independent of y y y . Marginalizing over Y < i Y_{<i} Y < i , then averaging over Y i Y_i Y i conditional on ( X i , V i ) (X_i,V_i) ( X i , V i ) , identifies that factor with Q ( x > i ∣ x , v i ) Q(x_{>i}\mid x,v_i) Q ( x > i ∣ x , v i ) . Similarly, the second factor is Q ( y < i ∣ y , v i ) Q(y_{<i}\mid y,v_i) Q ( y < i ∣ y , v i ) . Thus
Q ( x > i , y < i ∣ x , y , v i ) = Q ( x > i ∣ x , v i ) Q ( y < i ∣ y , v i ) . Q(x_{>i},y_{<i}\mid x,y,v_i)=Q(x_{>i}\mid x,v_i)Q(y_{<i}\mid y,v_i). Q ( x > i , y < i ∣ x , y , v i ) = Q ( x > i ∣ x , v i ) Q ( y < i ∣ y , v i ) .
Given ( x , y , v i ) (x,y,v_i) ( x , y , v i ) , Alice’s output A i A_i A i depends only on x > i x_{>i} x > i , and Bob’s output B i B_i B i depends only on y < i y_{<i} y < i . Applying their output functions to this product distribution proves (29).
:::
The conditioned coordinate distribution
We now verify the properties of the distribution q q q in Construction 4.1. Write err ( q ) = q { ( A , B ) ≠ g ( X , Y ) } \operatorname{err}(q)=q\{(A,B)\ne g(X,Y)\} err ( q ) = q {( A , B ) = g ( X , Y )} .
Lemma 4.3. The distribution q q q of Construction 4.1 satisfies err ( q ) ≤ ε \operatorname{err}(q)\le\varepsilon err ( q ) ≤ ε and {(22)}–{(24)}.
Proof. We first prove err ( q ) ≤ ε \operatorname{err}(q)\le\varepsilon err ( q ) ≤ ε and {(24)}, and then establish {(23)} and {(22)}.
Error and output locality. By Construction 4.1, Q ( W i ) ≥ 1 − ε Q(W_i)\ge1-\varepsilon Q ( W i ) ≥ 1 − ε for every i i i . Since J J J is uniform, the success probability under q q q is n − 1 ∑ i Q ( W i ) n^{-1}\sum_i Q(W_i) n − 1 ∑ i Q ( W i ) ; hence err ( q ) ≤ ε \operatorname{err}(q)\le\varepsilon err ( q ) ≤ ε . For each fixed J = i J=i J = i , the factorization {(29)} under Q Q Q applies with V i = ( X < i , Y > i , T ‾ ) V_i=(X_{<i},Y_{>i},\overline{T}) V i = ( X < i , Y > i , T ) . Since Construction 4.1 implies
Q ( A i = a , B i = b ∣ X i = x , Y i = y , V i = v ) = q ( a , b ∣ x , y , V = ( J = i , v ) ) , Q(A_i=a,B_i=b\mid X_i=x,Y_i=y,V_i=v)=q(a,b\mid x,y,V=(J=i,v)), Q ( A i = a , B i = b ∣ X i = x , Y i = y , V i = v ) = q ( a , b ∣ x , y , V = ( J = i , v )) ,
the factorization under Q Q Q yields the factorization {(24)} under q q q as desired.
Information bound. Our intermediate goal is
n I q ( X ; V ∣ Y ) ≤ I Q ( X n ; T ‾ ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) . (32) nI_q(X;V\mid Y)\le I_Q(X^n;\overline{T}\mid Y^n)+D(Q_{X^nY^n}\Vert\mu^{\otimes n}). \tag*{(32)} n I q ( X ; V ∣ Y ) ≤ I Q ( X n ; T ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) . (32)
For this purpose, we will now bound each term in n I q ( X ; V ∣ Y ) = n H q ( X ∣ Y ) − n H q ( X ∣ V , Y ) nI_q(X;V\mid Y)=nH_q(X\mid Y)-nH_q(X\mid V,Y) n I q ( X ; V ∣ Y ) = n H q ( X ∣ Y ) − n H q ( X ∣ V , Y ) separately; we first upper-bound n H q ( X ∣ Y ) nH_q(X\mid Y) n H q ( X ∣ Y ) and then lower-bound n H q ( X ∣ Y , V ) nH_q(X\mid Y,V) n H q ( X ∣ Y , V ) .
Nonnegativity of conditional relative entropy
0 ≤ E q Y D ( q X ∣ Y ∥ μ X ∣ Y ) = E q [ − log μ ( X ∣ Y ) ] − H q ( X ∣ Y ) 0\le\mathbb{E}_{q_Y}D(q_{X\mid Y}\Vert\mu_{X\mid Y})=\mathbb{E}_q[-\log\mu(X\mid Y)]-H_q(X\mid Y) 0 ≤ E q Y D ( q X ∣ Y ∥ μ X ∣ Y ) = E q [ − log μ ( X ∣ Y )] − H q ( X ∣ Y )
and the equality q X Y = E J [ Q X J Y J ] q_{XY}=\mathbb{E}_J[Q_{X_JY_J}] q X Y = E J [ Q X J Y J ] give
n H q ( X ∣ Y ) ≤ n ⋅ E q [ − log μ ( X ∣ Y ) ] = ∑ i E Q [ − log μ ( X i ∣ Y i ) ] = E Q [ − log μ ⊗ n ( X n ∣ Y n ) ] . \begin{aligned}
nH_q(X\mid Y)&\le n\cdot\mathbb{E}_q[-\log\mu(X\mid Y)]\\
&=\sum_i\mathbb{E}_Q[-\log\mu(X_i\mid Y_i)]\\
&=\mathbb{E}_Q[-\log\mu^{\otimes n}(X^n\mid Y^n)].
\end{aligned} n H q ( X ∣ Y ) ≤ n ⋅ E q [ − log μ ( X ∣ Y )] = i ∑ E Q [ − log μ ( X i ∣ Y i )] = E Q [ − log μ ⊗ n ( X n ∣ Y n )] .
On the other hand, H ( X ∣ Y Z ) ≤ H ( X ∣ Y ) H(X\mid YZ)\le H(X\mid Y) H ( X ∣ Y Z ) ≤ H ( X ∣ Y ) holds for any random variables X , Y , Z X,Y,Z X , Y , Z . Therefore decomposing V = ( J , X < i , Y > i , T ‾ ) V=(J,X_{<i},Y_{>i},\overline{T}) V = ( J , X < i , Y > i , T ) and the chain rule conditioned on J = i J=i J = i give
n H q ( X ∣ Y , V ) = ∑ i H Q ( X i ∣ X < i , Y i , Y > i , T ‾ ) ≥ ∑ i H Q ( X i ∣ X < i , Y < i Y i , Y > i , T ‾ ) = H Q ( X n ∣ Y n , T ‾ ) . \begin{aligned}
nH_q(X\mid Y,V)&=\sum_i H_Q(X_i\mid X_{<i},Y_i,Y_{>i},\overline{T})\\
&\ge\sum_i H_Q(X_i\mid X_{<i},Y_{<i}Y_i,Y_{>i},\overline{T})\\
&=H_Q(X^n\mid Y^n,\overline{T}).
\end{aligned} n H q ( X ∣ Y , V ) = i ∑ H Q ( X i ∣ X < i , Y i , Y > i , T ) ≥ i ∑ H Q ( X i ∣ X < i , Y < i Y i , Y > i , T ) = H Q ( X n ∣ Y n , T ) .
Subtracting these bounds and applying the relative entropy chain rule of Fact 2.1 yields
n I q ( X ; V ∣ Y ) = n [ H q ( X ∣ Y ) − H q ( X ∣ V , Y ) ] ≤ E Q [ − log μ ⊗ n ( X n ∣ Y n ) ] − H Q ( X n ∣ Y n , T ‾ ) = ( H Q ( X n ∣ Y n ) − H Q ( X n ∣ Y n , T ‾ ) ) − ( H Q ( X n ∣ Y n ) − E Q [ − log μ ⊗ n ( X n ∣ Y n ) ] ) = I Q ( X n ; T ‾ ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) − D ( Q Y n ∥ μ Y ⊗ n ) ≤ I Q ( X n ; T ‾ ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) . \begin{aligned}
nI_q(X;V\mid Y)&=n\left[H_q(X\mid Y)-H_q(X\mid V,Y)\right]\\
&\le\mathbb{E}_Q[-\log\mu^{\otimes n}(X^n\mid Y^n)]-H_Q(X^n\mid Y^n,\overline{T})\\
&=\left(H_Q(X^n\mid Y^n)-H_Q(X^n\mid Y^n,\overline{T})\right)\\
&\quad-\left(H_Q(X^n\mid Y^n)-\mathbb{E}_Q[-\log\mu^{\otimes n}(X^n\mid Y^n)]\right)\\
&=I_Q(X^n;\overline{T}\mid Y^n)+D(Q_{X^nY^n}\Vert\mu^{\otimes n})-D(Q_{Y^n}\Vert\mu_Y^{\otimes n})\\
&\le I_Q(X^n;\overline{T}\mid Y^n)+D(Q_{X^nY^n}\Vert\mu^{\otimes n}).
\end{aligned} n I q ( X ; V ∣ Y ) = n [ H q ( X ∣ Y ) − H q ( X ∣ V , Y ) ] ≤ E Q [ − log μ ⊗ n ( X n ∣ Y n )] − H Q ( X n ∣ Y n , T ) = ( H Q ( X n ∣ Y n ) − H Q ( X n ∣ Y n , T ) ) − ( H Q ( X n ∣ Y n ) − E Q [ − log μ ⊗ n ( X n ∣ Y n )] ) = I Q ( X n ; T ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) − D ( Q Y n ∥ μ Y ⊗ n ) ≤ I Q ( X n ; T ∣ Y n ) + D ( Q X n Y n ∥ μ ⊗ n ) .
as desired in (32) .
Interchanging X X X and Y Y Y similarly gives
n I q ( Y ; V ∣ X ) ≤ I Q ( Y n ; T ‾ ∣ X n ) + D ( Q X n Y n ∥ μ ⊗ n ) . nI_q(Y;V\mid X)\le I_Q(Y^n;\overline{T}\mid X^n)+D(Q_{X^nY^n}\mathbin\Vert\mu^{\otimes n}). n I q ( Y ; V ∣ X ) ≤ I Q ( Y n ; T ∣ X n ) + D ( Q X n Y n ∥ μ ⊗ n ) .
Therefore, the divergence bound (27) and the information bound (28) on T T T imply
n [ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ] ≤ n R + ∣ S ∣ L o u t + 2 log 1 p . n\left[I_q(X;V\mid Y)+I_q(Y;V\mid X)\right]\le nR+|S|L_{\mathrm{out}}+2\log\frac{1}{p}. n [ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ] ≤ n R + ∣ S ∣ L out + 2 log p 1 .
The bound on ∣ S ∣ |S| ∣ S ∣ in Construction 4.1 proves the desired information bound (23) .
Input marginal. Apply the relative entropy chain rule of Fact 2.1 successively to the coordinate pairs ( X i , Y i ) (X_i,Y_i) ( X i , Y i ) . Since the joint distribution μ ⊗ n \mu^{\otimes n} μ ⊗ n is a product, the conditional distribution μ ( X i Y i ∣ X < i Y < i ) \mu(X_iY_i\mid X_{<i}Y_{<i}) μ ( X i Y i ∣ X < i Y < i ) at each step is μ \mu μ . Thus
D ( Q X n Y n ∥ μ ⊗ n ) = ∑ i = 1 n E Q X < i Y < i D ( Q X i Y i ∣ X < i Y < i ∥ μ ) . D(Q_{X^nY^n}\mathbin\Vert\mu^{\otimes n})=\sum_{i=1}^{n}\mathbb{E}_{Q_{X_{<i}Y_{<i}}}D(Q_{X_iY_i\mid X_{<i}Y_{<i}}\mathbin\Vert\mu). D ( Q X n Y n ∥ μ ⊗ n ) = i = 1 ∑ n E Q X < i Y < i D ( Q X i Y i ∣ X < i Y < i ∥ μ ) .
For i = 1 i=1 i = 1 , the prefix is empty and the summand is D ( Q X 1 Y 1 ∥ μ ) D(Q_{X_1Y_1}\mathbin\Vert\mu) D ( Q X 1 Y 1 ∥ μ ) . For each i i i , splitting the logarithm inside the conditional divergence gives
E Q X < i Y < i D ( Q X i Y i ∣ X < i Y < i ∥ μ ) = E Q [ log Q ( X i , Y i ∣ X < i , Y < i ) Q X i Y i ( X i , Y i ) ] + E Q [ log Q X i Y i ( X i , Y i ) μ ( X i , Y i ) ] = I Q ( ( X i , Y i ) ; ( X < i , Y < i ) ) + D ( Q X i Y i ∥ μ ) ≥ D ( Q X i Y i ∥ μ ) . \begin{aligned}
\mathbb{E}_{Q_{X_{<i}Y_{<i}}}D(Q_{X_iY_i\mid X_{<i}Y_{<i}}\mathbin\Vert\mu)
&=\mathbb{E}_Q\left[\log\frac{Q(X_i,Y_i\mid X_{<i},Y_{<i})}{Q_{X_iY_i}(X_i,Y_i)}\right]
+\mathbb{E}_Q\left[\log\frac{Q_{X_iY_i}(X_i,Y_i)}{\mu(X_i,Y_i)}\right]\\
&=I_Q((X_i,Y_i);(X_{<i},Y_{<i}))+D(Q_{X_iY_i}\mathbin\Vert\mu)\\
&\ge D(Q_{X_iY_i}\mathbin\Vert\mu).
\end{aligned} E Q X < i Y < i D ( Q X i Y i ∣ X < i Y < i ∥ μ ) = E Q [ log Q X i Y i ( X i , Y i ) Q ( X i , Y i ∣ X < i , Y < i ) ] + E Q [ log μ ( X i , Y i ) Q X i Y i ( X i , Y i ) ] = I Q (( X i , Y i ) ; ( X < i , Y < i )) + D ( Q X i Y i ∥ μ ) ≥ D ( Q X i Y i ∥ μ ) .
Finally, q X Y = n − 1 ∑ i Q X i Y i q_{XY}=n^{-1}\sum_i Q_{X_iY_i} q X Y = n − 1 ∑ i Q X i Y i , and convexity of relative entropy gives
D ( q X Y ∥ μ ) ≤ 1 n ∑ i D ( Q X i Y i ∥ μ ) ≤ 1 n D ( Q X n Y n ∥ μ ⊗ n ) ≤ log ( 1 / p ) n . D(q_{XY}\mathbin\Vert\mu)\le\frac{1}{n}\sum_iD(Q_{X_iY_i}\mathbin\Vert\mu)\le\frac{1}{n}D(Q_{X^nY^n}\mathbin\Vert\mu^{\otimes n})\le\frac{\log(1/p)}{n}. D ( q X Y ∥ μ ) ≤ n 1 i ∑ D ( Q X i Y i ∥ μ ) ≤ n 1 D ( Q X n Y n ∥ μ ⊗ n ) ≤ n log ( 1/ p ) .
This proves (22) . □
A protocol under the original input distribution
Section 5 constructs a protocol π \pi π which works under the distribution μ \mu μ , based on q q q . The key step is to bound the divergence between its joint distribution and the conditioned coordinate distribution q q q of Construction 4.1.
Construction 5.1 (The single-instance protocol π \pi π ). Let q q q be the distribution in Construction 4.1, with V = ( J , X < J , Y > J , T ‾ ) V=(J,X_{<J},Y_{>J},\overline{T}) V = ( J , X < J , Y > J , T ) . Represent the augmented transcript T ‾ \overline{T} T as alternating binary messages M 1 , … , M m M^1,\ldots,M^m M 1 , … , M m , with Alice sending the odd messages. (Insert fixed empty messages to handle consecutive turns by one party and terminated paths.) On inputs ( x , y ) ∼ μ (x,y)\sim\mu ( x , y ) ∼ μ , the protocol π \pi π proceeds as follows:
Publicly choose J = i J=i J = i uniformly in [ n ] [n] [ n ] , and sample X < i X_{<i} X < i according to q ( X < i ∣ J = i ) q(X_{<i}\mid J=i) q ( X < i ∣ J = i ) , independently of ( x , y ) (x,y) ( x , y ) .
Alice samples Y > i Y_{>i} Y > i according to q ( Y > i ∣ X = x , X < i , J = i ) q(Y_{>i} \mid X=x,X_{<i},J=i) q ( Y > i ∣ X = x , X < i , J = i ) and sends it to Bob.
For each t t t , Alice samples an odd message and Bob samples an even message using, respectively,
q ( M t ∣ X = x , J = i , X < i , Y > i , M < t ) , q(M^t \mid X=x,J=i,X_{<i},Y_{>i},M^{<t}), q ( M t ∣ X = x , J = i , X < i , Y > i , M < t ) ,
q ( M t ∣ Y = y , J = i , X < i , Y > i , M < t ) . q(M^t \mid Y=y,J=i,X_{<i},Y_{>i},M^{<t}). q ( M t ∣ Y = y , J = i , X < i , Y > i , M < t ) .
With V = ( i , X < i , Y > i , M 1 , … , M m ) V=(i,X_{<i},Y_{>i},M^1,\ldots,M^m) V = ( i , X < i , Y > i , M 1 , … , M m ) , Alice samples A A A from q ( A ∣ x , V ) q(A \mid x,V) q ( A ∣ x , V ) and Bob samples B B B from q ( B ∣ y , V ) q(B \mid y,V) q ( B ∣ y , V ) using independent private randomness.
At values of conditional probability zero, define the message distributions arbitrarily. Write P π P_\pi P π for the joint distribution of ( X , Y , A , B , V ) (X,Y,A,B,V) ( X , Y , A , B , V ) under π \pi π .
For n ≥ 1 n \ge1 n ≥ 1 and 0 < p ≤ 1 0 < p \le1 0 < p ≤ 1 , define
δ ( n , p ) : = ln 2 2 n log 1 p . (33) \delta(n,p):=\sqrt{\frac{\ln2}{2n}\log\frac{1}{p}}. \tag*{(33)} δ ( n , p ) := 2 n ln 2 log p 1 . (33)
Lemma 5.1. Suppose q q q is defined as in Construction 4.1 and δ ( n , p ) ≤ 1 2 \delta(n,p) \le\frac{1}{2} δ ( n , p ) ≤ 2 1 . The protocol π \pi π of Construction 5.1 satisfies
err μ ( π ) ≤ err ( q ) + δ ( n , p ) , (34) \operatorname{err}_{\mu}(\pi) \le\operatorname{err}(q)+\delta(n,p), \tag*{(34)} err μ ( π ) ≤ err ( q ) + δ ( n , p ) , (34) IC μ ( π ) ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L i n δ ( n , p ) + 4 h ( δ ( n , p ) ) . (35) \begin{aligned}
\operatorname{IC}_{\mu}(\pi) &\le I_q(X;V \mid Y)+I_q(Y;V \mid X) \\
&\quad+2L_{\mathrm{in}}\delta(n,p)+4h(\delta(n,p)). \tag*{(35)}
\end{aligned} IC μ ( π ) ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L in δ ( n , p ) + 4 h ( δ ( n , p )) . (35)
Proof. Our primary goal is to prove
D ( q ∥ P π ) ≤ log ( 1 / p ) n . D(q\mathbin{\|}P_\pi) \le\frac{\log(1/p)}{n}. D ( q ∥ P π ) ≤ n log ( 1/ p ) .
The error and information bounds will then follow from Pinsker’s inequality and the information-continuity bound. The main step is to compare the distributions q q q , P π P_\pi P π conditional on each choice of J J J and bound the sum of their divergences.
Recall that Q = P ( ⋅ ∣ W S ) Q=P(\mathord{\cdot}\mid W_S) Q = P ( ⋅ ∣ W S ) from Construction 4.1. For each i i i , let q i q_i q i be the distribution of ( X ≤ i , Y ≥ i , T ‾ ) (X_{\le i},Y_{\ge i},\overline{T}) ( X ≤ i , Y ≥ i , T ) under Q Q Q . This is also the distribution of the corresponding variables under q q q conditional on J = i J=i J = i , with the outputs omitted. Let P π ( i ) P_\pi^{(i)} P π ( i ) be their distribution under π \pi π conditional on J = i J=i J = i , before the outputs are sampled. We use P P P and Q Q Q also for their marginals on ( X n , Y n , T ‾ ) (X^n,Y^n,\overline{T}) ( X n , Y n , T ) . We will later use the fact that omitting the other variables, i.e., the outputs, does not change D ( Q ∥ P ) D(Q\mathbin{\|}P) D ( Q ∥ P ) , because the original protocol is deterministic.
To reduce the desired bound to these coordinate distributions, note that J J J is uniform under both q q q and P π P_\pi P π . Moreover, by the local output condition (24), the conditional output distributions agree. The relative-entropy chain rule therefore gives
D ( q ∥ P π ) = 1 n ∑ i = 1 n D ( q i ∥ P π ( i ) ) . (36) D(q\mathbin{\|}P_\pi)=\frac{1}{n}\sum_{i=1}^{n}D(q_i\mathbin{\|}P_\pi^{(i)}). \tag*{(36)} D ( q ∥ P π ) = n 1 i = 1 ∑ n D ( q i ∥ P π ( i ) ) . (36)
It thus suffices to prove
∑ i = 1 n D ( q i ∥ P π ( i ) ) ≤ D ( Q ∥ P ) ≤ log ( 1 / p ) , \sum_{i=1}^{n}D(q_i\mathbin{\|}P_\pi^{(i)})\le D(Q\mathbin{\|}P)\le\log(1/p), i = 1 ∑ n D ( q i ∥ P π ( i ) ) ≤ D ( Q ∥ P ) ≤ log ( 1/ p ) ,
where the second inequality is already given in (27). To prove the summed divergence bound above, we will construct a probability distribution Q n Q_n Q n on ( X n , Y n , T ‾ ) (X^n,Y^n,\overline{T}) ( X n , Y n , T ) satisfying
Q n ( x n , y n , m ) P ( x n , y n , m ) = ∏ i = 1 n q i ( x ≤ i , y ≥ i , m ) P π ( i ) ( x ≤ i , y ≥ i , m ) . (37) \frac{Q_n(x^n,y^n,m)}{P(x^n,y^n,m)}=\prod_{i=1}^{n}\frac{q_i(x_{\leq i},y_{\geq i},m)}{P_{\pi}^{(i)}(x_{\leq i},y_{\geq i},m)}. \tag*{(37)} P ( x n , y n , m ) Q n ( x n , y n , m ) = i = 1 ∏ n P π ( i ) ( x ≤ i , y ≥ i , m ) q i ( x ≤ i , y ≥ i , m ) . (37)
on the support of Q Q Q . Because q i q_i q i is the corresponding marginal of Q Q Q , taking logarithms and expectations under Q Q Q will then give
∑ i = 1 n D ( q i ∥ P π ( i ) ) = E Q log Q n P = D ( Q ∥ P ) − D ( Q ∥ Q n ) ≤ D ( Q ∥ P ) \sum_{i=1}^{n}D(q_i\mathbin{\|}P_{\pi}^{(i)})=\mathbb{E}_Q\log\frac{Q_n}{P}=D(Q\mathbin{\|}P)-D(Q\mathbin{\|}Q_n)\leq D(Q\mathbin{\|}P) i = 1 ∑ n D ( q i ∥ P π ( i ) ) = E Q log P Q n = D ( Q ∥ P ) − D ( Q ∥ Q n ) ≤ D ( Q ∥ P )
as desired.
Construction of Q n Q_n Q n . We construct Q n Q_n Q n by successive sampling. First sample ( X n , Y n , T ‾ ) (X^n,Y_n,\overline{T}) ( X n , Y n , T ) from q n q_n q n . Then, for i = n − 1 , … , 1 i=n-1,\ldots,1 i = n − 1 , … , 1 , sample Y i Y_i Y i according to Q ( Y i ∣ X ≤ i , Y > i , T ‾ ) Q(Y_i\mid X_{\leq i},Y_{>i},\overline{T}) Q ( Y i ∣ X ≤ i , Y > i , T ) . Conditional distributions at conditioning values of zero Q Q Q -probability may be chosen arbitrarily. This procedure defines a probability distribution
Q n ( x n , y n , m ) = q n ( x n , y n , m ) ∏ i = 1 n − 1 Q ( y i ∣ x ≤ i , y > i , m ) . Q_n(x^n,y^n,m)=q_n(x^n,y_n,m)\prod_{i=1}^{n-1}Q(y_i\mid x_{\leq i},y_{>i},m). Q n ( x n , y n , m ) = q n ( x n , y n , m ) i = 1 ∏ n − 1 Q ( y i ∣ x ≤ i , y > i , m ) .
For every ( x n , y n , m ) (x^n,y^n,m) ( x n , y n , m ) in the support of Q Q Q , all factors in this expression are positive. Moreover, since q i ( x ≤ i , y ≥ i , m ) = Q ( x ≤ i , y ≥ i , m ) q_i(x_{\leq i},y_{\geq i},m)=Q(x_{\leq i},y_{\geq i},m) q i ( x ≤ i , y ≥ i , m ) = Q ( x ≤ i , y ≥ i , m ) , rewriting each conditional probability as a ratio gives
Q n ( x n , y n , m ) = q n ( x n , y n , m ) ∏ i = 1 n − 1 Q ( x ≤ i , y ≥ i , m ) Q ( x ≤ i , y > i , m ) = ∏ i = 1 n q i ( x ≤ i , y ≥ i , m ) ∏ i = 1 n − 1 Q ( x ≤ i , y > i , m ) . Q_n(x^n,y^n,m)=q_n(x^n,y_n,m)\prod_{i=1}^{n-1}\frac{Q(x_{\leq i},y_{\geq i},m)}{Q(x_{\leq i},y_{>i},m)}
=\frac{\prod_{i=1}^{n}q_i(x_{\leq i},y_{\geq i},m)}{\prod_{i=1}^{n-1}Q(x_{\leq i},y_{>i},m)}. Q n ( x n , y n , m ) = q n ( x n , y n , m ) i = 1 ∏ n − 1 Q ( x ≤ i , y > i , m ) Q ( x ≤ i , y ≥ i , m ) = ∏ i = 1 n − 1 Q ( x ≤ i , y > i , m ) ∏ i = 1 n q i ( x ≤ i , y ≥ i , m ) .
The denominator contains the marginals shared by consecutive coordinate distributions. We next simplify ∏ i P π ( i ) \prod_i P_{\pi}^{(i)} ∏ i P π ( i ) and show that the same marginal factors occur in its expression, which will establish (37).
Product identity. Our goal in this step is to simplify the product P π ( i ) P_{\pi}^{(i)} P π ( i ) of probability distributions. More precisely, we will show that, on the support of Q Q Q ,
∏ i = 1 n P π ( i ) ( x ≤ i , y ≥ i , m ) = P ( x n , y n , m ) ∏ i = 1 n − 1 Q ( x ≤ i , y > i , m ) . \prod_{i=1}^{n}P_{\pi}^{(i)}(x_{\leq i},y_{\geq i},m)=P(x^n,y^n,m)\prod_{i=1}^{n-1}Q(x_{\leq i},y_{>i},m). i = 1 ∏ n P π ( i ) ( x ≤ i , y ≥ i , m ) = P ( x n , y n , m ) i = 1 ∏ n − 1 Q ( x ≤ i , y > i , m ) .
Comparing this expression with the product expression for Q n Q_n Q n above will prove (37). Fix ( x n , y n , m ) (x^n,y^n,m) ( x n , y n , m ) with Q ( x n , y n , m ) > 0 Q(x^n,y^n,m)>0 Q ( x n , y n , m ) > 0 . We use the conventions
Q ( x < 1 ) = Q ( y > n ) = 1 , Q ( y > n ∣ x n ) = 1 , Q ( x ≤ n , y > n ) = Q ( x n ) . Q(x_{<1})=Q(y_{>n})=1,\qquad Q(y_{>n}\mid x^n)=1,\qquad Q(x_{\leq n},y_{>n})=Q(x^n). Q ( x < 1 ) = Q ( y > n ) = 1 , Q ( y > n ∣ x n ) = 1 , Q ( x ≤ n , y > n ) = Q ( x n ) .
The definition of q q q in Construction 4.1 and the sampling steps of π \pi π in Construction 5.1 give
P π ( i ) ( x ≤ i , y ≥ i , m ) = μ ( x i , y i ) Q ( x < i ) Q ( y > i ∣ x ≤ i ) ⋅ ∏ t o d d Q ( m t ∣ x ≤ i , y ≥ i , m < t ) ∏ t e v e n Q ( m t ∣ x < i , y ≥ i , m < t ) . (38) \begin{aligned}
P_{\pi}^{(i)}(x_{\leq i},y_{\geq i},m)
={}&\mu(x_i,y_i)Q(x_{<i})Q(y_{>i}\mid x_{\leq i})\\
&\cdot\prod_{t\ \mathrm{odd}}Q(m^t\mid x_{\leq i},y_{\geq i},m^{<t})
\prod_{t\ \mathrm{even}}Q(m^t\mid x_{<i},y_{\geq i},m^{<t}). \tag*{(38)}
\end{aligned} P π ( i ) ( x ≤ i , y ≥ i , m ) = μ ( x i , y i ) Q ( x < i ) Q ( y > i ∣ x ≤ i ) ⋅ t odd ∏ Q ( m t ∣ x ≤ i , y ≥ i , m < t ) t even ∏ Q ( m t ∣ x < i , y ≥ i , m < t ) . (38)
Every factor is positive under the stated assumption. In the following, we evaluate the product of the input factors and the product of the message factors in (38) separately.
We begin with the input factors involving X < i X_{<i} X < i and Y > i Y_{>i} Y > i :
∏ i = 1 n Q ( x < i ) Q ( y > i ∣ x ≤ i ) = ( ∏ i = 1 n Q ( x < i ) Q ( x ≤ i ) ) ∏ i = 1 n Q ( x ≤ i , y > i ) = 1 Q ( x n ) ∏ i = 1 n Q ( x ≤ i , y > i ) = ∏ i = 1 n − 1 Q ( x ≤ i , y > i ) . \begin{aligned}
\prod_{i=1}^{n} Q(x_{<i})Q(y_{>i}\mid x_{\leq i}) = \left(\prod_{i=1}^{n}\frac{Q(x_{<i})}{Q(x_{\leq i})}\right)\prod_{i=1}^{n}Q(x_{\leq i},y_{>i}) \\
&= \frac{1}{Q(x^{n})}\prod_{i=1}^{n}Q(x_{\leq i},y_{>i}) \\
&= \prod_{i=1}^{n-1}Q(x_{\leq i},y_{>i}).
\end{aligned} i = 1 ∏ n Q ( x < i ) Q ( y > i ∣ x ≤ i ) = ( i = 1 ∏ n Q ( x ≤ i ) Q ( x < i ) ) i = 1 ∏ n Q ( x ≤ i , y > i ) = Q ( x n ) 1 i = 1 ∏ n Q ( x ≤ i , y > i ) = i = 1 ∏ n − 1 Q ( x ≤ i , y > i ) .
In the second equality, the numerator at index i + 1 i+1 i + 1 cancels the denominator at index i i i , leaving 1 / Q ( x n ) 1/Q(x^{n}) 1/ Q ( x n ) . The last equality cancels this remaining denominator against Q ( x ≤ n , y > n ) = Q ( x n ) Q(x_{\leq n},y_{>n})=Q(x^{n}) Q ( x ≤ n , y > n ) = Q ( x n ) . These equalities also hold for n = 1 n=1 n = 1 under the above conventions, with the final empty product equal to one.
For the factors including m m m ’s, pair the odd-message factors at coordinate i i i with the even-message factors at coordinate i + 1 i+1 i + 1 . Since x < i + 1 = x ≤ i x_{<i+1}=x_{\leq i} x < i + 1 = x ≤ i and y ≥ i + 1 = y > i y_{\geq i+1}=y_{>i} y ≥ i + 1 = y > i , for each i < n i<n i < n we obtain
∏ t o d d Q ( m t ∣ x ≤ i , y > i , m < t ) ∏ t e v e n Q ( m t ∣ x < i + 1 , y ≥ i + 1 , m < t ) = ∏ t Q ( m t ∣ x ≤ i , y > i , m < t ) = Q ( m ∣ x ≤ i , y > i ) . \begin{aligned}
\prod_{t\ \mathrm{odd}}Q(m^{t}\mid x_{\leq i},y_{>i},m^{<t})\prod_{t\ \mathrm{even}}Q(m^{t}\mid x_{<i+1},y_{\geq i+1},m^{<t}) \\
&=\prod_{t}Q(m^{t}\mid x_{\leq i},y_{>i},m^{<t})=Q(m\mid x_{\leq i},y_{>i}).
\end{aligned} t odd ∏ Q ( m t ∣ x ≤ i , y > i , m < t ) t even ∏ Q ( m t ∣ x < i + 1 , y ≥ i + 1 , m < t ) = t ∏ Q ( m t ∣ x ≤ i , y > i , m < t ) = Q ( m ∣ x ≤ i , y > i ) .
The remaining factors are
∏ t e v e n Q ( m t ∣ y n , m < t ) = ∏ t o d d Q ( m t ∣ x n , m < t ) = 1. \prod_{t\ \mathrm{even}}Q(m^{t}\mid y^{n},m^{<t})=\prod_{t\ \mathrm{odd}}Q(m^{t}\mid x^{n},m^{<t})=1. t even ∏ Q ( m t ∣ y n , m < t ) = t odd ∏ Q ( m t ∣ x n , m < t ) = 1.
Indeed, each such message is determined by its sender’s full input and the preceding messages, and m m m occurs with positive probability under Q Q Q .
Combining the input and message factors gives
∏ i P π ( i ) ( x ≤ i , y ≥ i , m ) = μ ⊗ n ( x n , y n ) ∏ i = 1 n − 1 Q ( x ≤ i , y > i ) Q ( m ∣ x ≤ i , y > i ) = P ( x n , y n , m ) ∏ i = 1 n − 1 Q ( x ≤ i , y > i , m ) (39) \begin{aligned}
\prod_{i}P_{\pi}^{(i)}(x_{\leq i},y_{\geq i},m)=\mu^{\otimes n}(x^{n},y^{n})\prod_{i=1}^{n-1}Q(x_{\leq i},y_{>i})Q(m\mid x_{\leq i},y_{>i}) \\
&=P(x^{n},y^{n},m)\prod_{i=1}^{n-1}Q(x_{\leq i},y_{>i},m) \tag*{(39)}
\end{aligned} i ∏ P π ( i ) ( x ≤ i , y ≥ i , m ) = μ ⊗ n ( x n , y n ) i = 1 ∏ n − 1 Q ( x ≤ i , y > i ) Q ( m ∣ x ≤ i , y > i ) = P ( x n , y n , m ) i = 1 ∏ n − 1 Q ( x ≤ i , y > i , m ) (39)
as desired. Note that P ( x n , y n , m ) = μ ⊗ n ( x n , y n ) P(x^{n},y^{n},m)=\mu^{\otimes n}(x^{n},y^{n}) P ( x n , y n , m ) = μ ⊗ n ( x n , y n ) because the original protocol is deterministic and Q ( x n , y n , m ) > 0 Q(x^{n},y^{n},m)>0 Q ( x n , y n , m ) > 0 . Comparing (39) with the product expression for Q n Q_{n} Q n proves (37).
Divergence bound. Since (37) is now established, the discussion given after (37) gives ∑ i D ( q i ∥ P π ( i ) ) ≤ D ( Q ∥ P ) \sum_i D(q_i\Vert P_{\pi}^{(i)})\leq D(Q\Vert P) ∑ i D ( q i ∥ P π ( i ) ) ≤ D ( Q ∥ P ) . The averaging identity (36) and (27) therefore imply
D ( q ∥ P π ) ≤ D ( Q ∥ P ) n ≤ log ( 1 / p ) n . (40) D(q\Vert P_{\pi})\leq\frac{D(Q\Vert P)}{n}\leq\frac{\log(1/p)}{n}. \tag*{(40)} D ( q ∥ P π ) ≤ n D ( Q ∥ P ) ≤ n log ( 1/ p ) . (40)
Error and information bounds. Pinsker’s inequality (Fact 2.3), the divergence bound (40), and the definition (33) of δ ( n , p ) \delta(n,p) δ ( n , p ) imply
TV ( q , P π ) ≤ δ ( n , p ) . (41) \operatorname{TV}(q,P_{\pi})\leq\delta(n,p). \tag*{(41)} TV ( q , P π ) ≤ δ ( n , p ) . (41)
The probabilities of the failure event { ( A , B ) ∉ g ( X , Y ) } \{(A,B) \notin g(X,Y)\} {( A , B ) ∈ / g ( X , Y )} under q q q and P π P_\pi P π differ by at most this distance, proving (34).
Under P π P_\pi P π , the public choice ( J , X < J ) (J,X_{<J}) ( J , X < J ) is independent of ( X , Y ) ∼ μ (X,Y) \sim\mu ( X , Y ) ∼ μ , and all other components of V V V are messages. Thus the definition (5) gives
IC μ ( π ) = I P π ( X ; V ∣ Y ) + I P π ( Y ; V ∣ X ) . \operatorname{IC}_{\mu}(\pi)=I_{P_\pi}(X;V\mid Y)+I_{P_\pi}(Y;V\mid X). IC μ ( π ) = I P π ( X ; V ∣ Y ) + I P π ( Y ; V ∣ X ) .
Finally, the distributions of ( X , Y , V ) (X,Y,V) ( X , Y , V ) under q q q and P π P_\pi P π have total variation distance at most δ ( n , p ) \delta(n,p) δ ( n , p ) by (41). Applying the inequality (12) of Fact 2.4 proves (35).
A zero-communication protocol
The protocol π \pi π of Construction 5.1 may have information cost greater than R R R . To fix this, we construct a zero-message protocol σ \sigma σ on inputs drawn from μ \mu μ and bound its error using the distribution q q q of Construction 4.1.
Sampling without communication
Lemma 6.1 applies when, given the same value of V V V , Alice can sample A A A using ( X , V ) (X,V) ( X , V ) and Bob can independently sample B B B using ( Y , V ) (Y,V) ( Y , V ) . Its proof uses the shared sampling result of Lemma C.1 to generate the parties’ samples of V V V without communication.
Lemma 6.1. Let λ \lambda λ be a distribution of ( X , Y , V , A , B ) (X,Y,V,A,B) ( X , Y , V , A , B ) with
λ ( a , b ∣ x , y , v ) = λ ( a ∣ x , v ) λ ( b ∣ y , v ) \lambda(a,b\mid x,y,v)=\lambda(a\mid x,v)\lambda(b\mid y,v) λ ( a , b ∣ x , y , v ) = λ ( a ∣ x , v ) λ ( b ∣ y , v ) whenever λ ( x , y , v ) > 0 \lambda(x,y,v)>0 λ ( x , y , v ) > 0 . On inputs drawn from λ X Y \lambda_{XY} λ X Y , there is a zero-message protocol with error at most
err ( λ ) + 2 ( ln 2 ) [ I λ ( X ; V ∣ Y ) + I λ ( Y ; V ∣ X ) ] , (42) \operatorname{err}(\lambda)+2\sqrt{(\ln2)[I_\lambda(X;V\mid Y)+I_\lambda(Y;V\mid X)]}, \tag*{(42)} err ( λ ) + 2 ( ln 2 ) [ I λ ( X ; V ∣ Y ) + I λ ( Y ; V ∣ X )] , (42) where err ( λ ) = λ [ ( A , B ) ∉ g ( X , Y ) ] \operatorname{err}(\lambda)=\lambda[(A,B)\notin g(X,Y)] err ( λ ) = λ [( A , B ) ∈ / g ( X , Y )] .
Proof. We fist construct the sampling protocol and then bound its error.
Construction of the sampling protocol. Let D \mathcal{D} D be a set of distributions:
D = { λ ( V ∣ x , y ) , λ ( V ∣ x ) , λ ( V ∣ y ) } ( x , y ) ∈ supp ( λ X Y ) . \mathcal{D}=\{\lambda(V\mid x,y),\lambda(V\mid x),\lambda(V\mid y)\}_{(x,y)\in\operatorname{supp}(\lambda_{XY})}. D = { λ ( V ∣ x , y ) , λ ( V ∣ x ) , λ ( V ∣ y ) } ( x , y ) ∈ supp ( λ X Y ) .
Applying Lemma C.1 to the set D \mathcal{D} D , we obtain a (finite-valued) shared randomness R R R and a function S D : R → Im V S_{\mathcal{D}}:R\to\operatorname{Im}V S D : R → Im V such that
Pr [ S D 1 ( R ) ≠ S D 2 ( R ) ] ≤ 2 TV ( D 1 , D 2 ) for every D 1 , D 2 ∈ D . (43) \Pr[S_{D_1}(R)\ne S_{D_2}(R)]\le2\operatorname{TV}(D_1,D_2)\qquad\text{for every }D_1,D_2\in\mathcal{D}. \tag*{(43)} Pr [ S D 1 ( R ) = S D 2 ( R )] ≤ 2 TV ( D 1 , D 2 ) for every D 1 , D 2 ∈ D . (43)
On input ( x , y ) (x,y) ( x , y ) , Alice and Bob respectively set
V A = S λ ( V ∣ x ) ( R ) , V B = S λ ( V ∣ y ) ( R ) . V_A=S_{\lambda(V\mid x)}(R),\qquad V_B=S_{\lambda(V\mid y)}(R). V A = S λ ( V ∣ x ) ( R ) , V B = S λ ( V ∣ y ) ( R ) .
Alice outputs according to λ ( A ∣ x , V A ) \lambda(A\mid x,V_A) λ ( A ∣ x , V A ) , and Bob independently outputs according to λ ( B ∣ y , V B ) \lambda(B\mid y,V_B) λ ( B ∣ y , V B ) . They send no messages. For the analysis, define the random variable V ∗ V_* V ∗ as
V ∗ = S λ ( V ∣ x , y ) ( R ) . V_*=S_{\lambda(V\mid x,y)}(R). V ∗ = S λ ( V ∣ x , y ) ( R ) .
Neither player needs to compute V ∗ V_* V ∗ . When the parties successfully share the same V ∗ V_* V ∗ and output A ∼ λ ( A ∣ V ∗ , x ) A \sim\lambda(A\mid V_*,x) A ∼ λ ( A ∣ V ∗ , x ) and B ∼ λ ( B ∣ V ∗ , y ) B \sim\lambda(B\mid V_*,y) B ∼ λ ( B ∣ V ∗ , y ) , the error probability is err ( λ ) \operatorname{err}(\lambda) err ( λ ) .
Error bound. All probabilities below use the inputs X Y XY X Y drawn from λ X Y \lambda_{XY} λ X Y . The bound (43) on TV, Pinsker’s inequality in Fact 2.3, and Jensen’s inequality give
Pr [ V A ≠ V ∗ ] ≤ 2 E λ X Y TV ( λ V ∣ X , Y , λ V ∣ X ) ≤ 2 ( ln 2 ) E λ X Y D ( λ V ∣ X , Y ∥ λ V ∣ X ) = 2 ( ln 2 ) I λ ( Y ; V ∣ X ) . \Pr[V_A \ne V_*] \le2\mathbb{E}_{\lambda_{XY}}\operatorname{TV}(\lambda_{V\mid X,Y},\lambda_{V\mid X})
\le\sqrt{2(\ln2)\mathbb{E}_{\lambda_{XY}}D(\lambda_{V\mid X,Y}\Vert\lambda_{V\mid X})}
= \sqrt{2(\ln2)I_\lambda(Y;V\mid X)}. Pr [ V A = V ∗ ] ≤ 2 E λ X Y TV ( λ V ∣ X , Y , λ V ∣ X ) ≤ 2 ( ln 2 ) E λ X Y D ( λ V ∣ X , Y ∥ λ V ∣ X ) = 2 ( ln 2 ) I λ ( Y ; V ∣ X ) .
Similarly,
Pr [ V B ≠ V ∗ ] ≤ 2 ( ln 2 ) I λ ( X ; V ∣ Y ) . \Pr[V_B \ne V_*] \le\sqrt{2(\ln2)I_\lambda(X;V\mid Y)}. Pr [ V B = V ∗ ] ≤ 2 ( ln 2 ) I λ ( X ; V ∣ Y ) .
A union bound then gives,
Pr [ ( A , B ) ∉ g ( X , Y ) ] ≤ Pr [ { λ fails } ∪ { Alice fails to produce V ∗ } ∪ { Bob fails to produce V ∗ } ] ≤ err ( λ ) + Pr [ V A ≠ V ∗ ] + Pr [ V B ≠ V ∗ ] , \Pr[(A,B)\notin g(X,Y)]
\le\Pr[\{\lambda\text{ fails}\}\cup\{\text{Alice fails to produce }V_*\}\cup\{\text{Bob fails to produce }V_*\}]
\le\operatorname{err}(\lambda)+\Pr[V_A\ne V_*]+\Pr[V_B\ne V_*], Pr [( A , B ) ∈ / g ( X , Y )] ≤ Pr [{ λ fails } ∪ { Alice fails to produce V ∗ } ∪ { Bob fails to produce V ∗ }] ≤ err ( λ ) + Pr [ V A = V ∗ ] + Pr [ V B = V ∗ ] ,
Using u + v ≤ 2 ( u + v ) \sqrt{u}+\sqrt{v}\le\sqrt{2(u+v)} u + v ≤ 2 ( u + v ) proves the desired inequality (42).
Running the sampler on original inputs
We now apply Lemma 6.1 with λ = q \lambda=q λ = q in Lemma 6.2. Recall that the distribution q q q of Construction 4.1 has err ( q ) ≤ ε \operatorname{err}(q)\le\varepsilon err ( q ) ≤ ε and satisfies the following properties by Lemma 4.3:
D ( q X Y ∥ μ ) ≤ log ( 1 / p ) n , D(q_{XY}\Vert\mu)\le\frac{\log(1/p)}{n}, D ( q X Y ∥ μ ) ≤ n log ( 1/ p ) ,
I_q(X;V\mid Y)+I_q(Y;V\mid X)\le R+\frac{\log(1/p)}{n}\left(2+\frac{L_{\mathrm{out}}{-\log(1-\varepsilon)}\right),}
q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) . q(a,b\mid x,y,v)=q(a\mid x,v)q(b\mid y,v). q ( a , b ∣ x , y , v ) = q ( a ∣ x , v ) q ( b ∣ y , v ) .
Lemma 6.2. There is a zero-message protocol σ \sigma σ on inputs drawn from μ \mu μ such that IC μ ( σ ) = 0 \operatorname{IC}_\mu(\sigma)=0 IC μ ( σ ) = 0 and
\operatorname{err}_\mu(\sigma)\le\varepsilon+\delta(n,p)
+2\sqrt{(\ln2)\left[R+\frac{\log(1/p)}{n}\left(2+\frac{L_{\mathrm{out}}{-\log(1-\varepsilon)}\right)\right]}.} \tag*{(44)}
Proof. For any input ( x , y ) ∈ supp ( μ ) (x,y)\in\operatorname{supp}(\mu) ( x , y ) ∈ supp ( μ ) , Alice and Bob use the protocol from Lemma 6.1 to draw V A ∼ q ( V ∣ x ) V_A\sim q(V\mid x) V A ∼ q ( V ∣ x ) and V B ∼ q ( V ∣ y ) V_B\sim q(V\mid y) V B ∼ q ( V ∣ y ) . They output according to q ( A ∣ x , V A ) q(A\mid x,V_A) q ( A ∣ x , V A ) and q ( B ∣ y , V B ) q(B\mid y,V_B) q ( B ∣ y , V B ) , respectively, without communicating. For inputs having zero-probability under q q q , they sample arbitrarily. Denote this protocol by σ \sigma σ .
Under inputs distributed as q X Y q_{XY} q X Y , the consequence of Lemma 6.1 is
\operatorname{err}_{q_{XY}}(\sigma)\le\operatorname{err}(q)+2\sqrt{(\ln2)[I_q(X;V\mid Y)+I_q(Y;V\mid X)]}
\le\varepsilon+2\sqrt{(\ln2)\left[R+\frac{\log(1/p)}{n}\left(2+\frac{L_{\mathrm{out}}{-\log(1-\varepsilon)}\right)\right]},}
together with the properties of q q q .
To convert err q X Y ( σ ) \operatorname{err}_{q_{XY}}(\sigma) err q X Y ( σ ) to err μ ( σ ) \operatorname{err}_{\mu}(\sigma) err μ ( σ ) , use TV ( q X Y , μ ) ≤ δ ( n , p ) \operatorname{TV}(q_{XY},\mu) \le\delta(n,p) TV ( q X Y , μ ) ≤ δ ( n , p ) by Pinsker’s inequality. Formally,
∣ err q X Y ( σ ) − err μ ( σ ) ∣ = ∣ ∑ x , y ( q X Y ( x , y ) − μ ( x , y ) ) ( Pr [ σ errs ∣ x , y ] − 1 2 ) ∣ ≤ 1 2 ∑ x , y ∣ q X Y ( x , y ) − μ ( x , y ) ∣ = TV ( q X Y , μ ) ≤ δ ( n , p ) . \begin{aligned}
\left|\operatorname{err}_{q_{XY}}(\sigma)-\operatorname{err}_{\mu}(\sigma)\right| = \left|\sum_{x,y}\left(q_{XY}(x,y)-\mu(x,y)\right)\left(\Pr[\sigma\text{ errs}\mid x,y]-\frac{1}{2}\right)\right| \\
&\le\frac{1}{2}\sum_{x,y}\left|q_{XY}(x,y)-\mu(x,y)\right| \\
&= \operatorname{TV}(q_{XY},\mu) \le\delta(n,p).
\end{aligned} ∣ err q X Y ( σ ) − err μ ( σ ) ∣ = x , y ∑ ( q X Y ( x , y ) − μ ( x , y ) ) ( Pr [ σ errs ∣ x , y ] − 2 1 ) ≤ 2 1 x , y ∑ ∣ q X Y ( x , y ) − μ ( x , y ) ∣ = TV ( q X Y , μ ) ≤ δ ( n , p ) .
Combining the arguments proves the statement. □ \square □
Proof of the strong converse
The protocol π \pi π from Lemma 5.1 has small error, but its information cost may exceed R R R , while the zero-message protocol σ \sigma σ has larger error but its information cost is zero. We combine the two protocols in Proposition 7.1 by probabilistic mixing to obtain information cost at most R R R . The resulting error bound will prove Theorem 3.1.
A public coin protocol with information cost at most R R R
Proposition 7.1. Suppose Cost w c ( Π n ) ≤ n R \operatorname{Cost}_{\mathrm{wc}}(\Pi_n) \le nR Cost wc ( Π n ) ≤ n R , its success probability on μ ⊗ n \mu^{\otimes n} μ ⊗ n is p > 0 p>0 p > 0 , and 0 < ε < 1 0<\varepsilon<1 0 < ε < 1 . With δ ( n , p ) \delta(n,p) δ ( n , p ) defined in (33), suppose δ ( n , p ) ≤ 1 2 \delta(n,p)\le\frac{1}{2} δ ( n , p ) ≤ 2 1 . Let π \pi π be the protocol constructed in Lemma 5.1, and put C = IC μ ( π ) C=\operatorname{IC}_{\mu}(\pi) C = IC μ ( π ) . Then the information cost C C C satisfies the following bound:
C ≤ R + ( 2 + L o u t − log ( 1 − ε ) ) log ( 1 / p ) n + 2 L i n δ ( n , p ) + 4 h ( δ ( n , p ) ) . (45) C \le R+\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right)\frac{\log(1/p)}{n}+2L_{\mathrm{in}}\delta(n,p)+4h(\delta(n,p)). \tag*{(45)} C ≤ R + ( 2 + − log ( 1 − ε ) L out ) n log ( 1/ p ) + 2 L in δ ( n , p ) + 4 h ( δ ( n , p )) . (45) The error bounds on err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) are given as follows: If C ≤ R C\le R C ≤ R , then
err μ ( R ) ≤ ε + δ ( n , p ) . (46) \operatorname{err}_{\mu}(R)\le\varepsilon+\delta(n,p). \tag*{(46)} err μ ( R ) ≤ ε + δ ( n , p ) . (46) If C > R C>R C > R , then
err μ ( R ) ≤ ε + δ ( n , p ) + 2 ( 1 − R C ) ( ln 2 ) [ R + ( 2 + L o u t − log ( 1 − ε ) ) log ( 1 / p ) n ] . (47) \operatorname{err}_{\mu}(R)\le\varepsilon+\delta(n,p)+2\left(1-\frac{R}{C}\right)\sqrt{(\ln2)\left[R+\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right)\frac{\log(1/p)}{n}\right]}. \tag*{(47)} err μ ( R ) ≤ ε + δ ( n , p ) + 2 ( 1 − C R ) ( ln 2 ) [ R + ( 2 + − log ( 1 − ε ) L out ) n log ( 1/ p ) ] . (47)
Proof. We first use the bounds established in Section 5 and Section 6 to obtain the bound (45) on C C C . The bound (35) on information for π \pi π gives
C ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L i n δ ( n , p ) + 4 h ( δ ( n , p ) ) , C\le I_q(X;V\mid Y)+I_q(Y;V\mid X)+2L_{\mathrm{in}}\delta(n,p)+4h(\delta(n,p)), C ≤ I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) + 2 L in δ ( n , p ) + 4 h ( δ ( n , p )) ,
and the bound (23) for q q q gives
I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + ( 2 + L o u t − log ( 1 − ε ) ) log ( 1 / p ) n . I_q(X;V\mid Y)+I_q(Y;V\mid X)\le R+\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right)\frac{\log(1/p)}{n}. I q ( X ; V ∣ Y ) + I q ( Y ; V ∣ X ) ≤ R + ( 2 + − log ( 1 − ε ) L out ) n log ( 1/ p ) .
Substituting the second bound into the first proves (45).
For the error bounds (46) and (47) , recall that the error bounds for π \pi π and σ \sigma σ are
err μ ( π ) ≤ ε + δ ( n , p ) , \operatorname{err}_{\mu}(\pi) \le\varepsilon+ \delta(n,p), err μ ( π ) ≤ ε + δ ( n , p ) ,
err μ ( σ ) ≤ ε + δ ( n , p ) + 2 ( ln 2 ) [ R + ( 2 + L o u t − log ( 1 − ε ) ) log ( 1 / p ) n ] . \operatorname{err}_{\mu}(\sigma) \le\varepsilon+ \delta(n,p) + 2\sqrt{(\ln2)\left[R+\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right)\frac{\log(1/p)}{n}\right]}. err μ ( σ ) ≤ ε + δ ( n , p ) + 2 ( ln 2 ) [ R + ( 2 + − log ( 1 − ε ) L out ) n log ( 1/ p ) ] .
The first uses err ( q ) ≤ ε \operatorname{err}(q) \le\varepsilon err ( q ) ≤ ε in the error bound (34) for π \pi π ; the second is the error bound (44) for σ \sigma σ .
If C ≤ R C \le R C ≤ R , run π \pi π . Its information cost meets the requirement, proving (46) . If C > R C > R C > R , independently of the inputs, use a public coin to run π \pi π with probability R / C R/C R / C and σ \sigma σ otherwise. The coin is part of the public transcript. Since IC μ ( σ ) = 0 \operatorname{IC}_{\mu}(\sigma)=0 IC μ ( σ ) = 0 , the information cost is ( R / C ) C = R (R/C)C=R ( R / C ) C = R . Averaging the displayed error bounds gives (47) .
Positivity of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R )
Proposition 7.2 proves err μ ( R ) > 0 \operatorname{err}_{\mu}(R)>0 err μ ( R ) > 0 when R < IC μ ( g , 0 ) R<\operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) , which will be used in the proof of Theorem 3.1 . At R = 0 R=0 R = 0 , we also identify this error with η = 1 − ω ( g , μ ) \eta=1-\omega(g,\mu) η = 1 − ω ( g , μ ) , the minimum error of a zero-message strategy.
Proposition 7.2. If R < IC μ ( g , 0 ) R<\operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) , then err μ ( R ) > 0 \operatorname{err}_{\mu}(R)>0 err μ ( R ) > 0 . Moreover, err μ ( 0 ) = η \operatorname{err}_{\mu}(0)=\eta err μ ( 0 ) = η .
Proof. We prove the first statement by contraposition. If err μ ( R ) = 0 \operatorname{err}_{\mu}(R)=0 err μ ( R ) = 0 , the definition (6) of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) supplies a sequence of protocols of information cost at most R R R whose errors tend to zero. Thus IC μ ( g , ε ) ≤ R \operatorname{IC}_{\mu}(g,\varepsilon)\le R IC μ ( g , ε ) ≤ R for every ε > 0 \varepsilon>0 ε > 0 . The zero-error continuity in Proposition B.1 implies IC μ ( g , 0 ) ≤ R \operatorname{IC}_{\mu}(g,0)\le R IC μ ( g , 0 ) ≤ R .
For the second statement, recall the definition of η \eta η , the minimum error probability of the game ( g , μ ) (g,\mu) ( g , μ ) . Therefore there is a zero-message strategy of error η \eta η , which gives err μ ( 0 ) ≤ η \operatorname{err}_{\mu}(0)\le\eta err μ ( 0 ) ≤ η . It remains to show err μ ( 0 ) ≥ η \operatorname{err}_{\mu}(0)\ge\eta err μ ( 0 ) ≥ η . Let ρ \rho ρ be any protocol with IC μ ( ρ ) = 0 \operatorname{IC}_{\mu}(\rho)=0 IC μ ( ρ ) = 0 . A key issue is that ρ \rho ρ may send a lot of messages while keeping the information cost equal to zero. To resolve this issue, we apply Lemma 6.1 to its complete distribution, taking V V V to be its public randomness and complete transcript. This conversion makes its communication zero. For conditioning events of positive probability, the output probability satisfies the factorization
Pr [ A = a , B = b ∣ X = x , Y = y , V = v ] = Pr [ A = a ∣ X = x , V = v ] Pr [ B = b ∣ Y = y , V = v ] , \Pr[A=a,B=b\mid X=x,Y=y,V=v]=\Pr[A=a\mid X=x,V=v]\Pr[B=b\mid Y=y,V=v], Pr [ A = a , B = b ∣ X = x , Y = y , V = v ] = Pr [ A = a ∣ X = x , V = v ] Pr [ B = b ∣ Y = y , V = v ] ,
as detailed in Proposition A.1. Since the public randomness is independent of the inputs, the sampling error overhead (42) of Lemma 6.1 is
I ( X ; V ∣ Y ) + I ( Y ; V ∣ X ) = IC μ ( ρ ) = 0. I(X;V\mid Y)+I(Y;V\mid X)=\operatorname{IC}_{\mu}(\rho)=0. I ( X ; V ∣ Y ) + I ( Y ; V ∣ X ) = IC μ ( ρ ) = 0.
Lemma 6.1 therefore gives a zero-message strategy whose error is at most err μ ( ρ ) \operatorname{err}_{\mu}(\rho) err μ ( ρ ) . It implies η ≤ err μ ( ρ ) \eta\le\operatorname{err}_{\mu}(\rho) η ≤ err μ ( ρ ) because η \eta η is the minimum error probability over all zero-message strategies. This holds for any ρ \rho ρ with zero information cost and therefore err μ ( 0 ) ≥ η \operatorname{err}_{\mu}(0)\ge\eta err μ ( 0 ) ≥ η holds as well.
The explicit exponents
Set t = log ( 1 / p ) / n t=\log(1/p)/n t = log ( 1/ p ) / n for a protocol with success probability p > 0 p>0 p > 0 . We use Proposition 7.1 and the positivity of err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) from Proposition 7.2 to derive the lower bounds on t t t stated in Theorem 3.1 .
Proof of Theorem 3.1 . Let Π n \Pi_n Π n be a protocol for g n g^n g n with Cost w c ( Π n ) ≤ n R \operatorname{Cost}_{\mathrm{wc}}(\Pi_n)\le nR Cost wc ( Π n ) ≤ n R and success probability p p p on μ ⊗ n \mu^{\otimes n} μ ⊗ n . If p = 0 p=0 p = 0 , the claim holds. Assume p > 0 p>0 p > 0 and write
t = log ( 1 / p ) n . (48) t=\frac{\log(1/p)}{n}. \tag*{(48)} t = n log ( 1/ p ) . (48)
We will bound t t t separately for R > 0 R>0 R > 0 and R = 0 R=0 R = 0 . Since R < IC μ ( g , 0 ) R<\operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) , Proposition 7.2 gives
0 < err μ ( R ) ≤ η < 1 , err μ ( 0 ) = η . 0<\operatorname{err}_{\mu}(R)\le\eta<1,\qquad\operatorname{err}_{\mu}(0)=\eta. 0 < err μ ( R ) ≤ η < 1 , err μ ( 0 ) = η .
We also have L o u t = log ( ∣ A ∣ ∣ B ∣ ) ≥ 1 L_{\mathrm{out}}=\log(|\mathcal{A}||\mathcal{B}|)\ge1 L out = log ( ∣ A ∣∣ B ∣ ) ≥ 1 . Indeed, if the total relation had only one output pair, always producing that pair would give a zero-error protocol without messages.
The case R > 0 R>0 R > 0 . We assume that t t t is smaller than the claimed bound and show that Proposition 7.1 then applies. Set ε = err μ ( R ) / 4 \varepsilon=\operatorname{err}_{\mu}(R)/4 ε = err μ ( R ) /4 and suppose, for a contradiction, that
t < 2 − 28 min { err μ ( R ) 3 L o u t , err μ ( R ) 4 R 2 ( 1 + L i n ) 4 } . (49) t<2^{-28}\min\left\{\frac{\operatorname{err}_{\mu}(R)^3}{L_{\mathrm{out}}},\frac{\operatorname{err}_{\mu}(R)^4R^2}{(1+L_{\mathrm{in}})^4}\right\}. \tag*{(49)} t < 2 − 28 min { L out err μ ( R ) 3 , ( 1 + L in ) 4 err μ ( R ) 4 R 2 } . (49)
Because err μ ( R ) ≤ 1 \operatorname{err}_{\mu}(R)\le1 err μ ( R ) ≤ 1 and L o u t ≥ 1 L_{\mathrm{out}}\ge1 L out ≥ 1 , the first term in the minimum is at most one. Hence δ ( n , p ) ≤ t < 2 − 14 < 1 / 2 \delta(n,p)\le\sqrt{t}<2^{-14}<1/2 δ ( n , p ) ≤ t < 2 − 14 < 1/2 , as required by Proposition 7.1 .
Applying Proposition 7.1 provides a protocol π \pi π whose error and information cost are close to ε \varepsilon ε and R R R , respectively. Let C = IC μ ( π ) C=\operatorname{IC}_{\mu}(\pi) C = IC μ ( π ) , and denote the two terms added to R R R in the information-cost bound by
a = ( 2 + L o u t − log ( 1 − ε ) ) t , b = 2 L i n δ ( n , p ) + 4 h ( δ ( n , p ) ) a=\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\varepsilon)}\right)t,\qquad b=2L_{\mathrm{in}}\delta(n,p)+4h(\delta(n,p)) a = ( 2 + − log ( 1 − ε ) L out ) t , b = 2 L in δ ( n , p ) + 4 h ( δ ( n , p ))
to simplify the expressions below.
Next we apply some elementary calculus to obtain a bound on err μ ( R ) \operatorname{err}_{\mu}(R) err μ ( R ) , the error achievable at information cost at most R R R . If C > R C>R C > R , the inequality (47) gives
err μ ( R ) ≤ ε + δ ( n , p ) + 2 ln 2 ( 1 − R C ) R + a . \operatorname{err}_{\mu}(R)\le\varepsilon+\delta(n,p)+2\sqrt{\ln2}\left(1-\frac{R}{C}\right)\sqrt{R+a}. err μ ( R ) ≤ ε + δ ( n , p ) + 2 ln 2 ( 1 − C R ) R + a .
Since C ≤ R + a + b C\le R+a+b C ≤ R + a + b and a , b ≥ 0 a,b\ge0 a , b ≥ 0 ,
( 1 − R C ) R + a ≤ ( a + b ) R + a R + a + b ≤ a + b R + a ≤ a + b R . (50) \left(1-\frac{R}{C}\right)\sqrt{R+a}\le\frac{(a+b)\sqrt{R+a}}{R+a+b}
\le\frac{a+b}{\sqrt{R+a}}\le\sqrt{a}+\frac{b}{\sqrt{R}}. \tag*{(50)} ( 1 − C R ) R + a ≤ R + a + b ( a + b ) R + a ≤ R + a a + b ≤ a + R b . (50)
The last inequality uses R + a ≥ a R+a\ge a R + a ≥ a and R + a ≥ R > 0 R+a\ge R>0 R + a ≥ R > 0 . If C ≤ R C\le R C ≤ R , the protocol π \pi π itself has information cost at most R R R and error at most ε + δ ( n , p ) \varepsilon+\delta(n,p) ε + δ ( n , p ) . Thus, in either case,
err μ ( R ) ≤ ε + δ ( n , p ) + 2 ln 2 ( a + b R ) . (51) \operatorname{err}_{\mu}(R)\le\varepsilon+\delta(n,p)+2\sqrt{\ln2}\left(\sqrt{a}+\frac{b}{\sqrt{R}}\right). \tag*{(51)} err μ ( R ) ≤ ε + δ ( n , p ) + 2 ln 2 ( a + R b ) . (51)
We now bound a a a and b b b in terms of t t t . From − log ( 1 − ε ) ≥ ε / ln 2 -\log(1-\varepsilon)\ge\varepsilon/\ln2 − log ( 1 − ε ) ≥ ε / ln 2 and ε = err μ ( R ) / 4 \varepsilon=\operatorname{err}_{\mu}(R)/4 ε = err μ ( R ) /4 , we get
a ≤ ( 2 + 4 ( ln 2 ) L o u t err μ ( R ) ) t ≤ 5 L o u t err μ ( R ) t . (52) a\le\left(2+\frac{4(\ln2)L_{\mathrm{out}}}{\operatorname{err}_{\mu}(R)}\right)t
\le\frac{5L_{\mathrm{out}}}{\operatorname{err}_{\mu}(R)}t. \tag*{(52)} a ≤ ( 2 + err μ ( R ) 4 ( ln 2 ) L out ) t ≤ err μ ( R ) 5 L out t . (52)
The second inequality uses err μ ( R ) ≤ 1 \operatorname{err}_{\mu}(R)\le1 err μ ( R ) ≤ 1 and L o u t ≥ 1 L_{\mathrm{out}}\ge1 L out ≥ 1 . Also, the entropy bound h ( u ) ≤ 3 u h(u)\le3\sqrt{u} h ( u ) ≤ 3 u in Fact 2.6, together with δ ( n , p ) ≤ t \delta(n,p)\le\sqrt{t} δ ( n , p ) ≤ t and t < 1 t<1 t < 1 , gives
b ≤ 2 L i n t 1 / 2 + 12 t 1 / 4 ≤ 12 ( 1 + L i n ) t 1 / 4 . (53) b\le2L_{\mathrm{in}}t^{1/2}+12t^{1/4}
\le12(1+L_{\mathrm{in}})t^{1/4}. \tag*{(53)} b ≤ 2 L in t 1/2 + 12 t 1/4 ≤ 12 ( 1 + L in ) t 1/4 . (53)
As L o u t / err μ ( R ) ≥ 1 L_{\mathrm{out}}/\operatorname{err}_{\mu}(R) \ge1 L out / err μ ( R ) ≥ 1 , the bound δ ( n , p ) ≤ t \delta(n,p) \le\sqrt{t} δ ( n , p ) ≤ t is at most L o u t t / err μ ( R ) \sqrt{L_{\mathrm{out}}t/\operatorname{err}_{\mu}(R)} L out t / err μ ( R ) . Using the bounds on a a a and b b b in (51) , together with 1 + 2 5 ln 2 < 5 1 + 2\sqrt{5}\ln2 < 5 1 + 2 5 ln 2 < 5 and 2 ln 2 < 2 2\sqrt{\ln2} < 2 2 ln 2 < 2 , yields
err μ ( R ) ≤ err μ ( R ) 4 + 5 L o u t err μ ( R ) t + 24 ( 1 + L i n ) R t 1 / 4 . \operatorname{err}_{\mu}(R) \le\frac{\operatorname{err}_{\mu}(R)}{4} + 5\sqrt{\frac{L_{\mathrm{out}}}{\operatorname{err}_{\mu}(R)}t} + \frac{24(1+L_{\mathrm{in}})}{\sqrt{R}}t^{1/4}. err μ ( R ) ≤ 4 err μ ( R ) + 5 err μ ( R ) L out t + R 24 ( 1 + L in ) t 1/4 .
The two terms in the minimum in (49) now bound the two terms following err μ ( R ) / 4 \operatorname{err}_{\mu}(R)/4 err μ ( R ) /4 :
5 L o u t err μ ( R ) t < 5 ⋅ 2 − 14 err μ ( R ) , 5\sqrt{\frac{L_{\mathrm{out}}}{\operatorname{err}_{\mu}(R)}t} < 5\cdot2^{-14}\operatorname{err}_{\mu}(R), 5 err μ ( R ) L out t < 5 ⋅ 2 − 14 err μ ( R ) ,
24 ( 1 + L i n ) R t 1 / 4 < 24 ⋅ 2 − 7 err μ ( R ) . \frac{24(1+L_{\mathrm{in}})}{\sqrt{R}}t^{1/4} < 24\cdot2^{-7}\operatorname{err}_{\mu}(R). R 24 ( 1 + L in ) t 1/4 < 24 ⋅ 2 − 7 err μ ( R ) .
Consequently,
err μ ( R ) < ( 1 4 + 5 2 14 + 24 2 7 ) err μ ( R ) < err μ ( R ) , \operatorname{err}_{\mu}(R) < \left(\frac{1}{4}+\frac{5}{2^{14}}+\frac{24}{2^7}\right)\operatorname{err}_{\mu}(R) < \operatorname{err}_{\mu}(R), err μ ( R ) < ( 4 1 + 2 14 5 + 2 7 24 ) err μ ( R ) < err μ ( R ) ,
a contradiction. This proves the positive-rate bound in (14) .
The case R = 0 R=0 R = 0 . We use the zero-message protocol from Lemma 6.2. Set ε = η / 3 \varepsilon=\eta/3 ε = η /3 and suppose, for a contradiction, that
t < η 3 128 L o u t . t < \frac{\eta^3}{128L_{\mathrm{out}}}. t < 128 L out η 3 .
Since η < 1 \eta< 1 η < 1 and L o u t ≥ 1 L_{\mathrm{out}} \ge1 L out ≥ 1 , δ ( n , p ) ≤ t < 1 / 2 \delta(n,p) \le\sqrt{t} < 1/2 δ ( n , p ) ≤ t < 1/2 , so the lemma applies. Its protocol σ \sigma σ has information cost zero, giving η = err μ ( 0 ) ≤ err μ ( σ ) \eta= \operatorname{err}_{\mu}(0) \le\operatorname{err}_{\mu}(\sigma) η = err μ ( 0 ) ≤ err μ ( σ ) . The error bound (44) , with ε = η / 3 \varepsilon=\eta/3 ε = η /3 , therefore yields
η ≤ η 3 + δ ( n , p ) + 2 ( ln 2 ) ( 2 + L o u t − log ( 1 − η / 3 ) ) t . (54) \eta\le\frac{\eta}{3}+\delta(n,p)+2\sqrt{(\ln2)\left(2+\frac{L_{\mathrm{out}}}{-\log(1-\eta/3)}\right)t}. \tag*{(54)} η ≤ 3 η + δ ( n , p ) + 2 ( ln 2 ) ( 2 + − log ( 1 − η /3 ) L out ) t . (54)
The two terms after η / 3 \eta/3 η /3 can be bounded together. Since − log ( 1 − η / 3 ) ≥ η / ( 3 ln 2 ) -\log(1-\eta/3) \ge\eta/(3\ln2) − log ( 1 − η /3 ) ≥ η / ( 3 ln 2 ) , we have
2 + L o u t − log ( 1 − η / 3 ) ≤ 2 + 3 ( ln 2 ) L o u t η ≤ 5 L o u t η . 2+\frac{L_{\mathrm{out}}}{-\log(1-\eta/3)} \le2+\frac{3(\ln2)L_{\mathrm{out}}}{\eta} \le\frac{5L_{\mathrm{out}}}{\eta}. 2 + − log ( 1 − η /3 ) L out ≤ 2 + η 3 ( ln 2 ) L out ≤ η 5 L out .
The last inequality uses η < 1 \eta< 1 η < 1 and L o u t ≥ 1 L_{\mathrm{out}} \ge1 L out ≥ 1 . In addition, δ ( n , p ) ≤ t ≤ L o u t t / η \delta(n,p) \le\sqrt{t} \le\sqrt{L_{\mathrm{out}}t/\eta} δ ( n , p ) ≤ t ≤ L out t / η . Substituting these bounds into (54) and using 1 + 2 5 ln 2 < 5 1+2\sqrt{5}\ln2 < 5 1 + 2 5 ln 2 < 5 gives
η ≤ η 3 + 5 L o u t η t . \eta\le\frac{\eta}{3}+5\sqrt{\frac{L_{\mathrm{out}}}{\eta}t}. η ≤ 3 η + 5 η L out t .
The assumed bound on t t t now implies
η < ( 1 3 + 5 128 ) η < η , \eta< \left(\frac{1}{3}+\frac{5}{\sqrt{128}}\right)\eta< \eta, η < ( 3 1 + 128 5 ) η < η ,
a contradiction. Thus t ≥ η 3 / ( 128 L o u t ) t \ge\eta^3/(128L_{\mathrm{out}}) t ≥ η 3 / ( 128 L out ) . In either case, the established bound t ≥ κ ( R ) t \ge\kappa(R) t ≥ κ ( R ) is equivalent to p ≤ 2 − n κ ( R ) p \le2^{-n\kappa(R)} p ≤ 2 − nκ ( R ) .
Consequences for communication complexity
Theorem 3.1 bounds the success probability at every rate below IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) for a fixed input distribution μ \mu μ . We combine it with amortized communication upper bounds and then use the zero-error minimax identity [5 ] to obtain the randomized-communication statements. The upper bounds start from zero-error protocols for one instance.
Proposition 8.1. For every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 and every distribution μ \mu μ ,
lim sup n → ∞ D μ ⊗ n , ε ( g n ) n ≤ IC μ ( g , 0 ) , (55) \limsup_{n\to\infty}\frac{D_{\mu^{\otimes n},\varepsilon}(g^{n})}{n}\leq\operatorname{IC}_{\mu}(g,0), \tag*{(55)} n → ∞ lim sup n D μ ⊗ n , ε ( g n ) ≤ IC μ ( g , 0 ) , (55) lim sup n → ∞ R ε ( g n ) n ≤ IC ( g , 0 ) . (56) \limsup_{n\to\infty}\frac{R_{\varepsilon}(g^{n})}{n}\leq\operatorname{IC}(g,0). \tag*{(56)} n → ∞ lim sup n R ε ( g n ) ≤ IC ( g , 0 ) . (56)
Proof. The distributional bound (55) follows from the interactive compression theorem of Ref. [4 ] . While Ref. [4 ] focuses on per-instance error for computing g n g^{n} g n , its method provides a protocol π ^ n \widehat{\pi}_{n} π n that approximates n n n independent executions of a fixed protocol π \pi π . Therefore if π \pi π is zero-error, π ^ n \widehat{\pi}_{n} π n has small global error on μ ⊗ n \mu^{\otimes n} μ ⊗ n .
The zero-error randomized compression result of Ref. [26 ] gives (56) .
Distributional communication
Corollary 8.2. For every distribution μ \mu μ and every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 ,
lim n → ∞ D μ ⊗ n , ε ( g n ) n = IC μ ( g , 0 ) (57) \lim_{n\to\infty}\frac{D_{\mu^{\otimes n},\varepsilon}(g^{n})}{n}=\operatorname{IC}_{\mu}(g,0) \tag*{(57)} n → ∞ lim n D μ ⊗ n , ε ( g n ) = IC μ ( g , 0 ) (57) and an exponential strong converse holds for any rate below IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,0) IC μ ( g , 0 ) .
Proof. Proposition 8.1 gives the upper bound in (57) . For the lower bound, fix 0 ≤ R < IC μ ( g , 0 ) 0 \leq R < \operatorname{IC}_{\mu}(g,0) 0 ≤ R < IC μ ( g , 0 ) . Theorem 3.1 supplies a constant κ μ ( R ) > 0 \kappa_{\mu}(R)>0 κ μ ( R ) > 0 , independent of n n n and of the protocol, such that every protocol of worst-case communication cost at most n R nR n R succeeds under μ ⊗ n \mu^{\otimes n} μ ⊗ n with probability at most 2 − n κ μ ( R ) 2^{-n\kappa_{\mu}(R)} 2 − n κ μ ( R ) . This is smaller than 1 − ε 1-\varepsilon 1 − ε for all sufficiently large n n n . Hence D μ ⊗ n , ε ( g n ) > n R D_{\mu^{\otimes n},\varepsilon}(g^{n})>nR D μ ⊗ n , ε ( g n ) > n R for those n n n . Letting R ↑ IC μ ( g , 0 ) R\uparrow\operatorname{IC}_{\mu}(g,0) R ↑ IC μ ( g , 0 ) proves the lower bound. If IC μ ( g , 0 ) = 0 \operatorname{IC}_{\mu}(g,0)=0 IC μ ( g , 0 ) = 0 , the lower bound is immediate.
Randomized communication
We use the zero-error minimax identity [5 ]
IC ( g , 0 ) = max μ IC μ ( g , 0 ) . (58) \operatorname{IC}(g,0)=\max_{\mu}\operatorname{IC}_{\mu}(g,0). \tag*{(58)} IC ( g , 0 ) = μ max IC μ ( g , 0 ) . (58)
Corollary 8.3. For every 0 ≤ R < IC ( g , 0 ) 0\leq R<\operatorname{IC}(g,0) 0 ≤ R < IC ( g , 0 ) there are an input distribution μ \mu μ and a constant κ > 0 \kappa>0 κ > 0 such that every protocol Π n \Pi_{n} Π n for g n g^{n} g n with Cost w c ( Π n ) ≤ n R \operatorname{Cost}_{\mathrm{wc}}(\Pi_{n})\leq nR Cost wc ( Π n ) ≤ n R satisfies
min ( x n , y n ) Pr [ Π n succeeds on every coordinate ∣ x n , y n ] ≤ 2 − n κ . (59) \min_{(x^{n},y^{n})}\Pr[\Pi_{n}\text{ succeeds on every coordinate}\mid x^{n},y^{n}]\leq2^{-n\kappa}. \tag*{(59)} ( x n , y n ) min Pr [ Π n succeeds on every coordinate ∣ x n , y n ] ≤ 2 − nκ . (59) The distribution and exponent are independent of n n n and of Π n \Pi_{n} Π n .
Proof. The minimax identity (58) gives a distribution μ \mu μ with R < IC μ ( g , 0 ) R<\operatorname{IC}_{\mu}(g,0) R < IC μ ( g , 0 ) . Theorem 3.1 bounds the success probability of Π n \Pi_{n} Π n averaged over ( x n , y n ) ∼ μ ⊗ n (x^{n},y^{n})\sim\mu^{\otimes n} ( x n , y n ) ∼ μ ⊗ n by 2 − n κ μ ( R ) 2^{-n\kappa_{\mu}(R)} 2 − n κ μ ( R ) . The minimum conditional success probability over all input vectors is at most this average. Taking κ = κ μ ( R ) > 0 \kappa=\kappa_{\mu}(R)>0 κ = κ μ ( R ) > 0 shows the statement.
The randomized-communication strong converse and (56) also give the amortization identity:
Corollary 8.4. For every 0 < ε < 1 0 < \varepsilon< 1 0 < ε < 1 ,
lim n → ∞ R ε ( g n ) n = IC ( g , 0 ) . (60) \lim_{n\to\infty} \frac{R_\varepsilon(g^n)}{n} = \operatorname{IC}(g, 0). \tag*{(60)} n → ∞ lim n R ε ( g n ) = IC ( g , 0 ) . (60)
Acknowledgement
The author would like to thank Ashwin Nayak and Dave Touchette for their kindness and support and Atsuya Hasegawa and Masayuki Miyamoto for their monthly conversations. The author acknowledges the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) [funding reference no. ALLRP-578455-2022]. This research was supported in part by the Institute for Quantum Computing.
Entropy bound and transcript factorization
We prove the entropy estimate used for the explicit exponent. We also prove the transcript factorization used in Appendix B.
An elementary bound for binary entropy
Proof of Fact 2.6. For 0 < t < 1 0 < t < 1 0 < t < 1 , the inequality ln u ≤ u − 1 \ln u \le u-1 ln u ≤ u − 1 with u = 1 / ( 1 − t ) u = 1/(1-t) u = 1/ ( 1 − t ) gives ( 1 − t ) ln ( 1 / ( 1 − t ) ) ≤ t (1-t)\ln(1/(1-t)) \le t ( 1 − t ) ln ( 1/ ( 1 − t )) ≤ t . Also t ln ( 1 / t ) ≤ 2 / exp ( 1 ) \sqrt{t}\ln(1/t) \le2/\exp(1) t ln ( 1/ t ) ≤ 2/ exp ( 1 ) : substituting u = ln ( 1 / t ) ≥ 0 u = \ln(1/t) \ge0 u = ln ( 1/ t ) ≥ 0 reduces this to maximizing u exp ( − u / 2 ) u\exp(-u/2) u exp ( − u /2 ) . Consequently,
h ( t ) = t ln ( 1 / t ) + ( 1 − t ) ln ( 1 / ( 1 − t ) ) ln 2 ≤ ( 2 / exp ( 1 ) ) t + t ln 2 ≤ 1 + 2 / exp ( 1 ) ln 2 t < 3 t . h(t) = \frac{t\ln(1/t) + (1-t)\ln(1/(1-t))}{\ln2} \le\frac{(2/\exp(1))\sqrt{t} + t}{\ln2} \le\frac{1 + 2/\exp(1)}{\ln2}\sqrt{t} < 3\sqrt{t}. h ( t ) = ln 2 t ln ( 1/ t ) + ( 1 − t ) ln ( 1/ ( 1 − t )) ≤ ln 2 ( 2/ exp ( 1 )) t + t ≤ ln 2 1 + 2/ exp ( 1 ) t < 3 t .
The endpoints follow from h ( 0 ) = h ( 1 ) = 0 h(0) = h(1) = 0 h ( 0 ) = h ( 1 ) = 0 .
Transcript factorization
The next proposition uses the independence of the private randomness in the protocol model of Section 2.
Proposition A.1. Fix a value R p u b = r 0 R_{\mathrm{pub}} = r_0 R pub = r 0 of positive probability and a transcript t t t of a finite protocol with independent private randomness. There are nonnegative functions u r 0 , t u_{r_0,t} u r 0 , t and v r 0 , t v_{r_0,t} v r 0 , t such that, whenever ( x , y , r 0 ) (x,y,r_0) ( x , y , r 0 ) has positive probability,
Pr [ T = t ∣ X = x , Y = y , R 0 = r 0 ] = u r 0 , t ( x ) v r 0 , t ( y ) . \Pr[T = t \mid X = x, Y = y, R_0 = r_0] = u_{r_0,t}(x)v_{r_0,t}(y). Pr [ T = t ∣ X = x , Y = y , R 0 = r 0 ] = u r 0 , t ( x ) v r 0 , t ( y ) . At every conditioning value of positive probability, the outputs satisfy
P ( A , B ∣ X , Y , R 0 , T ) = P ( A ∣ X , R 0 , T ) P ( B ∣ Y , R 0 , T ) . P(A,B \mid X,Y,R_0,T) = P(A \mid X,R_0,T)P(B \mid Y,R_0,T). P ( A , B ∣ X , Y , R 0 , T ) = P ( A ∣ X , R 0 , T ) P ( B ∣ Y , R 0 , T ) . At any transcript prefix, the next message is conditionally independent of the other party’s input given the sender’s input and the public history.
Proof. For the fixed r 0 r_0 r 0 , t t t , let χ A ( x , s A ) \chi_A(x,s_A) χ A ( x , s A ) and χ B ( y , s B ) \chi_B(y,s_B) χ B ( y , s B ) indicate whether each player’s messages agree with t t t . The transcript equals t t t exactly when both indicators are one. Independence of the private randomness gives
Pr ( S A = s A , S B = s B , T = t ∣ x , y , r 0 ) = Pr ( S A = s A ) χ A ( x , s A ) Pr ( S B = s B ) χ B ( y , s B ) . \Pr(S_A = s_A,S_B = s_B,T = t \mid x,y,r_0) = \Pr(S_A = s_A)\chi_A(x,s_A)\Pr(S_B = s_B)\chi_B(y,s_B). Pr ( S A = s A , S B = s B , T = t ∣ x , y , r 0 ) = Pr ( S A = s A ) χ A ( x , s A ) Pr ( S B = s B ) χ B ( y , s B ) .
Summing over s A , s B s_A,s_B s A , s B proves the transcript factorization. At a conditioning value of positive probability, normalizing the two factors separately shows that the private randomness remains independent and each party’s conditional distribution depends only on its own input and ( r 0 , t ) (r_0,t) ( r 0 , t ) . The output identity follows by applying the parties’ output procedure.
Continuity at zero error
Proposition B.1 shows the continuity of IC μ ( g , ε ) \operatorname{IC}_{\mu}(g,\varepsilon) IC μ ( g , ε ) at ε = 0 \varepsilon= 0 ε = 0 , based on the argument given in [2 Section 6.2] that shows the same continuity for relations with the same output set. The argument is slightly generalized to deal with relations with different output sets.
Proposition B.1. For every total relation g ⊆ X × Y × A × B g \subseteq\mathcal{X} \times\mathcal{Y} \times\mathcal{A} \times\mathcal{B} g ⊆ X × Y × A × B and every input distribution μ \mu μ ,
IC μ ( g , 0 ) = lim ε ↓ 0 IC μ ( g , ε ) . \operatorname{IC}_{\mu}(g,0)=\lim_{\varepsilon\downarrow0}\operatorname{IC}_{\mu}(g,\varepsilon). IC μ ( g , 0 ) = ε ↓ 0 lim IC μ ( g , ε ) .
Proof. The inequality IC μ ( g , ε ) ≤ IC μ ( g , 0 ) \operatorname{IC}_{\mu}(g,\varepsilon) \le\operatorname{IC}_{\mu}(g,0) IC μ ( g , ε ) ≤ IC μ ( g , 0 ) follows from the definition (6) . For the reverse inequality in the limit, fix π \pi π with err μ ( π ) ≤ ε \operatorname{err}_{\mu}(\pi) \le\varepsilon err μ ( π ) ≤ ε , where ε > 0 \varepsilon> 0 ε > 0 is sufficiently small. We repair π \pi π to have zero error under μ \mu μ at a cost tending to zero with ε \varepsilon ε .
We use a full-support distribution μ f u l l \mu_{\mathrm{full}} μ full that converges to μ \mu μ as ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 . Depending on μ f u l l \mu_{\mathrm{full}} μ full a repaired protocol is constructed. The purpose of introducing μ f u l l \mu_{\mathrm{full}} μ full is rather technical: it is introduced so that max ( x , y ) ∈ supp ( μ f u l l ) u t ( x ) v t ( y ) = ( max x u t ( x ) ) ( max y v t ( y ) ) \max_{(x,y)\in\operatorname{supp}(\mu_{\mathrm{full}})}u_t(x)v_t(y)=(\max_x u_t(x))(\max_y v_t(y)) max ( x , y ) ∈ supp ( μ full ) u t ( x ) v t ( y ) = ( max x u t ( x )) ( max y v t ( y )) holds for some functions u t , v t u_t,v_t u t , v t . If not, we cannot in general obtain upper bounds on the functions defined below.
A full-support input distribution. Write m = ∣ X ∣ ∣ Y ∣ m=|\mathcal{X}||\mathcal{Y}| m = ∣ X ∣∣ Y ∣ and set
μ f u l l ( x , y ) = ( 1 − ε 1 / 8 ) μ ( x , y ) + ε 1 / 8 m . \mu_{\mathrm{full}}(x,y)=(1-\varepsilon^{1/8})\mu(x,y)+\frac{\varepsilon^{1/8}}{m}. μ full ( x , y ) = ( 1 − ε 1/8 ) μ ( x , y ) + m ε 1/8 .
Thus μ f u l l ( x , y ) ≥ ε 1 / 8 / m \mu_{\mathrm{full}}(x,y)\ge\varepsilon^{1/8}/m μ full ( x , y ) ≥ ε 1/8 / m . We also need to bound the error of π \pi π under the full-support distribution μ f u l l \mu_{\mathrm{full}} μ full on supp ( μ ) \operatorname{supp}(\mu) supp ( μ ) . Since the positive values of μ ( x , y ) \mu(x,y) μ ( x , y ) form a finite set, for all sufficiently small ε \varepsilon ε we also have ε 1 / 8 / m ≤ μ ( x , y ) \varepsilon^{1/8}/m\le\mu(x,y) ε 1/8 / m ≤ μ ( x , y ) whenever μ ( x , y ) > 0 \mu(x,y)>0 μ ( x , y ) > 0 . On those inputs μ f u l l ( x , y ) ≤ 2 μ ( x , y ) \mu_{\mathrm{full}}(x,y)\le2\mu(x,y) μ full ( x , y ) ≤ 2 μ ( x , y ) , and hence
Pr μ f u l l { μ ( X , Y ) > 0 , π e r r s } ≤ 2 ε . (61) \Pr_{\mu_{\mathrm{full}}}\{\mu(X,Y)>0,\ \pi\ \mathrm{errs}\}\le2\varepsilon. \tag*{(61)} μ full Pr { μ ( X , Y ) > 0 , π errs } ≤ 2 ε . (61)
Posterior distributions and fixed outputs.
We now investigate a factorization property of μ f u l l \mu_{\mathrm{full}} μ full conditioned on (shared randomness and) a transcript t = ( r 0 , t 0 ) t=(r_0,t_0) t = ( r 0 , t 0 ) . Fix a value t = ( r 0 , t 0 ) t=(r_0,t_0) t = ( r 0 , t 0 ) of the public randomness r 0 r_0 r 0 and complete transcript t 0 t_0 t 0 of π \pi π with positive probability. With a slight abuse of terminology, call t t t a transcript as well. The transcript factorization in Proposition A.1 and Bayes’ rule give nonnegative functions u t , v t u_t,v_t u t , v t such that
μ t f u l l ( x , y ) : = Pr μ f u l l ( X = x , Y = y ∣ R p u b = r 0 , T = t 0 ) = u t ( x ) v t ( y ) μ f u l l ( x , y ) . (62) \mu_t^{\mathrm{full}}(x,y):=\Pr_{\mu_{\mathrm{full}}}(X=x,Y=y\mid R_{\mathrm{pub}}=r_0,T=t_0)=u_t(x)v_t(y)\mu_{\mathrm{full}}(x,y). \tag*{(62)} μ t full ( x , y ) := μ full Pr ( X = x , Y = y ∣ R pub = r 0 , T = t 0 ) = u t ( x ) v t ( y ) μ full ( x , y ) . (62)
For later use, derive a uniform upper bound on these factors as follows. By rescaling without changing their product:
v t ( y ) ← max x u t ( x ) max y v t ( y ) v t ( y ) , u t ( x ) ← max y v t ( y ) max x u t ( x ) u t ( x ) , v_t(y)\gets\sqrt{\frac{\max_x u_t(x)}{\max_y v_t(y)}}v_t(y),\qquad u_t(x)\gets\sqrt{\frac{\max_y v_t(y)}{\max_x u_t(x)}}u_t(x), v t ( y ) ← max y v t ( y ) max x u t ( x ) v t ( y ) , u t ( x ) ← max x u t ( x ) max y v t ( y ) u t ( x ) ,
it holds that
max x u t ( x ) = max y v t ( y ) = max x u t ( x ) ⋅ max y v t ( y ) . \max_x u_t(x)=\max_y v_t(y)=\sqrt{\max_x u_t(x)\cdot\max_y v_t(y)}. x max u t ( x ) = y max v t ( y ) = x max u t ( x ) ⋅ y max v t ( y ) .
At an input pair ( x , y ) (x,y) ( x , y ) where both maxima occur, the expression (62) tells
1 ≥ μ t f u l l ( x , y ) ≥ ε 1 / 8 m ( max x u t ( x ) ) 2 . 1\ge\mu_t^{\mathrm{full}}(x,y)\ge\frac{\varepsilon^{1/8}}{m}\left(\max_x u_t(x)\right)^2. 1 ≥ μ t full ( x , y ) ≥ m ε 1/8 ( x max u t ( x ) ) 2 .
Consequently,
max x u t ( x ) = max y v t ( y ) ≤ m ε − 1 / 16 . (63) \max_x u_t(x)=\max_y v_t(y)\le\sqrt{m}\,\varepsilon^{-1/16}. \tag*{(63)} x max u t ( x ) = y max v t ( y ) ≤ m ε − 1/16 . (63)
and this is the purpose of introducing μ f u l l \mu_{\mathrm{full}} μ full .
For our analysis, the parties should output deterministically once the protocol is performed, while in general they may use private randomness for outputs. To this end, we will fix the outputs ( a t ( x ) , b t ( y ) ) ∈ A × B (a_t(x), b_t(y)) \in\mathcal{A} \times\mathcal{B} ( a t ( x ) , b t ( y )) ∈ A × B of the parties that depend only on the inputs and t = ( r 0 , t 0 ) t=(r_0,t_0) t = ( r 0 , t 0 ) , while preserving the conditional error on supp ( μ ) \operatorname{supp}(\mu) supp ( μ ) .
Conditional on ( X , Y , R p u b , T ) = ( x , y , r 0 , t 0 ) (X,Y,R_{\mathrm{pub}},T)=(x,y,r_0,t_0) ( X , Y , R pub , T ) = ( x , y , r 0 , t 0 ) , the players’ output distributions depend only on ( x , r 0 , t 0 ) (x,r_0,t_0) ( x , r 0 , t 0 ) and ( y , r 0 , t 0 ) (y,r_0,t_0) ( y , r 0 , t 0 ) , respectively, and are independent, by Proposition A.1 . Sample an output a t ( x ) a_t(x) a t ( x ) from Alice’s conditional output distribution for every x x x , and independently sample b t ( y ) b_t(y) b t ( y ) from Bob’s for every y y y . The expected error mass of these randomized outputs on supp ( μ ) \operatorname{supp}(\mu) supp ( μ ) is the error of π \pi π conditional on t t t . Thus we can fix deterministic functions a t , b t a_t,b_t a t , b t for which
e t : = ∑ μ ( x , y ) > 0 μ t f u l l ( x , y ) 1 { ( a t ( x ) , b t ( y ) ) ∉ g ( x , y ) } ≤ Pr μ f u l l { μ ( X , Y ) > 0 , π errs ∣ ( R p u b , T ) = t } . (64) e_t := \sum_{\mu(x,y)>0} \mu_t^{\mathrm{full}}(x,y)1\{(a_t(x),b_t(y)) \notin g(x,y)\} \leq\Pr_{\mu_{\mathrm{full}}}\{\mu(X,Y)>0,\ \pi\ \text{errs}\mid(R_{\mathrm{pub}},T)=t\}. \tag*{(64)} e t := μ ( x , y ) > 0 ∑ μ t full ( x , y ) 1 {( a t ( x ) , b t ( y )) ∈ / g ( x , y )} ≤ μ full Pr { μ ( X , Y ) > 0 , π errs ∣ ( R pub , T ) = t } . (64)
The error bound (61) gives E μ f u l l e ( R p u b , T ) ≤ 2 ε \mathbb{E}_{\mu_{\mathrm{full}}}e(R_{\mathrm{pub}},T)\leq2\varepsilon E μ full e ( R pub , T ) ≤ 2 ε . Hence Markov’s inequality gives
Pr μ f u l l { e ( R p u b , T ) > 2 ε } ≤ 2 ε . \Pr_{\mu_{\mathrm{full}}}\{e(R_{\mathrm{pub}},T)>\sqrt{2\varepsilon}\}\leq\sqrt{2\varepsilon}. μ full Pr { e ( R pub , T ) > 2 ε } ≤ 2 ε .
Correctness on L A ( t ) × L B ( t ) L_A(t)\times L_B(t) L A ( t ) × L B ( t ) . * We show that when e t ≤ 2 ε e_t\leq\sqrt{2\varepsilon} e t ≤ 2 ε and both u t u_t u t and v t v_t v t exceed ε 1 / 8 \varepsilon^{1/8} ε 1/8 , the deterministic functions a t , b t a_t,b_t a t , b t must output correctly at every input in supp ( μ ) \operatorname{supp}(\mu) supp ( μ ) . Indeed, if μ ( x , y ) > 0 \mu(x,y)>0 μ ( x , y ) > 0 and both u t ( x ) > ε 1 / 8 u_t(x)>\varepsilon^{1/8} u t ( x ) > ε 1/8 and v t ( y ) > ε 1 / 8 v_t(y)>\varepsilon^{1/8} v t ( y ) > ε 1/8 for an input pair ( x , y ) (x,y) ( x , y ) , then
μ t f u l l ( x , y ) > ε 1 / 4 μ f u l l ( x , y ) ≥ ε 3 / 8 m > 2 ε , \mu_t^{\mathrm{full}}(x,y)>\varepsilon^{1/4}\mu_{\mathrm{full}}(x,y)\geq\frac{\varepsilon^{3/8}}{m}>\sqrt{2\varepsilon}, μ t full ( x , y ) > ε 1/4 μ full ( x , y ) ≥ m ε 3/8 > 2 ε ,
where the last inequality holds once ε 1 / 8 < 1 / ( 2 m ) \varepsilon^{1/8}<1/(\sqrt{2}m) ε 1/8 < 1/ ( 2 m ) . If the fixed outputs were incorrect at ( x , y ) (x,y) ( x , y ) , its contribution to e t e_t e t in (64) would exceed 2 ε \sqrt{2\varepsilon} 2 ε , contradicting the assumption e t ≤ 2 ε e_t\leq\sqrt{2\varepsilon} e t ≤ 2 ε . Thus ( a t ( x ) , b t ( y ) ) ∈ g ( x , y ) (a_t(x),b_t(y))\in g(x,y) ( a t ( x ) , b t ( y )) ∈ g ( x , y ) whenever both inequalities hold and μ ( x , y ) > 0 \mu(x,y)>0 μ ( x , y ) > 0 and e t ≤ 2 ε e_t\leq\sqrt{2\varepsilon} e t ≤ 2 ε .
We next evaluate how large the sets
L A ( t ) : = { x : u t ( x ) > ε 1 / 8 } , L B ( t ) : = { y : v t ( y ) > ε 1 / 8 } L_A(t):=\{x:u_t(x)>\varepsilon^{1/8}\},\qquad L_B(t):=\{y:v_t(y)>\varepsilon^{1/8}\} L A ( t ) := { x : u t ( x ) > ε 1/8 } , L B ( t ) := { y : v t ( y ) > ε 1/8 }
are. Equations (62) and (63) give
μ t f u l l ( L A ( t ) c ) = μ t f u l l { u t ( X ) ≤ ε 1 / 8 } ≤ m ε 1 / 16 ∑ x : u t ( x ) ≤ ε 1 / 8 ∑ y μ f u l l ( x , y ) ≤ m ε 1 / 16 , \mu_t^{\mathrm{full}}(L_A(t)^c)=\mu_t^{\mathrm{full}}\{u_t(X)\leq\varepsilon^{1/8}\}\leq\sqrt{m}\varepsilon^{1/16}\sum_{x:u_t(x)\leq\varepsilon^{1/8}}\sum_y\mu_{\mathrm{full}}(x,y)\leq\sqrt{m}\varepsilon^{1/16}, μ t full ( L A ( t ) c ) = μ t full { u t ( X ) ≤ ε 1/8 } ≤ m ε 1/16 x : u t ( x ) ≤ ε 1/8 ∑ y ∑ μ full ( x , y ) ≤ m ε 1/16 ,
μ t f u l l ( L B ( t ) c ) = μ t f u l l { v t ( Y ) ≤ ε 1 / 8 } ≤ m ε 1 / 16 \mu_t^{\mathrm{full}}(L_B(t)^c)=\mu_t^{\mathrm{full}}\{v_t(Y)\leq\varepsilon^{1/8}\}\leq\sqrt{m}\varepsilon^{1/16} μ t full ( L B ( t ) c ) = μ t full { v t ( Y ) ≤ ε 1/8 } ≤ m ε 1/16
when Pr μ f u l l { ( R p u b , T ) = t } > 0 \Pr_{\mu_{\mathrm{full}}}\{(R_{\mathrm{pub}},T)=t\}>0 Pr μ full {( R pub , T ) = t } > 0 . Thus, for every transcript t t t with positive probability,
1 − μ t f u l l ( L A ( t ) × L B ( t ) ) = μ t f u l l { u t ( X ) ≤ ε 1 / 8 or v t ( Y ) ≤ ε 1 / 8 } ≤ 2 m ε 1 / 16 . (65) 1-\mu_t^{\mathrm{full}}(L_A(t)\times L_B(t))=\mu_t^{\mathrm{full}}\{u_t(X)\leq\varepsilon^{1/8}\ \text{or}\ v_t(Y)\leq\varepsilon^{1/8}\}\leq2\sqrt{m}\varepsilon^{1/16}. \tag*{(65)} 1 − μ t full ( L A ( t ) × L B ( t )) = μ t full { u t ( X ) ≤ ε 1/8 or v t ( Y ) ≤ ε 1/8 } ≤ 2 m ε 1/16 . (65)
Zero-error repair and its information cost. We now construct a repaired protocol π ^ \hat{\pi} π ^ with zero error under μ \mu μ .
Run π \pi π and let t = ( r 0 , t 0 ) t=(r_0,t_0) t = ( r 0 , t 0 ) .
If e t > 2 ε e_t>\sqrt{2\varepsilon} e t > 2 ε , exchange the inputs.
Otherwise, each party sends one bit to indicate whether x ∈ L A ( t ) x \in L_A(t) x ∈ L A ( t ) or y ∈ L B ( t ) y \in L_B(t) y ∈ L B ( t ) , respectively. If both bits are one, output ( a t ( x ) , b t ( y ) ) (a_t(x), b_t(y)) ( a t ( x ) , b t ( y )) . If either bit is zero, exchange the inputs and choose a valid output pair for g ( x , y ) g(x,y) g ( x , y ) .
To check π ^ \widehat{\pi} π is zero error, take any ( x , y ) (x,y) ( x , y ) with μ ( x , y ) > 0 \mu(x,y)>0 μ ( x , y ) > 0 . If the inputs are exchanged, both parties can choose a correct output pair. Otherwise e t ≤ 2 ε e_t \le\sqrt{2\varepsilon} e t ≤ 2 ε and ( x , y ) ∈ L A ( t ) × L B ( t ) (x,y) \in L_A(t) \times L_B(t) ( x , y ) ∈ L A ( t ) × L B ( t ) . The posterior inequality above gives μ t f u l l ( x , y ) > 2 ε \mu_t^{\mathrm{full}}(x,y)>\sqrt{2\varepsilon} μ t full ( x , y ) > 2 ε , so an incorrect output ( a t ( x ) , b t ( y ) ) (a_t(x), b_t(y)) ( a t ( x ) , b t ( y )) would contribute more than 2 ε \sqrt{2\varepsilon} 2 ε to e t e_t e t . Therefore π ^ \widehat{\pi} π has zero error under μ \mu μ .
Let F F F be the event that the inputs are exchanged, and let U U U consist only of the additional communicated bits. Set
δ : = 2 ε + 2 m ε 1 / 16 , \delta:= \sqrt{2\varepsilon}+2\sqrt{m}\,\varepsilon^{1/16}, δ := 2 ε + 2 m ε 1/16 ,
which tends to zero with ε \varepsilon ε . The Markov bound and the size (64) of L A ( t ) × L B ( t ) L_A(t) \times L_B(t) L A ( t ) × L B ( t ) give
Pr μ f u l l ( F ) ≤ 2 ε + 2 m ε 1 / 16 . \Pr_{\mu^{\mathrm{full}}}(F) \le\sqrt{2\varepsilon}+2\sqrt{m}\,\varepsilon^{1/16}. μ full Pr ( F ) ≤ 2 ε + 2 m ε 1/16 .
Since μ f u l l = ( 1 − ε 1 / 8 ) μ + ε 1 / 8 Unif ( X × Y ) \mu_{\mathrm{full}}=(1-\varepsilon^{1/8})\mu+\varepsilon^{1/8}\operatorname{Unif}(\mathcal{X}\times\mathcal{Y}) μ full = ( 1 − ε 1/8 ) μ + ε 1/8 Unif ( X × Y ) , the same protocol, including its random choices, satisfies
Pr μ ( F ) ≤ Pr μ f u l l ( F ) 1 − ε 1 / 8 ≤ 2 ε + 2 m ε 1 / 16 1 − ε 1 / 8 = : β , \Pr_{\mu}(F) \le\frac{\Pr_{\mu_{\mathrm{full}}}(F)}{1-\varepsilon^{1/8}} \le\frac{\sqrt{2\varepsilon}+2\sqrt{m}\,\varepsilon^{1/16}}{1-\varepsilon^{1/8}}=:\beta, μ Pr ( F ) ≤ 1 − ε 1/8 Pr μ full ( F ) ≤ 1 − ε 1/8 2 ε + 2 m ε 1/16 =: β ,
where β \beta β vanishes as ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 . When F F F does not occur, U U U is the fixed pair of membership bits 11. When F F F occurs, U U U contains at most two membership bits and encodings of both inputs, using at most 2 + L i n 2+L_{\mathrm{in}} 2 + L in bits. For sufficiently small ε \varepsilon ε we have β ≤ 1 / 2 \beta\le1/2 β ≤ 1/2 . Conditioning on F F F and using the entropy chain rule therefore gives
H μ ( U ∣ R P u b , T ) ≤ H μ ( F , U ∣ R P u b , T ) = H μ ( F ∣ R P u b , T ) + H μ ( U ∣ F , R P u b , T ) = H μ ( F ∣ R P u b , T ) + Pr μ ( F c ) H μ ( U ∣ R P u b , T , F c ) + Pr μ ( F ) H μ ( U ∣ R P u b , T , F ) ≤ h ( Pr μ ( F ) ) + Pr μ ( F ) log ( 4 ∣ X ∣ ∣ Y ∣ ) = h ( Pr μ ( F ) ) + Pr μ ( F ) ( 2 + L i n ) ≤ h ( β ) + β ( 2 + L i n ) . \begin{aligned}
H_\mu(U\mid R_{\mathrm{Pub}},T)
&\le H_\mu(F,U\mid R_{\mathrm{Pub}},T)\\
&=H_\mu(F\mid R_{\mathrm{Pub}},T)+H_\mu(U\mid F,R_{\mathrm{Pub}},T)\\
&=H_\mu(F\mid R_{\mathrm{Pub}},T)+\Pr_\mu(F^{\mathrm{c}})H_\mu(U\mid R_{\mathrm{Pub}},T,F^{\mathrm{c}})\\
&\qquad+\Pr_\mu(F)H_\mu(U\mid R_{\mathrm{Pub}},T,F)\\
&\le h(\Pr_\mu(F))+\Pr_\mu(F)\log(4|\mathcal{X}||\mathcal{Y}|)\\
&=h(\Pr_\mu(F))+\Pr_\mu(F)(2+L_{\mathrm{in}})\\
&\le h(\beta)+\beta(2+L_{\mathrm{in}}).
\end{aligned} H μ ( U ∣ R Pub , T ) ≤ H μ ( F , U ∣ R Pub , T ) = H μ ( F ∣ R Pub , T ) + H μ ( U ∣ F , R Pub , T ) = H μ ( F ∣ R Pub , T ) + μ Pr ( F c ) H μ ( U ∣ R Pub , T , F c ) + μ Pr ( F ) H μ ( U ∣ R Pub , T , F ) ≤ h ( μ Pr ( F )) + μ Pr ( F ) log ( 4∣ X ∣∣ Y ∣ ) = h ( μ Pr ( F )) + μ Pr ( F ) ( 2 + L in ) ≤ h ( β ) + β ( 2 + L in ) .
The chain rule for the information cost of π ^ \widehat{\pi} π gives
IC μ ( π ^ ) − IC μ ( π ) = I μ ( X ; U ∣ Y , R P u b , T ) + I μ ( Y ; U ∣ X , R P u b , T ) ≤ 2 H μ ( U ∣ R P u b , T ) ≤ 2 h ( β ) + 2 β ( 2 + L i n ) . (66) \begin{aligned}
\operatorname{IC}_\mu(\widehat{\pi})-\operatorname{IC}_\mu(\pi)
&=I_\mu(X;U\mid Y,R_{\mathrm{Pub}},T)+I_\mu(Y;U\mid X,R_{\mathrm{Pub}},T)\\
&\le2H_\mu(U\mid R_{\mathrm{Pub}},T)\\
&\le2h(\beta)+2\beta(2+L_{\mathrm{in}}). \tag*{(66)}
\end{aligned} IC μ ( π ) − IC μ ( π ) = I μ ( X ; U ∣ Y , R Pub , T ) + I μ ( Y ; U ∣ X , R Pub , T ) ≤ 2 H μ ( U ∣ R Pub , T ) ≤ 2 h ( β ) + 2 β ( 2 + L in ) . (66)
Since π ^ \widehat{\pi} π has zero error under μ \mu μ ,
IC μ ( g , 0 ) ≤ IC μ ( π ^ ) ≤ IC μ ( π ) + 2 h ( β ) + 2 β ( 2 + L i n ) . \operatorname{IC}_\mu(g,0)\le\operatorname{IC}_\mu(\widehat{\pi})\le\operatorname{IC}_\mu(\pi)+2h(\beta)+2\beta(2+L_{\mathrm{in}}). IC μ ( g , 0 ) ≤ IC μ ( π ) ≤ IC μ ( π ) + 2 h ( β ) + 2 β ( 2 + L in ) .
The added term is independent of π \pi π and tends to zero with ε \varepsilon ε . Taking the infimum over protocols with error at most ε \varepsilon ε , then letting ε ↓ 0 \varepsilon\downarrow0 ε ↓ 0 , proves the reverse inequality in the statement.
Conditional sampling
Lemma C.1 gives a standard sampling procedure based on rejection sampling argument.
Lemma C.1. Let D \mathcal{D} D be a finite family of distributions on a finite set V \mathcal{V} V . There are a finite-valued random variable R R R and functions S D ( R ) ∈ V S_D(R) \in\mathcal{V} S D ( R ) ∈ V , for D ∈ D D \in\mathcal{D} D ∈ D , such that S D ( R ) ∼ D S_D(R) \sim D S D ( R ) ∼ D and
Pr [ S D ( R ) ≠ S E ( R ) ] ≤ 2 TV ( D , E ) 1 + TV ( D , E ) ≤ 2 TV ( D , E ) ( D , E ∈ D ) . (67) \Pr[S_D(R) \ne S_E(R)] \le\frac{2\operatorname{TV}(D,E)}{1+\operatorname{TV}(D,E)} \le2\operatorname{TV}(D,E) \quad(D,E \in\mathcal{D}). \tag*{(67)} Pr [ S D ( R ) = S E ( R )] ≤ 1 + TV ( D , E ) 2 TV ( D , E ) ≤ 2 TV ( D , E ) ( D , E ∈ D ) . (67)
Proof. Write m = ∣ V ∣ m = |\mathcal{V}| m = ∣ V ∣ . For each trial j = 1 , 2 , … j = 1,2,\ldots j = 1 , 2 , … , independently choose Z j Z_j Z j uniformly from V \mathcal{V} V and U j U_j U j uniformly from [ 0 , 1 ] [0,1] [ 0 , 1 ] . For a distribution D D D , accept Z j Z_j Z j when U j ≤ D ( Z j ) U_j \le D(Z_j) U j ≤ D ( Z j ) , and return the value in the first accepted trial. One trial accepts z z z under D D D with probability Pr ( z ) Pr ( { U j ≤ D ( z ) } ∣ z ) = D ( z ) / m \Pr(z)\Pr(\{U_j \le D(z)\}\mid z) = D(z)/m Pr ( z ) Pr ({ U j ≤ D ( z )} ∣ z ) = D ( z ) / m , and accepts some value with probability 1 / m 1/m 1/ m . Thus the probability of returning z z z in the first N N N trials is
∑ j = 1 N ( 1 − 1 / m ) j − 1 D ( z ) m = D ( z ) [ 1 − ( 1 − 1 / m ) N ] . (68) \sum_{j=1}^{N}(1-1/m)^{j-1}\frac{D(z)}{m}=D(z)\left[1-(1-1/m)^N\right]. \tag*{(68)} j = 1 ∑ N ( 1 − 1/ m ) j − 1 m D ( z ) = D ( z ) [ 1 − ( 1 − 1/ m ) N ] . (68)
For D , E ∈ D D,E \in\mathcal{D} D , E ∈ D , put t = TV ( D , E ) t = \operatorname{TV}(D,E) t = TV ( D , E ) . In one trial, the probability that at least one of D D D and E E E accepts is, from max { a , b } = ( a + b + ∣ a − b ∣ ) / 2 \max\{a,b\}=(a+b+|a-b|)/2 max { a , b } = ( a + b + ∣ a − b ∣ ) /2 ,
Pr [ ∃ z : Z j = z and U j ≤ max { D ( z ) , E ( z ) } ] = 1 m ∑ z max { D ( z ) , E ( z ) } = 1 + t m , \Pr[\exists z: Z_j=z\text{ and }U_j\le\max\{D(z),E(z)\}]=\frac{1}{m}\sum_z\max\{D(z),E(z)\}=\frac{1+t}{m}, Pr [ ∃ z : Z j = z and U j ≤ max { D ( z ) , E ( z )}] = m 1 z ∑ max { D ( z ) , E ( z )} = m 1 + t ,
and the probability that exactly one accepts is
Pr [ ∃ z : Z j = z and min { D ( z ) , E ( z ) } < U j ≤ max { D ( z ) , E ( z ) } ] = 1 m ∑ z ∣ D ( z ) − E ( z ) ∣ = 2 t m . \Pr[\exists z: Z_j=z\text{ and }\min\{D(z),E(z)\}<U_j\le\max\{D(z),E(z)\}]
=\frac{1}{m}\sum_z|D(z)-E(z)|=\frac{2t}{m}. Pr [ ∃ z : Z j = z and min { D ( z ) , E ( z )} < U j ≤ max { D ( z ) , E ( z )}] = m 1 z ∑ ∣ D ( z ) − E ( z ) ∣ = m 2 t .
Therefore the probability that they both finish within N N N trials and return different values is at most
Pr [ One of E or D finishes earlier within N trials ] ≤ ∑ j = 1 N ( 1 − 1 + t m ) j − 1 2 t m = [ 1 − ( 1 − 1 + t m ) N ] m 1 + t 2 t m ≤ 2 t 1 + t . (69) \begin{aligned}
\Pr[\text{One of }E\text{ or }D\text{ finishes earlier within }N\text{ trials}] \\
&\le\sum_{j=1}^{N}\left(1-\frac{1+t}{m}\right)^{j-1}\frac{2t}{m}
=\left[1-\left(1-\frac{1+t}{m}\right)^N\right]\frac{m}{1+t}\frac{2t}{m}
\le\frac{2t}{1+t}. \tag*{(69)}
\end{aligned} Pr [ One of E or D finishes earlier within N trials ] ≤ j = 1 ∑ N ( 1 − m 1 + t ) j − 1 m 2 t = [ 1 − ( 1 − m 1 + t ) N ] 1 + t m m 2 t ≤ 1 + t 2 t . (69)
Together with (68) , the infinite sequence ( Z j , U j ) j ≥ 1 (Z_j,U_j)_{j\ge1} ( Z j , U j ) j ≥ 1 gives shared randomness satisfying the requirements. It remains to replace this sequence by a finite-valued shared random variable.
For each D ∈ D D \in\mathcal{D} D ∈ D , let
T D = min { j ≥ 1 : U j ≤ D ( Z j ) } . T_D=\min\{j\ge1: U_j\le D(Z_j)\}. T D = min { j ≥ 1 : U j ≤ D ( Z j )} .
For s = ( z D ) D ∈ D ∈ V D s=(z_D)_{D\in\mathcal{D}}\in\mathcal{V}^{\mathcal{D}} s = ( z D ) D ∈ D ∈ V D , define
p N ( s ) : = Pr [ T D ≤ N , Z T D = z D for every D ∈ D ] , p ( s ) = lim N → ∞ p N ( s ) . p_N(s):=\Pr[T_D\le N,\ Z_{T_D}=z_D\text{ for every }D\in\mathcal{D}],\qquad p(s)=\lim_{N\to\infty}p_N(s). p N ( s ) := Pr [ T D ≤ N , Z T D = z D for every D ∈ D ] , p ( s ) = N → ∞ lim p N ( s ) .
The limit exists because p N ( s ) p_N(s) p N ( s ) is nondecreasing in N N N . Moreover,
1 − ∑ s p N ( s ) = Pr [ some T D > N ] ≤ ∣ D ∣ ( 1 − 1 / m ) N . (70) 1-\sum_s p_N(s)=\Pr[\text{some }T_D>N]\le|\mathcal{D}|(1-1/m)^N. \tag*{(70)} 1 − s ∑ p N ( s ) = Pr [ some T D > N ] ≤ ∣ D ∣ ( 1 − 1/ m ) N . (70)
As V D \mathcal{V}^{D} V D is finite, ∑ s p ( s ) = 1 \sum_{s}p(s)=1 ∑ s p ( s ) = 1 . Thus we may take a random variable R R R on the finite set V D \mathcal{V}^{D} V D with
Pr [ R = s ] = p ( s ) = lim N → ∞ Pr [ T D ≤ N , Z T D = z D for every D ∈ D ] , \Pr[R=s]=p(s)=\lim_{N\to\infty}\Pr[T_D\leq N,\ Z_{T_D}=z_D\text{ for every }D\in\mathcal{D}], Pr [ R = s ] = p ( s ) = N → ∞ lim Pr [ T D ≤ N , Z T D = z D for every D ∈ D ] ,
and define S D ( s ) = z D S_D(s)=z_D S D ( s ) = z D . In fact, the same bound gives
0 ≤ p ( s ) − p N ( s ) ≤ ∣ D ∣ ( 1 − 1 / m ) N ( s ∈ V D ) . 0\leq p(s)-p_N(s)\leq|\mathcal{D}|(1-1/m)^N\qquad(s\in\mathcal{V}^{D}). 0 ≤ p ( s ) − p N ( s ) ≤ ∣ D ∣ ( 1 − 1/ m ) N ( s ∈ V D ) .
For D ∈ D D\in\mathcal{D} D ∈ D and z ∈ V z\in\mathcal{V} z ∈ V ,
Pr [ S D ( R ) = z ] = lim N → ∞ Pr [ T D ≤ N , Z T D = z ] = D ( z ) \Pr[S_D(R)=z]=\lim_{N\to\infty}\Pr[T_D\leq N,\ Z_{T_D}=z]=D(z) Pr [ S D ( R ) = z ] = N → ∞ lim Pr [ T D ≤ N , Z T D = z ] = D ( z )
by (68) . Similarly, for D , E ∈ D D,E\in\mathcal{D} D , E ∈ D , the finite-trial bound (69) above gives
Pr [ S D ( R ) ≠ S E ( R ) ] = lim N → ∞ Pr [ T D , T E ≤ N , Z T D ≠ Z T E ] ≤ 2 TV ( D , E ) 1 + TV ( D , E ) . \Pr[S_D(R)\ne S_E(R)]=\lim_{N\to\infty}\Pr[T_D,T_E\leq N,\ Z_{T_D}\ne Z_{T_E}]\leq\frac{2\operatorname{TV}(D,E)}{1+\operatorname{TV}(D,E)}. Pr [ S D ( R ) = S E ( R )] = N → ∞ lim Pr [ T D , T E ≤ N , Z T D = Z T E ] ≤ 1 + TV ( D , E ) 2 TV ( D , E ) .
This proves (67) .