1
$\begingroup$

Generally data processing inequality says that the entropy cannot increase on applying a function f, or to be precise $H(f(X))\leq H(X)$ (also it is reversed if we know the function is k-to-1 so there is an extra log(k) factor. or the mutual information DPI is $I(X:f(Y))\leq I(X,Y)$. I was wondering, what happens if we have a randomized/probabilistic function $f$. Say for example, f arbitrarily flips every bit with some probability $p$, does it still hold? can we claim anything more.

Also references to papers/notes to read more on using probabilistic techniques are welcome.

$\endgroup$

1 Answer 1

0
$\begingroup$

Have you tried writing a randomized function $f_R$ as a distribution $F$ over deterministic functions, and looked at $H(f(X))$ as $\mathbb{E}_{f\sim F}[H(f(X))]$ to see where this led? See e.g. Lemma 2 of these lecture notes for a related question (with total variation distance instead of entropy/mutual information).

-- Edit: as a small comment: in general, you will most likely need to assume that $f$ is independent of $X,Y$ (i.e., the randomized function has its "own coins", and cannot depend on the random variables it applies to).

$\endgroup$
1
  • $\begingroup$ Ur absolutely right, about the randomness in $f_R$ being independent than the randomness in X,Y itself. I was actually hoping if we could simply use the bruteforce approach actually? $H(f(X))=\sum_k Pr[f(X)=k]log(Pr[f(X)=k])$, and maybe then think of evaluating Pr[f(X)=k]? I will anywaz look at the reference, seems interesting! $\endgroup$ Feb 19, 2015 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .