James L. Massey (1934-2013)

Posted on June 16, 2013 by Sergio Verdu

James Massey, pioneering coding and information theorist, passed away today June 16, 2013 after a battle with cancer.

An extended interview can be found in

http://www.ieeeghn.org/wiki/index.php/Oral-History:James_L._Massey

Claude Shannon Centennial Stamp U. S. Postal Service

Posted on May 1, 2013 by Sergio Verdu

Please add your name to the petition list:

http://www.itsoc.org/about/shannons-centenary-us-postal-stamp

An Inequality Involving a Product of Mutual Informations

Posted on April 5, 2013 by Jingbo Liu

Many inequalities in information theory have entropies or mutual informations appearing as linear additive terms (e.g. Shannon-type inequalities). It’s also not uncommon to see entropies appearing as exponents (e.g. entropy power inequality). But perhaps it’s not immediately seen how products of mutual informations make sense.

Recently I have encountered an inequality involving a product of mutual informations, which I cannot find a good way to prove (or disprove, though some numerics and asymptotic analysis seem to suggest its validity). I would much appreciate it if someone could be smart and gracious enough to provide a proof, or counter example, or generalization.

The formulation is quite simple: suppose $X$ is a binary random variable with $\displaystyle P(X=0)=P(X=1)=1/2$ . The random variable $Y$ is the output of $X$ passing through a binary symmetric channel. Moreover $Z$ is another random variable such that $X-Y-Z$ forms a Markov chain. The claim is that $I(X;Z)\ge I(X;Y)I(Y;Z)$ . (Note that the left side is also upper bounded by either one of the two factors on the right side, by the well-known data processing inequality.

At first glance this inequality seems absurd because different units appear on the two sides; but this may be resolved by considering that $Y$ has only one bit of information.

For a given joint distribution of $X$ and $Y$ , the equality can be achieved when $Z$ is an injective function of $Y$ .

Teaching Lossless Data Compression

Posted on April 1, 2013 by Sergio Verdu

http://www.princeton.edu/~verdu/reprints/VerITNL2011.pdf

An Extremal Conjecture: Experimenting with Online Collaboration

Posted on March 5, 2013 by Thomas Courtade

I have an extremal conjecture that I have been working on intermittently with some colleagues (including Jiantao Jiao, Tsachy Weissman, Chandra Nair, and Kartik Venkat). Despite our efforts, we have not been able to prove it. Hence, I thought I would experiment with online collaboration by offering it to the broader IT community.

In order to make things interesting, we are offering a $1000 prize for the first correct proof of the conjecture, or a $250 award for the first counterexample! Feel free to post your thoughts in the public comments. You can also email me if you have questions or want to bounce some ideas off me.

Although I have no way of enforcing them, please abide by the following ground rules:

If you decide to work on this conjecture, please send me an email to let me know that you are doing so. As part of this experiment with online collaboration, I want to gauge how many people become involved at various degrees.
If you solve the conjecture or make significant progress, please keep me informed.
If you repost this conjecture, or publish any results, please cite this blog post appropriately.

One final disclaimer: this post is meant to be a brief introduction to the conjecture, with a few partial results to get the conversation started; it is not an exhaustive account of the approaches we have tried.

1. The Conjecture

Conjecture 1. Suppose ${X,Y}$ are jointly Gaussian, each with unit variance and correlation ${\rho}$ . Then, for any ${U,V}$ satisfying ${U-X-Y-V}$ , the following inequality holds:

$\displaystyle 2^{-2I(Y;U)} 2^{-2I(X;V|U)} \geq (1-\rho^2)+ \rho^2 2^{-2I(X;U)} 2^{-2I(Y;V|U)} . \ \ \ \ \ (1)$

2. Partial Results

There are several partial results which suggest the validity of Conjecture 1. Moreover, numerical experiments have not produced a counterexample.

Conjecture 1 extends the following well-known consequence of the conditional entropy power inequality to include long Markov chains.

Lemma 1 (Oohama, 1997). Suppose ${X,Y}$ are jointly Gaussian, each with unit variance and correlation ${\rho}$ . Then, for any ${U}$ satisfying ${U-X-Y}$ , the following inequality holds:

$\displaystyle 2^{-2 I(Y;U)} \geq 1-\rho^2+\rho^2 2^{-2I(X;U)}. \ \ \ \ \ (2)$

Proof: Consider any ${U}$ satisfying ${U-X-Y}$ . Let ${Y_u, X_u}$ denote the random variables ${X,Y}$ conditioned on ${U=u}$ . By Markovity and definition of ${X,Y}$ , we have that ${Y_u = \rho X_u + Z}$ , where ${Z\sim N(0,1-\rho^2)}$ is independent of ${X_u}$ . Hence, the conditional entropy power inequality implies that

$\displaystyle 2^{2h(Y|U)} \geq \rho^2 2^{2h(X|U)} + 2 \pi e(1-\rho^2) = 2 \pi e \rho^2 2^{-2I(X;U)} + 2 \pi e(1-\rho^2). \ \ \ \ \ (3)$

From here, the lemma easily follows. $\Box$

Lemma 1 can be applied to prove the following special case of Conjecture 1. This result subsumes most of the special cases I can think of analyzing analytically.

Proposition 1. Suppose ${X,Y}$ are jointly Gaussian, each with unit variance and correlation ${\rho}$ . If ${U-X-Y}$ are jointly Gaussian and ${U-X-Y-V}$ , then

$\displaystyle 2^{-2I(Y;U)} 2^{-2I(X;V|U)} \geq (1-\rho^2)+ \rho^2 2^{-2I(X;U)} 2^{-2I(Y;V|U)}. \ \ \ \ \ (4)$

Proof: Without loss of generality, we can assume that ${U}$ has zero mean and unit variance. Define ${\rho_u = E[XU]}$ . Since ${U-X-Y}$ are jointly Gaussian, we have

$\displaystyle I(X;U) =\frac{1}{2}\log\frac{1}{1-\rho_u^2} \ \ \ \ \ (5)$

$\displaystyle I(Y;U) =\frac{1}{2}\log\frac{1}{1-\rho^2\rho_u^2}. \ \ \ \ \ (6)$

Let ${X_u,Y_u,V_u}$ denote the random variables ${X,Y,V}$ conditioned on ${U=u}$ , respectively. Define ${\rho_{XY|u}}$ to be the correlation coefficient between ${X_u}$ and ${Y_u}$ . It is readily verified that

$\displaystyle \rho_{XY|u} = \frac{\rho\sqrt{1-\rho_u^2}}{\sqrt{1-\rho^2\rho_u^2}}, \ \ \ \ \ (7)$

which does not depend on the particular value of ${u}$ . By plugging (5)-(7) into (4), we see that (4) is equivalent to

$\displaystyle 2^{-2I(X;V|U)} \geq (1-\rho_{XY|u}^2)+ \rho_{XY|u}^2 2^{-2I(Y;V|U)}. \ \ \ \ \ (8)$

For every ${u}$ , the variables ${X_u,Y_u}$ are jointly Gaussian with correlation coefficient ${\rho_{XY|u}}$ and ${X_u-Y_u-V_u}$ form a Markov chain, hence Lemma 1 implies

$\displaystyle 2^{-2I(X_u;V_u)} \geq (1-\rho_{XY|u}^2)+ \rho_{XY|u}^2 2^{-2I(Y_u;V_u)}. \ \ \ \ \ (9)$

The desired inequality (8) follows by convexity of

$\displaystyle \log\left[(1-\rho_{XY|u}^2)+ \rho_{XY|u}^2 2^{-2z}\right] \ \ \ \ \ (10)$

as a function of ${z}$ . $\Box$

3. Equivalent Forms

There are many equivalent forms of Conjecture 1. For example, (1) can be replaced by the symmetric inequality

$\displaystyle 2^{-2(I(X;V)+I(Y;U))} \geq (1-\rho^2)2^{-2I(U;V)}+ \rho^2 2^{-2(I(X;U)+I(Y;V))}. \ \ \ \ \ (11)$

Alternatively, we can consider dual forms of Conjecture 1. For instance, one such form is stated as follows:

Conjecture 1′. Suppose ${X,Y}$ are jointly Gaussian, each with unit variance and correlation ${\rho}$ . For ${\lambda\in [{1}/({1+\rho^2}),1]}$ , the infimum of

$\displaystyle I(X,Y;U,V)-\lambda\Big(I(X;UV)+I(Y;UV)\Big), \ \ \ \ \ (12)$

taken over all ${U,V}$ satisfying ${U-X-Y-V}$ is attained when ${U,X,Y,V}$ are jointly Gaussian.

President Obama bestows 2011 National Medals of Science and Technology

Posted on February 1, 2013 by Sergio Verdu

including Claude E. Shannon Award winner Sol Golomb

http://www.whitehouse.gov/photos-and-video/video/2013/02/01/president-obama-honors-countrys-top-innovators-and-scientists-2011

Nevanlinna Prize

Posted on January 31, 2013 by Sergio Verdu

Nominations of people born on or after January 1, 1974

for outstanding contributions in Mathematical Aspects of Information Sciences including:

All mathematical aspects of computer science, including complexity theory, logic of programming languages, analysis of algorithms, cryptography, computer vision, pattern recognition, information processing and modelling of intelligence.
Scientific computing and numerical analysis. Computational aspects of optimization and control theory. Computer algebra.

Nomination Procedure: http://www.mathunion.org/general/prizes/nevanlinna/details/

The Epijournal: a new publication model

Posted on January 23, 2013 by Sergio Verdu

http://www.nature.com/news/mathematicians-aim-to-take-publishers-out-of-publishing-1.12243

Information and Inference (new journal)

Posted on January 3, 2013 by Sergio Verdu

The first issue of Information and Inference has just appeared:

http://imaiai.oxfordjournals.org/content/current

It includes the following editorial:

In recent years, a great deal of energy and talent have been devoted to new research problems arising from our era of abundant and varied data/information. These efforts have combined advanced methods drawn from across the spectrum of established academic disciplines: discrete and applied mathematics, computer science, theoretical statistics, physics, engineering, biology and even finance. This new journal is designed to serve as a meeting place for ideas connecting the theory and application of information and inference from across these disciplines.

While the frontiers of research involving information and inference are dynamic, we are currently planning to publish in information theory, statistical inference, network analysis, numerical analysis, learning theory, applied and computational harmonic analysis, probability, combinatorics, signal and image processing, and high-dimensional geometry; we also encourage papers not fitting the above description, but which expose novel problems, innovative data types, surprising connections between disciplines and alternative approaches to inference. This first issue exemplifies this topical diversity of the subject matter, linked by the use of sophisticated mathematical modelling, techniques of analysis, and focus on timely applications.

To enhance the impact of each manuscript, authors are encouraged to provide software to illus- trate their algorithm and where possible replicate the experiments presented in their manuscripts. Manuscripts with accompanying software are marked as “reproducible” and have the software linked on the journal website under supplementary material. It is with pleasure that we welcome the scien- tific community to this new publication venue.

Robert Calderbank David L. Donoho John Shawe-Taylor Jared Tanner

Comparing Variability of Random Variables

Posted on January 2, 2013 by Tara Javidi

Consider exchangeable random variables ${X_1, \ldots, X_n, \ldots}$ . A couple of facts seem quite intuitive:

Statement 1. The “variability” of sample mean ${S_m = \frac{1}{m} \sum_{i=1}^{m} X_i}$ decreases with ${m}$ .

Statement 2. Let the average of functions ${f_1, f_2, \ldots, f_n}$ be defined as ${\overline{f} (x) := \frac{1}{n} \sum_{i=1}^{n} f_i(x)}$ . Then ${\max_{1\leq i \leq n} \overline{f}(X_i)}$ is less “variable” than ${\max_{1\leq i \leq n} f_i (X_i)}$ .

To make these statements precise, one faces the fundamental question of comparing two random variables ${W}$ and ${Z}$ (or more precisely comparing two distributions). One common way we think of ordering random variables is the notion of stochastic dominance:

$\displaystyle W \leq_{st} Z \Leftrightarrow F_W(t) \geq F_Z(t) \ \ \ \mbox{ for all real } t.$

However, this notion really is only a suitable notion when one is concerned with the actual size of the random quantities of interest, while, in our scenario of interest, a more natural order would be that which compares the variability between two random variables (or more precisely, again, the two distributions). It turns out that a very useful notion, used in a variety of fields, is due to Ross (1983): Random variable ${W}$ is said to be stochastically less variable than random variable ${Z}$ (denoted by ${\leq_v}$ ) when every risk-averse decision maker will choose ${W}$ over ${Z}$ (given they have similar means). More precisely, for random variables ${W}$ and ${Z}$ with finite means

$\displaystyle W \leq_{v} Z \Leftrightarrow \mathbb{E}[f(X)] \leq \mathbb{E}[f(Y)] \ \ \mbox{ for increasing and convex function } f \in \mathcal{F}$

where ${\mathcal{F}}$ is the set of functions for which the above expectations exist.

One interesting, but perhaps not entirely obvious, fact is that this notion of ordering ${W\leq_v Z}$ is equivalent to saying that there is a sequence of mean preserving spreads that in the limit transforms the distribution of ${W}$ into the distribution of another random variable ${W'}$ with finite mean such that ${W'\leq_{st} Z}$ ! Also, using results by Hardy, Littlewood and Polya (1929), the stochastic variability order introduced above can be shown to be equivalent to Lorenz (1905) ordering used in economics to measure income equality.

Now with this, we are ready to formalize our previous statements. The first statement is actually due to Arnold and Villasenor (1986):

$\displaystyle \frac{1}{m} \sum_{i=1}^{m} X_i \leq_v \frac{1}{m-1} \sum_{i=1}^{m-1} X_i \ \ \ \ \ \ \ \ \ \ \ \ \mbox{for all }\ \ m \in \mathbb{N}.$

Note that when you apply this fact to a sequence of iid random variables with finite mean ${\mu}$ , it strengthens the strong law of large number in that it ensures that the almost sure convergence of the sample mean to the mean value ${\mu}$ occurs with monotonically decreasing variability (as the sample size grows).

The second statement comes up in proving certain optimality result in sharing parallel servers in fork-join queueing systems (J. 2008) and has a similar flavor:

$\displaystyle \max_{1\leq i \leq n} \overline{f}(X_i) \leq_v \max_{1\leq i \leq n} f_i (X_i).$

The cleanest way to prove both statements, to the best of my knowledge, is based on the following theorem first proved by Blackwell in 1953 (later strengthened to random elements in separable Banach spaces by Strassen in 1965, hence referred to by some as Strassen’s theorem):

Theorem 1 Let ${W}$ and ${Z}$ be two random variables with finite means. A necessary and sufficient condition for ${W \leq_v Z}$ is that there are two random variables ${\hat{W}}$ and ${\hat{Z}}$ with the same marginals as ${W}$ and ${Z}$ , respectively, such that ${\mathbb{E}[\hat{Z} |\hat{W}] \geq \hat{W}}$ almost surely.

For instance, to prove the first statement we consider ${\hat{W} = W = \frac{1}{n} \sum_{i=1}^n X_i}$ and ${Z = \frac{1}{n-1} \sum_{i=1}^{n-1} X_i}$ . All that is necessary now is to note that ${\hat{Z} : = \frac{1}{n-1} \sum_{i\in I, i \neq J} X_i}$ , ${J}$ is an independent uniform rv on the set ${I := \{1,2, \ldots, n\}}$ , has the same distribution as random variable ${Z}$ . Furthermore,

$\displaystyle \mathbb{E} [ \hat{Z} | W ] = \mathbb{E} [ \frac{1}{n} \sum_{J=1}^{n} (\frac{1}{n-1} \sum_{i\in I, i \neq J} X_i ) | W ] = \mathbb{E} [ \frac{1}{n} \sum_{j=1}^{n} X_j | W ] = W.$

Similarly to prove the second statement, one can construct ${\hat{Z}}$ by selecting a random permutation of functions ${f_1, \ldots, f_n}$ .