New identities for the Shannon-Wiener entropy function with applications

In Renyi’s A Diary on Information Theory, [8], he points out that the entropy formula, i.e.,

where logs are to the base 2, was arrived at, independently, by Claude Shannon and Norbert Wiener in 1948. This famous formula was the revolutionary precursor of the information age. Renyi goes on to say that,

• this formula had already appeared in the work of Boltzmann which is why it is also called the Boltzmann-Shannon Formula. Boltzmann arrived at this formula in connection with a completely different problem. Almost half a century before Shannon he gave essentially the same formula to describe entropy in his investigations of statistical mechanics. He showed that if, in a gas containing a large number of molecules the probabilities of the possible states of the individual molecules are $p_{1},p_{2},\ldots,p_{N}$ then the entropy of the system is $H=c(p_{1}\log\frac{1}{p_{1}}+p_{2}\log\frac{1}{p_{2}}+\cdots+p_{N}\log\frac{1}{p_{N}})$ where $c$ is a constant. (In statistical mechanics the natural logarithm is used and not base 2 …). The entropy of a physical system is the measure of its disorder …

Since 1948 there have been many advances in information theory and entropy. A well-known paper of Dembo, Cover and Thomas is devoted to inequalities in information theory. Here, we concentrate on equalities. We show how a Shannon function $H(p,q)$ can be expanded in infinitely many ways in an infinite series of functions each of which is a linear combination of Shannon functions of the type $H\bigl{(}f(p),g(q)\bigr{)}$, where $f,g$ are quotients of polynomials of degree $n$ for any $n\geq 2$. Apart from its intrinsic interest, this new result gives insight into the algorithm in Section 6 for constructing a common secret key between two communicating parties — see also [2], [3], [4], [6].

Recall that a binary symmetric channel has input and output symbols drawn from $\{0,1\}$. We say that there is a common probability $q=1-p$ of any symbol being transmitted incorrectly, independently for each transmitted symbol, $0\leq p\leq 1$.

We use the channel matrix $P=\left(\begin{array}[]{cc}p&q\\ q&p\end{array}\right)$. Again, $p$ is the probability of success, i.e., $p$ denotes the probability that 0 is transmitted to 0 and also the probability that 1 gets transmitted to 1. The second extension $P^{(2)}$ of $P$ has alphabet $\{00,01,10,11\}$ and channel matrix

An alternative way to think of an $n^{th}$ extension of a channel $C$ (see Welsh [9]) is to regard it as $n$ copies of $C$ acting independently and in parallel. See Figure 1.

Let us assume also that, for $C$, the input probability of 0 and the input probability of 1 are both equal to $\frac{1}{2}$.

• Proof.

  (a) Since, by definition, the $X_{i}$ are independent,

  $$H(\mathbf{X})=H(X_{1})+H(X_{2})+\cdots+H(X_{n}).$$

  We have

  	$\displaystyle H(X_{i})$	$\displaystyle=-\biggl{[}Pr(X_{i}=0)\log Pr(X_{i}=0)+Pr(X_{i}=1)\log Pr(X_{i}=1)\biggr{]}$
  		$\displaystyle=-\biggl{[}\frac{1}{2}\log\bigl{(}\frac{1}{2}\bigr{)}+\frac{1}{2}\log\bigl{(}\frac{1}{2}\bigr{)}\biggr{]}$
  		$\displaystyle=-\log\bigl{(}\frac{1}{2}\bigr{)}$
  		$\displaystyle=-[\log 1-\log 2]=\log 2=1.$

  Thus $H(\mathbf{X})=n$.

  (b) The value of $Y_{i}$ only depends on $X_{i}$. The $X_{i}$ are independent. Thus $Y_{1},Y_{2},\ldots,Y_{n}$ are independent. For any $Y_{i}$ we have

  $$Pr(Y_{i}=0)=Pr(X_{i}=0)(p)+Pr(X_{i}=1)(q)=\frac{1}{2}(p+q)=\frac{1}{2}.$$

  Also $Pr(Y_{i}=1)=\frac{1}{2}$. Then, as for $X_{i}$, $H(Y_{i})=1$. Thus $H(\mathbf{Y})=H(Y_{1},Y_{2},\ldots,Y_{n})=\sum_{i}H(Y_{i})=n$.

