Limit theorem

Chebyshev’s inequality

$$\begin{align} {\sigma ^2} &= \int {{{\left( {x – \mu } \right)}^2}{f_X}\left( x \right)dx} \\ &\ge \int_{ – \infty }^{u – c} {{{\left( {x – \mu } \right)}^2}{f_X}\left( x \right)dx} + \int_{u + c}^\infty {{{\left( {x – \mu } \right)}^2}{f_X}\left( x \right)dx} \\ &\ge {c^2}\int_{ – \infty }^{u – c} {{f_X}\left( x \right)dx} {\rm{ + }}{c^2}\int_{u + c}^\infty {{f_X}\left( x \right)dx} \\ &={c^2}{\rm{P}}\left( {\left| {X – \mu } \right| \ge c} \right) \end{align}$$

$${\rm{P}}\left( {\left| {X – \mu } \right| \ge c} \right) \le \frac{{{\sigma ^2}}}{{{c^2}}} \to {\rm{P}}\left( {\left| {X – \mu } \right| \ge k\sigma } \right) \le \frac{1}{{{k^2}}}$$

Convergence

$${M_n} = \frac{{{X_1} + \cdots + {X_n}}}{n}$$

$$\begin{align} {\rm{E}}\left[ {{M_n}} \right] &= \frac{{{\rm{E}}\left[ {{X_1}} \right] + \cdots + {\rm{E}}\left[ {{X_n}} \right]}}{n} = \frac{{n\mu }}{n} = \mu \\ {\mathop{\rm var}} \left( {{M_n}} \right) &= \frac{{{{\left( {{X_1} – \mu } \right)}^2} + \cdots + {{\left( {{X_n} – \mu } \right)}^2}}}{{{n^2}}} = \frac{{n{\sigma ^2}}}{{{n^2}}} = \frac{{{\sigma ^2}}}{n} \to 0\\ {\rm{P}}\left( {\left| {{M_n} – \mu } \right| \ge \varepsilon } \right) &\le \frac{{{\mathop{\rm var}} \left( {{M_n}} \right)}}{{{\varepsilon ^2}}} = \frac{{{\sigma ^2}}}{{n{\varepsilon ^2}}} \to 0 \end{align}$$

Example

Bernoulli process ${\sigma _x} = p\left( {1 – p} \right) = \frac{1}{4}$

95% confidence of error smaller than 1% ${\rm{P}}\left( {\left| {{M_n} – \mu } \right| \ge 0.01} \right) \le 0.05$

$$\begin{align} {\rm{P}}\left( {\left| {{M_n} – \mu } \right| \ge 0.01} \right) &\le \frac{{\sigma _{{M_n}}^2}}{{{{0.01}^2}}} = \frac{{\sigma _x^2}}{{{{0.01}^2}n}}\\ &\le \frac{1}{{4n{{\left( {0.01} \right)}^2}}} \le 0.05 \end{align}$$

Scaling of $M_n$

$$\begin{align} {S_n} = {X_1} + \cdots + {X_n} &\to {\mathop{\rm var}} \left( {{S_n}} \right) = n{\sigma ^2}\\ {M_n} = \frac{{{S_n}}}{n} &\to {\mathop{\rm var}} \left( {{M_n}} \right) = \frac{{{\sigma ^2}}}{n}\\ \frac{{{S_n}}}{{\sqrt n }} &\to {\mathop{\rm var}} \left( {\frac{{{S_n}}}{{\sqrt n }}} \right) = \frac{{{\mathop{\rm var}} \left( {{S_n}} \right)}}{n} = {\sigma ^2} \end{align}$$

Central limit theorem

Standardized ${S_n} = {X_1} + \cdots + {X_n}$

$${Z_n} = \frac{{{S_n} – {\rm{E}}\left[ {{S_n}} \right]}}{{{\sigma _{{S_n}}}}} = \frac{{{S_n} – n{\rm{E}}\left[ X \right]}}{{\sqrt n \sigma }} \sim N\left( {0,1} \right)$$

