Information

Contents

Maxwell's Demon

Information is a concept first used to resolve the paradox of Maxwell's demon. About 150 years ago, the physicist J. C. Maxwell came up with an intriguing idea. He conceived a thought experiment, in which a little demon who operates a friction-free trap door to separate molecules of one type from the other (see Figure 01), and finally arrives at a system with lower entropy. Such organizing entity of Maxwell's seems to violate the second law of thermodynamics as the demon only selects molecules but does no work. This paradox kept physicists in suspense for half a century until Leo Szilard showed that the demon's stunt really isn't free of charge. When he creates the precious commodity called information; it actually produces an amount of entropy (through mental processing* in the brain) exactly offsetting the decrement in the re-arrangement. The unit of this commodity is the bit, and each time the demon chooses a molecule to shuffle, he shells out one bit ("select" or "un-select") of information for this cognitive act, precisely balances the

Figure 01 Maxwell's Demon [view large image]

thermodynamics accounts. The new concept has since shown its useful-ness in communication and computer, but perhaps its greatest power lies in biology, for the organizing entities in living beings - the proteins and certain RNAs - are but Maxwell's demons.

Information and Non-equilibrium

The information content in a given sequence of units be they letters in a sentence, or nucleotides in DNA, depends on the minimum number of instructions needed to specify or describe the structure. Many instructions are needed to specify a complex, information-bearing structure such as DNA. Only a few instructions are need to specify an ordered structure such as a crystal. In this case we have a description of the initial sequence or unit arrangement which is then repeated ad infinitum according to the packing instructions (see Figure 02).

Figure 02 Crystal [view large image]

A system would be most probably in an equilibrium state (or maximum randomness) when leaves to its own devices as shown in Figure 03. In static configuration, it is the un-organized arrangement of books in library, for example. In thermodynamics, it is the distribution of particles in the most probable state (maximum entropy). In DNA, it is the random arrangement of the nucleotides. In atom/molecule, it is the ground state (lowest energy level) for the electrons/atoms.

Figure 03 Equilibrium [view large image]

Pre-requisites for Information:
• There should be rules or processes to arrange the system in a non-equilibrium state. The rules themselves are a form of stored information. They are similar to mathematical formulae but not as compact, more like a set of algorithm (a logical sequence of steps). Just like mathematical formulae, a small number of fixed rules can generate an un-predictable amount of complexity - resembling the endless varieties of movement described by the Newton's equation of motion.
  • In static configuration, it is the rules of cataloging in the library. External energy is required for the arrangement.
  • In thermodynamics, it is the external energy that re-arranges the system to a non-equilibrium state. The rule is prescribed by thermodynamics.
  • In DNA, it requires energy to arrange the codons (sequence of three nucleotides) for the production of a particular protein. The rule is provided by the genetic code.
  • In atom/molecule, it is again the external energy that excites the electron(s)/atom(s) to higher energy level. Quantum theory is the rule in the atomic domain.
• There should be a number of available states.
  • In static configuration, it is the space on the book shelf.
  • In thermodynamics, it is the distribution of particles in phase space (composed of position and velocity).
  • In DNA, it is the position in the helix.
  • In atom/molecule, it is the higher energy levels for the electrons or atoms.
