MY AMERICAN SCIENTIST
LOG IN! REGISTER!
SEARCH
 
RSS
Logo IMG
HOME > PAST ISSUE > March-April 2001 > Article Detail

COMPUTING SCIENCE

How to Count

Brian Hayes

Mental Arithmetic

A week or two after the November election, while the perils and pitfalls of counting were still the topic of every conversation, I received two fascinating papers by Peter R. Killeen and Thomas J. Taylor of Arizona State University, giving an analysis of errors in cascade counters. The papers make no mention of ballot counting. Their motivation comes from a quite different area: the question of how people and animals judge duration. One hypothesis holds that a mental or neuronal counter accumulates pulses from a pacemaker oscillator. Killeen (a psychologist) and Taylor (a mathematician) investigate the effect that errors in the counter would have on the accuracy of biological timers. Along the way they discover a great deal about fallible counters in general.

Killeen and Taylor summarize the operation of a cascade counter by means of a transition matrix, which gives the probability of every possible transition between states. For example, here is the transition matrix for a four-state (or two-bit) binary counter that operates without error:

Click to Enlarge Image

The first row indicates that if the current state of the counter is 00, the next state will be 01. The remaining rows show further transitions from 01 to 10, from 10 to 11, and finally (when the counter exceeds its capacity) from 11 back to 00. All other transitions have zero probability.

Now consider the corresponding matrix for a two-bit counter vulnerable to lost-pulse errors:

Click to Enlarge Image

Here p is the probability of a correct counting transition, and q is equal to 1–p, the probability of a signaling failure. All the entries on the main diagonal are q, since this is the probability that the initial input will fail to register, so that the state of the counter remains unchanged. The entries on the "superdiagonal"—corresponding to a correct transition—are equal to p or powers of p. The transition from 00 to 01 has probability p, but the 01-to-10 transition has probability p2, because two bits must change and two signals must be transmitted. Along the "subdiagonal," some entries are the product of p and q, since the transition requires one success and one failure.

The beauty of the matrix representation is that it can trace the evolution of the counter's state through many transitions. A single application of the matrix gives the probability distribution after one input event. To find the probabilities after two inputs, simply multiply the matrix by itself. More generally, the state of the counter after N inputs is specified by the Nth power of the matrix.

From a study of the matrix power series, Killeen and Taylor measure the decay of information in a fallible cascade counter. In the low-order bits of the counter, the correlation between N and R diminishes continually, approaching a limit where the bits are essentially random. But correlations persist in the high-order bits, as long as the capacity of the counter is not exceeded. In a totally random process, the distribution of R would become flat, and all entries in the matrix would be equal to 1/N. But a fallible counter maintains a delicate balance between order and randomness. The distribution of R is neither flat (as in a random-number generator) nor smoothly peaked (as in a unary counter); it is a curve with curious lumps and oscillations and a hint of self-similarity, or fractal structure. The hint becomes patent when Killeen and Taylor examine the spectrum of the transition matrix—the series of characteristic numbers known as eigenvalues. The spectrum yields a classic fractal object called a Julia set. Viewed in this light, counting correctly is a rather dull pastime, and so is counting at random; but just the right dash of error turns it into a thing of beauty.





» Post Comment

 

EMAIL TO A FRIEND :

Of Possible Interest

Perspective: Searching for Great Adventures

Computing Science: New Dilemmas for the Prisoner

Feature Article: Digital Forensics

Subscribe to American Scientist