COMPUTING SCIENCE

# How to Count

# Peano Arithmetic

The simplest kind of counting is based on tally marks. Start with a blank sheet of paper. For each object to be counted, make a mark on the page. When you're finished, the number of marks should match the number of objects.

This kind of counting is surely ancient, but it was given a formal, axiomatic basis just a century ago by the Italian mathematician Giuseppe Peano. Peano's scheme of arithmetic begins by postulating the existence of the number zero, or 0. The next number is defined as the successor of zero, written *S*(0). Next comes the successor of the successor of zero, or *S*(*S*(0)), then *S*(*S*(*S*(0))), and so on. Continuing in this long-winded way, you can count as high as you please; it's just a matter of applying the same rule over and over.

Peano's axioms belong to the ideal world of Platonic mathematics—the same world where geometric points are dimensionless, circles are perfectly round, and lines run straight and true to infinity. In that empyrean realm, chad are never hanging, and every count is full, fair and accurate. But that's not the world we live and count in.

When considering the causes of counting errors, it's helpful to have in mind a specific counting machine. A Peano counter might be a box with a long row of light bulbs on the front panel. Events to be counted enter the machine via a single input port; the input could be a wire, and the events pulses of voltage. The light bulbs are the machine's output. Initially, all the bulbs are dark. Each time an event is recorded, a bulb turns on—and thereafter stays on forever—so that the number of lit bulbs represents the number of events counted.

Such a machine could have many modes of failure. For example, a bulb could burn out, or a fuse could blow. Here I shall focus on one specific type of error: the possibility that a count fails to register. That is, a pulse arrives at the input, but no bulb lights up in response; the input is ignored, and the state of the machine remains unchanged. Such lost counts are assumed to be random and uncorrelated accidents, so that the machine operates probabilistically. If the counter is in state *R* when a pulse arrives, it moves to the correct successor state *S*(*R*) with probability *p*, and it stays in state *R* with probability 1–*p*.

The basic mathematical properties of the probabilistic Peano counter are easy to describe. Because events can get lost but extra events are never introduced, the registered count *R* must always be less than or equal to the true count *N*. Also, the successive values of *R* must form a nondecreasing sequence: The counter can never run backwards. In any long series of counting trials, the mean value of *R* should be equal to *pN*. For example, with *p* = 0.75, a stream of 100 events will register 75 counts on the average. The extent to which individual results depart from the mean can also be measured statistically. The standard deviation of the distribution is proportional to the square root of *p*(1–*p*); thus the results are scattered most widely when *p* is 1/2, and the distribution gets narrower as *p* approaches either 0 or 1.

In a Peano counter with given values of *N* and *p*, you can easily gauge the probability of observing any value of *R*. However, predicting *R* when you know *N* is seldom what you want to do. More often, you are given *R* and you want to estimate *N*; that is, you know the tally announced by the county canvassing board, and you want to estimate how many votes were actually cast for each candidate. This inverse problem is subtler, especially when you don't know *p*. But if you can count the same set of objects many times, you can learn the shape of the distribution; then, the mean and the width yield an estimate of *N*.

**IN THIS SECTION**

EMAIL TO A FRIEND :

**Of Possible Interest**

**Perspective**: Searching for Great Adventures

**Computing Science**: New Dilemmas for the Prisoner

**Feature Article**: Digital Forensics