37
$\begingroup$

While I have passed some courses on probability theory, both in the high school and the university, I have a hard time reading TCS papers when it comes to probability.

It seems that the authors of the TCS papers are very acquainted with probability. They magically work with probability formulas and prove theorems very easily; while I have to work some good hours to understand how one formula was derived, and how identities (or inequalities) are proved.

I decided to solve my problem once and for all: I want to read a book from cover to cover.

So, if you are asked to suggest one and only one book on probability, what book will you recommend?

Improve this question
$\endgroup$
8
  • 3
    $\begingroup$ +1 because I'd appreciate a good reference. Also, may I suggest that such a book would need to cover Bayesian inference? $\endgroup$
    – Steve
    Commented Apr 1, 2011 at 12:53
  • 4
    $\begingroup$ @Incredible: Would you clarify more? A probability book in general, or a probability book focusing on the connection to theoretical computer science? $\endgroup$
    – Yoshio Okamoto
    Commented Apr 1, 2011 at 13:04
  • $\begingroup$ @Yoshio: I don't seek a book in which probability in the context of TCS is explained. I just need a book which, after reading it cover to cover, I can get acquainted with probability so that reading and demystifying TCS papers work like a charm. $\endgroup$
    – Incredible
    Commented Apr 1, 2011 at 13:54
  • $\begingroup$ @Steve: Yeah, Bayesian inference is appreciated. I recently read a paper (Lower Bounds for Zero Knowledge on the Internet) in which Bayesian inference was used in an essential way, and I couldn't easily decrypt theorems and lemmas. $\endgroup$
    – Sadeq Dousti
    Commented Apr 1, 2011 at 13:59
  • 1
    $\begingroup$ how come this never became CW ? $\endgroup$
    – Suresh Venkat
    Commented Apr 11, 2011 at 16:54

14 Answers 14

Reset to default
25
$\begingroup$

Have you tried these two books?

  1. Probability and Computing: Randomized Algorithms and Probabilistic Analysis by Mitzenmacher and Upfal.
  2. Randomized Algorithms by Motwani and Raghavan

Note that these two books cover much more than just randomized algorithms, e.g. they cover Probabilistic Method, Markov Chain Theory, Martingales etc, of course with many applications in TCS. The first book is easier to read with many examples whose proofs were worked out in detail. The second book is really a classic, not very updated, but still very useful. They both have a lot of exercises, so you will have plenty of material to practice what you've learnt.

Improve this answer
$\endgroup$
13
$\begingroup$

The canonical undergraduate textbook for probability theory remains A First Course in Probability by Sheldon Ross. The book is an excellent reference/refresher for everyone else. Regardless of what a few grouchy internet reviewers claim, the book covers all of the most important topics in elementary probability clearly and with strong motivating examples.

Improve this answer
$\endgroup$
12
$\begingroup$

I think the solution to your problem is not reading a probability book, but reading more papers in TCS.

Most papers in TCS don't actually use very advanced probability tools. Most of them use a small collection of basic and well known probability tricks. The reason you have a hard time following them is that you are not yet familiar with this bag of tricks, and many of those papers don't bother to explain these tricks because they assume the reader knows them. Some of those tricks are not taught in most probability books, at least not in the specific form they are used in TCS papers.

Another reason is that TCS papers use a slightly different terminology than the one taught in basic probability courses - e.g., in TCS papers a random variable can usually take values in $\{0,1\}^n$, while usually in probability courses random variables are defined as taking real values.

So, by reading more TCS papers, you will get more familiar with the bag of common tricks and with the terminology, and and with time they will be easier to understand.

That said, reading a book on probability is always a good idea. Among the books suggested above, I am only familiar with "Probability and Computing: Randomized Algorithms and Probabilistic Analysis" of Mitzenmacher and Upfal, and it is a very good read - in particular, it will help you get familiar with the some of the terminology and tricks used in TCS.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Well said! I wish we could gather some items from this "bag of tricks," so as to help newcomers to the field. Maybe you can start a community wiki with one example. $\endgroup$
    – Sadeq Dousti
    Commented Jun 13, 2012 at 21:48
  • 1
    $\begingroup$ Regarding the random variables example: I remember 6 years ago, when I had this same question: Why TCS RVs aren't defined over reals? I searched and found the answer: There's more to RVs than we learn in elementary probability classes. Here's a link for those interested: en.wikipedia.org/wiki/…. $\endgroup$
    – Sadeq Dousti
    Commented Jun 13, 2012 at 21:53
10
$\begingroup$

