CS206 - FALL 2009: WHAT TO READ BEFORE CLASS

The following list shows what I intend to cover in each class. After the class I will modify the entry to reflect what was actually covered. In this way it will also serve as a lecture diary for the course. If you try to read over this material in advance, it should make it easier to follow the class. It could also reduce note-taking if you just annotate the relevant course notes during the class. In parentheses I list the relevant sections in S. Ross, "A First Course in Probability", 7th Ed.

1. (Sept. 2, 2009) Bureauracracy. Review some set theory.

2. (Sept 8, 2009) [NOTE: this Tuesday is a Rutgers Monday] Start basic ingredients of Probability: Random experiment;
sample space; many examples given. Events, with many examples. (2.2 - 2.4)

3. (Sept 9, 2009) Probability measure and some properties. Conditional probability, the conditional probability formula, and examples. (3.2,3.3)

4. (Sept. 14, 2009) Other probability facts, Bayes Rule, and examples. Independence; pairwise independence. (3.3, 3.4)

5. (Sept. 16, 2009) k-wise independence, mutual independence, and examples. Begin counting and combinatorics: the basic principle of counting (cartesian product rule); ordered sampling, with replacement (this is balls-in-boxes). (3.4, 1.2, 1.3)

6. (Sept. 21, 2009) [Class given by Professor Pavlovic] examples (birthdays). Unordered sampling (combinations), binomial coefficients and properties. (1.3, 1.4)

7. (Sept. 23, 2009) Pascal's relation and Pascal's triangle; Newton's binomial theorem and implications. Examples with unordered sampling. (1.4)

8,9. (Sept. 30, 2009) Continued. Lotteries, Poker and Bridge. The inclusion/exclusion formula for the probability of a union; examples. (2.4).

10. (Oct. 5, 2009) Continued; the formula, its proof and a tricky counting rendered as "straightforward" using the formula. Derangements (2.4).

11. (Oct. 7, 2009) Continued. The probability that exactly k of the people in the n-hat experiment get their own hats. The partition experiment and examples, e.g. Bridge, model-2. (1.5)

12. (Oct. 12, 2009) Continued, multinomial coefficients, permutations of k types of indistinguishable items, examples.

13. (Oct. 14, 2009) Begin Random variables, the frequency function, some examples. Independence for random variables.

14. (Oct. 19, 2009) Continued. Repeated (independent) trials and product probability (6.2 and pages 125-126).

15. (Oct. 21, 2009) Continued. Bernoulli trials, binomial frequency function for the number of successes in n trials (4.6).

16. (Oct. 26, 2009) I will try to mention all topics the exam might include, and I will briefly take some questions from past exams. Then resume Bernoulli trial examples. What the binomial frequency function looks like. Infinite sequences of Bernoulli trials, waiting for one success, the geometric random variable and its frequency function (4.8).

17. (Oct. 28, 2009) MIDTERM.

18. (Nov. 2, 2009) Return midterm. Continue Geometric Random variable. Waiting for k successes; negative binomial random variable and examples. Begin expectation and its properties (4.3).

19. (Nov. 4, 2009) Continued: (i) expectation is Linear; (ii) the expectation is the center of (probability) mass. Examples. Expected wait for the first success in Bernoulli trials. Begin "method of indicators", with examples: Ex 1. expected number who get their own hat in n-hat experiment;

20. (Nov. 9, 2009) Continued: Ex 2. expected number of empty boxes in n-ball, n-box experiment; Ex 3. mean of the binomial random variable. derive mean of negative-binomial random variable. Coupon collecting (7.1, 7.2).

21. (Nov. 11, 2009) Begin Covariance, uncorrelated random variables and independence (7.4). Variance of a random variable and some properties: (section 4.6).

22. (Nov. 16, 2009) Variance of the geometric (section 4.8), negative binomial (section 4.8), and binomial random variables (4.6).

23. (Nov. 18, 2009) The variance of an average and the Law of Large Numbers. Tchebycheff's inequality (section 8.2). More on the Law of Large Numbers. Using Tchebycheff to "check" the probability measure on S. Begin generating functions for sequences.

24. (Nov. 23, 2009) Reprise Law of large numbers, with an example. Return to generating functions and their properties. Generating functions for (non-negative) integer-valued random variables. The convolution of two sequences and its generating function. Generating function of (i) an indicator random variable, of (ii) the number of successes in n Bernoulli trials, of (iii) a geometric random variable. Using the generating function to compute mean and variance.