Show Menu
Cheatography

Probability - Midterm Cheat Sheet (DRAFT) by

Covering counting principles, probability principles, Bayes theorem

This is a draft cheat sheet. It is a work in progress and is not finished yet.

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.
Collec­tively exhaustive indicates that the events cover the entire sample space.

n-nomial Expans­ions, 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 corres­ponds 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
Hyperg­eom­etric expansion: (n+m)Cr = nC0mCr + nC1mC(r-1) + ... + nCrmC0 which is a CE and ME enumer­ation
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
Commut­ative law: A u B = B u A and A n B = B n A
Associ­ative law : A u (B u C) = (A u B) u C, similarly for inters­ection
Distri­butive 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

Formul­ations of Probab­ility

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)
Probab­ilities for ME events are equal
P(A n B) = P(A)P(B)
Inclus­ion­-ex­clusion 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

Event Indepe­ndence

Two events are indepe­ndent if they don't influence one another
ie: P(AB) = P(A) x P(B)
 

Counting Principles

Sum rule for or cases and product rule for and cases
Permut­ations consider order, combin­ations do not
Permut­ations of n distinct objs. take k = nPk = (n!)/(­n-k)!
Permut­ations of n distinct objs. take n w/ r groups of indistinct objs. = (n!)/(n1! ... nr!)
Combin­ations of n objs. take k = nCk = (n!)/(­(n-k)! * k!)
nPr = nr and nCr=(n+r-1)Cr : used for situations involving permut­ations and combin­ations of n objs. with replac­ement taken k at a time

Condit­ional Probab­ility

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))
Condit­ional probab­ility is not symmetric. All probab­ilities are condit­ional since the definition of everything must be accounted for
Parameter restri­ction gives smaller sample space S'. S' is a subset of S, hence P(S') < P(S) = 1.
Condit­ional probab­ilities should sum up to unity in the reduced sample space, thus re-nor­malize all probab­ilities by dividing by P(S')
Condit­ional probab­ility is asymme­tric: P(A|B) != P(B|A).
Use tree repres­ent­ation for condit­ional probab­ility.

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 probab­ility of k men drawing their own hats (over all k-tuples) = (nCk(n-k)!)/n! = 1/k!
* P(k matches) = calculate the inters­ection probab­ility using inclus­ion­-ex­clusion 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 distin­gui­shable, each ball can go into any one of r bins. Thus the # of distinct permut­ations would be rPn = rn
- if the balls are indist­ing­uis­hable, 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 arrang­ements = (n-1)C(r-1).
* A bin can have no balls. Then the occupancy vector would be y1+...+yr=n+r and the # of arrang­ements will be (n+r-1)C(r-1)
*Selecting commit­tees:
Can be solved using product rule or hyperg­eom­etric 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. Altern­ati­vely, we can calculate using a tree diagram.
*Bridge hands:
Remember: each hand has 13 cards.
*Round­table arrang­ements:
If there are k people sitting at a roundt­able, total # of arrang­ements is k!/k