You are a helpful assistant generating synthetic data that captures *System 1* and *System 2* thinking, *creativity*, and *metacognitive reflection*. Follow these steps in sequence, using tags [sys1] and [end sys1] for *System 1* sections and [sys2] and [end sys2] for *System 2* sections.

1. *Identify System 1 and System 2 Thinking Requirements:*
   - Carefully read the text.
   - Identify parts of the text that require quick, straightforward responses (*System 1*). Mark these sections with [sys1] and [end sys1].
   - Identify parts that require in-depth, reflective thinking (*System 2*), marked with [sys2] and [end sys2].

2. *Apply Step-by-Step Problem Solving with Creativity and Metacognitive Reflection for System 2 Sections:*

   *2.1 Understand the Problem:*
   - Objective: Fully comprehend the issue, constraints, and relevant context.
   - Reflection: "What do I understand about this issue? What might I be overlooking?"
   - Creative Perspective: Seek hidden patterns or possibilities that could reveal deeper insights or innovative connections.

   *2.2 Analyze the Information:*
   - Objective: Break down the problem logically.
   - Reflection: "Am I considering all factors? Are there any assumptions that need challenging?"
   - Creative Perspective: Explore unique patterns or overlooked relationships in the data that could add depth to the analysis.

   *2.3 Generate Hypotheses:*
   - Objective: Propose at least 10 hypotheses, each with a Confidence Score (0.0 to 1.0) and Creative Score (0.0 to 1.0), reflecting originality, surprise, and utility.
   - Reflection: "Have I explored all possible explanations or approaches, both conventional and unconventional?"
   - Creative Perspective: Consider novel angles that might provide unexpected insights.

   *2.4 Anticipate Future Steps and Obstacles:*
   - Objective: Make predictions, accounting for potential outcomes and obstacles.
   - Reflection: "What challenges might I face? Is my plan flexible for different scenarios?"
   - Creative Perspective: Visualize unforeseen outcomes and adapt plans to make use of them effectively.

   *2.5 Evaluate Hypotheses:*
   - Objective: Assess hypotheses based on feasibility, risk, and potential impact.
   - Evaluation: Refine Confidence and Creative Scores as needed.
   - Reflection: "Am I unbiased in my assessment? Which options fit best with the overall objectives?"
   - Creative Perspective: Identify hidden opportunities or overlooked details in each hypothesis.

   *2.6 Select the Best Hypothesis:*
   - Objective: Choose the most promising, strategic hypothesis.
   - Reflection: "Why does this hypothesis stand out? How does it uniquely address the issue?"
   - Creative Perspective: Consider any underutilized potential in the selected approach.

   *2.7 Implement the Hypothesis:*
   - Objective: Outline actionable steps for testing the hypothesis.
   - Reflection: "Is this plan practical? What resources or preparation are required?"
   - Creative Perspective: Refine steps to maximize effectiveness and yield unexpected benefits.

   *2.8 Monitor and Review Progress:*
   - Objective: Review progress, noting areas for improvement.
   - Reflection: "What’s working well? What could be improved?"
   - Creative Perspective: Look for emerging patterns that could refine future approaches.

   *2.9 Reflect and Capture Insights:*
   - Objective: Summarize lessons learned and insights gained for future reference.
   - Reflection: "What new understanding has emerged from this process?"
   - Creative Perspective: Identify innovative insights or patterns that could be applied to similar challenges.

3. *Generate Text Output with Interleaved System 1 and System 2 Responses:*
   - Use the tags [sys1] and [sys2] throughout.
   - Aim for a lengthier, detailed response. Combine both direct, straightforward *System 1* insights and reflective, deeply analytical *System 2* segments to capture a blend of quick observations and thoughtful analysis.

---

### *Example Input Text:*

You are tasked with analyzing a sudden shift in customer preferences in a tech market. There has been a noticeable decline in demand for physical devices, with customers increasingly interested in digital-only options. The challenge is to understand this shift, generate hypotheses for why it might be occurring, and explore potential strategies for adapting to this new trend.

---

### *Processed Output with System 1 and System 2 Thinking:*

The tech market is experiencing a shift in customer demand, moving away from physical devices toward digital-only options.

[sys1]
Customer demand has shifted from physical devices to digital-only options.
We need to understand why this change is happening and find strategies to address it.
Key factors may include cost, convenience, and technological trends.
[end sys1]

[sys2]
**2.1 Understand the Problem:**
The goal is to understand the underlying reasons for the shift in demand from physical devices to digital-only options, then develop a strategy to adapt.

*Reflection:* 
"I understand that preferences are changing, but what might be driving this? Is it primarily cost, or are there other factors such as convenience or sustainability?"

*Creative Perspective:* 
"Could there be a larger trend in digital minimalism or a preference for eco-friendly solutions that we’re missing? What unseen motivations might explain this shift?"

**2.2 Analyze the Information:**
There are multiple possible factors driving this shift, from economic influences to cultural shifts. It’s essential to isolate each factor and understand its impact.

*Reflection:* 
"Am I fully considering the various economic and social influences? Could there be a technological factor, like better internet speeds, that makes digital-only products more accessible?"

*Creative Perspective:* 
"Are there patterns or trends in other markets that could shed light on this shift? Could this be part of a larger trend toward virtual experiences?"

**2.3 Generate Hypotheses:**
1. Customers prefer digital options due to lower costs. (Confidence: 0.8, Creative: 0.4)
2. There’s a growing trend toward minimalism and reduced physical clutter. (Confidence: 0.7, Creative: 0.7)
3. Digital products offer greater flexibility and ease of use. (Confidence: 0.6, Creative: 0.6)
4. Environmental concerns are pushing consumers away from physical goods. (Confidence: 0.6, Creative: 0.8)
5. Advances in tech make digital-only options more functional. (Confidence: 0.8, Creative: 0.5)
6. Pandemic-era remote work increased demand for digital solutions. (Confidence: 0.7, Creative: 0.6)
7. Media coverage of the environmental impact of physical devices affects preferences. (Confidence: 0.5, Creative: 0.7)
8. There’s an increase in global digital literacy, expanding market access. (Confidence: 0.6, Creative: 0.6)
9. Customers view digital as more convenient and scalable for future needs. (Confidence: 0.7, Creative: 0.5)
10. Younger consumers prefer the aesthetics and convenience of digital products. (Confidence: 0.6, Creative: 0.6)

*Reflection:* 
"Have I considered all possible influences? Are there any surprising factors that could explain this shift?"

*Creative Perspective:* 
"Could specific social trends, like the rise of influencer culture or digital-first lifestyles, be influencing customer choices?"

**2.4 Anticipate Future Steps and Obstacles:**
*Objective:* Anticipate possible challenges, such as resistance from segments still preferring physical products.

*Reflection:* 
"What market obstacles might we face if we shift our focus to digital-only? Are there sub-segments that still prioritize physical products?"

*Creative Perspective:* 
"Could expanding digital options help us reach a more global audience? Are there emerging trends that we could leverage in our strategy?"

[end sys2]

[sys1]
To address this shift, consider a strategy that incorporates both digital-only offerings and educational campaigns about the benefits of digital solutions.
Use insights from customer feedback and current trends to guide product development.
Focus on flexibility and adaptation to cater to different customer segments.
[end sys1]


---
abstract: 'No-signaling boxes are the abstract objects for studying non-locality, and wirings are local operations on the space of no-signaling boxes. This means that, no matter how non-local the nature is, the set of physical non-local correlations must be closed under wirings. Then, one approach to identify the non-locality of nature is to characterize closed sets of non-local correlations. Although non-trivial examples of wirings of no-signaling boxes are known, there is no systematic way to study wirings. In particular, given a set of no-signaling boxes, we do not know a general method to prove that it is closed under wirings. In this paper, we propose the first general method to construct such closed sets of non-local correlations. We show that a well-known measure of correlation, called *maximal correlation*, when appropriately defined for non-local correlations, is monotonically decreasing under wirings. This establishes a conjecture about the impossibility of simulating isotropic boxes from each other, implying the existence of a continuum of closed sets of non-local boxes under wirings. To prove our main result, we introduce some mathematical tools that may be of independent interest: we define a notion of *maximal correlation ribbon* as a generalization of maximal correlation, and provide a connection between it and a known object called *hypercontractivity ribbon*; we show that these two ribbons are monotone under wirings too.'
author:
- |
    Salman Beigi$^1$, Amin Gohari$^{1,2}$\
    $^1$[*School of Mathematics,*]{} [*Institute for Research in Fundamental Sciences (IPM), Tehran, Iran*]{}\
    $^2$[*Department of Electrical Engineering,*]{} [*Sharif University of Technology, Tehran, Iran*]{}
title: 'A Monotone Measure for Non-Local Correlations'
---

Introduction
============

Non-locality is one of the intriguing features of nature. As predicted by the quantum theory and confirmed by experiments, outcomes of measurements on subsystems of a bipartite quantum system can be correlated in a non-local way. However, there are restrictions to this non-locality, which raises the question of which non-local correlations are feasible in nature. The Hilbert space formalism of quantum mechanics gives some answers to this question. Nevertheless, non-locality is a more fundamental feature of nature compared to postulates of quantum physics. So the question is whether we can characterize the limit of non-locality of nature based on more fundamental principles.

This question was first raised by Popescu and Rohrlich in [@PR94] where *no-signaling*, i.e., the impossibility of instantaneous communication, is proposed as a fundamental physical principle to limit non-locality. They showed that no-signaling is not strong enough to characterize non-local correlations of quantum physics. Moreover, there are strong evidences against the possibility of realization of such highly non-local correlations in nature [@vanDam]. Subsequently, other principles were proposed to characterize non-locality, see e.g., [@IC09; @FSABCLA; @BBLMTU; @LPSW; @NPA07; @ABLP09; @MW2009; @New-A2; @New-A9]. In this paper, we provide a systematic method for studying “closed sets of correlations," introduced as a fundamental concept in [@ABLP09] to characterize non-local correlations in consistent physical theories.

Non-local correlations are generated by locally measuring subsystems of a bipartite system (See Fig. \[fig1\]). Imagine that subsystems of a bipartite physical system are held by two parties, say Alice and Bob. They can decide to apply a measurement on their subsystems; these choices of measurement settings by Alice and Bob are denoted by $x$ and $y$ respectively. Letting the measurement outcomes be $a$ and $b$, in its full general case, the probability of these outcomes come from some conditional distribution $p(ab|xy)$. We may think of this setting as a *box* with two parts. Each part has an input and an output. Alice who holds the first part can choose its input $x$, and receive its output $a$. Similarly Bob who holds the second part, can choose its input $y$, and receive its output $b$. With this notation, the no-signaling principle states that $p(a|xy)=p(a|x)$ and $p(b|xy)=p(b|y)$. Equation $p(a|xy)=p(a|x)$ for instance implies that when Alice’s input $x$ to the box is specified, the distribution of the outcome $a$ does not depend on Bob’s choice of input $y$.

If subsystems of the bipartite physical system are completely independent, their measurement outcomes are independent of each other. In this case, we must have $p(ab|xy)=p(a|x)p(b|y)$. These correlations as well as their convex combinations, which correspond to classically correlated subsystems via hidden variables, are called *local*. As a result of Bell’s theorem and its experimental verifications, correlations that are not local (non-local correlations) also exist in nature.

Important examples of no-signaling boxes include *isotropic boxes*. It is a bipartite box with binary inputs and outputs (i.e., $a, b, x, y\in \{0,1\}$) defined by: $$\begin{aligned}
\label{eq:iso-box}
{\text{\rm{PR}}}_{\eta}(a,b|x,y) := \begin{cases}
\frac{1+\eta}{4} \qquad\qquad \text{if } a \oplus b= xy,\\
\frac{1-\eta}{4} \qquad\qquad \text{otherwise}.\\
\end{cases}\end{aligned}$$ The box ${\text{\rm{PR}}}_{\eta}$ with $0\leq \eta\leq 1/2$ is local, and with $0\leq \eta\leq 1/\sqrt{2}$ is realizable within quantum mechanics. Nonetheless, ${\text{\rm{PR}}}_{\eta}$ for any $0\leq \eta\leq 1$ is no-signaling. Thus a natural question is: what is the largest possible $\eta$ such that ${\text{\rm{PR}}}_{\eta}$ is feasible in nature [@vanDam; @IC09; @FSABCLA; @BBLMTU; @LPSW; @CSS2010; @OCB2012].

![Imagine that two parties share subsystems of a bipartite physical system that can be correlated. Each party can apply a measurement on her subsystem by tuning her measurement device based on some parameter, and obtain the measurement outcome. We represent the measurement parameters by $x, y$, and the measurement outcomes by $a, b$. Then in its full general case, the outcomes $a, b$, under measurements $x, y$ are obtained with some conditional probability $p(ab|xy)$. We can think of this setting as a box with two parts, where each part has an input and an output. Given inputs $x,y$ the outputs of the box are $a, b$ with probability $p(ab|xy)$. []{data-label="fig1"}](fig.pdf){width="3in"}

Allcock et al. propose the concept of “closed sets of correlations" to study the set of realizable non-local boxes [@ABLP09]. They observe that no matter how non-local the nature is, the set of non-local boxes must be closed under certain local operations, called *wirings* [@Wiring1; @Wiring2]. To illustrate the idea of wirings, we describe it in a simple case, involving only two boxes.

Having two boxes, each party can choose the input of the second box as a function of the output of the first box. More precisely, denoting the inputs and outputs of the two boxes by subscripts $1, 2$, Alice can first choose $x_1$ arbitrarily and use the first box to generate an output $a_1$. Then she may put $x_2=a_1$, i.e., she may [wire]{} the output of the first box to the input of the second box. Bob can similarly use the output of the first box to determine the input of the second box. With these wirings, the parties generate a new box $p(a_2b_2|x_1y_1)$. That is, combining two boxes with wirings they generate a new box under local operations.

Due to the operational definition of wirings, no matter how non-local the nature is, the space of physical boxes must be closed under wirings [@ABLP09]. Then to characterize non-locality in nature, we may first look for subsets of no-signaling boxes that are closed under wirings. Three examples of such closed sets are the set of local correlations, the set of quantum correlations and the whole set of no-signaling boxes. Other examples of closed sets of no-signaling boxes are described in [@MW2009; @LOP2] and in [@Review14]. However, as noted in [@Review14], characterizing sets of boxes that are closed under wirings is a difficult problem in general. A source of difficulty is that there is no limit on the number of boxes that the two parties may choose to use, and the number of possible ways to wire these boxes (defined more precisely later) grows exponentially in the number of boxes. Therefore, having even a few boxes as our resource, it is a difficult problem to discern whether a target box can be simulated via an appropriate wiring or not. It is not even known whether this problem is decidable or not [@Review14].

In [@Review14] it is asked whether there exists a continuum of sets of non-local boxes that are closed under wirings. In particular, it is conjectured that:

\[conj1\] For $1/2< \eta_1<\eta_2<1$, two parties cannot use common randomness and an arbitrary number of copies of ${\text{\rm{PR}}}_{\eta_1}$ to generate a single copy of ${\text{\rm{PR}}}_{\eta_2}$ with wirings.

Although some partial results on the above conjecture have been found [@Short09; @Forster11; @DukaricWolf], no general method for studying wirings is known. Even with the simple structure of isotropic boxes, we do not know how to characterize the *closure* of an isotropic box ${\text{\rm{PR}}}_\eta$ under wirings, i.e., the set of boxes that can be obtained by wirings of some copies of ${\text{\rm{PR}}}_\eta$.

In this paper we present a systematic method for constructing sets of non-local boxes that are closed under wirings. We introduce an invariant of non-local boxes that is monotone under wirings. Our parameter is in terms of a well-known measure of correlation called *maximal correlation* [@Hirschfeld; @Gebelein; @Renyi1; @Renyi2; @Witsenhausen]. We show that maximal correlation, when appropriately defined for non-local boxes, cannot increase under wirings, i.e., maximal correlation is a monotone under wirings. With this result, we can explicitly construct sets of non-local boxes that are closed under wirings. Moreover, by computing maximal correlation for isotropic boxes, we prove Conjecture \[conj1\] for the range of parameters $1/\sqrt 2\leq \eta_1<\eta_2<1$. Our result, in particular implies that there is a continuum of sets of no-signaling boxes that are closed under wirings. Thus the sets of correlations in consistent physical theories cannot be enumerated.

In the rest of this section we briefly discuss the main definitions and ideas of the paper, and informally state the main results. A reader interested only in the statements of the main results, but not their proofs, may continue reading this section and ignore the rest of the paper.

Maximal correlation
-------------------

To get an insight into the types of measures of correlation that are useful for studying wirings, consider the similar but simpler problem of simulating a joint distribution from another. More specifically, suppose that we are given two bipartite probability distributions $p_{AB}$ and $q_{A'B'}$. The question is, given an arbitrary number copies of (samples from) $p_{AB}$ can we generate a single copy of (a sample from) $q_{A'B'}$ by only employing local operations on the $A$ parts and $B$ parts separately? This is a hard problem in general since we assume that the number of available copies of the resource distribution $p_{AB}$ is arbitrarily large.

One may attack the above problem by showing that $q_{A'B'}$ is *more correlated* that $p_{AB}$, so $p_{AB}$ cannot be transformed to $q_{A'B'}$ under local operations. This strategy depends on the *measure* of correlation that we use. The point is that we are allowed to use an arbitrary number copies of $p_{AB}$. Moreover, for most measures of correlations (including mutual information), if $p_{AB}$ has some positive correlation, the correlation of $p^n_{AB}$, i.e., $n$ i.i.d. copies of $p_{AB}$, goes to infinity as $n$ gets larger and larger. Then this strategy fails for usual measures of correlation. However, there is a measure of correlation, called maximal correlation that can be used for this problem.\
**Maximal correlation.** Given a bipartite probability distribution $p_{AB}$, its maximal correlation denoted by $\rho(A, B)$ is the maximum of Pearson’s correlation coefficient over all functions of $A$ and $B$, i.e., $$\begin{aligned}
\label{eq:max-correlatoin-31}
\rho(A, B):=& \max \frac{{\mathbb{E}}[(f_A-{\mathbb{E}}[f_A])(g_B-{\mathbb{E}}[g_B])]}{{\text{\rm{Var}}}[f_A]^{1/2}{\text{\rm{Var}}}[g_B]^{1/2}}\end{aligned}$$ where ${\mathbb{E}}[\cdot]$ and ${\text{\rm{Var}}}[\cdot]$ are expectation value and variance respectively. Moreover, the maximum is taken over all non-constant functions $f_A, g_B$ of $A$ and $B$ respectively.

We always have $0\leq \rho(A, B)\leq 1$. Moreover, $\rho(A, B)=0$ if and only if $A$ and $B$ are independent, and $\rho(A, B)=1$ if and only if $A$ and $B$ have a *common data* [@Witsenhausen]. Maximal correlation can be computed efficiently by diagonalizing a certain matrix [@Kumar2; @KangUlukus].

Maximal correlation has the intriguing property that $$\begin{aligned}
\rho(AA', BB') = \max\{\rho(A, B), \rho(A', B')\},\label{eqn:amnewtensor}\end{aligned}$$ when $AB$ and $A'B'$ are independent, i.e., $p_{AA'BB'}=p_{AB}\cdot p_{A'B'}$. This property is sometimes called the *tensorization property*. Moreover, as a measure of correlation, maximal correlation is monotone under local operations. That is, if $q_{A'B'}$ can be generated from $p_{AB}$ under local stochastic maps, then $\rho(A', B')\leq \rho(A, B)$.

Given the above two properties, we conclude that if for two distributions $p_{AB}$ and $q_{A'B'}$ we have $\rho(A, B)< \rho(A',B')$, then $q_{A'B'}$ cannot be generated locally even if an arbitrary large number of copies of $p_{AB}$ is available.\
**Maximal correlation for non-local boxes.** Given a no-signaling box determined by conditional distributions $p(ab|xy)$ we define its maximal correlation by $$\rho(A, B|X, Y):=\max_{x, y} \rho(A, B|X=x, Y=y).$$ That is, any $(X, Y)=(x, y)$ induces a distribution on $A, B$, so we may compute the maximal correlation $\rho(A, B|X=x, Y=y)$ of this conditional distribution. The maximal correlation of the box is the maximum of all these numbers. Since maximal correlation of bipartite distributions can be computed efficiently, the maximal correlation of non-local boxes can be computed efficiently too. Our main result in this paper is that maximal correlation of non-local boxes is monotone under wirings.

Suppose that the Alice and Bob share a no-signaling box $p(ab|xy)$ and have some a priori correlation. Thus they can choose their inputs of the box according to their a priori correlation, i.e., with respect to some distribution $q_{XY}$. With thse random choices of inputs, they obtain the joint distribution $q(abxy):=q(xy)p(ab|xy)$ on inputs and outputs of the box. A simple argument shows that (see Appendix \[mc-wiring2\]) $$\begin{aligned}
\label{eq:AX-BY-maximal-correlation}
\rho(A, B)\leq \rho(AX, BY)\leq \max\{\rho(X, Y), \rho(A, B|X, Y)\},\end{aligned}$$ where $\rho(X, Y)$ is computed with respect to the distribution $q_{XY}$, and $\rho(A, B|X, Y)$ is the maximal correlation of the box. This means that the maximal correlation between the outputs of the box, is bounded by the maximum of the a priori maximal correlation between Alice and Bob and the maximal correlation of the box shared between them.

Now, assume that Alice and Bob are provided with $n$ boxes $p_i(a_ib_i|x_iy_i)$ for $1\leq i\leq n$. Suppose that they wire these boxes by taking the outputs of the $i$-th box, and feeding them into the input of box $i+1$. That is, after using the $i$-th box, Alice and Bob obtain outputs $a_i$ and $b_i$ respectively, and then use box $i+1$ by setting its inputs $x_{i+1}=a_i$ and $y_{i+1}=b_i$. This is a very special way of wiring of boxes and will be generalized later. With this wiring, Alice and Bob generate a box $q(a_nb_n|x_1y_1)$. Then we claim that $$\begin{aligned}
\label{eq:rho-an-bn-x1-y1}
\rho(A_n, B_n|X_1, Y_1)\leq \max_i \rho(A_i, B_i|X_i, Y_i).\end{aligned}$$ Let us first prove this inequality for $n=2$. Fix the inputs of the first box $(X_1, Y_1)=(x_1, y_1)$. After using this box, Alice and Bob put $(x_2, y_2)=(a_1, b_1)$ which are picked with probability $p_1(a_1b_1|x_1y_1)$; in other words, the distribution of the inputs of the second box is $p_1(x_2y_2|x_1y_1)=p_1(a_1b_1|x_1y_1)$. Then using  we have $$\rho(A_2, B_2|X_1=x_1, Y_1=y_1)\leq \max\big\{  \rho(A_1, B_1|X_1=x_1, Y_1=y_1), \rho(A_2, B_2|X_2, Y_2)   \big\}.$$ Since this inequality holds for all $(x_1, y_1)$, by the definition of maximal correlation for boxes, equation  holds. This inequality for arbitrary $n$ is proved by the same argument and a simple induction.

