Why not include private randomness in internal communication information definition?

Question

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))$

Answer 1

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.