0.13 Coding  (Page 3/22)

Here's another everyday example. Someone living in Ithaca (New York) would be completely unsurprisedthat the weather forecast called for rain, and such a prediction would convey little real information since it rains frequently.On the other hand, to someone living in Reno (Nevada), a forecast of rain would be very surprising, and would convey that very unusualmeteorological events were at hand. In short, it would convey considerable information. Again, the amount of informationconveyed is inversely proportional to the probabilities of the events.

To transform this informal argument into a mathematical statement, consider a set of $N$ possible events $x_i$ , for $i=1,2,...,N$ . Each event represents one possible outcome of an experiment, such as the flipping of a coin or the transmissionof a symbol across a communication channel. Let $p\left(x_i\right)$ be the probability that the $i$ th event occurs, and suppose that some event must occur. When flipping the coin, it cannot roll into the corner and stand on its edge; each flip results in either $H$ or $T$ . This means that ${\sum }_{i=1}^{N}p\left(x_i\right)=1$ . The goal is to find a function $I\left(x_i\right)$ that represents the amount of information conveyed by each outcome.

The following three qualitative conditions all relate the probabilities of events with the amount of information they convey:

Thus, receipt of the symbol $x_i$ should

1. give the same information as receipt of $x_j$ if they are equally likely,
2. give more information if $x_i$ is less likely than $x_j$ , and
3. convey no information if it is known a priori that $x_i$ is the only alternative.

What kinds of functions $I\left(x_i\right)$ fulfill these requirements? There are many. For instance, $I\left(x_i\right)=\frac{1}{p\left(x_i\right)}-1$ and $I\left(x_i\right)=\frac{1-p^2\left(x_i\right)}{p\left(x_i\right)}$ both fulfill (i)–(iii).

To narrow down the possibilities, consider what happens when a series of experiments are conducted, or equivalently, when a series ofsymbols are transmitted. Intuitively, it seems reasonable that if $x_i$ occurs at one trial and $x_j$ occurs at the next, then the total information in the twotrials should be the sum of the information conveyed by receipt of $x_i$ and the information conveyed by receipt of $x_j$ ; that is, $I\left(x_i\right)+I\left(x_j\right)$ . This assumes that the two trials are independent of each other,that the second trial is not influenced by the outcome of first (and vice versa).

Formally, two events are defined to be independent if the probability that both occur is equal to the product of the individual probabilities—that is, if

where $p\left(x_i\text{and}{x}_j\right)$ means that $x_i$ occurred in the first trial and $x_j$ occurred in the second. This additivity requirement for the amount ofinformation conveyed by the occurrence of independent eventsis formally stated in terms of the information function as

when the events $x_i$ and $x_j$ are independent.

Combining the additivity in $\left(iv\right)$ with the three conditions $\left(i\right)--\left(iii\right)$ , there is one (and only one) possibility for $I\left(x_i\right)$ :

It is easy to see that $\left(i\right)--\left(iii\right)$ are fulfilled, and $\left(iv\right)$ follows from the properties of the $log$ (recall that $log\left(ab\right)=log\left(a\right)+log\left(b\right)$ ). Therefore,