Topics:

1. Syllabus and Intro.
2. Why probability is useful
   1. AT&T installed bandwidth to provide level of iphone service (not all users want to use it simultaneously).
   2. also web servers, roads, cashiers, ...
   3. fair price for financial CDO that reduces risk
3. Model
   1. Real thing too expensive, dangerous, time-consuming (aircraft design).
   2. Capture the relevant, ignore the rest.
   3. Coin flip: relevant: it's fair? not relevant: copper, tin, zinc, ...
   4. Validate model if possible.
4. Computer simulation model
   1. For systems too complicated for a simple math equation (i.e., most systems outside school)
   2. Often a graph of components linked together, e.g., with
      1. Matlab Simulink
      2. PSPICE
   3. many examples, e.g. antilock brake, US economy
   4. Can do experiments on it.
5. Deterministic model
   1. Resistor: V=IR
   2. Limitations: perhaps not if I=1000000 amps. Why?
   3. Limitations: perhaps not if I=0.00000000001 amps. Why?
6. Probability model
   1. Roulette wheel: {$p_i=\frac{1}{38} $} (ignoring http://www.amazon.com/Eudaemonic-Pie-Thomas-Bass/dp/0595142362 )
7. Statistical regularity
   1. {$ lim_{n\rightarrow\infty}f_k(n) =p_k $}
   2. law of large numbers
   3. weird distributions (e.g., Cauchy) violate this, but that's probably beyond this course.
8. Properties of relative frequency
   1. the frequencies of all the possibilities sum to 1.
   2. if an event is composed of several outcomes that are disjoint, the event's probability is the sum of the outcomes' probabilities.
   3. E.g., If the event is your passing this course and the relevant outcomes are grades A, B, C, D, with probabilities .3, .3, .2, .1, then p_pass=.9. (These numbers are fictitious.)
9. Axiomatic approach
   1. Probability is between 0 and 1.
   2. Probs sum to 1.
   3. If the events are disjoint, then the probs add.
10. Building a model
    1. Want to model telephone conversations where speaker talks 1/3 of time.
    2. Could use an urn with 2 black, 1 white ball.
    3. Computer random number generator easier.
11. Detailed example in more detail - phone system
    1. Design telephone system for 48 simultaneous users.
    2. Transmit packet of voice every 10msecs.
    3. Only 1/3 users are active.
    4. 48 channels wasteful.
    5. Alloc only M<48 channels.
    6. In the next 10msec block, A people talked.
    7. If A>M, discard A-M packets.
    8. How good is this?
    9. n trials
    10. N_k(n) trials have k packets
    11. frequency f_k(n)=N_k(n)/n
    12. f_k(n)->p_k probability
    13. We'll see the exact formula (Poisson) later.
    14. average number of packets in one interval: {$$\frac{\sum_{k=1}^{48} kN_k(n)}{n} \rightarrow \sum_{k=1}^{48} kp_k = E[A] $$}
    15. That is the expected value of A.
12. Probability application: unreliable communication channel.
    1. Transmitter transmits 0 or 1.
    2. Receiver receives 0 or 1.
    3. However, a transmitted 0 is received as a 0 only 90% of the time, and
    4. a transmitted 1 is received as a 1 only 80% of the time, so
    5. if you receive a 0 what's the probability that a 0 was transmitted?
    6. ditto 1.
    7. (You don't have enough info to answer this; you need to know also the probability that a 0 was transmitted. Perhaps the transmitter always sends a 0.)
13. Another application: stocking spare parts:
    1. There are 10 identical lights in the classroom ceiling.
    2. The lifetime of each bulb follows a certain distribution. Perhaps it dies uniformly anytime between 1000 and 3000 hours.
    3. As soon as a light dies, the janitor replaces it with a new one.
    4. How many lights should the janitor stock so that there's a 90% chance that s/he won't run out within 5000 hours?

Reading:

1. Leon-Garcia, chapter 1.

Announcements:

1. Homework 1 available.
2. Bring your clicker on Fri.

Topics:

1. Why not use LMS?
   1. This wiki is much easier to use. I can create and save material more easily.
   2. You don't need to login to see the content. You can deep-link into the material. People outside the course can see, and save, the material.
   3. A few years ago, LMS sued an open source competitor. (They lost!)
2. Coin toss applet demonstrates how the observed frequencies converge (slowly) to the theoretical probability.
3. Example of unreliable channel
   1. Want to transmit a bit: 0, 1
   2. It arrives wrong with probability e, say 0.001
   3. Idea: transmit each bit 3 times and vote.
      1. 000 -> 0
      2. 001 -> 0
      3. 011 -> 1
   4. 3 bits arrive correct with probability (1-e)³ = 0.997002999
   5. 1 error with probability 3(1-e)²e = 0.002994
   6. 2 errors with probability 3(1-e)e² = 0.000002997
   7. 3 errors with probability e³ = 0.000000001
   8. corrected bit is correct if 0 or 1 errors, with probability (1-e)³+3(1-e)²e = 0.999996999
   9. We reduced probability of error by factor of 1000.
   10. Cost: triple the transmission plus a little logic HW.
4. Example of text compression
   1. Simple way: Use 5 bits for each letter: A=00000, B=00001
   2. In English, 'E' common, 'Q' rare
   3. Use fewer bits for E than Q.
   4. Morse code did this 170 years ago.
      1. E = .
      2. Q = _ _ . _
   5. Aside: An expert Morse coder is faster than texting.
   6. English can be compressed to about 1 bit per letter (with difficulty); 2 bits is easy.
   7. Aside: there is so much structure in English text, that if you add the bit strings for 2 different texts bit-by-bit, they can usually mostly be reconstructed.
   8. That's how cryptoanalysis works.
5. Example of reliable system design
   1. Nuclear power plant fails if
      1. water leaks
      2. and operator asleep (a surprising number of disasters happen in the graveyard shift).
      3. and backup pump fails
      4. or was turned off for maintenance
      5. .....
   2. What's the probability of failure? This depends on the probabilities of the various failure modes. Those might be impossible to determine accurately.
   3. Design a better system? Coal mining kills.
   4. The backup procedures themselves can cause problems (and are almost impossible to test). A failure with the recovery procedure was part of the reason for the recent Skype outage.

1. A random experiment has 2 parts:
   1. experimental procedure
   2. set of measurements
2. Random experiment may have subexperiments and sequences of experiments.
3. Outcome or sample point {$\zeta$}: a non-decomposable observation.
4. Sample space S: set of all outcomes
5. |S|:
   1. finite, e.g. {H,T}
   2. discrete = countable, e.g., 1,2,3,4,... Sometimes discrete includes finite.
   3. uncountable, e.g., {$\Re$}, aka continuous.
6. Types of infinity:
   1. Some sets have finite size, e.g., 2 or 6.
   2. Other sets have infinite size.
   3. Those are either countable or uncountable.
   4. A countably infinite set can be arranged in order so that its elements can be numbered 1,2,3,...
   5. The set of natural numbers is obviously countable.
   6. The set of positive rational numbers between 0 and 1 is also countable. You can order it thus: {$$ \frac{1}{1}, \frac{1}{2}, \frac{1}{3}, \frac{2}{3}, \frac{1}{4}, \ \frac{3}{4}, \frac{1}{5}, \frac{2}{5}, \frac{3}{5}, \ \cdots $$}
   7. The set of real numbers is not countable (aka uncountable). Proving this is beyond this course. (It uses something called diagonalization.
   8. Uncountably infinite is a bigger infinity than countably infinite, but that's beyond this course.
7. Why is this relevant to probability?
   1. We can assign probabilities to discrete outcomes, but not to individual continuous outcomes.
   2. We can assign probabilities to some events, or sets of continuous outcomes.
8. E.g. Consider this experiment to watch an atom of sodium-26.
   1. Its half-life is 1 second (Applet: Nuclear Isotope Half-lifes)
   2. Define the outcomes to be the number of complete seconds before it decays: {$ S=\{0, 1, 2, 3, \cdots \} $}
   3. {$ |S| $} is countably infinite, i.e., discrete.
   4. {$ p(0)=\frac{1}{2}, p(1)=\frac{1}{4}, \cdots $} {$ p(k)=2^{-(k+1)} $}
   5. {$$ \sum_{k=0}^\infty p(k) = 1 $$}
   6. We can define events like these:
      1. The atom decays within the 1st second. p=.5.
      2. The atom decays within the first 3 seconds. p=.875.
      3. The atom's lifetime is an even number of seconds. {$$ p = \frac{1}{2} + \frac{1}{8} + \frac{1}{32} + \cdots = \frac{2}{3} $$}
9. Now consider another experiment: Watch another atom of Na-26
   1. But this time the outcome is defined to be the real number, x, that is the time until it decays.
   2. {$ S = \{ x | x\ge0 \} $}
   3. |S| is uncountably infinite.
   4. We cannot talk about the probability that x=1.23 exactly. (It just doesn't work out.)
   5. However, we can define the event that {$ 1.23 < x < 1.24 $}, and talk about its probability.
   6. {$ P[x>x_0] = 2^{-x_0} $} (corrected)
   7. {$ P[1.23 < x < 1.24] $} {$ = 2^{-1.23} - 2^{-1.24} = 0.003 $}
10. Event
    1. collection of outcomes, subset of S
    2. what we're interested in.
    3. e.g., outcome is voltage, event is V>5.
    4. certain event: S
    5. null event: {$\emptyset$}
    6. elementary event: one discrete outcome
11. Set theory
    1. Sets: S, A, B, ...
    2. Universal set: U
    3. elements or points: a, b, c
    4. {$ a\in S, a\notin S $}, {$A\subset B$}
    5. Venn diagram
       
    6. empty set: {} or {$\emptyset$}
    7. operations on sets: equality, union, intersection, complement, relative complement
    8. properties (axioms): commutative, associative, distributive
    9. theorems: de Morgan
12. Prove deMorgan 2 different ways.
    1. Use the fact that A equals B iff A is a subset of B and B is a subset of A.
    2. Look at the Venn diagram; there are only 4 cases.
13. 2.1.4 Event classes
    1. Remember: an event is a set of outcomes of an experiment, e.g., voltage.
    2. In a continuous sample space, we're interested only in some possible events.
    3. We're interested in events that we can measure.
    4. E.g., we're not interested in the event that the voltage is exactly an irrational number.
    5. Events that we're interested in are intervals, like [.5,.6] and [.7,.8].
    6. Also unions and complements of intervals.
    7. This matches the real world. You can't measure a voltage as 3.14159265...; you measure it in the range [3.14,3.15].
    8. Define {$\cal F$} to be the class of events of interest: those sets of intervals.
    9. We assign probabilities only to events in {$\cal F$}.
14. 2.2 Axioms of probability
    1. An axiom system is a general set of rules. The probability axioms apply to all probabilities.
    2. Axioms start with common sense rules, but get less obvious.
    3. I: 0<=P[A]
    4. II: P[S]=1
    5. III: {$ A\cap B=\emptyset \rightarrow $} {$ P[A\cup B] = P[A]+P[B] $}
    6. III': For {$ A_1, A_2, .... $} if {$ \forall_{i\ne j} A_i \cap A_j = \emptyset$} then {$P[\bigcup_{i=1}^\infty A_i] $} {$ = \sum_{i=1}^\infty P[A_i] $}
15. Example: cards. Q=event that card is queen, H=event that card is heart. These events are not disjoint. Probabilities do not sum.
    1. {$Q\cap H \ne\emptyset $}
    2. P[Q] = 1/13=4/52, P[H] = 1/4=13/52, P[Q {$\cup$} H] = 16/52!=17/52.
16. Example C=event that card is clubs. H and C are disjoint. Probabilities do sum.
    1. {$C\cap H \ne\emptyset $}
    2. P[C] = 13/52, P[H] = 1/4=13/52, P[Q {$\cup$} H] = 26/52.
17. Example. Flip a fair coin {$A_i$} is the event that the first time you see heads is the i-th time, for {$i\ge1$}.
    1. We can assign probabilities to these countably infinite number of events.
    2. {$ P[A_i] = 1/2^i $}
    3. They are disjoint, so probabilities sum.
    4. Probability that the first head occurs in the 10th or later toss = {$ \sum_{i=10}^\infty 1/2^i $}
18. Corollory 1
    1. {$ P[A^c] = 1-P[A] $}
    2. E.g., P[heart] = 1/4, so P[not heart] = 3/4
19. Corollory 2: P[A] <=1
20. Corollory 3: P[{$ \emptyset $}] = 0
21. Corollory 4:
    1. For {$ A_1, A_2, .... A_n $} if {$ \forall_{i\ne j} A_i \cap A_j = \emptyset$} then {$P\left[\bigcup_{i=1}^n A_i\right] = \sum_{i=1}^n P[A_i] $}
    2. Proof by induction from axiom III.

1. Homework 2 online.
2. Teaching assistants' photos online.
3. How Did Economists Get It So Wrong? is the article by Paul Krugman (2008 Nobel Memorial Prize in Economic Science) that I mentioned in the first lecture. It says, "the economics profession went astray because economists, as a group, mistook beauty, clad in impressive-looking mathematics, for truth." You might see a certain relevance to this course. You have to get the model right before trying to solve it.
   Though I don't know much about it, I'll cheerfully try to answer any questions about econometrics.
   Another relevance to this course, in an enrichment sense, is that some people believe that the law of large numbers does not apply to certain variables, like stock prices. They think that larger and larger sample frequencies do not converge to a probability, because the variance of the underlying distribution is infinite. See Do financial returns have finite or infinite variance? A paradox and an explanation. This also is beyond this course.
4. Corrections: 1, 2, 3
5. iClicker (2nd try)
   1. Answer this question (won't be graded): 2+2=? 1, B:2, C:3.9999, D:4, E: whatever you want it to be.
   2. Register your iClicker, using your RCS ID. E.g., I would register as W Randolph Franklin frankwr
6. iclicker exercise based on retransmitting a noisy bit 3 times here (not graded)
   1. Set e=0.1
   2. What is probability of no error in 3 bits:
      • A 0.1
      • B 0.3
      • C 0.001
      • D 0.729
      • E 0.9
7. Corollory 5: {$ P[A\cup B] $} {$ = P[A] + P[B] - P[A\cap B] $}
   1. Proof from the fact that {$ P[A], P[B], P[A\cap B] $} are disjoint.
   2. Example: Queens and hearts. P[Q]=4/52, P[H]=13/52, P[Q {$\cup$} H]=16/52, P[Q {$\cap$} H]=1/52.
   3. {$ P[A\cup B] \le P[A] + P[B] $}
8. Corollory 6: {$ \begin{array}{c} P\left[\cup_{i=1}^n A_i\right] = \\ \sum_{i=1}^n P[A_i] \\ - \sum_{i<j} P[A_i\cap A_j] \\ + \sum_{i<j<k} P[A_i\cap A_j\cap A_k] \cdots \\ + (-1)^{n+1} P[\cap_{i=1}^n A_i] \end{array} $}
   1. Example Q=queen card, H=heart, F= face card
      1. P[Q]=4/52, P[H]=13/52, P[F]=12/52,
      2. P[Q {$\cap$} H]=1/52, P[Q {$\cap$} F] = you tell me
      3. P[H {$\cap$} F]= you tell me
      4. P[Q {$\cap$} H {$\cap$} F] = you tell me
      5. So P[Q {$\cup$} H {$\cup$} F] = ?
   2. Example from Roulette:
      1. R=red, B=black, E=even, A=1-12
      2. P[R] = P[B] = P[E] = 16/38. P[A]=12/38
      3. {$ P[R\cup E \cup A] $} = ?
      4. You could try at http://www.roulette4fun.com/online_game.php but it's slow.
9. Corollory 7: if {$A\subset B$} then P[A] <= P[B]
   Example: Probability of a repeated coin toss having its first head in the 2nd-4th toss (1/2+1/4+1/8) {$\ge$} Probability of it happening in the 3rd toss (1/4).
10. 2.2.1 Discrete sample space
    1. If sample space is finite, probabilities of all the outcomes tell you everything.
    2. sometimes they're all equal.
    3. Then {$ \text{P[event]} $} {$ = \frac{\text{# outcomes in event}}{\text{total # outcomes}} $}
    4. For countably infinite sample space, probabilities of all the outcomes also tell you everything.
    5. E.g. fair coin. P[even] = 1/2
    6. E.g. example 2.9. Try numbers from http://random.org/.
    7. What probabilities to assign to outcomes is a good question.
    8. Example 2.10. Toss coin 3 times.
       1. Choice 1: outcomes are TTT ... HHH, each with probability 1/8
       2. Choice 2: outcomes are # heads: 0...3, each with probability 1/4.
       3. Incompatible. What are probabilities of # heads for choice 1?
       4. Which is correct?
       5. Both might be mathematically ok.
       6. It depends on what physical system you are modeling.
       7. You might try doing the experiment and observing.
       8. You might add a new assumption: The coin is fair and the tosses independent.
11. Example 2.11: countably infinite sample space.
    1. Toss fair coin, outcome is # tosses until 1st head.
    2. What are reasonable probabilities?
    3. Do they sum to 1?
12. 2.2.2 Continuous sample spaces
    1. Usually we can't assign probabilities to points on real line. (It just doesn't work out mathematically.)
    2. Work with set of intervals, and Boolean operations on them.
    3. Set may be finite or countable.
    4. This set of events is a Borel set.
    5. Notation:
       1. [a,b] closed. includes both. a<=x<=b
       2. (a,b) open. includes neither. a<x<b
       3. [a,b) includes a but not b, a<=x<b
       4. (a,b] includes b but not a, a<x<=b
    6. Assign probabilities to intervals (open or closed).
    7. E.g., uniform distribution on [0,1] {$$ P[a\le x\le b] = \frac{1}{b-a} $$}
    8. Nonuniform distributions are common.
    9. Even with a continuous sample space, a few specific points might have probabilities. The following is mathematically a valid probability distribution. However I can't immediately think of a physical system that it models.
       1. {$ S = \{ x | 0\le x\le 1 \} $}
       2. {$ p(x=1) = 1/2 $}
       3. For {$ 0\le x_0 \le 1, p(x<x_0) = x_0/2 $}
13. For fun: Heads you win, tails... you win. You can beat the toss of a coin and here's how...
14. Example 2.13, page 39, nonuniform distribution: chip lifetime.
    1. Propose that P[(t, {$ \infty $} )] = {$ e^{-at} $} for t>0.
    2. Does this satisfy the axioms?
    3. I: yes >0
    4. II: yes, P[S] = {$ e^0 $} = 1
    5. III here is more like a definition for the probability of a finite interval
    6. P[(r,s)] = P[(r, {$ \infty $} )] - P[(s, {$ \infty $} )] = {$ e^{-ar} - e^{-as} $}
15. Probability of a precise value occurring is 0, but it still can occur, since SOME value has to occur.
16. Example 2.14: picking 2 numbers randomly in a unit square.
    1. Assume that the probability of a point falling in a particular region is proportional to the area of that region.
    2. E.g. P[x>1/2 and y<1/10] = 1/20
    3. P[x>y] = 1/2
17. Recap:
    1. Problem statement defines a random experiment
    2. with an experimental procedure and set of measurements and observations
    3. that determine the possible outcomes and sample space
    4. Make an initial probability assignment
    5. based on experience or whatever
    6. that satisfies the axioms.

1. iclickers: We'll try yet again. Bruce Laplante writes, "Some students do not realize that the iClicker takes 3 AAA batteries. The third battery is all the way down the tube and requires a few taps of the clicker to get it out. When batteries die, students who don't know this replace only 2, and the transmitter still won't work."
2. iClicker (2nd try)
   1. Register your iClicker, using your RCS ID. E.g., I would register as W Randolph Franklin frankwr
   2. Answer this question (won't be graded): 2+2=?
      1. 1
      2. 2
      3. 3.9999
      4. 4
      5. Whatever you want it to be.
   3. Continuous probability:
      1. S is the real interval [0,1].
      2. P([a,b]) = b-a if 0<=a<=b<=1.
      3. Event A = [.2,.6].
      4. Event B = [.4,1].
      5. What is P[A]?
         1. .2
         2. .4
         3. .6
         4. .8
         5. 1.
      6. What is P[B]?
         1. .2
         2. .4
         3. .6
         4. .8
         5. 1.
      7. What is P[A {$\cup$} B]?
         1. .2
         2. .4
         3. .6
         4. .8
         5. 1.
      8. What is P[A {$\cap$} B]?
         1. .2
         2. .4
         3. .6
         4. .8
         5. 1.
      9. What is P[A {$\cup$} B^c ]?
         1. .2
         2. .4
         3. .6
         4. .8
         5. 1.
3. Today: counting methods.
   1. We have an urn with n balls.
   2. Maybe the balls are all different, maybe not.
   3. W/o looking, we take k balls out and look at them.
   4. Maybe we put each ball back after looking at it, maybe not.
   5. Suppose we took out one white and one green ball. Maybe we care about their order, so that's a different case from green then white, maybe not.
4. Applications:
   1. How many ways can we divide a class of 12 students into 2 groups of 6?
   2. How many ways can we pick 4 teams of 6 students from a class of 88 students (leaving 64 students behind)?
   3. We pick 5 cards from a deck. What's the probability that they're all the same suit?
   4. We're picking teams of 12 students, but now the order matters since they're playing baseball and that's the batting order.
   5. We have 100 widgets; 10 are bad. We pick 5 widgets. What's the probability that none are bad? Exactly 1? More than 3?
   6. In the approval voting scheme, you mark as many candidates as you please. The candidate with the most votes wins. How many different ways can you mark the ballot?
   7. In preferential voting, you mark as many candidates as you please, but rank them 1,2,3,... How many different ways can you mark the ballot?
   8. Efficiency rankings have been calculated for each of 32 football teams. Assuming that everything were uniform and random, what's the probability that both Pittsburgh and Green Bay are in the top 5?
5. Leon-Garcia 2.3: Counting methods, pp 41-46.
   1. finite sample space
   2. each outcome equally probable
   3. get some useful formulae
   4. warmup: consider a multiple choice exam where 1st answer has 3 choices, 2nd answer has 5 choices and 3rd answer has 6 choices.
      1. Q: How many ways can a student answer the exam?
      2. A: 3x5x6
   5. If there are k questions, and the i-th question has {$n_i$} answers then the number of possible combinations of answers is {$n_1n_2 .. n_k $}
6. 2.3.1 Sampling WITH replacement and WITH ordering
   1. Consider an urn with n different colored balls.
   2. Repeat k times:
      1. Draw a ball.
      2. Write down its color.
      3. Put it back.
   3. # Distinct ordered k-tuples = {$n^k$}
7. Example 2.1.5. How many distinct ordered pairs for 2 balls from 5? 5*5.
8. iClicker. Suppose I want to eat one of the following 4 places, for tonight and again tomorrow, and don't care if I eat at the same place both times: Commons, Sage, Union, Knotty Pine. How many choices to I have where to eat?
   1. 16
   2. 12
   3. 8
   4. 4
   5. something else
9. 2.3.2 Sampling WITHOUT replacement and WITH ordering
   1. Consider an urn with n different colored balls.
   2. Repeat k times:
      1. Draw a ball.
      2. Write down its color.
      3. Don't put it back.
   3. # Distinct ordered k-tuples = n(n-1)(n-2)...(n-k+1)
10. iClicker. Suppose I want to visit two of the following four cities: Buffalo, Miami, Boston, New York. I don't want to visit one city twice, and the order matters. How many choices to I have how to visit?
    1. 16
    2. 12
    3. 8
    4. 4
    5. something else
11. Example 2.1.6: Draw 2 balls from 5 w/o replacement.
    1. 5 choices for 1st ball, 4 for 2nd. 20 outcomes.
    2. Probability that 1st ball is larger?
    3. List the 20 outcomes. 10 have 1st ball larger. P=1/2.
12. Example 2.1.7: Draw 3 balls from 5 with replacement. What's the probability they're all different?
    1. P = {$ \small \frac{\text{# cases where they're different}} {\text{# cases where I don't care}} $}
    2. P = {$ \small \frac{\text{# case w/o replacement}} {\text{# cases w replacement}} $}
    3. P = {$ \frac{5*4*3}{5*5*5} $}
13. 2.3.3 Permutations of n distinct objects
    1. Distinct means that you can tell the objects apart.
    2. This is sampling w/o replacement for k=n
    3. 1.2.3.4...n = n!
    4. It grows fast. 1!=1, 2!=2, 3!=6, 4!=24, 5!=120, 6!=720, 7!=5040
    5. Stirling approx: {$$ n! $$} {$$ \approx \sqrt{2\pi n} \left(\frac{n}{e}\right)^n\left(1+\frac{1}{12n}+...\right) $$}
    6. Therefore if you ignore the last term, the relative error is about 1/(12n).
14. Example 2.1.8. # permutations of 3 objects. 6!
15. Example 2.1.9. 12 airplane crashes last year. Assume independent, uniform, etc, etc. What's probability of exactly one in each month?
    1. For each crash, let the outcome be its month.
    2. # events for all 12 crashes = {$ 12^{12} $}
    3. # events for 12 crashes in 12 different months = 12!
    4. Probability = {$ 12!/(12^{12}) = 0.000054 $}
    5. Random does not mean evenly spaced.
16. 2.3.4 Sampling w/o replacement and w/o ordering
    1. We care what objects we pick but not the order
    2. E.g., drawing a hand of cards.
    3. term: Combinations of k objects selected from n. Binomial coefficient. {$ C^n_k = {n \choose k} = \frac{n!}{k! (n-k)!} $}
    4. Permutations is when order matters.
17. Example 2.20. Select 2 from 5 w/o order. {$ 5\choose 2 $}
18. Example 2.21 # permutations of k black and n-k white balls. This is choosing k from n.
19. Example 2.22. 10 of 50 items are bad. What's probability 5 of 10 selected randomly are bad?
    1. # ways to have 10 bad items in 50 is {$ 50\choose 10$}
    2. # ways to have exactly 5 bad is 3 ways to select 5 good from 40 times # ways to select 5 bad from 10 = {$ {40\choose5} {10\choose5} $}
    3. Probability is ratio.
20. Multinomial coefficient: Partition n items into sets of size {$ k_1, k_2, ... k_j, \sum k_i=n $} {$ \frac{n!}{k_1! k_2! ... k_j!} $}
21. 2.3.5. skip
22. Probability in the news: Statistician Cracks Code For Lottery Tickets

Reading for Tues: 2.4 Conditional probability, page 47-

1. Homework 3 out.
2. Review last time by solving the applications I posted then.
3. New stuff, pp. 47-66:
   1. Conditional probability - If you know that event A has occurred, does that change the probability that event B has occurred?
   2. Independence of events - If no, then A and B are independent.
   3. Sequential experiments - Find the probability of a sequence of experiments from the probabilities of the separate steps.
   4. Binomial probabilities - tossing a sequence of unfair coins.
   5. Multinomial probabilities - tossing a sequence of unfair dice.
   6. Geometric probabilities - toss a coin until you see the 1st head.
   7. Sequences of dependent experiments - What you see in step 1 influences what you do in step 2.
4. 2.4 Conditional probability, page 47.
   1. big topic
   2. E.g., if it snows today, is it more likely to snow tomorrow? next week? in 6 months?
   3. E.g., what is the probability of the stock market rising tomorrow given that (it went up today, the deficit went down, an oil pipeline was blown up, ...)?
   4. What's the probability that a CF bulb is alive after 1000 hours given that I bought it at Walmart?
   5. definition {$ P[A|B] = \frac{P[A\cap B]}{P[B]} $}
5. Consider a fictional university that has both undergrads and grads. It also has both Engineers and others:
   
6. iClicker: What's the probability that a student is an Engineer?
   1. 1/7
   2. 4/7
   3. 5/7
   4. 3/4
   5. 3/5
7. iClicker: What's the probability that a student is an Engineer, given that s/he is an undergrad?
   1. 1/7
   2. 4/7
   3. 5/7
   4. 3/4
   5. 3/5
8. P[A{$\cap$}B] = P[A|B]P[B] = P[B|A]P[A]
9. Example 2.26 Binary communication. Source transmits 0 with probability (1-p) and 1 with probability p. Receiver errs with probability e. What are probabilities of 4 events?
10. Total probability theorem
    1. {$B_i$} mutually exclusive events whose union is S
    2. P[A] = P[A {$\cap B_1$} + P[A {$\cap B_2$} + ...
    3. {$ P[A] = P[A|B_1]P[B_1] $} {$ + P[A|B_2]P[B_2] + ... $}
    
    What's the probability that a student is an undergrad, given ... (Numbers are fictitious.)
11. Example 2.28. Chip quality control.
    1. Each chip is either good or bad.
    2. P[good]=(1-p), P[bad]=p.
    3. If the chip is good: P[still alive at t] = {$ e^{-at} $}
    4. If the chip is bad: P[still alive at t] = {$ e^{-1000at} $}
    5. What's the probability that a random chip is still alive at t?
12. 2.4.1, p52. Bayes' rule. This lets you invert the conditional probabilities.
    1. B_j partition S. That means that
       1. If {$i\ne j$} then {$ B_i\cap B_j=\emptyset $} and
       2. {$ \bigcup_i B_i = S $}
    2. {$$ P[B_j|A] = \frac{B_j\cap A}{P[A]} $$} {$$ = \frac{P[A|B_j] P[B_j]}{\sum_k P[A|B_k] P[B_k]} $$}
    3. application:
       1. We have a priori probs {$ P[B_j] $}
       2. Event A occurs. Knowing that A has happened gives us info that changes the probs.
       3. Compute a posteriori probs {$ P[B_j|A] $}
13. In the above diagram, what's the probability that an undergrad is an engineer?
14. Example 2.29 comm channel: If receiver sees 1, which input was more probable? (You hope the answer is 1.)
15. Example 2.30 chip quality control: For example 2.28, how long do we have to burn in chips so that the survivors have a 99% probability of being good? p=0.1, a=1/20000.
16. Example: False positives in a medical test
    1. T = test for disease was positive; T' = .. negative
    2. D = you have disease; D' = .. don't ..
    3. P[T|D] = .99, P[T'|D'] = .95, P[D] = 0.001
    4. P[D'|T] (false positive) = 0.98 !!!
17. Example: Pick a cookie, from same page.
18. 2.5 Independent events
    1. {$ P[A\cap B] = P[A] P[B] $}
    2. P[A|B] = P[A], P[B|A] = P[B]
19. A,B independent means that knowing A doesn't help you with B.
20. Mutually exclusive events w.p.>0 must be dependent.
21. Example 2.33. Last condition above is required.
    
22. More that 2 events:
    1. N events are independent iff the occurrance of no combo of the events affects another event.
    2. Each pair is independent.
    3. Also need {$ P[A\cap B\cap C] = P[A] P[B] P[C] $}
    4. This is not intuitive A, B, and C might be pairwise independent, but, as a group of 3, are dependent.
    5. See example 2.32, page 55. A: x>1/2. B: y>1/2. C: x>y
23. Common application: independence of experiments in a sequence.
24. Example 2.34: coin tosses are assumed to be independent of each other.
    P[HHT] = P[1st coin is H] P[2nd is H] P[3rd is T].
25. Example 2.35 System reliability
    1. Controller and 3 peripherals.
    2. System is up iff controller and at least 2 peripherals are up.
    3. Add a 2nd controller.
26. 2.6 p59 Sequential experiments: maybe independent
27. 2.6.1 Sequences of independent experiments
    1. Example 2.36
28. 2.6.2 Binomial probability
    1. Bernoulli trial flip a possibly unfair coin once. p is probability of head.
    2. (Bernoulli did stats, econ, physics, ... in 18th century.)
29. Example 2.37
    1. P[TTH] = {$ (1-p)^2 p $}
    2. P[1 head] = {$ 3 (1-p)^2 p $}
30. Probability of exactly k successes = {$$ p_n(k) = {n \choose k} p^k (1-p)^{n-k} $$}
31. {$ \sum_{k=0}^n p_n(k) = 1 $}
32. Example 2.38
33. Can avoid computing n! by computing {$ p_n(k) $} recursively, or by using approximation. Also, in C++, using double instead of float helps. (Almost always you should use double instead of float. It's the same speed.)
34. Example 2.39
35. Example 2.40 Error correction coding
36. Multinomial probability law
    1. There are M different possible outcomes from an experiment, e.g., faces of a die showing.
    2. Probability of particular outcome: {$p_i$}
    3. Now run the experiment n times.
    4. Probability that i-th outcome occurred {$k_i$} times, {$ \sum_{i=1}^M k_i = n $} {$$ P[(k_1,k_2,...,k_M)] $$} {$$ = \frac{n!}{k_1! k_2! ... k_M!} p_1^{k_1} p_2^{k_2}...p_M^{k_M} $$}
37. Example 2.41 dartboard.
38. Example 2.42 random phone numbers.
39. 2.7 Computer generation of random numbers
    1. Skip this section, except for following points.
    2. Executive summary: it's surprisingly hard to generate good random numbers. Commercial SW has been known to get this wrong. By now, they've gotten it right (I hope), so just call a subroutine.
    3. Arizona lottery got it wrong in 1998.
    4. Even random electronic noise is hard to use properly. The best selling 1955 book A Million Random Digits with 100,000 Normal Deviates had trouble generating random numbers this way. Asymmetries crept into their circuits perhaps because of component drift. For a laugh, read the reviews.
    5. Pseudo-random number generator: The subroutine returns numbers according to some algorithm (e.g., it doesn't use cosmic rays), but for your purposes, they're random.
    6. Computer random number routines usually return the same sequence of number each time you run your program, so you can reproduce your results.
    7. You can override this by seeding the generator with a genuine random number from linux /dev/random.
40. 2.8 and 2.9 p70 Fine points: Skip.

1. Review Bayes theorem, since it is important. Here is a fictitious (because none of these probilities have any justification) SETI example.
   1. A priori probability of extraterrestrial life = P[L] = {$10^{-8} $}.
   2. For ease of typing, let L' be the complement of L.
   3. Run a SETI experiment. R (for Radio) is the event that it has a positive result.
   4. P[R|L] = {$ 10^{-5} $}, P[R|L'] = {$ 10^{-10} $}.
   5. What is P[L|R] ?
2. Some specific probability laws
   1. In all of these, successive events are independent of each other.
   2. A Bernoulli trial is one toss of a coin where p is probability of head.
   3. We saw binomial and multinomial probilities on Tues.
   4. The binomial law gives the probability of exactly k heads in n tosses of an unfair coin.
   5. The multinomial law gives the probability of exactly ki occurrances of the i-th face in n tosses of a die.
3. iClicker: You have a coin where the probability of a head is p=2/3 If you toss it twice, what's the probability that you will see one head and one tail?
   • 1/2
   • 1/3
   • 2/9
   • 5/9
   • 4/9
4. 2.6.4 p63 Geometric probability law
   1. Repeat Bernoulli experiment until 1st success.
   2. Define outcome to be # trials until that happens.
   3. Define q=(1-p).
   4. {$ p(m) = (1-p)^{m-1}p = q^{m-1}p $} (p has 2 different uses here).
   5. {$ \sum_{m=1}^\infty p(m) =1$}
   6. Probability that more than K trials are required = {$q^K$}.
5. Example: probability that more than 10 tosses of a die are required to get a 6 = {$ \left(\frac{5}{6}\right)^{10} = 0.16 $}
6. iClicker: You have a coin where the probability of a head is p=2/3 What's the probability that the 1st head occurs on the 2nd toss?
   • 1/2
   • 1/3
   • 2/9
   • 5/9
   • 4/9
7. Example 2.43: error control by retransmission. A sent over a noisy channel is checksummed so the receiver can tell if it got mangled, and then ask for retransmission. TCP/IP does this.
   Aside: This works better when the roundtrip time is reasonable. Using this when talking to Mars is challenging.
8. 2.6.5 p64 Sequences, chains, of dependent experiments.
   1. This is an important topic, but mostly beyond this course.
   2. In many areas, there are a sequence of observations, and the probability of each observation depends on what you observed before.
   3. It relates to Markov chains.
   4. Motivation: speech and language recognition, translation, compression
   5. E.g., in English text, the probability of a u is higher if the previous char was q.
   6. The probability of a b may be higher if the previous char was u (than if it was x), but is lower if the previous two chars are qu.
   7. Need to look at probabilities of sequences, char by char.
   8. Same idea in speech recognition: phonemes follow phonemes...
   9. Same in language understanding: verb follows noun...
9. Example 2.44, p64
   1. In this example, you repeatedly choose an urn to draw a ball from, depending on what the previous ball was.
10. Chapter 3, p 96. Discrete random variables
    1. From now on our random experiments will always produce numbers, called random variables, at least indirectly.
    2. Then we can compute, e.g., a fair value to pay for a gamble. What should you pay to play roulette so that betting on red breaks even on average?
    3. Discrete is different from discreet.
    4. Random experiment → nonnumerical outcome {$ \zeta $} →
    5. Random Variable {$ X(\zeta ) $}. Any real number.
    6. Random vars in general: X, Y, ...
    7. particular values: x, y, ...
    8. It's the outcome that's random, not the r.v., which is a deterministic function of the outcome.
11. Example 3.1 Coin tosses
    1. Define X to be the number of heads from 3 tosses.
    2. {$ \zeta $}=HHH, X(HHH) =3, {$ S_X=\{0,1,2,3\} $}
12. Example 3.2 Betting game addon to 3.1
    1. Define another random var Y to be payoff: 8 if X=3, 1 if X=2, 0 else.
    2. Y is derived from X
13. Example 3.3 add probs to 3.2, assuming fair coin. P[X=2], P[Y=8]
14. 3.1.1 Ignore since it's starred.
15. 3.2 Discrete r.v. and Probability mass function (pmf).
    1. The pmf shows the probability of every value of random variable X, and of every real number.
    2. If X cannot have the value x, then the pmf is 0 at x.
    3. {$ p_X(x) = P[X=x] = P[\{\zeta:X(\zeta)=x\}] $}
16. p100: 3 properties of pmf. They're all common sense.
    1. Nonnegative.
    2. Sums to one.
    3. The probability of an event B is the sum of the probabilities of the outcomes in B.
17. Example 3.5 probability of # heads in 3 coin tosses: {$ p_X(0)=1/8 $}
18. Example 3.6 betting game {$ p_Y(1)=3/8 $}
19. Fig 3.4. You can graph the pmf.
20. There are many types of random variables, depending on the shape of the pmf. These start out the same as the various probability laws in Chapter 2. However we'll see more types (e.g., Poisson) and more properties of each type (e.g., mean, standard deviation, generating function).
21. Example 3.7 random number generator
    1. produces integer X equally likely in range 0..M-1
    2. {$ S_X=\{0, 1, ... M-1 \} $}
    3. pmf: {$ p_X(k)=1/M $} for k in 0..M-1.
    4. X is a uniform random variable over that set.
22. Example 3.8 Bernoulli random variable
    1. indicator function {$ I_A(\zeta)=1 $} iff {$ \zeta\in A $}
    2. pmf of {$ I_A $}: {$ p_I(0)=1-p, p_I(1)=p $}
    3. {$ I_A $} is a Bernoulli random variable.
23. Example 3.9 Message transmission until success
    1. {$ p_X(k)=q^{k-1}p, k=1,2,3,... $}
    2. Geometric random variable
    3. What about P[X is even]?
24. Example 3.10 Number of transmission errors
    1. {$ p_X(k) = {n \choose k} p^k q^{n-k}, k=0,1,...n $}
    2. binomial random variable
25. Fig 3.5 You can graph the relative frequencies from running an experiment repeatedly.
    1. It will approach the pmf graph (absent pathological cases like the Cauchy distribition that are beyond this course.)
26. 3.3 p104 Expected value and other moments
    1. This is a way to summarize a r.v., and capture important aspects.
    2. E.g., What's a fair price to pay for a lottery ticket?
    3. Mean or expected value or center of mass: {$ m_X = E[X] = \sum_{x\in S_X} x p_X(x) $}
    4. Defined iff absolute convergence: {$ \sum |x| p(x) < \infty $}
27. Example 3.11 Mean of Bernoulli r.v.
28. Example 3.12 Mean of Binomial r.v. What's the expected # of heads in 3 tosses?
29. Example 3.13 Mean of uniform discrete r.v.
30. Run an experiment n times and observe {$ x(1), x(2), ... $}
    1. {$ N_k(n) $} # times {$ x_k $} was seen
    2. {$ f_k(n) = N_k(n)/n $} frequencies
    3. Sample mean {$ <X>_n = \sum x_kf_k(n) $}
    4. With lots of experiments, frequencies approach probabilities and sample mean converges to E[X]
    5. However it may take a long time, which is why stock market investors can go broke first.
31. Example 3.14 p 106 Betting game
32. Example 3.15 Mean of a geometric r.v.
33. Example 3.16 St Petersburg paradox
34. 3.1.1 Expected value of a function of a r.v.
    1. Z=g(X)
    2. E[Z] = E[g(x)] = {$ \sum_k g(x_k) p_X(x_k) $}
35. Example 3.17 square law device
36. {$ E[a g(X)+b h(X)+c] = a E[g(X)] + b E[h(x)] + c $}
37. Example 3.18 Square law device continued
38. Example 3.19 Multiplexor discards packets
39. Next time:
    1. Variance, how spread out is the random variable?
    2. Lots more specific distribitions.
    3. Continuous random variables.

1. This chapter covers Discrete (finite or countably infinite) r.v.. This contrasts to continuous, to be covered later.
2. Discrete r.v.s we've seen so far:
   1. uniform: M events 0...M-1 with equal probs
   2. bernoulli: events: 0 w.p. q=(1-p) or 1 w.p. p
   3. binomial: # heads in n bernoulli events
   4. geometric: # trials until success, each trial has probability p.
3. Compute mean of a binomial distribution (started last Fri).
4. Compute mean of a geometric distribution (started last Fri).
5. 3.3.1, page 107: Operations on means: sums, scaling, functions
6. iclicker: From a deck of cards, I draw a card, look at it, put it back and reshuffle. Then I do it again. What's the probability that exactly one of the 2 cards is a heart?
   • A: 2/13
   • B: 3/16
   • C: 1/4
   • D: 3/8
   • E: 1/2
7. iclicker: From a deck of cards, I draw a card, look at it, put it back and reshuffle. I keep repeating this. What's the probability that the 2nd card is the 1st time I see hearts?
   • A: 2/13
   • B: 3/16
   • C: 1/4
   • D: 3/8
   • E: 1/2

1. 3.3.2 page 109 Variance of an r.v.
   1. That means, how wide is its distribution?
   2. Example: compare the performance of stocks vs bonds from year to year. The expected values (means) of the returns may not be so different. (This is debated and depends, e.g., on what period you look at). However, stocks' returns have a much larger variance than bonds.
   3. {$ \sigma^2_X = VAR[X] = E[(X-m_X)^2] = \sum (x-m_x)^2 p_X(x) $}
   4. standard deviation {$ \sigma_X = \sqrt{VAR[X]} $}
   5. {$ VAR[X] = E[X^2] - m_X^2 $}
   6. 2nd moment: {$ E[X^2] $}
   7. also 3rd, 4th... moments, like a Taylor series for probability
   8. shifting the distribution: VAR[X+c] = VAR[X] ''(corrected from VAR[c])''
   9. scaling: {$ VAR[cX] = c^2 VAR[X] $}
2. Derive variance for Bernoulli.
3. Example 3.20 3 coin tosses
   1. general rule for binomial: VAR[X]npq
   2. Derive it.
   3. Note that it sums since the events are independent.
   4. Note that variance/mean shrinks as n grows.
4. iclicker: The experiment is drawing a card from a deck, seeing if it's hearts, putting it back, shuffling, and repeating for a total of 100 times. The random variable is the total # of hearts seen, from 0 to 100. What's the mean of this r.v.?
   • A: 1/4
   • B: 25
   • C: 1/2
   • D: 50
   • E: 1
5. iclicker: The experiment is drawing a card from a deck, seeing if it's hearts, putting it back, shuffling, and repeating for a total of 100 times. The random variable is the # of hearts seen, from 0 to 100. What's the variance of this r.v.?
   • A: 3/16
   • B: 1
   • C: 25/4
   • D: 75/4
   • E: 100
6. Example 3.22 Variance of geometric r.v. We'll derive it.
7. 3.4 page 111 Conditional pmf
8. Example 3.23 random clock - skip
9. Example 3.24 Residual waiting time
   1. X, time to xmit message, is uniform in 1...L.
   2. If X is over m, what's probability that remaining time is j?
   3. {$ p_X(m+j|X>m) = \frac{P[X =m+j]}{P[X>m]} = \frac{1/L}{(L-m)/L} = 1/(L-m) $}
10. {$ p_X(x) = \sum p_X(x|B_i) P[B_i] $}
11. Example 3.25 p 113 device lifetimes
    1. 2 classes of devices, geometric lifetimes.
    2. Type 1, probability {$\alpha$}, parameter r. Type 2 parameter s.
    3. What's pmf of the total set of devices?
12. Example 3.26.
13. 3.5 More important discrete r.v
14. Table 3.1: We haven't seen {$ G_X(z) $} yet.
15. 3.5.4 Poisson r.v.
    1. The experiment is observing how many of a large number of rare events happen in, say, 1 minute.
    2. E.g., how many cosmic particles hit your DRAM, how many people to call center.
    3. The individual events are independent.
    4. The r.v. is the number that happen in that period.
    5. There is one parameter, {$\alpha$}. Often this is called {$\lambda$}.
    6. {$$ p(k) = \frac{\alpha^k}{k!}e^{-\alpha} $$}
    7. Mean and std dev are both {$\alpha$}.

1. Correction: Variance of shifted r.v.: VAR[X+c] = VAR[X]
2. Hang Zhang's office hours are: Mon 7:10-8pm (or as long as people are there asking questions), and Wednesday at 10:00-11:10am in ECSE flip flop lounge.
3. Poisson r.v. continued.
4. Poisson approximates binomial for fixed np as {$n\rightarrow\infty $} . I'll try to prove this. One useful approximation is this: {$ (1-x)^a \rightarrow e^{-ax} $} as {$ x\rightarrow 0 $} You can prove it, with some work, from the following equation: {$ e^x = \sum_i \frac{x^i}{i!} $}
5. Proof that Poisson mean is {$ \alpha $}
6. Since its variance is also {$ \alpha $}, about 2/3 of the time, {$ \mu-\sigma < x < \mu + \sigma $} so {$ \alpha-\sqrt{\alpha} < x < \alpha+\sqrt{\alpha} $}
7. Poisson example 3.30 p 122 call center queries; Probability of over 4 calls in 10 seconds.
8. Example 3.31 packet arrivals: Probability of no packets in a particular interval.
9. Example 3.32 Optical transmission errors.
10. iclicker: Your home page gets on average 1 hit per hour. The number of hits per 25 hours with about 2/3 probability is in the following range:
    • -4 to 6
    • 0 to 2
    • 0 to 50
    • 20 to 30
    • 24 to 26
11. Section 3.5.5 Discrete uniform r.v. - We'll derive the mean and variance.
12. Zipf r.v.
    1. {$ p(k) = c/k $} where c is chosen to make {$ \sum_{k=1}^L p(k)=1 $}
    2. L is important because summing to {$ \infty $} slowly diverges. That is, it keeps increasing, proportional to {$ \ln n $} .
    3. The population of the i-th largest city is said to follow this.
    4. This may apply to other statistics, like the sales of the i-th most popular book on Amazon.
    5. I used weasel words above because there is some argument about that, which is beyond this course.
    6. Zipf has a long tail because rare events, cumulatively, are more common than you'd think. (Again, some people dispute this.)
13. Example: Try Zipf on the 1000 most common words. For L=1000, c=1/7. (corrected).
14. iclicker: What's the probability of the most common word?
    • 1/1000
    • 1/100
    • 1/70
    • 1/7
    • 1/2
15. iclicker: What's the probability of the 10th most common word?
    • 1/1000
    • 1/100
    • 1/70
    • 1/7
    • 1/2
16. zeta r.v. - generalizes Zipf by adding exponent.
    1. {$ p(k) = c/k^\alpha $} where c is chosen to make {$ \sum_{k=1}^L p(k)=1 $}
    2. Sum to infinity exists for {$ \alpha>1 $}
    3. Mean exists for {$ \alpha>2 $}, variance exists for {$ \alpha>3 $}
    4. This is an example of a perfectly well defined probability distribution whose moments may not exist.
17. Review questions
    1. Sampling with replacement with ordering: Each day I eat lunch at either the Union, Mcdonalds, Brueggers, or Sage. How many ways can I eat lunch over 5 days next week?
    2. sampling w/o replacement and w/o order: How many different possible teams of 3 people can you pick from a group of 5?
    3. sampling w/o replacement and with order: 5 people run a race for gold, silver, bronse. How many ways can the medals be won, w/o any ties?
    4. binomial: A coin falls heads with p=.6. You toss it 3 times. What's the probability of 2 heads and 1 tail?
    5. multinomial: You play 38-slot roulette 3 times. Once you got red, once black and once 0 or 00. What was the probability?
    6. conditional probability: You have 2 dice, one 6-sided and one 12-sided. You pick one of them at random and throw it w/o looking; the top is 2. What's the probability that you threw the 6-sided die?
    7. What's the expected number of times you'll have to toss the unknown die to get your first 2?
18. Special office hour: On Thurs 2/24, Hang will be in the flip flop lounge from 7 to 8pm. As always, I will also be available after Friday class, and Hang will be available Monday 7:10-8pm in the FF loung.

1. I post announcements at the top of the this web page, before moving them to the current day.
2. Last year's 1st midterm exam is here: Exam1
3. The different counting formulae for selecting k items from n.
   1. With replacement; order matters: {$ n^k $}.
   2. W/o replacement; order matters: {$ n(n-1)\cdots(n-k+1) = \frac{n!}{(n-k)!} $}.
   3. With replacement; order does not matter: {$ {{n-1+k} \choose k} $} (corrected; thanks Bryan). See page 47 in the text.
   4. W/o replacement; order does not matter: {$ {n\choose k}=\frac{n!}{k!(n-k)!} $}.
4. More review:
   1. Independence: Consider {1,2,3,...12}. Is the set of even numbers independent of the set of multiples of 3? What if we use {1,2,..10}?
5. iclicker
   We often add a check bit to an 8-bit byte, and set it so there are an odd number of 1 bits. When we read the byte, which is now 9 bits, if there are an even number of 1s, then we know that there was an error.
   Assume that the probability of any one bit going bad is 1e-10. (The real number is much smaller.)
   What is the probability of the byte going bad (within 1 significant digit)?
   • 1e-10
   • 8e-10
   • 9e-10
   • 3.6e-19
   • 7.2e-19
   What is the probability of the byte going bad, but we don't notice that (because there were 2 bad bits)?
   • 1e-10
   • 8e-10
   • 9e-10
   • 3.6e-19
   • 7.2e-19
6. Several review questions from the book.
   1. 2.83 on page 90.
   2. 2.99.
   3. 3.5 on page 130.
   4. 3.9.
   5. 3.15.
   6. 3.26.
   7. 3.88 on page 139.