Introduction to CoE 161

Welcome to CoE 161 / CoE 197!

Since we are offering this class remotely, there will be many changes to our normal course delivery:

1. There will be no face-to-face lecture classes. All the material will be made available via this site.
2. There will be more emphasis on student-centric activities, e.g. analysis, design, and simulations. Thus, you will be mostly "learning by doing". In this context, we will set aside an hour every week for consultations and questions via video-conferencing.
3. Grades will be based on the submitted deliverables from the activities. Though we will not be very strict regarding the deadlines, it is a good idea to keep up with the class schedule and avoid cramming later in the semester.

Please remember that this semester is very different from those before, and please make sure you inform me if you have any issues or difficulties regarding the class. Also, keep in mind that you will need to pay a bit more attention to your time management as it will play a critical role during the course of the semester.

Let's get started!

Measuring Complexity

Figure 1: Measuring complexity (from Ron Eglash, RPI).

For any system we are studying, designing, or building, an interesting and important question is usually: "How complex is this system?" or "How complex should this system be?". In general, we want to be able to compare two systems, and be able to say that one system is more complex than the other. In this case, having a numerical metric would be very convenient.

Possible ways of measuring complexity (obviously not a complete list!):

1. Human observation, thus making any kind of rating subjective.
2. Complexity based on the number of parts, components, or distinct elements. However, this depends on the definition of what is a "part". This is dependent on the observer's scale, from functional components down to atoms at the extreme case, as shown in Fig. 1.
3. Number of dimensions. This is sometimes hard to measure, e.g. degrees of freedom, etc.
4. Number of parameters controlling the system.
5. The minimal description needed. However, we need to figure out which language we need to use.
6. Information content. We then need to figure out how to define and measure information.
7. Minimum generator or constructor (to build the system). We need to define what tools and methods we need to use to build the system.
8. Minimum energy and/or time to construct the system. However, some systems evolve with time, so defining the beginning and end points can be difficult.

All of these measures are associated with a model of the system in question. Thus observers could use different models, and therefore come up with different notions of the complexity of the said system. We do not expect to come up with a single universal measure of complexity, but we can explore a framework that is optimal for (a) a particular observer, (b) a particular context, and (c) a particular purpose. Let us focus on the measures related to how unexpected an observation is, an approach known as Information Theory.

Some of the ideas and concepts that follow are based on basic probability ideas. You can review them here: Probability Review I.

The Basics of Information Theory

We want to create a metric for measuring the information we get from observing the occurrence of an event that has a probability $p$. Let us ignore all other features of the event, except whether the event occurred or not. We can then think of the event as seeing if a symbol, whose probability of occurring is $p$, appears. Thus, our definition of information is in terms of the probability $p$.

An Axiomatic Approach

Let us define our information measure as $I\left(p\right)$. We want $I\left(p\right)$ to have several properties:

Axiom	Implied Property
Information is a non-negative quantity.	$I\left(p\right)\geq 0$
If an event has a $p=1$, then we get no information from the occurrence of that event.	$I\left(1\right)=0$
If two independent events occur, then the information we get from observing the two events is the sum of the two 'informations'.	$I\left(p_{1}\cdot p_{2}\right)=I\left(p_{1}\right)+I\left(p_{2}\right)$
$I\left(p\right)$ is a continuous and monotonic function of the probability $p$.

Using these properties, we can then derive the following expressions:

$I\left(p^{2}\right)=I\left(p\cdot p\right)=I\left(p\right)+I\left(p\right)=2\cdot I\left(p\right)$

(1)

Thus, by induction:

$I\left(p^{n}\right)=n\cdot I\left(p\right)$

(2)

We can then write $I\left(p\right)=I\left(\left(p^{\frac {1}{m}}\right)^{m}\right)=m\cdot I\left(p^{\frac {1}{m}}\right)$, or equivalently:

$I\left(p^{\frac {1}{m}}\right)={\frac {1}{m}}\cdot I\left(p\right)$

(3)

In general, we get:

$I\left(p^{\frac {n}{m}}\right)={\frac {n}{m}}\cdot I\left(p\right)$

(4)

Since $I\left(p\right)$ is continuous, and for $0<p\leq 1$ and $a>0$ for a real number $a$, we get:

$I\left(p^{a}\right)=a\cdot I\left(p\right)$

(5)

From this, and by inspection, we can express $I\left(p\right)$, for some base $b$ as:

