Class Notes (834,991)
CSCA67H3 (56)
Lecture

# Weeks 9&10 - Probability.pdf

14 Pages
378 Views

Department
Computer Science
Course
CSCA67H3
Professor
Anna Bretscher
Semester
Fall

Description
History of Pascal’s Triangle Pascal was not the ﬁrst to discover the triangle of binomial coef- ﬁcients but was given credit because of how he related it to his work with probability and expectation. The triangle may have ﬁrst appeared more than 300 years earlier during the 11 century in China: 1 Distributing Objects Example. How many ways can 20 different diplomats be as- signed to 5 different continents? Solution. Rephrase the problem as an arrangement we already know. Q. What if each continent needs to have 4 diplomats each? A. Example. How many ways are there to distribute 20 identical chocolate bars and 15 identical sticks of gum to 5 children? Solution. 2 Example. How many integer solutions are there to the equation x + x + x + x = 12 with x ▯ 0? 1 2 3 4 i Solution. Q. What if we require that each x i 1? A. Theorem. The number of ways to distribute r identical objects into n distinct boxes with at least one object in each box is C(n▯ 1;r ▯ 1). Proof. We need to place n of the r objects amongst the n boxes leaving us with r ▯ n objects to distribute into the n boxes. 3 Q. How many ways can we do this? A. This formula generalizes nicely. Whenever we have restrictions on the number of items in a box, we can subtract those items from the total we are choosing from. Theorem. The number of ways to distribute r identical objects into n distinct boxes with at least r objects in the i box is i C((r ▯ r ▯1r ▯ 2:: ▯ r ) + n ▯ 1;n ▯ 1) Proof. Left as an exercise. 4 Example. How many arrangements are there with n 0s and m 1s and k runs of 0s. A run is the same digit occurring consecu- tively 1 or more times. 110010001110 has three runs of 0s. Solution. Let’s try to rephrase this as something we can solve. How? ▯ ▯ ▯ ▯ 5 Probability The deﬁnition we will use was ﬁrst deﬁned by the French mathematician Pierre-Simon Laplace. He is famous for his work in astronomy, statistics and physics: ▯ Laplace tranform, Laplace’s equation ▯ First to postulate the existence of black holes ▯ inductive reasoning based on proba- bility, today called Bayesian probability which plays a large role in artiﬁcial in- telligence. Deﬁnition. An experiment is a clearly deﬁned procedure that re- sults in one of a possible set of outcomes or elementary events. Deﬁnition. A sample(probability) space of a random experiment is a set S that includes all possible outcomes of the experiment. Example. If the experiment is to throw a standard die and record the outcome then: sample space S = 6 Deﬁnition. A compound event is a subset of S consisting of sev- eral elementary events. Q. Using the experiment of throwing a die, what is an example of a compound event? A. Deﬁnition. Let S be the sample space of an experiment and E be an event in S then Laplace’s deﬁnition of probability says that the probability of E is: prob (E) = jEj jSj Q. What is
More Less

Related notes for CSCA67H3
Me

OR

Join OneClass

Access over 10 million pages of study
documents for 1.3 million courses.

Join to view

OR

By registering, I agree to the Terms and Privacy Policies
Just a few more details

So we can recommend you notes for your school.