1 Communication as an engineering problem
11 Communication
Information theory was originally developed to provide a theoretical framework for addressing an engineering problem of communication. Formally, consider a scenario where a sender wants to transmit a message, denoted as , to a receiver. In information theory, the semantic content of messages is irrelevant; the focus is solely on the engineering aspects of transmission. Here, the message is treated as a sequence of symbols.
12 Symbols
Symbols are distinct, identifiable entities that form the alphabet used to represent a message. For instance, the digits from 0 to 9 can be used to represent any integer number (the message). Similarly, nodding or shaking one’s head can be considered symbols representing the messages “yes” and “no.” For hearing-impaired individuals, hand gestures are used as symbols to communicate, with each gesture representing a specific symbol.
13 Encoding
The simplest symbolic system capable of transmitting information must have at least two distinct symbols, such as “0” and “1.” Using this simple formal language, we can encode basic messages.
A message about whether it will rain tomorrow can be encoded with just two symbols:
The outcome of a coin flip can be encoded similarly:
Messages can be represented by the codes used for their encoding. More complex messages can be encoded as sequences of symbols.
For four possible messages:
The following encoding can be used:
These binary sequences carry information. Importantly, there is no way to transmit this information in a more compact form; we need at least a sequence of length 2 binary symbols to encode the weather and coin states. Thus, this code is optimal and cannot be further compressed.
2 Bits
21 Uncertainty
A particular message can be considered successfully transmitted if and only if the receiver can identify this specific message from the set of all possible messages . The larger the set is, the harder it is to select from the set of all possible messages. Therefore, the larger , the greater the uncertainty associated with determining the transmitted message. Uncertainty is directly related to the number of possible messages.
22 Bits
Various encoding schemes can be used to transmit the same message. To abstract away from the details of specific encodings and focus on the information content itself, we introduce the concept of bits. A bit is the minimum amount of information required to eliminate uncertainty between two possibilities. The sender must transmit at least 1 bit so that the receiver can distinguish the sent message from a set of two possible messages .
If the set of all possible messages contains messages, each bit of information can be used to eliminate half of the remaining possibilities.
- The first bit divides the set into two halves:
- The second bit further divides the set:
23 Information
The amount of bits required to identify a specific message is called the information content . The sender sends bits of information by transmitting the message , and the receiver receives bits of information when decoding the message to identify from the set .
3 Hartley function
31 Bits
When there are multiple possible outcomes, we can distinguish between them if we have the necessary information. The minimal amount of information is 1 bit. By definition, each bit of information distinguishes between 2 possibilities. For example, 1 bit of information is required to unambiguously identify the sex of a child. The event:
corresponds to exactly 1 bit of information, and the inverse event similarly corresponds to 1 bit of information:
32 Additivity
For two independent and equally probable events:
we expect the total amount of information received when both events have occurred to be additive:
Since the logarithm satisfies this property, the possible choice is:
33 Probability
The probability characterizes the frequency of an event. An event with a high probability provides a small amount of information. For instance, the probability of the sunrise is nearly one, so the information that there will be a sunrise tomorrow carries little value. In contrast, the information that there will be no sunrise tomorrow conveys a significant amount of information. Thus, the lower the probability, the more information is conveyed:
The appropriate formula that satisfies these conditions is:
34 Inverse probability
The inverse probability represents the expected number of trials needed to achieve one occurrence of an event with probability . For example, if , the event occurs, on average, once every 100 trials.
35 Information content
In -valued logic, each -valued digit (0, 1, …, ) represents information:
Information is the capacity to distinguish between possibilities. Each bit of information distinguishes 2 possibilities, and it can assume 2 different values, 0 and 1. bits of information distinguish possibilities. Hence, the amount of information required to distinguish between possibilities is bits.
If there are outcomes, each time you assign a bit value to an outcome, you divide all outcomes into 2 sets corresponding to the bit values:
Now, for any , knowing the corresponding bit value allows you to determine whether or , thereby halving the uncertainty.
Repeating this times, you partition into disjoint sets, or more precisely, , as contains only elements:
Once the sets contain only one element, further bits do not provide additional meaningful information. Therefore, the amount of information is proportional to the size of . Each bit splits into 2 parts, and each subsequent bit continues dividing the sets into 2 parts. However, it is only meaningful to repeat these binary divisions up to times.
Thus, the exact number of bits needed to distinguish all outcomes is:
4 Self-information
Self-information, introduced by Claude Shannon, quantifies the amount of information or “surprise” associated with the occurrence of an event. The key properties of Shannon’s self-information are:
- An event with a probability of 100% is unsurprising and thus carries no information.
- Events that are less probable yield more information when they occur.
- For two independent events, the total information is the sum of their individual self-informations.
The self-information for an event is defined as:
For a random variable taking a specific value with probability , the self-information is:
41 Odds ratio
The odds of an event is defined as the difference in self-information (also known as surprisal) between the event and its complement :
5 Shannon entropy
Boltzmann distribution: maximizes thermodynamic probability and provides the probability for each state, so the Boltzmann formula defines a probability distribution: Shannon’s information entropy can be applied to this probability distribution: As a result, we get statistical entropy expressed via the partition function: The amount of information needed to encode the probability distribution by energy levels can be calculated via Shannon’s formula. This amount of information directly corresponds to the statistical thermodynamic entropy with units, which translates bits into energy per temperature units.
51 Information associated with a probability distribution.
Information corresponds to the amount of uncertainty: the more uncertain (less probable) an outcome is, the more information it carries.
As for a single outcome , we can define the information associated with the probability distribution . Let it be the expected value of the self-information:
This quantity is known as the Shannon entropy, it can be interpreted as the average amount of information produced by the probability distribution.
As a random variable induces its own probability distribution , the entropy can be defined specifically for the random variable:
which is equivalent to the distribution of the events .
Fair dice: induces the uniform distribution over the set of possible outcomes .
We need exactly bits to encode each outcome. All outcomes are equally probable, so we need the same bits of information to encode any outcome on average.
On the other hand, when we roll a fair dice, we receive bits of information from any outcome, and on average we receive the entropy amount of information:
52 Conditional entropy
Entropy can be generalized to the conditional case. Suppose that we have random variables and , with their (marginal) distributions and and their joint distribution .
53 Specific conditional entropy
can be trivially defined by replacing the probability with the conditional probability :
54 Conditional entropy
(non specific) is can be defined as the expected value of the specific conditional entropy over all possible values of :