# 1985 Kyoto Prize in Mathematics

Claude Shannon’s acceptance speech “Development of Communication and Computing, and my Hobby”

http://emuseum.kyotoprize.org/sites/default/files/ClaudeElwoodShannon_e.pdf

# Bayesian Methods

A nice history can be found in

Fienberg, Stephen E. (2006). “When Did Bayesian Inference Become “Bayesian”?”. *Bayesian Analysis* **1** (1): 1–40.

http://ba.stat.cmu.edu/journal/2006/vol01/issue01/fienberg.pdf

# James L. Massey (1934-2013)

# Claude Shannon Centennial Stamp U. S. Postal Service

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

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 are binary random variables with , and is another random variable such that forms a Markov chain. The claim is that . (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 has only one bit of information.

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

———————————-

Update: the inequality has been proved, thanks very much for the help by Sudeep Kamath (see comments). An alternative proof (which avoids computing the monotonicity of is sketched as follows: by convexity of the function (see for example, proof of Mrs Gerbers Lemma), we have for any , where . Averaging over under gives , and the claim follows after rearrangements.

# Teaching Lossless Data Compression

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

# An Extremal Conjecture: Experimenting with Online Collaboration

**Update (4/3/2014): I believe I have solved the conjecture, and proven it to be correct. **~~I will make a preprint available shortly~~(see link below). The original blog post remains available below. — Tom

**Preprint available here:** “An extremal inequality for long Markov chains“.

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 or 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 are jointly Gaussian, each with unit variance and correlation . Then, for any satisfying , the following inequality holds:

**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 are jointly Gaussian, each with unit variance and correlation . Then, for any satisfying , the following inequality holds:

*Proof:* Consider any satisfying . Let denote the random variables conditioned on . By Markovity and definition of , we have that , where is independent of . Hence, the conditional entropy power inequality implies that

From here, the lemma easily follows.

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 are jointly Gaussian, each with unit variance and correlation . If are jointly Gaussian and , then

*Proof:* Without loss of generality, we can assume that has zero mean and unit variance. Define . Since are jointly Gaussian, we have

Let denote the random variables conditioned on , respectively. Define to be the correlation coefficient between and . It is readily verified that

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

For every , the variables are jointly Gaussian with correlation coefficient and form a Markov chain, hence Lemma 1 implies

The desired inequality (8) follows by convexity of

as a function of .

**3. Equivalent Forms **

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

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

Conjecture 1′.Suppose are jointly Gaussian, each with unit variance and correlation . For , the infimum of

taken over all satisfying is attained when are jointly Gaussian.

# President Obama bestows 2011 National Medals of Science and Technology

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

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/