February 25, 2021

Dartboard Estimates

Throwing darts at a target may sound like a curiously haphazard way to solve a mathematical problem. Properly applied as a kind of intelligent guessing, however, it can become a highly effective technique for obtaining answers to certain problems in Ramsey theory (see "Playing Fields of Logic") and in other areas of mathematics.

Suppose that instead of the usual rings and diagonals, a dartboard features a target in the shape of a triangle inside a circle. If you were to throw darts at the board without aiming, the darts would land randomly within the circle and the triangle. By counting up the number of darts that land anywhere on the target and those that land only within the triangle, you can estimate the triangle's size relative to that of the circle.

For example, if 10 out of 100 randomly thrown darts fall inside the triangle, the triangle has approximately one-tenth the area of the circle.

For a dartboard consisting of a triangle inside a circle inside a square, the proportion of randomly thrown darts that land inside the triangle provides an estimate of the triangle's area relative to that of the square. You can also estimate the circle's area relative to that of the square or find an approximate value of π.

Such poorly played games of darts can provide remarkably good estimates of a variety of mathematical quantities, including π (pi), the ratio of the circumference of a circle to its diameter. Just make a target in which a circle of a given radius fits snugly inside a square with sides equal to twice the circle's radius.

The number of darts that hit the circle divided by the number that hit the square outside the circle provides an estimate of the value of π divided by four. The more inaccurate the aim and the larger the number of throws, the better the estimate becomes (see also "Buffon's Needling Ants" and "Targeting Pi").

Random choices can also play a prominent role in mathematical proofs. In 1947, Paul Erdős (1913-1996) used a probabilistic method to show, without actually determining the Ramsey number itself, that a given Ramsey number has to be greater than a certain value (see "Puzzling Groups and Ramsey Numbers").

The darts of Erdős's thought experiment were flips of a coin. In effect, he started with a room of mutual strangers, brought each of the pairs together, and introduced them only if a coin flip came up heads. The result was a random mixture of strangers and fresh acquaintances, linked in various ways.

By an ingenious chain of reasoning, Erdős then demonstrated that the probability of getting a party with a desired mix of strangers and acquaintances is practically certain beyond a particular size of group.

However, although Erdős could demonstrate the existence of the right kinds of patterns among the random pairings of his thought experiment, he could give no hint as to how to find such pairings or draw and color the relevant graphs and subgraphs to determine the Ramsey number.

Using mathematical recipes that involve the equivalent of coin flips has proved a useful strategy for solving a wide range of problems in mathematics, from testing whether a number is prime (evenly divisible only by itself and 1) to estimating such mathematical quantities as π.

Such randomized algorithms are also extremely useful in computer science for sorting data, recognizing patterns, generating images, and searching databases on a computer. In many cases, random choices or paths shorten the task at hand and help to avoid cases of computational gridlock.

The same thing can happen when two people walking in opposite directions along a sidewalk both step to the same side to avoid colliding, then do it again and again. They get trapped in an embarrassing dance until the stalemate is somehow finally broken.

A coin toss can solve the problem for both the inadvertent dancers and a computer that is engaged in resolving conflicting instructions or deciding which of two or more equally likely courses to take.

Probabilities also enter into Monte Carlo simulations for modeling the behavior of atoms in a gas and other physical systems (see also "Random Bits"). You can toss coins or throw dice to obtain answers for both mathematical and physical questions, and, with the help of a computer, this can sometimes be done surprisingly quickly and efficiently.

Ironically, Erdős himself never worked with a computer. His insights, however, suggested novel probabilistic methods of tackling tough problems well suited to the powerful, ubiquitous computers of today.

Next: Group Thoughts

No comments: