COMP 61: Discrete Math
This page will contain all notes and links for the lectures on probability.
Week 12, Thursday, April 3
- Covered: Sample space, events, union and intersection of events, the birthday problem.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 6, sections 30, 31.
- Links
- wiki on poker probability.
- The birthday problem
- wiki.
Besides the sections on the basic problem, look at section 7.4 ("near matches"). This concerns our third bet.
Also note that section 7.6 deals with the average number of people you have to ask, to find a birthday match. It is a bit higher than 23. I will go over this next week.
- Number of particles in the universe (estimated)
- Someone asked me the following question after class:
If we record birthdays of people queried iteratively (say, on the street; we won't run out of people to ask), how many people do we expect to ask before recording all possible birthdays?
This is known as the
Coupon Collector's Problem. Here, we have n ``coupons". The answer is Theta(nlogn).
Week 13, Thursday, April 10
- Covered: Conditional probability
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 6, section 32.
- Links
- Monty Hall problem
- xkcd 1282 ... some people can win this game 100% of the time.
- BBC intro to the problem.
Includes an introductory video. Read the last 3 short paragraphs on diagnostic tests.
- Simulator. If you find a neater one, let me know.
- Another description, including video of a lecture, and an explanation of how the conditional probability formula can be misused.
- Blinky Monty.
A variation of the game, involving some prior knowledge.
- A research paper on an extension of the game:
many doors and many offers to switch.
Week 14, Thursday, April 17
- Covered: Bayes theorem, random variables, expectation.
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Scheinerman: chapter 6, section 33, 34.
- Links
- Bayes theorem
- TED talk about coins,
diagnosing diseases, and statistics in court cases.
- Law of total probability
- For indicator random variables, see the links below. Some of them will be covered in the next (half) class on probability.
Week 15, Thursday, April 24 (please see the graphs page as well, for this day).
- Covered: Three examples of using indicator random variables (I.R.V.)
- Class notes (see full notes if you want to practice step-by-step; otherwise see condensed)
- Textbook sources
- Links (roughly in order of increasing difficulty; in class we discussed problems 1, 2 and 5)
- 1) The hat check problem.
-
Link
1 uses IRVs for an expected value calculation.
Jump to page 8.
- Secondary links (not involving IRVs):
Link 2 and
link 3 calculate the probability
of an outcome for this problem.
- 2) The hiring problem.
- See this link.
Note that the second problem in this link, involving birthdays, is dealt with separately below.
- Harmonic series (related to the hiring problem).
- 3) Finding local maxima in permutations.
- Jump to the 30:00 mark in this youtube video,
which is part of Harvard's
Stat 110 course. This part of the lecture lasts 9 minutes.
After that is an explanation of the St. Petersburg paradox which is fun to think about.
Here's the wiki on that.
- 4) Counting inversions in permutations. (involves IRVs with 2 subscripts)
- Look at problem 2 in this
homework set
from a course at WVU. This follows the hat check problem. Problem 3 is not related to IRVs, but is interesting.
- 5) A birthday problem. (involves IRVs with 2 subscripts)
- The 2nd example in this
link
is a variant of our good old birthday problem. I discuss this and one more variant
here.
- 6) A problem with balls and bins.
- See the second example in this link.
Evaluation of the expected value of each IRV is a bit more complicated in this example than in previous ones.
Note that the first example in this link is equivalent to the hat check problem. It deals with fixed points in permutations.
In a permutation of the integers 1...n, a fixed point occurs when integer k is placed at position k.
Here are some more links for probability enthusiasts.