Another classic of TCS/Combinatorics oriented probability is Alon and Spencer's The Probabilistic Method.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ This is a good recommendation. As Or Meir said in his answer, TCS uses a relatively limited bag of tricks from probability theory. Alon and Spencer's book focuses on this bag of tricks without getting bogged down in technical details from probability theory that are not so relevant to TCS. $\endgroup$
    – Timothy Chow
    Commented Jun 14, 2012 at 14:16
9
$\begingroup$

To add to Dai Le's answer, a more recent book by Dubhashi and Panconesi provides many examples of the use of probability in the analysis of algorithms.

Improve this answer
$\endgroup$
8
$\begingroup$

Several related topics on different SE websites:

  1. Book for probability
  2. Prerequisites on probability theory
  3. Supplementary reading for probability theory studies
  4. What book would you recommend for non-statisticians (mostly statistical books)

While I have not read any of these books, I had the luxury of taking a look at some of them. I liked the three-volume series by HPS (Hoel, Port, and Stone). It did not expect much background, and there was a clear distinction between the topics probability, statistics, and stochastic processes ( a separate volume is devoted to each topic). Moreover, each volume is rather short.

I must reemphasize that I'm not aware of the contents any of the listed books. I invite other members to comment on this post.

Improve this answer
$\endgroup$
6
$\begingroup$

Several posters in this discussion recommended Feller's two volume set. A more recent and also reportedly very good textbook is Grimmett and Stirzaker. Also, here's an interesting bibliography by a professional statistician.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I got Feller and Grimmet and Stirzaker. Together with the online MIT course "Fundamentals of Probability", it has proven a good gateway to concepts of probability you will need as an advanced senior/junior graduate student. $\endgroup$
    – chazisop
    Commented Jun 14, 2012 at 12:47
5
$\begingroup$

A very good book :

Probability by Leo Breiman

Improve this answer
$\endgroup$
1
  • 4
    $\begingroup$ The preface says: "A prerequisite is some knowledge of real variable theory, such as the ideas of measure, measurable functions, and so on. Roughly, the first seven chapters of Measure Theory by Paul Halmos is sufficient background...No prior knowledge of probability is assumed, but browsing through an elementary book such as the one by William Feller (Vol. I) ... gives an excellent feeling for the subject." This must be an advanced book! $\endgroup$
    – Sadeq Dousti
    Commented Apr 1, 2011 at 17:56
4
$\begingroup$

Concrete Mathematics by Knuth et al. Much of probability is figuring out the size of your universe, and from there figuring out which fraction of your universe you are interested in.

Improve this answer
$\endgroup$
4
$\begingroup$

An excellent introductory probability book for computer science people is Henk Tijms, Understanding Probability, Cambridge University Press, 2nd ed., 2007. This book distinguishes itself from other introductory probability texts by its emphasis on why probability works and how to apply it.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Of the books mentioned I agree on Brieman's "Probability", Sheldon Ross' book "A First Course in Probability" The book "Probability" by Hoel, Port and Stone from their three Volume series. Most of the other books I either don't know or don't think they are appropriate. Bayesian statistics is not part of probability theory. Kai Li Chung's "A Course in Probability Theory" is the one i learned out of along with volume II of Feller's book "An Introduction to Probability Theory and its Applications" are good books that I learned from. Feller is good for heuristics and interesting problems. Chung is good for the formal mathematics. Feller and Chung can be difficult to read though, especially for self-study. Another great writer of probability books is Sid Resnick. His book "A Probability Path" is delightful to read. Neveu's "Calculus of Probability" was another book that we used in my graduate probability course.

Improve this answer
$\endgroup$
2
$\begingroup$

A great book with EE slant: http://www.mhhe.com/engcs/electrical/papoulis/ a fantastic book with CS slant: http://www.amazon.com/dp/0471333417/.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I also like Papoulis, though I'm not sure it needed a 50% increase in bulk, or a new author, for a new edition. If you see an older edition (e.g. the reprint second edition that was published by Dell and sold in large quantities) going cheap, buy it. $\endgroup$
    – András Salamon
    Commented Apr 14, 2011 at 20:21
2
$\begingroup$

Just to add to the suggestions others have given, this note by Oded Goldreich is one of the most useful ones I've found so far. It gives a lot of examples of how probability is used in various branches Computer Science. The references at the end of the book are also definitely worth looking at.

Randomized Methods in Computation: Tentative Collection of Reading Materials

Improve this answer
$\endgroup$
1
$\begingroup$

This book is used for an intro probability class at MIT. http://vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf

Table of contents:

  • Sample Space and Probability
  • Discrete Random Variables
  • General Random Variables
  • Further Topics on Random Variables and Expectations
  • The Bernoulli and Poisson Processes
  • Markov Chains
  • Limit Theorems
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.