$I\left(p\right)=-\log _{b}\left(p\right)=\log _{b}\left({\frac {1}{p}}\right)$

(5)

Note that:

$\log _{b_{2}}\left(x\right)=\log _{b_{2}}\left(b_{1}\right)\cdot \log _{b_{1}}\left(x\right)$

(6)

Thus, we can easily change the base of the logarithm, and the resulting information measure are differ by just a multiplicative constant, and have the following units:

b	Units
2	bits (from binary)
3	trits (from trinary)
$e$	nats (from natural logarithm)
10	Hartleys

By default, and unless specified, we will be using $b=2$, so when we write $\log \left(p\right)$, we mean $\log _{2}\left(p\right)$.

A Simple Example

If we flip a fair coin, we will get two possible events: $\{h,t\}$, with probabilities $\{{\tfrac {1}{2}},{\tfrac {1}{2}}\}$. Thus, a one coin flip gives us $-\log _{2}\left({\tfrac {1}{2}}\right)=1$ bit of information, regardless of the result ($h$ or $t$).

If we flip the coin $n$ times, or equivalently, if we flip $n$ coins at the same time, the amount of information (in bits) that we would get is equal to:

$-\log _{2}\left(\left({\tfrac {1}{2}}\right)^{n}\right)=\log _{2}\left(2^{n}\right)=n\cdot \log _{2}\left(2\right)=n$

(7)

Enumerating the sequence of 16 flips would give us $hhththhthhthhthh$, or using a 1 for $h$ and 0 for $t$, we would get 1101011011011011. Notice that $n$ fair coin flips gives us $n$ bits of information, and requires a binary word that is $n$ digits long to describe.

Another Example: Surprise! The Unexpected Observation

Information can be thought of as the amount of surprise at seeing an event. Note that a highly probable outcome is not surprising. Consider the following events:

Event	Probability	Information (Surprise)
Someone tells you $1=1$.	$1$	$\log _{2}\left(1\right)=0$
You got the wrong answer on a 4-choice multiple choice question.	${\frac {3}{4}}$	$\log _{2}\left({\frac {4}{3}}\right)=0.415\,\mathrm {bits}$
You guessed correctly on a 4-choice multiple choice question.	${\frac {1}{4}}$	$\log _{2}\left(4\right)=2\,\mathrm {bits}$
You got the correct answer in a True or False question.	${\frac {1}{2}}$	$\log _{2}\left(2\right)=1\,\mathrm {bit}$
You rolled a seven on rolling a pair of dice.	${\frac {6}{36}}$	$\log _{2}\left(6\right)=2.58\,\mathrm {bits}$
Winning the Ultra Lotto 6/58 jackpot.	${\frac {1}{40400000}}$	$\log _{2}\left(40400000\right)=25.27\,\mathrm {bits}$

Introducing Entropy

Consider a source generating a stream of symbols. If there are $n$ distinct symbols, $\{a_{1},a_{2},\ldots a_{n}\}$, and the source emits these symbols with probabilities $\{p_{1},p_{2},\ldots p_{n}\}$ respectively. Let us assume that the symbols are emitted independently, e.g. the emitted symbol does not depend on past symbols.

If we observe the symbol $a_{i}$, we get $\log _{2}\left({\tfrac {1}{p_{i}}}\right)$ bits of information from that particular observation.

For $N$ observations, the symbol $a_{i}$ would occur approximately $\left(N\cdot p_{i}\right)$ times. Therefore, if we have $N$ independent observations, the total information, $I$, that we will get is:

$I=\sum _{i=1}^{n}{\left(N\cdot p_{i}\right)\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)}$

(8)

The average information that we get per symbol that we observe would then be equal to:

${\frac {I}{N}}={\frac {1}{N}}\sum _{i=1}^{n}{\left(N\cdot p_{i}\right)\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)}=\sum _{i=1}^{n}{p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)}$

(9)

Note that since $\lim _{x\rightarrow 0}x\cdot \log _{2}\left({\tfrac {1}{x}}\right)=0$, we will define $p_{i}\cdot \log _{2}\left({\tfrac {1}{p_{i}}}\right)=0$ when $p_{i}=0$.

The Definition of Entropy

Given a discrete probability distribution $P=\{p_{1},p_{2},\ldots ,p_{n}\}$, the entropy of the distribution $P$ is:

$H\left(P\right)=\sum _{i=1}^{n}p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)$