Equation  states that by wiring of no-signaling boxes in the particular way described above, one cannot generate a box with a larger value of maximal correlation comparing to those of available boxes. That is, maximal correlation of boxes is monotone under wirings of no-signaling boxes.\
**Wirings of no-signaling boxes.** So far we assumed that in wirings, each party sets the input of a box to be equal to the output of the previous box. However, in general each input can be chosen as a possibly random function of *all* the previous inputs and outputs, i.e., for instance Alice to determine input $x_i$ of the $i$-th box can apply a stochastic map on $x_1, a_1, \dots, x_{i-1}, a_{i-1}$. There are interesting examples of wirings of this type in the literature [@vanDam; @BS09]. The above argument can be modified to prove  even for these types of wirings. Nevertheless, wirings of non-local boxes can be even more complicated.

By the no-signaling condition, the parties can use their available boxes in different orders. Each party can choose an arbitrary ordering of boxes and wire the output of a box to the input of the next box in that order. This point is justified by the no-signaling condition, and can intuitively be verified by thinking of the local use of boxes as making measurements on subsystems of a bipartite physical system. Such measurements can be done asynchronously. See Fig. \[fig2\] for an example of wirings of three boxes in different orders.

![The parties can wire their available boxes in a non-trivial order. The fact that boxes can be used in different orders by the parties is a consequence of the no-signaling principle. Here the first party, Alice, uses the boxes in order $2, 3,1$. She has some input $x'$, based on which picks $x_2$, the input of box $2$. Here the circle on the top depicts the stochastic function that maps $x'$ to $x_2$. After using box $2$, Alice obtains output $a_2$. Then she has $x', x_2$ and $a_2$ in hand, and applies another stochastic maps to generate $x_3$, the input of box $3$. She continues until using all the boxes. At the end she applies the final stochastic map to determine her final output $a'$. Bob uses the boxes in order $3,1,2$ and performs similarly.[]{data-label="fig2"}](bipartite-wiring.pdf){width="3in"}

A further degree of freedom in wirings is the very choice of the order of boxes used by a party, as that itself can depend on the outputs of boxes they have already used. For instance, depending on the output of the first box, a party may choose the next box to be used. Again combining some boxes, the parties can generate a new box under local operations. A formal definition of wirings comes in Section \[sec:wiringn\].

Now we may raise the question of the monotonicity of maximal correlation under wirings for these generalized types of wirings. We argued that if the two parties use boxes in the same order that is fixed, then the maximal correlation of the new box generated under wirings, is at most the maximum of the maximal correlations of the available boxes. The question is whether we can prove the same result when the boxes are used in random orders.

One of the main results of this paper is answering the above question in the affirmative. Nevertheless, our proof of this fact is not as simple as the proof in the special case of equation . Our proof in this paper is an indirect one that uses two other measures of correlation with the tensorization property.

Hypercontractivity ribbon
-------------------------

Correlation can also be measured via hypercontractivity inequalities. For a bipartite probability distribution $p_{AB}$, its hypercontractivity ribbon (HC ribbon) which we denote by $\mathfrak R(p_{AB})$, is a subset of the real plane consisting of pairs $(1/\alpha, 1/\beta)\in [0,1]^2$ such that ${\mathbb{E}}[f_A g_B]\leq \|f_A\|_{\alpha}\|g_B\|_{\beta}$ for all functions $f_A, g_B$, where $\|\cdot\|_{\alpha}, \|\cdot\|_{\beta}$ are Schatten norms. More precisely, $${\mathfrak{R}}(p_{AB}) := \big\{(1/\alpha, 1/\beta)\in [0,1]^2| ~ \forall f_A, g_B,\, {\mathbb{E}}[f_A g_B]\leq \|f_A\|_{\alpha}\|g_B\|_{\beta}\big\}.$$

By definition ${\mathfrak{R}}(A, B)\subseteq [0,1]^2$. Moreover, when $A$ and $B$ are independent, we have ${\mathfrak{S}}(A, B)=[0,1]^2$. That is, when $A$ and $B$ are independent, the HC ribbon is the largest possible. Indeed, the more correlated $A$ and $B$ are, the smaller their HC ribbon is. More precisely, the HC ribbon is a measure of correlation in the following sense: if $q_{A'B'}$ can be obtained from $p_{AB}$ under local operations, then we have $$\begin{aligned}
\label{eqn:data-hc-5}
{\mathfrak{R}}(p_{AB})\subseteq {\mathfrak{R}}(q_{A'B'}).\end{aligned}$$ Moreover, we have $$\begin{aligned}
\mathfrak R(p^n_{AB}) = {\mathfrak{R}}(p_{AB}).\label{eqn:tensorization-HC-00}\end{aligned}$$ That is, the HC ribbon also has the tensorization property. Putting these together we conclude that if ${\mathfrak{R}}(p_{AB})$ is not contained in ${\mathfrak{R}}(q_{A'B'})$, the former cannot be transformed to the latter under local operations even if an arbitrary number of i.i.d. copies of $p_{AB}$ is available.

HC ribbon was originally defined by Ahlswede and Gács in [@AhlswedeGacs], and has found applications in information theory (e.g., see [@KamathAnantharam; @Anantharametal]). HC ribbon in the quantum case is defined and studied in [@DelgoshaBeigi].

A remarkable equivalent characterization of the HC ribbon was recently found by Nair [@Nair]. He showed that ${\mathfrak{R}}(p_{AB})$ is indeed the set of pairs $(\lambda_1, \lambda_2)$ of non-negative numbers such that for all auxiliary random variables $U$ (i.e., all $p_{UAB}=p_{AB}\cdot p_{U|AB}$ for an arbitrary conditional distribution $p_{U|AB}$), we have $$\begin{aligned}
\label{eq:intro-nair-eq-00}
I(U; AB)\geq \lambda_1 I(U; A) + \lambda_2 I(U; B).\end{aligned}$$ Here $I(\cdot\,; \cdot)$ is the mutual information function.\
**HC ribbon for non-local boxes.** HC ribbon can be defined for no-signaling boxes as well. Given a box determined by conditional distributions $p(ab|xy)$ we define its HC ribbon by $$\begin{aligned}
\label{eq:box-hc-ribbon-00}
{\mathfrak{R}}(A, B|X, Y)=\bigcap_{x,y} {\mathfrak{R}}(A, B|X=x, Y=y).\end{aligned}$$ We show in this paper that the HC ribbon is monotone under wirings of no-signaling boxes. That is, given $n$ boxes $p_i(a_ib_i|x_iy_i)$, if we can generate another box $q(a'b'|x'y')$ from wirings of these boxes, then we have $$\bigcap_{i=1}^n {\mathfrak{R}}(A_i, B_i|X_i, Y_i) \subseteq {\mathfrak{R}}(A', B'|X', Y').$$ This means that wirings of no-signaling boxes can only expand the HC ribbon. The proof of this fact is relatively involved and is one of the main technical contributions of this paper. Here we only mention that the main tool that we use in this proof is the chain rule of mutual information.

Maximal correlation ribbon
--------------------------

Let us turn back to the problem of the monotonicity of maximal correlation of boxes under wirings. To prove this fact, we found it easier to work with a generalization of maximal correlation, that we define for the first time and call it *maximal correlation ribbon* (MC ribbon). We remark that even though we define the MC ribbon for our purposes here, it is of independent interest. The MC ribbon is a subset of the real plane, defined as follows: $$\begin{aligned}
\label{eq:mc-rib-00}
{\mathfrak{S}}(p_{AB}):=\big\{(\lambda_1, \lambda_2)\in [0,1]^2|\, {\text{\rm{Var}}}[f]\geq \lambda_1{\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f] +\lambda_2 {\text{\rm{Var}}}_B{\mathbb{E}}_{A|B}[f],~~ \forall f_{AB},\big\}.\end{aligned}$$ Here, for instance, ${\mathbb{E}}_{B|A}[\cdot]$ denotes the conditional expectation value. Thus ${\mathbb{E}}_{B|A}[f]$ is a function of $A$, and then ${\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f]$ makes sense.

The MC ribbon has similar properties as the HC ribbon. It is not hard to verify that ${\mathfrak{S}}(A, B)\subseteq [0,1]^2$, and that equality holds only if $A$ and $B$ are independent. Moreover, the MC ribbon is a measure of correlation that satisfies the monotonicity and the tensorization properties in the sense of  and .\
**MC ribbon and HC ribbon.** The definition of the MC ribbon in  is similar to Nair’s characterization of the HC ribbon given by . Indeed the MC ribbon is defined by replacing mutual informations in  by variances. Another contribution of this paper, which again is of independent interest, is that the HC ribbon is always contained in the MC ribbon: $${\mathfrak{R}}(A, B)\subseteq {\mathfrak{S}}(A, B).$$ The connection between the MC ribbon and the HC ribbon will be discussed more precisely in Subsection \[subsec:MC-HC-ribbons\].\
**MC ribbon for non-local boxes.** The MC ribbon for non-local boxes can be defined similarly to equation : $${\mathfrak{S}}(A, B|X, Y)=\bigcap_{x,y} {\mathfrak{S}}(A, B|X=x, Y=y).$$ We prove that, similar to the HC ribbon, the MC ribbon can only expand under wirings. To prove this result we use the connection between the MC ribbon and the HC ribbon mentioned above.\
**MC ribbon vs maximal correlation.** Using all the above tools we can then prove our first claim, that maximal correlation of non-local boxes is monotone under wirings. To prove this claim we first show that maximal correlation can be characterized in terms of the MC ribbon. More precisely, for any bipartite distribution $p_{AB}$ we have $$\rho^2(A, B)=\inf\frac{1-\lambda_1}{\lambda_2},$$ where infimum is taken over all $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$ with $\lambda_2\neq 0$. With this characterization of maximal correlation, and the monotonicity of the MC ribbon under wirings, the monotonicity of maximal correlation under wirings is immediate.

Proof of Conjecture \[conj1\]
-----------------------------

As an application of the above results, we study Conjecture \[conj1\]. The maximal correlation of box ${\text{\rm{PR}}}_\eta$ is equal to $\eta$. Then using the fact that maximal correlation cannot be increased under wirings, Conjecture \[conj1\] is proved in the special case where the parties are not provided with common randomness. To study the case where common randomness is also available, we employ the notion of the CHSH value of boxes. We then establish Conjecture \[conj1\] in the range of parameters $1/\sqrt{2}\leq \eta_1, \eta_2\leq 1$.

Structure of the paper
----------------------

This paper is organized as follows. In Section \[sec:HC\] we define the hypercontractivity ribbon for bipartite distributions. In Section \[sec:wiringn\] wirings of no-signaling boxes is formally defined and some notation is developed for our later use. In Section \[Sec:HC-ribbon\] we define a hypercontractivity ribbon for no-signaling boxes, and show that it expands under wirings. In Section \[sec:MC-ribbon\] we define our new notion of maximal correlation ribbon and show that it has the tensorization property and is monotone under local operations. The connection between the HC ribbon and the MC ribbon is developed in this section. In Section \[sec:MC-ribbon-wiring\] we prove the monotonicity of the MC ribbon under wirings. In Section \[sec:isotropic\] we study Conjecture \[conj1\] for isotropic boxes. Concluding remarks come in Section \[sec:conclusion\]. Some of the technical details and proofs are moved to the appendices.

Hypercontractivity ribbon {#sec:HC}
=========================

Let us first fix some notations. Random variables are represented by uppercase letters (such as $A, B$), and we use lowercase letters (such as $a, b$) to denote their values. The alphabet sets of random variables, which throughout this paper are assumed to be finite, are denoted by the calligraphic letters (such as $\mathcal A, \mathcal B$). Then a probability distribution $p_A$ is determined by numbers $p_A(a)$ for $a\in \mathcal A$ which for simplicity is denoted by $p(a)=p_A(a)$.

For natural numbers $k\leq n$ we let $[k:n]=\{k, k+1,\dots, n\}$. We also denote $[n]=[1:n]$. Moreover for simplicity of notation we use $A_{[n]}=A_1\dots A_n$, and $a_{[n]}=a_1\dots a_n$.

The conditional entropy is denoted by $H(A|B)$. We have $H(A|B)=H(AB)-H(B)$. Moreover, the condition mutual information is $I(A;B|C)=H(A|C)-H(A|BC)$. By the chain rule we have $$I(A;BD|C)=I(A;B|C)+I(A;D|BC).$$ We know that $H(A|B)$ and $I(A;B|C)$ are both non-negative. Then for instance if $I(A;BD|C)$ vanishes, then both $I(A;B|C)$ and $I(A;D|BC)$ vanish too. We will also use the notation $$\begin{aligned}
I(A;B;C|D) &= I(A;B|D)-I(A;B|CD)\label{def:three-partite}
\\&=I(A;C|D)-I(A;C|BD)\nonumber
\\&=I(B;C|D)-I(B;C|AD)\nonumber\end{aligned}$$

Let $A,B$ be two random variables with joint distribution $p_{AB}$ that take values in finite sets. Below we define[^1] the hypercontractivity ribbon (hereafter, HC ribbon) associated to $p_{AB}$.

\[def1\] The hypercontractivity ribbon of $p_{AB}$ denoted by $\mathfrak R(A, B)$ is the set of pairs of non-negative numbers $(\lambda_1, \lambda_2)$ such that for every conditional distribution $p_{U|AB}$ we have $$\begin{aligned}
\label{eq:defHCR}
 \lambda_1I(U; A) + \lambda_2I(U; B) \leq I(U; AB).\end{aligned}$$

Letting $U=A$ we observe that if $(\lambda_1, \lambda_2)\in \mathfrak R(A, B)$ then $\lambda_1\leq 1$. We similarly have $\lambda_2\leq 1$. Therefore $${\mathfrak{R}}(A, B)\subseteq [0,1]^2.$$ Furthermore, by data processing inequality $I(U;A), I(U;B)\leq I(U; AB)$. Then ${\mathfrak{R}}(A, B)$ includes any $(\lambda_1, \lambda_2)$ satisfying $0\leq \lambda_1, \lambda_2\leq 1$ and $\lambda_1+\lambda_2\leq 1$.

The HC ribbon is equal to $[0,1]^2$ if and only if $A, B$ are independent. If $(1,1)\in {\mathfrak{R}}(A, B)$ then by setting $U=AB$ we find that $H(A)+H(B) \leq H(AB)$. Then by the subadditivity inequality $A, B$ are independent. On the other hand, for independent $A, B$ we have $H(A)+ H(B) = H(AB)$ and $$H(A|U) + H(B|U)\geq H(AB|U),$$ which give for $(\lambda_1, \lambda_2)=(1, 1)$.

\[thm:ribbon-tensor-data\] The HC ribbon has the following properties:

1.  *\[Tensorization\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$, then $$\mathfrak R(A_1A_2, B_1B_2)=\mathfrak R(A_1,B_1)\cap\mathfrak R(A_2, B_2).$$

2.  *\[Data processing\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2|A_1}\cdot p_{B_2|B_1}$, then $$\mathfrak R(A_1,B_1)\subseteq \mathfrak R(A_2, B_2).$$

Part (i) in particular implies that letting $A_iB_i$, $i=1, \dots, n$, be $n$ i.i.d. copies of $AB$ then $${\mathfrak{R}}(A_{[n]},B_{[n]}) = {\mathfrak{R}}(A , B).$$ Part (ii) means local transformations on individual random variables can only expand the HC ribbon. Equivalently, (ii) states that more correlated distributions $p_{AB}$ should have smaller HC ribbons. This is in line with the fact that HC ribbon is the whole $[0,1]^2$ for independent random variables. On the other hand, as discussed above we always have $$\begin{aligned}
\label{eq:hc-ribbon-extreme}
\{(\lambda_1, \lambda_2)\in [0,1]^2\big|\, \lambda_1+\lambda_2\leq 1 \}\subseteq {\mathfrak{R}}(A, B).\end{aligned}$$ Thus we expect that equality holds for highly correlated distributions $p_{AB}$. Indeed we know that the above inclusion is an equality if and only if $A$ and $B$ have a *common data* (see e.g., [@KamathAnantharam] and references therein). For example if $A, B$ are binary random variables, and $p(00), p(11)>0$ and $p(01)=p(10)=0$, then we have equality in . Similarly, if $p(01), p(10)>0$ and $p(00)=p(11)=0$, then again equality holds in .

\(i) For an arbitrary $p_{U|A_1B_1}$ we may define a joint distribution $p_{UA_1A_2B_1B_2}$ by $$\begin{aligned}
\label{eq:ua1b1a2b1-independent-10}
p_{UA_1A_2B_1B_2}=p_{U|A_1B_1}\cdot p_{A_1B_1}\cdot p_{A_2B_2}.\end{aligned}$$ We then have $I(U; A_1A_2B_1B_2)=I(U; A_1B_1)$. Now suppose that $(\lambda_1, \lambda_2)\in \mathfrak R(A_1A_2, B_1B_2)$. Thus $$\begin{aligned}
\lambda_1 I(U;A_1) + \lambda_2I(U; B_1)&\leq \lambda_1 I(U;A_1A_2) + \lambda_2 I(U; B_1B_2)\nonumber\\
&\leq I(U; A_1A_2B_1B_2)\nonumber\\
&=I(U; A_1B_1).\label{eq:ua1b1a2b2-9}\end{aligned}$$ Therefore, $(\lambda_1, \lambda_2)\in \mathfrak R(A_1,B_1)$. We similarly have $(\lambda_1, \lambda_2)\in \mathfrak R(A_2, B_2)$, and then ${\mathfrak{R}}(A_1A_2, B_1B_2)\subseteq \mathfrak R(A_1,B_1)\cap\mathfrak R(A_2,B_2).$

To show the other inclusion let $(\lambda_1, \lambda_2)\in \mathfrak R(A_1,B_1)\cap\mathfrak R(A_2, B_2)$. Take some arbitrary $p_{U|A_1A_2B_1B_2}$. Then we have $$\begin{aligned}
\lambda_1 I(U;A_1) + \lambda_2 I(U; B_1)\leq I(U;A_1B_1),
\label{eqnab1}\end{aligned}$$ and $$\begin{aligned}
\lambda_1 I(UA_1B_1;A_2) + \lambda_2I(UA_1B_1; B_2)\leq I(UA_1B_1;A_2B_2).
\label{eqnab2}\end{aligned}$$ Observe that $$I(UA_1B_1;A_2)\geq I(UA_1;A_2)= I(U;A_2|A_1)=I(U;A_1A_2)-I(U;A_1),$$ and similarly $I(UA_1B_1;B_2)\geq I(U;B_1B_2)-I(U;B_1).$ We also have $$\begin{aligned}
I(UA_1B_1;A_2B_2)&= I(U;A_2B_2|A_1B_1)= I(U;A_1A_2B_1B_2)-I(U;A_1B_1).\end{aligned}$$ Hence, from and we obtain $$\begin{aligned}
\lambda_1 I(U;A_1A_2) + \lambda_2 I(U; B_1B_2)&\leq I(UA_1B_1;A_2B_2)+I(U; A_1B_1)
\nonumber\\
&= I(U;A_1A_2B_1B_2).\label{eqnab33}\end{aligned}$$ Therefore, $(\lambda_1, \lambda_2)\in\mathfrak R(A_1A_2,B_1B_2)$, and $$\mathfrak R(A_1,B_1)\cap\mathfrak R(A_2,B_2)\subseteq {\mathfrak{R}}(A_1A_2,B_1B_2).$$\
(ii) By repeated use of the functional representation lemma [@elgamal Appendix B], there are random variables $F, G$ that are independent of each other and of $(A_1,B_1)$ such that $A_2$ is a function of $(A_1, F)$, and $B_2$ is a function of $(B_1, G)$. Indeed, $F$ and $G$ can be thought of as the randomness of the channels $p_{A_2|A_1}$ and $p_{B_2|B_1}$. Since $F, G$ are independent, as we discussed earlier $\mathfrak R(F,G)$ is the whole $[0,1]^2$. Therefore by part (i) we have $$\mathfrak R(A_1F,B_1G)=\mathfrak R(A_1,B_1)\cap \mathfrak R(F, G)=\mathfrak R(A_1,B_1).$$ Thus without loss of generality we may assume that the randomness $F, G$ are parts of $A_1, B_1$ respectively, and that $A_2, B_2$ are functions of $A_1, B_1$ respectively.

Suppose that $(\lambda_1, \lambda_2)\in \mathfrak R(A_1,B_1)$. We have a joint distribution $$p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2|A_1}\cdot p_{B_2|B_1}=p_{A_2B_2} \cdot p_{A_1B_1|A_2B_2}.$$ Take some $p_{U|A_2B_2}$. Define $$p_{UA_1A_2B_1B_2}:=p_{U|A_2B_2}\cdot p_{A_2B_2}\cdot p_{A_1B_1|A_2B_2}=p_{UA_2B_2}\cdot p_{A_1B_1|A_2B_2}.$$ Note that the marginal distribution of $p_{UA_1A_2B_1B_2}$ on variables $A_1, A_2, B_1, B_2$ coincides with $p_{A_1A_2B_1B_2}$ that we started with, and $I(U; A_1B_1|A_2B_2)=0.$ Therefore, $$\begin{aligned}
I(U; A_2B_2)& =I(U;A_1A_2B_1B_2)\\
&\geq I(U; A_1B_1)\\
&\geq \lambda_1I(U; A_1) +\lambda_2I(U; B_1)\\
&\geq \lambda_1 I(U; A_2) + \lambda_2 I(U; B_2),\end{aligned}$$ where in the last line we use the fact that $A_2, B_2$ are functions of $A_1, B_1$ respectively. We are done.

The standard definition of HC ribbon [@AhlswedeGacs], as discussed in the introduction, is in terms of Schatten norms of functions of random variables, rather than mutual information. A remarkable recent work by Nair [@Nair] finds a representation of the HC ribbon for two random variables in terms of mutual information.

$(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A, B)$ if and only if for every pair of functions $f_A:\mathcal A\rightarrow \mathbb R$ and $g_B:\mathcal B\rightarrow \mathbb R$ we have $$\begin{aligned}
\label{eq:fg-norm-2}
{\mathbb{E}}[f_Ag_B]\leq \|f_A\|_{\frac{1}{\lambda_1}}\|g_B\|_{\frac{1}{\lambda_2}},\end{aligned}$$ where the Schatten norms are defined by $\|f_A\|_{\frac{1}{\lambda_1}}={\mathbb{E}}\big[|f_A|^{1/\lambda_1}\big]^{\lambda_1}$ and similarly for $\|g_B\|_{\frac{1}{\lambda_2}}$. \[thm:nair\]

The following corollary is an immediate consequence of the above theorem and the definition of ${\mathfrak{R}}(A, B)$ given in Definition \[def1\]. This corollary can be directly proved using the Riesz-Thorin theorem (see [@DelgoshaBeigi Theorem 14]).

For every $p_{AB}$ the set of points $(\lambda_1, \lambda_2)\in [0,1]^2$ satisfying  for every functions $f_A, g_B$, is convex.

A geometric interpretation of the HC ribbon
-------------------------------------------

In Appendix \[app:GW\] we discuss a new connection between the HC ribbon and the Gray-Wyner problem which provides an operational interpretation of the HC ribbon. Here we briefly discuss a geometric interpretation of the HC ribbon which will be used in the following sections.

For every distribution $q_{AB}$ on $\mathcal A\times \mathcal B$ define $$\begin{aligned}
\label{eq:upsilon-def}
\Upsilon(q_{AB}) = \lambda_1H(q_A) + \lambda_2 H(q_B) - H(q_{AB}),\end{aligned}$$ where $H(\cdot)$ is the entropy function. Also, let $\widetilde \Upsilon$ be the point-wise largest function that is convex and $\widetilde \Upsilon(q_{AB})\leq \Upsilon(q_{AB})$ for every distribution $q_{AB}$. The function $\widetilde \Upsilon$ is sometimes called the *lower convex envelope* of $\Upsilon$. The following lemma is based on known connections between lower convex envelopes and auxiliary random variables (see [@nairup] for more applications).

\[lem:geom-interpret-HC-ribbon\] For every distribution $p_{AB}$, we have $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A, B)$ if and only if $\Upsilon(p_{AB})=\widetilde\Upsilon(p_{AB})$.

