math

math

Distributions
Discrete
Bernoulli
Binomial
Poisson
Geometric
Continuous
Uniform
Exponential
Gaussian
Expectations & variance
Zoo of functions
Inequalities
Conditional probabilities
Limit theorems
Some problem types
First-step analysis
Counting in expectation
Max/min of $n$ RVs
Combinatorics
Markov chains
Puzzles
Birthday problem
Gambler’s ruin
Random walk
Coupon collector
Information-theoretic puzzles
Reservoir sampling
Secretary problem
Monty Hall
Longest run of heads
Throwing balls into bins
Path counting
Statistics
Maximum likelihood estimation
Bias & variance
Math things
Taylor series
Derivative rules
Handy equations
description
concept
memoryless, waiting
geometric, exponential
trials with success & failure
Bernoulli, binomial
large sample, average
CLT, approximately Gaussian
bound given only mean / variance
Markov / Chebyshev inequalities
estimating parameter from data
MLE, MAP, Bayesian update
update belief from evidence
Bayes rule
function of a RV
Jensen’s inequality
expected count of things
linearity + indicators
expected hitting time / return probability
first-step analysis, solve recurrence
Markov property (future depends only on present)
first-step analysis
Distributions
discrete
continuous
counting
binomial: how many successes in nnn trials?
Poisson: how many events in fixed window?
waiting
geometric: how many trials until first success?
exponential: how long until first event?
Discrete
Bernoulli
bernoulli RV X∼Bernoulli⁡(p)X\sim\operatorname{Bernoulli}(p)X∼Bernoulli(p) models a single trial with ppp probability of success
P(X=1)=p,P(X=0)=1−pP(X=1)=p,P(X=0)=1-pP(X=1)=p,P(X=0)=1−p
compact PMF form
P(X=x)=px(1−p)1−xP(X=x)=p^x(1-p)^{1-x}P(X=x)=px(1−p)1−x
E[X]=p\mathbb E[X]=pE[X]=p, Var[X]=p(1−p)\text{Var}[X]=p(1-p)Var[X]=p(1−p)​
proof
E[X]=1⋅p+0⋅(1−p)=p\mathbb E[X]=1\cdot p+0\cdot (1-p)=pE[X]=1⋅p+0⋅(1−p)=p​
E[X2]=12⋅p+02⋅(1−p)=p\mathbb E[X^2]=1^2\cdot p+0^2\cdot (1-p)=pE[X2]=12⋅p+02⋅(1−p)=p​
Var⁡[X]=E[X2]−E[X]2=p−p2=p(1−p)\operatorname{Var}[X]=\mathbb E[X^2]-\mathbb E[X]^2=p-p^2=p(1-p)Var[X]=E[X2]−E[X]2=p−p2=p(1−p)​
categorial RV generalizes Bernoulli from 2 to kkk outcomes
P(X=i)=piP(X=i)=p_iP(X=i)=pi​
each item iii is Bernoulli⁡(pi)\operatorname{Bernoulli}(p_i)Bernoulli(pi​), so E[Xi]=pi\mathbb E[X_i]=p_iE[Xi​]=pi​ and Var⁡(Xi)=pi(1−pi)\operatorname{Var}(X_i)=p_i(1-p_i)Var(Xi​)=pi​(1−pi​)​
handy techniques
indicator squaring: for any binary variable X∈{0,1}X\in\{0,1\}X∈{0,1}, X2=XX^2=XX2=X so E[X2]=E[X]\mathbb E[X^2]=\mathbb E[X]E[X2]=E[X]​
Binomial
binomial RV X∼Binomial⁡(n,p)X\sim\operatorname{Binomial}(n,p)X∼Binomial(n,p) is the sum of nnn independent Bernoulli(p)\text{Bernoulli}(p)Bernoulli(p) trials
X=∑i=1nXiX=\sum_{i=1}^n X_iX=∑i=1n​Xi​ where Xi∼Bernoulli⁡(p)X_i\sim\operatorname{Bernoulli}(p)Xi​∼Bernoulli(p)​
P(X=k)=(nk)pk(1−p)n−kP(X=k)=\binom nk p^k(1-p)^{n-k}P(X=k)=(kn​)pk(1−p)n−k
every sequence with kkk successes has the same probability pk(1−p)n−kp^k(1-p)^{n-k}pk(1−p)n−k, and there are (nk)\binom nk(kn​) such sequences
Binomial theorem
(a+b)n=∑k=0n(nk)akbn−k(a+b)^n=\sum_{k=0}^n\binom nk a^k b^{n-k}(a+b)n=k=0∑n​(kn​)akbn−k
we can verify that ∑kP(X=k)=1\sum_k P(X=k)=1∑k​P(X=k)=1​
∑k=0n(nk)pk(1−p)n−k=(p+(1−p))n=1n=1\begin{align*}
\sum_{k=0}^n\binom nk p^k(1-p)^{n-k}=(p+(1-p))^n=1^n=1
\end{align*}k=0∑n​(kn​)pk(1−p)n−k=(p+(1−p))n=1n=1​
E[X]=np\mathbb E[X]=npE[X]=np, Var[X]=np(1−p)\text{Var}[X]=np(1-p)Var[X]=np(1−p)​
proof
E[X]=E[∑i=1nXi]=∑i=1nE[Xi]=np\mathbb E[X]=\mathbb E\left[\sum_{i=1}^n X_i\right]=\sum_{i=1}^n\mathbb E[X_i]=npE[X]=E[∑i=1n​Xi​]=∑i=1n​E[Xi​]=np​
Var⁡[X]=Var⁡[∑i=1nXi]=∑i=1nVar⁡[Xi]=np(1−p)\operatorname{Var}[X]=\operatorname{Var}[\sum_{i=1}^nX_i]=\sum_{i=1}^n\operatorname{Var}[X_i]=np(1-p)Var[X]=Var[∑i=1n​Xi​]=∑i=1n​Var[Xi​]=np(1−p) (second equality follows because the XiX_iXi​ are independent)
handy techniques
decompose into Bernoulli and use linearity of expectation
decompose X2X^2X2 into cross-terms
X2=(∑iXi)2=∑iXi2+∑i≠jXiXjX^2=\left(\sum_i X_i\right)^2=\sum_i X_i^2+\sum_{i\neq j}X_iX_jX2=(i∑​Xi​)2=i∑​Xi2​+i=j∑​Xi​Xj​
this makes computing expectation easy (using the fact that Xi2=XiX_i^2=X_iXi2​=Xi​ for indicator variables)
E[X2]=∑iE[Xi]+∑i≠jE[XiXj]=nE[Xi]+n(n−1)E[XiXj]\mathbb E[X^2]=\sum_i\mathbb E[X_i]+\sum_{i\neq j}\mathbb E[X_iX_j]=n\mathbb E[X_i]+n(n-1)\mathbb E[X_iX_j]E[X2]=i∑​E[Xi​]+i=j∑​E[Xi​Xj​]=nE[Xi​]+n(n−1)E[Xi​Xj​]
Poisson
Poisson RV X∼Poisson⁡(λ)X\sim\operatorname{Poisson}(\lambda)X∼Poisson(λ) models the number of events in a fixed interval when they occur independently at an average rate of λ\lambdaλ over that interval
P(X=k)=λke−λk!P(X=k)=\frac{\lambda^ke^{-\lambda}}{k!}P(X=k)=k!λke−λ​
the number of events in interval of length ttt distributed as N(t)∼Poisson⁡(λt)N(t)\sim\operatorname{Poisson}(\lambda t)N(t)∼Poisson(λt)​
derivation using binomial limit: divide the fixed interval into nnn tiny time intervals, assuming it is small enough that at most one event occurs in each interval
then the total count is Binomial⁡(n,p)\operatorname{Binomial}(n,p)Binomial(n,p) with np=λnp=\lambdanp=λ​
P(X=k)=(nk)pk(1−p)n−k=n!k!(n−k)!(λn)n(1−λn)n−k=λkk!⋅n!(n−k)!nk⏟→1⋅(1−λn)n⏟→e−λ⋅(1−λn)−k⏟→1\begin{align*}
P(X=k) &=\binom nk p^k(1-p)^{n-k}\\
&= \frac{n!}{k!(n-k)!}\left(\frac\lambda n\right)^n\left(1-\frac\lambda n\right)^{n-k}\\
&= \frac{\lambda^k}{k!}\cdot\underbrace{\frac{n!}{(n-k)!n^k}}_{\to 1}\cdot\underbrace{\left(1-\frac\lambda n\right)^n}_{\to e^{-\lambda}}\cdot\underbrace{\left(1-\frac\lambda n\right)^{-k}}_{\to 1}
\end{align*}P(X=k)​=(kn​)pk(1−p)n−k=k!(n−k)!n!​(nλ​)n(1−nλ​)n−k=k!λk​⋅→1(n−k)!nkn!​​​⋅→e−λ(1−nλ​)n​​⋅→1(1−nλ​)−k​​​
E[X]=Var[X]=λ\mathbb E[X]=\text{Var}[X]=\lambdaE[X]=Var[X]=λ​
E[X]=λ\mathbb E[X]=\lambdaE[X]=λ is basically the definition of rate λ\lambdaλ​
sums of independent Poisson are Poisson, with rates that add
can be derived using MGF uniqueness
X+Y∼Poisson⁡(λ1+λ2)X+Y\sim\operatorname{Poisson}(\lambda_1+\lambda_2)X+Y∼Poisson(λ1​+λ2​)
Geometric
geometric RV X∼Geometric⁡(p)X\sim\operatorname{Geometric}(p)X∼Geometric(p) models the number of Bernoulli trials XXX until first success (inclusive), where each trial has ppp probability of success
P(X=k)=(1−p)k−1⋅pP(X=k)=(1-p)^{k-1}\cdot pP(X=k)=(1−p)k−1⋅p
the tail probability is a pure power of (1−p)(1-p)(1−p)​
P(X>k)=(1−p)kP(X>k)=(1-p)^kP(X>k)=(1−p)k
memoryless: P(X>m+n∣X>m)=P(X>n)P(X>m+n\mid X>m)=P(X>n)P(X>m+n∣X>m)=P(X>n)​
the fact that you’ve failed mmm times already is irrelevant
the geometric distribution is the only memoryless distribution on the positive integers   ⟺  \iff⟺ any discrete waiting-time distribution that is memoryless must be geometric
the geometric series looks like ∑k=0∞rk\sum_{k=0}^\infty r^k∑k=0∞​rk​
converges for ∣r∣<1\lvert r\rvert <1∣r∣<1 to 11−r\frac{1}{1-r}1−r1​, diverges otherwise
can try to remember this by checking that for r=2r=2r=2, ∑k=0∞1/2k→2\sum_{k=0}^\infty 1/2^k\to2∑k=0∞​1/2k→2​
sanity check: PMF sums to 1
∑k=1∞(1−p)k−1p=p∑i=0∞(1−p)i=p⋅11−(1−p)sum of geometric series=p⋅1p=1\begin{align*}
\sum_{k=1}^\infty (1-p)^{k-1}p &= p\sum_{i=0}^\infty (1-p)^i\\
&=p\cdot\frac{1}{1-(1-p)}&\text{sum of geometric series}\\
&=p\cdot \frac 1p\\
&= 1
\end{align*}k=1∑∞​(1−p)k−1p​=pi=0∑∞​(1−p)i=p⋅1−(1−p)1​=p⋅p1​=1​sum of geometric series​
expected wait time E[X]=1/p\mathbb E[X]=1/pE[X]=1/p​
direct solution: X=kX=kX=k means k−1k-1k−1 failures
E[X]=∑k=1∞k⋅P(X=k)\mathbb E[X]=\sum_{k=1}^\infty k\cdot P(X=k)E[X]=k=1∑∞​k⋅P(X=k)
a little tricky to solve but gives E[X]=1/p\mathbb E[X]=1/pE[X]=1/p​
solution based on first-step analysis: on the first flip, we succeed with probability ppp (X=1X=1X=1) and fail with probability 1−p1-p1−p, in which case we’re back to where we started (X=1+E[X]X=1+\mathbb E[X]X=1+E[X])
E[X]=p⋅1+(1−p)(1+E[X])\mathbb E[X]=p\cdot 1+(1-p)(1+\mathbb E[X])E[X]=p⋅1+(1−p)(1+E[X])
algebra then produces E[X]=1p\mathbb E[X]=\frac 1pE[X]=p1​​
intuition: every trial has ppp change of ending the process, so on average we need 1/p1/p1/p attempts
Var⁡(X)=1−pp2\operatorname{Var}(X)=\frac{1-p}{p^2}Var(X)=p21−p​​
as p→0p\to 0p→0, both mean and variance blow up
rare successes have high variability in waiting time
handy techniques
first-step analysis
re-index using i=k−1i=k-1i=k−1, turning ∑k=1∞\sum_{k=1}^\infty∑k=1∞​ to ∑i=0∞\sum_{i=0}^\infty∑i=0∞​​
Continuous
Uniform
uniform RV X∼Uniform⁡(a,b)X\sim\operatorname{Uniform}(a,b)X∼Uniform(a,b) on [a,b][a,b][a,b] means XXX is equally likely to be anywhere on the interval [a,b][a,b][a,b]​
E[X]=a+b2\mathbb E[X]=\frac{a+b}{2}E[X]=2a+b​​
E[X]=∫abx⋅1b−adx=1b−ab2−a22fundamental theorem of calc=(b−a)(b+a)2(b−a)=a+b2\begin{align*}
\mathbb E[X]&=\int_a^bx\cdot\frac{1}{b-a}dx\\
&=\frac{1}{b-a}\frac{b^2-a^2}{2}&\text{fundamental theorem of calc}\\
&=\frac{(b-a)(b+a)}{2(b-a)}\\
&=\frac{a+b}{2}
\end{align*}E[X]​=∫ab​x⋅b−a1​dx=b−a1​2b2−a2​=2(b−a)(b−a)(b+a)​=2a+b​​fundamental theorem of calc
Var⁡(X)=(b−a)212\operatorname{Var}(X)=\frac{(b-a)^2}{12}Var(X)=12(b−a)2​​
PDF
fX(x)=1b−afor a≤x≤bf_X(x)=\frac{1}{b-a}\quad\text{for }a\leq x\leq bfX​(x)=b−a1​for a≤x≤b
CDF
FX(x)={0x<ax−ab−aa≤x≤b1x>bF_X(x)=\begin{cases}
0&x<a\\
\frac{x-a}{b-a}&a\leq x\leq b\\
1&x>b
\end{cases}FX​(x)=⎩⎨⎧​0b−ax−a​1​x<aa≤x≤bx>b​
difference between two uniform distributions is triangular
the n+1n+1n+1 gaps between nnn uniform points are distributed the same way
Exponential
exponential RV X∼Exp⁡(λ)X\sim\operatorname{Exp}(\lambda)X∼Exp(λ) with rate λ\lambdaλ models waiting time until the next event, where events happen at an average rate of λ\lambdaλ per unit time
equivalently, waiting time until first event in a Poisson process with rate λ\lambdaλ​
fX(x)=λe−λx,x≥0f_X(x)=\lambda e^{-\lambda x},\quad x\geq 0fX​(x)=λe−λx,x≥0
tail formula (aka survival function)
P(X>x)=e−λxP(X>x)=e^{-\lambda x}P(X>x)=e−λx
memoryless: P(X>s+t∣X>s)=P(X>t)P(X>s+t\mid X>s)=P(X>t)P(X>s+t∣X>s)=P(X>t)​
the fact that you’ve waited for sss units of time already is irrelevant
the exponential is the only continuous distribution on [0,∞][0,\infty][0,∞] that is memoryless
continuous analog to the geometric: waiting time in continuous time
E[X]=1λ\mathbb E[X]=\frac 1\lambdaE[X]=λ1​, Var⁡(X)=1λ2\operatorname{Var}(X)=\frac{1}{\lambda^2}Var(X)=λ21​​
if events happen at rate λ\lambdaλ/unit time on average, then on average you need to wait 1/λ1/\lambda1/λ units of time between events
relation between Poisson and exponential
two equivalent statements
number of events in unit interval is Poisson⁡(λ)\operatorname{Poisson}(\lambda)Poisson(λ)​
inter-event time is Exp⁡(λ)\operatorname{Exp}(\lambda)Exp(λ)​
how many events in the next hour? → Poisson
how long until the next event? → exponential
minimum of exponentials: if X1∼Exp⁡(λ1)X_1\sim\operatorname{Exp}(\lambda_1)X1​∼Exp(λ1​) and X2∼Exp⁡(λ2)X_2\sim\operatorname{Exp}(\lambda_2)X2​∼Exp(λ2​) are independent, then
min⁡(X1,X2)∼Exp⁡(λ1+λ2)\min(X_1,X_2)\sim\operatorname{Exp}(\lambda_1+\lambda_2)min(X1​,X2​)∼Exp(λ1​+λ2​)
intuition: if emails arrive at rate λ1\lambda_1λ1​ and texts at rate λ2\lambda_2λ2​, then the waiting time for “either an email or a text” is exponential with rate λ1+λ2\lambda_1+\lambda_2λ1​+λ2​​
proof
P(min⁡(X1,X2)>t)=P(X1>t and X2>t)=P(X1>t)P(X2>t)independence=e−λ1te−λ2t=e−(λ1+λ2)t\begin{align*}
P(\min(X_1,X_2)>t)&=P(X_1>t\text{ and }X_2>t)\\
&=P(X_1>t)P(X_2>t)&\text{independence}\\
&=e^{-\lambda_1 t}e^{-\lambda_2t}\\
&=e^{-(\lambda_1+\lambda_2) t}
\end{align*}P(min(X1​,X2​)>t)​=P(X1​>t and X2​>t)=P(X1​>t)P(X2​>t)=e−λ1​te−λ2​t=e−(λ1​+λ2​)t​independence
which is the tail function of Exp⁡(λ1+λ2)\operatorname{Exp}(\lambda_1+\lambda_2)Exp(λ1​+λ2​)​
Gaussian
Gaussian RV X∼N(μ,σ2)X\sim \mathcal N(\mu,\sigma^2)X∼N(μ,σ2) with mean μ\muμ and variance σ2\sigma^2σ2​
relationship between general and standard normal RV
subtract the mean to shift to 0, divideå by standard dev to rescale to unit variance
Z=X−μσ∼N(0,1)Z=\frac{X-\mu}{\sigma}\sim N(0,1)Z=σX−μ​∼N(0,1)
example: if heights are normally distributed with μ=70\mu=70μ=70 and σ=3\sigma=3σ=3, what fraction of people are taller than 76 inches?
X∼N(70,9)  ⟹  Z=X−703∼N(0,1)P(X>76)=P(Z>2)X\sim\mathcal N(70,9)\implies Z=\frac{X-70}{3}\sim\mathcal N(0,1)\\
P(X>76)=P(Z>2)X∼N(70,9)⟹Z=3X−70​∼N(0,1)P(X>76)=P(Z>2)
the percentile zαz_\alphazα​ is the value such that
P(Z≤zα)=α  ⟺  P(Z>zα)=1−αP(Z\leq z_\alpha)=\alpha\iff P(Z> z_\alpha)=1-\alphaP(Z≤zα​)=α⟺P(Z>zα​)=1−α
i.e., zαz_\alphazα​ is the point on the axis with probability mass α\alphaα to the left
symmetry: z1−α=−zαz_{1-\alpha}=-z_\alphaz1−α​=−zα​​
2-sided intervals: P(∣Z∣≤z1−α/2)=1−α  ⟺  P(∣Z∣>z1−α/2)=αP(\lvert Z\rvert\leq z_{1-\alpha/2})=1-\alpha\iff P(\lvert Z\rvert > z_{1-\alpha/2})=\alphaP(∣Z∣≤z1−α/2​)=1−α⟺P(∣Z∣>z1−α/2​)=α​
a (1−α)(1-\alpha)(1−α) confidence interval uses zα/2z_{\alpha/2}zα/2​ and z1−α/2z_{1-\alpha/2}z1−α/2​ as endpoints
stated as bounds: P(∣Z∣≤c)≥1−α  ⟺  c≥z1−α/2P(\lvert Z\rvert\leq c)\geq 1-\alpha\iff c\geq z_{1-\alpha/2}P(∣Z∣≤c)≥1−α⟺c≥z1−α/2​​
this also means that for X∼N(μ,σ2)X\sim\mathcal N(\mu,\sigma^2)X∼N(μ,σ2), the α\alphaα-percentile is xα=μ+σ⋅zαx_\alpha=\mu+\sigma\cdot z_\alphaxα​=μ+σ⋅zα​​
P(X≤xα)=P(Z≤xα−μσ)=α  ⟹  zα=xα−μσ  ⟹  xα=μ+σ⋅zαP(X\leq x_\alpha)=P\left(Z\leq \frac{x_\alpha-\mu}{\sigma}\right)=\alpha\implies z_\alpha=\frac{x_\alpha-\mu}{\sigma}\implies x_\alpha=\mu+\sigma\cdot z_\alphaP(X≤xα​)=P(Z≤σxα​−μ​)=α⟹zα​=σxα​−μ​⟹xα​=μ+σ⋅zα​
sum of independent Gaussians is Gaussian: if X1∼N(μ1,σ12)X_1\sim \mathcal N(\mu_1,\sigma_1^2)X1​∼N(μ1​,σ12​) and X2∼N(μ2,σ22)X_2\sim \mathcal N(\mu_2,\sigma_2^2)X2​∼N(μ2​,σ22​), then
X1+X2∼N(μ1+μ2,σ12+σ22)X_1+X_2\sim\mathcal N(\mu_1+\mu_2,\sigma_1^2+\sigma_2^2)X1​+X2​∼N(μ1​+μ2​,σ12​+σ22​)
Expectations & variance
expectation
E[X]=∑xx P(X=k)or∫−∞∞x f(x) dx\mathbb E[X]=\sum_x x\,P(X=k)\quad\text{or}\quad \int_{-\infty}^\infty x\, f(x)\,dxE[X]=x∑​xP(X=k)or∫−∞∞​xf(x)dx
expectation of a function over XXX​
E[g(X)]=∑xg(x) P(X=x)or∫−∞∞g(x) f(x) dx\mathbb E[g(X)]=\sum_x g(x)\,P(X=x)\quad\text{or}\quad \int_{-\infty}^\infty g(x)\,f(x)\, dxE[g(X)]=x∑​g(x)P(X=x)or∫−∞∞​g(x)f(x)dx
tail formula for non-negative RVs
E[X]=∫0∞P(X>x) dx=∫0∞1−F(x) dx\mathbb E[X]=\int_{0}^\infty P(X>x)\,dx=\int_{0}^\infty 1-F(x)\,dxE[X]=∫0∞​P(X>x)dx=∫0∞​1−F(x)dx
variance
Var⁡(X)=E[(X−E[X])2]=E[X2]−(E[X])2\begin{align*}
\operatorname{Var}(X)&=\mathbb E[(X-\mathbb E[X])^2]\\
&= \mathbb E[X^2]-(\mathbb E[X])^2
\end{align*}Var(X)​=E[(X−E[X])2]=E[X2]−(E[X])2​
linearity of expectation (regardless of independence)
E[aX+bY+c]=aE[X]+bE[Y]+c\mathbb E[aX+bY+c]=a\mathbb E[X]+b\mathbb E[Y]+cE[aX+bY+c]=aE[X]+bE[Y]+c
for independent XXX and YYY​
E[XY]=E[X]E[Y]\mathbb E[XY]=\mathbb E[X]\mathbb E[Y]E[XY]=E[X]E[Y]
if XXX and YYY are independent, then
Var⁡(X+Y)=Var⁡(X)+Var⁡(Y)\operatorname{Var}(X+Y)=\operatorname{Var}(X)+\operatorname{Var}(Y)Var(X+Y)=Var(X)+Var(Y)
Zoo of functions
probability mass function (PMF) of discrete RVs
p(k)=P(X=k)p(k)=P(X=k)p(k)=P(X=k)
properties
p(k)≥0p(k)\geq 0p(k)≥0​
∑kp(k)=1\sum_k p(k)=1∑k​p(k)=1​
probability density function (PDF) of continuous RVs
f(x) such that P(a≤x≤b)=∫abf(x) dxf(x)\text{ such that }P(a\leq x\leq b)=\int_a^b f(x)\, dxf(x) such that P(a≤x≤b)=∫ab​f(x)dx
differentiate CDF to get PDF: f(x)=F′(x)f(x)=F'(x)f(x)=F′(x)​
cumulative distribution function (CDF) for both discrete and continuous RVs
F(x)=P(X≤x)F(x)=P(X\leq x)F(x)=P(X≤x)
for discrete: F(x)=∑k≤xp(k)F(x)=\sum_{k\leq x} p(k)F(x)=∑k≤x​p(k)​
for continuous: F(x)=∫−∞xf(x) dxF(x)=\int_{-\infty}^x f(x)\, dxF(x)=∫−∞x​f(x)dx​
note P(a≤x≤b)=F(b)−F(a)P(a\leq x\leq b)=F(b)-F(a)P(a≤x≤b)=F(b)−F(a)​
Inequalities
Markov’s inequality: for any non-negative RV XXX and a>0a>0a>0,
P(X≥a)≤E[X]aP(X\geq a)\leq \frac{\mathbb E[X]}{a}P(X≥a)≤aE[X]​
intuitively, E[X]\mathbb E[X]E[X] cannot be smaller than the contribution of values greater than aaa​
proof
E[X]≥∑x≥axP(X=x)≥a∑x≥aP(X=x)=aP(X≥a)\mathbb E[X]\geq\sum_{x\geq a}xP(X=x)\geq a\sum_{x\geq a}P(X=x)=aP(X\geq a)E[X]≥x≥a∑​xP(X=x)≥ax≥a∑​P(X=x)=aP(X≥a)
Chebyshev’s inequality: for any RV XXX with mean μ\muμ and variance σ2\sigma^2σ2​
P(∣X−μ∣≥kσ)≤1k2P(\lvert X-\mu\rvert\geq k\sigma)\leq\frac{1}{k^2}P(∣X−μ∣≥kσ)≤k21​
at least 1−1/k21-1/k^21−1/k2 of the distribution lies within kkk standard deviations of the mean
e.g., 75% of probability mass sits within 2 standard deviations
proof: apply Markov to (X−μ)2(X-\mu)^2(X−μ)2​
P(∣X−μ∣≥kσ)=P((X−μ)2≥k2σ2)≤E[(X−μ)2]k2σ2=σ2k2σ2=1k2P(\lvert X-\mu\rvert\geq k\sigma)=P((X-\mu)^2\geq k^2\sigma^2)\leq \frac{\mathbb E[(X-\mu)^2]}{k^2\sigma^2}=\frac{\sigma^2}{k^2\sigma^2}=\frac{1}{k^2}P(∣X−μ∣≥kσ)=P((X−μ)2≥k2σ2)≤k2σ2E[(X−μ)2]​=k2σ2σ2​=k21​
another form, by substituting ϵ=kσ\epsilon=k\sigmaϵ=kσ​
P(∣X−μ∣≥ϵ)≤σ2ϵ2P(\lvert X-\mu\rvert\geq \epsilon)\leq\frac{\sigma^2}{\epsilon^2}P(∣X−μ∣≥ϵ)≤ϵ2σ2​
Jensen’s inequality describes how expectations interact with convex/concave transformations
φ convex  ⟹  φ(E[X])≤E[φ(X)]φ concave  ⟹  φ(E[X])≥E[φ(X)]\varphi\text{ convex}\implies \varphi(\mathbb E[X])\leq \mathbb E[\varphi(X)]\\
\varphi\text{ concave}\implies \varphi(\mathbb E[X])\geq \mathbb E[\varphi(X)]φ convex⟹φ(E[X])≤E[φ(X)]φ concave⟹φ(E[X])≥E[φ(X)]
to remember, use φ(x)=x2\varphi(x)=x^2φ(x)=x2 (convex) with X∈{−1,+1}X\in\{-1,+1\}X∈{−1,+1}​
φ(E[X])=φ(0)=0\varphi(\mathbb E[X])=\varphi(0)=0φ(E[X])=φ(0)=0​
E[φ(X)]=1\mathbb E[\varphi(X)]=1E[φ(X)]=1​
convex functions have φ′′≥0\varphi^{\prime\prime}\geq0φ′′≥0 everywhere (slope is increasing)
x2x^2x2, x4x^4x4, … (xnx^nxn for any even nnn)
∣x∣\lvert x\rvert∣x∣​
axa^xax (for a>1a>1a>1)
1/x1/x1/x (for x>0x>0x>0)
max⁡(x1,x2,…)\max(x_1,x_2,…)max(x1​,x2​,…)​
concave functions have φ′′≤0\varphi^{\prime\prime}\leq 0φ′′≤0 everywhere (slope is decreasing)
x\sqrt{x}x​​
log⁡x\log xlogx​
xpx^pxp for 0<p<10<p<10<p<1​
min⁡(x1,x2,…)\min(x_1,x_2,…)min(x1​,x2​,…)​
linear functions are both convex and concave
worth memorizing: log⁡E[X]≥E[log⁡X]\log\mathbb E[X]\geq\mathbb E[\log X]logE[X]≥E[logX]​
AM-GM inequality (arithmetic mean, geometric mean): arithmetic mean always ≥\geq≥ geometric mean
a1+⋯ann≤a1⋯ann\frac{a_1+\cdots a_n}{n}\leq \sqrt[n]{a_1\cdots a_n}na1​+⋯an​​≤na1​⋯an​​
proof: take log of both sides, apply Jensen’s inequality (using the fact that log is concave), then exponentiate both sides
Cauchy-Schwarz inequality
E[XY]2≤E[X2]E[Y2]\mathbb E[XY]^2\leq\mathbb E[X^2]\mathbb E[Y^2]E[XY]2≤E[X2]E[Y2]
another form
(∑i=1nxiyi)2≤(∑i=1nxi2)(∑i=1nyi2)\left(\sum_{i=1}^nx_iy_i\right)^2\leq\left(\sum_{i=1}^n x_i^2\right)\left(\sum_{i=1}^n y_i^2\right)(i=1∑n​xi​yi​)2≤(i=1∑n​xi2​)(i=1∑n​yi2​)
union bound
P(A1∪A2∪⋯∪An)≤P(A1)+P(A2)+⋯+P(An)P(A_1\cup A_2\cup\cdots\cup A_n)\leq P(A_1)+P(A_2)+\cdots +P(A_n)P(A1​∪A2​∪⋯∪An​)≤P(A1​)+P(A2​)+⋯+P(An​)
Conditional probabilities
suppose we have two random variables, XXX and YYY​
joint distribution: P(X=x,Y=y)P(X=x,Y=y)P(X=x,Y=y)​
marginal distribution: P(X=x)=∑yP(X=x,Y=y)P(X=x)=\sum_y P(X=x,Y=y)P(X=x)=∑y​P(X=x,Y=y)​
conditional distribution: P(X=x∣Y=y)P(X=x\mid Y=y)P(X=x∣Y=y)​
Bayes rule
P(A∣B)=P(B∣A)P(A)P(B)P(A\mid B)=\frac{P(B\mid A)P(A)}{P(B)}P(A∣B)=P(B)P(B∣A)P(A)​
P(A)P(A)P(A) is the prior (what we believed before seeing BBB)
P(A∣B)P(A\mid B)P(A∣B) is the posterior (what we believed after seeing BBB)
calculate P(B)P(B)P(B) with law of total probability
law of total expectation (also known as the tower property)
E[X]=∑yE[X∣Y=y]⋅P(Y=y)or∫−∞∞E[X∣Y=y]f(y) dy\mathbb E[X]=\sum_y\mathbb E[X\mid Y=y]\cdot P(Y=y)\quad\text{or}\quad\int_{-\infty}^\infty\mathbb E[X\mid Y=y]f(y)\,dyE[X]=y∑​E[X∣Y=y]⋅P(Y=y)or∫−∞∞​E[X∣Y=y]f(y)dy
can also be stated as E[X]=EY[E[X∣Y]]\mathbb E[X]=\mathbb E_Y[\mathbb E[X\mid Y]]E[X]=EY​[E[X∣Y]]​
note that in this statement, E[X∣Y]\mathbb E[X\mid Y]E[X∣Y] is itself RV expressed in terms of YYY​
law of total probability
P(A)=∑yP(A∣Y=y)⋅P(Y=y)P(A)=\sum_yP(A\mid Y=y)\cdot P(Y=y)P(A)=y∑​P(A∣Y=y)⋅P(Y=y)
Limit theorems
central limit theorem: mean of nnn iid RVs XiX_iXi​ with mean μ\muμ and variance σ2\sigma^2σ2 is Gaussian, no matter what the XiX_iXi​ look like
Xˉn=1n∑i=1nXi≈N(μ,σ2n)\bar X_n=\frac 1n\sum_{i=1}^n X_i\approx \mathcal N\left(\mu,\frac{\sigma^2}{n}\right)Xˉn​=n1​i=1∑n​Xi​≈N(μ,nσ2​)
derivation of variance
Var⁡(Xˉn)=Var⁡(1n∑i=1nXi)=1n2Var⁡(∑i=1nXi)=1n2∑i=1nVar⁡(Xi)=nn2σ2=σ2n\operatorname{Var}(\bar X_n)=\operatorname{Var}\left(\frac 1n\sum_{i=1}^n X_i\right)=\frac{1}{n^2}\operatorname{Var}\left(\sum_{i=1}^n X_i\right)=\frac{1}{n^2}\sum_{i=1}^n\operatorname{Var} (X_i)=\frac{n}{n^2}\sigma^2=\frac{\sigma^2}{n}Var(Xˉn​)=Var(n1​i=1∑n​Xi​)=n21​Var(i=1∑n​Xi​)=n21​i=1∑n​Var(Xi​)=n2n​σ2=nσ2​
standard error is the standard deviation of Xˉn\bar X_nXˉn​, which is σ/n\sigma/\sqrt nσ/n​​
what it means: error shrinks like n\sqrt nn​, need 100x samples to reduce error 10x
(1−α)(1-\alpha)(1−α) confidence interval is given by
Xˉn±z1−α/2⋅σn\bar X_n\pm z_{1-\alpha/2}\cdot\frac{\sigma}{\sqrt n}Xˉn​±z1−α/2​⋅n​σ​
law of large numbers: mean of nnn iid RVs XiX_iXi​ with mean μ\muμ converges to the true average
P(∣Xˉn−μ∣>ϵ)→0for any ϵ>0P(\lvert \bar X_n-\mu\rvert>\epsilon)\to0\quad\text{for any }\epsilon>0P(∣Xˉn​−μ∣>ϵ)→0for any ϵ>0
proof from Chebyshev’s (substitute ϵ=kσ\epsilon=k\sigmaϵ=kσ)
P(∣Xˉn−μ∣>ϵ)≤Var⁡(Xˉn)ϵ2=σ2nϵ2→0P(\lvert\bar X_n-\mu\rvert >\epsilon)\leq\frac{\operatorname{Var}(\bar X_n)}{\epsilon^2}=\frac{\sigma^2}{n\epsilon^2}\to0P(∣Xˉn​−μ∣>ϵ)≤ϵ2Var(Xˉn​)​=nϵ2σ2​→0
Some problem types
First-step analysis
what’s the expected number of coin flips to get two heads in a row?
let
E0E_0E0​ = expected flips to finish after just flipping tails (or just started)
E1E_1E1​ = expected flips after just flipping heads
E0=12(1+E0)⏟ tails, no progress+12(1+E1)⏟headsE_0=\underbrace{\frac 12 (1+E_0)}_\text{ tails, no progress}+\underbrace{\frac 12(1+E_1)}_\text{heads}E0​= tails, no progress21​(1+E0​)​​+heads21​(1+E1​)​​
E1=12(1+E0)⏟tails, start over+12⋅0⏟heads againE_1=\underbrace{\frac 12(1+E_0)}_\text{tails, start over}+\underbrace{\frac 12\cdot 0}_\text{heads again}E1​=tails, start over21​(1+E0​)​​+heads again21​⋅0​​
then solve system of linear equations to get E0=6E_0=6E0​=6​
first-step analysis trick: focus on the first step of the process, and express the expectations we want to solve for in terms of themselves. then solve system of linear equations.
Counting in expectation
how many things are expected to satisfy some property?
define Xi=1[item i has property]X_i=\mathbb 1[\text{item }i\text{ has property}]Xi​=1[item i has property] 
define a sum of indicator random variables N=∑iXiN=\sum_i X_iN=∑i​Xi​​
compute E[Xi]=P(Xi)\mathbb E[X_i]=P(X_i)E[Xi​]=P(Xi​) for each iii (use symmetry)
apply linearity of expectation: E[N]=∑iP(Xi)\mathbb E[N]=\sum_i P(X_i)E[N]=∑i​P(Xi​)​
examples: expected number of fixed points in a random permutation
by symmetry, position iii equally likely to have any item, so P(Xi=1)=1/nP(X_i=1)=1/nP(Xi​=1)=1/n​
Max/min of nnn RVs
if X1,…,XnX_1,…,X_nX1​,…,Xn​ are iid with common CDF FXF_XFX​​
for the max M=max⁡iXiM=\max_i X_iM=maxi​Xi​,
FM(x)=P(M≤x)=P(all Xi≤x)=[FX(x)]nF_M(x)=P(M\leq x)=P(\text{all }X_i\leq x)=[F_X(x)]^nFM​(x)=P(M≤x)=P(all Xi​≤x)=[FX​(x)]n
for the min m=min⁡iXim=\min_i X_im=mini​Xi​,
P(m>x)=P(every Xi>m)=[1−FX(x)]nFm(x)=1−P(m>x)P(m>x)=P(\text{every }X_i>m)=[1-F_X(x)]^n\\
F_m(x)=1-P(m>x)P(m>x)=P(every Xi​>m)=[1−FX​(x)]nFm​(x)=1−P(m>x)
two different approaches to calculate expectation of min or max
3-step recipe: CDF → PDF → integrate
for non-negative RVs, can use tail formula directly E[X]=∫0∞P(X>x) dx\mathbb E[X]=\int_{0}^\infty P(X>x)\,dxE[X]=∫0∞​P(X>x)dx​
let’s do this for Xi∼Uniform⁡[0,1]X_i\sim\operatorname{Uniform}[0,1]Xi​∼Uniform[0,1]​
max M=max⁡iXiM=\max_i X_iM=maxi​Xi​​
CDF: FM(x)=∏i=1nP(Xi≤x)=xnF_M(x)=\prod_{i=1}^n P(X_i\leq x)=x^nFM​(x)=∏i=1n​P(Xi​≤x)=xn​
PDF: fM(x)=ddxxn=nxn−1f_M(x)=\frac{d}{dx}x^n=nx^{n-1}fM​(x)=dxd​xn=nxn−1​
expectation: E[M]=∫01x⋅nxn−1 dx=n∫01xn dx=nn+1\mathbb E[M]=\int_0^1 x\cdot nx^{n-1}\,dx=n\int_0^1 x^n\,dx=\frac{n}{n+1}E[M]=∫01​x⋅nxn−1dx=n∫01​xndx=n+1n​​
intuition: nnn uniform points XiX_iXi​ split the segment into n+1n+1n+1 segments which are all equivalently distributed (by symmetry), so each must have mean length 1/(n+1)1/(n+1)1/(n+1)​
alternatively with tail formula: E[M]=∫01(1−xn) dx=x−xn+1n+1∣01=nn+1\mathbb E[M]=\int_0^1 (1-x^n)\,dx=x-\frac{x^{n+1}}{n+1}\rvert ^1_0=\frac{n}{n+1}E[M]=∫01​(1−xn)dx=x−n+1xn+1​∣01​=n+1n​​
min m=min⁡iXim=\min_i X_im=mini​Xi​​
P(m>x)=(1−x)nP(m>x)=(1-x)^nP(m>x)=(1−x)n​
CDF: Fm(x)=P(m≤x)=1−P(m≥x)=1−(1−x)nF_m(x)=P(m\leq x)=1-P(m\geq x)=1-(1-x)^nFm​(x)=P(m≤x)=1−P(m≥x)=1−(1−x)n​
PDF: fm(x)=ddxFm(x)=n(1−x)n−1f_m(x)=\frac{d}{dx} F_m(x)=n(1-x)^{n-1}fm​(x)=dxd​Fm​(x)=n(1−x)n−1​
expectation: E[m]=∫01x⋅n(1−x)n−1 dx=1n+1\mathbb E[m]=\int_0^1 x\cdot n(1-x)^{n-1}\,dx=\frac{1}{n+1}E[m]=∫01​x⋅n(1−x)n−1dx=n+11​​
for Xi∼Exponential⁡(λ)X_i\sim\operatorname{Exponential}(\lambda)Xi​∼Exponential(λ)​
min
P(m>x)=[P(Xi>x)]n=e−nλxP(m>x)=[P(X_i>x)]^n=e^{-n\lambda x}P(m>x)=[P(Xi​>x)]n=e−nλx​
E[m]=∫0∞e−nλx dx=1nλ\mathbb E[m]=\int_0^\infty e^{-n\lambda x}\,dx =\frac{1}{n\lambda}E[m]=∫0∞​e−nλxdx=nλ1​​
max is a lot more complicated, but good to know that it grows logarithmically with nnn​
for Xi∼N(0,1)X_i\sim\mathcal N(0,1)Xi​∼N(0,1), E[max⁡iXi]≈2ln⁡n\mathbb E[\max_iX_i]\approx\sqrt{2\ln n}E[maxi​Xi​]≈2lnn​ (this is pretty difficult to derive)
Combinatorics
combination: choosing kkk items from nnn, order doesn’t matter
(nk)=n!k!(n−k)!=P(n,k)k!\binom nk=\frac{n!}{k!(n-k)!}=\frac {P(n,k)}{k!}(kn​)=k!(n−k)!n!​=k!P(n,k)​
the relation to permutation: every set of kkk items can be arranged in k!k!k! orders, and combinations collapse the orderings into one
permutation: arranging kkk items from nnn, order matters
P(n,k)=n!(n−k)!P(n,k)=\frac{n!}{(n-k)!}P(n,k)=(n−k)!n!​
number of ways to arrange nnn objects when there are n1n_1n1​ of type 1, n2n_2n2​ of type 2, …
(nn1,...,nm)=n!n1!⋯nm!\binom{n}{n_1,...,n_m}=\frac{n!}{n_1!\cdots n_m!}(n1​,...,nm​n​)=n1​!⋯nm​!n!​
permute all nnn objects, the divide out the rearrangements of items within each type
a derangement is a permutation with no fixed points
combination with replacement: choosing kkk items from nnn types with replacement
(n+k−1k)\binom{n+k-1}{k}(kn+k−1​)
this is the stars and bars argument: each choice can be represented as a sequence of stars and bars, where there are kkk stars and n−1n-1n−1 bars → this is choosing kkk placements of stars from n+k−1n+k-1n+k−1 positions
how many ways are there to write non-negative integer nnn has sum of kkk non-negative integers?
visualize nnn stars with k−1k-1k−1 bars among them
order matters?
replacement?
count
yes
no
n!(n−k)!\frac{n!}{(n-k)!}(n−k)!n!​ (permutations)
no
no
(nk)\binom nk(kn​) (combinations)
yes
yes
nkn^knk​
no
yes
(n+k−1k)\binom{n+k-1}{k}(kn+k−1​) (stars and bars)
inclusion-exclusion principle
P(A∪B)=P(A)+P(B)−P(A∩B)P(A∪B∪C)=P(A)+P(B)+P(C)−P(A∩B)−P(A∩C)−P(B∩C)+P(A∩B∩C)P(A\cup B)=P(A)+P(B)-P(A\cap B)\\
P(A\cup B\cup C)=P(A)+P(B)+P(C)-P(A\cap B)-P(A\cap C)-P(B\cap C)+P(A\cap B\cap C)P(A∪B)=P(A)+P(B)−P(A∩B)P(A∪B∪C)=P(A)+P(B)+P(C)−P(A∩B)−P(A∩C)−P(B∩C)+P(A∩B∩C)
as counts
∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣\lvert A\cup B\cup C\rvert=\lvert A\rvert +\lvert B\rvert+\lvert C\rvert-\lvert A\cap B\rvert-\lvert A\cap C\rvert-\lvert B\cap C\rvert +\lvert A\cap B\cap C\rvert∣A∪B∪C∣=∣A∣+∣B∣+∣C∣−∣A∩B∣−∣A∩C∣−∣B∩C∣+∣A∩B∩C∣
Markov chains
Markov chain is a sequence of RVs X0,X1,X2,…X_0,X_1,X_2,…X0​,X1​,X2​,… taking values in some state space SSS satisfying the Markov property: the future depends only on the present
for finite state spaces, the chain is described by the transition matrix PPP where Pij=P(Xt+1=j∣Xt=i)P_{ij}=P(X_{t+1}=j\mid X_t=i)Pij​=P(Xt+1​=j∣Xt​=i)​
rows sum to 1 and are probability distributions over next-states
if πt\pi_tπt​ is the distribution over states at time ttt, then πt+1=πtP\pi_{t+1}=\pi_t Pπt+1​=πt​P​
a stationary distribution satisfies π=πP\pi=\pi Pπ=πP​
under mild conditions, the chain has a unique stationary distribution and πt→π\pi_t\to\piπt​→π regardless of where we started
the expected return time is the reciprocal of its stationary probability
E[return to state i]=1πi\mathbb E[\text{return to state }i]=\frac{1}{\pi_i}E[return to state i]=πi​1​
general principle to solve for expected absorption time
use first-step analysis to express the recurrence
expected time hjh_jhj​ to absorption from state jjj​
hA=0h_A=0hA​=0 for target absorbing state AAA​
hi=1+∑jPijhjh_i=1+\sum_jP_{ij}h_jhi​=1+j∑​Pij​hj​
probability of absorption qjq_jqj​ from state jjj​
qA=1q_A=1qA​=1 for desired absorbing state AAA, and qB=0q_B=0qB​=0 for all other absorbing states BBB​
qi=∑jPijqjq_i=\sum_jP_{ij}q_jqi​=j∑​Pij​qj​
solve recurrence
for small chains, can just solve the linear system
for chains with structure, guess a closed form and verify
to make an educated guess, compute the answer for small cases and try to generalize
think about what makes sense in terms of function shape
fit boundary conditions
handy techniques
symmetry can allow you to collapse equivalent states
for a random walk on a circle, easier to reparameterize hih_ihi​ to be expected hitting time from a particular distance rather than from a particular state
use stationary distribution to provide shortcuts for expected hitting time
on a graph where every node looks the same (cycles, complete graphs, etc.), expected hitting time hhh between adjacent vertices is always n−1n-1n−1 where nnn is the number of nodes
this is because E[return to self]=n\mathbb E[\text{return to self}]=nE[return to self]=n (since stationary distribution has 1/n1/n1/n everywhere)
and E[return to self]=1+h\mathbb E[\text{return to self}]=1+hE[return to self]=1+h because each of the ddd adjacent nodes contributes 1dh\frac1dhd1​h​
Puzzles
Birthday problem
how many people nnn does it take so that the probability of two people having the same birthday exceeds 50%?
P(collision)=1−P(all unique birthdays)P(\text{collision}) = 1 - P(\text{all unique birthdays})P(collision)=1−P(all unique birthdays)​
let ddd be number of days in the year and nnn the number of people
P(all unique birthdays)=dd⋅d−1d⋅d−2d⋯d−n+1d=d!(d−n)!⋅dnP(\text{all unique birthdays})=\frac{d}{d}\cdot\frac{d-1}{d}\cdot\frac{d-2}{d}\cdots\frac{d-n+1}{d}=\frac{d!}{(d-n)!\cdot d^n}P(all unique birthdays)=dd​⋅dd−1​⋅dd−2​⋯dd−n+1​=(d−n)!⋅dnd!​
Gambler’s ruin
you start with $aaa dollars
win $1 with probability ppp and lose $1 with probability 1−p1-p1−p​
stop when you reach $NNN (you win) or $0 (you’re ruined)
probability you reach $NNN?
let PiP_iPi​ be probability of reaching NNN starting from iii​
boundary conditions: P0=0,PN=1P_0=0,P_N=1P0​=0,PN​=1​
for any starting amount 0<i<N0<i<N0<i<N,
qi=p⋅qi+1+(1−p)⋅qi−1q_i=p\cdot q_{i+1}+(1-p)\cdot q_{i-1}qi​=p⋅qi+1​+(1−p)⋅qi−1​
second-order linear recurrence
when the game is fair, the probability of hitting NNN when starting at aaa is simply a/Na/Na/N​
approach 1: express expected value at stopping time in two different ways
let TTT be the stop time, and WTW_TWT​ be the wealth at time TTT​
we know E[WT]=a\mathbb E[W_T]=aE[WT​]=a (no drift)
we also know WTW_TWT​ is either 000 or NNN, so
E[WT]=qa⋅N+(1−qa)⋅0=qa⋅N\mathbb E[W_T]=q_a\cdot N+(1-q_a)\cdot 0=q_a\cdot NE[WT​]=qa​⋅N+(1−qa​)⋅0=qa​⋅N
combining these, we get qa=a/Nq_a=a/Nqa​=a/N​
approach 2: solve recurrence
qi=12qi−1+12qi+1  ⟹  qi+1−qi=qi−qi−1q_i=\frac 12 q_{i-1}+\frac 12 q_{i+1}\implies q_{i+1}-q_i=q_i-q_{i-1}qi​=21​qi−1​+21​qi+1​⟹qi+1​−qi​=qi​−qi−1​
all consecutive differences are equal → qiq_iqi​ is a linear function of iii​
with qi=0q_i=0qi​=0 and qN=1q_N=1qN​=1, we get qi=i/Nq_i=i/Nqi​=i/N​
this is a random walk with absorbing barriers at 000 and NNN​
in general, a martingale is a sequence of RVs M1,...,MnM_1,...,M_nM1​,...,Mn​ such that E[M1]=⋯=E[Mn]\mathbb E[M_1]=\cdots=\mathbb E[M_n]E[M1​]=⋯=E[Mn​]​
the expected absorption time hih_ihi​ is i(N−i)i(N-i)i(N−i)​
this is tricky to derive, but easy to verify by making sure it satisfies the recursive relationships given by first-step analysis
Random walk
simple symmetric random walk: let Sn=X1+⋯+XnS_n=X_1+\cdots +X_nSn​=X1​+⋯+Xn​ where each Xi=±1X_i=\pm 1Xi​=±1 with equal probability
obviously E[Sn]=E[Xi]=0\mathbb E[S_n]=\mathbb E[X_i]=0E[Sn​]=E[Xi​]=0​
each Xi=±1X_i=\pm 1Xi​=±1 has variance E[Xi2]−(E[Xi])2=1−0=1\mathbb E[X_i^2]-(\mathbb E[X_i])^2=1-0=1E[Xi2​]−(E[Xi​])2=1−0=1​
Var⁡(Sn)=∑i=1nVar⁡(Xi)=n\operatorname{Var}(S_n)=\sum_{i=1}^n\operatorname{Var}(X_i)=nVar(Sn​)=i=1∑n​Var(Xi​)=n
typical distance from origin (generally measured by standard deviation) grows like n\sqrt nn​​
in the biased case (Xi=1X_i=1Xi​=1 with ppp, else Xi=−1X_i=-1Xi​=−1)
E[Sn]=n(p⋅1+(1−p)⋅(−1))=n(2p−1)\mathbb E[S_n]=n(p\cdot 1+(1-p)\cdot (-1))=n(2p-1)E[Sn​]=n(p⋅1+(1−p)⋅(−1))=n(2p−1)
Coupon collector
nnn different types of coupons. every time you buy a cereal box, you get one coupon uniformly at random. in expectation, how much time does it take to collect all nnn coupons?
let phase kkk denote the phase in which we have kkk types
each phase Xk∼Geom⁡((n−k)/n)X_k\sim\operatorname{Geom}((n-k)/n)Xk​∼Geom((n−k)/n)​
the expected length of phase kkk is
E[Xk]=nn−k\mathbb E[X_k]=\frac{n}{n-k}E[Xk​]=n−kn​
total expected time
E[X]=∑k=0n−1E[Xk]=∑k=0n−1nn−k=n∑j=1n1j=n⋅Hn\mathbb E[X]=\sum_{k=0}^{n-1}\mathbb E[X_k]=\sum_{k=0}^{n-1}\frac{n}{n-k}=n\sum_{j=1}^n\frac 1j=n\cdot H_nE[X]=k=0∑n−1​E[Xk​]=k=0∑n−1​n−kn​=nj=1∑n​j1​=n⋅Hn​
where Hn=1+1/2+1/3+⋯+1/nH_n=1+1/2+1/3+\cdots+1/nHn​=1+1/2+1/3+⋯+1/n is the nnn-th harmonic number
final phase takes nnn boxes in expectation!
Information-theoretic puzzles
count the information
if we need to distinguish kkk possibilities and each test has mmm outcomes, then we need at least ⌈log⁡mk⌉\lceil\log_m k\rceil⌈logm​k⌉ tests
this is a lower bound
whether tests exist to achieve this bound depends on the constraints of the problem
9 coins, one is heavier, 2 weighings
divide into 3 groups of 3
left side heavy → counterfeit on left side
right side heavy → counterfeit on right side
balanced → counterfeit in the left-out set
then weigh 2 of the remaining 3
Reservoir sampling
we receive a stream of items: x1,x2,x3,…x_1,x_2,x_3,…x1​,x2​,x3​,… at the end of the stream, return a single item uniformly at random from all the items seen (length nnn of stream is not known ahead of time)
the algorithm
keep the first item: s=x1s=x_1s=x1​​
for n=2,3,4,…n=2,3,4,…n=2,3,4,…​
with probability 1/n1/n1/n, replace sss with xnx_nxn​​
proof of correctness by induction
claim: after processing nnn items, each of x1,…,xnx_1,…,x_nx1​,…,xn​ is stored in sss with probability 1/n1/n1/n​
base case (n=1)(n=1)(n=1): trivially, s=x1s=x_1s=x1​ with probability 1=1/11=1/11=1/1​
inductive step: after processing xnx_nxn​, there are two possible outcomes
s=xns=x_ns=xn​ (replace): this happens with probability 1/n1/n1/n​
s=xks=x_ks=xk​ for some k<nk<nk<n (keep): this requires (1) s=xks=x_ks=xk​ after step n−1n-1n−1, which has probability 1/(n−1)1/(n-1)1/(n−1) by induction, and that (2) we rejected xnx_nxn​, which has probability (n−1)/n(n-1)/n(n−1)/n​
 
1n−1⋅n−1n=1n\frac{1}{n-1}\cdot\frac{n-1}{n}=\frac 1nn−11​⋅nn−1​=n1​
thus every xkx_kxk​ is in the reservoir with probability 1/n1/n1/n after nnn steps
Secretary problem
problem: nnn candidates interviewed in random order, after each interview, decide immediately to hire or reject that candidate. our goal is to maximize probability of hiring the best candidate. we use the strategy: reject the first kkk candidates, then hire the next candidate better than all the first kkk (if no such candidate appears, hire the last one). what is the optimal kkk?
let P(k)=P(k)=P(k)= probability that strategy with threshold kkk hires the best candidate, let bbb be the position of the best candidate
for the strategy to succeed:
b>kb>kb>k: best candidate appears after the first kkk​
the best candidate among positions 1,…,b−11,…,b-11,…,b−1 is in 1,…,k1,…,k1,…,k (otherwise we hire someone before getting to bbb)
P(k)=∑b=k+1nP(best candidate at b)P(best among 1,...,b−1 appears ≤k)=∑b=k+1n1nkb−1=kn∑b=k+1n1b−1=kn∑i=kn−11i=kn(Hn−1−Hk−1)≈kn(log⁡(n−1)−log⁡(k−1))Hn≈log⁡n for large n≈knlog⁡nk=rlog⁡1rlet r=kn=−rlog⁡r\begin{align*}
P(k)&=\sum_{b=k+1}^n P(\text{best candidate at }b)P(\text{best among }1,...,b-1\text{ appears }\leq k)\\
&=\sum_{b=k+1}^n\frac 1n\frac{k}{b-1}\\
&=\frac kn\sum_{b=k+1}^n\frac{1}{b-1}\\
&=\frac kn\sum_{i=k}^{n-1}\frac{1}{i}\\
&=\frac kn(H_{n-1}-H_{k-1})\\
&\approx\frac kn(\log(n-1)-\log(k-1)) & H_n\approx \log n\text{ for large }n\\
&\approx\frac kn\log\frac nk\\
&=r\log \frac 1r&\text{let }r=\frac kn\\
&=-r\log r
\end{align*}P(k)​=b=k+1∑n​P(best candidate at b)P(best among 1,...,b−1 appears ≤k)=b=k+1∑n​n1​b−1k​=nk​b=k+1∑n​b−11​=nk​i=k∑n−1​i1​=nk​(Hn−1​−Hk−1​)≈nk​(log(n−1)−log(k−1))≈nk​logkn​=rlogr1​=−rlogr​Hn​≈logn for large nlet r=nk​​
taking the derivative, we see −ddrrlog⁡r=−log⁡r−1-\frac{d}{dr}r\log r=-\log r-1−drd​rlogr=−logr−1​
setting this to 0, we get log⁡r=−1  ⟹  r=1e  ⟹  k=ne\log r=-1\implies r=\frac 1e\implies k=\frac nelogr=−1⟹r=e1​⟹k=en​​
Monty Hall
let A∈{1,2,...,n}A\in\{1,2,...,n\}A∈{1,2,...,n} represent the car’s location and BBB be the set of doors Monty opens
we pick door ccc (without loss of generality)
we want P(A=j∣B)P(A=j\mid B)P(A=j∣B) for each unopened door jjj​
Bayes Theorem: P(A=j∣B)=P(B∣A=j)⋅P(A=j)P(B)P(A=j\mid B)=\frac{P(B\mid A=j)\cdot P(A=j)}{P(B)}P(A=j∣B)=P(B)P(B∣A=j)⋅P(A=j)​​
comparing P(A=j∣B)P(A=j\mid B)P(A=j∣B) for different jjj reduces to comparing P(B∣A=j)P(B\mid A=j)P(B∣A=j), because the prior P(A=j)=1/nP(A=j)=1/nP(A=j)=1/n is the same for all jjj and the denominator is shared
case 1: Monty opens n−2n-2n−2 doors, leaving our door and one other
denote with index rrr the one remaining door
P(B∣A=t)=1/(n−1)P(B\mid A=t)=1/(n-1)P(B∣A=t)=1/(n−1) because when your chosen door has the car, there are n−1n-1n−1 choices (i.e., n−1n-1n−1 choose n−2n-2n−2) for which door to leave closed
P(B∣A=r)=1P(B\mid A = r)=1P(B∣A=r)=1 because Monty is completely constrained in which set of doors he can open
P(B∣A=k)=0P(B\mid A=k)=0P(B∣A=k)=0 for all opened doors k∈Bk\in Bk∈B​
so the posteriors P(A=t∣B)∝1/(n−1)P(A=t\mid B)\propto 1/(n-1)P(A=t∣B)∝1/(n−1), P(A=r∣B)∝1P(A = r\mid B)\propto 1P(A=r∣B)∝1​
normalizing gives P(A=t∣B)=1/nP(A=t\mid B)=1/nP(A=t∣B)=1/n and P(A=r∣B)=(n−1)/nP(A = r\mid B)=(n-1)/nP(A=r∣B)=(n−1)/n​
case 2: Monty opens only 1 door
let rrr denote an arbitrary one of the remaining doors
P(B∣A=t)=1/(n−1)P(B\mid A=t)=1/(n-1)P(B∣A=t)=1/(n−1) because there are n−1n-1n−1 choices for which door to open
P(B∣A=r)=1/(n−2)P(B\mid A=r)=1/(n-2)P(B∣A=r)=1/(n−2) because there are n−2n-2n−2 choices for which door to open (every door except door ccc and door AAA is an option)
P(B∣A=k)=0P(B\mid A=k)=0P(B∣A=k)=0 where B={k}B=\{k\}B={k}​
so the posteriors P(A=t∣B)∝1/(n−1)P(A=t\mid B)\propto 1/(n-1)P(A=t∣B)∝1/(n−1) and P(A=r∣B)∝1/(n−2)P(A=r\mid B)\propto 1/(n-2)P(A=r∣B)∝1/(n−2)​
so the remaining doors are each slightly more likely
in general, the sum of probabilities of opened doors (k/nk/nk/n where kkk is the number of opened doors) is distributed onto the remaining unopened, unchosen doors (of which there are n−k−1n-k-1n−k−1)
Longest run of heads
we flip a fair coin nnn times and let LnL_nLn​ denote the longest run of consecutive heads
there is no clean closed form for E[Ln]\mathbb E[L_n]E[Ln​], but a well-known approximation is E[Ln]≈log⁡2(n)\mathbb E[L_n]\approx \log_2(n)E[Ln​]≈log2​(n)​
Throwing balls into bins
if we throw mmm balls into mmm bins uniformly, about 37% are empty, 37% get one ball, and the rest get two or more
Path counting
how many paths from (0,0)(0,0)(0,0) to (m,n)(m,n)(m,n) on a grid, where each step moves one unit right or one unit up?
every path consists of exactly mmm right-steps and nnn up-steps
a path is uniquely specified by choosing which of the m+nm+nm+n steps are right-steps
answer is (m+nm)\binom{m+n}{m}(mm+n​)​
how many of these paths pass through (a,b)(a,b)(a,b)?
multiply number of unique paths to (a,b)(a,b)(a,b) and number of unique paths from (a,b)(a,b)(a,b) to (m,n)(m,n)(m,n)​
(a+ba)⋅((m−a)+(n−b)m−a)\binom{a+b}{a}\cdot\binom{(m-a) + (n-b)}{m-a}(aa+b​)⋅(m−a(m−a)+(n−b)​)
Statistics
Maximum likelihood estimation
given data x1,…,xnx_1,…,x_nx1​,…,xn​ drawn from some distribution with unknown parameter θ\thetaθ​
maximum likelihood estimation: pick the θ\thetaθ that makes the observed data most probable
L(θ)=∏i=1np(xi;θ)θ^MLE=arg⁡max⁡θL(θ)L(\theta)=\prod_{i=1}^n p(x_i;\theta)\\
\hat\theta_\text{MLE}=\arg\max_\theta L(\theta)L(θ)=i=1∏n​p(xi​;θ)θ^MLE​=argθmax​L(θ)
log-likelihood trick: take log to turn product into sum
ℓ(θ)=log⁡L(θ)=∑i=1nlog⁡p(xi;θ)\ell(\theta)=\log L(\theta)=\sum_{i=1}^n\log p(x_i;\theta)ℓ(θ)=logL(θ)=i=1∑n​logp(xi​;θ)
differentiate with respect to θ\thetaθ, set to zero, and solve for θ^\hat\thetaθ^​
check that it’s a max and not a min by checking second derivative of endpoints
example: x1,…,xnx_1,…,x_nx1​,…,xn​ are iid from Bernoulli⁡(p)\operatorname{Bernoulli}(p)Bernoulli(p)​
PMF: P(X=x;p)=px(1−p)1−xP(X=x;p)=p^x(1-p)^{1-x}P(X=x;p)=px(1−p)1−x​
log likelihood
ℓ(λ)=∑ilog⁡px(1−p)1−x=∑ixlog⁡p+(1−x)log⁡(1−p)\ell(\lambda)=\sum_i\log p^x(1-p)^{1-x}=\sum_i x\log p+(1-x)\log(1-p)ℓ(λ)=i∑​logpx(1−p)1−x=i∑​xlogp+(1−x)log(1−p)
let kkk denote the number of 1s
ℓ(λ)=klog⁡p+(n−k)log⁡(1−p)\ell(\lambda)=k\log p+(n-k)\log(1-p)ℓ(λ)=klogp+(n−k)log(1−p)
derivative
ℓ′(λ)=kp−n−k1−p=0  ⟹  p=kn\ell'(\lambda)=\frac kp-\frac{n-k}{1-p}=0\implies p=\frac knℓ′(λ)=pk​−1−pn−k​=0⟹p=nk​
MLE is the sample frequency
example: x1,…,xnx_1,…,x_nx1​,…,xn​ are iid from Exp⁡(λ)\operatorname{Exp}(\lambda)Exp(λ)​
PDF: f(x;λ)=λe−λxf(x;\lambda)=\lambda e^{-\lambda x}f(x;λ)=λe−λx​
log likelihood
ℓ(λ)=∑ilog⁡(λe−λxi)=∑ilog⁡λ−λxi=nlog⁡λ−λ∑ixi\ell(\lambda)=\sum_i\log(\lambda e^{-\lambda x_i})=\sum_i\log\lambda -\lambda x_i=n\log \lambda-\lambda\sum_i x_iℓ(λ)=i∑​log(λe−λxi​)=i∑​logλ−λxi​=nlogλ−λi∑​xi​
derivative
ℓ′(λ)=nλ−∑ixi=0  ⟹  λ^MLE=n∑ixi\ell'(\lambda)=\frac n\lambda-\sum_i x_i=0\implies \hat\lambda_\text{MLE}=\frac{n}{\sum_i x_i}ℓ′(λ)=λn​−i∑​xi​=0⟹λ^MLE​=∑i​xi​n​
MLE is the reciprocal of the sample mean
this makes sense because Exp⁡(λ)\operatorname{Exp}(\lambda)Exp(λ) has mean 1/λ1/\lambda1/λ​
example: x1,…,xnx_1,…,x_nx1​,…,xn​ are iid from Uniform⁡(0,θ)\operatorname{Uniform}(0,\theta)Uniform(0,θ)​
PDF: f(x;θ)=1/θf(x;\theta)=1/\thetaf(x;θ)=1/θ​
likelihood
L(θ)={1θnif max⁡xi≤θ0otherwiseL(\theta)=\begin{cases}\frac{1}{\theta^n} & \text{if }\max x_i\leq\theta\\
0&\text{otherwise}
\end{cases}L(θ)={θn1​0​if maxxi​≤θotherwise​
this is maximized for the smallest value of θ\thetaθ that satisfies θ≥max⁡xi\theta\geq\max x_iθ≥maxxi​ so θ^=max⁡xi\hat\theta=\max x_iθ^=maxxi​​
models are trained to minimize CE loss = −1N∑ilog⁡p(xi)-\frac 1N\sum_i\log p(x_i)−N1​∑i​logp(xi​) which is the same as maximizing log likelihood = ∑ilog⁡p(xi)\sum_i\log p(x_i)∑i​logp(xi​)​
in other words, models are trained to make observed data as probable as possible
Bias & variance
true parameter θ\thetaθ, estimator θ^\hat\thetaθ^​
the estimator is a function of the data, and since the data is random → θ^\hat\thetaθ^ is an RV
bias: how close is θ^\hat\thetaθ^ to θ\thetaθ on average?
bias⁡[θ^]=E[θ^]−θ\operatorname{bias}[\hat \theta]=\mathbb E[\hat \theta]-\thetabias[θ^]=E[θ^]−θ
variance: how much does θ^\hat\thetaθ^ depend on the data distribution?
var⁡(θ^)=E[(θ^−E[θ^])2]\operatorname{var}(\hat\theta)=\mathbb E[(\hat\theta-\mathbb E[\hat \theta])^2]var(θ^)=E[(θ^−E[θ^])2]
mean squared error
MSE⁡(θ^)=E[(θ^−θ)2]\operatorname{MSE}(\hat\theta)=\mathbb E[(\hat\theta-\theta)^2]MSE(θ^)=E[(θ^−θ)2]
decomposes into bias^2 + variance
MSE⁡(θ^)=Bias⁡(θ^)2+Var⁡(θ^)\operatorname{MSE}(\hat\theta)=\operatorname{Bias}(\hat\theta)^2+\operatorname{Var}(\hat\theta)MSE(θ^)=Bias(θ^)2+Var(θ^)
Math things
Taylor series
a Taylor series approximates a function using a polynomial, using only information about the function at a single point
f(x)=∑n=0∞f(n)(a)n!(x−a)nf(x)=\sum_{n=0}^\infty \frac{f^{(n)}(a)}{n!}(x-a)^nf(x)=n=0∑∞​n!f(n)(a)​(x−a)n
a series around a=0a=0a=0 is called the Maclaurin series
the Taylor series of exe^xex around x=0x=0x=0 is
ex=1+x+x22!+x33!+⋯=∑n=0∞xnn!e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\cdots=\sum_{n=0}^\infty\frac{x^n}{n!}ex=1+x+2!x2​+3!x3​+⋯=n=0∑∞​n!xn​
has infinite radius of convergence, so it converges to exe^xex everywhere
suppose we want to approximate f(x)f(x)f(x) near x=0x=0x=0​
0th order approximation: f(x)≈f(0)f(x)\approx f(0)f(x)≈f(0)​
horizontal line at f(0)f(0)f(0)​
1st order approximation: f(x)≈f(0)+f′(0) xf(x)\approx f(0)+f^\prime(0)\,xf(x)≈f(0)+f′(0)x​
tangent line to fff at x=0x=0x=0, matching fff in both value and slope at the origin
2nd order approximation: f(x)≈f(0)+f′(0)x+f′′(0)2x2f(x)\approx f(0)+f^\prime(0)x+\frac{f^{\prime\prime(0)}}{2}x^2f(x)≈f(0)+f′(0)x+2f′′(0)​x2​
parabola that matches fff in value, slope, and curvature at 0
each new term adds another derivative of information, letting the polynomial hug the function more tightly near x=0x=0x=0​
Derivative rules
memorize these
ddxxn=nxn−1ddxex=exddxlog⁡x=1xddxsin⁡x=cos⁡xddxcos⁡x=−sin⁡x\frac{d}{dx}x^n=nx^{n-1}\\
\frac{d}{dx}e^x=e^x\\
\frac{d}{dx}\log x=\frac 1x\\
\frac{d}{dx}\sin x=\cos x\\
\frac{d}{dx}\cos x=-\sin xdxd​xn=nxn−1dxd​ex=exdxd​logx=x1​dxd​sinx=cosxdxd​cosx=−sinx
composition rules
ddxf(g(x))=f′(g(x))⋅g′(x)chain ruleddxf(x)g(x)=f′(x)g(x)+f(x)g′(x)product ruleddxf(x)g(x)=f′(x)g(x)−f(x)g′(x)g(x)2quotient rule\begin{align*}
\frac{d}{dx}f(g(x))&=f'(g(x))\cdot g'(x) &\text{chain rule}\\
\frac{d}{dx}f(x)g(x)&=f'(x)g(x)+f(x)g'(x)&\text{product rule}\\
\frac{d}{dx}\frac{f(x)}{g(x)}&=\frac{f'(x)g(x)-f(x)g'(x)}{g(x)^2}&\text{quotient rule}
\end{align*}dxd​f(g(x))dxd​f(x)g(x)dxd​g(x)f(x)​​=f′(g(x))⋅g′(x)=f′(x)g(x)+f(x)g′(x)=g(x)2f′(x)g(x)−f(x)g′(x)​​chain ruleproduct rulequotient rule​
Handy equations
the nnn-th harmonic number Hn=∑k=1n1k≈log⁡nH_n=\sum_{k=1}^n\frac 1k\approx\log nHn​=∑k=1n​k1​≈logn for large nnn​
log mean xy≤x+y2\sqrt{xy}\leq\frac{x+y}{2}xy​≤2x+y​ for x,y>0x, y>0x,y>0​
some identities for eee​
e=lim⁡n→∞(1+1n)ne=\lim_{n\to\infty}\left(1+\frac 1n\right)^ne=n→∞lim​(1+n1​)n
replace nnn with −n-n−n​
1e=lim⁡n→∞(1−1n)n\frac 1e=\lim_{n\to\infty}\left(1-\frac 1n\right)^ne1​=n→∞lim​(1−n1​)n
replace nnn with n/xn/xn/x​
ex=lim⁡n→∞(1+xn)ne^x=\lim_{n\to\infty}\left(1+\frac xn\right)^nex=n→∞lim​(1+nx​)n
exponential series
e=∑k=0∞1k!ex=∑n=0∞xnn!e−1=1−11!+12!−13!+⋯e=\sum_{k=0}^\infty\frac{1}{k!}\quad \quad e^x=\sum_{n=0}^\infty\frac{x^n}{n!}\quad\quad e^{-1}=1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\cdotse=k=0∑∞​k!1​ex=n=0∑∞​n!xn​e−1=1−1!1​+2!1​−3!1​+⋯

description	concept
memoryless, waiting	geometric, exponential
trials with success & failure	Bernoulli, binomial
large sample, average	CLT, approximately Gaussian
bound given only mean / variance	Markov / Chebyshev inequalities
estimating parameter from data	MLE, MAP, Bayesian update
update belief from evidence	Bayes rule
function of a RV	Jensen’s inequality
expected count of things	linearity + indicators
expected hitting time / return probability	first-step analysis, solve recurrence
Markov property (future depends only on present)	first-step analysis

	discrete	continuous
counting	binomial: how many successes in $n$ trials?	Poisson: how many events in fixed window?
waiting	geometric: how many trials until first success?	exponential: how long until first event?

order matters?	replacement?	count
yes	no	$\frac{n!}{(n-k)!}$ (permutations)
no	no	$\binom nk$ (combinations)
yes	yes	$n^k$
no	yes	$\binom{n+k-1}{k}$ (stars and bars)