(10)

For a continuous probability distribution, $P\left(x\right)$, entropy is defined as:

$H\left(P\right)=\int P\left(x\right)\cdot \log _{2}\left({\frac {1}{P\left(x\right)}}\right)dx$

(11)

This definition was introduced by Claude Shannon in his landmark 1948 paper. For more information on the life of Claude Shannon, you can read this article, or watch this documentary film.

Alternative Definition of Entropy

Let $X$ be a discrete random variable taking values from a finite set ${\mathcal {X}}=\{x_{1},x_{2},\ldots ,x_{n}\}$ with the corresponding probability distribution is $P=\{p_{1},p_{2},\ldots ,p_{n}\}$. For a given function $g$, the expected value of $g(X)$ is given by:

$\operatorname {E} [g(X)]=\sum _{i=1}^{n}p_{i}\cdot g(x_{i})$

(12)

If $X$ is a continuous random variable with distribution $p\left(x\right)$, then the expected value of $g(X)$ is given by:

$\operatorname {E} [g\left(X\right)]=\int p\left(x\right)\cdot g(x)dx$

(13)

Hence, for $g(x_{i})=\log \left({\tfrac {1}{p_{i}}}\right)$1, or $\log \left({\tfrac {1}{p\left(x\right)}}\right)$, we can see that:

$H\left(P\right)=\operatorname {E} [I\left(p\right)]$

(14)

Thus, we can think of entropy of a probability distribution as the expected value of the information of the distribution.

In this course, we mostly limit our discussion of information theory to discrete random variables due to some nuances when dealing with continuous random variables. In fact, Shannon thought it was natural to replace the summation to an integral in calculating entropy for continuous random variables, only to be later shown that such an update would be inconsistent with his axioms on entropy.

For a continuous random variable $X$, we define the differential entropy as

$H\left(P\right)=\int p(x)\log \left({\frac {1}{p(x)}}\right)$

(15)

Unlike in the discrete case, differential entropy may in fact be negative, which violates Shannon's first assumption.

The Gibbs Inequality

Figure 2: The plot of $y=\ln \left(x\right)$ and $y=x-1$.

Consider the natural logarithm function, $\ln \left(x\right)$. The slope of the the line tangent to $\ln \left(x\right)$ at any point $x$ is equal to ${\tfrac {\partial \ln \left(x\right)}{\partial x}}={\tfrac {1}{x}}$. Thus, at $x=1$, the equation of the tangent line is $y=x-1$, as seen in Fig. 2. Since $\ln \left(x\right)$ is concave down, and for $x>0$, we get the following inequality:

$\ln \left(x\right)\leq x-1$

(15)

The equality occurs when $x=1$.

For two probability distributions, $P=\{p_{1},p_{2},\ldots ,p_{n}\}$ and $Q=\{q_{1},q_{2},\ldots ,q_{n}\}$, and using eq. 15, we get the Gibbs Inequality:

$\sum _{i=1}^{n}p_{i}\ln \left({\frac {q_{i}}{p_{i}}}\right)\leq \sum _{i=1}^{n}p_{i}\left({\frac {q_{i}}{p_{i}}}-1\right)=\sum _{i=1}^{n}\left(q_{i}-p_{i}\right)=\sum _{i=1}^{n}q_{i}-\sum _{i=1}^{n}p_{i}=0$

(16)

This time, the equality occurs when $p_{i}=q_{i}$ for all $i$. Though we derived the inequality for base $e$, it is straightforward to show that the inequality holds for any base.

Let's use the Gibbs Inequality to find the probability distribution that maximizes the entropy. For a probability distribution, $P=\{p_{1},p_{2},\ldots ,p_{n}\}$:

${\begin{aligned}H\left(P\right)-\log _{2}\left(n\right)&=\sum _{i=1}^{n}p_{i}\log _{2}\left({\frac {1}{p_{i}}}\right)-\log _{2}\left(n\right)\\&=\sum _{i=1}^{n}p_{i}\log _{2}\left({\frac {1}{p_{i}}}\right)-\log _{2}\left(n\right)\sum _{i=1}^{n}p_{i}\\&=\sum _{i=1}^{n}p_{i}\log _{2}\left({\frac {1}{p_{i}}}\right)-\sum _{i=1}^{n}p_{i}\log _{2}\left(n\right)\\&=\sum _{i=1}^{n}p_{i}\left(\log _{2}\left({\frac {1}{p_{i}}}\right)-\log _{2}\left(n\right)\right)\\&=\sum _{i=1}^{n}p_{i}\left(\log _{2}\left({\frac {1}{p_{i}}}\right)+\log _{2}\left({\frac {1}{n}}\right)\right)\\&=\sum _{i=1}^{n}p_{i}\log _{2}\left({\frac {\frac {1}{n}}{p_{i}}}\right)\\&\leq 0\\\end{aligned}}$