$${\rm{P}}\left( {{Z_n} \le c} \right) \to {\rm{P}}\left( {Z \le c} \right) = \Phi \left( c \right)$$

CDF of ${Z_n}$ converges to normal CDF, not about convergence of PDF or PMF

Example: 

$n = 36,p = 0.5$, find ${\rm{P}}\left( {{S_n} \le 21} \right)$

Exact answer:

$$\sum\limits_{k = 0}^{21} {\left( {\begin{array}{*{20}{c}} {36}\\ k \end{array}} \right)} {\left( {\frac{1}{2}} \right)^{36}} = 0.8785$$

Method 1: Central limit theorem

$${Z_n} = \frac{{{S_n} – n{\rm{E}}\left[ X \right]}}{{\sqrt n \sigma }} = \frac{{{S_n} – np}}{{\sqrt {np\left( {1 – p} \right)} }}$$

$$\begin{align} {\rm{E}}\left[ {{S_n}} \right] &= np = 36 \cdot 0.5 = 18\\ \sigma _{{S_n}}^2 &= np\left( {1 – p} \right) = 9\\ {\rm{P}}\left( {{S_n} \le 21} \right) &\approx {\rm{P}}\left( {\frac{{{S_n} – 18}}{3} \le \frac{{21 – 18}}{3}} \right) = {\rm{P}}\left( {{Z_n} \le 1} \right) = 0.843 \end{align}$$

Method 2: 1/2 correction for binomial approximation

$$\begin{align} {\rm{P}}\left( {{S_n} \le 21} \right) &= {\rm{P}}\left( {{S_n} < 22} \right)\ \ \ {S_n}{\rm{\ is\ an\ integer}}\\ {\rm{P}}\left( {{S_n} \le 21.5} \right) &\approx {\rm{P}}\left( {{Z_n} \le \frac{{21.5 – 18}}{3}} \right) = {\rm{P}}\left( {{Z_n} \le 1.17} \right) = 0.879 \end{align}$$

The solution is closer to the exact answer.

De Moivre-Laplace CLT

When 1/2 correction is used, CLT can also approximate the binomial pmf, not just the binomial CDF.

$$\begin{align} {\rm{P}}\left( {{S_n} = 19} \right) &= {\rm{P}}\left( {18.5 \le {S_n} \le 19.5} \right) \approx {\rm{P}}\left( {0.17 \le {Z_n} \le 0.5} \right)\\ &= {\rm{P}}\left( {{Z_n} \le 0.5} \right) – {\rm{P}}\left( {{Z_n} \le 0.17} \right) = 0.124 \end{align}$$

Exact answer: ${\rm{P}}\left( {{S_n} = 19} \right) = \left( {\begin{array}{*{20}{c}} {36}\\ {19} \end{array}} \right){\left( {\frac{1}{2}} \right)^{36}} = 0.125$

Poisson arrivals during unit interval equals: sum of $n$ (independent) Poisson arrivals during $n$ intervals of length $1/n$. $X = {X_1} + \cdots + {X_n}$, ${\rm{E}}\left[ X \right] = 1$. Fix $p$ of $X_i$, when $n \to \infty$, the mean and variance are changing, so CLT cannot be applied here. For Binomial$\left( {n,p} \right)$:

$$\begin{align} p \ {\rm{fixed}},n &\to \infty : \ {\rm{normal}}\\ np \ {\rm{fixed}},n &\to \infty : \ {\rm{Poisson}} \end{align}$$

Bayesian statistical inference

Types of Inference models/approaches

$$X=aS+W$$

#1. Model building: know “signal” $S$, observe $X$, infer $a$

#2. Inferring unknown variables: know $a$, observe $X$, infer $S$

#3. Hypothesis testing: unknown takes one of few possible values, aim at small probability of incorrect decision

#4. Estimation: aim at a small estimation error

