Книга о вероятности

32

Несмотря на то, что я прошел несколько курсов по теории вероятностей, как в старшей школе, так и в университете, мне трудно читать документы TCS, когда речь идет о вероятности.

Кажется, что авторы работ TCS очень знакомы с вероятностью. Они волшебным образом работают с формулами вероятности и очень легко доказывают теоремы; в то время как я должен потратить несколько часов, чтобы понять, как получена одна формула и как доказываются тождества (или неравенства).

Я решил решить свою проблему раз и навсегда: хочу прочитать книгу от корки до корки.

Итак, если вас попросят предложить одну и только одну книгу по вероятности, какую книгу вы порекомендуете?

невероятно
источник
3
+1, потому что я был бы признателен за хорошую ссылку. Кроме того, могу ли я предположить, что такая книга должна охватывать байесовский вывод?
Стив
4
@ Неимоверно: Не могли бы вы уточнить больше? Книга вероятностей в целом или книга вероятностей, ориентированная на связь с теоретической информатикой?
Ёсио Окамото,
@Yoshio: я не ищу книгу, в которой объясняется вероятность в контексте TCS. Мне просто нужна книга, которую после прочтения обложки я могу узнать с вероятностью, чтобы чтение и демистификация документов TCS работали как очарование.
Невероятно
@Steve: Да, байесовский вывод ценится. Недавно я прочитал статью ( Нижние границы для нулевых знаний в Интернете ), в которой байесовский вывод использовался в основном, и я не мог легко расшифровать теоремы и леммы.
MS Dousti
1
почему это никогда не стало CW?
Суреш Венкат

Ответы:

22

Вы пробовали эти две книги?

  1. Вероятность и вычисления: рандомизированные алгоритмы и вероятностный анализ по Митценмахеру и Апфалу.
  2. Рандомизированные алгоритмы Мотвани и Рагхавана

Обратите внимание, что эти две книги охватывают гораздо больше, чем просто рандомизированные алгоритмы, например, они охватывают вероятностный метод, теорию цепей Маркова, мартингалы и т. Д., Конечно, со многими приложениями в TCS. Первая книга легче читается со многими примерами, доказательства которых были детально проработаны. Вторая книга действительно классическая, не очень обновленная, но все же очень полезная. У них обоих есть много упражнений, поэтому у вас будет много материала, чтобы практиковать то, что вы изучили.

Дай Ле
источник
12

Канонический учебник для студентов по теории вероятностей остается первым курсом по вероятности Шелдона Росса. Книга является отличным справочником / освежителем для всех остальных. Независимо от того, что утверждают несколько ворчливых интернет-обозревателей, в книге четко и с сильными мотивирующими примерами освещаются все наиболее важные темы с элементарной вероятностью.

Гек Беннетт
источник
11

Я думаю, что решением вашей проблемы является не чтение книги вероятностей, а чтение большего количества статей в 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.

Or Meir
источник
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.
M.S. Dousti
1
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/….
M.S. Dousti
9

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

Yonatan
источник
1
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
8

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.

M.S. Dousti
источник
6

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.

Mikhail Glushenkov
источник
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
4

A very good book :

Probability by Leo Breiman

Sylvain Peyronnet
источник
4
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!
M.S. Dousti
4

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.

Chad Brewbaker
источник
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.

Chris
источник
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.

Michael Chernick
источник