<p>Have you tried these two books? </p>

<ol>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521835402">Probability and Computing: Randomized Algorithms and Probabilistic Analysis</a> by  Mitzenmacher and Upfal.</li>
<li><a href="http://rads.stackoverflow.com/amzn/click/0521474655">Randomized Algorithms</a> by Motwani and Raghavan</li>
</ol>

<p>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.</p>

CC BY-SA 2.5
2011-04-02T00:15:52.373Z
2011-04-02T00:15:52.373Z
Dai Le
<p>The canonical undergraduate textbook for probability theory remains <a href="http://rads.stackoverflow.com/amzn/click/0130338516">A First Course in Probability</a> 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. </p>

CC BY-SA 2.5
2011-04-06T03:44:57.347Z
2011-04-06T03:44:57.347Z
Huck Bennett
<p>I think the solution to your problem is not reading a probability book, but reading more papers in TCS.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2012-06-13T21:48:37.933Z
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.
Sadeq Dousti
CC BY-SA 3.0
2012-06-13T21:53:01.563Z
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: http://en.wikipedia.org/wiki/Random_variable#Measure-theoretic_definition.
Sadeq Dousti
CC BY-SA 3.0
2012-06-13T09:37:51.537Z
2012-06-13T09:37:51.537Z
Or Meir
<p>To add to Dai Le's answer, <a href="http://rads.stackoverflow.com/amzn/click/0521884276">a more recent book by Dubhashi and Panconesi</a> provides many examples of the use of probability in the analysis of algorithms.</p>

CC BY-SA 3.0
2011-04-11T16:24:19.513Z
2011-04-11T16:24:19.513Z
RJK
<p>Several related topics on different SE websites:</p>

<ol>
<li><a href="https://mathoverflow.net/questions/20355/9544">Book for probability</a></li>
<li><a href="https://math.stackexchange.com/q/17388/2420">Prerequisites on probability theory</a></li>
<li><a href="https://math.stackexchange.com/q/5441/2420">Supplementary reading for probability theory studies</a></li>
<li><a href="https://stats.stackexchange.com/q/421">What book would you recommend for non-statisticians</a> (mostly statistical books)</li>
</ol>

<p>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.</p>

<p>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.</p>

CC BY-SA 2.5
2011-04-01T23:38:40.707Z
2011-04-01T23:38:40.707Z
2017-04-13T12:57:54.777Z
Sadeq Dousti
<p>Another classic of TCS/Combinatorics oriented probability is Alon and Spencer's <a href="http://rads.stackoverflow.com/amzn/click/0470170204">The Probabilistic Method</a>.</p>

CC BY-SA 3.0
2012-06-14T14:16:37.570Z
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.
Timothy Chow
CC BY-SA 3.0
2012-06-13T13:54:27.637Z
2012-06-13T13:54:27.637Z
Yonatan
<p>Several posters <a href="http://news.ycombinator.com/item?id=201913">in this discussion</a> recommended Feller's <a href="http://rads.stackoverflow.com/amzn/click/0471257087">two</a> <a href="http://rads.stackoverflow.com/amzn/click/0471257095">volume</a> set. A more recent and also reportedly very good textbook is <a href="http://rads.stackoverflow.com/amzn/click/0198572220">Grimmett and Stirzaker</a>. Also, <a href="http://cscs.umich.edu/~crshalizi/notebooks/probability.html">here's</a> an interesting bibliography by a professional statistician.</p>

CC BY-SA 3.0
2012-06-14T12:47:48.487Z
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.
chazisop
CC BY-SA 3.0
2011-04-07T09:11:39.967Z
2011-04-11T16:10:01.210Z
2011-04-11T16:10:01.210Z
Mikhail Glushenkov
<p>A very good book :</p>

<p><a href="http://rads.stackoverflow.com/amzn/click/0898712963" rel="noreferrer">Probability</a> by Leo Breiman</p>

