Math 300 , Spring 2004, Day 12, F, Feb 27 After classHit reload to get most current version

Multinomial coefficient (Derivation 2) calculated using the same pattern as the binomial:
 # of rearrangements of x A's, y B's, z C's, w D's.  x+y+z+w = n
Choose the x places to put A's in:  nCx ways.  Now there are n-x free places.
Choose the y places to put B's in: (n-x)Cy ways. There are n-x-y free places.
Choose the z places to put C's in:  (n-x-y)Cz ways  There are n-x-y-z = w free places.
Choose the w places to put D's in:  (n-x-y-z)Cw ways = wCw = 1 way.
Multiply these for the value of the multinomial coefficient.
Write each as a ratio of factorials, and cancel:
    n!            (n-x)!          (n-x-y)!          (n-x-y-z)!                =                     n!
 x!(n-x)!   y!(n-x-y)!    z!(n-x-y-z)!     w!(n-x-y-z-w!)                        x!y!z!w!0!

More about Binomial Coefficients: (handout)
A)  (x+y)ⁿ has binomial coefficients in the expansion.  nCk x^ky^n-k.
  Use this to show that Binomial distribution satisfies the law  1 = P(0) +P(1) +.....+P(n) (Prob. of everything = 1)
            How? Let x = p, y = q.  Then 1 = (p + q)ⁿ = P(0) +P(1) +.....+P(n)
B) Pascal's triangle: Interactive Probability: Bernoulli Trials.
Each pair sums to the one below.   nCk = (n-1)C(k-1) + (n-1)Ck
Sum of paths argument:  number of paths to position (n,k) = sum of number of paths to 2 positions just above.  (For Discrete alums--a setup to an argument by induction)

Start here Monday
Geometric distribution:  How many flips to the first head? Applet: BinomialTimelineExperiment
Model.  Identical Bernoulli trials:  Continue till first Success.  (Note, not exactly independent because you quit at the first head, but probability of success on any single trial stays the same--is independent of number of trials.)
Y = # of trials.  Sample space: (1,2,3,4,..........)  A discrete but not finite sample space.  Do tree.
P(Y = y) = (1-p)^y-1p = q^y-1p  (the sequence FF....FS, y-1 failures followed by 1 success)
           Some books use W = # of failures before the first success.  Y = W+1.
Does it work? Do the probabilities sum to 1?  p + qp + q²p + q³p +.......= 1.
    See p. 36, Geometric Series, Finite Geometric Series . .  Know these!
"It takes at least y to get a success"  Prob = No success on first y-1. = q^y-1
" Success happened on or before y'th" =    p + qp + q²p + q³p + ...+ q^y-1p  = Finite Geometric Series .

Negative binomial (p. 52)  Same as Geometric, only number of trials till the r'th success (k'th in applet).  Formula for y trials:  The last in the string is S; before that are y-1 letters, of which r-1 are S's (and y-r are F's).  So that part is binomial.
P(Y = y) = (y-1)C(r-1) p^r-1q^y-r p = (y-1)C(r-1) p^rq^y-r     What are the possible values for y?
- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
Reading: Ash  pp. 51-2. Also Finite Geom. / Geometric Series, p. 36. Ahead, Poisson dist, sec 2-5, pp. 63-67
HW:
Multinomial: Ash: pp. 52ff.  For these, write out the formulas for the results.  Calculate if it's not too hard; or, if suitable, stick it into an appropriate applet.
1, 4, 7 (7 is Multinomial, with 5 outcomes.  See if you can figure out how to see it that way, before looking at the answer.)
Binomial coefficients,Pascal's triangle, and (x+y)ⁿ:
A.  Remember Day 5: We can now prove ( nC1-nC2+nC3-nC4+.....+ nCn = 1).  Hint: Let x = 1 and y = 1 and look at the expansion of (x-y)ⁿ . The inclusion/exclusion theorem, for P(A or B or C....), is used in problem 7d, p. 52, assigned today.
B.  Pascal's triangle:  a) Complete the row for n = 8, using the handout and the row for 7.  answers
b)  Use algebra/arithmetic to show nCk = (n-1)C(k-1) + (n-1)Ck.  Try for smallish numbers, n =6, k=4, etc.  See  if you can show it in the general case, using algebra.
c)  Starting with   (x+y)³ =   x³y⁰ + 3x²y¹ + 3x¹y² + x⁰y³, multiply by (x+y) and collect terms to get (x+y)⁴.  Notice which 3Ck terms you sum to get each 4Ck coefficient.  Check with triangle. This should give some insight into how/why the triangle works as it does.

Rest Will be assigned Monday. Da) is added to pre-class version of page.
C.  Geometric/Neg. Binomial:  a) Give closed (no "...") formula for " Success happened on or before y'th" =    p + qp + q²p + q³p + ...+ q^y-1p  = ?  Use the Finite Geometric Series .  b) Check that this plus P(no successes on first y) =1.

D.  a)Make a tree to model the Negative binomial with k=2 (wait for 2nd success), through 4 trials (it gets fat quickly!)
   Write out the sequences that lead to the 2nd success on the 4th trial:  SFFS is one.
     Convince yourself that  (y-1)C(r-1) p^r-1q^y-r p is the correct probability in this case.
 
b) Use Applet:NegativeBinomialExperiment to get the histogram for the Geometric distribution (k=1).  Copy, roughly,  the distributions when p = .2 and p = .8, on the same scale.  Note each probability is q times the previous one.
c) Use the applet as in b.  With k = 2, (wait for 2nd success) run the value for p back and forth (between .2 and 1) to see the distribution. Repeat with k= 3, 4, 5.  Write what the shape is like at the extremes and how it changes.

Freund problem sheet:
13, 15, 17
Ash p. 53, 16 (a,b,c are straightforward.  There are several ways of getting d.  The shortest is the trickiest.  For e, write down the favorable sequences and their probabilities.  Then you can use the Geometric Series.)
   17.  Make a tree of the fav's.