Review of Basic Probability Theory

1 LECTURE 2. Review of Basic Probability Theory Probability SPACE AND AXIOMS. Probability Theory provides a set of mathematical rules to assign probabilities to outcomes of random experiments, , coin flips, packet arrivals, stock prices, neural spikes, noise voltages, and so on. Given a random experiment, its sample space is the set of all out- comes. An event is a subset of the sample space and we say that an event A occurs if the outcome of the random experiment is an element of A. Let F be a set of events. A. Probability measure P : F [0, 1] is a function that assigns probabilities to the events in F . We refer to the triple ( , F , P) as the Probability space of the random experiment.

2 The Probability measure P must satisfy the following. Axioms of Probability .. P(A) 0 for every event A in F .. P( ) = 1.. Countable additivity. If A 1 , A 2 , .. are disjoint, , A i A j = , i = j, then . P A i = P(A i ). i=1 i=1. For the Probability measure P to be well-defined over all events of interest, the set of events F must satisfy: . F .. If A F , then A c F .. If A 1 , A 2 , .. F , then i=1 A i F .. Due to these defining properties, F is often referred to as a -algebra or -field. 2 Review of Basic Probability Theory DISCRETE Probability SPACES. A Probability space ( , F , P) is said to be discrete if the sample space is countable, , finite or countably infinite.

3 Example . (Flipping a coin). = {H , T}, F = { , {H}, {T}, }, and P( ) = 0, P({H}) = p, P({T}) = 1 p, P( ) = 1, where p [0, 1] is the bias of the coin. A fair coin has a bias of 1/2. For discrete sample spaces, F is often the set of all subsets of , namely, the power set 2 of . (Recall that |2 | = 2| | .) In this case, the Probability measure P can be fully specified by assigning probabilities to individual outcomes (or singletons) { } so that P({ }) 0, , and P({ }) = 1.. Then it follows by the third axiom of Probability that for any event A , P(A) = P({ }). A. Example (Rolling a fair die). = {1, 2, 3, 4, 5, 6}, F = 2 = { , {1}, {2}, .. , }, and P({i}) = , i = 1, 2.

4 , 6. 1. 6. The Probability of the event A the outcome is even, , A = {2, 4, 6}, is P(A) = P({2}) + P({4}) + P({6}) = = . 3 1. 6 2. Example (Flipping a coin n times). A coin with bias p is flipped n times. Then = {H , T}n = {sequences of heads/tails of length n}, F = 2 , P({ }) = pi (1 p)n i , where i is the number of heads in . The Probability of the event A k the outcome consists of k heads and n k tails is n P(A k ) = P({ }) = pk (1 p)n k . : has k heads k We can verify that n n n P( ) = P(A k ) = pk (1 p)n k = 1. k=0 k=0. k Continuous Probability Spaces 3. Example (Flipping a coin until the first head). = {H , TH , T TH , T T TH , ..}, F = 2 , and P({ }) = (1 p)i p, where i is the number of tails in.

5 Again we can verify that . P( ) = P({ }) = (1 p)i p = 1. i=0. Example (Counting the number of packets). Consider the number of packets ar- riving at a node in a communication network in time interval (0, T] at rate (0, ). Then, = {0, 1, 2, 3, .. }, F = 2 , and ( T)k T. P({k}) = e , k = 0, 1, 2, .. , k! provided that the number of packets are Poisson distributed. Note that . ( T)k T. P( ) = e = 1. k=0. k! In all examples so far, F = 2 . This is not necessarily the case. Example .. (Rolling a colored die). Suppose that each face of a die is colored, say, . and are red, and through are blue. Further suppose that the observer of a die roll can only note the color of the face, not the actual number.)

6 Then = {1, 2, 3, 4, 5, 6} as before, but F = { , {1, 2}, {3, 4, 5, 6}, }. This is a valid -algebra (check!), but it is much smaller in size than the previous case and the Probability measure is fully specified by P({1, 2}) alone. As an extreme, if all six faces are of the same color, then we have the trivial -algebra F = { , }, which is still valid but hardly interesting. Thus, the choice of F controls the level of granularity at which one can assign probabilities. CONTINUOUS Probability SPACES. A continuous Probability space has an uncountable number of elements in . Unlike the discrete case, the choice of F = 2 , albeit valid, is too rich to admit an interesting prob- ability measure under the standard axioms of Probability .

7 At the same time, specifying probabilities to singletons is not sufficient to extrapolate probabilities for other events. Hence, F should be chosen more carefully, which is the main reason behind the intricate definitions of Probability measure and -algebra. Suppose that is a subinterval of the real line , for example, = [0, 1]. Then the 4 Review of Basic Probability Theory set of events is typically taken to contain all open subintervals of , , all intervals of the form (a, b), a, b . More formally, let F be the smallest -algebra that contains all open subintervals in . This -albegra is commonly referred to as the Borel -algebra B. and accordingly each event in B is called a Borel set.

8 Since B is a -algebra, it is closed under complement, countable unions, and countable intersections (cf. Problem . ), and contains many subsets other than open intervals. For example, since the half-open interval (a, b] can be represented by a countable intersection of open intervals (Borel sets) as (a, b] = (a, c), ( . ). c : c>b it is also Borel. As a matter of fact, B contains all open subsets and thus is the smallest -algebra that contains all open subsets of . The Probability of any Borel set can be fully specified by assigning probabilities to open intervals (or to closed intervals, half-closed intervals, half-intervals, etc.). Example . (Picking a random number between and ).))

9 = [0, 1], F = B, and P((a, b)) = b a, 0 < a < b < 1. This is the uniform distribution over . By ( . ) and the axioms of Probability , P((a, b]) = lim (c a) = b a, 0 < a < b < 1, c b It can be similarly checked that P([a, b]) = b a, 0 < a < b < 1. In particular, P({a}) = 0, a [0, 1], and the Probability of picking any specific number is zero. For any reasonable (such as a finite set or the d-dimensional Euclidean space d , but sometimes even a space of functions), the Borel -algebra can be defined as the smallest -algebra that contains all open subsets. When is countable, the Borel -algebra is 2 . Henceforth, we assume that F is the Borel -algebra of and any event of our interest is Borel unless specified otherwise.)

10 Note, however, that for an uncountable , there are many subsets of that are not Borel (if interested in these sets, refer to any graduate-level course on measure Theory ). Basic Probability LAWS. We can establish the following as simple corollaries of the axioms of Probability .. P(A c ) = 1 P(A). Conditional Probability and the Bayes Rule 5.. If A B, then P(A) P(B).. P(A B) = P(A) + P(B) P(A B).. P(A B) P(A) + P(B). More generally, we have the following inequality also known as Boole's inequality . that can be generalized to a countably infinite number of events. Union of events bound. For any events A 1 , A 2 , .. , A n , n n P A i P(A i ). i=1 i=1.