First we need some additional discussion on entropy.

More generally, if $X_{1},X_{2},\ldots,X_{m}$ is a collection of random variables each taking only a finite set of values, then we can regard $\mathbf{X}=(X_{1},X_{2},\ldots,X_{m})$ as a random vector taking a finite set of values and we define the joint entropy of $X_{1},\ldots,X_{m}$ by

Standard results for random variables then carry over to random vectors — see [1], [9].

Let $p=p_{1}+p_{2}+\cdots+p_{m}$ and $q=q_{1}+q_{2}+\cdots+q_{n}$ where each $p_{i}$ and $q_{j}$ is non-negative. Assume that $p,q$ are positive with $p+q=1$. Then

For example, suppose $m=1$ so $p_{1}=p$. Then we get

This is because $p_{1}H\bigl{(}\frac{p_{1}}{p_{1}},0\bigr{)}=p_{1}H(1,0)=p_{1}(1\log 1)=p_{1}(0)=0$.

• Proof.

  	$\displaystyle H(\mathbf{X}\,|\,\mathbf{Y})$	$\displaystyle=H(\mathbf{X},\mathbf{Y})-H(\mathbf{Y})$
  		$\displaystyle=H(\mathbf{X},\mathbf{Y},\mathbf{Z})-H(\mathbf{Z}\,|\,\mathbf{X},\mathbf{Y})-H(\mathbf{Y})$
  		$\displaystyle=H(\mathbf{X},\mathbf{Y},\mathbf{Z})-H(\mathbf{Y})\qquad\hbox{[\,since $H(\mathbf{Z}\,|\,\mathbf{X},\mathbf{Y})=0$\,]}$
  		$\displaystyle=H(\mathbf{Y})+H(\mathbf{X},\mathbf{Z}\,|\,\mathbf{Y})-H(\mathbf{Y})$
  		$\displaystyle=H(\mathbf{X},\mathbf{Z}\,|\,\mathbf{Y}),\qquad\hbox{proving (a).}$

  For (b),

  	$\displaystyle H(\mathbf{X}\,|\,\mathbf{Y})$	$\displaystyle=H(\mathbf{X},\mathbf{Z},\mathbf{Y})-H(\mathbf{Y})\hbox{ from (a)}$
  		$\displaystyle=H(\mathbf{X},\mathbf{Z},\mathbf{Y})-H(\mathbf{Y},\mathbf{Z})+H(\mathbf{Y},\mathbf{Z})-H(\mathbf{Y})$
  		$\displaystyle=H(\mathbf{X}\,|\,\mathbf{Y},\mathbf{Z})+H(\mathbf{Z}\,|\,\mathbf{Y}).$

  $\blacksquare$

We will use the above identity, i.e.,

which holds under the assumption that $H(\mathbf{Z}\,|\,\mathbf{X},\mathbf{Y})=0$. We begin with arrays $A=\left(\begin{array}[]{c}a_{1}\\ a_{2}\\ \vdots\\ a_{n}\end{array}\right)$, $B=\left(\begin{array}[]{c}b_{1}\\ b_{2}\\ \vdots\\ b_{n}\end{array}\right)$, where $n$ is even. We assume that $A,B$ are random binary strings subject to the condition that, for each $i$, we have $Pr(a_{i}=b_{i})=p$. We also assume that the events $\{(a_{i}=b_{i})\}$ form an independent set. We divide $A,B$ into blocks of size 2.

To start, put $\mathbf{X}=\left(\begin{array}[]{c}x_{1}\\ x_{2}\end{array}\right)$, $\mathbf{Y}=\left(\begin{array}[]{c}y_{1}\\ y_{2}\end{array}\right)$, $\mathbf{Z}=x_{1}+x_{2}$.

