Methods in Algorithmic Analysis

Chapter 3

Probability

Projections, estimates, and predictions have become a common part of our life. A weather

forecast says that there is a 60% chance of rain tomorrow. A TV announcer tells us that gross

sales of American products will increase by 3% this year. A Gallup poll claims that 45%

of Am ericans are afraid to go out at night because of fear of crime. A health-news reporter

states that a smoker has a 72.33% higher chance of getting cancer than a non-smoker or a

tuba player. A college student asks an instructor about his chances of getting an A, though he

did not do well on the midterm exam. A system administrator has determined that there is 7%

chance of at least one of his operating systems crashing every month. An Internet provider

estimates that 0.031% of transferred data is corrupted . . . .

The 20th century has seen large improvements in productivity and the quality of manufac-

turing in industry in the Western world. Much of this success has been attributed to the use

of probabilistic and statistical methods. Probability theory is the fi eld of mathematics that

measures the likelihood of events. Anyone playing with dice or cards quickly develops some

intuitive grasp of probability. Such notions of probability and randomness are as old as civ-

ilization itself. Tomb inscriptions and other archaeological evidence reveal that as early as

3500 B.C. Egyptians were using astragalus (four-sided ankle bones of animals) as a primitive

prototype of playing dice. The earliest known six-sided dice are from ancient M esopotamia,

now northern Iraq, and date to approximately 2750 B.C.

An awakening of interest in the mathematics of gambling occurred during the mid-seventeenth

century. In the nineteenth century, probability was recognized as a useful tool in various ap-

plications in astronomy, physics, actuarial mathematics, genetics, and biology. At the Inter-

national Congress of Mathematicians held in Paris in 1900, David Hilbert presented a famous

list of problems. He claimed that their solutions would be essential for the further develop-

ment of m athematics. S ince that time, finding a solution of a Hilbert problem is considered

by many as important in mathematics as winning a Nobel prize in the natural sciences

1

. In

1933, Andrei N. Kolmogorov

2

from Moscow University solved Hilbert’s sixth problem: he

1

No Nobel prize is awarded in mathematics.

2

Andrei Nikolaevich Kolmogorov (1903–1987) was one of the most famous Russian mathematicians of the

20th century. He tragically lost both of his parents at a young age and he worked for a while as a conductor on

the railway after school graduation. A. Kolmogorov made a major contribution to the sixth Hilbert problem, and

he completely solved Hilbert’s Thirteenth Problem in 1957, when he showed that Hilbert was wrong in asking

79