(17)

Since $\sum _{i=1}^{n}{\tfrac {1}{n}}=1$, we can use the Gibbs Inequality in obtaining the last step. Note that in this case, the equality occurs when $p_{i}={\tfrac {1}{n}}$.

We can then rewrite eq. 17 as:

$0\leq H\left(P\right)\leq \log _{2}\left(n\right)$

(18)

We can now look at the probability distributions at the upper and lower bounds of $H\left(P\right)$:

• At the lower bound, $H\left(P\right)=0$ when one of the $p_{i}$'s is equal to 1, and the rest are all zero.
• At the upper bound, $H\left(P\right)=\log _{2}\left(n\right)$ when $p_{i}={\tfrac {1}{n}}$ for all $i$.

Thus, the maximum of the entropy function is equal to $\log _{2}\left(n\right)$, where $n$ is the number of all possible events, and occurs when all the events are equally likely.

Example: Student Grades

How much information can we get from a single grade? Note that the maximum entropy occurs when all the grades have equal probability.

• For Pass/Fail grades, the possible outcomes are: $\{\mathrm {P} ,\mathrm {F} \}$ with probabilities $\{{\tfrac {1}{2}},{\tfrac {1}{2}}\}$. Thus,

$H\left(P\right)=\sum _{i=1}^{n}p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)={\frac {1}{2}}\cdot \log _{2}\left(2\right)+{\frac {1}{2}}\cdot \log _{2}\left(2\right)=1\,\mathrm {bit}$

(1)

• For grades = $\{1.00,2.00,3.00,4.00,5.00\}$ with probabilities $\{{\tfrac {1}{5}},{\tfrac {1}{5}},{\tfrac {1}{5}},{\tfrac {1}{5}},{\tfrac {1}{5}}\}$, we get:

$H\left(P\right)=\sum _{i=1}^{n}p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)=5\cdot {\frac {1}{5}}\cdot \log _{2}\left(5\right)=2.32\,\mathrm {bits}$

(2)

• For grades = $\{1.00,1.50,2.00,2.50,3.00,4.00,5.00\}$ with probabilities $\{{\tfrac {1}{7}},{\tfrac {1}{7}},{\tfrac {1}{7}},{\tfrac {1}{7}},{\tfrac {1}{7}},{\tfrac {1}{7}},{\tfrac {1}{7}}\}$, we have:

$H\left(P\right)=\sum _{i=1}^{n}p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)=7\cdot {\frac {1}{7}}\cdot \log _{2}\left(7\right)=2.81\,\mathrm {bits}$

(3)

• If we have all the possible grades $\{1.00,1.25,1.50,1.75,2.00,2.25,2.50,2.75,3.00,4.00,5.00,\mathrm {INC} ,\mathrm {DRP} ,\mathrm {LOA} \}$ with probabilities $\{{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}},{\tfrac {1}{14}}\}$, we have:

$H\left(P\right)=\sum _{i=1}^{n}p_{i}\cdot \log _{2}\left({\frac {1}{p_{i}}}\right)=14\cdot {\frac {1}{14}}\cdot \log _{2}\left(14\right)=3.81\,\mathrm {bits}$

(4)

Notes

1. These definitions of information and entropy might not be consistent with some other uses of the term. If a source transmits either the entire video of the Game of Thrones series, or the Lord of the Rings trilogy, and nothing else, then if we receive the entire Lord of the Rings trilogy, we get exactly one bit of information.
2. Our definition of information and entropy depend only on the probability distribution. In general, it will not make sense to talk about the information or entropy of a source without specifying the probability distribution. It is possible for two observers to have to different models of the source, thus associating two different probability distributions to the source. If this happens, then the two observers will assign different values of information and entropy associated with the source.

Activity A1.1 Who is Claude Shannon? -- This activity introduces Claude Shannon, and given this introduction to information theory, asks us to imagine how this can affect the computer engineering field.

Sources

• Tom Carter's notes on Information Theory