$\theta$ is an unknown parameter and the difference between classical statistics and Bayesian is that $\theta$ is constant in classical statistics, but a random variable in Bayesian.

$$\begin{align} {p_{\Theta \left| X \right.}}\left( {\theta \left| x \right.} \right) = \frac{{{p_\Theta }\left( \theta \right){f_{\Theta \left| X \right.}}\left( {\theta \left| x \right.} \right)}}{{{f_X}\left( x \right)}}& \qquad {\rm{Hypothesis \ testing}}\\ {f_{\Theta \left| X \right.}}\left( {\theta \left| x \right.} \right) = \frac{{{f_\Theta }\left( \theta \right){f_{\Theta \left| X \right.}}\left( {\theta \left| x \right.} \right)}}{{{f_X}\left( x \right)}}& \qquad {\rm{Estimation}} \end{align}$$

Maximum a posteriori probability (MAP): choose a single value that gives a maximum probability, often used in hypothesis testing, but may be misleading when look into the conditional expectation.

Least mean squares estimation (LMS): find $c$ to minimize ${\rm{E}}\left[ {{{\left( {\Theta – c} \right)}^2}} \right]$, in which $c = {\rm{E}}\left[ \Theta \right]$, then the optimal mean squared error is ${\mathop{\rm var}} \left( \Theta \right) = {\rm{E}}\left[ {{{\left( {\Theta – {\rm{E}}\left[ \Theta \right]} \right)}^2}} \right]$, summarized as

$${\rm{minimize \ E}}\left[ {{{\left( {\Theta – c} \right)}^2}} \right] \to c = {\rm{E}}\left[ \Theta \right] \to {\mathop{\rm var}} \left( \Theta \right) = {\rm{E}}\left[ {{{\left( {\Theta – {\rm{E}}\left[ \Theta \right]} \right)}^2}} \right]$$

$$\begin{align} {\rm{E}}\left[ {{{\left( {\Theta – c} \right)}^2}} \right] &= {\rm{E}}\left[ {{\Theta ^2}} \right] – 2c{\rm{E}}\left[ \Theta \right] + {c^2}\\ \frac{d}{{dc}}{\rm{E}}\left[ {{{\left( {\Theta – c} \right)}^2}} \right] &= – 2{\rm{E}}\left[ \Theta \right] + 2c = 0 \end{align}$$

LMS estimation of two random variables

$$\begin{align} {\rm{minimize \ E}}\left[ {{{\left( {\Theta – c} \right)}^2}\left| {X = x} \right.} \right] &\to c = {\rm{E}}\left[ {\Theta \left| {X = x} \right.} \right]\\ {\mathop{\rm var}} \left( {\Theta \left| {X = x} \right.} \right) = {\rm{E}}\left[ {{{\left( {\Theta – {\rm{E}}\left[ {\Theta \left| {X = x} \right.} \right]} \right)}^2}\left| {X = x} \right.} \right] &\le {\rm{E}}\left[ {{{\left( {\Theta – g\left( x \right)} \right)}^2}\left| {X = x} \right.} \right]\\ {\rm{E}}\left[ {{{\left( {\Theta – {\rm{E}}\left[ {\Theta \left| X \right.} \right]} \right)}^2}\left| X \right.} \right] &\le {\rm{E}}\left[ {{{\left( {\Theta – g\left( x \right)} \right)}^2}\left| X \right.} \right]\\ {\rm{E}}\left[ {{{\left( {\Theta – {\rm{E}}\left[ \Theta \right]} \right)}^2}} \right] &\le {\rm{E}}\left[ {{{\left( {\Theta – g\left( x \right)} \right)}^2}} \right] \end{align}$$

LMS estimation with several measurements: ${\rm{E}}\left[ {\Theta \left| {{X_1}, \cdots ,{X_n}} \right.} \right]$, is hard to compute and involves multi-dimensional integrals, etc.

