Counting and Discrete Probability

If task 1 can be done in n1 ways and task 2 in n2 ways, then doing them in sequence can be done in n1⋅n2n_1\cdot n_2 ways

Factorials: Arranging n distinct objects in order using the multiplication rule, but shrinking by subtracting one additional for each factor →n!n!

Permutations: Arrangement of r items chosen from n distinct items where order does matter → P(n,r)=n!(n−r)!P\left(n,r_{}\right)=\frac{n!}{\left(n-r\right)!}

Combinations: Arrangement of r items chosen from n distinct items where order does not matter → n!r!(n−r)!=P(n,r)r!\frac{n!}{r!\left(n-r\right)!}=\frac{P\left(n,r\right)}{r!}

Probability

  • Sample Space: Set of possible outcomes

  • Event: Subset of outcomes

Exclusivity and Independence are not the same

Cumulative Distribution Function (CDF): Essentially a percentile; probability that a discrete random variable equals a specific value P(X=x)

Probability Mass Function (PMF): Cumulative probability that a random variable is less than or equal to a specific value P(X<=x)


Expected Value

  • E[X]=μ=∑x⋅p(x)E\left\lbrack X\right\rbrack=\mu=\sum x\cdot p\left(x\right)

  • Probability Weighted Average

  • Also known as the long-run average

  • Running Average converges over time towards the expected value

  • A sequence of squares is calculated by n(n+1)(2n+1)6\frac{n\left(n+1\right)\left(2n+1\right)}{6}

Variance

  • E[(x−E[x])2]=∑(x−n)2⋅p(x)=E[x2]−(E[x])2=E[x2]−μ2E\left\lbrack\left(x-E\left\lbrack x\right\rbrack\right)^2\right\rbrack=\sum\left(x-n\right)^2\cdot p\left(x\right)=E\left\lbrack x^2\right\rbrack-\left(E\left\lbrack x\right\rbrack\right)^2=E\left\lbrack x^2\right\rbrack-\mu^2

  • Expected squared distance from the mean

  • Variance is in squared units

  • Standard deviation is in the same units as the mean


If x and y are discrete random variables, what is E[x+y]? E[x]+E[y]

If x and y are independent random variables, what is var(x+y)? var(x)+var(y)

If x and y are independent random variables, what is var(x+c)? var(x)

If x and y are independent random variables, what is var(ax)? a²var(x)

If we have 10 boxes, how many ways can we put 3 items in the boxes (one per box) 10!3!⋅7!\frac{10!}{3!\cdot7!}


The Binomial Distribution

If x is the # of successes in these trials, then x=x1+x2+x3x=x_1+x_2+x_3 where xix_{i} are samples of a Bernoulli random variable

Bernoulli Random Variable: A discrete random variable with only two possible outcomes.

  • Expected value = p

  • Variance = p(1-p)

Newton’s Binomial

Chebyshev’s Inequality holds for any random variable with finite mean and variance