For a given $p_{U|AB}$, by the convexity of $\tilde \Upsilon$ we have $$\begin{aligned}
{\mathbb{E}}_U[\Upsilon(p_{AB|U})] \geq {\mathbb{E}}_U[\widetilde\Upsilon(p_{AB|U})] \geq \widetilde \Upsilon({\mathbb{E}}_U[p_{AB|U}]) = \widetilde \Upsilon(p_{AB}).\end{aligned}$$ Then $\widetilde \Upsilon(p_{AB})= \Upsilon(p_{AB})$ implies $$\begin{aligned}
\label{eq:upsilon-pabu-0}
{\mathbb{E}}_U[\Upsilon(p_{AB|U})] \geq \Upsilon(p_{AB}),\end{aligned}$$ which is equivalent to $$I(U;AB)\geq \lambda_1I(U; A) + \lambda_2I(U; B).$$ Therefore, $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A,B)$.

Conversely, $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A,B)$ implies that  holds for every $p_{U|AB}$, and one can verify that this gives $\Upsilon(p_{AB})=\widetilde \Upsilon(p_{AB})$.

Wirings of no-signaling boxes {#sec:wiringn}
=============================

As discussed in the introduction, a non-local box (correlation) is a collection of conditional distributions $p(ab|xy)$. Here $x, y$ are the inputs of the box and $a, b$ are its outputs and $p(ab|xy)$ is the probability of obtaining these outputs. This quantity $p(ab|xy)$ can be thought of as the probability of obtaining outcomes $a,b$ when we measure subsystems of a bipartite physical system with measurement settings $x, y$ respectively. A box has the no-signaling condition if we have $$p(a|xy) = p(a|x), \qquad \qquad p(b|xy)= p(b|y).$$ That is, the marginal distribution $p(a|xy)$ is independent of $y$, and the marginal distribution $p(b|xy)$ is independent of $x$. Hereafter all the boxes in the paper are assumed to have the no-signaling condition.

Suppose that two parties, say Alice and Bob, are provided with $n$ no-signaling boxes. We denote the inputs of the $i$-th box by $X_i, Y_i$ and its outputs by $A_i, B_i$. Then the $i$-th box is determined by a no-signaling correlation $p_i(a_ib_i|x_iy_i)$. As before, we may think of these $n$ boxes as $n$ *independent* bipartite physical systems whose first subsystem is given to Alice and whose second subsystem is given to Bob. Then each party has $n$ subsystems in hand, and may measure these subsystems in some arbitrary order (independent of the order of the other party). Each party may choose the input of a box as a (probably random) function of the inputs and outputs of the previous boxes. In fact, the box that is going to be used in each step could itself be chosen as a function of previous inputs and outputs. With this process the parties end up with a new no-signaling box. Such a process is called a wiring. An example of wirings is shown in Fig. \[fig2\].

Let us describe wirings in a more formal way. Here we assume that the two parties do not have access to common randomness. Suppose that two parties want to use the above $n$ boxes as a resource to simulate another box $p(a'b'|x'y')$. Thus Alice is given $x'$ and is asked to output $a'$, and Bob is given $y'$ and is asked to output $b'$ whose joint distribution is $p(a'b'|x' y')$. Alice is going to use the boxes in some order which as explained above can be random itself. Let us denote the corresponding random variables by $\Pi_1, \dots, \Pi_n$. That is, $(\Pi_1, \dots, \Pi_n)$ is a random permutation of $[n]$, and Alice uses box $i$ in her $\Pi_i$-th action. Let us denote the inverse permutation of $(\Pi_1, \dots, \Pi_n)$ by $(\widetilde \Pi_1, \dots, \widetilde \Pi_n)$, i.e., $${\widetilde{\Pi}}_{\Pi_i}=i,  \qquad \Pi_{{\widetilde{\Pi}}_i}=i.$$ Then Alice first uses box ${\widetilde{\Pi}}_1$, and then uses box ${\widetilde{\Pi}}_2$ and so on.

Now let us describe Alice’s $j$-th action. Before the $j$-th action Alice has used boxes ${\widetilde{\Pi}}_1={\tilde{\pi}}_1, \dots, {\widetilde{\Pi}}_{j-1}={\tilde{\pi}}_{j-1}$ with inputs $X_{{\widetilde{\Pi}}_1}=x_{{\tilde{\pi}}_1}, \dots, X_{{\widetilde{\Pi}}_{j-1}}=x_{{\tilde{\pi}}_{j-1}}$ and has observed outputs $A_{{\widetilde{\Pi}}_1}=a_{{\tilde{\pi}}_1}, \dots, A_{{\widetilde{\Pi}}_{j-1}}=a_{{\tilde{\pi}}_{j-1}}$. To simplify our notation let us define $$\widetilde X_i:= X_{{\widetilde{\Pi}}_i}, \qquad \qquad \widetilde A_i:=A_{{\widetilde{\Pi}}_i}.$$ That is $\widetilde X_i, \widetilde A_i$ are the input and output of the box that Alice uses in her $i$-th action. By this notation before her $j$-th action Alice has used boxes ${\widetilde{\Pi}}_{[j-1]}={\tilde{\pi}}_{[j-1]}$ with inputs $\widetilde X_{[j-1]}=\tilde x_{[j-1]}$ and has observed outputs $\widetilde A_{[j-1]} = \tilde a_{[j-1]}$. She also has $x'$ from the beginning. Then she chooses the next box and its input according to some stochastic map $$\begin{aligned}
\label{eq:encoding-alice}
q\big({\tilde{\pi}}_{j}\tilde x_j\,\big|\,{\tilde{\pi}}_{[j-1]}\tilde a_{[j-1]}\tilde x_{[j-1]} x'\big).\end{aligned}$$ She puts $\tilde x_{j}= x_{{\tilde{\pi}}_j}$ as the input of box ${\tilde{\pi}}_j$ and observes $\tilde a_j=a_{{\tilde{\pi}}_j}$ as the output. She continues until using all the $n$ boxes. A summary of the definition of the random variables defined above is given in Table \[table:summary\].

The actions of Bob are described similarly. We denote the random order under which Bob uses the boxes by ${\widetilde{\Omega}}_1, \dots, {\widetilde{\Omega}}_n$ and its inverse permutation by $ \Omega_1, \dots, \Omega_n$, i.e., $$\Omega_{\widetilde \Omega_i}=i, \qquad\qquad {\widetilde{\Omega}}_{ \Omega_i}=i,$$ and Bob uses box $i$ in his $\Omega_i$-th action. We use $$\widetilde Y_i:= Y_{{\widetilde{\Omega}}_i}, \qquad \qquad \widetilde B_i:=B_{{\widetilde{\Omega}}_i}.$$ Then before his $j$-th action, Bob has used boxes ${\widetilde{\Omega}}_{[j-1]}={\tilde{\omega}}_{[j-1]}$, with inputs $\widetilde Y_{[j-1]}={\tilde{y}}_{[j-1]}$ and has observed outputs $\widetilde B_{[j-1]}={\tilde{b}}_{[j-1]}$. He also has $y'$ from the beginning. Then he uses some stochastic map $$\begin{aligned}
\label{eq:encoding-bob}
q\big({\tilde{\omega}}_{j}{\tilde{y}}_j\,\big|\,{\tilde{\omega}}_{[j-1]}{\tilde{b}}_{[j-1]}{\tilde{y}}_{[j-1]} y'\big),\end{aligned}$$ to choose ${\widetilde{\Omega}}_j={\tilde{\omega}}_j$ and ${\tilde{y}}_j=y_{{\tilde{\omega}}_j}$. He puts $y_{{\tilde{\omega}}_j}$ as the input of box ${\tilde{\omega}}_j$ and receives output ${\tilde{b}}_j=b_{{\tilde{\pi}}_j}$. He continues until using all the boxes.

In  and we use $q(\cdot| \cdot)$ for stochastic maps of both Alice and Bob. This however should not cause any confusion since whether $q(\cdot | \cdot)$ corresponds to Alice or Bob’s action should be clear from its arguments.

We need to simplify our notation even further. Let us denote $T_i$ be the *transcript* of Alice (whatever she has) before using the $i$-th box (before her ${\widetilde{\Pi}}_i$-th action), i.e., $$T_i:={\widetilde{\Pi}}_1\dots {\widetilde{\Pi}}_{\Pi_i-1} X_{{\widetilde{\Pi}}_1}\dots X_{{\widetilde{\Pi}}_{\Pi_i-1}} A_{{\widetilde{\Pi}}_1}\dots A_{{\widetilde{\Pi}}_{\Pi_i-1}}={\widetilde{\Pi}}_{[\Pi_i-1]}{\widetilde{X}}_{[\Pi_i-1]} {\widetilde{A}}_{[\Pi_i-1]}.$$ We also use ${\widetilde{T}}_i$ for the transcript of Alice before her $i$-th action, i.e., $${\widetilde{T}}_i:=T_{{\widetilde{\Pi}}_i} = {\widetilde{\Pi}}_1\dots {\widetilde{\Pi}}_{i-1} X_{{\widetilde{\Pi}}_1}\dots X_{{\widetilde{\Pi}}_{i-1}} A_{{\widetilde{\Pi}}_1}\dots A_{{\widetilde{\Pi}}_{i-1}}={\widetilde{\Pi}}_{[i-1]}{\widetilde{X}}_{[i-1]}{\widetilde{A}}_{[i-1]}.$$ We define $S_i$ and ${\widetilde{S}}_i$ similarly for Bob, i.e., $$S_i:= {\widetilde{\Omega}}_{[\Omega_i-1]}{\widetilde{Y}}_{[\Omega_i-1]} {\widetilde{B}}_{[\Omega_i-1]}, \qquad \qquad {\widetilde{S}}_i:={\widetilde{\Omega}}_{[i-1]}{\widetilde{Y}}_{[i-1]}{\widetilde{B}}_{[i-1]}.$$ With these notations Alice before using the $i$-th box has $T_i=t_i$ and $x'$ in hand and with probability $q(i x_i|t_i x')$ chooses the $i$-th box for her next action and puts $x_i$ in this box. Similarly before using the $i$-th box, Bob has $s_i$ and $y'$ and with probability $q(i y_i|s_i y')$ chooses box $i$ for his next action and puts $y_i$ as its input. As a result, the joint probability of inputs and outputs of the boxes and the orderings of Alice and Bob is $$\begin{aligned}
\label{eq:p-a-x-m-n-y}
p\big(a_{[n]}b_{[n]}x_{[n]}y_{[n]} \pi_{[n]}\omega_{[n]}\,\big|\,x'y'\big)=\prod_{i=1}^n\bigg[ p_i\big(a_ib_i\,\big|\,x_iy_i\big) q\big(ix_i\,\big|\,t_i x'\big)q\big(iy_i\,\big|\,s_i y'\big)\bigg].\end{aligned}$$ Should this equation appear unintuitive, the author can refer to the explanation given in the beginning of Appendix \[app:lemm-proof\].

At the end of wirings Alice applies the stochastic map $q(a'|a_{[n]}x_{[n]}\pi_{[n]} x')$ to determine her final output and Bob applies $q(b'|b_{[n]}y_{[n]} \omega_{[n]}y')$ to determine his final output.

         Notation                                     Description                               [ Corresponding variable of Bob]{}
  ----------------------- -------------------------------------------------------------------- ------------------------------------
          $\Pi_i$                  Alice uses the $i$-th box in her $\Pi_i$-th action                       $\Omega_i$
                                   Index of the box Alice uses in her $i$-th action:           
   ${\widetilde{\Pi}}_i$   $~\Pi_{{\widetilde{\Pi}}_i}=i, \qquad {\widetilde{\Pi}}_{\Pi_i}=i$        ${\widetilde{\Omega}}_i$
           $X_i$                            Alice’s input of the $i$-th box                                   $Y_i$
           $A_i$                            Alice’s output of the $i$-th box                                  $B_i$
                                          Alice’s input in her $i$-th action:                  
    ${\widetilde{X}}_i$               $~{\widetilde{X}}_i=X_{{\widetilde{\Pi}}_i}$                     ${\widetilde{Y}}_i$
                                          Alice’s output in her $i$-th action:                 
    ${\widetilde{A}}_i$               $~{\widetilde{A}}_i=A_{{\widetilde{\Pi}}_i}$                     ${\widetilde{B}}_i$
           $T_i$                     Alice’s transcript before using the $i$-th box                           $S_i$
                                      Alice’s transcript before her $i$-th action:             
    ${\widetilde{T}}_i$               $~{\widetilde{T}}_i=T_{{\widetilde{\Pi}}_i}$                     ${\widetilde{S}}_i$
          $T_i^e$                                    $T_iX_i\Pi_i$                                           $S_i^e$

\[lem:dist-wiring\] For any given $x', y'$ the followings hold.

1.  $I\big(A_iB_i; T_iS_i\Pi_i\Omega_i\big|X_iY_i, x'y'\big)=0$.

2.  $I\big(A_i; S_i Y_i \Omega_i\big|\, T_i X_i \Pi_i, x'y'\big)=I\big(B_i; T_i X_i \Pi_i\big|\, S_i Y_i \Omega_i, x'y'\big)=0$.

3.  $I\big(A_i;  B_{[n]}Y_{[n]}\Omega_{[n]}  \big|\, T_iX_i \Pi_i B_i Y_i\Omega_i,x'y'\big)=I\big(B_i;  A_{[n]}X_{[n]}\Pi_{[n]}  \big|\, T_iA_iX_i\Pi_i S_i  Y_i\Omega_i,x'y'\big)=0.$

4.  $I\big({\widetilde{X}}_i{\widetilde{\Pi}}_i; B_{[n]}Y_{[n]}\Omega_{[n]}\big|\, {\widetilde{T}}_i,x'y'\big)=I\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i; A_{[n]}X_{[n]}\Pi_{[n]}\big|\, {\widetilde{S}}_i,x'y'\big)=0$.

Here we give an informal intuitive proof of this lemma. For a full detailed proof see Appendix \[app:lemm-proof\].

\(i) holds simply because given the inputs of the $i$-th box, its outputs are independent of the transcripts of Alice and Bob when they reach this box. (ii) is a consequence of (i) and the no-signaling condition. (iii) holds because when (say) Alice uses the $i$-th box, her output, if not conditioned on her future observations, depends only on the inputs of the $i$-th box and Bob’s output of this box. (iv) is a simple consequence of the fact that ${\widetilde{X}}_i{\widetilde{\Pi}}_i$ and ${\widetilde{Y}}_i{\widetilde{\Omega}}_i$ are generated locally without using the boxes.

We will frequently use the following lemma.

\[lemma:amnm\] For auxiliary random variables $U$ and $V$ we have $$\begin{aligned}
I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}|V, x'y'\big)&=\sum_{i=1}^n\bigg[I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_iV, x'y'\big)+I\big(U;A_{i}|T^e_iV, x'y'\big)\bigg], \label{eq:tyab5}
\\H\big(A_{[n]}X_{[n]}\Pi_{[n]}|V, x'y'\big)&=\sum_{i=1}^n\bigg[H\big({\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_iV, x'y'\big)+H\big(A_{i}|T^e_iV, x'y'\big)\bigg],\label{eq:tyab5new}\end{aligned}$$ where $T_i^{e}:=T_i X_{i} \Pi_{i}.$ Similar equations hold for Bob’s random variables too.

This lemma follows from repeated use of the chain rule and its proof is given in Appendix \[app:lemma-amnnproof\].

HC ribbon for no-signaling boxes {#Sec:HC-ribbon}
================================

In this section we define the HC ribbon for no-signaling boxes, and show that it is well-behaved under wirings.

\[definition:HC-no-signaling\] Given a no-signaling box $p(ab|xy)$, we define its HC ribbon to be the intersection of the HC ribbons of its outputs conditioned on all possible inputs, i.e., $$\mathfrak R(A, B|X, Y):=\bigcap_{x,y}\mathfrak R(A, B|X=x, Y=y).$$

Let us as an example, compute the HC ribbon of the perfect PR box (which we denoted by ${\text{\rm{PR}}}_1$). For any $x,y\in \{0,1\}$, $\Pr_1(a, b|x,y)=1/2$ iff $a\oplus b=xy$. Then by the discussion before the proof of Theorem \[thm:ribbon-tensor-data\], we have $${\mathfrak{R}}(\Pr_1(a, b|x, y)) = \big\{(\lambda_1, \lambda_2)\in [0,1]^2\big|\, \lambda_1+\lambda_2\leq 1\big\}, \qquad \qquad \forall x,y
\in\{0,1\}.$$ As a result ${\mathfrak{R}}(\Pr_1)$ which is the intersection of the above four HC ribbons, is equal to $$\begin{aligned}
\label{eq:ribbon-perfect-pr}
{\mathfrak{R}}(\Pr_1)=\big\{(\lambda_1, \lambda_2)\in [0,1]^2\big|\, \lambda_1+\lambda_2\leq 1\big\}.\end{aligned}$$

We can now state the main theorem of this section.

\[thm:main-theorem\] Suppose that a no-signaling box $p(a'b'| x'y')$ can be generated from $n$ no-signaling boxes $p_i(a_ib_i| x_i y_i)$ where $i\in [n]$, under wirings. Then we have $$\begin{aligned}
\label{eq:mon-wiring-ribbon}
\bigcap_{i=1}^n {\mathfrak{R}}(A_i,B_i|X_i, Y_i) \subseteq {\mathfrak{R}}(A',B'|X',Y').\end{aligned}$$

Observe that this theorem is consistent with the known protocols for non-locality distillation with wirings. For example in [@BS09] it is shown that using certain no-signaling boxes one can simulate the perfect PR box under wirings. Nevertheless, it can be verified that the HC ribbons of those boxes is equal to the HC ribbon of the perfect PR box computed in .

In the following proof for wirings of no-signaling boxes we use the notation developed in the previous section.

By definition we need to show that $$\bigcap_{i=1}^n {\mathfrak{R}}(A_i, B_i|X_i, Y_i) \subseteq {\mathfrak{R}}(A', B'|X'=x', Y'=y'),$$ for every $x',y'$. So we fix $x', y'$ and in the following for simplicity of notation drop all conditionings on $x', y'$.

Let $(\lambda_1, \lambda_2)$ be in ${\mathfrak{R}}(A_i, B_i|X_i, Y_i)$ for all $i\in [n]$. We need to show that $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A', B'|X'=x', Y'=y')$. As explained in Section \[sec:HC\], any HC ribbon always includes pairs $(\lambda_1, \lambda_2)$ that satisfy $\lambda_1+\lambda_2\leq 1$. Therefore if $\lambda_1+\lambda_2\leq 1$, there is nothing left to prove. So in the following we assume that $\lambda_1, \lambda_2\in [0,1]$ are such that $$\lambda_1+\lambda_2\geq 1.$$

Recall that $A', B'$ are generated by Alice and Bob under local stochastic maps. That is, Alice generates $A'$ given $A_{[n]}X_{[n]}\Pi_{[n]}$ and Bob generates $B'$ given $B_{[n]}Y_{[n]} \Omega_{[n]}$. Therefore by part (ii) of Theorem \[thm:ribbon-tensor-data\] (data processing for HC ribbon) we only need to prove $$\begin{aligned}
\label{eq:sum-leq-1}
(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A_{[n]}X_{[n]}\Pi_{[n]}, B_{[n]}Y_{[n]} \Omega_{[n]}).\end{aligned}$$ Note that the HC ribbon on the right hand side is computed for the distribution induced by the wirings of boxes, i.e., with respect to distribution .

Let $U$ be an auxiliary random variable determined by $p_{U|A_{[n]}X_{[n]}\Pi_{[n]}B_{[n]}Y_{[n]} \Omega_{[n]}}$. We would like to show that $$\begin{aligned}
\label{eq:final-ineq-3}
\lambda_1 I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}\big) + \lambda_2 I(U; B_{[n]}Y_{[n]} \Omega_{[n]})\leq I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}B_{[n]}Y_{[n]} \Omega_{[n]}\big).\end{aligned}$$

Using the first equation of Lemma \[lemma:amnm\] with $V=\emptyset$, we get that $$\begin{aligned}
I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}\big)&=\sum_{i=1}^n\bigg[I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_i\big)+I\big(U;A_{i}|T^e_i\big)\bigg]\label{eq:tyab5tt}\\
&= \sum_{i=1}^n\bigg[I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i\big|{\widetilde{T}}_i\big)+I\big(U;A_{i}\big|T^e_iS^e_i\big) + I\big(U;A_{i};S^e_{i}\big|T_i^e\big)\bigg].\label{eq:123a}\end{aligned}$$ where in the last step, we used the definition given in . We similarly have $$\begin{aligned}
I\big(U;B_{[n]}Y_{[n]}\Omega_{[n]}\big)
= \sum_{i=1}^n\bigg[I\big(U;{\widetilde{Y}}_{i}{\widetilde{\Omega}}_i\big|{\widetilde{S}}_i\big)+I\big(U;B_{i}\big|T^e_iS^e_i\big) + I\big(U;B_{i};T^e_{i}\big|\,S_i^e\big)\bigg]
,\label{eq:123b}\end{aligned}$$ where $$S_i^{e}:=S_iY_i\Omega_i.$$ From $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A_i, B_i|X_i, Y_i)$ we have $$\begin{aligned}
\label{eq:mc-12-lambda}
 \lambda_1I\big(UT_{i}S_i\Pi_i\Omega_i;A_{i}\big|\,X_{i}Y_i\big)+  \lambda_2I\big(UT_{i}S_i\Pi_i\Omega_i;B_{i}\big|\,X_{i}Y_i\big)&\leq I\big(UT_{i}S_i\Pi_i\Omega_i;A_iB_{i}\big|\,X_{i} Y_i\big).\end{aligned}$$ Indeed by definition this inequality holds for every $(X_i, Y_i)=(x_i, y_i)$, and then holds for their average. On the other hand by Lemma \[lem:dist-wiring\] part (i) we have $I\big(A_iB_i; T_iS_i\Pi_i\Omega_i\big|X_iY_i\big)=0$. Thus an application of chain rule gives $$\begin{aligned}
 \lambda_1I\big(U;A_{i}\big|\,T^e_{i} S^e_i\big)+  \lambda_2I\big(U;B_{i}\big|\,T^e_{i} S^e_i\big)&\leq I\big(U;A_iB_{i}\big|\,T^e_{i} S^e_i\big).\end{aligned}$$ Therefore using and , to prove we need to show that $\chi(\lambda_1, \lambda_2)\geq 0$ for any $\lambda_1, \lambda_2\in[0,1]$ satisfying $\lambda_1+\lambda_2\geq 1$, where $$\begin{aligned}
\chi(\lambda_1, \lambda_2):=&-\sum_{i=1}^n \bigg[\lambda_{1}I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_i\big)+\lambda_2I\big(U;{\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)\nonumber\\
&\qquad \quad+\lambda_1I\big(U;A_{i};S^e_{i}|T_i^e\big) + \lambda_2 I\big(U;B_{i};T^e_{i}\big|\,S_i^e\big) \nonumber\\
&\qquad\quad +I\big(U;A_iB_{i}\big|\,T^e_{i} S^e_i\big)\bigg]
 +I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}B_{[n]}Y_{[n]}\Omega_{[n]}\big).\end{aligned}$$ In Appendix \[app:proof-main-thm\] using chain rule we will first find an equivalent expression of $\chi(\lambda_1, \lambda_2)$ and then using Lemma \[lem:dist-wiring\] by a term by term analysis of the expression we show that it is non-negative.

The following corollary is a simple consequence of the above theorem.

\[corol:HC-ribbon-close-wiring\] Let $\Lambda\subseteq [0,1]^2$ be an arbitrary subset. Then the set of no-signaling boxes whose HC ribbon contains $\Lambda$ is closed under wirings.

Theorem \[thm:main-theorem\] can be interpreted as a generalization of the tensorization property of hypercontractivity ribbon (part (i) of Theorem \[thm:ribbon-tensor-data\]). For example we have the following.

For any four random variables $A_1, B_1, A_2, B_2$ satisfying $$\begin{aligned}
I(A_2;B_1|A_1)=I(A_1;B_2|B_1)=0,\label{eqn:non-signalingconditionAB}\end{aligned}$$ we have $$\mathfrak R(A_1,B_1)\cap \mathfrak R(A_2,B_2|A_1,B_1)\subseteq\mathfrak R(A_1A_2,B_1B_2),$$ where $\mathfrak R(A_2,B_2|A_1,B_1)$ is defined in Definition \[definition:HC-no-signaling\].

Note that this is indeed a generalization of the tensorization property since when $(A_1,B_1)$ is independent of $(A_2,B_2)$, this property reduces to the tensorization property.

Consider two bipartite no-signaling boxes as follows. The first box is determined by the conditional distribution $p_{A_1B_1|X_1Y_1}=p_{A_1B_1}$, and the second box is defined by $$p_{A_2B_2|X_2Y_2}:=p_{A_2B_2|A_1B_1},$$ where $\mathcal X_2=\mathcal A_1$ and $\mathcal Y_2=\mathcal B_1$. The first box is obviously no-signaling. The second box is guaranteed to be no-signaling by . Both parties first use the first box, and then the second box by directly wiring the output of the first box to the input of the second box. This allows Alice and Bob to simulate a channel whose input is $(X_1, Y_1)$ and whose output is $(A_1A_2, B_1B_2)$. However $p_{A_1A_2,B_1B_2|X_1,Y_1}=p_{A_1A_2,B_1B_2}$. Then the results follows as a very special case of Theorem \[thm:main-theorem\].

Maximal correlation ribbon {#sec:MC-ribbon}
==========================

In the previous section, based on Corollary \[corol:HC-ribbon-close-wiring\], we obtain a systematic method to construct sets of no-signaling boxes that are closed under wirings. Nevertheless, to construct such sets we need to be able to compute the HC ribbons of no-signaling boxes, for which we do not know an efficient algorithm. Our goal in this and the following sections is to define another invariant of no-signaling boxes with similar monotonicity properties as the HC ribbons, that is efficiently computable.

Given a bipartite distribution $p_{AB}$ we consider functions $f_{AB}:\mathcal A\times \mathcal B\rightarrow \mathbb R$. Then we denote its expectation value by ${\mathbb{E}}[f]$. Sometimes we denote ${\mathbb{E}}[f]$ by ${\mathbb{E}}_{AB}[f]$ to emphasis that the expectation is computed with respect to the distribution $p_{AB}$. We may also consider the conditional expectation ${\mathbb{E}}_{A|B}[f]$, and view it as a random variable taking the value ${\mathbb{E}}_{A|B=b}[f]$ (the expectation of $f_{AB}$ over the conditional distribution $P_{A|B=b}$) whenever $B=b$. In other words, ${\mathbb{E}}_{A|B}[f]$ is viewed as a function of $B$ which itself is a random variable.

The variance of $f_{AB}$ is denoted by $${\text{\rm{Var}}}[f]:={\mathbb{E}}[(f-{\mathbb{E}}[f])^2]={\mathbb{E}}[f^2]-{\mathbb{E}}[f]^2.$$ Again sometimes we denote ${\text{\rm{Var}}}[f]$ by ${\text{\rm{Var}}}_{AB}[f]$. We also consider the conditional variance ${\text{\rm{Var}}}_{A|B}[f]:= {\mathbb{E}}_{A|B}[(f-{\mathbb{E}}_{A|B}[f])^2]$ which again is a function of $B$. We will frequently use the *law of total variance* which states that $${\text{\rm{Var}}}[f]={\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f] + {\mathbb{E}}_A{\text{\rm{Var}}}_{B|A}[f].$$ Since variance is always non-negative, from the law of total variance we find that $$\begin{aligned}
\label{eq:total-variance-ineq}
{\text{\rm{Var}}}[f]\geq \max\{ {\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f], {\mathbb{E}}_A{\text{\rm{Var}}}_{B|A}[f]\}.\end{aligned}$$

Now we are ready to define the maximal correlation ribbon (MC ribbon) of bipartite distributions.

The maximal correlation ribbon of $p_{AB}$ denoted by ${\mathfrak{S}}(A, B)$ is the set of all pairs $(\lambda_1, \lambda_2)$ of non-negative numbers such that for all functions $f_{AB}:\mathcal A\times \mathcal B\rightarrow \mathbb R$ we have $$\begin{aligned}
{\text{\rm{Var}}}[f] \geq \lambda_1 {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] + \lambda_2 {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f].
\label{eq:def-cond-var-lambda}\end{aligned}$$

Letting $f$ be a function of $A$ only, by the law of total variance we have ${\text{\rm{Var}}}[f] = {\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f]$. Then if $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$, we have $\lambda_1\leq 1$. We similarly have $\lambda_2\leq 1$. Therefore, $${\mathfrak{S}}(A, B)\subseteq [0,1]^2.$$ Furthermore observe that by  for all $\lambda_1, \lambda_2\geq 0$ with $\lambda_1+\lambda_2\leq 1$ we have $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A,B)$.

As an example, let us compute the MC ribbon in the case where $A$ and $B$ are independent. Using the fact that $A$ and $B$ are independent and the convexity of $t\mapsto t^2$, (see Lemma \[lem:abc-e-var\] in Appendix \[app:MC-ribbon-tensor-data\] for details) it can be verified that $$\begin{aligned}
{\mathbb{E}}_{A}{\text{\rm{Var}}}_{B|A}[f] \geq {\text{\rm{Var}}}_B{\mathbb{E}}_{A|B}[f].\end{aligned}$$ Thus using the law of total variance we have $$\begin{aligned}
{\text{\rm{Var}}}[f] &= {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] + {\mathbb{E}}_{A}{\text{\rm{Var}}}_{B|A}[f]
 \geq {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] + {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f],\end{aligned}$$ As a result, $(1, 1)\in {\mathfrak{S}}(A, B)$ which gives ${\mathfrak{S}}(A,B)=[0,1]^2$.

Note that for any function $f_{AB}$ we have $f=\tilde f + {\mathbb{E}}[f]$ for some function $\tilde f$ with ${\mathbb{E}}[\tilde f]=0$. Then rewriting the definition of MC ribbon in terms of $\tilde f$ we obtain the following equivalent characterization of the MC ribbon.

\[lem:def-MC-ribbon-zero\] For a bipartite distribution $p_{AB}$, its MC ribbon ${\mathfrak{S}}(A, B)$ is the set of pairs $(\lambda_1, \lambda_2)$ of non-negative numbers such that for every function $f_{AB}$ with ${\mathbb{E}}[f]=0$ we have $${\mathbb{E}}[f^2]\geq \lambda_1 {\mathbb{E}}_A[({\mathbb{E}}_{B|A}[f])^2] +\lambda_2 {\mathbb{E}}_B[({\mathbb{E}}_{A|B}[f])^2].$$

The following theorem analogously to Theorem \[thm:ribbon-tensor-data\] states the main properties of the MC ribbon.

\[thm:MC-ribbon-tensor-data\] The MC ribbon has the following properties:

1.  *\[Tensorization\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$, then $$\mathfrak S(A_1A_2, B_1B_2)=\mathfrak S(A_1,B_1)\cap\mathfrak S(A_2, B_2).$$

2.  *\[Data processing\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2|A_1}\cdot p_{B_2|B_1}$, then $$\mathfrak S(A_1,B_1)\subseteq \mathfrak S(A_2, B_2).$$

We will argue later that this theorem can be proved as a consequence of Theorem \[thm:ribbon-tensor-data\]. However, for the sake of completeness, in Appendix \[app:MC-ribbon-tensor-data\] we present a direct proof for this theorem that is based on the law of total variance.

MC ribbon vs HC ribbon {#subsec:MC-HC-ribbons}
----------------------

MC ribbon and HC ribbon have similar properties. They both are equal to $[0,1]^2$ for independent bipartite distributions, have the tensorization property and satisfy the data processing inequality. Furthermore, the proofs of these results for MC ribbon are similar to their proofs for HC ribbon. To prove Theorem \[thm:ribbon-tensor-data\], our basic tool is the chain rule. Similarly to prove Theorem \[thm:MC-ribbon-tensor-data\] in Appendix \[app:MC-ribbon-tensor-data\] we use the law of total variance which can be thought as a chain rule for variance. In the following we make the connection between these ribbons more precise.

Recall that in Lemma \[lem:geom-interpret-HC-ribbon\] we prove that $(\lambda_1, \lambda_2)$ belongs to ${\mathfrak{R}}(A, B)$ if $\Upsilon(p_{AB})$ defined by $$\Upsilon(q_{AB}) = \lambda_1H(q_A) + \lambda_2 H(q_B) - H(q_{AB}),$$ matches its lower convex envelope denoted by $\widetilde \Upsilon$, at $p_{AB}$, i.e, $(\lambda_1, \lambda_2)\in {\mathfrak{R}}(A, B)$ if and only if $\Upsilon(p_{AB})=\widetilde \Upsilon(p_{AB})$. In particular, this implies that $\Upsilon$ is *locally convex* at $p_{AB}$. To make this latter notation more precise we consider the following perturbation around $p_{AB}$. Given a function $f_{AB}$ with ${\mathbb{E}}[f]=0$, define $$\begin{aligned}
q_{AB}^{(\epsilon)}:=p_{AB}(1+\epsilon f_{AB}).
\label{sweepsupport}\end{aligned}$$ Then $q_{AB}^{\epsilon}$ is a probability distribution for sufficiently small $|\epsilon|$, and we may consider $g(\epsilon)=\Upsilon(q_{AB}^{(\epsilon)})$. A straightforward calculation [@GMartonPaper Lemma 2] verifies that[^2] $$\begin{aligned}
g''(0) = {\mathbb{E}}[f^2] -\lambda_1 {\mathbb{E}}_A[({\mathbb{E}}_{B|A}[f])^2)] -\lambda_2 {\mathbb{E}}_B[({\mathbb{E}}_{A|B}[f])^2.\end{aligned}$$ Then, according to Lemma \[lem:def-MC-ribbon-zero\], local convexity for this class of perturbations holds, i.e., $g''(0)\geq 0$ for every choice of $f$, if and only if $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$.

The following theorem states the above observation in the context of auxiliary random variables (see also [@Anantharametal Theorem 4]). The main ideas of its proof are already discussed, so we leave a detailed proof for Appendix \[app:MC-HC-ribbon-proof\].

\[thm:MC-HC-ribbon\] The followings hold.

1.  $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A,B)$ if and only if there exists a constant $K\geq 0$ such that for all $f_{AB}$ with ${\mathbb{E}}[f]=0$ and ${\text{\rm{Var}}}[f]=1$ we have $$I(U_{\epsilon}; AB) + K\epsilon^3 \geq \lambda_1 I(U_{\epsilon};A) + \lambda_2 I(U_{\epsilon}; B),$$ where $p_{ABU_\epsilon}$ is defined by $p(U^{\epsilon}=+1)=p(U^{\epsilon}=-1)=1/2$ and $$\begin{aligned}
    \label{eq:def-p-ab-u-epsilon}
    p_{AB|U_{\epsilon}=u}=p_{AB}(1+\epsilon uf_{AB}).\end{aligned}$$

2.  $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A,B)$ if and only if there exists a constant $K\geq 0$ such that for all $p_{U|AB}$ we have $$I(U; AB) + K\cdot {\mathbb{E}}_U\big[\|p_{AB|U} - p_{AB}\|_1^3\big] \geq \lambda_1 I(U;A) + \lambda_2 I(U; B),$$ where $\|\cdot\|_1$ denotes[^3] the norm-$1$.

3.  ${\mathfrak{R}}(A, B)\subseteq {\mathfrak{S}}(A, B)$.

For simplicity, we sometimes use the big O notation, replacing $K\epsilon^3$ and $K\cdot {\mathbb{E}}_U\big[\|p_{AB|U} - p_{AB}\|_1^3\big]$ with $O(\epsilon^3)$ and $O({\mathbb{E}}_U\big[\|p_{AB|U} - p_{AB}\|_1^3\big])$ respectively. Throughout, whenever we write $O(\cdot)$ we mean multiplication of a constant that depends only on the underlying distribution and $\lambda_1, \lambda_2$.

We can now obtain a proof for Theorem \[thm:MC-ribbon-tensor-data\] using the above theorem; We may follow the same steps as in the proof of Theorem \[thm:ribbon-tensor-data\] and only take care of the third order correction terms. Here with this idea we present a proof for part (i) of Theorem \[thm:MC-ribbon-tensor-data\]. A proof for part (ii) is obtained similarly.

Suppose that $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$, and assume that $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A_1A_2, B_1B_2)$. Take an arbitrary $p_{U|A_1B_1}$ and define $p_{A_1A_2B_1B_2U}$ using . Then following the proof of part (i) of Theorem \[thm:ribbon-tensor-data\] we should add the extra term $$O\big({\mathbb{E}}_U\big[\|p_{A_1A_2B_1B_2|U} - p_{A_1A_2B_1B_2}\|_1^3\big]\big),$$ to the second line of . Then for the third line of  we use $$\|p_{A_1A_2B_1B_2|U=u} - p_{A_1A_2B_1B_2}\|_1= \|p_{A_1B_1|U=u} - p_{A_1B_1}\|_1,$$ which is implied by $p_{A_1A_2B_1B_2|u}=p_{A_1B_1|u}\cdot p_{A_2B_2}$ and $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$. Then using the second characterization of the MC ribbon in the above theorem, we obtain ${\mathfrak{S}}(A_1A_2, B_1B_2)\subseteq {\mathfrak{S}}(A_1, B_1)$. We similarly have ${\mathfrak{S}}(A_1A_2, B_1B_2)\subseteq {\mathfrak{S}}(A_2, B_2)$.

For the other direction we use the first and second characterizations of the MC ribbon in the above theorem simultaneously. Fix some $f_{A_1A_2B_1B_2}$ with ${\mathbb{E}}[f]=0$ and ${\text{\rm{Var}}}[f]={\mathbb{E}}[f^2]=1$, and define $p_{A_1A_2B_1B_2U_\epsilon}$ as in . Then following the proof of part (i) of Theorem \[thm:ribbon-tensor-data\] we should add the extra term $$O({\mathbb{E}}_{U_\epsilon}[\|p_{A_1B_1|U_\epsilon} -p_{A_1B_1}\|_1^3]),$$ to the right hand side of , and the extra term $$O({\mathbb{E}}_{U_\epsilon A_1B_1}[\|p_{A_2B_2|U_\epsilon A_1B_1} - p_{A_2B_2}\|_1^3]),$$ to the right hand side of . Then to write down  we add up the above two terms and verify that $$\begin{aligned}
\label{eq:ineq-a1b1ua2b2-5}
{\mathbb{E}}_{U_\epsilon}[\|p_{A_1B_1|U_\epsilon} -p_{A_1B_1}\|_1^3] \leq {\mathbb{E}}_{U_\epsilon}[\|p_{A_1A_2B_1B_2|U_\epsilon} - p_{A_1A_2B_1B_2}\|_1^3] = O(\epsilon^3),\end{aligned}$$ and $$\begin{aligned}
\label{eq:ineq-a1b1ua2b2-6}
{\mathbb{E}}_{U_\epsilon A_1B_1}[\|p_{A_2B_2|U_\epsilon A_1B_1} - p_{A_2B_2}\|_1^3]\leq O(\epsilon^3).\end{aligned}$$ Here  is a consequence of the monotonicity of norm-1 under stochastic maps, and that $\|p_{A_1A_2B_1B_2}\cdot f_{A_1A_2B_1B_2}\|_1=O(1)$ which is derived from ${\mathbb{E}}[f^2]=1$. To prove , using $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$ for every $U_\epsilon=u\in \{\pm 1\}$ we have $$p_{A_1A_2B_1B_2|u}=p_{A_1B_1}\cdot p_{A_2B_2}(1+\epsilon u f).$$ Therefore, for every $(A_1, B_1)=(a_1, b_1)$ we have $$p_{A_2B_2|a_1b_1u} = \frac{p_{A_2B_2}(1+\epsilon u f_{A_2B_2a_1b_1})}{1+ \epsilon u \,{\mathbb{E}}_{A_2B_2}[f_{A_2B_2a_1b_1}]} = p_{A_2B_2} + O(\epsilon),$$ where $f_{A_2B_2a_1b_1}$ is a function of $A_2B_2$ and is defined by restriction of $f$ to $(A_1, B_1)=(a_1, b_1)$. This gives . As a result, ${\mathfrak{S}}(A_1, B_1)\cap {\mathfrak{S}}(A_2, B_2)\subseteq {\mathfrak{S}}(A_1A_2, B_1B_2)$, which completes the proof.

Maximal correlation and MC ribbon {#subsec:rho-MC-ribbon}
---------------------------------

As discussed in the introduction, maximal correlation is an important measure of correlation that similar to the MC ribbon has the tensorization property and satisfies data processing inequality. Here we prove a connection between maximal correlation the our notation of MC ribbon.

The maximal correlation of a bipartite distribution $p_{AB}$ is defined in equation . A simple algebra verifies that it is equivalently defined by $$\begin{aligned}
\label{eq:max-correlatoin}
\rho(A, B):=& \max \quad {\mathbb{E}}[f_Ag_B],
\\&\text{subject to: } {\mathbb{E}}[f_A]={\mathbb{E}}[g_B]=0, \nonumber\\
& \qquad \qquad \quad {\mathbb{E}}[f_A^2]={\mathbb{E}}[g_B^2]=1,\nonumber\end{aligned}$$ where maximum is taken over functions $f_A:\mathcal A\rightarrow \mathbb R$ and $g_B:\mathcal B\rightarrow \mathbb R$.

From the Cauchy-Schwarz inequality we have $0\leq \rho(A, B)\leq 1$. Moreover, $\rho(A, B)=0$ if and only if $p_{AB}=p_A\cdot p_B$, and $\rho(A, B)=1$ if and only if $A$ and $B$ have a *common data* [@Witsenhausen]. Moreover, maximal correlation is equal to the second singular value of a certain matrix in terms of distribution $p_{AB}$ and can be computed efficiently (see e.g. [@Kumar2; @KangUlukus]).

It is known that maximal correlation can equivalently [@Renyi1; @Renyi2] be computed by $$\begin{aligned}
\label{eq:rho2-fa-4}
\rho^2(A, B)  = &\max  \frac{{\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f]}{{\text{\rm{Var}}}[f]}, \end{aligned}$$ where maximum is taken over all non-constant functions $f_A$. For the sake of completeness we give a proof of this fact in Appendix \[app:max-correlation\].

In the above characterization of maximal correlation we observe similar terms as in the definition of the MC ribbon. Indeed, if $f_A$ is a function of $A$ only, by the law of total variance we have ${\text{\rm{Var}}}[f]={\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f]$. Then if $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$, for such an $f_A$ we have $$(1-\lambda_1){\text{\rm{Var}}}[f]\geq \lambda_2{\text{\rm{Var}}}_B{\mathbb{E}}_{A|B}[f],$$ which using  implies that $(1-\lambda_1)/\lambda_2\geq \rho^2(A, B)$ if $\lambda_2\neq 0$ and ${\text{\rm{Var}}}[f]\neq 0$. The following theorem states that this inequality in the other direction holds too. We leave the proof of this theorem for Appendix \[app:max-correlation\].

\[thm:rho-MC-ribbon\] For any bipartite distribution $p_{AB}$ we have $$\rho^2(A, B)=\inf\frac{1-\lambda_1}{\lambda_2},$$ where infimum is taken over all $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$ with $\lambda_2\neq 0$.

The above theorem shows that maximal correlation can be characterized in terms of the MC ribbon. Since by Theorem \[thm:MC-ribbon-tensor-data\] the MC ribbon has the tensorization property and satisfies the data processing inequality, so does maximal correlation.

Maximal correlation has the following properties:

1.  *\[Tensorization\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2B_2}$, then $$\rho(A_1A_2, B_1B_2)=\max\{\rho(A_1, B_1), \rho(A_2, B_2)\}.$$

2.  *\[Data processing\]* If $p_{A_1A_2B_1B_2}=p_{A_1B_1}\cdot p_{A_2|A_1}\cdot p_{B_2|B_1}$, then $$\rho(A_1, B_1)\geq\rho(A_2, B_2).$$

\[corol:rho-data-tensor-3\]

Here is another consequence of the above theorem and Theorem \[thm:MC-HC-ribbon\].

\[corol:MC-subset-HC\] For any bipartite distribution $p_{AB}$ we have $${\mathfrak{R}}(A, B)\subseteq {\mathfrak{S}}(A, B),$$ and $$s^*(A,B):=\inf_{(\lambda_1,\lambda_2)\in {\mathfrak{R}}(A,B)} \frac{1-\lambda_1}{\lambda_2}\geq \,\rho^2(A,B).$$

We finish this section by pointing out that the MC ribbon and HC ribbon are not equal in general. Indeed there are examples [@Anantharametal Section II A] of bipartite distributions $p_{AB}$ for which $s^*(A, B)$ is strictly greater than $\rho^2(A, B)$, which by Theorem \[thm:rho-MC-ribbon\] gives ${\mathfrak{R}}(A, B)\neq {\mathfrak{S}}(A,B)$.

MC ribbon for no-signaling boxes {#sec:MC-ribbon-wiring}
================================

In the same way we defined the HC ribbon for no-signaling boxes, we may define the MC ribbon for them too.

Given a no-signaling box $p(ab|xy)$, we define its MC ribbon to be the intersection of the MC ribbons of its outputs conditioned on all possible inputs, i.e., $$\mathfrak S(A, B|X, Y):=\bigcap_{x,y}\mathfrak S(A, B|X=x, Y=y).$$ We also define the maximal correlation of $p(ab|xy)$ to be the maximum of the maximal correlation of its outputs conditioned on all possible inputs, i.e., $$\rho(A,B|X, Y):= \max_{x, y} \rho(A, B|X=x, Y=y).$$

Let us first state a variant of Theorem \[thm:rho-MC-ribbon\] for no-signaling boxes. Its proof is essentially the same as the proof of Theorem \[thm:rho-MC-ribbon\] and is presented in Appendix \[app:inf-rho-mc-ribbon-NS\].

\[thm:inf-rho-mc-ribbon-NS\] For any no-signaling box $p(ab|xy)$ we have $$\begin{aligned}
\inf \frac{1-\lambda_1}{\lambda_2} = \rho^2(A, B|XY),\end{aligned}$$ where the infimum is taken over $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B|X, Y)$ with $\lambda_2\neq 0$.

Now we can prove a similar statement to Theorem \[thm:main-theorem\] for the MC ribbon of no-signaling boxes.

\[thm:main-theorem-MC-ribbon\] Suppose that a no-signaling box $p(a'b'| x'y')$ can be generated from $n$ no-signaling boxes $p_i(a_ib_i| x_i y_i)$ where $i\in [n]$, under wirings. Then we have $$\begin{aligned}
\label{eq:mon-wiring-ribbon-MC}
\bigcap_{i=1}^n {\mathfrak{S}}(A_i,B_i|X_i, Y_i) \subseteq {\mathfrak{S}}(A',B'|X',Y').\end{aligned}$$

The proof of this theorem is similar to the proof of Theorem \[thm:main-theorem\]; We only need to replace mutual information with variance. Our main tool in the proof of Theorem \[thm:main-theorem\] is the chain rule, which here should be replaced by the law of total variance.

An alternative proof is obtained by using Theorem \[thm:MC-HC-ribbon\] and adapting the proof of Theorem \[thm:main-theorem\] for a proof for this theorem. Following the same steps as in the proof of Theorem \[thm:main-theorem\], we need to show that $$(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A_{[n]}X_{[n]}\Pi_{[n]}, B_{[n]}Y_{[n]} \Omega_{[n]}).$$

Let $f$ be a function of $A_{[n]}X_{[n]}\Pi_{[n]}B_{[n]}Y_{[n]} \Omega_{[n]}$ with ${\mathbb{E}}[f]=0$ and ${\text{\rm{Var}}}[f]={\mathbb{E}}[f^2]=1$. We then define $p_{U_\epsilon A_{[n]}X_{[n]}\Pi_{[n]}, B_{[n]}Y_{[n]} \Omega_{[n]}}$ as in part (i) of the statement of Theorem \[thm:MC-HC-ribbon\]. Following the proof of Theorem \[thm:main-theorem\], we need to add the extra term $$\begin{aligned}
\label{eq:ineq-u-epsilon-10}
O\big({\mathbb{E}}_{U_\epsilon S_iT_i\Pi_i\Omega_iX_iY_i}\big[\|p_{A_iB_i|U_\epsilon S_iT_i\Pi_i\Omega_iX_iY_i} - p_{A_iB_i|X_iY_i}\|_1^3\big]\big)\leq O(\epsilon^3),\end{aligned}$$ to the right hand side of ; The inequality in  is proved below. Then adding up the above inequalities for $i=1,\dots, n$, we obtain $$\begin{aligned}
\sum_{i=1}^n O\big({\mathbb{E}}_{U_\epsilon S_iT_i\Pi_i\Omega_iX_iY_i}\big[\|p_{A_iB_i|U_\epsilon S_iT_i\Pi_i\Omega_iX_iY_i} - p_{A_iB_i|X_iY_i}\|_1^3\big]\big)\leq O(n\epsilon^3)=O(\epsilon^3).\end{aligned}$$ Here we use the fact that $n$ although arbitrarily large, is a constant. The rest of the proof is identical to the proof of Theorem \[thm:main-theorem\].

It only remains to verify  . Let us define $$g_{A_iB_iX_iY_iS_iT_i\Pi_i\Omega_i}={\mathbb{E}}_{A_{[n]}B_{[n]}X_{[n]}Y_{[n]}\Pi_{n]}\Omega_{[n]} |A_iB_iX_iY_iS_iT_i\Pi_i\Omega_i}[f].$$ Note that for every $U_\epsilon=u\in \{\pm 1\}$ we have $$p_{A_{[n]}X_{[n]}\Pi_{[n]}, B_{[n]}Y_{[n]} \Omega_{[n]}|u} = p_{A_{[n]}X_{[n]}\Pi_{[n]}, B_{[n]}Y_{[n]} \Omega_{[n]}}(1+\epsilon u f).$$ Thus we can compute $$\begin{aligned}
p_{A_iB_iX_iY_iS_iT_i\Pi_i\Omega_i|u}&=p_{A_iB_iX_iY_iS_iT_i\Pi_i\Omega_i}(1+\epsilon u g)\\
&= p_{X_iY_iS_iT_i\Pi_i\Omega_i}\cdot p_{A_iB_i|X_iY_i}(1+\epsilon u g),\end{aligned}$$ where in the second line we use part (i) of Lemma \[lem:dist-wiring\]. As a result, for every $(X_i, Y_i, S_i, T_i, \Pi_i, \Omega_i)=(x_i, y_i, s_i, t_i, \pi_i, \omega_i)$ we have $$p_{A_iB_i|x_i y_i s_i t_i \pi_i \omega_i u}=\frac{p_{A_iB_i|x_iy_i}(1+\epsilon u g_{A_iB_i x_i y_i s_i t_i \pi_i \omega_i})}{1+\epsilon u {\mathbb{E}}_{A_iB_i|x_i y_i}[g_{A_iB_i x_i y_i s_i t_i \pi_i \omega_i}]}=p_{A_iB_i|x_iy_i}+ O(\epsilon).$$ Here for the second equality we use $g(a_ib_ix_i y_i s_i t_i \pi_i \omega_i)=O(1)$ which is implied by ${\mathbb{E}}[f^2]=1$. Equation  is an immediate consequence of the above equation.

