I am reading the paper New Monotone and Lower Bounds in Unconditional Two Party Computation by Wolf and Wullschleger. In Definition 2 on the third page, they define $f(x):=P_{Y|X}(\cdot|x)$ and they claim that $f(X)$ is the sufficient statistics of $X$ from $Y$. This means that $I(Y; X)=I(Y; f(X))$ where $I(\cdot; \cdot)$ is the mutual information.

I don't understand the definition of $f$. What does $f(X)=c$ mean?

The above implies that we have the two Markov chains $Y\to X\to f(X)$ and $Y\to f(X)\to X$. I don't understand the second Markov chain. Is there any intuition behind this? (The proof is given in the paper but I am looking for some intuition.)

Is the entropy of $f(X)$ equal to $H(Y|X)$?


The function $f$ maps $x$ to the conditional distribution of $Y$ given that $X = x$. This is a "deterministic" function. The expression $f(X)$ is a random variable depending on $X$. When $X = x$, the value of this random variable is $f(X) = f(x)$. In words, the random variable $f(X)$ gives the distribution of $Y$ conditional on the value of $X$.

Given $f(X)$, the variables $X,Y$ become independent. Suppose that $f(X) = \phi$. For each $x$ such that $f(x) = \phi$, the conditional distribution of $Y$ given that $X = x$ is $\phi$, that is, $\Pr[Y = y | X = x] = \phi(y)$. This doesn't depend on the value of $x$ as long as $f(x) = \phi$. In particular, the value of $X$ tells us nothing on $Y$, so the conditional mutual information is zero.

  • $\begingroup$ Thanks. Can you please elaborate why the restriction "only for $x$ such that $f(x)=\phi$" does not break the Markov chain? I mean, Markov chain $X\to U\to Y$ means FOR ANY $u$ we have $\Pr[Y=y|X=x, U=u]=\Pr[Y=y|U=u]$, not just for some of them. $\endgroup$
    – SAmath
    Jun 8 '14 at 0:43
  • $\begingroup$ @SAmath When $U = f(X)$, the left-hand side isn't always defined, so this equation doesn't make sense. I don't know what the proper definition is, but I'm sure that with the correct definition, everything will work out. $\endgroup$ Jun 8 '14 at 5:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.