Recommended readings for Probability theory applied to algorithms
I highly recommend Mitzenmacher and Upfal, Probability and Computing.

It has almost all the background needed for a beginning graduate student to start in probabilistic algorithms and analysis, and is clearly written, nice examples, etc.