<p>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$.</p>

<p>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. </p>

CC BY-SA 3.0
2014-06-08T00:43:11.343Z
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.
SAmath
CC BY-SA 3.0
2014-06-08T05:54:09.850Z
@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.
Yuval Filmus
CC BY-SA 3.0
2014-06-06T06:50:20.480Z
2014-06-06T06:50:20.480Z
Yuval Filmus
<p>I am reading the paper <em><a href="http://jurg.wulli.com/crypto/WolWul05c.pdf" rel="nofollow">New Monotone and Lower Bounds in Unconditional Two Party Computation</a></em> 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.</p>

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

<p>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.)</p>

<p>Is the entropy of $f(X)$ equal to $H(Y|X)$?</p>

<cr.crypto-security><pr.probability><it.information-theory><shannon-entropy>
Sufficient Statistics of $X$ from $Y$
SAmath
# Sufficient Statistics of $X$ from $Y$

(Asked by: username_0 on 2014-06-05)

I am reading the paper *[New Monotone and Lower Bounds in Unconditional Two Party Computation](http://jurg.wulli.com/crypto/WolWul05c.pdf)* 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)$?

**Tags:** cr.crypto-security, pr.probability, it.information-theory, shannon-entropy


---

## 1 answers

### Answer by username_1 on 2014-06-06. Score: 1 | Accepted answer

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.

> **Comments:**
> **username_0**: 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.  
> **username_1**: @username_0 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.  

---

