DOC PREVIEW
MIT 6 041 - Probabilistic Systems Analysis

This preview shows page 1-2-3-25-26-27 out of 27 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 27 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

MIT 6 041 - Probabilistic Systems Analysis

Documents in this Course
Quiz 1

Quiz 1

5 pages

Quiz 2

Quiz 2

6 pages

Quiz 1

Quiz 1

11 pages

Quiz 2

Quiz 2

2 pages

Syllabus

Syllabus

11 pages

Quiz 2

Quiz 2

7 pages

Quiz 1

Quiz 1

6 pages

Quiz 1

Quiz 1

11 pages

Quiz 2

Quiz 2

13 pages

Quiz 1

Quiz 1

13 pages

Load more
Download Probabilistic Systems Analysis
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Probabilistic Systems Analysis and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Probabilistic Systems Analysis 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?