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.

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

For a discrete probability distribution $P=\{p_{1},p_{2},\ldots ,p_{n}\}$ the expected value of an associated discrete set $F=\{f_{1},f_{2},\ldots ,f_{n}\}$ is given by:

$\langle F\rangle =\sum _{i=1}^{n}f_{i}\cdot p_{i}$

(12)

Also, for a continuous probability distribution, $P\left(x\right)$, and an associated function $F\left(x\right)$:

$\langle F\left(x\right)\rangle =\int F\left(x\right)\cdot P\left(x\right)dx$

(13)

Hence, for $f_{i}=\log _{2}\left({\tfrac {1}{p_{i}}}\right)$, or $\log _{2}\left({\tfrac {1}{P\left(x\right)}}\right)$, we can see that:

$H\left(P\right)=\langle I\left(p\right)\rangle$

(14)

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

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 Gibb 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)

Sources

• Tom Carter's notes on Information Theory