Quiz I ReviewProbabilistic Systems Analysis6.041/6.431Massachusetts Institute of TechnologyOctober 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 formulasheet allowed•Date: Tuesday, October 12, 2010•Time: 7:30 - 9:00 PM•Location: 54-100•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 ofan experiment.•Probability Law: An assignment of a nonnegativenumber 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 AxiomsGiven a sample space Ω:1. Nonnegativity: P(A) ≥ 0 for each event A2. Additivity: If A and B are disjoint events, thenP(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 LawsGiven 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 eachevent A ⊆ Ω can be expressed asA = {s1, s2, . . . , sn} si∈ ΩTherefore the probability of the event A is given asP(A) = P(s1) + P(s2) + · · · + P(sn)•Discrete Uniform Probability Law: If alloutcomes 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 conditionalprobability of an event A ⊆ Ω is given asP(A|B) =P(A ∩ B)P(B)•P(A|B) is a valid probability law on Ω, satisfying1. P(A|B) ≥ 02. P(Ω|B) = 13. P(A1∪ A2∪ · · · |B) = P(A1|B) + P(A2|B) + · · · ,where {Ai}iis a set of disjoint events•P(A|B) can also be viewed as a probability law onthe restricted universe B.(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 7 / 26Multiplication Rule•Let A1, . . . , Anbe a set of events such thatPn−1∩i=1Ai> 0.Then the joint probability of all events isPn∩i=1Ai= P(A1)P(A2|A1)P(A3|A1∩A2) · · · P(An|n−1∩i=1Ai)P(A1)A1A3A1∩ A2∩ A3A2P(A2|A1)P(A3|A1∩ A2)(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 8 / 26Total Probability TheoremLet A1, . . . , Anbe disjoint events that partition Ω. IfP(Ai) > 0 for each i, then for any event B,P(B) =nXi=1P(B ∩ Ai) =nXi=1P(B|Ai)P(Ai)BA1A2A3A1A2A3BBBcBcBcBA1∩ BA2∩ BA3∩ B(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 9 / 26Bayes RuleGiven a finite partition A1, . . . , Anof Ω with P(Ai) > 0,then for each event B with P(B) > 0P(Ai|B) =P(B|Ai)P(Ai)P(B)=P(B|Ai)P(Ai)Pni=1P(B|Ai)P(Ai)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 ifP(A ∩ B) = P(A)P(B)orP(A|B) = P(A) if P(B) > 0•Events A and B are conditionally independentgiven an event C if and only ifP(A ∩ B|C ) = P(A|C )P(B|C )orP(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 / 26Independence of a Set of Events•The events A1, . . . , Anare pairwise independent iffor each i 6= jP(Ai∩ Aj) = P(Ai)P(Aj)•The events A1, . . . , Anare independent ifP \i∈SAi!=Yi∈SP(Ai) ∀ S ⊆ {1, 2, . . . , n}•Pairwise independence ; independence, butindependence ⇒ pairwise independence.(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 12 / 26Counting Techniques•Basic Counting Principle: For an m-stage processwith nichoices at stage i,# Choices = n1n2· · · nm•Permutations: k-length sequences drawn from ndistinct items without replacement (order isimportant):# Sequences = n(n − 1) · · · (n − k + 1) =n!(n−k)!•Combinations: Sets with k elements drawn from ndistinct items (order within sets is not important):# Sets =nk=n!k!(n−k)!(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 13 / 26Counting Techniques-contd•Partitions: The number of ways to partition an n-elementset into r disjoint subsets, with nkelements in the kthsubset:nn1, n2, . . . , nr=nn1n − n1n2· · ·n − n1− · · · − nr− 1nr=n !n1!n2!, · · · , nr!wherenk=n !k!(n − k)!rXi=1ni= n(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 14 / 26Discrete Random Variables•A random variable is a real-valued functiondefined on the sample space:X : Ω → R•The notation {X = x} denotes an event:{X = x} = {ω ∈ Ω|X (ω) = x} ⊆ Ω•The probability mass function (PMF) for therandom variable X assigns a probability to eachevent {X = x}:pX(x) = P({X = x}) = P{ω ∈ Ω|X (ω) = x}(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 15 / 26PMF Properties•Let X be a random variable and S a countablesubset of the real line•The axioms of probability hold:1. pX(x) ≥ 02. P(X ∈ S) =Px∈SpX(x)3.PxpX(x) = 1•If g is a real-valued function, then Y = g(X ) is arandom variable:ωX→ X (ω)g→ g(X (ω)) = Y (ω)with PMFpY(y) =Xx|g(x)=yPX(x)(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 16 / 26ExpectationGiven a random variable X with PMF pX(x):•E[X ] =PxxpX(x)•Given a derived random variable Y = g (X ):E[g(X )] =Xxg(x)pX(x) =XyypY(y) = E [Y ]E[Xn] =XxxnpX(x)•Linearity of Expectation: E[aX + b] = aE[X ] + b.(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 17 / 26VarianceThe expected value of a derived random variable g(X ) isE[g(X )] =Xxg(x)pX(x)The variance of X is calculated as•var(X ) = E[(X − E[X ])2] =Px(x − E[X ])2pX(x)•var(X ) = E[X2] − E[X ]2•var(aX + b) = a2var(X )Note that var(x) ≥ 0(Massachusetts Institute of Technology) Quiz I Review October 7, 2010 18 / 26Multiple Random VariablesLet X and Y denote random variables defined on asample space Ω.•The joint PMF of X and Y is denoted bypX
View Full Document
Unlocking...