CS 237: Probability in Computing


 Warren Bennett
 3 years ago
 Views:
Transcription
1 CS 237: Probability in Computing Wayne Snyder Computer Science Department Boston University Lecture 5: o Independence reviewed; Bayes' Rule o Counting principles and combinatorics; o Counting considered as sampling and constructing outcomes; selection with and without replacement; o Counting sequences: Enumerations and Crossproducts; Permutations; KPermutations Permutations with Duplicates Circular Permutations
2 Conditional Probability and Independence: Review Recall: (Conditional Probability) We can think of this as conditioning the sample space: S S = B A B A B A B
3 Independence and Dependence: Review Recall: (Independent Events) We say that two events A and B are independent if or, equivalently, and most importantly as we go forward: Example: What is the probability of getting HHT when flipping three fair coins? P( HHT ) = P(H) * P(H) * P(T) = ½ * ½ * ½ = 1/8. Note: Independence does not depend on physical independence, but on the mathematical relationship. However, it may indicate a lack of causality.
4 Independence and Dependence: Review How does this relate to tree diagrams? P(A B) considers an event B followed by an event A, and how the occurence of B affects the occurence of A. What are the labels on a tree diagram of this random experiment? B occurs (or not) A occurs (or not) P( A B ) P( A B ) = P(A B) * P(B) P( B ) P( A c B ) = 1  P( A B ) P( A c B ) P( A c ) P( A B c ) P( A B c ) P( A c B c ) P( A c B c )
5 Independence and Dependence: Review When the events are independent, then we have the familiar tree diagram in which we simply write the probabilities of the events on each arc: B occurs (or not) A occurs (or not) P( A ) P( A B ) = P(A) * P(B) P( B ) P( A c ) = 1 P(A) P( A c B ) P( A c ) P( A ) P( A B c ) P( A c ) P( A c B c )
6 Bayes Rule We can rearrange the conditional probability rule in a way that makes the sequence of the events irrelevant  which happened first, A or B? Or did they happen at the same time? Does it matter? We can do a little algebra to define conditional probabilities in terms of each other: so:
7 Bayes Rule The best way to understand this is to view it with a tree diagram! P(B A) = the probability that when A happens, it was preceeded by B: If A has happened, what is the probability that it did so on the path where B also occurred? Note: A = P( A B ) P( A B c ) So what percentage of A is due to A B? Same calculation as:
8 Bayes Rule This has an interesting flavor, because we can ask about causes of outcomes: A Priori Reasoning  I randomly choose a person and observe that he is male; what the probability that it is a smoker? The first toss of a pair of dice is a 5; what is the probability that the total is greater than 8? A Posteriori Reasoning  I find a cigarette butt on the ground, what is the probability that it was left by a man? The total of a pair of thrown dice is greater than 8; what is the probability that the first toss was a 5? This seems odd, because instead of reasoning forward from causes to effects we are reasoning backwards from effects to causes but really it is just different ways of phrasing the mathematical formulae. Time is not really relevant!
9 Recall the rule for finite, equiprobable probability spaces: S A To work with this definition, we will need to calculate the number of elements in A and S and we will analyze this according to how we constructed the sample points in S and in A during the random experiment. Compare with how we construct the sample space using a tree diagram!
10 The way in which we construct the sample space almost always follows what we might characterize as a sampling process: set (unordered) sequence (ordered)
11 (A) There is a basis collection of N elements that are used to create an outcome. Examples: The number of dots showing on a rolled die; letters in the alphabet, people in a group, playing cards in a standard deck. (B) K elements are selected from this collection to construct an outcome. An important distinction is: Do we put the elements back before selecting the next? (yes = with replacement ; no = without replacement ). Examples: Roll a die twice, or row 2 dice and observe the dots showing on the face; choose 5 letters, choose people for a committee, deal a poker hand. (C) The elements are used to construct an outcome, generally a sequence (a collection with an ordering, with possible duplicates), a set (an unordered collection without duplicates), (also possibly a bag or multiset (unordered collection with duplicates). Example: Collect 5 selected cards into a poker hand; arrange the 5 letters to make a word.
12 (A) There is a basis collection of N elements that are used to create an outcome. Examples: The number of dots showing on a rolled die; letters in the alphabet, people in a group, playing cards in a standard deck. (B) K elements are selected from this collection to construct an outcome. An important distinction is: Do we put the elements back before selecting the next? (yes = with replacement ; no = without replacement ). Examples: Roll a die twice, or row 2 dice and observe the dots showing on the face; choose 5 letters, choose people for a committee, deal a poker hand. (C) The elements are used to construct an outcome, generally a sequence (a collection with an ordering, with possible duplicates), a set (an unordered collection without duplicates), (also possibly a bag or multiset (unordered collection with duplicates)). Example: Collect 5 selected cards into a poker hand; arrange the 5 letters to make a word.
13 The important issues to note are (and you probably want to figure them out in this order): (i) Is the outcome ordered or unordered? Does the outcome have duplicates or not? Examples: If the two numbers showing on the dice are 2 and 5, put them in sequence [2,5] (duplicates allowed); put the 5 letters into a word (a sequence); put the 5 cards into a hand (a set). Note: in the case of [2,5] you may speak of the "first roll" or the "second roll" but in { 2,5 } you may only make statements about the collection without specifying an order ("at least one of the rolls is 5"). Words are sequences, and hands in card games are sets; otherwise you need to use context or it will be clear from the problem statement. (ii) Is the selection done with or without replacement? Examples: Selecting 5 cards for a poker hand is done without replacement (you keep the cards and don't put them back in the deck); choosing a committee of 3 from a group of 10 people is without replacement; in many cases, as with balls in a sack, it is part of the problem statement. (iii) Does the basis collection have duplicates or not? Examples: The collection of letters in "MISSISSIPPI" has duplicates, but in "WORD" there are no duplicates; two red balls in a sack are indistinguishable by color.
14 We will organize this along the dimensions of o ordered vs unordered and o selection with replacement vs without. and we will consider the role of duplicates when appropriate. These problems have names you should be familiar with from CS 131: For each of these I will provide a canonical problem to illustrate; I STRONGLY recommend you memorize these problems and the solution formulae, and when you see a new problem, try to translate it into one of the canonical problems.
15 Enumerations The simplest situation is where we are constructing a sequence with replacement, such as where the basis objects are literally replaced, or consist of information such as symbols, which can be copied without eliminating the original. Canonical Problem: You have N letters to choose from; how many words of K letters are there? Formula: N K Example: How many 10letter words all in lower case? A more general version of this involves counting crossproducts: Generalized Enumerations: Suppose you have K sets S 1, S 2,..., S k. What is the size of the crossproduct S 1 x S 2 x... x S k? Solution: S 1 * S 2 *... * S k Example: Part numbers for widgets consist of 3 uppercase letters followed by 2 digits. How many possible part numbers are there? 26 * 26 * 26 * 10 * 10 = 1,757,600
16 Permutations Next in order of difficulty (and not yet very difficult) are permutations, where you are constructing a sequence, but without replacement. This explains what happens when the basis set is some physical collection which can not (like letters) simply be copied from one place to another. The most basis form of permutation is simply a rearrangement of a sequence into a different order. The number of such permutations of N objects is denoted P(N,N). Canonical Problem 1(a): Suppose you have N students S 1, S 2,..., S n. In how many ways can they ALL be arranged in a sequence in N chairs? Formula: P(N,N) = N* (N1) *... * 1 = N! Example: How many permutations of the word "COMPUTER are there? Answer: 8! = 40,320
17 KPermutations If we do not simply rearrange all N objects, but consider selecting K <= N of them, and arranging these K, we have a KPermutation indicated by P(N,K). Canonical Problem 1(b): Suppose you have N students S 1, S 2,..., S n. In how many ways can K of them be arranged in a sequence in K chairs? Formula: K terms Example: How many passwords of 8 lowercase letters and digits can be made, if you are not allowed to repeat a letter or a digit? Answer: The not allowed to repeat means essentially that you are doing this without replacement. So we have P(36,8) = 36! / 28! = 1,220,096,908,800. Note: The usual formula at the extreme right is extremely inefficient. The first formula is the most efficient, if not the shortest to write down!
18 Counting With and Without Order Before we discuss combinations, let us first consider the relationship between ordered sequences and unordered collections (sets or multisets) For example, consider a set A = { S, E, T } of 3 letters (all distinct). Obviously there is only such set. There are 3! = 6 different sequences of all these letters, but obviously if we can not distinguish the two O s, then not all these sequences are distinct: S E T S T E E S T E T S T S E T E S Set = unordered, no duplicates Multiset = unordered, maybe duplicates
19 The Unordering Principle If there are M ordered collections of N elements, then there are M/N! unordered collections of the same M elements. When all elements are distinct, as in our previous example, then obviously, M/N! = N!/N! = 1. The basic idea here is that we are correcting for the overcounting when we assumed that the ordering mattered. Therefore we divide by the number of permutations. This principle also applies to only a part of the collection: Example: Suppose we have 4 girls and 5 boys, and we want to arrange them in 9 chairs, but we do not care what order the girls are in. How many such arrangements are there? Answer: There 9! permutations, but if we do not care about the order of the (sub)collection of 4 girls, then there are 9!/4! = 15,120 such sequences.
20 Permutations with Repetitions As another example of the Unordering Principle, let us consider what happens if you want to form a permutation P(N,N), but the N objects are not all distinct. An example may clarify: Example: How many distinct (different looking) permutations of the word FOO are there? If we simply list all 3! = 6 permutations, we observe that because the O is duplicated, and we can not tell the difference between two occurrences of O s, there are really only 3 distinct permutations. This should be clear if we distinguish the two occurrences of O with subscripts: F O 1 O 2 FOO FOO F O 2 O 1 FOO O 1 F O 2 OFO OFO O 1 O 2 F OOF OOF O 2 F O 1 OFO O 2 O 1 F OOF Sequences: O 1 O 2 O 1 O 2 Multiset: { O, O } There are 2! sequences, so 6/2! = 6/2 = 3.
21 Permutations with Repetitions If you have N (nondistinct) elements, consisting of m (distinct) elements with multiplicities K 1, K 2,..., K m, that is, K 1 + K K m = N, then the number of distinct permutations of the N elements is Example: How many distinct (different looking) permutations of the word MISSISSIPPI are there? Solution: There are 11 letters, with multiplicities: M: 1 I: 4 S: 4 P: 2 Therefore the answer is
22 Circular Permutations A related idea is permutations of elements arranged in a circle. The issue here is that (by the physical arrangement in a circle) we do not care about the exact position of each elements, but only who is next to whom. Therefore, we have to correct for the overcounting by dividing by the number of possible rotations around the circle. Example: There are 6 guests to be seated at a circular table. How many arrangements of the guests are there? Hint: The idea here is that if everyone moved to the left one seat, the arrangement would be the same; it only matters who is sitting next to whom. So we must factor out the rotations. For N guests, there are N rotations of every permutation. Solution: There are 6! permutations of the guests, but for any permutation, there are 6 others in which the same guests sit next to the same people, just in different rotations. Formula: There are circular permutations of N distinct objects.
2. Combinatorics: the systematic study of counting. The Basic Principle of Counting (BPC)
2. Combinatorics: the systematic study of counting The Basic Principle of Counting (BPC) Suppose r experiments will be performed. The 1st has n 1 possible outcomes, for each of these outcomes there are
More informationThe study of probability is concerned with the likelihood of events occurring. Many situations can be analyzed using a simplified model of probability
The study of probability is concerned with the likelihood of events occurring Like combinatorics, the origins of probability theory can be traced back to the study of gambling games Still a popular branch
More informationPROBABILITY. 1. Introduction. Candidates should able to:
PROBABILITY Candidates should able to: evaluate probabilities in simple cases by means of enumeration of equiprobable elementary events (e.g for the total score when two fair dice are thrown), or by calculation
More informationNovember 6, Chapter 8: Probability: The Mathematics of Chance
Chapter 8: Probability: The Mathematics of Chance November 6, 2013 Last Time Crystallographic notation Groups Crystallographic notation The first symbol is always a p, which indicates that the pattern
More informationIf a regular sixsided die is rolled, the possible outcomes can be listed as {1, 2, 3, 4, 5, 6} there are 6 outcomes.
Section 11.1: The Counting Principle 1. Combinatorics is the study of counting the different outcomes of some task. For example If a coin is flipped, the side facing upward will be a head or a tail the
More informationThe next several lectures will be concerned with probability theory. We will aim to make sense of statements such as the following:
CS 70 Discrete Mathematics for CS Fall 2004 Rao Lecture 14 Introduction to Probability The next several lectures will be concerned with probability theory. We will aim to make sense of statements such
More informationSTAT 430/510 Probability Lecture 1: Counting1
STAT 430/510 Probability Lecture 1: Counting1 Pengyuan (Penelope) Wang May 22, 2011 Introduction In the early days, probability was associated with games of chance, such as gambling. Probability is describing
More informationINDEPENDENT AND DEPENDENT EVENTS UNIT 6: PROBABILITY DAY 2
INDEPENDENT AND DEPENDENT EVENTS UNIT 6: PROBABILITY DAY 2 WARM UP Students in a mathematics class pick a card from a standard deck of 52 cards, record the suit, and return the card to the deck. The results
More informationNovember 8, Chapter 8: Probability: The Mathematics of Chance
Chapter 8: Probability: The Mathematics of Chance November 8, 2013 Last Time Probability Models and Rules Discrete Probability Models Equally Likely Outcomes Crystallographic notation The first symbol
More informationDiscrete Structures for Computer Science
Discrete Structures for Computer Science William Garrison bill@cs.pitt.edu 6311 Sennott Square Lecture #23: Discrete Probability Based on materials developed by Dr. Adam Lee The study of probability is
More informationNovember 11, Chapter 8: Probability: The Mathematics of Chance
Chapter 8: Probability: The Mathematics of Chance November 11, 2013 Last Time Probability Models and Rules Discrete Probability Models Equally Likely Outcomes Probability Rules Probability Rules Rule 1.
More information3 The multiplication rule/miscellaneous counting problems
Practice for Exam 1 1 Axioms of probability, disjoint and independent events 1 Suppose P (A 0, P (B 05 (a If A and B are independent, what is P (A B? What is P (A B? (b If A and B are disjoint, what is
More informationMULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question.
Study Guide for Test III (MATH 1630) Name MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question. Find the number of subsets of the set. 1) {x x is an even
More informationChapter 5  Elementary Probability Theory
Chapter 5  Elementary Probability Theory Historical Background Much of the early work in probability concerned games and gambling. One of the first to apply probability to matters other than gambling
More informationSection The Multiplication Principle and Permutations
Section 2.1  The Multiplication Principle and Permutations Example 1: A yogurt shop has 4 flavors (chocolate, vanilla, strawberry, and blueberry) and three sizes (small, medium, and large). How many different
More informationI. WHAT IS PROBABILITY?
C HAPTER 3 PROAILITY Random Experiments I. WHAT IS PROAILITY? The weatherman on 10 o clock news program states that there is a 20% chance that it will snow tomorrow, a 65% chance that it will rain and
More informationSection : Combinations and Permutations
Section 11.111.2: Combinations and Permutations Diana Pell A construction crew has three members. A team of two must be chosen for a particular job. In how many ways can the team be chosen? How many words
More informationEECS 203 Spring 2016 Lecture 15 Page 1 of 6
EECS 203 Spring 2016 Lecture 15 Page 1 of 6 Counting We ve been working on counting for the last two lectures. We re going to continue on counting and probability for about 1.5 more lectures (including
More informationSection 6.1 #16. Question: What is the probability that a fivecard poker hand contains a flush, that is, five cards of the same suit?
Section 6.1 #16 What is the probability that a fivecard poker hand contains a flush, that is, five cards of the same suit? page 1 Section 6.1 #38 Two events E 1 and E 2 are called independent if p(e 1
More informationProbability: Terminology and Examples Spring January 1, / 22
Probability: Terminology and Examples 18.05 Spring 2014 January 1, 2017 1 / 22 Board Question Deck of 52 cards 13 ranks: 2, 3,..., 9, 10, J, Q, K, A 4 suits:,,,, Poker hands Consists of 5 cards A onepair
More information3 The multiplication rule/miscellaneous counting problems
Practice for Exam 1 1 Axioms of probability, disjoint and independent events 1. Suppose P (A) = 0.4, P (B) = 0.5. (a) If A and B are independent, what is P (A B)? What is P (A B)? (b) If A and B are disjoint,
More informationA Probability Work Sheet
A Probability Work Sheet October 19, 2006 Introduction: Rolling a Die Suppose Geoff is given a fair sixsided die, which he rolls. What are the chances he rolls a six? In order to solve this problem, we
More informationApplied Statistics I
Applied Statistics I Liang Zhang Department of Mathematics, University of Utah June 12, 2008 Liang Zhang (UofU) Applied Statistics I June 12, 2008 1 / 29 In Probability, our main focus is to determine
More informationElementary Combinatorics
184 DISCRETE MATHEMATICAL STRUCTURES 7 Elementary Combinatorics 7.1 INTRODUCTION Combinatorics deals with counting and enumeration of specified objects, patterns or designs. Techniques of counting are
More informationProbability and Counting Techniques
Probability and Counting Techniques Diana Pell (Multiplication Principle) Suppose that a task consists of t choices performed consecutively. Suppose that choice 1 can be performed in m 1 ways; for each
More informationDiscrete Random Variables Day 1
Discrete Random Variables Day 1 What is a Random Variable? Every probability problem is equivalent to drawing something from a bag (perhaps more than once) Like Flipping a coin 3 times is equivalent to
More informationMath 146 Statistics for the Health Sciences Additional Exercises on Chapter 3
Math 46 Statistics for the Health Sciences Additional Exercises on Chapter 3 Student Name: Find the indicated probability. ) If you flip a coin three times, the possible outcomes are HHH HHT HTH HTT THH
More informationSTAT 430/510 Probability
STAT 430/510 Probability Hui Nie Lecture 1 May 26th, 2009 Introduction Probability is the study of randomness and uncertainty. In the early days, probability was associated with games of chance, such as
More informationChapter 1. Probability
Chapter 1. Probability 1.1 Basic Concepts Scientific method a. For a given problem, we define measures that explains the problem well. b. Data is collected with observation and the measures are calculated.
More informationChapter 1. Probability
Chapter 1. Probability 1.1 Basic Concepts Scientific method a. For a given problem, we define measures that explains the problem well. b. Data is collected with observation and the measures are calculated.
More informationProbability (Devore Chapter Two)
Probability (Devore Chapter Two) 101635101 Probability Winter 20112012 Contents 1 Axiomatic Probability 2 1.1 Outcomes and Events............................... 2 1.2 Rules of Probability................................
More informationHonors Precalculus Chapter 9 Summary Basic Combinatorics
Honors Precalculus Chapter 9 Summary Basic Combinatorics A. Factorial: n! means 0! = Why? B. Counting principle: 1. How many different ways can a license plate be formed a) if 7 letters are used and each
More informationAxiomatic Probability
Axiomatic Probability The objective of probability is to assign to each event A a number P(A), called the probability of the event A, which will give a precise measure of the chance thtat A will occur.
More informationProbability. Ms. Weinstein Probability & Statistics
Probability Ms. Weinstein Probability & Statistics Definitions Sample Space The sample space, S, of a random phenomenon is the set of all possible outcomes. Event An event is a set of outcomes of a random
More informationChapter 2. Permutations and Combinations
2. Permutations and Combinations Chapter 2. Permutations and Combinations In this chapter, we define sets and count the objects in them. Example Let S be the set of students in this classroom today. Find
More informationCHAPTER 2 PROBABILITY. 2.1 Sample Space. 2.2 Events
CHAPTER 2 PROBABILITY 2.1 Sample Space A probability model consists of the sample space and the way to assign probabilities. Sample space & sample point The sample space S, is the set of all possible outcomes
More informationWEEK 7 REVIEW. Multiplication Principle (6.3) Combinations and Permutations (6.4) Experiments, Sample Spaces and Events (7.1)
WEEK 7 REVIEW Multiplication Principle (6.3) Combinations and Permutations (6.4) Experiments, Sample Spaces and Events (7.) Definition of Probability (7.2) WEEK 87.3, 7.4 and Test Review THE MULTIPLICATION
More informationWeek 3 Classical Probability, Part I
Week 3 Classical Probability, Part I Week 3 Objectives Proper understanding of common statistical practices such as confidence intervals and hypothesis testing requires some familiarity with probability
More informationSection Introduction to Sets
Section 1.1  Introduction to Sets Definition: A set is a welldefined collection of objects usually denoted by uppercase letters. Definition: The elements, or members, of a set are denoted by lowercase
More informationMAT104: Fundamentals of Mathematics II Counting Techniques Class Exercises Solutions
MAT104: Fundamentals of Mathematics II Counting Techniques Class Exercises Solutions 1. Appetizers: Salads: Entrées: Desserts: 2. Letters: (A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U,
More informationTheory of Probability  Brett Bernstein
Theory of Probability  Brett Bernstein Lecture 3 Finishing Basic Probability Review Exercises 1. Model flipping two fair coins using a sample space and a probability measure. Compute the probability of
More informationProbability. The MEnTe Program Math Enrichment through Technology. Title V East Los Angeles College
Probability The MEnTe Program Math Enrichment through Technology Title V East Los Angeles College 2003 East Los Angeles College. All rights reserved. Topics Introduction Empirical Probability Theoretical
More informationCompound Probability. Set Theory. Basic Definitions
Compound Probability Set Theory A probability measure P is a function that maps subsets of the state space Ω to numbers in the interval [0, 1]. In order to study these functions, we need to know some basic
More informationRANDOM EXPERIMENTS AND EVENTS
Random Experiments and Events 18 RANDOM EXPERIMENTS AND EVENTS In daytoday life we see that before commencement of a cricket match two captains go for a toss. Tossing of a coin is an activity and getting
More informationContents 2.1 Basic Concepts of Probability Methods of Assigning Probabilities Principle of Counting  Permutation and Combination 39
CHAPTER 2 PROBABILITY Contents 2.1 Basic Concepts of Probability 38 2.2 Probability of an Event 39 2.3 Methods of Assigning Probabilities 39 2.4 Principle of Counting  Permutation and Combination 39 2.5
More informationExam III Review Problems
c Kathryn Bollinger and Benjamin Aurispa, November 10, 2011 1 Exam III Review Problems Fall 2011 Note: Not every topic is covered in this review. Please also take a look at the previous WeekinReviews
More information7.4 Permutations and Combinations
7.4 Permutations and Combinations The multiplication principle discussed in the preceding section can be used to develop two additional counting devices that are extremely useful in more complicated counting
More informationProbability Theory. Mohamed I. Riffi. Islamic University of Gaza
Probability Theory Mohamed I. Riffi Islamic University of Gaza Table of contents 1. Chapter 1 Probability Properties of probability Counting techniques 1 Chapter 1 Probability Probability Theorem P(φ)
More informationCounting & Basic probabilities. Stat 430 Heike Hofmann
Counting & Basic probabilities Stat 430 Heike Hofmann 1 Outline Combinatorics (Counting rules) Conditional probability Bayes rule 2 Combinatorics 3 Summation Principle Alternative Choices Start n1 ways
More informationChapter 7. Intro to Counting
Chapter 7. Intro to Counting 7.7 Counting by complement 7.8 Permutations with repetitions 7.9 Counting multisets 7.10 Assignment problems: Balls in bins 7.11 Inclusionexclusion principle 7.12 Counting
More informationCSE 312: Foundations of Computing II Quiz Section #2: InclusionExclusion, Pigeonhole, Introduction to Probability (solutions)
CSE 31: Foundations of Computing II Quiz Section #: InclusionExclusion, Pigeonhole, Introduction to Probability (solutions) Review: Main Theorems and Concepts Binomial Theorem: x, y R, n N: (x + y) n
More informationWeek 1: Probability models and counting
Week 1: Probability models and counting Part 1: Probability model Probability theory is the mathematical toolbox to describe phenomena or experiments where randomness occur. To have a probability model
More informationLecture 2: Sum rule, partition method, difference method, bijection method, product rules
Lecture 2: Sum rule, partition method, difference method, bijection method, product rules References: Relevant parts of chapter 15 of the Math for CS book. Discrete Structures II (Summer 2018) Rutgers
More informationCombinatorics: The Fine Art of Counting
Combinatorics: The Fine Art of Counting Week 6 Lecture Notes Discrete Probability Note Binomial coefficients are written horizontally. The symbol ~ is used to mean approximately equal. Introduction and
More informationIntroduction to Counting and Probability
Randolph High School Math League 20132014 Page 1 If chance will have me king, why, chance may crown me. Shakespeare, Macbeth, Act I, Scene 3 1 Introduction Introduction to Counting and Probability Counting
More informationCombinatorics: The Fine Art of Counting
Combinatorics: The Fine Art of Counting Lecture Notes Counting 101 Note to improve the readability of these lecture notes, we will assume that multiplication takes precedence over division, i.e. A / B*C
More informationMATH 215 DISCRETE MATHEMATICS INSTRUCTOR: P. WENG
MATH DISCRETE MATHEMATICS INSTRUCTOR: P. WENG Counting and Probability Suggested Problems Basic Counting Skills, InclusionExclusion, and Complement. (a An office building contains 7 floors and has 7 offices
More informationName. Is the game fair or not? Prove your answer with math. If the game is fair, play it 36 times and record the results.
Homework 5.1C You must complete table. Use math to decide if the game is fair or not. If Period the game is not fair, change the point system to make it fair. Game 1 Circle one: Fair or Not 2 six sided
More informationCounting (Enumerative Combinatorics) X. Zhang, Fordham Univ.
Counting (Enumerative Combinatorics) X. Zhang, Fordham Univ. 1 Chance of winning?! What s the chances of winning New York Megamillion Jackpot!! just pick 5 numbers from 1 to 56, plus a mega ball number
More informationCHAPTER 8 Additional Probability Topics
CHAPTER 8 Additional Probability Topics 8.1. Conditional Probability Conditional probability arises in probability experiments when the person performing the experiment is given some extra information
More informationMultiple Choice Questions for Review
Review Questions Multiple Choice Questions for Review 1. Suppose there are 12 students, among whom are three students, M, B, C (a Math Major, a Biology Major, a Computer Science Major. We want to send
More informationProblem Set 2. Counting
Problem Set 2. Counting 1. (Blitzstein: 1, Q3 Fred is planning to go out to dinner each night of a certain week, Monday through Friday, with each dinner being at one of his favorite ten restaurants. i
More informationCS 361: Probability & Statistics
January 31, 2018 CS 361: Probability & Statistics Probability Probability theory Probability Reasoning about uncertain situations with formal models Allows us to compute probabilities Experiments will
More informationCIS 2033 Lecture 6, Spring 2017
CIS 2033 Lecture 6, Spring 2017 Instructor: David Dobor February 2, 2017 In this lecture, we introduce the basic principle of counting, use it to count subsets, permutations, combinations, and partitions,
More informationMAT104: Fundamentals of Mathematics II Summary of Counting Techniques and Probability. Preliminary Concepts, Formulas, and Terminology
MAT104: Fundamentals of Mathematics II Summary of Counting Techniques and Probability Preliminary Concepts, Formulas, and Terminology Meanings of Basic Arithmetic Operations in Mathematics Addition: Generally
More informationProbability. March 06, J. Boulton MDM 4U1. P(A) = n(a) n(s) Introductory Probability
Most people think they understand odds and probability. Do you? Decision 1: Pick a card Decision 2: Switch or don't Outcomes: Make a tree diagram Do you think you understand probability? Probability Write
More informationThe topic for the third and final major portion of the course is Probability. We will aim to make sense of statements such as the following:
CS 70 Discrete Mathematics for CS Spring 2006 Vazirani Lecture 17 Introduction to Probability The topic for the third and final major portion of the course is Probability. We will aim to make sense of
More informationProbability Rules. 2) The probability, P, of any event ranges from which of the following?
Name: WORKSHEET : Date: Answer the following questions. 1) Probability of event E occurring is... P(E) = Number of ways to get E/Total number of outcomes possible in S, the sample space....if. 2) The probability,
More informationMULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question.
Statistics Homework Ch 5 Name MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question. Provide an appropriate response. 1) A coin is tossed. Find the probability
More informationAlgebra II Chapter 12 Test Review
Sections: Counting Principle Permutations Combinations Probability Name Choose the letter of the term that best matches each statement or phrase. 1. An illustration used to show the total number of A.
More informationProbability MAT230. Fall Discrete Mathematics. MAT230 (Discrete Math) Probability Fall / 37
Probability MAT230 Discrete Mathematics Fall 2018 MAT230 (Discrete Math) Probability Fall 2018 1 / 37 Outline 1 Discrete Probability 2 Sum and Product Rules for Probability 3 Expected Value MAT230 (Discrete
More informationMat 344F challenge set #2 Solutions
Mat 344F challenge set #2 Solutions. Put two balls into box, one ball into box 2 and three balls into box 3. The remaining 4 balls can now be distributed in any way among the three remaining boxes. This
More informationThe Product Rule The Product Rule: A procedure can be broken down into a sequence of two tasks. There are n ways to do the first task and n
Chapter 5 Chapter Summary 5.1 The Basics of Counting 5.2 The Pigeonhole Principle 5.3 Permutations and Combinations 5.5 Generalized Permutations and Combinations Section 5.1 The Product Rule The Product
More information1. An office building contains 27 floors and has 37 offices on each floor. How many offices are in the building?
1. An office building contains 27 floors and has 37 offices on each floor. How many offices are in the building? 2. A particular brand of shirt comes in 12 colors, has a male version and a female version,
More informationCSC/MTH 231 Discrete Structures II Spring, Homework 5
CSC/MTH 231 Discrete Structures II Spring, 2010 Homework 5 Name 1. A six sided die D (with sides numbered 1, 2, 3, 4, 5, 6) is thrown once. a. What is the probability that a 3 is thrown? b. What is the
More informationChapter 4: Introduction to Probability
MTH 243 Chapter 4: Introduction to Probability Suppose that we found that one of our pieces of data was unusual. For example suppose our pack of M&M s only had 30 and that was 3.1 standard deviations below
More informationMathematical Foundations HW 5 By 11:59pm, 12 Dec, 2015
1 Probability Axioms Let A,B,C be three arbitrary events. Find the probability of exactly one of these events occuring. Sample space S: {ABC, AB, AC, BC, A, B, C, }, and S = 8. P(A or B or C) = 3 8. note:
More informationMath 227 Elementary Statistics. Bluman 5 th edition
Math 227 Elementary Statistics Bluman 5 th edition CHAPTER 4 Probability and Counting Rules 2 Objectives Determine sample spaces and find the probability of an event using classical probability or empirical
More informationBell Work. WarmUp Exercises. Two sixsided dice are rolled. Find the probability of each sum or 7
WarmUp Exercises Two sixsided dice are rolled. Find the probability of each sum. 1. 7 Bell Work 2. 5 or 7 3. You toss a coin 3 times. What is the probability of getting 3 heads? WarmUp Notes Exercises
More informationBlock 1  Sets and Basic Combinatorics. Main Topics in Block 1:
Block 1  Sets and Basic Combinatorics Main Topics in Block 1: A short revision of some set theory Sets and subsets. Venn diagrams to represent sets. Describing sets using rules of inclusion. Set operations.
More informationCISC 1400 Discrete Structures
CISC 1400 Discrete Structures Chapter 6 Counting CISC1400 Yanjun Li 1 1 New York Lottery New York Megamillion Jackpot Pick 5 numbers from 1 56, plus a mega ball number from 1 46, you could win biggest
More informationRaise your hand if you rode a bus within the past month. Record the number of raised hands.
166 CHAPTER 3 PROBABILITY TOPICS Raise your hand if you rode a bus within the past month. Record the number of raised hands. Raise your hand if you answered "yes" to BOTH of the first two questions. Record
More informationS = {(1, 1), (1, 2),, (6, 6)}
Part, MULTIPLE CHOICE, 5 Points Each An experiment consists of rolling a pair of dice and observing the uppermost faces. The sample space for this experiment consists of 6 outcomes listed as pairs of numbers:
More informationPermutations and Combinations. MATH 107: Finite Mathematics University of Louisville. March 3, 2014
Permutations and Combinations MATH 107: Finite Mathematics University of Louisville March 3, 2014 Multiplicative review Nonreplacement counting questions 2 / 15 Building strings without repetition A familiar
More informationMath 1313 Section 6.2 Definition of Probability
Math 1313 Section 6.2 Definition of Probability Probability is a measure of the likelihood that an event occurs. For example, if there is a 20% chance of rain tomorrow, that means that the probability
More informationIndependent Events. 1. Given that the second baby is a girl, what is the. e.g. 2 The probability of bearing a boy baby is 2
Independent Events 7. Introduction Consider the following examples e.g. E throw a die twice A first thrown is "" second thrown is "" o find P( A) Solution: Since the occurrence of Udoes not dependu on
More informationAlgebra 2 Notes Section 10.1: Apply the Counting Principle and Permutations
Algebra 2 Notes Section 10.1: Apply the Counting Principle and Permutations Objective(s): Vocabulary: I. Fundamental Counting Principle: Two Events: Three or more Events: II. Permutation: (top of p. 684)
More informationStat210 WorkSheet#2 Chapter#2
1. When rolling a die 5 times, the number of elements of the sample space equals.(ans.=7,776) 2. If an experiment consists of throwing a die and then drawing a letter at random from the English alphabet,
More informationDependence. Math Circle. October 15, 2016
Dependence Math Circle October 15, 2016 1 Warm up games 1. Flip a coin and take it if the side of coin facing the table is a head. Otherwise, you will need to pay one. Will you play the game? Why? 2. If
More informationSample Spaces, Events, Probability
Sample Spaces, Events, Probability CS 3130/ECE 3530: Probability and Statistics for Engineers August 28, 2014 Sets A set is a collection of unique objects. Sets A set is a collection of unique objects.
More informationProbability of Independent and Dependent Events. CCM2 Unit 6: Probability
Probability of Independent and Dependent Events CCM2 Unit 6: Probability Independent and Dependent Events Independent Events: two events are said to be independent when one event has no affect on the probability
More informationGrade 6 Math Circles Fall Oct 14/15 Probability
1 Faculty of Mathematics Waterloo, Ontario Centre for Education in Mathematics and Computing Grade 6 Math Circles Fall 2014  Oct 14/15 Probability Probability is the likelihood of an event occurring.
More informationCounting and Probability Math 2320
Counting and Probability Math 2320 For a finite set A, the number of elements of A is denoted by A. We have two important rules for counting. 1. Union rule: Let A and B be two finite sets. Then A B = A
More informationAdvanced Intermediate Algebra Chapter 12 Summary INTRO TO PROBABILITY
Advanced Intermediate Algebra Chapter 12 Summary INTRO TO PROBABILITY 1. Jack and Jill do not like washing dishes. They decide to use a random method to select whose turn it is. They put some red and blue
More information101. Combinations. Vocabulary. Lesson. Mental Math. able to compute the number of subsets of size r.
Chapter 10 Lesson 101 Combinations BIG IDEA With a set of n elements, it is often useful to be able to compute the number of subsets of size r Vocabulary combination number of combinations of n things
More information1. How to identify the sample space of a probability experiment and how to identify simple events
Statistics Chapter 3 Name: 3.1 Basic Concepts of Probability Learning objectives: 1. How to identify the sample space of a probability experiment and how to identify simple events 2. How to use the Fundamental
More informationProbability. Dr. Zhang Fordham Univ.
Probability! Dr. Zhang Fordham Univ. 1 Probability: outline Introduction! Experiment, event, sample space! Probability of events! Calculate Probability! Through counting! Sum rule and general sum rule!
More informationLecture 6 Probability
Lecture 6 Probability Example: When you toss a coin, there are only two possible outcomes, heads and tails. What if we toss a coin two times? Figure below shows the results of tossing a coin 5000 times
More informationCSE 312: Foundations of Computing II Quiz Section #2: InclusionExclusion, Pigeonhole, Introduction to Probability
CSE 312: Foundations of Computing II Quiz Section #2: InclusionExclusion, Pigeonhole, Introduction to Probability Review: Main Theorems and Concepts Binomial Theorem: Principle of InclusionExclusion
More informationCSC/MATA67 Tutorial, Week 12
CSC/MATA67 Tutorial, Week 12 November 23, 2017 1 More counting problems A class consists of 15 students of whom 5 are prefects. Q: How many committees of 8 can be formed if each consists of a) exactly
More information