Estimator: $\widehat \Theta = {\rm{E}}\left[ {\Theta \left| X \right.} \right]$, with estimation error $\widetilde \Theta = \widehat \Theta – \Theta$

$$\begin{array}{l} {\rm{E}}\left[ {\widetilde \Theta \left| X \right.} \right] = {\rm{E}}\left[ {\widehat \Theta – \Theta \left| X \right.} \right] = {\rm{E}}\left[ {\widehat \Theta \left| X \right.} \right] – {\rm{E}}\left[ {\Theta \left| X \right.} \right] = \widehat \Theta – \widehat \Theta = 0\\ {\rm{E}}\left[ {\widetilde \Theta h\left( x \right)\left| X \right.} \right] = h\left( x \right){\rm{E}}\left[ {\widetilde \Theta \left| X \right.} \right] = 0 \to {\rm{E}}\left[ {\widetilde \Theta h\left( x \right)} \right] = 0\\ {\mathop{\rm cov}} \left( {\widetilde \Theta ,\widehat \Theta } \right) = {\rm{E}}\left[ {\left( {\widetilde \Theta – {\rm{E}}\left[ {\widetilde \Theta } \right]} \right) \cdot \left( {\widehat \Theta – {\rm{E}}\left[ {\widehat \Theta } \right]} \right)} \right] = {\rm{E}}\left[ {\widetilde \Theta \cdot \left( {\widehat \Theta – \Theta } \right)} \right] = 0\\ \widetilde \Theta = \widehat \Theta – \Theta \to {\mathop{\rm var}} \left( \Theta \right) = {\mathop{\rm var}} \left( {\widehat \Theta } \right) + {\mathop{\rm var}} \left( {\widetilde \Theta } \right) \end{array}$$

Linear LMS

Consider estimator of $\Theta$ of the form $\widehat \Theta = aX + b$ and minimize ${\rm{E}}\left[ {{{\left( {\Theta – aX – b} \right)}^2}} \right]$

$${\widehat \Theta _L} = {\rm{E}}\left[ \Theta \right] + \frac{{{\mathop{\rm cov}} \left( {X,\Theta } \right)}}{{{\mathop{\rm var}} \left( X \right)}}\left( {X – {\rm{E}}\left[ X \right]} \right)$$

$${\rm{E}}\left[ {{{\left( {{{\widehat \Theta }_L} – \Theta } \right)}^2}} \right] = \left( {1 – {\rho ^2}} \right)\sigma _\Theta ^2$$

Consider estimators of the form $\widehat \Theta = {a_1}{X_1} + \cdots + {a_n}{X_n} + b$ and minimize ${\rm{E}}\left[ {{{\left( {{a_1}{X_1} + \cdots + {a_n}{X_n} + b – \Theta } \right)}^2}} \right]$. Set derivatives to zero and linear system in $b$ and the $a_i$, only means, variances, covariances matter.

Cleanest linear LMS example

${X_i} = \Theta + {W_i}$, $\Theta ,{W_1}, \cdots ,{W_n}$ are independent, $\Theta \sim \mu ,\sigma _0^2$ and ${W_i} \sim 0,\sigma _i^2$, then

$${\widehat \Theta _L} = \frac{{\mu /\sigma _0^2 + \sum\limits_{i = 1}^n {{X_i}/\sigma _i^2} }}{{\sum\limits_{i = 1}^n {1/\sigma _i^2} }}$$

Classical statistical inference

Problem type

#1: hypothesis testing ${H_0}:\theta = 1/2 \ {\rm{versus}} \ {H_1}:\theta = 3/4$

#2: composite hypotheses ${H_0}:\theta = 1/2 \ {\rm{versus}} \ {H_1}:\theta \ne 1/2$

#3: estimation, design an estimator $\widehat \Theta$ to keep estimation error $\widehat \Theta – \theta$ small

Maximum likelihood estimation: pick $\theta$ that makes data most likely