• Proof.

  We want to calculate $\sum_{\mathbf{x},\mathbf{y}}H(\mathbf{Z}\,|\,\mathbf{x},\mathbf{y})Pr(X=\mathbf{x},Y=\mathbf{y})$. Given $\mathbf{x},\mathbf{y}$, say $\mathbf{x}=\left(\begin{array}[]{c}\alpha_{1}\\ \alpha_{2}\end{array}\right)$, $\mathbf{y}=\left(\begin{array}[]{c}\beta_{1}\\ \beta_{2}\end{array}\right)$ the value of $\mathbf{Z}$ is $\alpha_{1}+\alpha_{2}$. There is no uncertainty in the value of $\mathbf{Z}$ given $\mathbf{x},\mathbf{y}$, i.e., each term in the above sum for $H$ is $H(1,0)=0$. Therefore $H(\mathbf{Z}\,|\,\mathbf{X},\mathbf{Y})=0$. $\blacksquare$

From this we can use formula (4.1) for this block of size two. We can think of a channel from $\mathbf{X}$ to $\mathbf{Y}$ (or from $\mathbf{Y}$ to $\mathbf{X}$) which is the second extension of a binary symmetric channel where $p$ is the probability of success. We have

From Theorem 2.1 part (c) the left side, i.e., $H(\mathbf{X}\,|\,\mathbf{Y})$ is equal to $2H(p,q)$. Next we calculate the right side beginning with $H(\mathbf{Z}\,|\,\mathbf{Y})$, i.e., $H\left(\mathbf{Z}\,\Big{|}\,\left(\begin{array}[]{c}y_{1}\\ y_{2}\end{array}\right)\right)$. We have

We know that $Pr(x_{1}+x_{2}=y_{1}+y_{2})=p^{2}+q^{2}$ and $Pr(x_{1}+x_{2}\neq y_{1}+y_{2})=1-(p^{2}+q^{2})=2pq$ since $p+q=1$. From the standard formula we have $H(\mathbf{Z}\,|\,\mathbf{Y})=(p^{2}+q^{2})\log\left(\frac{1}{p^{2}+q^{2}}\right)+2pq\log\left(\frac{1}{2pq}\right)$ since $H(\mathbf{Z}\,|\,\mathbf{Y})=H(p^{2}+q^{2},2pq)$.

Next we calculate

Again we have two possibilities, i.e., $y_{1}+y_{2}=x_{1}+x_{2}$ and $y_{1}+y_{2}\neq x_{1}+x_{2}$. The corresponding probabilities are $p^{2}+q^{2}$ and $2pq$ respectively. We obtain

This comes about from the facts that

1. (a)

   If $y_{1}+y_{2}=x_{1}+x_{2}$ then we either have $y_{1}=x_{1}$ and $y_{2}=x_{2}$ or $y_{1}=1-x_{1}$, $y_{2}=1-x_{2}$.

2. (b)

   If $y_{1}+y_{2}\neq x_{1}+x_{2}$ then either $y_{1}=x_{1}$ and $y_{2}\neq x_{2}$ or $y_{1}\neq x_{1}$ and $y_{2}=x_{2}$.

3. (c)

   $H(\frac{1}{2},\frac{1}{2})=1$.

Then from equation (4.1) we have our first identity as follows

From Theorem 2.1 we have $H(\mathbf{X}|\mathbf{Y})=3H(p,q)$.

Similar to the case of blocks of size 2, we have $H(\mathbf{Z}|\mathbf{Y})=H(p^{3}+3pq^{2},q^{3}+3qp^{2})$. This is because the probabilities that $Z=y_{1}+y_{2}+y_{3}$ or $Z\neq y_{1}+y_{2}+y_{3}$ are, respectively, $p^{3}+3pq^{2}$ or $q^{3}+3qp^{2}$, as follows.

