Book contents
- Frontmatter
- Contents
- Preface
- 1 Events and Probability
- 2 Discrete Random Variables and Expectation
- 3 Moments and Deviations
- 4 Chernoff Bounds
- 5 Balls, Bins, and Random Graphs
- 6 The Probabilistic Method
- 7 Markov Chains and Random Walks
- 8 Continuous Distributions and the Poisson Process
- 9 Entropy, Randomness, and Information
- 10 The Monte Carlo Method
- 11 Coupling of Markov Chains
- 12 Martingales
- 13 Pairwise Independence and Universal Hash Functions
- 14 Balanced Allocations
- Further Reading
- Index
Preface
- Frontmatter
- Contents
- Preface
- 1 Events and Probability
- 2 Discrete Random Variables and Expectation
- 3 Moments and Deviations
- 4 Chernoff Bounds
- 5 Balls, Bins, and Random Graphs
- 6 The Probabilistic Method
- 7 Markov Chains and Random Walks
- 8 Continuous Distributions and the Poisson Process
- 9 Entropy, Randomness, and Information
- 10 The Monte Carlo Method
- 11 Coupling of Markov Chains
- 12 Martingales
- 13 Pairwise Independence and Universal Hash Functions
- 14 Balanced Allocations
- Further Reading
- Index
Summary
Why Randomness?
Why should computer scientists study and use randomness? Computers appear to behave far too unpredictably as it is! Adding randomness would seemingly be a disadvantage, adding further complications to the already challenging task of efficiently utilizing computers.
Science has learned in the last century to accept randomness as an essential component in modeling and analyzing nature. In physics, for example, Newton's laws led people to believe that the universe was a deterministic place; given a big enough calculator and the appropriate initial conditions, one could determine the location of planets years from now. The development of quantum theory suggests a rather different view; the universe still behaves according to laws, but the backbone of these laws is probabilistic. “God does not play dice with the universe” was Einstein's anecdotal objection to modern quantum mechanics. Nevertheless, the prevailing theory today for subparticle physics is based on random behavior and statistical laws, and randomness plays a significant role in almost every other field of science ranging from genetics and evolution in biology to modeling price fluctuations in a free-market economy.
Computer science is no exception. From the highly theoretical notion of probabilistic theorem proving to the very practical design of PC Ethernet cards, randomness and probabilistic methods play a key role in modern computer science. The last two decades have witnessed a tremendous growth in the use of probability theory in computing.
- Type
- Chapter
- Information
- Probability and ComputingRandomized Algorithms and Probabilistic Analysis, pp. xiii - xviPublisher: Cambridge University PressPrint publication year: 2005