Randomized Algorithms Probability

Question

I'm taking a grad level randomized algorithms course in the fall. The professor is known for being very detail oriented and mathematically rigorous, so I will be required to have an in-depth understanding of probability. What would be a good probability book to learn from that would be intuitive, but also have some mathematical rigor to it?

Answer 1

What textbooks does the course recommend? I like "Probability and Computing" by Mitzenmacher and Upfal and "Randomized Algorithms" by Motwani and Raghavan. They introduce the necessary theory from an algorithms viewpoint. I also recommend a book on inequalities, as bounding things is quite essential to the analysis of randomized algorithms. At the very least this cheat sheet.

Answer 2

You don't actually need a mathematically rigorous text on probability theory. I doubt that the professor will use $\sigma$-algebras and the like (unless they will mention martingales and will prefer to discuss them using these terms; no one would be able to follow). What you probably need is an understanding of probability theory, which you can only get by "playing" with it, for example in a course like that. If you have no background at all, just take an introductory text and work through some of the exercises.