Quiz I Review Probabilistic Systems Analysis 6.041/6.431 Massachusetts Institute of Technology October 7, 2010 (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 1 / 26Quiz Information Closed-book with one double-sided 8.5 x 11 formula • sheet allowed • Content: Chapters 1-2, Lecture 1-7, Recitations 1-7, Psets 1-4, Tutorials 1-3 • Show your reasoning when possible! (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 2 / 26A Probabilistic Model: • Sample Space: The set of all possible outcomes of an experiment. • Probability Law: An assignment of a nonnegative number P(E) to each event E. Event AEvent BEventsA BSample Space Probability LawExperimentP(A)P(B)(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 3 / 26Probability Axioms Given a sample space Ω: 1. Nonnegativity: P(A) ≥ 0 for each event A 2. Additivity: If A and B are disjoint events, then P(A ∪ B) = P(A) + P(B) If A1, A2, . . . , is a sequence of disjoint events, P(A1 ∪ A2 ∪ · · · ) = P(A1) + P(A2) + · · · 3. Normalization P(Ω) = 1 (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 4 / 26Properties of Probability Laws Given events A, B and C : 1. If A ⊂ B, then P(A) ≤ P(B) 2. P(A ∪ B) = P(A) + P(B) − P(A ∩ B) 3. P(A ∪ B) ≤ P(A) + P(B) 4. P(A ∪ B ∪ C ) = P(A) + P(Ac ∩ B) + P(Ac ∩ Bc ∩ C ) (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 5 / 26Discrete Models • Discrete Probability Law: If Ω is finite, then each event A ⊆ Ω can be expressed as A = {s1, s2, . . . , sn} si ∈ Ω Therefore the probability of the event A is given as P(A) = P(s1) + P(s2) + + P(sn)· · · • Discrete Uniform Probability Law: If all outcomes are equally likely, P(A) = |A||Ω| (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 6 / 26Conditional Probability • Given an event B with P(B) > 0, the conditional probability of an event A ⊆ Ω is given as P(A|B) = P( P A ( ∩ B) B) • P(A B) is a valid probability law on Ω, satisfying 1. |P(A|B) ≥ 0 2. P(Ω B) = 1 3. P(A1|∪ A2 ∪ · · · |B) = P(A1|B) + P(A2|B) + · · · , where {Ai }i is a set of disjoint events • P(A|B) can also be viewed as a probability law on the restricted universe B. (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 7 / 26� � � � Multiplication Rule • Let A1, . . . , An be a set of events such that n−1 P Ai > 0. =1i∩Then the joint probability of all events is n n−1 P i∩=1 Ai = P(A1)P(A2|A1)P(A3|A1∩A2) · · · P(An| i∩ Ai )=1 P(A1)A1A3A1∩ A2∩ A3A2P(A2|A1)P(A3|A1∩ A2)(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 8 / 26� � Total Probability Theorem Let A1, . . . , An be disjoint events that partition Ω. If P(Ai ) > 0 for each i, then for any event B, n n P(B) = P(B ∩ Ai ) = P(B|Ai )P(Ai ) i=1 i=1 BA1A2A3A1A2A3BBBcBcBcBA1∩ BA2∩ BA3∩ B(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 9 / 26Bayes Rule Given a finite partition A1, . . . , An of Ω with P(Ai ) > 0, then for each event B with P(B) > 0 P(Ai |B) = P(B|Ai )P(Ai )= � ni P =1 (B|Ai | )P i (Ai ) Ai )P(B) P(B A )P( BA1A2A3A1A2A3BBBcBcBcBA1∩ BA2∩ BA3∩ B(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 10 / 26Independence of Events • Events A and B are independent if and only if P(A ∩ B) = P(A)P(B) or P(A B) = P(A) if P(B) > 0 | • Events A and B are conditionally independent given an event C if and only if P(A ∩ B|C ) = P(A|C )P(B|C ) or P(A|B ∩ C ) = P(A|C ) if P(B ∩ C ) > 0 • Independence � Conditional Independence. (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 11 / 26� � � � � Independence of a Set of Events • The events A1, . . . , An are pairwise independent if for each i = j P(Ai ∩ Aj ) = P(Ai )P(Aj ) • The events A1, . . . , An are independent if P Ai = P(Ai ) ∀ S ⊆ {1, 2, . . . , n}i∈S i∈S • Pairwise independence � independence, but independence pairwise independence. ⇒ (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 12 / 26Counting Techniques • Basic Counting Principle: For an m-stage process with ni choices at stage i, # Choices = n1n2 nm · · · • Permutations: k-length sequences drawn from n distinct items without replacement (order is important): # Sequences = n(n − 1) · · · (n − k + 1) = (n− n! k)! Combinations: Sets with k elements drawn from n• distinct items (order within sets is not important): � � # Sets = n = n! k k!(n−k)! (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 13 / 26� � � Counting Techniques-contd • Partitions: The number of ways to partition an n-element set into r disjoint subsets, with nk elements in the kth subset: � � � �� � � � n = n n − n1 n − n1 − · · · − nr − 1 n1, n2, . . . , nr n1 n2 · · · nr n ! = n1!n2!, , nr !· · · where n n ! = k k!(n − k)! r ni = n i=1 (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 14 / 26Discrete Random Variables A random variable is a real-valued function • defined on the sample space: X : Ω R→ • The notation {X = x} denotes an event: {X = x} = {ω ∈ Ω|X (ω) = x} ⊆ Ω • The probability mass function (PMF) for the random variable X assigns a probability to each event {X = x}: � � pX (x) = P({X = x}) = P {ω ∈ Ω|X (ω) = x} (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 15 / 26� � PMF Properties Let X be a random variable and S a countable • subset of the real line • The axioms of probability hold: 1. pX (x) ≥ 0 2. P(X ∈ S) = pX (x)� x∈S 3. x pX (x) = 1 • If g is a real-valued function, then Y = g (X ) is a random variable: ω X X (ω) g g(X (ω)) = Y (ω) → →with PMF pY (y) = PX (x) x g(x)=y| (Massachusetts Institute of Technology) Quiz I Review October 7, 2010 16 / 26� � � � Expectation Given a random variable X with PMF pX (x): • …
View Full Document