• There is a mean (a way) to execute the rule/process.
  • In static configuration, a librarian is required to complete the task.
  • In thermodynamics, an electrical motor will usually do the trick.
  • In DNA, it relies on natural selection to acquire the viable codons.
  • In atom/molecule, it requires light energy to excite the atom/molecule to higher energy level.

  The resulting state is considered to be informational / useful, if it provides a way to locate the books in the static configuration example. it can produce refrigeration in a box, e.g, in the thermodynamics example. the gene benefits the living organism. the atoms can be excited to metastable state for the production of laser. Figure 04 shows the non-equilibrium states for the same examples as illustrated in Figure 03. The "information" defined in the above context is not universally accepted because of its

  Figure 04 Non-equilibrium [view large image]

  subjective connotations - many situations can be met only by an intelligent being or a living organism; and "usefulness" to some may be garbage to others.

  Figure 05 shows an example which should be very easy to understand. According to one definition of "information", the meaning of the messages is completely ignored but takes into account only the variations that is possible in the message. Thus the grammatical rules are more or less taken out of the equation. The image on the left portrays Bob as a dummy who can only utter Ba Ba Ba Ba to Alice. There is no variation in the message resulting in no "information content". On the other hand, the picture on the right shows

  Figure 05 Information Content [view large image]

  Bob to possess a wonderful command of vocabulary. Alice is surprise to hear the actual message out of so many possibilities. Therefore, this definition uses the "average amount of surprise" as its criterion. It doesn't take into account the "meaning" of the message.

  The series of lottery winning numbers provides one more example according to such definition of information, e.g., in Lotto 6/49 out of almost 50 million tickets sold, the odds is one in 13,983,816 or the information = -log₂(13983816) -24 (see formula in "Mathematical Formulation").

  [Top]

  ---

  Another Example

  Let us consider the example of finding a book in the library. If someone goes into a large library to borrow a copy of "War and Peace", it will take only a few minutes to find the book when the library is in a good state of order (as illustrated in Figure 04). The book will be on the fiction shelves and the author's name will appear in alphabetical order. In the catalogue, the book is given a unique decimal number. There is only one possible way in which "War and Peace" can be arranged in relation to all the other books. Indeed, there is only one possible way in which the contents of the entire library can be arranged. But then imagine a second library, in which by some quirk of the rules books are arranged on the shelves according

  to the color of their bindings (Figure 06). There may be a thousand red books grouped together in one section of the shelves. This arrangement contains a certain amount of order and conveys some information, but not as much as in the first library. Since there are no rules governing the ordering of books on the shelves by title and author within the red section, the number of possible ways of arranging the books there is much greater. If the borrower knows that "War and Peace" has a red binding, he will proceed to the right section, but then he will have to examine each book in turn until he chances upon the one he is looking for. Then imagine a third library, in which all the rules have broken down. The books are strewn at random on any shelf or on a desk (as the case in Figure 03). "War and Peace" could be anywhere in the building. There is no denying that the books are in a certain specific sequence, but the sequence is a "noise," not a message. It is only one of a truly immense number of possible ways of arranging the books, and there is no telling which one, because all are equally probable. A borrower's

  Figure 06 Imperfect Cataloging [view large image]

  ignorance of the actual arrangement is great in proportion to the quantity of these possible, equally probable ways.

  [Top]

  ---

  Mathematical Formulation

  To quantify the concept of information, let us consider a simple linear array, like the deck of eight cards (Figure 07). How much information would be needed to locate a particular member in such an array with a perfectly shuffled set? With the cards, the problem is like finding out in a binary guessing game when they are turned face down. Let's start, for example, with the Ace of Hearts. We are allowed in such a binary game to ask someone who knows where the Ace is a series of questions that can be answered "yes" or "no" - a game where the question "Is it this one?" is repeated as often as needed. Guessing randomly would eventually get us there; there are eight possibilities for drawing a first card. But, on the average, we would do better if we asked the question for successive subdivisions of the deck - first for subsets of four card, then

  of two, and finally of one. This way, we would hit upon the Ace in three steps, regardless where it happens to be. The "yes" or "no" are the constraints (the rules or procedures), which resolve more uncertainties with more questionings and in turn obtaining more information. Thus, 3 is the minimum number of correct binary choices or, by our definition above, the amount of information needed to locate a card in this particular arrangement. In effect, what we have been doing here is taking the binary logarithm of the number of possibilities (N=8), i.e., log2(8) = 3. In other words, the information required to determine the location in a deck of 8 cards is 3 bits. A bit is the smallest unit of information. It is one of the two distinct

  Figure 07 Information and Rules [view large image]

  alternatives, which can be any of the hot/cold, black/white, in/out, up/down, ... pairs. The number of possible alternatives N for a series of K trials is 2K. Using up/down for example with K=3 trials. There are N = 23 = 8 possible alternatives: (up, down, up), (up, down, down),

  (up, up, down), (up, up, up), (down, up, down), (down, up, up), (down, down, up), (down, down, down).
  
  For any number of possibilities (alternatives) N, the information I for specifying a member in a linear array (or specifying a particular combination among the many alternatives), is given by
  
  I = - log₂(N) = - K .
  
  I here has a negative sign for any N larger than 1, denoting that the information has to be acquired in order to make a correct choice. For the case where the N choices are subdivided into subsets/partitions ( i ) of uniform size (n_i), like the four suits in a complete deck of cards. Then the information needed to specify the membership in a partition is again given by
  
  I_i = log₂(n_i/N) = log₂(p_i)      where p_i = n_i/N is the probability of finding the member in the partition.
  
  Using the example in Figure 07 with N = 8, the different values of n_i/N and I_i associated with different partition size are shown in the table below:
  
          i          1     2      3       4
         n_i         8     4      2       1
        n_i/N      1     1/2    1/4    1/8
          I_i        0     -1     -2     -3
  
  

  For ni = 8, all the members are distributed randomly in one partition, finding the member there is certain but difficult without any information; while for ni = 1, the members are distributed orderly in eight equal size partitions, the chance of finding the member in each is 1/8 and 3 bits of information is required to find the member. In other words, a greater amount of uncertainty is resolved (more information) if the target chosen is one of a large number of possibilities and if it is one of the more unlikely of those possibilities as shown in Figure 08.

  Figure 08 Information and Probability [view large image]

  If the partitions are non-uniform in size, then the mean information is given by summing over all the partitions:
  
  I = (p_i) log₂(p_i)      ---------- (1).
  
  Thus, for N = 8;  n₁ = 2;  n₂ = 2;  n₃ =4;  I = (1/2)x(-1) + (1/2)x(-1) + (1/4)x(-2) = -3/2.
  
  The information I is referred to as logical entropy. It is the constraints (rules), which impose the order (creating the information) in the configuration. The process of re-arrangement will generate entropy (to the external environment via the mental or biological process as mention earlier) so that the second law of thermodynamic would not be violated.
  
  The measurement of disorder is called thermodynamic entropy: All systems tend to become more disorder with the progression of time. Energy is required to re-arrange the system back to a more orderly state - a non-equilibrium state. The Boltzmann equation expresses entropy as:
  
  S = -k(p_i) ln(p_i)      ---------- (2).
  
  where k = 1.38 x 10^-16 erg/K = 8.617 x 10^-5 ev/K is the Boltzmann's constant and p_i = e^-E_i/kT / e^-E_i/kT is the probability of finding the particle in state i, temperature T, energy E_i, and ln is logarithm with base e = 2.71828.
  
  Just as entropy is a measure of disorder, information is a measure of order. Any thing that is so thoroughly defined that it can be put together only in one or a few ways is perceived as orderly. Any thing that can be reproduced in thousands or millions of different but entirely equivalent ways is perceived as disorderly. Information thus becomes a concept equivalent to entropy, and any system can be described in terms of one or the other. An increase of entropy implies a decrease of information, and vice versa. A mathematical relationship can be obtained by equating Eq. (1) and (2):
  
  S = -(k ln2) I,       or     S + (k ln2) I = 0      ---------- (3).
  
  Numerically, 1 unit of information I = -1 equals to an entropy S 10^-16 erg/K, which is very small comparing to the entropy generated in raising 1 gram of water by 1^oC at room temperature (27^oC), i.e., S = 1.4x10^-8 erg/K.
  
  

  The entropy in Eq.(3) is related to the information either by the mental (or biological) process in creating the information or via the natural decay from order to disorder. The relationship between information and entropy can be illustrated by the evolution of puffs of smoke, e.g., in the smoke signal as shown in Figure 09. Initially, when the puffs have just been delivered, most of the smoke molecules are concentrated near a point (as shown by Box Diagram 1 for one puff). At that instant, the system has significant order and information as interpreted by certain codes for the signalling. With time, the smoke molecules spread through the space, distributing themselves more and more evenly; the system evolves toward more probable states, states of less order and less information (Box Diagrams 2-3). Finally, the distribution of the molecules is completely even (Box Diagram 4). The system then lacks a definable structure - its molecules merely move about at random; order and information have decayed to zero. This is the state of thermodynamic equilibrium. Thus, the molecular system loses its information with time. Eventually, all the information dissipate into entropy as related by the equation :

  Figure 09 Information and Entropy [view large image]

  S2 = -(k ln2) I1 (see Figure 09).

  [Top]

  ---

  Order / Disorder

  We have some intuitive notion of orderliness - we can often see at a glance whether a structure is orderly or disorderly - but this doesn't go beyond rather simple architectural or functional periodicities. That intuition breaks down as we deal with macromolecules, like DNA, RNA, or proteins. Considered individually, these are largely aperiodic structures, yet their specifications require immense amounts of information. In paradoxical contrast, a periodic structure - say, a synthetic stretch of DNA encoding nothing but prolines - may immediately strike us as orderly, though it contains a relatively modest amount of information (and is described by a simple algorithm).
  
  The degree of disorder of a given system can be gauged by the number of equivalent ways it can be constructed, and the entropy of the system is proportional to the logarithm of this number. When the number is 1, the entropy is zero
  (S = k ln(1) = 0). This doesn't happen very often; it is the case of a perfect crystal at absolute zero temperature. At that temperature there is then only one way of assembling the lattice structure with molecules that are all indistinguishable from one another. Thus, paradoxically, information is zero for a perfectly ordered crystal structure (I = log₂(1/1) = 0). As the crystal is warmed up, its entropy rises above zero. Its molecules vibrate in various ways about their equilibrium positions, and there are then several ways of assembling what is perceived as one and the same structure. The following two examples in Figure 10 illustrate the relationship between assembly (also known as arrangements or multiplicity) and entropy. In example a, there are eight distinguishable particles distributed in two boxes in different arrangements, which constitute the macrostates with different value of n (the number of particles within the box on the left). The microstates are the individual configurations within each macrostate. If the total number of configurations is denoted by , then it is related to the entropy S by the expression: S = k ln, where k is the Boltzmann's constant. Example b shows the multiplicity (Arrangements) of throwing a pair of distinguishable dice with the probability P of the outcome denoted by P = /(Total # of Microstates). The multiplicity for each macrostate is designated by (macrostate) in red.
  
  

  Figure 10 Entropy and Arrangements (Multiplicity)

  See "Entropy" for a more general definition.
  
  An orderly system tends to become more disorder with the progress of time. The sequence of pictures in Figure 11 illustrates the consequence when, the force (holding up the buildings) is removed by the implosion - it tends to disintegrate into rubble

  (greater disorder). This tendency toward greater disorder is prescribed by the second law ofthermodynamics and can be used to define the "arrow of time" since the sequence of events always flows one way to greater disorder. It is highly improbable for the reverse to happen naturally. Note that the second law of thermodynamics applies only to a closed system. For an open system, its orderliness can be boosted up at the expense of the surroundings (making it more disorder) with the infusion of energy.

  Figure 11 Arrow of Time [view large image]

  The time's arrow of thermodynamic events holds for living as well as nonliving matter. Living beings continuously lose information and would sink to thermodynamic equilibrium just as surely as nonliving systems do. There is only on way to keep a system from sinking to equilibrium: to infuse new information. Organisms manage to stay the sinking a little by linking their molecular building blocks with bonds that don't come easily apart. However, this only delays their decay, but doesn't stop it. No chemical bond can resist the continuous thermal jostling of molecules forever. Thus, to maintain its highly non-equilibrium state, an organism must continuously pump in information. The organism takes information from the environment and funnels it inside. By virtue of Eq. (3), this means that the environment must undergo an equivalent increase in thermodynamic entropy; for every bit of information the organism gains, the entropy in the external environment must rise by a corresponding amount.

  [Top]

  ---

  Complexity

  Complexity is a relatively new field in science, as such there is no unanimous in its definition. There are many different definitions as shown in Table 01; each has its own problem. A unified view will be universally accepted only when the field becomes mature.
  
  

  Complexity As	Definition	Example(s)	Problem
  Size	Larger size means higher complexity	Size of body or genome	Some simple organisms have larger genome size than human's
  Entropy	More variation signifies more complex message	HHH... has no variation and zero entropy, the random sequence DXW... has lot of variation	The most complex object is in between most orderly and complete randomness
  Algorithmic Content	Shorter computer program to describe the object corresponds to lesser complexity	HHH... requires very short description, garbled message cannot be compressed	Random object leads to high information content
  Logical Depth	Complexity is measured by how difficult to construct the object	HHH... is very easy to construct, while a specific message requires more work	It is difficult to measure the difficulty
  Fractal Dimension	Higher fractal dimension equals to higher complexity	The coastal line is more complex than a straight line	There are other kinds of complexity not defined by fractal dimension
  Degree of Hierarchy	Complexity is equated to the number of sub-systems	Organ to cells to organelles to macro-molecules to ...	It is difficult to separate the whole into parts

  Table 01 Definitions of Complexity

  Seth Lloyd has once listed 31 Measures of Complexity, the list has now grown to 42.
  
  

  A working definition is taken here from ordinary discourse, which states: "it is a state of intricacy, complication, variety, or involvement, as in the interconnected parts of a structure - a quality of having many interacting, different components". Quantitatively, complexity can be measured roughly in term of the number of components such as the number of parts in a machine, the number of cell types in living organism (see Figure 12), or the vocabulary in a language. It is believed that complexity is created in nature by fluctuations - random deviations from some average, equilibrium value of density, temperature, pressure, etc. - also called "instabilities" or "inhomogeneities". Normally, an open system near equilibrium

  Figure 12 Evolution to Greater Complexity [view large image]

  does not evolve spontaneously to new and interesting structures. But should those fluctuations become too great for the open system to damp, the system will then

  departs far from equilibrium and be forced to reorganize. Such reorganization generates a kind of "dynamic steady state" provided the energy flow rate exceeds the thermal relaxation rate. The feedback loops are positive in this kind of process. Complexity itself consequently creates the condition for greater instability, which in turn provides an opportunity for greater reordering. Another approach to view the development of complexity is through the concept of energy flow per unit mass. Figure 13(a) shows the increase of complexity as the energy flow (per unit mass) into the various systems increases over the age of the universe. Figure 13b depicts qualitatively the departure from equilibrium at each bifurcate point where the energy flow has reached a critical value and thus can promote more complexity in the system. The dotted curves indicate the options that have not been taken by the evolution. The bifurcation is created when the system enters a nonlinear mode beyond some energy threshold. Thus the development of complexity is a

  Figure 13 Complexity and Energy Flow [view large image]

  phenomenon closely related to the chaos theory or nonlinearity with a positive feedback loop.

  Table 02 below compares randomness, order, and complexity in the context of information.

  System	Structure	Alphabetical Arrangement	Natural System	Order	Information
  Randomness	random	HSIA TESHO SR I	molecules in the air	none	none
  Order	periodic	HHHHHHHHHHH	crystal	lot	none
  Complexity	aperiodic	HORSE THIS A IS	Nucleotides C, T, A, G	some	some
  Specified Complexity	aperiodic	THIS IS A HORSE	Viable genes to produce proteins	lot	lot

  Table 02 Information, Order, and Complexity

  The difference between randomness and complexity in Table 02 is that while both may look random to an untrained eye, effort has been spent and information has been created to arrange the sequence in complexity similar to the case of the Maxwell's demon. Only man-made and biological systems have evolved to the level of specific complexity, in which the units are arranged in such a way that the sequence is capable of performing a certain function. The examples for specified complexity in the table either conveys a message by following a set of grammatical rules or produces proteins according to the genetic codes. Order looks nice but is incapable of conveying a message or encrypting information.