<p>I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to have a shorter notation.</p>

<p>To see the equivalence, observe that
<span class="math-container">\begin{eqnarray}
I(X; \Pi | Y, PR(Y) ) &amp;=&amp; I(X; \Pi, PR(Y) | Y ) - I(X; PR(Y) | Y ) \\
&amp; = &amp; I(X; \Pi, PR(Y) | Y ) \\
&amp; = &amp; I(X; \Pi | Y ) + I(X; PR(Y) | Y, \Pi ) \\
&amp; = &amp; I(X; \Pi | Y )
\end{eqnarray}</span>
Here, the first and third equalities follow from the chain rule, the second equality follows since <span class="math-container">$X$</span> and <span class="math-container">$PR(Y)$</span> are independent even conditioned on <span class="math-container">$Y$</span>, and the fourth equality follows <span class="math-container">$X$</span> and <span class="math-container">$PR(Y)$</span> are independent even conditioned on <span class="math-container">$Y$</span> and <span class="math-container">$\Pi$</span>. </p>

<p>The last independence takes a bit of effort to verify, but it basically follows from the rectangle property of protocols (and one also needs to note that conditioning on <span class="math-container">$Y$</span> severs the possible dependence of <span class="math-container">$X$</span> and <span class="math-container">$PR(Y)$</span> given <span class="math-container">$\Pi$</span>). A bit more specifically, observe that conditioned <span class="math-container">$\Pi$</span> and <span class="math-container">$Y$</span>, the set of values of <span class="math-container">$X$</span> and <span class="math-container">$PR(Y)$</span> that are consistent with <span class="math-container">$\Pi$</span> and <span class="math-container">$Y$</span> form a rectangle. Since <span class="math-container">$X$</span> and <span class="math-container">$PR(Y)$</span> started as independent variables, conditioning them on being in this rectangle preserves their independence.</p>

CC BY-SA 4.0
2019-06-11T11:40:01.497Z
2019-06-11T11:40:01.497Z
Or Meir
<p>I am using <a href="https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf" rel="nofollow noreferrer">https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf</a> as a reference.</p>

<p>This isn't exactly a research question but I can't find a good place to ask it.</p>

<p>Suppose we have <span class="math-container">$f:X\times Y \to Z$</span>, <span class="math-container">$u$</span> a distribution on <span class="math-container">$X\times Y$</span>, and <span class="math-container">$\delta &gt;0$</span>. </p>

<p>Now consider communication protocols that allow both public and private randomness- this means a distribution (the public randomness) on a set of computation trees, each node of which has a player's name, and two edges outgoing marked by <span class="math-container">$0,1$</span>, and the node gets as info the private randomness of that player; the leafs have no player's name, and instead just contain the output of the protocol (an element of <span class="math-container">$Z$</span>).</p>

