Weeks 9&10 - Probability.pdf

14 Pages
Unlock Document

Computer Science
Anna Bretscher

History of Pascal’s Triangle Pascal was not the first to discover the triangle of binomial coef- ficients but was given credit because of how he related it to his work with probability and expectation. The triangle may have first 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 definition we will use was first defined 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 artificial in- telligence. Definition. An experiment is a clearly defined procedure that re- sults in one of a possible set of outcomes or elementary events. Definition. 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 Definition. 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. Definition. Let S be the sample space of an experiment and E be an event in S then Laplace’s definition of probability says that the probability of E is: prob (E) = jEj jSj Q. What is
More Less

Related notes for CSCA67H3

Log In


Join OneClass

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

Sign up

Join to view


By registering, I agree to the Terms and Privacy Policies
Already have an account?
Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.

Add your courses

Get notes from the top students in your class.