Abstract

Discrete probability is not only interesting in itself but also essential for analysis of algorithms. In this short course, you will be introduced to some probability theory topics such as tail inequalities and martingales that are useful for computer science. Our starting point is the analysis of a simple algorithm for finding the maximum among n elements. Next some entertaining counterintuitive examples are mentioned like non-transitive dice, and games that if played longer do not favor the stronger. Several inequalities, including a recent one by Ross that is stronger than the second moment method, are stated. Finally, it is shown that one can apply martingale tail inequalities to Doob martingales to analyze problems like bin-packing.



Information: