Probability and Statistics 2

• machine in 2 states – working × broken
• w → b … probability 0.01
• w → w … 0.99
• b → w … 0.9
• b → b … 0.1

a fly which may get caught in a web … absorbing states

• sequence of random variables $X_0,X_1,\dots$ such that "all probabilities are defined"
  • e.g. $P(X_0=1\land X_1=2\land X_3=0)$ is defined

• stochastic process such that
  • $\exists$ finite/countable set $S:\text{Im}X_t\subseteq S\;\forall t$
    • elements of $S$ … states
    • $t$ … time
  • $(\forall i,j\in S)(\exists p_{ij}\in [0,1])(\forall t)(\forall a_0,a_1,\dots,a_t,a_{t+1})$
• notes
  • this is a discrete time Markov chain
  • discrete space … $|S|\leq |\mathbb N|$
  • time-homogeneous
    • $p_{ij}$ not depeding on $t$
  • Markov condition
    • only applies if the condition probabilities are defined
  • Markov condition … "forgetting the past"

• vertices … $S$
• directed edges … $\set{(i,j):p_{ij}\gt 0}$

from state $i$ we go to $j$ with the probability of $p_{ij}$ independent of the past

• $P(X_1=w)=p_{11}=0.99$
• $P(X_2=w)=p_{11}\cdot p_{11}+p_{12}\cdot p_{21}=0.99\cdot 0.99+0.01\cdot 0.9$
  • using the total probability theorem

• $\pi_i^{(t)}=P(X_t=i)$
  • $t\in\mathbb N_0$
  • $i\in S$

• $\pi^{(t+1)}=\pi^{(t)}\cdot P$
  • where $\pi^{(t)}=(\pi_1^{(t)},\dots,\pi_n^{(t)})$ row vector
• proof … definition of matrix multiplication & total probability theorem

• $P(X_0=a_0,X_1=a_1,\dots,X_t=a_t)=\pi_{a_0}^{(0)}\cdot P_{a_0a_1}\cdot P_{a_1a_2}\cdot\ldots\cdot P_{a_{t-1}a_t}$
• proof by induction

• $r_{ij}(k)=P(X_{t+k}=j\mid X_t=i)$
• $r_{ij}(1)=P(X_{t+1}=j\mid X_t=i)=p_{ij}$
• it is independent of $t$

• $\forall$ Markov chain, $\forall i,j,k:$
  • $r_{ij}(k+1)=\sum_{u=1}^n r_{iu}(k) p_{uj}$
  • $r_{ij}(k+\ell)=\sum_{u=1}^n r_{iu}(k) r_{uj}(\ell)$
  • $r_{ij}(k)=(P^k)_{ij}$
• proof
  • 1 is a special case of 2 ($r_{uj}(1)=p_{uj})$
  • $1\implies 3$ … matrix multiplication & induction
  • …

• $i\to j$
• $j\in A(i)$
• $j$ is accessible from $i\equiv$ $\exists t:\underbrace{P(X_t=j\mid X_0=i)}_{r_{ij}(t)}\gt 0$
• $\iff$ in the transition digraph exists directed path $i\to j$ of length $t$

• reflexive: $i\in A(i)$ … $t=0$ in the definition
• symmetric: the formula $i\in A(j)\land j\in A(i)$ is symmetric
• transitive: in the digraph $\exists$ path $i$ to $j$, $\exists$ path $j$ to $k$ $\implies\exists$ walk $i\to k$

• it is transient otherwise
• česky rekurentní, tranzientní

• $T_i=\infty$ if the set is empty (there is no such $t$)
• $T_i$ … random variable
• $f_{ij}(n)=P(\text{we get to }j\text{ first at time }n\mid X_0=i)=P(T_j=n\mid X_0=i)$
  • we define it for $n\gt 0$
• $f_{ij}=P(T_j\lt\infty\mid X_0=i)=\sum_{n\geq 1} f_{ij}(n)$

• $f_{ii}\lt 1$ … probability of ever getting back
• $\iff P(T_i=\infty)\gt 0$
• $\iff P(\text{get back infinitely often})\lt 1$

• with probability 1/2 we go to the left
• $f_{00}(2)=(\frac12)^2+(\frac12)^2=\frac12$
• $f_{00}(1)=f_{00}(3)=\dots=0$
• $f_{00}(4)=\frac{1}{2^4}\cdot 2$
  • $r_{00}(4)\neq f_{00}(4)$
  • $r_{00}(4)=\frac{1}{2^4}\cdot 4$
• is 0 recurrent?
  • by definition, we should add $f_{00}(2)+f_{00}(4)+\dots$ and check if it equals 1
  • theorem: $i$ is a recurrent state $\iff\sum_{n=1}^\infty r_{ii}(n)=\infty$
    • $B_n=\begin{cases} 1&\text{ if }X_n=i\\ 0 &\text{ otherwise}\end{cases}$
      • we got back
      • $\mathbb E(B_n\mid X_0=i)=P(X_n=i\mid X_0=i)=r_{ii}(n)$
    • $r_{00}(2n)=$ probability that out of the $2n$ steps, $n$ were to the left, $n$ were to the right
      • $=\frac1{2^{2n}}\cdot{2n\choose n}\doteq\frac c{\sqrt n}$ … see Matoušek, Nešetřil
    • $\sum_{n=1}^\infty \frac{c}{\sqrt n}=\infty$ (taught in calculus)
    • $\mathbb E(T_0\mid X_0=0)=\infty$ (we did not prove that)

if $i\leftrightarrow j$, then either both $i$ and $j$ are recurrent or both $i$ and $j$ are transient

• $C$ … equiv class of $\leftrightarrow$ in a finite Markov chain
• $C$ is recurrent ($\forall i\in C$ is recurrent) $\iff(\forall i \in C)(\forall j\in S):$ if $i\to j$ then $j\in C$
  • → $C$ is closed

• df: $\pi:S\to [0,1]$ such that $\sum_{i\in S}\pi_i=1$ is called a stationary distribution if $\text{``}\pi P=\pi\text{"}$
  • $\forall i:\sum_i\pi_i p_{ij}=\pi_j$
• if $\pi^{(0)}$ (the PMF of $X_0$) is $\pi$, then $\pi^{(1)}$ is $\pi$ as well
• $\pi^{(1)}=\pi^{(0)}P$

1. $\exists$ unique stat. distribution $\pi$
2. $\forall i:\lim_{n\to\infty}(P^n)_{ij}=\pi_j$

$i\in S$ is aperiodic if $d_i=1$

$i$ is positive recurrent if $i$ is recurrent and $\mathbb E(T_i\mid X_0=i)\lt\infty$

• if $i,j\in S$, $i\leftrightarrow j$, then
  • $d_i=d_j$
  • $i$ is transient $\iff j$ is trainsient
  • $i$ is recurrent $\iff j$ is recurrent
  • $i$ is null recurrent $\iff j$ is null recurrent
  • $i$ is positive recurrent $\iff j$ is positive recurrent
• these are properties of the class of $\leftrightarrow$

• if a Markov chain is irreducible, aperiodic and finite, then
  • there exists a unique stationary distribution $\pi$: $\pi P=\pi$
  • $\forall ij:\lim(P^t)_{ij}=\pi_j$
    • $P(X_t=j\mid X_0=i)\doteq\pi_j$
• actually, MC does not have to be finite, it suffices if all states are positive recurrent (?)
• steady state (?)
  • if $\pi^{(0)}=\pi$ then $\pi^{(1)}=\pi$

• $Pj=Ij$ (row sums are 1)
• $(P-I)j=0$
• $P-I$ is sungular matrix
• $\exists x:x(P-I)=0\implies xP=x$
• $\pi=\frac xc$ such that $\sum \pi_i=1$
• problem
  • $x$ may have negative coordinates
  • to fix: use Perron-Frobenius theorem
  • the correct proof is shown in class of probabilistic techniques

• $\pi$ describes long-term behavior of the MC
• Page Rank (original google search) … MC model of people browsing WWW
• given $\pi$, we can find a MC such that $\pi$ is its stationary distribution; then we can run the MC to generate random objects with distribution $\pi$
  • Markov chain Monte Carlo (MCMC)

• MC may have this property
• $\forall i\neq j:\pi_iP_{ij}=\pi_jP_{ji}$

stationary distribution $\iff$ the same number of ants at each state at each time – ants don't "accumulate"

detailed balance equation is stronger than $\pi P=\pi$

• choose aperiodic irreducible digraph
• $p_{ij}=\min\set{1,\frac{\pi _j}{\pi_i}}\cdot C$
• $p_{ji}=\min\set{1,\frac{\pi_i}{\pi_j}}\cdot C$
• choose $C$ such that
  • $\forall i:\sum_{j\neq i} p_{ij}\lt 1$
  • df. $p_{ii}=1-\sum_{j\neq i}p_{ij}\gt 0$
  • $\implies d_i=1$
• tune the process to make convergence fast

• $A$ … set of absorbing states
• question 1: which $i\in A$ we end at?
• question 2: how fast?

$a_i=P(\exists t:X_t=0\mid X_0=i)$

$T=\min\set{t: X_t\in A}$

• $a_0=1$
• $a_i=0$ if $i\in A,\,i\neq 0$
• $a_i=\sum_j p_{ij}\cdot a_j$ otherwise

• $\mu_i=0$ if $i\in A$
• $\mu_i=1+\sum_j p_{ij}\mu_j$ if $i\notin A$

• $P(\exists t:X_t=0\mid X_0=0)=1$
• $P(\exists t: X_t=0\mid X_0=i\in A\setminus\set{0})=0$
• $i\notin A$
  • $B_j=\set{\exists t:X_t=0}$
  • $P(B_i)=\sum_{j\in S} p_{ij}\cdot \underbrace{P(B_i\mid X_1=j)}_{P(B_j)=a_j}$

• $A=\set{0}$
• $\mu_0=0$
• $\mu_1=1+\frac12\mu_0+\frac12\mu_2$
• $\mu_2=1+\frac12\mu_1+\frac12\mu_3$
• $\mu_{n-1}=1+\frac12\mu_{n-2}+\frac12\mu_{n}$
• $\mu_n=1+\mu_{n-1}$
• solution
  • $\mu_1=2n-1$
  • $\mu_n=n^2$
  • $\mu_{i}\leq n^2$

• input: $\varphi=(x_1\lor x_2)\land(x_3\lor\neg x_1)\land\ldots$
  • clauses with exactly 2 literals
• output: a satisfying assignment OR “unsatisfiable”
• there exists a polynomial algorithm
• we will show a randomized algorithm
  1. arbitrarily initialize $(x_1,\dots,x_n)$
  2. while $\varphi$ has an unsatisfied clause
     • choose one of the unsatisfied clauses and change one of its variables
  3. return $(x_1,\dots,x_n)$
• repeat (2) $\leq2mn^2$ times
  • then, if $\varphi$ is still unsatisfied, return “unsatisfiable”
  • this may introduce errors
• theorem: the algorithm makes an error with probability $\leq 2^{-m}$
• proof
  • $x_1^*,\dots,x_n^*$ … one of the satisfying assignments
  • $D_t$ the number of $i$ such that $x_i\neq x_i^*$ at time $t$
    • $t=0,1,\dots,2mn^2$
    • $0\leq D_t\leq n$
    • $D_t=0\implies$ we found a solution
  • situation
    • we assume that clause $(x_1\lor x_2)$ is unsatisfied at time $t$ and we choose it
    • $\implies x_1=x_2=F$
      • $(x_1\neq x_2)$
      • ($x_2\neq\neg x_1)$ … we could remove such clauses
    • $\implies x_1^*\lor x_2^*$ is $T$
    • we randomly switch $x_1$ or $x_2$ which increases or decreases $D$
    • …
• we can get a 3-SAT randomized algorithm with $(\frac43)^n$ time complexity this way

• not observable $(X_t)$ … Markov chain
• observable $(Y_t)$ … $Y_t$ is obtained from $X_t$
• widely aplplicable
• smart algorithm (Vitebri algorithm)

• $P:\mathcal F\to[0,1]$ such that
  • $P(\Omega)=1$
  • $P(\bigcup A_n)=\sum P(A_n)$ if disjoint

• randomized algorithms
• is it possible to have true randomness?
  • hardware methods to sample random bits
  • software methods
    • their independence can be “weak” (for statistics) or “strong” (for cryptography)

• we prove that some graph exists by showing that random graph has certain property with probability greater than zero
• $G(n,p)$ … graph with vertices $1,\dots,n$
  • $\forall i,j:i\sim j$ with probability $p$ (all independent)
• $P(G(n,\frac12)$ has no $K_k$ nor $\overline K_k$ as an induced subgraph$)\gt 0$ if $n\leq 2^{k/2}$
• thus $\exists G$ on $2^{k/2}$ vertices with no induced $K_k$ nor $\overline K_k$
• Ramsey theorem

• frequentist
  • $P(A)=$ number of good / number of all
  • “in long term repetition”
  • repeat a random experiment independently $n$ times
  • observe that $A$ happens $k$ times
  • $P(A):=k/n$
• Bayesian
  • P(it will rain tomorrow)
  • subjective probability → betting
    • does satisfy axioms!
  • “random universe”
    • $\Omega$ = set of all possible universes

$\hat\theta$ is a point estimate for $\Theta$

$B(\alpha,\beta)=\int_0^1x^{\alpha-1}(1-x)^{\beta-1}=\frac{(\alpha-1)!(\beta-1)!}{(\alpha+\beta-1)!}$

$f_\Theta(x)=\frac1{B(\alpha,\beta)}x^{\alpha-1}(1-x)^{\beta-1}$

• in the maximum, this will be equal to zero
• maximum … $\frac{\alpha-1}{\alpha-1+\beta-1}$

• LMS = least mean square
• estimate such that $\mathbb E((\Theta-\hat\theta)^2\mid X=x)$ is minimal
• to compute it
  • …

• point extimates
  • MAP
  • LMS
• interval estimates
  • confidence intervals (in classical statistics) → credible sets $S$

• rejection sympling
• MCMC sampling
  • Monte Carlo Markov chains
  • Metropolis Hastings method
  • we construct a MC from the probability distribution we want
  • we run the MC for long enough

• mean … LMS = $\min\mathbb E((\Theta-\hat\theta)^2\mid X=x)$
• median … $\min\mathbb E(|\Theta-\hat\theta|\mid X=x)$
• modus … MAP

• events
  • $A\perp B\iff P(A\cap B)=P(A)\cdot P(B)$
  • $A\perp_C B\iff P(A\cap B\mid C)=P(A\mid C)\cdot P(B\mid C)$
    • $A,B$ are independent conditionally given $C$
• it is possible (even typical) that $A\perp_C B$, $A\perp_{C^C} B$, but not $A\perp B$

• $\mathbb E(Y\mid X=x)$ vs. $\mathbb E(Y\mid X)$
• $\mathbb E(Y\mid X=x)=g(x)$ … number
• $\mathbb E(Y\mid X)=g(X)$ … random variable
• we proved that $\mathbb E(\mathbb E(Y\mid X))=\mathbb E(g(X))=\mathbb EY$
  • “law of iterated expectation”
• basic task of statistics
  • estimate one quantity (Y) given data/measurement (X)
• example: groups of students, their exam results
• estimator
  • $\hat Y=\mathbb E(Y\mid X)=g(X)$
• $\tilde Y=\hat Y-Y$
• we proved that $\mathbb E(\tilde Y\mid X)=0$
  • therefore $\mathbb E(\tilde Y)=\mathbb E(\mathbb E(\tilde Y\mid X))=0$
• also, $\text{cov}(\tilde Y,\hat Y)=0$
  • they are uncorellated
• note
  • uncorellated $\impliedby$ independent
  • uncorellated $\centernot\implies$ independent
• conditional variance
• iterated variance / eve's rule
  • $\text{var }Y=\mathbb E(\text{var}(Y\mid X))+\text{var}(\mathbb E(Y\mid X))$
  • intragroup variance + intergroup variance

$1-x\approx e^{-x}$

• $m$ balls
• $n$ bins
• $X_i$ … number of balls in bin $i$
• birthday paradox … $P(\max X_i\geq 2)$

• how many bins are used?
• approximation of $X_i$
• max load … $\max\set{X_1,\dots,X_n}$

• $I_i=1$ if $X_i=0$ (otherwise 1)
• $\mathbb E(\sum_i I_i)=\sum_i\mathbb EI_i\approx ne^{-\frac mn}$

• $X_i\sim \text{Bin}(m,\frac 1n)\approx\text{Pois}(\frac mn)$
• $\mathbb EX_i=\frac mn$

• bucket sort
• hash collisions

theorem: any event that happens with probability $\leq p$ in the Poisson case happens with probability $\leq p\cdot e\sqrt m$ in the exact case

…

• descriptive – describe what we observed
• inferential – deduce properties of a larger set
  • how many people are left-handed?
  • we can observe this on a small sample of people
• observational study vs. randomized study (RCT, randomized control trial)
• treatment – what you do to experimental units
• example
  • experimental units … students
  • treatment … which tutorial student attends
    • placebo, control group
  • observational study → we let the students decide which tutorial to attend
  • randomized study → we assign the tutorials to students (randomly)
• confounders
  • people can get better because they believe they are treated
• random $\neq$ arbitrary
  • haphazard
• statistics – parametric vs. non-parametric
  • parametric → observations from parametrized random variables
  • t-test
  • permutation test

• black (4.3/5) vs. navy blue (4/5)
• descriptive statistics
• observational study

• permutation test
• https://www.jwilber.me/permutationtest/
• we observe … $T(X,Y)$
• $Z:=X,Y$
• $\mathcal F=\set{T(\pi(Z))\mid \pi\in S_{m+n}}$
• p-value: percentage of $\mathcal F$ more extreme than observed
• speed-up … we use only $k$ random samples from $S_{m+n}$

• one-sample test
• two-sample test
• paired test
  • quality of wool before/after treatment
  • give black & blue to $n$ testers, ask each tester to score both
    • randomize the order of testing the color
  • use one-sample test on $D_i=X_i-Y_i$

for paired test, we only permute $X_i$ with $Y_i$

$Y_i=$ "sign of $X_i$"

• 10 values
• $H_0$ … median = 0
• sign $S\sim\text{Bin}(10,\frac12)$
• one-sided test … $F_S(3)=P(S\leq 3)=0.17$
• two-sided test … $P(S\leq 3\lor S\geq 7)=0.34$
• but we are suspicious
  • we can rank absolute values (from lowest to highest) and write the averages of the ranks (for rank 3–5 → the average will be 4)
  • we can multiply that by the sign ($S$)

• data … $X_1,\dots,X_n$
• ranks of $|X_i|$ … $R_1,\dots,R_n$
• $T^+=\sum_{X_i\gt 0}R_i$
• $T^-=\sum_{X_i\lt 0} R_i$
• $T=T^+-T^-=\sum R_i\cdot\text{sign}(X_n)$
• $T^++T^-=\sum i=\frac {n(n+1)}2$
• we will use stronger null hypothesis
  • $H_0:$ median = 0 & distribution is symmetric
• assuming $H_0$… (and ignoring ties)
  • $T=\sum_{i=1}^n i\cdot V_i$
  • $V_i=\begin{cases}+1 \text{ prob. } 1/2\\ -1\end{cases}$
  • $V_i^+=0/1$
    • $\sim\text{Ber}(\frac12)$
  • $T^+=\sum i\cdot V_i^+$
  • $V_i$ … independent
  • what can we do?
    • we can compute CDF of $T$
    • we can apply CLT to approximate (can we really?)

• wilcox test in R → $0.07$
• what is correct? $0.07$ or $0.17$?
• it depends on what we can assume
  • sign test
  • Wilcoxon signed rank test
  • Student's t-test

• $1-P(\text{type II error})$
• to increase, we have two choices
  • we can get more data
  • or we can make stronger assumptions
    • but we should not cheat – if it is obvious that the data is not normally distributed, we should not say they are

• $X_i=A_i-B_i$
• null hypothesis … the procedure did not help nor hurt
  • the distribution may be very weird
  • but it will be symmetrical
• if $A_i,B_i$ have same distribution, then $A_i-B_i$ has distribution symmetrical around 0, median 0

• $U=\sum_{i=1}^m\sum_{j=1}^nS(X_i,Y_j)$
• $S(X_i,Y_j)=\begin{cases} 1 & X_i\gt Y_j\\ \frac12 & X_i=Y_j \\ 0 & X_i\lt Y_j\end{cases}$
• 2-sample test
• we have two populations, $X$ and $Y$
  • we get $X_1,\dots,X_m$ and $Y_1,\dots,Y_n$
  • usually, $m\neq n$
• sign test is a paired variant of this
• we use the same approach as in the permutation test with $U$ instead of $T=\bar X_m-\bar Y_n$

• numerical … real numbers (weight, time, price)
  • → permutation test
• ordinal … classes (light/medium/heavy, quick/slow)
  • → $U$-test

• data $X_1,\dots,X_n$ iid
• sample mean $\bar X_n=\frac1n\sum_{i=1}^n X_i$
  • distr. of $\bar X_n:\mathbb E \bar X_n=\mathbb E X_i=\mu$
  • variance of $\bar X_n:\text{var}\bar X_n=\frac1n\sigma^2$
  • CLT: $\bar X_n$ has $\approx$ Normal distribution $N(\mu,(\frac\sigma{\sqrt n})^2)$
  • $P(\bar X_n\lt a)$ can be approximated by the normal distribution $N$
• now, we want the same of a different parameter
  • $M$ … median of $X_i$
  • $\hat M=$ sample median: “middle value of $X_1,\dots,X_n$”
  • $X_{\set{1}},\dots,X_{\set{n}}$ … sorted data
  • $\hat M=X_{\set{\frac n2}}$
    • estimator function of data we use to estimate the true $M$
• bootstrapping … sampling with repetition from $X_1,\dots,X_n$
  • we can approximate the distribution of $\hat M$
• interval estimate for median $M$
  • $M^*$ … bootstrapped median (median of the one set of bootstrapped data)
  • $M_\alpha^*=\set{x:P(M^*\leq x)=\alpha}$
  • this method is simple and does not depend on the distribution of the data

• $M_X(s)=p\cdot e^{s\cdot 1}+(1-p)\cdot e^{s\cdot 0}$
• $M_X(s)=1-p+pe^s$
• note: $e^s=1+s+\frac{s^2}2+\frac{s^3}{3!}+\dots=\sum_{k=0}^\infty\frac{s^k}{k!}$
• $M_X(s)=1+p(s+\frac{s^2}2+\frac{s^3}{3!}+\dots)$

$\mathbb E[X^k]$ … $k$-th moment of $X$

$\mathbb E[e^{sX}]=\mathbb E[\sum\frac{(sX)^k}{k!}]=\mathbb E[\sum X^k\frac{s^k}{k!}]=\sum\mathbb E[X^k\frac{s^k}{k!}]=\sum_{k=0}^\infty\mathbb E[X^k]\cdot \frac{s^k}{k!}$

• $\mathbb EX=[s^1]M_X(s)=p$
  • this notation selects the coefficient of the $s^1$ in the GF
• $\mathbb EX^2=[\frac{s^2}{2!}]M_X(s)=p$

• $M_X(s)=\mathbb E[e^{sX}]\overset{\text{LOTUS}}{=}\int_{-\infty}^\infty e^{sx}f_X(x)\text { d}x$
• …
• $M_X(s)=e^{s^2/2}$

• $X\sim N(\mu,\sigma^2)$
• $\frac{X-\mu}{\sigma}=Y\sim N(0,1)$
• $X=\sigma Y+\mu$
• $M_X(s)=e^{\mu s}\cdot e^{\sigma^2 s^2/2}$

• let $X,Y$ be RVs such that $(\exists\varepsilon\gt 0)(\forall s\in (-\varepsilon,\varepsilon)):M_X(s)=M_Y(s)\in\mathbb R$
• then $F_X=F_Y$

• $X_1\sim N(\mu_1,\sigma^2_1)$
• $X_2\sim N(\mu_2,\sigma^2_2)$
• $\implies X_1+X_2\sim N(\mu,\sigma^2)$
• proof
  • $M_{X_1}=\text{exp}(\mu_1s+\sigma_1^2s^2/2)$
  • $M_{X_2}=\text{exp}(\mu_2s+\sigma_2^2s^2/2)$
  • …

$X,Y$ independent $\implies M_{X+Y}=M_X\cdot M_Y$

$M_{X+Y}(s)=\mathbb E[e^{s(X+Y)}]=\mathbb E[e^{sX}\cdot e^{sY}]=\mathbb E[e^{sX}]\cdot \mathbb E[e^{sY}]=M_X(s)\cdot M_Y(s)$

• $X\sim\text{Bin}(n,p)$
• $M_X(s)=(1-p+pe^s)^n$

• $Y,X_1,X_2,X_3,\dots$ RVs
• $(\exists\varepsilon\gt 0)(\forall s\in (-\varepsilon,\varepsilon)):\lim_{n\to\infty} M_{X_n}(s)=M_Y(s)$
• $F_Y$ is continuous
• then $X_n\xrightarrow d Y$
  • $\lim_{n\to\infty} F_{X_n}(s)=F_Y(s)$

• $X_1,X_2,\dots$ i.i.d. (independent identically distributed) RVs
• $\mathbb EX_i=\mu$, $\text{var} X_i=\sigma^2$
• $Y_n:=\frac{X_1+\dots+X_n-n\mu}{\sqrt{n}\sigma}$
• $Y_n\xrightarrow d N(0,1)$
  • that is $\lim_{n\to\infty}F_{Y_n}(t)=\Phi(t)$

• we may assume $\mu=0$
  • otherwise, we would set $X_n'=X_n-\mu$
  • variance would not change
  • the formula for $Y_n$ also would not change (we subtract $n\mu$ there)
• $M_{X_i}(s)=1+as+bs^2+O(s^3)\quad(s\doteq 0)$
  • $a=\mu=0$
  • $b=\frac12\mathbb EX_i^2=\frac12(\sigma^2-\mu^2)=\frac12\sigma^2$
• $M_{X_i}(s)=1+\frac{\sigma^2}2s^2+O(s^3)$
• $M_{Y_n}(s)=\prod M_{X_i}\left(\frac s{\sqrt n\sigma}\right)$
• we will use the previous theorem for $Y,Y_1,Y_2,\dots$
• we need to show that $\lim M_{Y_n}(s)=M_Y(s)$
  • or that $\lim_{n\to\infty}M_{X_n}(\frac s{\sqrt n\sigma})^n=e^{s^2/2}$
• $M_{X_n}(\frac s{\sqrt n\sigma})^n=…=\text{exp}(n\ln(1+\frac{s^2}{2n}+O(s^3))$
• …