How to understand intuitively the concavity of the binary entropy?

Question

In Nielsen and Chuang's Quantum Computation and Quantum Information book, introducing the binary entropy, they gave an intuitive example about why binary entropy is concave:

Alice has in her possession two coins, one a quarter from the US, the other a dollar coin from Australia. Both coins have been altered to exhibit bias, with the probability of heads on the US coin being $p_U$, and the probability of heads on the Australian coin being $p_A$. Suppose Alice flips the US coin with probability $q$ and the Australian coin with probability $1 − q$, telling Bob whether the result was heads or tails. How much information does Bob gain on average? Intuitively it is clear that Bob should gain at least as much information as the average of the information he would have gained from a US coin flip or an Australian coin flip. As an equation this intuition may be expressed as: $$ H\left(q p_{\mathrm{U}}+(1-q) p_{\mathrm{A}}\right) \geq q H\left(p_{\mathrm{U}}\right)+(1-q) H\left(p_{\mathrm{A}}\right) $$

My main question is that I understand how to prove the concavity by math, but I don't get the intuition they mentioned here. I guess does it mean that $H\left(q p_{\mathrm{U}}+(1-q) p_{\mathrm{A}}\right)$ shows we have the information that we have two different coins while $q H\left(p_{\mathrm{U}}\right)+(1-q) H\left(p_{\mathrm{A}}\right)$ doesn't show the information that we have two different coins, so the information is less than the left term in the formula?

Answer 1

Consider the probability vector $P(i)=q p_U(i) + (1-q) p_A(i)$. You can understand this as a process involving two sequential choices: first a coin is tossed to decide between $p_U$ and $p_A$, with the former picked with probability $q$, and then another coin (or dice, or however you like to imagine it) to decide between the possible outcomes $i$ according to the probabilities given by $p_U$ or $p_A$.

You can imagine this is a two-layered "tree of possibilities", with the first layer representing the choice between $p_U$ and $p_A$, and the second layer the choice of $i$ for each of the two cases in the first layer.

There are two natural questions you can ask about this process:

1. What is the information content corresponding to the possible outcomes? In other words, completely disregarding the internal structure of $P$ (meaning its being actually composed of two sequential choices), what is its entropy? This is $H(P)=H(q p_U+(1-q)p_A)$.

2. If you already know the outcome of the first choice (that is, you know whether you are in the $p_U$ or in the $p_A$ branch), what is the information content corresponding to the possible outcomes? This is $H(p_U)$ if we are in the $p_U$ branch, or $H(p_A)$ if we are in the other. If we don't want to assume we already know the outcome of the first coin toss, we then ought to consider the average such entropy, which is, therefore, $q H(p_U)+(1-q)H(p_A)$.

   You are therefore saying: consider the process of throwing the first coin, ending up with one of $p_U$ or $p_A$, and then asking what is the entropy of the remaining outcomes; what entropy should I expect to find?

Putting it in yet another way, the two quantities measure information content under different assumptions on what is known: $H(P)$ is the information content with no prior information; $q H(p_U)+(1-q)H(p_A)$ is the (average) information content once the outcome of the first coin toss is known.

If you know more about the process, in the sense of assuming you already know some outcomes, you should expect to see less entropy for the remaining randomness. You can see this more clearly imagining the extreme case in which both $p_U$ and $p_A$ are deterministic, i.e. have zero entropy. Then, if you know nothing, the entropy of the process if $H(P)$, but if already know whether you are sampling from $p_U$ or $p_A$, then the entropy is zero. And it remains zero even if you don't actually know which of the two you ended up with, because the average between zero and zero is zero.

Answer 2

The intuition you're looking for is explained using an example in the very next paragraph of the textbook.

Suppose, $p_U = \frac{1}{3}$ and $p_A = \frac{5}{6}$, and Alice tells Bob that the result of her toss is heads. Then Bob immediately realizes that the coin Alice tossed was most likely the American coin. So, in this scenario, Bob gains some additional information about the identity of the tossed coin as well. This explains why the LHS of your quoted inequality should intuitively be greater than or equal to the RHS in most cases.

I'd caution that this idea should serve as a rough intuition only and that it isn't enough to prove the inequality.