Probability and Computing: Randomized Algorithms and Probabilistic AnalysisCambridge University Press, 31.01.2005 Randomization and probabilistic techniques play an important role in modern computer science, with applications ranging from combinatorial optimization and machine learning to communication networks and secure protocols. This 2005 textbook is designed to accompany a one- or two-semester course for advanced undergraduates or beginning graduate students in computer science and applied mathematics. It gives an excellent introduction to the probabilistic techniques and paradigms used in the development of probabilistic algorithms and analyses. It assumes only an elementary background in discrete mathematics and gives a rigorous yet accessible treatment of the material, with numerous examples and applications. The first half of the book covers core material, including random sampling, expectations, Markov's inequality, Chevyshev's inequality, Chernoff bounds, the probabilistic method and Markov chains. The second half covers more advanced topics such as continuous probability, applications of limited independence, entropy, Markov chain Monte Carlo methods and balanced allocations. With its comprehensive selection of topics, along with many examples and exercises, this book is an indispensable teaching tool. |
Inhalt
Preface | |
Discrete Random Variables and Expectation | |
Expected RunTime of Quicksort | |
Moments and Deviations 3 1 Markovs Inequality | |
Balls Bins and Random Graphs | |
Definitions and Representations | |
Continuous Distributions | |
Entropy Randomnessand Information | |
The Monte Carlo Method | |
Martingales | |
Chernoff Bounds | |
Pairwise Independence andUniversal Hash Functions | |
Häufige Begriffe und Wortgruppen
2universal family apply approximation assume atrandom ballsandbins bits Bloom filter Chernoff bound choose chosen independently chosen uniformly clause codeword coin flips color compute consider coupling customers Definition distribution with parameter edges elements equations example Exercise expected number exponentially distributed family of hash finite gives Hamiltonian cycle hash functions Hence high probability independent sets independently and uniformly induction input integer inthe Las Vegas algorithm least Lemma ln n/ln Markov chain martingale maximum load nodes number of balls number of bins numberof obtain ofthe output packet pair pairwise independent path permutation Poisson process polynomial Pr(X probabilistic probability 1/2 problem Proof prove queue random graph randomized algorithm randomly sample satisfying assignment sequence stationary distribution step sufficiently large Suppose thatthe Theorem transition uniform uniformly at random upper bound variation distance vertex vertices wins