CC BY-SA 2.5
2011-04-01T17:56:16.977Z
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!
Sadeq Dousti
CC BY-SA 2.5
2011-04-01T16:11:04.793Z
2011-04-01T16:11:04.793Z
Sylvain Peyronnet
<p><a href="http://rads.stackoverflow.com/amzn/click/0201558025" rel="nofollow">Concrete Mathematics</a> 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.</p>

CC BY-SA 2.5
2011-04-05T01:05:16.163Z
2011-04-05T01:05:16.163Z
Chad Brewbaker
<p>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.</p>

CC BY-SA 3.0
2011-05-22T17:57:56.753Z
2011-05-22T17:57:56.753Z
Chris
<p>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.</p>

CC BY-SA 3.0
2012-06-12T15:00:47.043Z
2012-06-12T19:46:26.613Z
2012-06-12T19:46:26.613Z
Michael R. Chernick
<p>Just to add to the suggestions others have given, this note by <a href="http://www.wisdom.weizmann.ac.il/~/oded/" rel="nofollow">Oded Goldreich</a> 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.</p>

<p><a href="http://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf" rel="nofollow">Randomized Methods in Computation: Tentative Collection of Reading Materials</a></p>

CC BY-SA 3.0
2014-03-17T16:13:44.123Z
2014-03-17T16:13:44.123Z
Obinna Okechukwu
<p>This book is used for an intro probability class at MIT. <a href="http://vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf" rel="nofollow">http://vfu.bg/en/e-Learning/Math--Bertsekas_Tsitsiklis_Introduction_to_probability.pdf</a></p>

<p>Table of contents:</p>

<ul>
<li>Sample Space and Probability</li>
<li>Discrete Random Variables</li>
<li>General Random Variables</li>
<li>Further Topics on Random Variables and Expectations</li>
<li>The Bernoulli and Poisson Processes</li>
<li>Markov Chains</li>
<li>Limit Theorems</li>
</ul>

CC BY-SA 3.0
2013-10-23T21:32:41.330Z
2013-10-23T21:32:41.330Z
sk8asd123
<p>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.</p>

<p>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.</p>

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

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

CC BY-SA 2.5
2011-04-01T12:53:55.557Z
+1 because I'd appreciate a good reference. Also, may I suggest that such a book would need to cover Bayesian inference?
Steve
CC BY-SA 2.5
2011-04-01T13:04:41.473Z
@Incredible: Would you clarify more?  A probability book in general, or a probability book focusing on the connection to theoretical computer science?
Yoshio Okamoto
CC BY-SA 2.5
2011-04-01T13:54:32.367Z
@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.
Incredible
CC BY-SA 2.5
2011-04-01T13:59:55.403Z
@Steve: Yeah, Bayesian inference is appreciated. I recently read a paper ([Lower Bounds for Zero Knowledge on the Internet](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1998.743499)) in which Bayesian inference was used in an essential way, and I couldn't easily decrypt theorems and lemmas.
Sadeq Dousti
CC BY-SA 3.0
2011-04-11T16:54:36.840Z
how come this never became CW ?
Suresh Venkat
CC BY-SA 3.0
2011-04-11T16:55:34.967Z
@Steve, @Sadeq, if you want to do probability for TCS, then you don't need Bayesian methods :). For ML, that's another story.
Suresh Venkat
CC BY-SA 3.0
2011-04-11T16:59:13.013Z
@Suresh... good point!
Steve
CC BY-SA 3.0
2011-04-13T12:07:08.223Z
Now it is CW (like other similar big-list questions).
Kaveh
<reference-request><big-list><pr.probability><books>
Book on Probability
Incredible
# Book on Probability

(Asked by: username_0 on 2011-04-01)

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?

**Tags:** reference-request, big-list, pr.probability, books
> **Comments:**
> **username_1**: +1 because I'd appreciate a good reference. Also, may I suggest that such a book would need to cover Bayesian inference?  
> **username_2**: @Incredible: Would you clarify more?  A probability book in general, or a probability book focusing on the connection to theoretical computer science?  
> **username_0**: @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.  
> **username_3**: @Steve: Yeah, Bayesian inference is appreciated. I recently read a paper ([Lower Bounds for Zero Knowledge on the Internet](http://www.computer.org/portal/web/csdl/doi/10.1109/SFCS.1998.743499)) in which Bayesian inference was used in an essential way, and I couldn't easily decrypt theorems and lemmas.  
> **username_4**: how come this never became CW ?  
> **username_4**: @Steve, @Sadeq, if you want to do probability for TCS, then you don't need Bayesian methods :). For ML, that's another story.  
> **username_1**: @Suresh... good point!  
> **username_5**: Now it is CW (like other similar big-list questions).  

---

## 13 answers

### Answer by username_6 on 2011-04-02. Score: 25

Have you tried these two books?

1. [Probability and Computing: Randomized Algorithms and Probabilistic Analysis](http://rads.stackoverflow.com/amzn/click/0521835402) by Mitzenmacher and Upfal.
2. [Randomized Algorithms](http://rads.stackoverflow.com/amzn/click/0521474655) 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.


---

### Answer by username_7 on 2011-04-06. Score: 13

The canonical undergraduate textbook for probability theory remains [A First Course in Probability](http://rads.stackoverflow.com/amzn/click/0130338516) 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.


---

### Answer by username_8 on 2012-06-13. Score: 12

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.

> **Comments:**
> **username_3**: 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.  
> **username_3**: 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: http://en.wikipedia.org/wiki/Random_variable#Measure-theoretic_definition.  

---

### Answer by username_10 on 2012-06-13. Score: 10

Another classic of TCS/Combinatorics oriented probability is Alon and Spencer's [The Probabilistic Method](http://rads.stackoverflow.com/amzn/click/0470170204).

> **Comments:**
> **username_11**: 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.  

---

### Answer by username_9 on 2011-04-11. Score: 9

To add to Dai Le's answer, [a more recent book by Dubhashi and Panconesi](http://rads.stackoverflow.com/amzn/click/0521884276) provides many examples of the use of probability in the analysis of algorithms.


---

### Answer by username_3 on 2011-04-01. Score: 8

Several related topics on different SE websites:

1. [Book for probability](https://mathoverflow.net/questions/20355/9544)
2. [Prerequisites on probability theory](https://math.stackexchange.com/q/17388/2420)
3. [Supplementary reading for probability theory studies](https://math.stackexchange.com/q/5441/2420)
4. [What book would you recommend for non-statisticians](https://stats.stackexchange.com/q/421) (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.


---

### Answer by username_12 on 2011-04-07. Score: 6

Several posters [in this discussion](http://news.ycombinator.com/item?id=201913) recommended Feller's [two](http://rads.stackoverflow.com/amzn/click/0471257087) [volume](http://rads.stackoverflow.com/amzn/click/0471257095) set. A more recent and also reportedly very good textbook is [Grimmett and Stirzaker](http://rads.stackoverflow.com/amzn/click/0198572220). Also, [here's](http://cscs.umich.edu/~crshalizi/notebooks/probability.html) an interesting bibliography by a professional statistician.

> **Comments:**
> **username_13**: 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.  

---

### Answer by username_14 on 2011-04-01. Score: 5

A very good book :

[Probability](http://rads.stackoverflow.com/amzn/click/0898712963) by Leo Breiman

> **Comments:**
> **username_3**: 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!  

---

### Answer by username_15 on 2011-04-05. Score: 4

[Concrete Mathematics](http://rads.stackoverflow.com/amzn/click/0201558025) 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.


---

### Answer by username_16 on 2011-05-22. Score: 4

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.


---

### Answer by username_17 on 2012-06-12. Score: 4

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.


---

### Answer by username_18 on 2014-03-17. Score: 2

Just to add to the suggestions others have given, this note by [Oded Goldreich](http://www.wisdom.weizmann.ac.il/~/oded/) 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](http://www.wisdom.weizmann.ac.il/~oded/PDF/rnd.pdf)


---

### Answer by username_19 on 2013-10-23. Score: 1

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


---

