Probability Concepts and Axioms in Computing
Explore the fundamental concepts of probability in computing, including sample space, events, and the three probability axioms. Learn about mutually exclusive events, partition sets, discrete vs. continuous sample spaces, and the consequences of the probability axioms through illustrative examples.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Chapter 2 Probability on Events "Introduction to Probability for Computing", Harchol-Balter '24 1
Sample Space and Events Probability is defined in terms of some experiment. = Sample space of the experiment = Set of all possible outcomes Defn: An event, ?, is any subset of the sample space, . Example: Roll die twice Q: What does event ?1represent? Q: What is ?1 ?2 ? Q: What is ?1? Q: Are ?1 and ?2independent? (we ll see) "Introduction to Probability for Computing", Harchol-Balter '24 2
Sample Space and Events Defn: If ?1 ?2= , then ?1 and ?2 are mutually exclusive. Defn: If ?1,?2, ,??are events such that ?? ??= , ? ?, and such that ?=1 ??= ? then we say that events ?1,?2, ,?? partition set ?. ? Q: What is an example of events that partition for 2 rolls of a die? "Introduction to Probability for Computing", Harchol-Balter '24 3
Sample Space and Events Defn: A sample space is discrete if the number of outcomes is: __________________. A sample space is continuous if the number of outcomes is: __________________. uncountable countable Q: Which of these experiments have a discrete/continuous sample space? Roll a die 2 times Throw a dart at a unit interval. Flip a coin until we see the first head. Mark the time when the 100th email arrives. discrete continuous discrete continuous "Introduction to Probability for Computing", Harchol-Balter '24 4
Probability Defined on Events = probability of event ? = probability that the outcome of the experiment lies in set ? } ?{? The 3 Probability Axioms: Non-negativity: ?{?} 0 for any event ?. Additivity: If ?1,?2,?3, is a countable sequence of disjoint events, then ?{?1 ?2 ?3 } = ?{?1} + ?{?2} + ?{?3} + Normalization: ?{ } = 1 "Introduction to Probability for Computing", Harchol-Balter '24 5
Consequences of the 3 Probability Axioms Lemma 2.5: ?{? ?} =?{?} + ?{?} ?{? ?} Proof: (Hint: Think about Additivity Axiom) "Introduction to Probability for Computing", Harchol-Balter '24 6
Consequences of the 3 Probability Axioms Lemma 2.5: ?{? ?} =?{?} + ?{?} ?{? ?} Proof: Express ? ? as a union of mutually exclusive sets ? ? =? ? \ ? ? Then, by the Additivity Axiom we have 2 observations: ?{? ?} =? ? + ?{? \ ? ? } ?{?} =? ? \ ? ? + ? ? ? Now substitute the 2nd equation into the 1st . Lemma 2.6: ?{? ?} ?{?} + ?{?} Proof: WHY?? "Introduction to Probability for Computing", Harchol-Balter '24 7
Consequences of the 3 Probability Axioms Q: You throw a dart, equally likely to land anywhere in [0,1]. What is ?{Dart lands at 0.3}? (Argue using the Probability Axioms.) 1 0 0.3 "Introduction to Probability for Computing", Harchol-Balter '24 8
Conditional Probability on Events Defn: The conditional probability of event ? given event ? is ?{?|?} =?{? ?} ?{?} assuming ? ? > 0. Two equivalent views: 2 10 (of the 10 outcomes in set ?, only 2 of these are in set ?) ?{? | ? } = 2 42 10 42 ?{? ?} ?{?} 2 10 ?{? | ? } = = = "Introduction to Probability for Computing", Harchol-Balter '24 9
Conditional Probability on Events Defn: The conditional probability of event ? given event ? is ?{?|?} =?{? ?} ?{?} assuming ? ? > 0. Sandwich choices: Q: What is ?{Cheese | 2nd half of week} ? Argue this from 2 views. Mon Jelly Tues Cheese Wed Turkey Thur Cheese Fri Turkey Sat Cheese Sun None 1st half of week 2nd half of week "Introduction to Probability for Computing", Harchol-Balter '24 10
Conditional Probability on Events Defn: The conditional probability of event ? given event ? is ?{?|?} =?{? ?} ?{?} assuming ? ? > 0. Sandwich choices: Q: What is ?{Cheese | 2nd half of week} ? Argue this from 2 views. Mon Jelly Tues Cheese Wed Turkey Thur Cheese Fri Turkey Sat Cheese Sun None 1st half of week ?{Cheese | 2nd half } =2 (of the 4 days in 2nd half, 2 are cheese sandwiches) 4 2 7 4 7 2nd half of week ?{Cheese 2nd half} ?{2nd half} =2 ?{Cheese | 2nd half } = = 4 "Introduction to Probability for Computing", Harchol-Balter '24 11
Conditional Probability on Events Q: What is ?{both are colts | 1 colt} ? The offspring of a horse is called a foal. Horse couples have one foal at a time. Each foal is equally likely to be a colt or a filly. We re told that a horse couple had 2 foals, and at least one of these is a colt. "Introduction to Probability for Computing", Harchol-Balter '24 12
Conditional Probability on Events ?{both are colts | 1 colt} ?{both are colts & 1 colt} ?{ 1 colt} = ?{both are colts } ?{ 1 colt} The offspring of a horse is called a foal. Horse couples have one foal at a time. Each foal is equally likely to be a colt or a filly. = 1 4 3 4 = We re told that a horse couple had 2 foals, and at least one of these is a colt. 1 3 = "Introduction to Probability for Computing", Harchol-Balter '24 13
Conditional Probability on Events ?{both are colts | 1 colt} 1 3 = The offspring of a horse is called a foal. Horse couples have one foal at a time. Each foal is equally likely to be a colt or a filly. We re told that a horse couple had 2 foals, and at least one of these is a colt. "Introduction to Probability for Computing", Harchol-Balter '24 14
Conditional Probability on Events If ?{?1 ?2} > 0, then: ?{?2|?1} =?{?1 ?2} ?{?1} Equivalently, we can write: If ?{?1 ?2} > 0, then: ?{?1 ?2} = ?{?1} ?{?2|?1} ?{?1 ?2} = ?{?2} ?{?1|?2} Likewise: Probability outcome is in both ?1 and ?2 Probability outcome is in ?1 Probability outcome is in ?2 given that it s in ?1 "Introduction to Probability for Computing", Harchol-Balter '24 15
Chain Rule for Conditioning If ?{?1 ?2} > 0, then: If ?{?1 ?2} > 0, then: ?{?1 ?2} = ?{?1} ?{?2|?1} This can be generalized! Theorem 2.10: [Chain Rule for Conditioning] If ?{?1 ?2 ?3 ??} > 0, then ?{?1 ?2 ?3 ??} = ?{?1} ?{?2 ?1 ?{?3 ?1 ?2 ?{?? | ?1 ?2 ?3 ?? 1} "Introduction to Probability for Computing", Harchol-Balter '24 16
Independent Events Defn: Events ? and ? are independent, written ? ?, if: ?{? ?} = ?{?} ?{?} Here s an equivalent and more intuitive definition: Defn: Assuming ?{?} > 0 , Events ? and ? are independent, if: ?{? | ?} = ?{?} See the book for a proof of the equivalence. "Introduction to Probability for Computing", Harchol-Balter '24 17
Practice with Independent Events Defn: Events ? and ? are independent, written ? ?, if: ?{? ?} = ?{?} ?{?} Defn: Assuming ?{?} > 0 , Events ? and ? are independent, if: ?{? | ?} = ?{?} No! Q: Can two mutually exclusive, non-null events be independent? Q: Suppose we roll a die twice. Which of these pairs of events are independent: a. Let ?= 1stroll is 6. Let ? = 2ndroll is 6 b. Let ?= Sum of rolls is 7. Let ? = 2ndroll is 4 Both! "Introduction to Probability for Computing", Harchol-Balter '24 18
Practice with Independent Events You are routing a packet from the source to the destination. But each of the 16 edges in the network only works with probability ?. Q: What is the probability that you can get the packet from the source to the destination? "Introduction to Probability for Computing", Harchol-Balter '24 19
Practice with Independent Events Each edge works with probability ?. There are 8 paths. Let ?? denote the event that the ?? path is usable (not broken). Q: What is ? ??? Q: What is ? ??? Q: What is ? Can get from source to destination ? ? Can get from source to destination = ? At least one path works = ? ?1 ?2 ?8 = 1 ? All paths are broken = 1 ? ?1 ? ?2 ? ?8 = 1 1 ?2 8 "Introduction to Probability for Computing", Harchol-Balter '24 20
More Independence Definitions Defn 2.15: Events ?1,?2, ,??are independent if, for every subset ? of 1,2, ,? : ? ?? = ?{??} ? ? ? ? Defn 2.16: Events ?1,?2, ,??are pairwise independent if every pair of events is independent. Defn 2.17: Two events ? and ? are said to be conditionally independent given ?, where ?{?} > 0, if ?{? ? ? = ?{? ? ?{? ? "Introduction to Probability for Computing", Harchol-Balter '24 21
Law of Total Probability ? = ? ? (? ?) For any sets ? and ?: ? ? = ? ? ? + ? ? ? = ? ? | ? ?{?}+ ? ? | ? ? ? Generalizing, we have: Theorem 2.18: [Law of Total Probability] Let ?1,?2, ,?? partition the state space . Then: ? ? ?{?} = ?{? ??} = ?{?|??} ?{??} ?=1 ?=1 "Introduction to Probability for Computing", Harchol-Balter '24 22
Law of Total Probability The Law of Total Probability applies to conditional probability as well: Theorem 2.19: [Law of Total Probability for Conditional Probability] Let ?1,?2, ,?? partition the state space . Then: ? ? ? ?} = ?{? | ? ??} ? ?? ?} ?=1 "Introduction to Probability for Computing", Harchol-Balter '24 23
Bayes Law Sometimes we want to know ?{? | ?} but all we know is the reverse direction, ?{? | ?}. Theorem 2.20 : [Bayes Law] Assuming ? ? > 0 , ?{? | ?} =?{? ?} =?{? | F } ?{?} ?{?} ?{?} Theorem 2.21: [Extended Bayes Law] Let ?1,?2, ,??partition . Assuming ? ? > 0 , ?{? | ?} =?{? | ?} ?{?} ?{? | F } ?{?} ?=1 ?{? | ??} ?{??} = ? ?{?} "Introduction to Probability for Computing", Harchol-Balter '24 24
Bayes Law Example There s a rare child cancer that occurs in one out of a million kids. There s a test for this cancer that is 99.9% effective: Q: Suppose my child s test result is positive. How worried should I be? "Introduction to Probability for Computing", Harchol-Balter '24 25
Bayes Law Example Rare cancer occurs in 1 out of 106 kids. Test for this cancer is 99.9% effective: Q: My child s test result is positive. How worried should I be? ?{Cancer | Test Pos} ?{Test pos | Cancer} ?{Cancer} = ?{Test pos Cancer ? Cancer} + ?{Test pos No cancer} ?{No cancer} Why so low? 0.999 10 6 10 6 1 10 6+ 10 3= = 0.999 10 6+ 10 3 (1 10 6) 1001 "Introduction to Probability for Computing", Harchol-Balter '24 26