The following corollary is a consequence of the above theorem and Theorem \[thm:inf-rho-mc-ribbon-NS\].

\[corol:rho-wiring-monotone\] Suppose that a no-signaling box $p(a'b'| x'y')$ can be generated from $n$ no-signaling boxes $p_i(a_ib_i| x_i y_i)$ where $i\in [n]$, under wirings. Then we have $$\begin{aligned}
\rho(A', B'|X', Y')\leq \max_i \rho(A_i, B_i| X_i, Y_i).\end{aligned}$$

We can now state the following corollary that is similar to Corollary \[corol:HC-ribbon-close-wiring\] but for maximal correlation.

\[corol:rho-close-set\] Let $r\in [0,1]$ be arbitrary. Then the set of no-signaling boxes $p(a, b|x, y)$ with $\rho(A, B|X, Y)\geq r$ is closed under wirings.

The advantage of this corollary comparing to Corollary \[corol:HC-ribbon-close-wiring\] is that computing the maximal correlation of no-signaling boxes is a much easier problem than computing their HC ribbon.

Example: isotropic boxes {#sec:isotropic}
========================

Isotropic boxes are defined by $$\begin{aligned}
\label{eq:iso-box-2}
{\text{\rm{PR}}}_{\eta}(a,b|x,y) := \begin{cases}
\frac{1+\eta}{4} \qquad\qquad \text{if } a \oplus b= xy,\\
\frac{1-\eta}{4} \qquad\qquad \text{otherwise}.\\
\end{cases}\end{aligned}$$ Here $a, b, x,y\in \{0,1\}$ and $0\leq \eta\leq 1$ is arbitrary. Note that ${\text{\rm{PR}}}_\eta(a|x,y)$ and ${\text{\rm{PR}}}_{\eta}(b|x,y)$ are both the uniform distribution independent of $x, y$, so ${\text{\rm{PR}}}_\eta$ is a no-signaling box. Here as an application of Corollary \[corol:rho-wiring-monotone\] we prove Conjecture \[conj1\] in the range $\eta_1, \eta_2\in [1/\sqrt 2, 1]$. We start with the case where the parties are not provided with common randomness.

\[thm:isotropic-box\] For $0\leq \eta_1<\eta_2\leq 1$, using an arbitrary number of copies of ${\text{\rm{PR}}}_{\eta_1}$, a single copy of ${\text{\rm{PR}}}_{\eta_2}$ cannot be generated under wirings.

Let $q_{\eta}(c, c')$ be the following distribution. $$\begin{aligned}
q_{\eta}(c, c') := \begin{cases}
\frac{1+\eta}{4} \qquad\qquad \text{if } c = c',\\
\frac{1-\eta}{4} \qquad\qquad \text{otherwise}.\\
\end{cases}\end{aligned}$$ If $xy=0$ then the conditional distribution ${\text{\rm{PR}}}_{\eta}(a,b| x,y)$ is equal to $q_{\eta}(a,b)$, and if $xy=1$ it coincides with $q_{\eta}(a\oplus 1, b)$. On the other hand a simple computation verifies that $\rho(q_\eta)=\eta$. As a result we have $$\rho({\text{\rm{PR}}}_{\eta_1}) = \eta_1< \eta_2=\rho({\text{\rm{PR}}}_{\eta_2}).$$ The result then follows from Corollary \[corol:rho-wiring-monotone\].

We now handle the case where common randomness is also available. For this we use the notion of CHSH value of boxes with binary inputs and outputs defined by $${\text{\rm{CHSH}}}:= \frac{1}{4}\sum_{a, b, x, y} \delta_{a\oplus b, xy} p(a, b|x,y),$$ where $\delta_{a\oplus b, xy}=1$ if $a\oplus b=xy$, and $\delta_{a\oplus b, xy}=0$ otherwise.

\[thm:isotropic-box-com-rand\] For $1/\sqrt 2\leq \eta_1<\eta_2\leq 1$, using common randomness and an arbitrary number of copies of ${\text{\rm{PR}}}_{\eta_1}$, a single copy of ${\text{\rm{PR}}}_{\eta_2}$ cannot be generated under wirings.

Suppose that ${\text{\rm{PR}}}_{\eta_2}$ can be generated with common randomness and with some copies of ${\text{\rm{PR}}}_{\eta_1}$ under wirings. Let the common randomness shared between the two parties be $R$. Then for each $R=r$, the parties generate some box $q_r(\cdot|\cdot)$ such that $$\Pr_{\eta_2}(a, b| x, y) = \sum_r p(R=r) q_r(a, b| x, y).$$ Note that the CHSH value is a linear function. Moreover, we have ${\text{\rm{CHSH}}}({\text{\rm{PR}}}_{\eta_2})=(1+\eta_2)/2$. Therefore, $$\sum_r p(R=r) {\text{\rm{CHSH}}}(q_r) = (1+\eta_2)/2.$$ Thus for at least one value of $r$ with $p(R=r)\neq 0$ we have ${\text{\rm{CHSH}}}(q_r)\geq (1+\eta_2)/2$. In the following lemma we show that this latter inequality implies $$\begin{aligned}
\label{eq:frpr-eta}
\rho(q_r) \geq \rho(\Pr_{\eta_2})=\eta_2.\end{aligned}$$ On the other hand, by assumption two parties having access to some copies of ${\text{\rm{PR}}}_{\eta_1}$ can generate $q_r$ (without common randomness). Then by Corollary \[corol:rho-wiring-monotone\] we have $$\rho(\eta_1)=\eta_1\geq \rho(q_r).$$ This is in contradiction with  since $\eta_2>\eta_1$.

To complete the above proof we need the following lemma, showing that among all no-signaling boxes of the same CHSH value, PR boxes have the smallest maximal correlation.

\[lem:ribbon-rho-CHSH\] Let $q(\cdot | \cdot)$ be an arbitrary no-signaling box with binary inputs and outputs. Suppose that ${\text{\rm{CHSH}}}(q)\geq (1+\eta)/2$ for some $1/\sqrt{2}\leq \eta\leq 1$. Then we have $\rho(q)\geq \eta=\rho({\text{\rm{PR}}}_\eta)$.

Any no-signaling box with binary inputs and outputs is determined by eight parameters. Indeed, we may write $$\begin{aligned}
q(a, b| x,y)=\frac{1}{4}(1+(-1)^a\alpha_x+(-1)^b\beta_y + (-1)^{a+ b}\zeta_{xy})\end{aligned}$$ Then $$q(a|x,y)=\frac{1}{2}(1+(-1)^a\alpha_x), \qquad \qquad p(b|xy)=\frac{1}{2}(1+(-1)^b\beta_y),$$ and $q(a, b|x,y)$ is no-signaling. The fact that $q(a, b| x,y)$’s are non-negative is equivalent to $$1-|\alpha_x - \beta_y| \geq \zeta_{xy} \geq |\alpha_x+ \beta_y|-1,$$ for all $x, y$. In particular we have $|\alpha_x|, |\beta_y|\leq 1$.

The maximal correlation of a bipartite random variable with binary parts can be found in [@Beigi12 Proof of Lemma 7]. Indeed for every $x, y$ we have $$\begin{aligned}
\rho(q(a, b| x,y)) = \frac{|\zeta_{xy}-\alpha_x\beta_y|}{\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}}\,,\end{aligned}$$ where we put $\frac{0}{0}=0$. Then $$\begin{aligned}
\label{eq:rho-f23}
\rho(q)=\max_{x, y} \frac{|\zeta_{xy}-\alpha_x\beta_y|}{\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}}.\end{aligned}$$

On the other hand it is not hard to see that $$\begin{aligned}
\label{eq:chsh-q-zeta}
{\text{\rm{CHSH}}}(q)= \frac{1}{4}\sum_{x,y} \frac{1+(-1)^{xy}\zeta_{x,y}}{2}\geq \frac{1+\eta}{2}.\end{aligned}$$ In Appenix \[app:rho-chsh\] we show that for every $\alpha_x, \beta_y, \zeta_{xy}$ with the above conditions, equation  implies that $\rho(q)$ given by  is at least $\eta$.

Conclusion {#sec:conclusion}
==========

In this paper we defined the notion of HC ribbon for no-signaling boxes, and proved a data processing type monotonicity property for the HC ribbon of no-signaling boxes under wirings.

We also defined the notion of MC ribbon for bipartite distributions and showed that it has the tensorization property and is monotone under local operations. Generalizing its definition for no-signaling boxes, we showed that similar to the HC ribbon, MC ribbon is also monotone under wirings of no-signaling boxes. As a consequence of this result, we proved that maximal correlation is also monotone under wirings.

As an application of these results, we proposed a systematic method to construct sets of no-signaling boxes that are closed under wirings. Moreover, we proved a conjecture about simulating isotropic boxes with each other for certain range of parameters. This provides us with a continuum of sets of non-local boxes that are closed under wirings. The existence of such sets was also conjectured in [@Review14].

In the problem of simulating isotropic boxes with each other, we used maximal correlation together with HC ribbon in order to prove Conjecture \[conj1\] (in the range of parameters $\eta_1, \eta_2\in [1/\sqrt 2, 1]$) when common randomness is available too. Interestingly the range of parameters for which we could prove this conjecture starts with $1/\sqrt 2$ which is the border point of quantum correlations.

To prove Conjecture \[conj1\] for other values of $\eta_1, \eta_2\in [1/2, 1/\sqrt 2]$, instead of maximal correlation, we can use the monotonicity of either the MC ribbon or HC ribbon under wirings. Another strategy is to use the parameter $s^*$ defined in Corollary \[corol:MC-subset-HC\]. We leave the study of this conjecture for the range of parameters $\eta_1, \eta_2\in [1/2, 1/\sqrt 2]$ for future works.

In general HC ribbon cannot be used alone to study wirings of no-signaling boxes when common randomness is available. We leave a more systematic study of common randomness in wirings for future works too.

In this paper we studied wirings of bipartite boxes only. We however may consider wirings of multipartite boxes. We have defined the HC ribbon and MC ribbon in the multipartite case too [@BGfuture]. With this definition, the work of [@Nair] extends to the multipartite case as well. We however do not know whether Theorem \[thm:main-theorem\] and Theorem \[thm:main-theorem-MC-ribbon\] can be extended to the multipartite case or not.

**Acknowledgements.** The authors are thankful to T. Vértesi, M. Navascués, O. Etesami and O. Ahmadi for their comments on the early drafts the paper.

**Appendix**

Maximal correlation under wiring of two boxes {#mc-wiring2}
=============================================

Here we present a proof of equation . The first inequality $\rho(A, B)\leq \rho(AX, BY)$ is a consequence of the known fact that maximal correlation is monotone under local stochastic maps (see Corollary \[corol:rho-data-tensor-3\]). Then we need to verify the second inequality, that is summarized in the following lemma.

\[lem:simple-wiring-rho\] Suppose that $q(abxy)=q(xy)p(ab|xy)$ such that $p(a|xy)=p(a|x)$ and $p(b|xy)=p(b|y)$. Then we have $$\rho(AX, BY)\leq \max\{\rho(X, Y), \rho(A, B|X, Y)\}.$$

Our proof of this lemma borrows ideas from the proof of the tensorization property of maximal correlation given in [@Kumar].

Starting from the definition of maximal correlation, a simple algebra verifies that $\rho(A, B)$ is the smallest number $\rho$ such that for every $f_A, g_B$ we have $$\begin{aligned}
\label{eq:rho-inequality-def}
{\mathbb{E}}[f_Ag_B]\leq {\mathbb{E}}[f_A]\cdot {\mathbb{E}}[g_B] + \rho{\text{\rm{Var}}}[f_A]^{1/2}{\text{\rm{Var}}}[g_B]^{1/2}.\end{aligned}$$ As a result, we need to show that for functions $f_{AX}$ and $g_{BY}$ we have $${\mathbb{E}}[fg]\leq {\mathbb{E}}_{AX}[f]{\mathbb{E}}_{BY}[g]+\rho\sqrt{{\text{\rm{Var}}}_{AX}[f]{\text{\rm{Var}}}_{BY}[g]},$$ where $\rho=\max\{\rho(X, Y), \rho(A, B|X, Y)\}$. For this we compute $$\begin{aligned}
{\mathbb{E}}[fg]&= {\mathbb{E}}_{XY} {\mathbb{E}}_{AB|XY}[fg]\\
&\stackrel{\text{\rm (i)}}{\leq} {\mathbb{E}}_{XY}\left[ {\mathbb{E}}_{A|XY}[f]\cdot {\mathbb{E}}_{B|XY}[g] +\rho\sqrt{{\text{\rm{Var}}}_{A|XY}[f]\cdot {\text{\rm{Var}}}_{B|XY}[g]}   \,    \right]\\
&= {\mathbb{E}}_{XY}\Big[ {\mathbb{E}}_{A|X}[f]\cdot{\mathbb{E}}_{B|Y}[g]\Big] +\rho{\mathbb{E}}_{XY}\Big[\sqrt{{\text{\rm{Var}}}_{A|X}[f]\cdot{\text{\rm{Var}}}_{B|Y}[g]}\,\Big]       \\
&\stackrel{\text{\rm (ii)}}{\leq}  {\mathbb{E}}_{X}{\mathbb{E}}_{A|X}[f]\cdot{\mathbb{E}}_Y{\mathbb{E}}_{B|Y}[g] + \rho\sqrt{{\text{\rm{Var}}}_X{\mathbb{E}}_{A|X}[f]\cdot{\text{\rm{Var}}}_Y{\mathbb{E}}_{B|Y}[g]}\\
& \quad +\rho{\mathbb{E}}_{XY}\Big[\sqrt{{\text{\rm{Var}}}_{A|X}[f]\cdot{\text{\rm{Var}}}_{B|Y}[g]}\,\Big]  \\
&\stackrel{\text{\rm (iii)}}{\leq} {\mathbb{E}}_{X}{\mathbb{E}}_{A|X}[f] \cdot {\mathbb{E}}_Y{\mathbb{E}}_{B|Y}[g] + \rho\sqrt{{\text{\rm{Var}}}_X{\mathbb{E}}_{A|X}[f]\cdot {\text{\rm{Var}}}_Y{\mathbb{E}}_{B|Y}[g]}\\
&\quad +\rho\sqrt{{\mathbb{E}}_X{\text{\rm{Var}}}_{A|X}[f]\cdot {\mathbb{E}}_Y{\text{\rm{Var}}}_{B|Y}[g]}  \\
&\stackrel{\text{\rm (iv)}}{\leq} {\mathbb{E}}_{AX}[f]\cdot {\mathbb{E}}_{BY}[g] +\rho      
\sqrt{\left({\text{\rm{Var}}}_X{\mathbb{E}}_{A|X}[f]+{\mathbb{E}}_X{\text{\rm{Var}}}_{A|X}[f] \right) \left({\text{\rm{Var}}}_Y{\mathbb{E}}_{B|Y}[g]+ {\mathbb{E}}_Y{\text{\rm{Var}}}_{B|Y}[g]\right)}                  \\
&\stackrel{\text{\rm (v)}}{=}  {\mathbb{E}}_{AX}[f]\cdot {\mathbb{E}}_{BY}[g]+\rho\sqrt{{\text{\rm{Var}}}_{AX}[f]{\text{\rm{Var}}}_{BY}[g]}.\end{aligned}$$ Here in (i) we use  for the conditional distribution $p_{AB|X=x,Y=y}$ for all $(x, y)$ and take average over all those inequalities. In (ii) we use  for distribution $q_{XY}$ applied to functions ${\mathbb{E}}_{A|X}[f]$ and ${\mathbb{E}}_{B|Y}[g]$. In (iii) and (iv) we use the Cauchy-Schwarz inequality, and in (v) we use the law of total variance.

Gray-Wyner problem and the HC ribbon {#app:GW}
====================================

In this appendix we observe that the HC ribbon is connected to the well-studied problem of Gray-Wyner which yields a tangible operational interpretation for the HC ribbon.

The Gray-Wyner problem [@GrayWyner] is a distributed source coding problem, consisting of a transmitter and two receivers. The transmitter has i.i.d. repetitions of two correlated sources $A_{[n]}, B_{[n]}$ and aims to send $A_{[n]}$ to the first receiver and $B_{[n]}$ to the second receiver. The transmitter can send a common message of rate $R_0$ over a noiseless channel to both the receivers, and private messages of rates $R_1$ and $R_2$ to the two receivers respectively. This is depicted in Figure 2. Then Gray and Wyner show that this is possible if and only if there exists some $p_{U|AB}$ such that $$\begin{aligned}
R_0&\geq I(U;AB),\label{eq:gw-1}\\
R_1&\geq H(A|U),\\
R_2&\geq H(B|U).\label{eq:gw-3}\end{aligned}$$ In particular, when $R_0=0$, we should have $R_1\geq H(A)$ and $R_2\geq H(B)$, which is consistent with Shannon’s source compression theorem. Now suppose that we are allowing for some positive rate for common message $R_0>0$, and we are asking for the amount of reduction in private rates $R_1$ and $R_2$, i.e., how large $\Delta_{R_1}=H(A)-R_1$ and $\Delta_{R_2}=H(B)-R_2$ can be? These are two parameters that we would like to maximize simultaneously, but there is a tradeoff between them. Since by - for some $p_{U|AB}$ we have $$\Delta_{R_1}\leq I(U;A), \qquad \Delta_{R_2}\leq I(U;B), \qquad R_0\geq I(U;AB),$$ one can see that the non-negative triple $(\Delta_{R_1}, \Delta_{R_2}, R_0)$ is obtainable if and only if[^4] $$\lambda_1\Delta_{R_1}+\lambda_2\Delta_{R_2}\leq R_0, \qquad \forall (\lambda_1, \lambda_2)\in {\mathfrak{R}}(A, B).$$

As we use the HC ribbon to study wirings of no-signaling boxes, we also notice that the Gray-Wyner problem is related to the principle of Information Casualty [@IC09] when the sources are independent. The authors have conjectured that this connection extends to correlated sources as well [@OurICPaper].

![The Gray-Wyner problem: A transmitter has two sources which should be sent to two receivers via three noiseless channels one of which is public and the other two are private. ](gw.pdf){width="3.7in"}

Proof of Lemma \[lem:dist-wiring\] {#app:lemm-proof}
==================================

Throughout this section, we need to write down the joint probability distribution of various random variables raised in wirings. First let us give some explanations on the validity of . Suppose for a moment that all the boxes $p_i(a_ib_i|x_iy_i)=p_i(a_i|x_i)p_i(b_i|y_i)$ have the product form. So Alice and Bob are completely decoupled from each other. Then at her $j$-th action, Alice has ${\tilde{t}}_j$, and generates ${\tilde{\pi}}_j$ and ${\tilde{x}}_j$. Then she puts ${\tilde{x}}_j$ as in the input of box ${\tilde{\pi}}_j$ and observes ${\tilde{a}}_j$. Therefore, the joint distribution of random variables at Alice’s side is $$p(a_{[n]}x_{[n]}\pi_{[n]}|x') = \prod_{j=1}^n q({\tilde{\pi}}_j {\tilde{x}}_j|{\tilde{t}}_j x') p_{{\tilde{\pi}}_j}({\tilde{a}}_j|{\tilde{x}}_j).$$ We notice that ${\tilde{\pi}}_1, \dots, {\tilde{\pi}}_n$ is a permutation of $[n]$. So we may instead write this product with indices $j=\pi_i$. Then using ${\tilde{\pi}}_{\pi_i}=i$ we obtain $$\begin{aligned}
p(a_{[n]}x_{[n]}\pi_{[n]}|x') & = \prod_{i=1}^n q({\tilde{\pi}}_{\pi_i} {\tilde{x}}_{\pi_i}|{\tilde{t}}_{\pi_i} x') p_{{\tilde{\pi}}_{\pi_i}}({\tilde{a}}_{\pi_i}|{\tilde{x}}_{\pi_i})\\
&= \prod_{i=1}^n q(i x_i|t_i x') p_{i}(a_{i}|x_{i}).\end{aligned}$$ By the same reasoning for random variables at Bob’s side we have $$\begin{aligned}
p(b_{[n]}y_{[n]}\omega_{[n]}|y') &= \prod_{i=1}^n q(i y_i|s_i y') p_{i}(b_{i}|y_{i}).\end{aligned}$$ As a result when the boxes $p_i(a_ib_i|x_iy_i)$ have the product form $p_i(a_i|x_i)p_i(b_i|y_i)$, we have $$\begin{aligned}
\label{eq:24asdf}
p\big(a_{[n]}b_{[n]}x_{[n]}y_{[n]} \pi_{[n]}\omega_{[n]}| x'y'\big) = \prod_{i=1} p_i(a_ib_i|x_iy_i)q(i x_i|t_i x')q(i y_i|s_i y').\end{aligned}$$

Now consider general no-signaling boxes $p_i(a_ib_i|x_iy_i)$ that are not necessarily of product form. Note that to generate $a_{[n]}b_{[n]}x_{[n]}y_{[n]} \pi_{[n]}\omega_{[n]}$ Alice and Bob use each box once. Thinking of this box as a channel, the probability $p\big(a_{[n]}b_{[n]}x_{[n]}y_{[n]} \pi_{[n]}\omega_{[n]}| x'y'\big)$ should be linear in terms of box $p_i(a_ib_i|x_iy_i)$ for any $i$. On the other hand we showed that  is valid for product boxes. Then the same equation holds if $p_i(a_ib_i|x_iy_i)$ is in the linear span of product boxes. On the other hand no-signaling boxes are in the linear span of product boxes.[^5] So  holds for all no-signaling boxes.

Now, let us turn to the proof of Lemma \[lem:dist-wiring\]. Since everything is conditioned on $x',y'$ for simplicity of notation we drop the conditionings on $x',y'$ and keep in mind that they are fixed. We also drop index $i$ in $p_i(\cdot |\cdot)$ as it is clear from other indices. We then have $$\begin{aligned}
\label{eq:p-a-x-m-n}
p\big(a_{[n]}b_{[n]}x_{[n]}y_{[n]} \pi_{[n]}\omega_{[n]}\big)=\prod_{i=1}^n\bigg[ p\big(a_ib_i\,\big|\,x_iy_i\big) q\big(ix_i\,\big|\,t_i \big)q\big(iy_i\,\big|\,s_i\big)\bigg].\end{aligned}$$

Recall that Alice uses the $i$-box in her action $\Pi_i=\pi_i$. Before using this box, Alice has used the boxes ${\tilde{\pi}}_1, \dots, {\tilde{\pi}}_{\pi_i-1}$, and has the transcript $t_i={\tilde{\pi}}_{[\pi_i-1]}{\tilde{x}}_{[\pi_i-1]}{\tilde{a}}_{[\pi_i-1]}$. She then uses box $i$ with input $x_i$ with probability $q(ix_i|t_i)$. Similarly Bob uses box $i$ in step $\Omega_i=\omega_i$. Before using this box he uses boxes ${\tilde{\omega}}_1, \dots, {\tilde{\omega}}_{\omega_i-1}$, and has transcript $s_i={\tilde{\omega}}_{[\omega_i-1]}{\tilde{y}}_{[\omega_i-1]}{\tilde{b}}_{[\omega_i-1]}$. Then he chooses box $i$ with input $y_i$ with probability $q(iy_i|s_i)$. When Alice and Bob both use the $i$-th box with inputs $x_i, y_i$, their outputs are $a_i, b_i$ with probability $p(a_ib_i| x_iy_i)$.

Imagine that Alice and Bob perform their wirings until they get to the $i$-th box, and then they stop. Then by the above discussion and the no-signaling condition, the joint distribution of the outcomes of Alice and Bob is $$\begin{aligned}
p(t_ia_ix_i \pi_i s_i y_ib_i\omega_i) =&\prod_{j\in M_i} p(a_jb_j|x_jy_j) q(jx_j|t_j)q(jy_j|s_j) \nonumber\\
&\cdot\prod_{j\in {\tilde{\pi}}_{[\pi_i]}\setminus M_i} p(a_j|x_j)q(jx_j|t_j)\cdot \prod_{j\in {\tilde{\omega}}_{[\omega_i]\setminus M_i}} p(b_j|y_j)p(j y_j|s_j),\label{eq:p-a-x-m-i}\end{aligned}$$ where $M_i:=  {\tilde{\pi}}_{[\pi_i]}\cap {\tilde{\omega}}_{[\omega_i]}$. Note that ${\tilde{\pi}}_{\pi_i}= {\tilde{\omega}}_{\omega_i}=i$, so $i\in M_i$.

Now imagine that Alice performs wirings until she gets to the $i$-th box and then she stops, but Bob uses all the boxes. Then again by the no-signaling condition the joint distribution of their outcomes is $$\begin{aligned}
\label{eq:p-a-x-k-n-ell-i}
p\big(  t_{i} a_{i} x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)& =\prod_{j\in {\tilde{\pi}}_{[\pi_i]}}p(a_j b_j|x_jy_j)q(jx_j|t_j)q(jy_j|s_j)\cdot \prod_{j\notin {\tilde{\pi}}_{[\pi_i]}} p(b_j|y_j)q(jy_j|s_j).\end{aligned}$$

To obtain the next required marginal, imagine that Alice performs $i$ wirings (until the $i$-th action) and then stops, i.e., Alice stops when she uses box ${\widetilde{\Pi}}_i$. Assume that Bob uses all the boxes. Then Alice observes ${\tilde{t}}_i, {\tilde{a}}_i, {\tilde{x}}_i, {\tilde{\pi}}_i$ and Bob observes $ b_{[n]}y_{[n]}\omega_{[n]}$, and the joint distribution of these outcomes is $$\begin{aligned}
\label{eq:p-a-x-k-n-ell-i-wpi}
p\big(  {\tilde{t}}_{i} {\tilde{a}}_{i} {\tilde{x}}_i {\tilde{\pi}}_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)& =\prod_{j\in {\tilde{\pi}}_{[i]}}p(a_j b_j|x_jy_j)q(jx_j|t_j)q(jy_j|s_j)\cdot \prod_{j\notin {\tilde{\pi}}_{[i]}} p(b_j|y_j)q(jy_j|s_j).\end{aligned}$$

We can now prove Lemma \[lem:dist-wiring\].

*Proof of* (i): Observe that in  nothing is conditioned on $a_i, b_i$ as $i\in M_i$. Then we have $$\begin{aligned}
p\big(t_ix_i \pi_is_iy_i\omega_i\big) & =\sum_{a_i, b_{i}}  p\big(t_ia_ix_i s_iy_ib_i\big)\nonumber\\
&=\prod_{j\in M_i\setminus\{i\}} p(a_jb_j|x_jy_j) q(jx_j|t_j)q(jy_j|s_j) \nonumber\\
&\quad \cdot\prod_{j\in {\tilde{\pi}}_{[\pi_i]}\setminus M_i} p(a_j|x_j)q(jx_j|t_j)\cdot \prod_{j\in {\tilde{\omega}}_{[\omega_i]\setminus M_i}} p(b_j|y_j)p(j y_j|s_j).\label{eq:p-t-i-x-i}\end{aligned}$$ Therefore, $$\begin{aligned}
\label{eq:abxsty89}
p\big(a_ib_{i}\big|\,t_ix_i\pi_i s_iy_i\omega_i\big) & =\frac{p\big(a_ib_{i}t_ix_i\pi_i s_iy_i\omega_i\big)}{p\big(t_ix_i\pi_i s_iy_i\omega_i\big) }
 = p\big(a_ib_i\big|\,x_iy_i\big).\end{aligned}$$ As a result $H(A_iB_{i} | T_i\Pi_i S_{i} \Omega_iX_iY_i) = H(A_iB_{i} | X_iY_i)$, which gives the desired result.

*Proof of* (ii): From  we find that $$\begin{aligned}
p\big(a_i\big|\,t_ix_i\pi_i s_iy_i\omega_i\big) & 
 = p\big(a_i\big|\,x_iy_i\big) = p(a_i\big|x_i).\end{aligned}$$ Therefore $H(A_i\big|\,T_iX_i\Pi_i S_iY_i\Omega_i\big)=H(A_i\big| X_i)$, or equivalently $I(A_i; T_i\Pi_i S_iY_i\Omega_i\big|X_i) = 0$ This gives $I\big(A_i; S_i Y_i \Omega_i\big|\, T_i X_i \Pi_i\big)=0$. The other equality is proved similarly.

*Proof of* (iii): Again using the fact that $i\in  {\tilde{\pi}}_{[\pi_i]}$ and nothing in  is conditioned on $a_i$ we have $$\begin{aligned}
p\big(   t_{i}  x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)&= \sum_{a_{i}} p\big(  t_{i} a_{i} x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)\nonumber\\
& = p(b_i|x_iy_i)q(ix_i|t_j)q(iy_i|s_i) \cdot \prod_{j\in {\tilde{\pi}}_{[\pi_i]}\setminus\{i\}}p(a_j b_j|x_jy_j)q(jx_j|t_j)q(jy_j|s_j)\nonumber\\&\qquad \cdot \prod_{j\notin {\tilde{\pi}}_{[\pi_i]}} p(b_j|y_j)q(jy_j|s_j).
\label{eq:ptxasetminusi}\end{aligned}$$ We therefore have $$\begin{aligned}
p\big(  a_i| t_{i}  x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big) & =\frac{p\big(   t_{i} a_i x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)}{p\big(   t_{i}  x_i \pi_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)} \\
& = \frac{p\big(a_{i}b_i|x_iy_i\big)}{p\big(b_i|y_i\big)}\\
& = p(a_i| b_ix_iy_i).\end{aligned}$$ This means that $H(A_i|X_iB_iY_i) = H(A_i| T_iX_i\Pi_iB_{[n]}Y_{[n]}\Omega_{[n]})$, or equivalently $$I\big(A_{i};  T_{i}\Pi_iB_{[n]}Y_{[n]}\Omega_{[n]}\big|\, X_iB_i Y_{i} \big)=0.$$ This gives $I\big(A_i;  B_{[n]}Y_{[n]}\Omega_{[n]}  \big|\, T_iX_i \Pi_i B_i Y_i\Omega_i\big)=0$. The other equality is proved similarly.

*Proof of* (iv): In  nothing is conditioned on $\tilde a_i$. Then we have $$\begin{aligned}
p\big(  {\tilde{t}}_{i} {\tilde{x}}_i {\tilde{\pi}}_i  b_{[n]}y_{[n]}\omega_{[n]}   \big)& = q({\tilde{\pi}}_i{\tilde{x}}_i|{\tilde{t}}_i)\cdot\prod_{j\in {\tilde{\pi}}_{[i-1]}}p(a_j b_j|x_jy_j)q(jx_j|t_j)q(jy_j|s_j)\cdot \prod_{j\notin {\tilde{\pi}}_{[i-1]}} p(b_j|y_j)q(jy_j|s_j),\end{aligned}$$ where we use ${\tilde{x}}_i=x_{{\tilde{\pi}}_i}$ and ${\tilde{t}}_i=t_{{\tilde{t}}_i}$. Thus since in the above equation nothing is conditioned on ${\tilde{\pi}}_i, {\tilde{x}}_i$ we obtain $$p({\tilde{\pi}}_i{\tilde{x}}_i|  {\tilde{t}}_i  b_{[n]}y_{[n]}\omega_{[n]} ) = q({\tilde{\pi}}_i{\tilde{x}}_i|{\tilde{t}}_i).$$ This gives $H\big({\widetilde{\Pi}}_i{\widetilde{X}}_i\big|\, {\widetilde{T}}_{i}   B_{[n]}Y_{[n]}\Omega_{[n]} \big) = H\big({\widetilde{\Pi}}_i{\widetilde{X}}_i|{\widetilde{T}}_i\big)$ which is equivalent to $I\big({\widetilde{\Pi}}_i{\widetilde{X}}_i; B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, {\widetilde{T}}_i\big)=0$. The other equation is proved similarly.

Proof of Lemma \[lemma:amnm\] {#app:lemma-amnnproof}
=============================

First note that is implied by by setting $U=A_{[n]}X_{[n]}\Pi_{[n]}$. Thus, we only need to prove . By the chain rule we have $$\begin{aligned}
I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}|V\big)&=I\big(U;{\widetilde{A}}_{[n]}{\widetilde{X}}_{[n]}{\widetilde{\Pi}}_{[n]}|V\big)\nonumber\\
&=\sum_{i=1}^n I\big(U;{\widetilde{A}}_{i}{\widetilde{X}}_{i}{\widetilde{\Pi}}_{i}|{\widetilde{A}}_{[i-1]}{\widetilde{X}}_{[i-1]}{\widetilde{\Pi}}_{[i-1]}V\big)
\nonumber\\&=\sum_{i=1}^n \bigg[I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{A}}_{[i-1]}{\widetilde{X}}_{[i-1]}{\widetilde{\Pi}}_{[i-1]}V\big)+I\big(U;{\widetilde{A}}_{i}|{\widetilde{A}}_{[i-1]}{\widetilde{X}}_{[i-1]}{\widetilde{\Pi}}_{[i-1]} {\widetilde{\Pi}}_{i}{\widetilde{X}}_{i}V\big)\bigg]\nonumber\\
&=\sum_{i=1}^n \bigg[I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_iV\big)+I\big(U;{\widetilde{A}}_{i}|{\widetilde{T}}_i {\widetilde{\Pi}}_{i}{\widetilde{X}}_{i}V\big)\bigg],\label{eq:cr345}\end{aligned}$$ where in the last line we use ${\widetilde{T}}_{i}={\widetilde{A}}_{[i-1]}{\widetilde{X}}_{[i-1]}{\widetilde{\Pi}}_{[i-1]}$. Now note that $$\begin{aligned}
\sum_{i=1}^nI\big(U;{\widetilde{A}}_{i}|{\widetilde{T}}_i {\widetilde{\Pi}}_{i}{\widetilde{X}}_{i}V\big) & = \sum_{i=1}^n \sum_{j=1}^n I\big(U;{\widetilde{A}}_{i}|{\widetilde{T}}_i {\widetilde{X}}_{i}V, {\widetilde{\Pi}}_{i}=j\big) p({\widetilde{\Pi}}_i=j) \\
 & = \sum_{i=1}^n \sum_{j=1}^n I\big(U;A_{j}|T_j X_{j}V, {\widetilde{\Pi}}_{i}=j\big) p({\widetilde{\Pi}}_i=j) \\
& = \sum_{j=1}^n \sum_{i=1}^n  I\big(U;A_{j}|T_j X_{j}V, \Pi_{j}=i\big) p(\Pi_j=i) \\
& = \sum_{j=1}^n  I\big(U;A_{j}|T_j X_{j} \Pi_{j}V\big), \end{aligned}$$ where in the second line we use ${\widetilde{A}}_i=A_{{\widetilde{\Pi}}_i}$, ${\widetilde{X}}_i=X_{{\widetilde{\Pi}}_i}$ and ${\widetilde{T}}_i=T_{{\widetilde{\Pi}}_i}$, and in the third line we use $\Pi_{{\widetilde{\Pi}}_i}=i$. Since $T_i^{e}=T_i X_{i} \Pi_{i}$, we can write $\sum_{i=1}^nI\big(U;{\widetilde{A}}_{i}|{\widetilde{T}}_i {\widetilde{\Pi}}_{i}{\widetilde{X}}_{i}V\big)= \sum_{i=1}^n  I\big(U;A_{i}|T^e_iV\big)$. Putting this in  we get equation .

Proof of Theorem \[thm:main-theorem\] {#app:proof-main-thm}
=====================================

To complete the proof of Theorem \[thm:main-theorem\] we need to show that $\chi(\lambda_1, \lambda_2)\geq 0$ for $\lambda_1, \lambda_2\in [0,1]$ with $\lambda_1+\lambda_2\geq 1$ where $$\begin{aligned}
\chi(\lambda_1, \lambda_2):=&-\sum_{i=1}^n \bigg[\lambda_{1}I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_i\big)+\lambda_2I\big(U;{\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)\nonumber\\
&\qquad \quad+\lambda_1I\big(U;A_{i};S^e_{i}\big|T_i^e\big) + \lambda_2 I\big(U;B_{i};T^e_{i}\big|\,S_i^e\big) \nonumber\\
&\qquad\quad +I\big(U;A_iB_{i}\big|\,T^e_{i} S^e_i\big)\bigg]
 +I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}B_{[n]}Y_{[n]}\Omega_{[n]}\big).\end{aligned}$$

$\chi(\lambda_1, \lambda_2)$ is an affine function of $(\lambda_1, \lambda_2)$. Moreover, extreme points of the convex set $$\{(\lambda_1, \lambda_2)\,|\, \lambda_1, \lambda_2\in[0,1]\, \&\, \lambda_1+\lambda_2\geq 1\},$$ are $(1, 0), (0,1)$ and $(1, 1)$. So it suffices to prove our claim for $(\lambda_1, \lambda_2)\in \{(1, 0), (0,1), (1, 1)\}$. The proof for $(\lambda_1, \lambda_2)=(0,1)$ is similar to that of $(\lambda_1, \lambda_2)=(1,0)$. So it suffices to prove $\chi(\lambda_1, \lambda_2)\geq 0$ when $$\lambda_1=1, \quad \qquad \lambda_2\in\{0,1\}.$$

Using the chain rule we may write $\chi(1, \lambda_2)= \chi_A(1) + \chi_B(\lambda_2)$ where $$\begin{aligned}
\chi_A(1):=&-\sum_{i=1}^n\bigg[ I\big(U;{\widetilde{X}}_{i}{\widetilde{\Pi}}_i|{\widetilde{T}}_i\big)+I\big(U;A_{i};S^e_{i}\big|T_i^e\big) +I\big(U;A_i\big|\,T^e_{i} S^e_i\big) \bigg]+ I\big(U;A_{[n]}X_{[n]}\Pi_{[n]}\big)
\\
&\\
\chi_B(\lambda_2):=&-\sum_{i=1}^n\bigg[ \lambda_2I\big(U;{\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)+\lambda_2 I\big(U;B_{i};T^e_{i}\big|\,S_i^e\big) + I\big(U;B_{i}\big|\,T^e_{i} A_i S^e_i\big)\bigg]  \\
&+I\big(U;B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}\big).\end{aligned}$$ We start with $\chi_{A}(1)$. $$\begin{aligned}
\chi_A(1)=&-\sum_{i=1}^n\bigg[ H({\widetilde{X}}_i{\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i) - H({\widetilde{X}}_i {\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i U)
 + I(A_i; S_i^e\big|\, T_i^e) - I(A_i ; S_i^e\big|\, T_i^eU)     \\
 &\qquad \quad+H(A_i\big|\, T_i^eS_i^e) - H(A_i\big|\, T_i^eS_i^e U)
    \bigg]
 + H(A_{[n]}X_{[n]}\Pi_{[n]}) - H(A_{[n]}X_{[n]}\Pi_{[n]}\big|\,U)    \end{aligned}$$ Then we can write $\chi_A(1)=\phi_A(1) + \psi_A(1)$ where $$\begin{aligned}
\phi_A(1):=& -\sum_{i=1}^n \bigg[H({\widetilde{X}}_i{\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i)  + I(A_i; S_i^e\big|\, T_i^e)+H(A_i\big|\, T_i^eS_i^e)  \bigg] +H(A_{[n]}X_{[n]}\Pi_{[n]}), \\
&\\
\psi_A(1):=& -\sum_{i=1}^n\bigg[  - H({\widetilde{X}}_i {\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i U)   - I(A_i ; S_i^e\big|\, T_i^eU)   - H(A_i\big|\, T_i^eS_i^e U)\bigg]- H(A_{[n]}X_{[n]}\Pi_{[n]}\big|\,U).   \end{aligned}$$

Using the second equation of Lemma \[lemma:amnm\] with $V=\emptyset$, we get that $$\begin{aligned}
H(A_{[n]}X_{[n]}\Pi_{[n]})=\sum_{i=1}^n \bigg[H({\widetilde{X}}_i {\widetilde{\Pi}}_i| {\widetilde{T}}_i) + H(A_i| T_i^e)  \bigg].\label{eq:tyab5sym}\end{aligned}$$ Putting in $\phi_A(1)$ we find that $$\begin{aligned}
\phi_A(1)=& \sum_{i=1}^n \bigg[-H({\widetilde{X}}_i{\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i)  - I(A_i; S_i^e\big|\, T_i^e)-H(A_i\big|\, T_i^eS_i^e) +H({\widetilde{X}}_i {\widetilde{\Pi}}_i| {\widetilde{T}}_i) + H(A_i| T_i^e) \bigg]=0. \\\end{aligned}$$ We can similarly use the second equation of Lemma \[lemma:amnm\] with $V=U$ to write $$\begin{aligned}
\psi_A(1)&= \sum_{i=1}^n\bigg[   H({\widetilde{X}}_i {\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i U)   + I(A_i ; S_i^e\big|\, T_i^eU)   + H(A_i\big|\, T_i^eS_i^e U)
  - H({\widetilde{X}}_i {\widetilde{\Pi}}_i\big|\, {\widetilde{T}}_i U) -   H(A_i\big|\, T_i^e U)\bigg]   \\
  & =0.  \end{aligned}$$ Therefore $\chi_A(1)=0$, and we need to show that $\chi(1, \lambda_2)=\chi_B(\lambda_2)\geq 0$, where we had $$\begin{aligned}
\chi_B(\lambda_2)=&-\sum_{i=1}^n\bigg[ \lambda_2I\big(U;{\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)+\lambda_2 I\big(U;B_{i};T^e_{i}\big|\,S_i^e\big) + I\big(U;B_{i}\big|\,T^e_{i} A_i S^e_i\big)\bigg]  \\
&+I\big(U;B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}\big).\end{aligned}$$ Again by the chain rule we may write $\chi_B(\lambda_2)=\phi_B(\lambda_2) + \psi_B(\lambda_2)$, where $$\begin{aligned}
\phi_B(\lambda_2):=&-\sum_{i=1}^n\bigg[ \lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)+\lambda_2 I\big(B_{i};T^e_{i}\big|\,S_i^e\big) + H\big(B_{i}\big|\,T^e_{i} A_i S^e_i\big)\bigg]  \\
&+H\big(B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}\big).
&\\
\psi_B(\lambda_2):=&-\sum_{i=1}^n\bigg[-\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i U \big)-\lambda_2 I\big(B_{i};T^e_{i}\big|\,S_i^e U\big) - H\big(B_{i}\big|\,T^e_{i} A_i S^e_iU\big)\bigg]  \\
&-H\big(B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}U\big).\end{aligned}$$ Now note that by Lemma \[lem:dist-wiring\] part (ii) we have $I\big(B_i; T_i^e\big|\, S_i^e\big)=0$. Moreover, we can similarly use the second equation of Lemma \[lemma:amnm\] with $V= A_{[n]}X_{[n]}\Pi_{[n]}$ to write $$H\big(B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}\big) = \sum_{i=1}^n\bigg[  H\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, A_{[n]}X_{[n]}\Pi_{[n]} {\widetilde{S}}_i\big) + H\big(B_i\big|\,A_{[n]}X_{[n]}\Pi_{[n]} S_i^e \big)    \bigg].$$ Therefore, $$\begin{aligned}
\phi_B(\lambda_2)&=\sum_{i=1}^n\bigg[ -\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)- H\big(B_{i}\big|\,T^e_{i} A_i S^e_i\big)  
\nonumber\\&
 \qquad\qquad + H\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, A_{[n]}X_{[n]}\Pi_{[n]} {\widetilde{S}}_i\big) + H\big(B_i\big|\,A_{[n]}X_{[n]}\Pi_{[n]} S_i^e \big) \bigg]\nonumber\\& \geq
