Probability and Computing: Randomized Algorithms and Probabilistic AnalysisRandomization 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 twosemester 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. 
What people are saying  Write a review
User ratings
5 stars 
 
4 stars 
 
3 stars 
 
2 stars 
 
1 star 

User Review  Flag as inappropriate
Excellent book. Lower level than Motwani Raghavan; so, good for raw beginners. Section on routing on butterfly network not clear to me. Other parts were fine.
Review: Probability and Computing: Randomized Algorithms and Probabilistic Analysis
User Review  GoodreadsThis book is an okay introduction to probabilistic algorithms. However, the problems sets are nighimpossible with out a strong background in probability (certainly nothing in the book helps in doing ... Read full review
Contents
II  1 
III  3 
IV  8 
V  12 
VI  14 
VII  20 
VIII  22 
IX  23 
LXXVIII  177 
LXXIX  182 
LXXX  188 
LXXXI  191 
LXXXII  193 
LXXXIII  194 
LXXXIV  196 
LXXXV  197 
X  25 
XI  26 
XII  30 
XIII  32 
XIV  34 
XV  38 
XVI  44 
XVII  45 
XVIII  48 
XX  50 
XXI  52 
XXII  53 
XXIII  54 
XXIV  57 
XXV  61 
XXVI  63 
XXVIII  67 
XXX  69 
XXXI  71 
XXXII  72 
XXXIII  73 
XXXIV  78 
XXXV  83 
XXXVI  90 
XXXVII  92 
XXXVIII  93 
XXXIX  94 
XL  98 
XLI  99 
XLII  104 
XLIII  106 
XLIV  107 
XLV  109 
XLVI  111 
XLVII  112 
XLVIII  113 
XLIX  119 
L  124 
LI  126 
LII  128 
LIII  129 
LIV  130 
LV  131 
LVI  133 
LVIII  134 
LX  135 
LXI  136 
LXII  138 
LXIII  141 
LXIV  142 
LXVI  143 
LXVII  146 
LXVIII  148 
LXIX  153 
LXX  156 
LXXI  159 
LXXII  163 
LXXIII  166 
LXXIV  167 
LXXV  173 
LXXVI  174 
LXXVII  176 
LXXXVI  199 
LXXXVII  201 
LXXXVIII  204 
LXXXIX  205 
XC  207 
XCI  210 
XCII  212 
XCIII  213 
XCIV  216 
XCVI  219 
XCVII  225 
XCVIII  228 
XCIX  230 
C  234 
CI  237 
CII  245 
CIII  252 
CIV  255 
CVI  257 
CVII  259 
CVIII  263 
CIX  265 
CX  267 
CXI  270 
CXII  271 
CXIII  274 
CXIV  275 
CXV  276 
CXVI  277 
CXVII  278 
CXVIII  281 
CXIX  282 
CXX  286 
CXXI  289 
CXXII  295 
CXXIII  297 
CXXIV  299 
CXXV  300 
CXXVI  303 
CXXVII  305 
CXXVIII  307 
CXXIX  308 
CXXXI  309 
CXXXII  314 
CXXXIII  315 
CXXXIV  316 
CXXXV  317 
CXXXVI  318 
CXXXVII  319 
CXXXVIII  321 
CXXXIX  323 
CXL  324 
CXLI  326 
CXLII  328 
CXLIII  333 
CXLIV  336 
CXLV  341 
CXLVI  344 
CXLVIII  345 
CL  349 
350  
Other editions  View all
Common terms and phrases
apply assume binomial bins Bloom filter chapter Chebyshev's inequality Chernoff bound choose chosen independently chosen uniformly clause codeword coin flips color compute consider constant coupling coupon decoding function Definition elements entropy event example Exercise expected number exponentially distributed fair coin finite geometric random variable given gives graph G Hamiltonian cycle hash functions heads Hence high probability independent sets independently and uniformly input integer Lemma linearity of expectations log2 Markov chain Markov's inequality martingale maximum load node number of balls number of bits number of steps obtain output packet pair pairwise independent path permutation phase player Poisson process polynomial Pr(X probability 1/2 problem Proof prove queue Quicksort random graph random walk randomized algorithm randomly routing sample space satisfying assignment sequence stationary distribution Suppose Theorem total number uniform uniformly at random unusededges list upper bound Var[X variation distance vertex vertices wins yields