Basic terms
Sample space is the collection of all possible outcomes.
Events is a specific collection of outcomes.
Mutually exclusive indicates that the events are disjoint.
Collectively exhaustive indicates that the events cover the entire sample space. |
n-nomial Expansions, Theorems and Identities
(a+b)n = Sum over k (nCkakb(n-k)) where k goes from 0 to n
Binomial coeff. identity: nCk = (n-1)C(k-1) + (n-1)Ck where first term corresponds to A and second to AC
nCm = nCn-m
Sum over r (nCr(-1)r(1)(n+r) is 0 where r goes from 0 to n
Sum over r ((nCr)2) = 2nCn where r goes from 0 to n
Sum over s (sCm) = ^(n+1)C~(m+1) where s goes from m to n
Hypergeometric expansion: (n+m)Cr = nC0mCr + nC1mC(r-1) + ... + nCrmC0 which is a CE and ME enumeration
n! = (n/e)n x root(2n x pi) - Stirling's approx. for n!
Trinomial expansion: (a+b+c)n = sum over i, j, k (C'aibjck) where i, j, k go from 0 to n and i+j+k=n and C'=n!/(i!j!k!)
In an n-nomial expansion (a1 + ... + ar)n , the # of terms in the sum is rCn = (r+n-1)Cn = (r+n-1)C(r-1) |
|
|
Basics of set theory
S=entire sample space=A u AC where A = any subset of S
Null set (contains 0 members) = phi
SC=phi and phiC=S
(AC)C=A
A n B = A.B = AB for all x iff x in A and x in B
A u B = {x|x in A and/or x in B}
A - B = A n BC
If A and B are ME, A n B = phi
If events E1 to En are CE, then E1 u ... u En = S
Commutative law: A u B = B u A and A n B = B n A
Associative law : A u (B u C) = (A u B) u C, similarly for intersection
Distributive laws: A u (B n C) = (A u B) n (A u C) and A n (B u C) = (A n B) u (A n C)
A n phi = phi and A u phi = A
A n S = A = A n (B u BC)
A u B = A u (AC n B) = B u (BC n A)
A = B iff A is a subset of B and vice versa |
Formulations of Probability
0<=P(E)<=1
P(S)=1 where S is the entire sample space
For ME events A and B, P(A u B) = P(A) + P(B)
1 = P(S) = P(E u EC) = P(E) + P(EC)
Probabilities for ME events are equal
P(A n B) = P(A)P(B)
Inclusion-exclusion principle: P(E1 u ... u En) = (sum(P(Ei)) for i=1..n) - (sum(P(EiEi+1)) for i=1...n-1) +... +/- P(E1E2...En), ie: singles - pairs + triples - quadruples + ... +/- n-tuple |
|
|
Counting Principles
Sum rule for or cases and product rule for and cases
Permutations consider order, combinations do not
Permutations of n distinct objs. take k = nPk = (n!)/(n-k)!
Permutations of n distinct objs. take n w/ r groups of indistinct objs. = (n!)/(n1! ... nr!)
Combinations of n objs. take k = nCk = (n!)/((n-k)! * k!)
nPr = nr and nCr=(n+r-1)Cr : used for situations involving permutations and combinations of n objs. with replacement taken k at a time |
Conditional Probability
P(A|B) = P(AB)/P(B)
Bayes' Rule: P(A|B)=(P(B|A)P(A))/P(B)=(P(B|A)P(A))/(P(B|A)P(A) + P(B|AC)P(AC))
Conditional probability is not symmetric |
Hat Matching Problem
* n men throw their hats on the floor and each man randomly picks up his hat.
* If k men out of n draw their own hats, then the remaining men don't draw their own hats.
Hence, the probability of k men drawing their own hats (over all k-tuples) = (nCk(n-k)!)/n! = 1/k!
* P(k matches) = calculate the intersection probability using inclusion-exclusion principle and divide by k! |
|
|
Problem Patterns, Tips and Solutions
* Always sketch trees for problems involving product rule, with smaller use cases
* 5-card draw poker:
If the number of cards is n (usually 52), total # of ways of drawing 5 cards is nC5.
Number of ways to pick one card value = 13C1
Number of ways to pick k suits = 4Ck where k can go from 1 to 4.
* Balls and bins:
If there are n balls and r bins, there can be 2 scenarios:
- if the balls are distinguishable, each ball can go into any one of r bins. Thus the # of distinct permutations would be rPn = rn
- if the balls are indistinguishable, there will be 2 cases:
* No bin should be empty. Occupancy vector is x1+...+xr=n where every x is at least 1. In this case, there can be n-1 possible locations for bin separators from which we can choose r-1 to ensure at least 1 ball in each bin. # of possible arrangements = (n-1)C(r-1).
* A bin can have no balls. Then the occupancy vector would be y1+...+yr=n+r and the # of arrangements will be (n+r-1)C(r-1)
*Selecting committees:
Can be solved using product rule or hypergeometric approach.
*Drawing the only special ball from n balls in k trials:
Total outcomes = nCk = (1+(n-1))Ck = 1C0(n-1)Ck + 1C1(n-1)C(k-1) - the first term is for no special ball and the second term is for the special ball. Alternatively, we can calculate using a tree diagram.
*Bridge hands:
Remember: each hand has 13 cards.
*Roundtable arrangements:
If there are k people sitting at a roundtable, total # of arrangements is k!/k |
|
