ABSTRACT
This chapter presents the results on the intersection of probabilistic methods and graph searching games. It summarizes some notation from graph theory, and covers a few elementary but key theorems in discrete probability. The chapter introduces some basic definitions and theorems from discrete probability theory, and also presents a few elementary properties of a probability space. It mentions a generalization of Boole's inequality, known as Bonferroni's inequality. The chapter focuses on bounding from above the probability that a random variable is far away from the expectation. The well-known Central Limit Theorem suggests that the distribution of the sum of many independent random variables is approximately normal, and so the bounds we obtained earlier should not be far from the truth. This is actually the case under general circumstances. Two random variables are independent if and only if the events related to those random variables are independent events.
