Information Theory

Welcome to yet another issue of “Intractable Problems”, a column designed to challenge and stimulate your thinking skills. In this issue we want to examine the nature and characteristics of information.

What is information, you may ask? This is a difficult question. I suppose that information is something that is useful, as opposed to noise, which is not. We do not define it any further. Given this thing called information, what do we know about it? Well, to quote Lord Kelvin, a physicist:

“When you can measure what you are speaking about, and express it in numbers, you know something about it; but when you cannot measure it, when you cannot express it in numbers, your knowledge is of a meager and unsatisfactory kind: it may be the beginning of knowledge, but you have scarcely in your thoughts advanced to the stage of science.

So, how do we measure information? Shannon, the father of information theory, measured information by calculating the entropy of an event, or the amount of surprise that an event gives. Consider that there is a box which every once in a while spits out a coloured ball. If the box has, over time, continually spit out black balls, then not much information is gained when the box spits out another black ball. But, if a white ball pops out unexpectedly then we can get quite excited! Lots of new information was gained. We can measure the amount of new information from the probability that something differed from the norm. This is entropy, which is a measure of how ordered things are.

Information theory is derived from an engineering definition based on probability[1]. It is not a definition based on meaning. This can be quite confusing to those of us who suspect that we can somehow extract meaning from data. Has anyone ever talked to you about knowledge systems, or knowledge engineering, or data mining?  Think about what these systems claim to do.  Ask how the systems define meaning and you might be surprised to find that the definition is based upon a  hand-waving argument and fluff.  Understanding meaning can be a very intractable problem.  Anyone who has ever tried to make sense out of the assembly instructions for a child’s toy can easily attest to this difficulty.

Entropy increases when things become more disordered. In physics, Boltzmann’s second law of thermodynamics says that the total amount of disorder in the universe increases with time. In other words, the entropy increases. If we associate Shannon’s information entropy with the physical concept of entropy, then we can predict that total information in the universe increases with time. Oh my goodness!  What would this mean?

Well, if at first someone doesn’t see things your way, then wait for a while and they may eventually see the light. Second, if things seem to go from bad to worse, perhaps it is because you now have more information and can understand the problem better. Third, if you truly have lots and lots of information, then you are probably a very disordered person.

Our misunderstanding about information has grown to the point where people now use terms such as “Executive Information Systems”. Obviously, to do our best as computer people, we want to provide systems that will give the most information with the least amount of effort.  But think, such systems will give the most information to executives only when events are completely and uniformly random, with each result coming as a complete surprise! Now, do you think that executives really want to be surprised every time they turn on their computer?

Next issue, I will present a challenging and exciting colouring problem for your pleasure. Start practicing with your crayons!


1. Hamming, R. Coding and Information Theory, Prentice Hall, 1980.