Dictator functions maximize mutual information

Abstract: Let

(m a t h b f X, m a t h b f Y)

denote

n

independent, identically distributed copies of two arbitrarily correlated Rademacher random variables

(X, Y)

. We prove that the inequality

I (f (m a t h b f X); g (m a t h b f Y)) l e I (X; Y)

holds for any two Boolean functions:

f, g c o l o n {- 1, 1}^{n} o - 1, 1

(

I (c d o t; c d o t)

denotes mutual information). We further show that equality in general is achieved only by the dictator functions

f (m a t h b f x) = p m g (m a t h b f x) = p m x_{i}

,

i i n 1, 2, d o t s, n

.

Recommendations

Cites work

Cited in

(3)

This page was built for publication: Dictator functions maximize mutual information