$${\widehat \theta _{MAP}} = \arg \mathop {\max }\limits_\theta {p_\Theta }\left( {x;\theta } \right)$$

Example: $\mathop {\max }\limits_\theta \mathop \Pi \limits_{i = 1}^n \theta {e^{ – \theta {x_i}}}$

$$\begin{align} \mathop {\max }\limits_\theta \mathop \Pi \limits_{i = 1}^n \theta {e^{ – \theta {x_i}}} &\to \mathop {\max }\limits_\theta \left( {n\log \theta – \theta \sum\limits_{i = 1}^n {{x_i}} } \right)\\ \frac{n}{\theta } – \sum\limits_{i = 1}^n {{x_i}} = 0 &\to {\widehat \theta _{ML}} = \frac{n}{{{x_1} + \cdots + {x_n}}} \end{align}$$

desirable properties of estimators

(1) unbiased: ${\rm{E}}\left[ {{{\widehat \Theta }_n}} \right] = \theta$

(2) consistent: ${\widehat \Theta _n} \to \theta$ in probability

(3) small mean squared error (MSE): ${\rm{E}}\left[ {{{\left( {\widehat \Theta – \theta } \right)}^2}} \right] = {\mathop{\rm var}} \left( {\widehat \Theta – \theta } \right) + \left( {{\rm{E}}\left[ {\widehat \Theta – \theta } \right]} \right) = {\mathop{\rm var}} \left( {\widehat \Theta } \right) + {\left( {{\rm{biased}}} \right)^2}$

Confidence intervals (CIs)

random interval $\left[ {\widehat \Theta _n^ – ,\widehat \Theta _n^ + } \right]$ with an $1 – \alpha$ confidence interval

$${\rm{P}}\left( {\widehat \Theta _n^ – \le \theta \le \widehat \Theta _n^ + } \right) \ge 1 – \alpha$$

CI in estimation of the mean ${\widehat \Theta _n} = \left( {{X_1} + \cdots + {X_n}} \right)/n$

$$\Phi \left( {1.96} \right) = 1 – 0.05/2$$

$${\rm{P}}\left( {\frac{{\left| {{{\widehat \Theta }_n} – \theta } \right|}}{{\sigma /\sqrt n }} \le 1.96} \right) \approx 0.95$$

$${\rm{P}}\left( {{{\widehat \Theta }_n} – \frac{{1.96\sigma }}{{\sqrt n }} \le \theta \le {{\widehat \Theta }_n} + \frac{{1.96\sigma }}{{\sqrt n }}} \right) \approx 0.95$$

more generally

$$\Phi \left( z \right) = 1 – \alpha /2 \to {\rm{P}}\left( {{{\widehat \Theta }_n} – \frac{{z\sigma }}{{\sqrt n }} \le \theta \le {{\widehat \Theta }_n} + \frac{{z\sigma }}{{\sqrt n }}} \right) \approx 1 – \alpha$$

Since the $\sigma$ is unknown, then we should estimate the value of $\sigma$

option 1: upper bound on $\sigma$, for example Bernoulli $\sigma = \sqrt {p\left( {1 – p} \right)} \le 1/2$

option 2: ad hoc estimate of $\sigma$, for example Bernoulli$\theta$, $\widehat \sigma = \sqrt {\widehat \Theta \left( {1 – \widehat \Theta } \right)}$

option 3: generic estimation of the variance

$$\begin{array}{l} {\sigma ^2} = {\rm{E}}\left[ {{{\left( {{X_i} – \theta } \right)}^2}} \right]\\ \widehat \sigma _n^2 = \frac{1}{n}\sum\limits_{i = 1}^n {{{({X_i} – \theta )}^2}} \to {\sigma ^2}\\ \widehat S_n^2 = \frac{1}{{n – 1}}\sum\limits_{i = 1}^n {{{({X_i} – {{\widehat \Theta }_n})}^2}} \to {\sigma ^2} \end{array}$$