Probability and Computing

From MaRDI portal





The book presents an introduction to the ideas and techniques used in the development of randomized algorithms and the probabilistic analysis of algorithms. Randomized algorithms make use of (pseudo) random numbers, for example to make decisions in the execution of the algorithm or as basic ingredients such as in Monte Carlo methods. Complexity theory often deals with the worst-case analysis of algorithms, in particular their performance on pathological cases. However, the latter happen quite rarely in practice. Probabilistic analysis of algorithms is concerned with studying how algorithms perform in the majority of non-pathological cases. The appropriate language to formulate concepts and results is, obviously, probability theory. The book consists of 14 chapters, the first seven of which constitute core material for a one-semester course. The second seven chapters contain more advanced material either for a second course or as additional material in a more advanced course. Chapters 1 to 3 review basic notions of probability theory, such as events and probability, discrete random variables and expectation and moments and deviations. Together with these concepts, the first examples of randomized algorithms, such as a randomized min-cut algorithm are introduced. In Chapter 4 moment generating functions and Chernoff bounds are treated. As an application a randomized technique for packet routing in sparse networks is discussed and Chernoff bounds are used to analyse the performance of the algorithm on a hypercube and on a butterfly network. Chapter 5 is concerned with balls, bins and random graphs. The probabilistic method is presented and discussed in Chapter 6, together with several variations, such as the expectation argument, the second moment method and Lovász local lemma. Chapter 7 introduces Markov chains and random walks. Models of simple queues and Parrondo's paradox are also discussed. The second part of the book begins with Chapter 8, which introduces continuous distributions and the Poisson process, as well as continuous Markov processes and Markovian queues. Chapter 9 deals with entropy, randomness, and information and Chapter 10 with the Monte Carlo method. In Chapter 11 coupling of Markov chains is treated, as examples serve the shuffling of cards and random walks on a hypercube; as an application the approximate sampling of proper colourings of a graph is presented. Chapter 12 introduces martingales and, e.g., pattern matching serves as an application of the Azuma-Hoeffding inequality. The last two chapters are devoted to pairwise independence and universal hash functions, on the one hand, and balanced allocations on the other. Each chapter has a section with exercises, most of which are theoretical, some are programming exercises. The book is very well written and contains useful material on probability theory and its application in computer science.




Cited in
(only showing first 100 items - show all)








This page was built for publication: Probability and Computing

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5463630)