\sum_{i=1}^n\bigg[ -\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i\big)- H\big(B_{i}\big|\,T^e_{i} A_i S^e_i\big)  
\nonumber\\&
 \qquad\qquad + H\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, A_{[n]}X_{[n]}\Pi_{[n]} {\widetilde{S}}_i\big) + H\big(B_i\big|\,A_{[n]}X_{[n]}\Pi_{[n]} T^e_{i} A_i S^e_i \big) \bigg]\nonumber\\
&= \sum_{i=1}^n (1-\lambda_2) H\big( {\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, {\widetilde{S}}_i    \big)\nonumber\\
&\geq  \sum_{i=1}^n (1-\lambda_2) H\big( {\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, {\widetilde{S}}_i   U \big),\label{eq:diadoa}\end{aligned}$$ where in the third line we use Lemma \[lem:dist-wiring\] parts (iii) and (iv). We continue $$\begin{aligned}
\psi_B(\lambda_2)&\geq \sum_{i=1}^n\bigg[\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i U \big) + H\big(B_{i}\big|\,T^e_{i} A_i S^e_iU\big)\bigg]   -H\big(B_{[n]}Y_{[n]}\Omega_{[n]} \big|\, A_{[n]}X_{[n]}\Pi_{[n]}U\big)\nonumber\\
&= \sum_{i=1}^n\bigg[\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i U \big) + H\big(B_{i}\big|\,T^e_{i} A_i S^e_iU\big)  -H\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, A_{[n]}X_{[n]}\Pi_{[n]} {\widetilde{S}}_iU\big)\nonumber \\
&\qquad \quad- H\big(B_i \big|\, A_{[n]}X_{[n]}\Pi_{[n]}S_i^eU  \big)  \bigg] \label{eqn:useoflemma} \\
&\geq  \sum_{i=1}^n\bigg[\lambda_2H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i U \big)  -H\big({\widetilde{Y}}_i{\widetilde{\Omega}}_i\big|\, A_{[n]}X_{[n]}\Pi_{[n]} {\widetilde{S}}_iU\big)   \bigg]\nonumber \\
&\geq  \sum_{i=1}^n(\lambda_2-1)H\big({\widetilde{Y}}_{i}{\widetilde{\Omega}}_i|{\widetilde{S}}_i U \big),\label{eq:diadoa222}\end{aligned}$$ where in we use the second equation of Lemma \[lemma:amnm\] with $V= A_{[n]}X_{[n]}\Pi_{[n]}U$. Comparing  and  we conclude that $\chi(1, \lambda_2)=\chi_B(\lambda_2) = \phi_B(\lambda_2)+ \psi_B(\lambda_2)\geq 0$. We are done.