If $Z=y_{1}+y_{2}+y_{3}$, then either $x_{1}=y_{1}$, $x_{2}=y_{2}$, $x_{3}=y_{3}$ or else, for some $i$, $1\leq i\leq 3$ (3 possibilities) $x_{i}=y_{i}$ and, for the other two indices $j,k$, $x_{j}\neq y_{j}$ and $x_{k}\neq y_{k}$.

A similar analysis can be carried out for the case where $Z\neq y_{1}+y_{2}+y_{3}$. We then get $H(\mathbf{X}\,|\,\mathbf{Y},\mathbf{Z})=f(p,q)+f(q,p)$ where

We now use the grouping axiom for $m=1$. The $p$ in the formula refers to $\frac{p^{3}}{p^{3}+3pq^{2}}$ here and the $q$ there is now replaced by $\frac{3pq^{2}}{p^{3}+3pq^{2}}$. Then

$f(q,p)$ is obtained by interchanging $p$ with $q$. We note that, since $p+q=1$, $3pq^{2}\log 3+3qp^{2}\log 3=3pq\log 3$.

From working with blocks of size 3 we get

For blocks of size 2 formula (4.3) can be put in a more compact form in terms of capacities, namely,

Using the same method we can find a formula analogous to formulae (4.3), (4) for obtaining $nH(p,q)$ as a linear combination of terms of the form $H(u,v)$ where $u,v$ involve terms in $p^{n},p^{n-2}q^{2},\ldots,q^{n},q^{n-2}p^{2},\ldots$ plus extra terms such as $3pq\log 3$ as in formula (4).

The result of Theorem 2.1 can be extended to the more general case where we take the product of $n$ binary symmetric channels even if the channel matrices can be different corresponding to differing $p$-values.

As an example, suppose we use the product of 2 binary symmetric channels with channel matrices

Then the argument in Section 4 goes through. To avoid being overwhelmed by symbols we made a provisional notation change.

Then we arrive at the following addition formula

Similarly to the above we can derive a formula for $h(p_{1})+h(p_{2})+\cdots+h(p_{n})$.

The above method of using blocks of various sizes is reminiscent of the algorithm for the key exchange in [4] which relates to earlier work in [2], [6] and others. Indeed the identities above were informed by the details of the algorithm.

The algorithm starts with two arrays $(a_{1},\ldots,a_{n})$ and $(b_{1},\ldots,b_{n})$. We assume that the set of events $\{a_{i}=b_{i}\}$ is an independent set with $p=Pr(a_{i}=b_{i})$. We subdivide $A,B$ into corresponding sub-blocks of size $t$, where $t$ divides $n$. Exchanging parities by public discussion we end up with new shorter sub-arrays $A_{1},B_{1}$, where the probabilities of corresponding entries being equal are independent with probability $p_{1}>p$. Eventually after $m$ iterations we end up with a common secret key $A_{m}=B_{m}$.

Let us take an example. Start with two binary arrays $(a_{1},\ldots,a_{n})$ and $(b_{1},\ldots,b_{n})$ of length $n$ with $n$ even, $n=2t$, say. We subdivide the arrays into corresponding blocks of size 2. If the two blocks are $\left(\begin{array}[]{c}a_{1}\\ a_{2}\end{array}\right)$ and $\left(\begin{array}[]{c}b_{1}\\ b_{2}\end{array}\right)$ we discard those blocks if the parities disagree. If the parities agree, which happens with probability $p^{2}+q^{2}$, we keep $a_{1}$ and $b_{1}$, discarding $a_{2}$ and $b_{2}$. Thus, on average, we keep $(p^{2}+q^{2})\frac{n}{2}$ partial blocks and discard $\bigl{[}1-(p^{2}+q^{2})\bigr{]}\frac{n}{2}$ blocks of size 2.

Let us suppose $n=100$ and $p=0.7$. From Theorem 2.1 part (d), the information that $Y$ has about $X$, i.e., that $B$ has about $A$ is $100[1-H(0.7,0.3)]\approx 100(1-0.8813)\approx 11.87$ Shannon bits.

We are seeking to find a sub-array of $A,B$ such that corresponding bits are equal. Our method is to publicly exchange parities. The length of this secret key will be at most 11.

Back to the algorithm. $A,B$ keep on average $(50)(p^{2}+q^{2})$ blocks of size 2, i.e., $(50)(0.58)=29$ blocks of size 2. $A$ and $B$ remove the bottom element of each block. We are left with 29 pairs of elements $(a_{1},b_{1})$. The probability that $a_{1}=b_{1}$ given that $a_{1}+a_{2}=b_{1}+b_{2}$ is $\frac{p^{2}}{p^{2}+q^{2}}$, i.e., $\frac{(0.7)^{2}}{(0.7)^{2}+(0.3)^{2}}=\frac{0.49}{0.58}\approx 0.845$. Next, $1-H(0.845,0.155)\approx(1-0.6221)\approx 0.3779$. To summarize, we started with 100 pairs $(a_{i},b_{i})$ with $Pr(a_{i}=b_{i})=0.7$. The information revealed to $B$ by $A$ is $(100)(1-H(0.7,0.3))=11.87$ Shannon bits of information. After the first step of the algorithm we are left with 29 pairs $(a_{j},b_{j})$ with $Pr(a_{j}=b_{j})=0.845$. The amount of information revealed to the remnant of $B$ by the remnant of $A$ is $29(0.3779)\approx 10.96$ Shannon bits of information. So we have “wasted” less than 1 bit, i.e. the wastage is about 8%. Mathematically we have $100\bigl{(}1-H(0.7,0.3)\bigr{)}=29\bigl{(}1-H(0.845,0.155)\bigr{)}+$ Wastage. In general we have

where $W$ denotes the wastage. Dividing by $\frac{n}{2}$ we get

To sum up then the new identities tell us exactly how much information was wasted and not utilized. They also tell us, in conjunction with the algorithm, the optimum size of the sub-blocks at each stage.

One of the original motivations for work in coding theory was that the Shannon fundamental theorem showed how capacity was the bound for accurate communication but the problem was to construct linear codes or other codes such as turbo codes that came close to the bound.

Here we have an analogous situation. In the example just considered the maximum length of a cryptographic common secret key obtained as a common subset of $A,B$ is bounded by $n(1-H(p))$. The problem is to find algorithms which produce such a common secret key coming close to this Shannon bound of $n\bigl{(}1-H(p)\bigr{)}$.

This work nicely illustrates the inter-connections between codes, cryptography, and information theory. Information theory tells us the bound. The identities tell us the size of the sub-blocks for constructing a common secret key which attains, or gets close to, the information theory bound.

Coding theory is then used to ensure that the two communicating parties have a common secret key by using the hash function described in the algorithm using a code $C$. Error correction can ensure that the common secret key can be obtained without using another round of the algorithm (thereby shortening the common key) if the difference between the keys of $A$ and $B$ is less than the minimum distance of the dual code of $C$. This improves on the standard method of checking parities of random subsets of the keys $A_{m},B_{m}$ at the last stage.

1. 1.

   Please see Chapter 25 of the forthcoming Cryptography, Information Theory, and Error-Correction: A Handbook for the Twenty-First Century, by Bruen, Forcinito, and McQuillan, [3], for background information, additional details, and related material.

2. 2.

   Standard tables for entropy list values to two decimal places. When $p$ is close to 1 interpolation for three decimal places is difficult as $h(p)$ is very steeply sloped near $p=1$. Formula 4.3 may help since $\frac{p^{2}}{p^{2}+q^{2}}$ is less than $p$, and the formula can be re-iterated.

3. 3.

   In [4] the emphasis is on the situation where the eavesdropper has no initial information. The case where the eavesdropper has initial information is discussed in [6]. In Section 7 of [4] the quoted result uses Renyi entropy rather than Shannon entropy.

4. 4.

   The methods in this note suggest possible generalizations which we do not pursue here.