CS70 Guide
  • This site is now deprecated
  • LaTeX Reference
  • Discrete Math
    • Overview
    • Propositional Logic
    • Proofs
    • Stable Matching
    • Graphs
    • Modular Arithmetic
    • RSA Cryptography
    • Polynomials
    • Countability
    • Computability
  • Probability
    • Overview
    • Counting
    • Discrete Probability
    • Hashing and the Union Bound
    • Expectation and Variance
    • Concentration Inequalities
    • Continuous Probability
    • Markov Chains
    • The Beta Family
    • The Gamma Family
    • Conditional Expectation and Variance
Powered by GitBook
On this page

Was this helpful?

  1. Probability

Overview

PreviousComputabilityNextCounting

Last updated 2 years ago

Was this helpful?

The probability section of this guide will likely never be fully completed, due to the fact that the is such an excellent resource in probability theory. Go read it and do the problems!

Instead of a full write-up, the pages in this section will typically just link to relevant sections from the textbook. Personally, I found everything I needed to do well in CS70 probability (and much more) here, including examples that are very similar to problems you might see on the homework.

TL;DR don't use this section of the guide, just read the 140 textbook.

Here is a running list of topics in this section:

  • provides us an intuitive method of figuring out how many possible ways there are to do something.

  • , such as the Binomial or Geometric distributions, describe the probabilities of a finite set of outcomes.

  • , such as the Poisson or Normal distributions, help us model real values, like lifetime or height.

  • model transitions between discrete states.

  • are tools to describe the characteristics of a random variable or distribution.

  • allow us to approximate bounds for random variables when we only know their expectation and/or variance.

There is far more to explore in learning the basics of probability- not everything is included in this list!

Reference

Distribution
Values
Density
Expectation
Variance
Links

Uniform(m,n)

[m, n]

Bernoulli(p)

Indicator

0, 1

P(X=1) = p

P(X=0) = 1-p

Binomial(n,p)

[0, n]

Geometric(p)

Hypergeom.(N,G,n)

[0, n]

Uniform Continuous

(a, b)

Beta(r,s)

(0, 1)

Normal(0,1)

0

1

Poisson()

Exponential()

(Gamma(1, ))

Gamma(r, )

Where (nk)=n!k!(n−k)!\binom{n}{k} = \frac{n!}{k!(n-k)!}(kn​)=k!(n−k)!n!​and Γ(r)=∫0∞xr−1e−xdx=(r−1)Γ(r−1)=(r−1)!\Gamma(r) = \int_0^\infty x^{r-1}e^{-x}dx = (r-1)\Gamma(r-1) = (r-1)!Γ(r)=∫0∞​xr−1e−xdx=(r−1)Γ(r−1)=(r−1)!

1n−m+1\frac{1}{n-m+1}n−m+11​
m+n2\frac{m+n}{2}2m+n​
(n−m+1)2−112\frac{(n-m+1)^2-1}{12}12(n−m+1)2−1​
ppp
p(1−p)p(1-p)p(1−p)
(nk)pkqn−k\binom{n}{k}p^kq^{n-k}(kn​)pkqn−k
npnpnp
np(1−p)np(1-p)np(1−p)
μ\muμ
x≥0x\ge0x≥0
e−μμkk!e^{-\mu}\frac{\mu^k}{k!}e−μk!μk​
μ\muμ
μ\muμ
x≥1x \ge 1x≥1
(1−p)kp(1-p)^kp(1−p)kp
1p\frac{1}{p}p1​
1−pp2\frac{1-p}{p^2}p21−p​
(Gg)(Bb)(Nn)\frac{\binom{G}{g}\binom{B}{b}}{\binom{N}{n}}(nN​)(gG​)(bB​)​
nGNn\frac{G}{N}nNG​
nGNBNN−nN−1n\frac{G}{N}\frac{B}{N}\frac{N-n}{N-1}nNG​NB​N−1N−n​
1b−a\frac{1}{b-a}b−a1​
a+b2\frac{a+b}{2}2a+b​
(b−a)212\frac{(b-a)^2}{12}12(b−a)2​
Γ(r+s)Γ(r)Γ(s)xr−1(1−x)s−1\frac{\Gamma(r+s)}{\Gamma(r)\Gamma(s)}x^{r-1}(1-x)^{s-1}Γ(r)Γ(s)Γ(r+s)​xr−1(1−x)s−1
rr+s\frac{r}{r+s}r+sr​
rs(r+s)2(r+s)\frac{rs}{(r+s)^2(r+s)}(r+s)2(r+s)rs​
λ\lambdaλ
λ\lambdaλ
x≥0x\ge0x≥0
λe−λx\lambda e^{-\lambda x}λe−λx
1λ\frac{1}{\lambda}λ1​
1λ2\frac{1}{\lambda^2}λ21​
λ\lambdaλ
x≥0x\ge0x≥0
λrΓ(r)xr−1eλx\frac{\lambda^r}{\Gamma(r)}x^{r-1}e^{\lambda x}Γ(r)λr​xr−1eλx
rλ\frac{r}{\lambda}λr​
rλ2\frac{r}{\lambda^2}λ2r​
x∈Rx \in \mathbb{R}x∈R
12πe−12x2\frac{1}{\sqrt{2\pi}}e^{-\frac{1}{2}x^2}2π​1​e−21​x2
Prob 140 textbook
Counting
Discrete probability distributions
Continuous probability distributions
Markov chains
Expectation and variance
Concentration inequalities
http://prob140.org/assets/final_reference_fa18.pdf