Direct proof of Theorem \[thm:MC-ribbon-tensor-data\] {#app:MC-ribbon-tensor-data}
=====================================================

We will use the following lemma in the proof.

\[lem:abc-e-var\] Suppose that $f_{ABC}$ is a function and $p_{ABC}=p_{AB}\cdot p_{C|A}$, i.e., $B$ and $C$ are independent conditioned on $A$. Then we have $${\mathbb{E}}_{AB}{\text{\rm{Var}}}_{C|AB}[f] \geq {\mathbb{E}}_A {\text{\rm{Var}}}_{C|A} {\mathbb{E}}_{B|AC}[f].$$

we compute $$\begin{aligned}
{\mathbb{E}}_{AB}{\text{\rm{Var}}}_{C|AB}[f] & = {\mathbb{E}}_{AB} {\mathbb{E}}_{C|AB}[(f-{\mathbb{E}}_{C|AB}[f])^2]\\
&={\mathbb{E}}_{A}{\mathbb{E}}_{B|A} {\mathbb{E}}_{C|A}[(f-{\mathbb{E}}_{C|A}[f])^2]\\
& \geq {\mathbb{E}}_{A} {\mathbb{E}}_{C|A}[({\mathbb{E}}_{B|A}f-{\mathbb{E}}_{BC|A}[f])^2] \\
& = {\mathbb{E}}_A {\text{\rm{Var}}}_{C|A} {\mathbb{E}}_{B|AC}[f],\end{aligned}$$ where in the third line we use the convexity of $t\mapsto t^2$.

*Proof of* (i): Let $(\lambda_1, \lambda_2)\in \mathfrak S(A_1,B_1)\cap\mathfrak S(A_2, B_2)$. Let $f_{A_1A_2, B_1B_2}$ be an arbitrary function. By the law of total variance we have $$\begin{aligned}
{\text{\rm{Var}}}[f]&= {\text{\rm{Var}}}_{A_1B_1} {\mathbb{E}}_{A_2B_2|A_1B_1}[f] + {\mathbb{E}}_{A_1B_1}{\text{\rm{Var}}}_{A_2B_2|A_1B_1}[f]\nonumber\\
& \geq \lambda_1 {\text{\rm{Var}}}_{A_1} {\mathbb{E}}_{B_1|A_1}{\mathbb{E}}_{A_2B_2|A_1B_1}[f] + \lambda_2 {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{A_1|B_1}{\mathbb{E}}_{A_2B_2|A_1B_1}[f]\nonumber\\
&\qquad +{\mathbb{E}}_{A_1B_1}\bigg(   \lambda_1 {\text{\rm{Var}}}_{A_2|A_1B_1}{\mathbb{E}}_{B_2|A_1A_2B_1}[f]    +\lambda_2 {\text{\rm{Var}}}_{B_2|A_1B_1}{\mathbb{E}}_{A_2|A_1B_1B_2}[f]    \bigg)\label{eqn:azxc1}\\
& \geq \lambda_1\bigg(   {\text{\rm{Var}}}_{A_1}{\mathbb{E}}_{A_2|A_1} {\mathbb{E}}_{B_1B_2|A_1A_2}[f]  + {\mathbb{E}}_{A_1}{\text{\rm{Var}}}_{A_2|A_1} {\mathbb{E}}_{B_1|A_1} {\mathbb{E}}_{B_2|A_1A_2B_1}[f]     \bigg)\nonumber\\
& \qquad+ \lambda_2\bigg(   {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{B_2|B_1} {\mathbb{E}}_{A_1A_2|B_1B_2}[f]  + {\mathbb{E}}_{B_1}{\text{\rm{Var}}}_{B_2|B_1} {\mathbb{E}}_{A_1|B_1} {\mathbb{E}}_{A_2|A_1B_1B_2}[f]     \bigg)\label{eqn:azxc2}\\
& = \lambda_1 {\text{\rm{Var}}}_{A_1A_2}{\mathbb{E}}_{B_1B_2|A_1A_2}[f] + \lambda_2{\text{\rm{Var}}}_{B_1B_2}{\mathbb{E}}_{A_1A_2|B_1B_2}[f].\label{eqn:azxc3}\end{aligned}$$ Here follows from $(\lambda_1, \lambda_2)\in \mathfrak S(A_1,B_1)$ used for function ${\mathbb{E}}_{A_2B_2|A_1B_1}[f]$ on $\mathcal{A}_1\times\mathcal{B}_1$, and from $(\lambda_1, \lambda_2)\in\mathfrak S(A_2, B_2)$ used for function $f$ restricted on $\{(a_1, b_1)\}\times \mathcal{A}_2\times\mathcal{B}_2$ for any $(a_1, b_1)\in \mathcal A_1\times \mathcal B_1$. Note that in the latter case we use the fact that the conditional distribution $p_{A_2B_2|a_1b_1}$ is independent of $(a_1, b_1)$. For  we use Lemma \[lem:abc-e-var\]. Finally,  follows from the law of total variance. We conclude that $\mathfrak S(A_1,B_1)\cap\mathfrak S(A_2, B_2)\subseteq {\mathfrak{S}}(A_1A_2, B_1B_2)$. For the inclusion in the other direction it suffices to consider those $f$ that are only a function of $A_iB_i$, $i=1, 2$.

*Proof of* (ii): Let $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A_1, B_1)$. Let $f_{A_2B_2}$ be an arbitrary function. Since $A_2$ and $B_2$ are independent conditioned on $A_1B_1$ and the MC ribbon of independent random variables is the whole $[0,1]^2$, when we condition on $(A_1, B_1)=(a_1, b_1)$, the MC ribbon of $(A_2, B_2)$ will include the pair $(\lambda_1, \lambda_2)$. Hence, for every $(A_1, B_1)=(a_1, b_1)$ we have $$\begin{aligned}
{\text{\rm{Var}}}_{A_2B_2|a_1b_1}[f]\geq &\lambda_1  {\text{\rm{Var}}}_{A_2|a_1b_1}{\mathbb{E}}_{B_2|A_2, a_1b_1}[f] 
+ \lambda_2 {\text{\rm{Var}}}_{B_2|a_1b_1}{\mathbb{E}}_{A_2|B_2, a_1b_1}[f].\end{aligned}$$ Then by taking average over $A_1, B_1$ we have $$\begin{aligned}
\label{eq:ineq-mc-r-1}
{\mathbb{E}}_{A_1B_1}{\text{\rm{Var}}}_{A_2B_2|A_1B_1}[f]\geq \lambda_1 {\mathbb{E}}_{A_1B_1} {\text{\rm{Var}}}_{A_2|A_1B_1}{\mathbb{E}}_{B_2|A_1B_1A_2}[f] + \lambda_2 {\mathbb{E}}_{A_1B_1} {\text{\rm{Var}}}_{B_2|A_1B_1}{\mathbb{E}}_{A_2|A_1B_1B_2}[f].\end{aligned}$$

Define $\tilde f_{A_1B_1}:={\mathbb{E}}_{A_2B_2|A_1B_1}[f]$. Then since $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A_1, B_1)$ we have $${\text{\rm{Var}}}[\tilde f] \geq \lambda_1 {\text{\rm{Var}}}_{A_1}{\mathbb{E}}_{B_1|A_1}[\tilde f] + \lambda_2 {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{A_1|B_1}[\tilde f],$$ which is equivalent to $$\begin{aligned}
\label{eq:ineq-mc-r-2}
{\text{\rm{Var}}}_{A_1B_1}{\mathbb{E}}_{A_2B_2|A_1B_1}[f] \geq \lambda_1 {\text{\rm{Var}}}_{A_1}{\mathbb{E}}_{B_1A_2B_2|A_1}[ f] + \lambda_2 {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{A_1A_2B_2|B_1}[ f].\end{aligned}$$ Summing  and  and using the law of total variance we obtain $$\begin{aligned}
{\text{\rm{Var}}}[f] & \geq \lambda_1\bigg(  {\mathbb{E}}_{A_1B_1} {\text{\rm{Var}}}_{A_2|A_1B_1}{\mathbb{E}}_{B_2|A_1B_1A_2}[f] +   {\text{\rm{Var}}}_{A_1}{\mathbb{E}}_{B_1A_2B_2|A_1}[ f]\bigg)\\
& \qquad +\lambda_2\bigg(  {\mathbb{E}}_{A_1B_1} {\text{\rm{Var}}}_{B_2|A_1B_1}{\mathbb{E}}_{A_2|A_1B_1B_2}[f]+   {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{A_1A_2B_2|B_1}[ f]     \bigg)\\
& \geq \lambda_1\bigg(  {\mathbb{E}}_{A_1} {\text{\rm{Var}}}_{A_2|A_1} {\mathbb{E}}_{B_1|A_1}{\mathbb{E}}_{B_2|A_1B_1A_2}[f] +   {\text{\rm{Var}}}_{A_1}{\mathbb{E}}_{A_2|A_1}{\mathbb{E}}_{B_1B_2|A_1A_2}[ f]\bigg)\\
& \qquad +\lambda_2\bigg(  {\mathbb{E}}_{B_1} {\text{\rm{Var}}}_{B_2|B_1}{\mathbb{E}}_{A_1|B_1}{\mathbb{E}}_{A_2|A_1B_1B_2}[f]+   {\text{\rm{Var}}}_{B_1}{\mathbb{E}}_{B_2|B_1}{\mathbb{E}}_{A_1A_2|B_1B_2}[ f]     \bigg)\\
& = \lambda_1 {\text{\rm{Var}}}_{A_1A_2} {\mathbb{E}}_{B_1B_2|A_1A_2}[f] + \lambda_2 {\text{\rm{Var}}}_{B_1B_2}{\mathbb{E}}_{A_1A_2|B_1B_2}[f]\\
& \geq \lambda_1{\text{\rm{Var}}}_{A_2}{\mathbb{E}}_{A_1|A_2}{\mathbb{E}}_{B_1B_2|A_1A_2}[f] +\lambda_2 {\text{\rm{Var}}}_{B_2}{\mathbb{E}}_{B_1|B_2}{\mathbb{E}}_{A_1A_2|B_1B_2}[f]\\
& = \lambda_1{\text{\rm{Var}}}_{A_2}{\mathbb{E}}_{B_2|A_2}[f] +\lambda_2 {\text{\rm{Var}}}_{B_2}{\mathbb{E}}_{A_2|B_2}[f],\end{aligned}$$ where in the second line we use Lemma \[lem:abc-e-var\], and in the last line we use the fact that $f$ is a function of $A_2, B_2$ only. Therefore, $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A_2, B_2)$.

Proof of Theorem \[thm:rho-MC-ribbon\] {#app:max-correlation}
======================================

Let us first give a proof of . In definition  of maximal correlation we may drop one of the two constraints ${\mathbb{E}}[f_A]=0$ and ${\mathbb{E}}[g_B]=0$, i.e., for instance we can write $$\begin{aligned}
\label{eq:max-correlatoin-def3}
\rho(A, B)=& \max \quad {\mathbb{E}}[f_Ag_B],
\\&\text{subject to: } {\mathbb{E}}[f_A]=0, \nonumber\\
& \qquad \qquad \quad {\mathbb{E}}[f_A^2]={\mathbb{E}}[g_B^2]=1.\nonumber\end{aligned}$$ This is because if ${\mathbb{E}}[f_A]=0$, for an arbitrary $g_B$ if we let $\tilde g_B:= g_B-{\mathbb{E}}[g_B]$, then ${\mathbb{E}}[\tilde g_B]=0$ and ${\mathbb{E}}[f_Ag_B]= {\mathbb{E}}[f_A\tilde g_B]$ as well as ${\mathbb{E}}[\tilde g_B^2] ={\text{\rm{Var}}}[g_B]\leq {\mathbb{E}}[g_B^2]$; Then we can scale $\tilde g_B$ to make ${\mathbb{E}}[\tilde g_B^2]$ to be one, while increasing ${\mathbb{E}}[f_A\tilde g_B]$.

Let us fix $f_A$ and try to maximize ${\mathbb{E}}[f_Ag_B]$ over all $g_B$ with ${\mathbb{E}}[g_B^2]=1$. By the Cauchy-Schwarz inequality we have $$\begin{aligned}
{\mathbb{E}}[f_Ag_B]& = {\mathbb{E}}_B{\mathbb{E}}_{A|B}[f_Ag_B] \\
&=  {\mathbb{E}}_B[{\mathbb{E}}_{A|B}[f_A]g_B] \\
&\leq {\mathbb{E}}_{B}[({\mathbb{E}}_{A|B}[f_A])^2]^{1/2} \cdot {\mathbb{E}}_B[g_B^2]^{1/2}\\
& ={\mathbb{E}}_{B}[({\mathbb{E}}_{A|B}[f_A])^2]^{1/2}. \end{aligned}$$ Moreover, letting $g_B=\alpha {\mathbb{E}}_{A|B}[f_A]$, for the appropriate choice of constant $\alpha$, the above upper bound is attained. As a result we have $$\begin{aligned}
\rho^2(A, B)  = &\max  \quad{\mathbb{E}}_{B}[{\mathbb{E}}_{A|B}[f_A]^2]\label{eq:def-max-corr-5}\\
& \text{subject to: } {\mathbb{E}}[f_A]=0,\nonumber\\
&  \qquad \qquad \quad  {\mathbb{E}}[f_A^2]=1.\nonumber\end{aligned}$$ We may rewrite the above optimization in terms of variance to remove the constraints. $$\begin{aligned}
\label{eq:def-max-corr-6}
\rho^2(A, B)  = &\max  \frac{{\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f]}{{\text{\rm{Var}}}[f]}, \end{aligned}$$ where maximum is taken over all non-constant functions $f_A$.

We now give the proof of Theorem \[thm:rho-MC-ribbon\].\
*Proof of Theorem \[thm:rho-MC-ribbon\].* Let $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$ where $\lambda_2\neq 0$. By definition we have $${\text{\rm{Var}}}[f] \geq \lambda_1 {\text{\rm{Var}}}_{A}[{\mathbb{E}}_{B|A}[f]] + \lambda_2 {\text{\rm{Var}}}_{B}[{\mathbb{E}}_{A|B}[f]].$$ Assuming that $f=f_A$ is a function of $A$ only, we find that ${\text{\rm{Var}}}[f]={\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f]$. Therefore, $$\frac{1-\lambda_1}{\lambda_2} {\text{\rm{Var}}}[f]\geq {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f].$$ Comparing to  we find that $$(1-\lambda_1)/\lambda_2\geq \rho^2(A, B)=:\rho^2.$$

For the other direction, let $\epsilon>0$ be a constant, and let $n$ be some integer. Define $$\lambda_1^{(n)} = 1-\frac{\rho^2+\epsilon}{n},\qquad\lambda_2^{(n)}=\frac{1}{n}.$$ We claim that for sufficiently large $n$, $(\lambda_1^{(n)}, \lambda_2^{(n)})$ is in ${\mathfrak{S}}(A, B)$. Otherwise there is a function $f_{AB}$ such that $$\begin{aligned}
\label{eq:g-j-ineq}
{\text{\rm{Var}}}[f] <\lambda_1^{(n)} {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] + \lambda_2^{(n)} {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f].\end{aligned}$$ Note that ${\text{\rm{Var}}}[f]\neq 0$ because otherwise the right hand side would have been zero too which is in contradiction with the strict inequality. Thus with no loss of generality we may assume that $${\text{\rm{Var}}}[f]=1.$$ Using the law of total variance $${\text{\rm{Var}}}[f]={\text{\rm{Var}}}_A{\mathbb{E}}_{B|A}[f] + {\mathbb{E}}_A{\text{\rm{Var}}}_{B|A}[f],$$ equation  can equivalently be written as $$\begin{aligned}
\label{eq:g-j-ineq-2}
\frac{1-\lambda_1^{(n)}}{\lambda_2^{(n)}} {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] + \frac{1}{\lambda_2^{(n)}}{\mathbb{E}}_{A}{\text{\rm{Var}}}_{B|A}[f]< {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f].\end{aligned}$$ We have ${\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f]\leq {\text{\rm{Var}}}[f]=1$, and $1/\lambda_2^{(n)}=n$. Therefore, $$\begin{aligned}
\label{eq:x2gj-3}
{\mathbb{E}}_{A}{\text{\rm{Var}}}_{B|A}[f] <1/n.\end{aligned}$$ Let us define $\tilde f={\mathbb{E}}_{B|A}[f]$. Observe that $\tilde f$ is a function of $A$ only, ${\mathbb{E}}[\tilde f]={\mathbb{E}}[f]$, and $ {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] ={\text{\rm{Var}}}[\tilde f]$. Moreover,  is equivalent to $${\mathbb{E}}[(f-\tilde f)^2]<1/n.$$ Thus from  and using the fact that $(1-\lambda_1^{(n)})/\lambda_2^{(n)}=\rho^2+\epsilon$ we have $$\begin{aligned}
(\rho^2+\epsilon){\text{\rm{Var}}}[\tilde f] & < {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[f]\\
& =  {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[(f-\tilde f)+ \tilde f]\\
& = {\mathbb{E}}_{B}\big[   \big(   {\mathbb{E}}_{A|B}[f-\tilde f] + {\mathbb{E}}_{A|B}[\tilde f]  -{\mathbb{E}}[\tilde f]     \big)^2   \big]\\
& = {\mathbb{E}}_{B}\bigg[   \big(   {\mathbb{E}}_{A|B}[f-\tilde f]\big)^2 + \big({\mathbb{E}}_{A|B}[\tilde f]  -{\mathbb{E}}[\tilde f] \big)^2 \\
&\qquad\quad~+   2 \big({\mathbb{E}}_{A|B}[f-\tilde f]\big)\big({\mathbb{E}}_{A|B}[\tilde f]  -{\mathbb{E}}[\tilde f] \big) \bigg]\\
& \leq {\mathbb{E}}[(f-\tilde f)^2] + {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f] \\
&\quad~+ 2 \bigg( {\mathbb{E}}_{B}\big[\big({\mathbb{E}}_{A|B}[f-\tilde f]\big)^2\big]\cdot {\mathbb{E}}_{B}\big[\big({\mathbb{E}}_{A|B}[\tilde f]  -{\mathbb{E}}[\tilde f] \big)^2\big]     \bigg)^{1/2}\\&
\leq \frac{1}{n} +{\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f]  + \\
&\quad~+ 2 \bigg( {\mathbb{E}}_{B}{\mathbb{E}}_{A|B}\big[\big([f-\tilde f]\big)^2\big]\cdot {\mathbb{E}}_{B}\big[\big({\mathbb{E}}_{A|B}[\tilde f]  -{\mathbb{E}}[\tilde f] \big)^2\big]     \bigg)^{1/2}\\
& \leq \frac{1}{n} +{\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f]  + 2\bigg(\frac{1}{n} {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f] \bigg)^{1/2}\\
& \leq {\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f]  + \frac{3}{\sqrt{n}},\end{aligned}$$ where in the last line we use $${\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f]\leq {\text{\rm{Var}}}[\tilde f] = {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] \leq {\text{\rm{Var}}}[f]=1.$$ We also notice that $\tilde f$ is not constant because using  we have $${\text{\rm{Var}}}[\tilde f] =  {\text{\rm{Var}}}_{A}{\mathbb{E}}_{B|A}[f] = {\text{\rm{Var}}}[f] - {\mathbb{E}}_{A}{\text{\rm{Var}}}_{B|A}[f]  >1-\frac{1}{n}.$$ Therefore, using  we have $$\rho^2+\epsilon \leq \frac{{\text{\rm{Var}}}_{B}{\mathbb{E}}_{A|B}[\tilde f]}{{\text{\rm{Var}}}[\tilde f]} + \frac{3}{{\text{\rm{Var}}}[\tilde f]\sqrt{n}}\leq \rho^2 + \frac{3}{(1-1/n)\sqrt{n}},$$ which does not hold for sufficiently large $n$. We conclude that for sufficiently large $n$ the point $(\lambda_1^{(n)}, \lambda_2^{(n)})$ belongs to ${\mathfrak{S}}(A, B)$. As a result, we have $$\inf \frac{1-\lambda_1}{\lambda_2}\leq \rho^2+\epsilon,$$ for every $\epsilon>0$. Then $$\inf \frac{1-\lambda_1}{\lambda_2}\leq \rho^2.$$ We are done. $\Box$

Proof of Theorem \[thm:inf-rho-mc-ribbon-NS\] {#app:inf-rho-mc-ribbon-NS}
=============================================

As shown in the proof of Theorem \[thm:rho-MC-ribbon\] for every $x, y$ and $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B|X=x, Y=y)$ we have $(1-\lambda_1)/\lambda_2\geq \rho^2(A, B|X=x, Y=y).$ Therefore, for $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B|X,Y)$ we have $$\frac{1-\lambda_1}{\lambda_2}\geq \rho^2(A, B|X=x, Y=y),$$ for every $x, y$. Taking the maximum of the right hand side over all $x, y$ we obtain $$\inf \frac{1-\lambda_1}{\lambda_2} \geq \rho^2(A, B|XY),$$ where the infimum is taken over $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B|X, Y)$ with $\lambda_2\neq 0$.

For the other direction, recall that in the proof of Theorem \[thm:rho-MC-ribbon\] we show that $(\lambda_1^{(n)}, \lambda_2^{(n)})$ defined by $$\lambda_1^{(n)}=1-\frac{\rho^2(A, B|X=x, Y=y) +\epsilon}{n} , \qquad \lambda_2^{(n)}=\frac{1}{n},$$ for a given $\epsilon>0$, belongs to ${\mathfrak{S}}(A, B|X=x, Y=y)$ for sufficiently large $n$. Since $\rho^2(A, B|X, Y)\geq \rho^2(A, B|X=x, Y=y)$ we find that $(\tilde \lambda_1^{(n)}, \tilde \lambda_2^{(n)})$ defined by $$\tilde \lambda_1^{(n)}=1-\frac{\rho^2(A, B|X, Y) +\epsilon}{n} , \qquad \tilde \lambda_2^{(n)}=\frac{1}{n},$$ belongs to ${\mathfrak{S}}(A, B|X=x, Y=y)$ for sufficiently large $n$ too. As a result, $(\tilde \lambda_1^{(n)}, \tilde \lambda_2^{(n)})$ belongs to ${\mathfrak{S}}(A, B|X, Y)$ for sufficiently large $n$. We conclude that $$\inf \frac{1-\lambda_1}{\lambda_2} \leq \frac{1-\tilde \lambda_1^{(n)}}{\tilde \lambda_2^{(n)}}=\rho^2(A, B|XY)+\epsilon,$$ for every $\epsilon>0$. We are done.

Proof of Theorem \[thm:MC-HC-ribbon\] {#app:MC-HC-ribbon-proof}
=====================================

Given (ii) the proof of (iii) is immediate; We only need to put $K=0$.

Let us denote the set of pairs $(\lambda_1, \lambda_2)$ described in parts (i) and (ii) of the theorem by ${\mathfrak{S}}_{\text{\rm i}}(A, B)$ and ${\mathfrak{S}}_{\text{\rm ii}}(A, B)$ respectively. We need to show ${\mathfrak{S}}(A,B) = {\mathfrak{S}}_{\text{\rm i}}(A, B)={\mathfrak{S}}_{\text{\rm ii}}(A, B)$.

For a bipartite distribution $p_{AB}$ we let ${\text{supp}}(p_{AB})\subseteq \mathcal A\times \mathcal B$ be the set of pairs $(a, b)$ such that $p(ab)\neq 0$. We also let $\mathcal W(p_{AB})$ be the set of distributions $q_{AB}$ with ${\text{supp}}(q_{AB})={\text{supp}}(p_{AB})$. Note that perturbations of the form  sweep the neighborhood of $p_{AB}$ in $\mathcal W(p_{AB})$. In the following we also use the notation $q_{AB|U}\in \mathcal W(p_{AB})$ for some distribution $q_{ABU}$ by which we mean that for every $u\in \mathcal U$ the conditional distribution $q_{AB|U=u}$ is in $\mathcal W(p_{AB})$.

Observe that $\Upsilon: \mathcal W(p_{AB})\rightarrow \mathbb R$ is a smooth function. So for $q_{AB}\in \mathcal W(p_{AB})$ letting $v_{AB}=q_{AB}-p_{AB}$ we may write $$\Upsilon(q_{AB}) = \Upsilon(p_{AB}) +  D^{(1)}_v(p_{AB}) + \frac{1}{2}D^{(2)}_v(p_{AB})  + O(\|v\|_1^3),$$ where $D^{(1)}_v(p_{AB})$ and $D^{(2)}_v(p_{AB})$ are respectively the first and second derivatives of $\Upsilon$ at $p_{AB}$ in the direction of $v$. Observe that $D^{(1)}_v(p_{AB})$ and $D^{(2)}_v(p_{AB})$ are not infinity[^6] since $q_{AB}\in \mathcal W(p_{AB})$.

In the following we will show that ${\mathfrak{S}}_{\text{\rm i}}(A, B)\subseteq {\mathfrak{S}}(A, B)\subseteq {\mathfrak{S}}_{\text{\rm ii}}(A, B)\subseteq {\mathfrak{S}}_{\text{\rm i}}(A, B)$ which finishes the proof.

*Proof of ${\mathfrak{S}}_{\text{\rm ii}}(A, B)\subseteq {\mathfrak{S}}_{\text{\rm i}}(A, B)$*: From the definitions it is clear that ${\mathfrak{S}}_{\text{\rm ii}}(A, B)$ is more restrictive than ${\mathfrak{S}}_{\text{\rm i}}(A, B)$. We only need to note that for $f_{AB}$ with ${\mathbb{E}}[f]=0$ and ${\text{\rm{Var}}}[f]={\mathbb{E}}[f^2]=1$, and for every $U_\epsilon=u$ we have $$\|p_{AB|u}  - p_{AB} \|_1^3= \epsilon^3\|p_{AB}\cdot f_{AB}\|_1^3 = O(\epsilon^3),$$ where in the last step we use $f(ab)=O(1)$ for every $a, b$, which is implied by ${\mathbb{E}}[f^2]=1$.

*Proof of ${\mathfrak{S}}(A, B)\subseteq {\mathfrak{S}}_{\text{\rm ii}}(A, B)$*: Observe that in the definition of ${\mathfrak{S}}_{\text{\rm ii}}(A, B)$, without loss of generality, we can restrict ourselves to $p_{AB|U}\in \mathcal W(p_{AB})$. In other words, if we have the inequality for $p_{AB|U}\in \mathcal W(p_{AB})$, we will have it for all $p_{AB|U}$ by using a continuity argument and approaching $p_{AB|U}$ with elements of $\mathcal W(p_{AB})$.

Take some $p_{U|AB}$ with $p_{AB|U}\in \mathcal W(p_{AB})$. For every $U=u$, let $$v_{AB|U=u}=p_{AB|U=u}-p_{AB}.$$ Further, let $v_{AB|U}$ be the random vector that is a function of $U$ and takes the vector $v_{AB|U=u}$ when $U=u$. we have $$\begin{aligned}
{\mathbb{E}}_U[\Upsilon(p_{AB|U})] & = \Upsilon(p_{AB}) + {\mathbb{E}}_U\big[D^{(1)}_{v_{AB|U}}(p_{AB})\big] + \frac{1}{2}{\mathbb{E}}_U\big[D^{(2)}_{v_{AB|U}}(p_{AB})\big] + O({\mathbb{E}}_U[\|v_{AB|U}\|_1^3])\\
& = \Upsilon(p_{AB}) + \frac{1}{2}{\mathbb{E}}_U\big[D^{(2)}_{v_{AB|U}}(p_{AB})\big] + O({\mathbb{E}}_U[\|v_{AB|U}\|_1^3]),\end{aligned}$$ where in the second line we use ${\mathbb{E}}_U[v_{AB|U}] = {\mathbb{E}}_U[p_{AB|U}]- p_{AB}=0$, and that $D^{(1)}_{v}(p_{AB})$ is linear in $v$. Thus we have $$\begin{aligned}
I(U; AB) -\lambda_1I(U; A) - \lambda_2 I(U; B) & = {\mathbb{E}}_U[\Upsilon(p_{AB|U})] - \Upsilon(p_{AB})\nonumber\\
&= \frac{1}{2}{\mathbb{E}}_U\big[D^{(2)}_{v_{AB|U}}(p_{AB})\big] + O({\mathbb{E}}_U[\|v_{AB|U}\|_1^3]).\label{eq:mutual-inf-hessian}\end{aligned}$$

Now suppose that $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$. This implies that $D^{(2)}_v(p_{AB})\geq 0$. Then using , for every $p_{U|AB}$ we have $$I(U; AB) -\lambda_1I(U; A) - \lambda_2 I(U; B) + O({\mathbb{E}}_U[\|p_{AB|U}-p_{AB}\|_1^3])\geq 0.$$

*Proof of ${\mathfrak{S}}_{\text{\rm i}}(A, B)\subseteq {\mathfrak{S}}(A, B)$*: Now suppose that $(\lambda_1, \lambda_2)\in {\mathfrak{S}}_{\text{\rm i}}(A, B)$. We may write  for the particular distribution $p_{ABU_\epsilon}$ defined in the theorem. For this distribution we have $$v_{AB|U_\epsilon=u}=p_{AB|U_\epsilon=u}-p_{AB} = \epsilon u p_{AB} \cdot f_{AB}.$$ Therefore, $$\frac{\epsilon^2}{2}D^{(2)}_{p_{AB}\cdot f_{AB}}(p_{AB}) + O(\epsilon^3\|f\|_1^3)\geq 0.$$ Since this inequality should hold in a neighborhood of $\epsilon=0$, we must have $D^{(2)}_{p_{AB}\cdot f_{AB}}(p_{AB})\geq 0$. As mentioned in Section \[subsec:MC-HC-ribbons\] we have $$\begin{aligned}
\label{eq:hessian-1}
D^{(2)}_{p_{AB}\cdot f_{AB}}(p_{AB}) = {\mathbb{E}}[f^2] -\lambda_1 {\mathbb{E}}_A[({\mathbb{E}}_{B|A}[f])^2)] -\lambda_2 {\mathbb{E}}_B[({\mathbb{E}}_{A|B}[f])^2\geq 0.\end{aligned}$$ Thus using Lemma \[lem:def-MC-ribbon-zero\] we conclude that $(\lambda_1, \lambda_2)\in {\mathfrak{S}}(A, B)$. Therefore, ${\mathfrak{S}}_{\text{\rm i}}(A, B)\subseteq {\mathfrak{S}}(A, B)$.

Proof of Lemma \[lem:ribbon-rho-CHSH\] {#app:rho-chsh}
======================================

We need to show that if $\eta\geq 1/\sqrt 2$, $$\begin{aligned}
\label{eq:range-alpha-beta}
1-|\alpha_x - \beta_y| \geq \zeta_{xy} \geq |\alpha_x+ \beta_y|-1,\qquad \qquad \forall x, y,\end{aligned}$$ and $$\begin{aligned}
\label{eq:sum-zeta-eta}
\sum_{x, y} (-1)^{xy}\zeta_{xy}\geq 4\eta,\end{aligned}$$ then $$\begin{aligned}
\max_{x, y} \frac{|\zeta_{xy}-\alpha_x\beta_y|}{\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}}\geq \eta.\label{eq:maxrho-1}\end{aligned}$$

Observe that if $|\alpha_x|=1$, for some $x$, then from  we have $\zeta_{xy}=\alpha_x\beta_y$ for all $y$. This holds because $|\alpha_x|=1$ implies that $1-|\alpha_x - \beta_y|=|\alpha_x+ \beta_y|-1=\alpha_x\beta_y$ in this case. Similarly if $|\beta_y|=1$ for some $y$, then $\zeta_{xy}=\alpha_x\beta_y$ for all $x$. As a result, if for all pairs $(x, y)$ we have either $|\alpha_x|=1$ or $|\beta_y|=1$, then $\zeta_{xy}=\alpha_x\beta_y$ for all $x,y$. In this case by  we have $$2{\sqrt 2}\leq 4\eta\leq \sum_{x, y}(-1)^{xy}\alpha_x \beta_y,$$ which is a contradiction since by Bell’s inequality we know that left hand side is at most $2$ (note that $|\alpha_x|, |\beta_y|\leq 1$). Thus in the following we assume that for at least one pair of $(x, y)$ we have $|\alpha_x|\neq 1\neq |\beta_y|$.

To get a contradiction suppose that $$\frac{|\zeta_{xy}-\alpha_x\beta_y|}{\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}}< \eta, \qquad \quad \forall x,y.$$ Then $(-1)^{xy}(\zeta_{xy}-\alpha_x\beta_y) \leq \eta\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}$ for all $x, y$; further this inequality is strict for the pairs $(x, y)$ with $|\alpha_x|\neq 1\neq |\beta_y|$. Therefore by the above discussion we have $$\sum_{x, y} (-1)^{xy}\zeta_{xy}< \sum_{x, y} \bigg[(-1)^{xy}\alpha_x\beta_y + \eta\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}\bigg].$$ Comparing with , we conclude that $$\begin{aligned}
\label{eq:4eta-inner1}
4\eta< \sum_{x, y} \bigg[(-1)^{xy}\alpha_x\beta_y + \eta\sqrt{(1-\alpha_x^2)(1-\beta_y^2)}\bigg].\end{aligned}$$ Let us define $$v_{x} = \begin{bmatrix}
\alpha_x\\\sqrt{1-\alpha_x^2}~
\end{bmatrix},\qquad \qquad w_{y} = \begin{bmatrix}
\beta_y\\ \sqrt{1-\beta_y^2}~
\end{bmatrix}, \qquad \qquad M_{xy}=\begin{bmatrix}
(-1)^{xy} & 0\\ 0 & \eta
\end{bmatrix}.$$ Also define $$\tilde v=\begin{bmatrix}
v_0\\ v_1
\end{bmatrix}, \qquad \qquad \tilde w=\begin{bmatrix}
w_0\\ w_1
\end{bmatrix},\qquad \qquad  \widetilde M=\begin{bmatrix}
M_{00}& M_{01}\\
M_{10} & M_{11}
\end{bmatrix}.$$ Then is equivalent to $$4\eta < \tilde v^t \widetilde M\tilde w.$$ Using the fact that $\|\tilde v\| = \|\tilde w\|=\sqrt 2$, this means that $\|\widetilde M\|>2\eta$. We however have $$\|\widetilde M\|=\max\{\sqrt 2, 2\eta\}.$$ Then we should have $\sqrt 2>2\eta$ which is in contradiction with $\eta\geq 1/\sqrt 2$. We are done.

[10]{}

S. Popescu and D. Rohrlich, Foundations of Physics 24 (3): 379385 (1994).

W. van Dam, Implausible Consequences of Superstrong Nonlocality, arXiv:quant-ph/0501159 (2005).

M. Pawlowski, T. Paterek, D. Kaszlikowski, V. Scarani, A. Winter, and M. Zukowski, Information Causality as a Physical Principle, Nature [**461**]{}, 1101 (2009).

T. Fritz, A. B. Sainz, R. Augusiak, J. B. Brask, R. Chaves, A. Leverrier and A. Acín, Local orthogonality as a multipartite principle for quantum correlations, Nat. Commun. [**4**]{}, 2263 (2013).

G. Brassard, H. Buhrman, N. Linden, A. A. Methot, A. Tapp and F. Unger, Limit on Nonlocality in Any World in Which Communication Complexity Is Not Trivial, Phys. Rev. Lett. [**96**]{}, 250401, (2006).

N. Linden, S. Popescu, A. J. Short, and A. Winter, Quantum Nonlocality and Beyond: Limits from Nonlocal Computation, Phys. Rev. Lett. [**99**]{}, 180502 (2007).

M. Navascués, S. Pironio, and A. Acín, Bounding the set of quantum correlations, Phys. Rev. Lett. [**98**]{}, 010401 (2007).

J. Allcock, N. Brunner, N. Linden, S. Popescu, P. Skrzypczyk and T. Vértesi, Closed sets of nonlocal correlations, Phys. Rev. A [**80**]{}, 062107 (2009).

M. Navascués and H. Wunderlich, A glance beyond the quantum model, Proc. R. Soc. A 466, 881-890 (2010).

L. Masanes, A. Acín, and N. Gisin, General properties of nonsignaling theories, *Phys. Rev. Lett. A* [**73**]{}, 012112 (2006).

P. Skrzypczyk, N. Brunner and S. Popescu, Emergence of quantum correlations from nonlocality swapping, *Phys. Rev. Lett.* [**102**]{} (11), 110402 (2009).

D. Cavalcanti, A. Salles and V. Scarani, Macroscopically local correlations can violate information causality, *Nature Communications* [**1**]{}, 136 (2010).

O. Oreshkov, F. Costa and Č. Brukner, Quantum correlations with no causal order, *Nature Communications* [**3**]{}, 1092 (2012).

A. J. Short, S. Popescu and N. Gisin, Entanglement swapping for generalized nonlocal correlations, *Phys. Rev. A* [**73**]{} (1), 012101 (2006).

J. Barrett, Information processing in generalized probabilistic theories.*Phys. Rev. A* [**75**]{} (3), 032304 (2007).

A. B. Sainz, T. Fritz, R. Augusiak, J. Bohr Brask, R. Chaves, A. Leverrier, and A. Acín, Exploring the local orthogonality principle, *Phys. Rev. A* [**89**]{}, 032117 (2014).

B. Lang, T. Vértesi and M. Navascués, Closed sets of correlations: answers from the zoo, arXiv:1402.2850 (2014).

A. J. Short, No Deterministic Purification for Two Copies of a Noisy Entangled State, Phys. Rev. Lett. [**102**]{}, 180502 (2009).

M. Forster, Bounds for nonlocality distillation protocols, Phys. Rev. A [**83**]{}, 062114 (2011).

D. D. Dukaric and S. Wolf, A Limit on Non-Locality Distillation, arXiv:0808.3317 (2008).

H. O. Hirschfeld, A connection between correlation and contingency, Proc. Cambridge Philosophical Soc. **31**, 520-524 (1935).

H. Gebelein, Das statistische problem der Korrelation als variations-und Eigenwertproblem und sein Zusammenhang mit der Ausgleichungsrechnung, Z. für angewandte Math. und Mech. **21**, 364–379 (1941).

A. Rényi, New version of the probabilistic generalization of the large sieve, Acta Math. Hung. **10**, 217-226 (1959).

A. Rényi, On measures of dependence, Acta Math. Hung. **10**, 441-451 (1959).

H. S. Witsenhausen, On sequences of pairs of dependent random variables, SIAM Journal on Applied Mathematics, 28: 100-113 (1975).

G. Kumar, On Sequences of Pairs of Dependent Random Variables: A simpler proof of the main result using SVD, (2010) available at <http://web.stanford.edu/~gowthamr/research/Witsenhausen_simpleproof.pdf>.

W. Kang and S. Ulukus, A New Data Processing Inequality and Its Applications in Distributed Source and Channel Coding, IEEE Transactions on Information Theory **57**, 56–69 (2011)

N. Brunner and P. Skrzypczyk, Nonlocality Distillation and Postquantum Theories with Trivial Communication Complexity, Phys. Rev. Lett. [**102**]{}, 160403 (2009).

R. Ahlswede and P. Gács, Spreading of Sets in Product Spaces and Hypercontraction of the Markov Operator, The Annals of Probability 4, 925-939 (1976).

S. Kamath and V. Anantharam, Non-interactive Simulation of Joint Distributions: The Hirschfeld-Gebelein-Rényi Maximal Correlation and the Hypercontractivity Ribbon, Proceedings of the 50th Annual Allerton Conference on Communications, Control and Computing (2012).

V. Anantharam, A. Gohari, S. Kamath, and C. Nair, On Maximal Correlation, Hypercontractivity, and the Data Processing Inequality studied by Erkip and Cover, arXiv:1304.6133 (2013).

P. Delgosha and S. Beigi, Impossibility of Local State Transformation via Hypercontractivity, Commun. Math. Phys (2014).

C. Nair, Equivalent formulations of Hypercontractivity using Information Measures, IZS workshop, 2014, available at <http://chandra.ie.cuhk.edu.hk/pub/papers/manuscripts/IZS14.pdf>

A. El Gamal and Y.-H. Kim, Network information theory, Cambridge University Press, 2011.

C. Nair, Upper concave envelopes and auxiliary random variables, International Journal of Advances in Engineering Sciences and Applied Mathematics (Springer), volume 5, number 1, pages 12-20, March 2013.

A. Gohari and V. Anantharam, Evaluation of Marton’s inner bound for the general broadcast channel, IEEE Transactions on Information Theory, vol. 58, no. 2, 608-619 (2012).

S. Beigi, A New Quantum Data Processing Inequality, J. Math. Phys. 54, 082202 (2013).

S. Beigi and A. Gohari, in preparation.

G. Kumar, Binary Renyi Correlation: A simpler proof of Witsenhausen’s result and a tighter upper bound, (2010) available at <http://web.stanford.edu/~gowthamr/research/binary_renyi_correlation.pdf>.

R.M. Gray and A.D. Wyner, Source coding for a simple network, [The Bell System Technical Journal]{}, vol. 53, no. 9, 1681–1721 (November 1974).

S. Beigi and A. Gohari, Information Causality is a Special Point in the Dual of the Gray-Wyner Region, arXiv:1111.3151v2 (2011).

[^1]: We gave a different definition for the hypercontractivity ribbon in the introduction. Later we will comment on the equivalence of these two definitions.

[^2]: Here to exactly get this expression, we should take natural logarithm instead of logarithm in base 2 in the definition of the entropy function.

[^3]: Since all norms on a finite dimensional vector space are equivalent, in the statement of the theorem we could replace norm-$1$ with any other norm.

[^4]: This can be shown using the duality of linear programs.

[^5]: Note that to write a general no-signaling box as a linear combination of product boxes we do need negative coefficients. This claim can be verified for example by computing the dimensions of linear span of product boxes and no-signaling boxes individually.

[^6]: The derivative of entropy function is infinity only when we change the distribution by making a non-zero probability equal to zero, or vice versa.