# Sufficient Statistics of $X$ from $Y$

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.
• 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. Jun 8 '14 at 0:43
• @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. Jun 8 '14 at 5:54