<p>If <span class="math-container">$\prod$</span> is a protocol computing <span class="math-container">$f$</span> with at most <span class="math-container">$\delta$</span> error (the probabiliy space is over both inputs, public and private randomness), we let abuse of notation use <span class="math-container">$\prod$</span> as a random variable of a string of what they players said in addition to the public randomness (to clarify, it's a pair (<span class="math-container">$R,T$</span>) where <span class="math-container">$R$</span> is the public random and <span class="math-container">$T$</span> the transcript). We can define its external information complexity to be <span class="math-container">$I_{u,\delta}(X,Y;\prod)$</span>.</p>

<p>We also define the internal information complexity to be </p>

<p><span class="math-container">$I(X;\prod|Y)+I(Y;\prod|X)$</span>, intuitively the first summand should be what player <span class="math-container">$B$</span> (who got <span class="math-container">$Y$</span>) learns about <span class="math-container">$X$</span>, and similiarly for the second.</p>

<p>What confuses me is shouldn't we also condition on the private randomness here?</p>

<p>I.e <span class="math-container">$I(X;\prod|Y,PR(Y))+I(Y;\prod|X,PR(X))$</span></p>

CC BY-SA 4.0
2019-06-08T17:05:13.560Z
I think a short answer is because we want $IC$ to be a lower bound on communication complexity, and it's clearly true for the given definition (see proof of Prop 2). It doesn't seem as obvious to me for your definition; let's see if an expert can explain if it works.
usul
CC BY-SA 4.0
2019-06-08T18:15:06.280Z
@usul Thanks, that is a true point, though I would be happy for an intuitive explanation that we're measuring something natural (Atm it seems kinda weird?). More of these definitions seem weird- clearly we if you have such a protocol using public randomness, then by averaging there is a deterministic with information at most that of yours (both in the external and internal settings), so the only reason to allow public randomness seems to phrase things more easily?
user135743
<it.information-theory><communication-complexity>
Why not include private randomness in internal communication information definition?
user135743
# Why not include private randomness in internal communication information definition?

(Asked by: username_0 on 2019-06-08)

I am using <https://www.cs.toronto.edu/~toni/Courses/CommComplexity2014/Lectures/lecture12.pdf> as a reference.

This isn't exactly a research question but I can't find a good place to ask it.

Suppose we have $f:X\times Y \to Z$, $u$ a distribution on $X\times Y$, and $\delta >0$.

Now consider communication protocols that allow both public and private randomness- this means a distribution (the public randomness) on a set of computation trees, each node of which has a player's name, and two edges outgoing marked by $0,1$, and the node gets as info the private randomness of that player; the leafs have no player's name, and instead just contain the output of the protocol (an element of $Z$).

If $\prod$ is a protocol computing $f$ with at most $\delta$ error (the probabiliy space is over both inputs, public and private randomness), we let abuse of notation use $\prod$ as a random variable of a string of what they players said in addition to the public randomness (to clarify, it's a pair ($R,T$) where $R$ is the public random and $T$ the transcript). We can define its external information complexity to be $I\_{u,\delta}(X,Y;\prod)$.

We also define the internal information complexity to be

$I(X;\prod|Y)+I(Y;\prod|X)$, intuitively the first summand should be what player $B$ (who got $Y$) learns about $X$, and similiarly for the second.

What confuses me is shouldn't we also condition on the private randomness here?

I.e $I(X;\prod|Y,PR(Y))+I(Y;\prod|X,PR(X))$

**Tags:** it.information-theory, communication-complexity

> **Comments:**
> **username_1**: I think a short answer is because we want $IC$ to be a lower bound on communication complexity, and it's clearly true for the given definition (see proof of Prop 2). It doesn't seem as obvious to me for your definition; let's see if an expert can explain if it works.  
> **username_0**: @username_1 Thanks, that is a true point, though I would be happy for an intuitive explanation that we're measuring something natural (Atm it seems kinda weird?). More of these definitions seem weird- clearly we if you have such a protocol using public randomness, then by averaging there is a deterministic with information at most that of yours (both in the external and internal settings), so the only reason to allow public randomness seems to phrase things more easily?  

---

## 1 answers

### Answer by username_2 on 2019-06-11. Score: 4 | Accepted answer

I agree that the definition you suggest is more natural. However, this definition is equivalent to the definition without the private randomness, so I assume they omit the private randomness just to have a shorter notation.

To see the equivalence, observe that
\begin{eqnarray}
I(X; \Pi | Y, PR(Y) ) &=& I(X; \Pi, PR(Y) | Y ) - I(X; PR(Y) | Y ) \\
& = & I(X; \Pi, PR(Y) | Y ) \\
& = & I(X; \Pi | Y ) + I(X; PR(Y) | Y, \Pi ) \\
& = & I(X; \Pi | Y )
\end{eqnarray}
Here, the first and third equalities follow from the chain rule, the second equality follows since $X$ and $PR(Y)$ are independent even conditioned on $Y$, and the fourth equality follows $X$ and $PR(Y)$ are independent even conditioned on $Y$ and $\Pi$.

The last independence takes a bit of effort to verify, but it basically follows from the rectangle property of protocols (and one also needs to note that conditioning on $Y$ severs the possible dependence of $X$ and $PR(Y)$ given $\Pi$). A bit more specifically, observe that conditioned $\Pi$ and $Y$, the set of values of $X$ and $PR(Y)$ that are consistent with $\Pi$ and $Y$ form a rectangle. Since $X$ and $PR(Y)$ started as independent variables, conditioning them on being in this rectangle preserves their independence.


---

