Central Limit Theorem and Law of Large Numbers

Bounds

Markov Bound

Questo bound è abbastanza banale se fatto da un punto di vista grafico, comunque afferma che

$$P(X\ge y)\le \frac{E[X]}{y}$$

Il motivo è che (assumendo che $X$ sia una variabile aleatoria non negativa)

$$yP(X\ge y)=y{\int }_{x=y}^{+\infty }f(x)dx\le {\int }_{x=y}^{+\infty }xf(x)d\le {\int }_{-\infty }^{+\infty }xf(x)d=E[X]$$

Il che finisce la dimostrazione.

Chebychev Bound

Questa è una conseguenza abbastanza diretta sul bound precedente: Afferma che

$$P(|x-E[X]|\ge y)\le \frac{{\sigma }^2}{y^2}$$

E in pratica dice che all'infinito viene tutto compattata sul valore atteso La dimostrazione è abbastanza semplice, si sostituisce $(x-E[X]{)}^2$ su $X$ di Markov e ${\epsilon }^2$ a $y$ e poi si dovrebbe già avere il risultato

Chernoff Bound

Asserisce che

$$P(Z\ge t)\le \underset{s>0}{\inf }{e}^{-st}{M}_Z(s)=\underset{s>0}{\inf }{e}^{-st}E[e^{sZ}]$$

Moments of random variable

https://en.wikipedia.org/wiki/Moment-generating_function Per capire il significato di questo bound invece, è necessario prima capire cosa sia un moment generating function. È una funzione generale che crea i momenti di una variabile aleatoria. Un momento per una variabile aleatoria è descrivibile come n-esimo momento: $E[X^n]$ La funzione generatrice dei momenti è describile come:

$$M_X(\lambda )=E[\exp (\lambda X)]$$

Il motivo per cui vale, è che con l'espansione di taylor, vedi Hopital, Taylor, Peano Possiamo estrarre in modo abbastanza semplice i momenti: Infatti:

$$e^{tX}=1+tX+\frac{t^2{X}^2}{2!}+\frac{t^3{X}^3}{3!}+\dots$$

Quindi per esempio se volessimo il primo momento, prendiamo la derivata rispetto a $t$e settiamo $t=0$, perché la cosa molto bella è che i coefficienti si cancellano tutti, e l'unico termine che rimane senza $t$ è il momento cercato, per questo motivo estraiamo easy i momenti.

Dimostrazione Chernoff's Bound

Anche questa è una conseguenza abbastanza immediata di Markov, viene affermato che

$$P(Z\ge t)\le \underset{s>0}{\inf }{e}^{-st}{M}_Z(s)=\underset{s>0}{\inf }{e}^{-st}E[e^{sZ}]$$

Guardandolo dall'altro in basso non ho idea del perché valga.

La dimostrazione avviene così

$$P(Z\ge t)=P(e^{sZ}\ge e^{st})\le \frac{E[e^{sZ}]}{e^{st}}$$

Dove $s$ è qualunque $s>0$ perché per quello la funzione resta crescente, e quindi la dimostrazione vale ancora. La cosa interessante di questo bound è che la probabilità che succeda scende in modo esponenziale.

Hoeffding's Inequality

Anche conosciuto come Chernoff or Okamoto Bound. L'enunciato è che se considero la somma delle classiche variabili aleatorie con stessa media varianza $S_n$ allora vale che, tale per cui con probabilità $1$ vale che $a_i\le X_i\le b_i$. Ricorda che $S_n={\sum }_{i=1}^n{X}_i$

$$P(|S_n-\mathbf{E}[S_n]|\ge t)\le 2e^{-2t^2/\sum (b_i-a_i{)}^2}$$

Questo ci dice quanto velocemente la media converge nel valore atteso che ci aspettiamo per la legge dei grandi numeri.

Simpler form

Se supponiamo che $X_i$ siano tutte in $[0,C]$ allora possiamo scrivere la relazione in forma più elegante come

$$P(|S_n-\mathbf{E}[S_n]|\ge t)\le 2e^{-2N{t}^2/C^2}$$

Ci permette di avere un bound su accuratezza in funzione del numero di samples che andiamo a prendere.

La dimostrazione di questo mi sembra abbastanza tecnica, c'è bisogno di guardare https://web.eecs.umich.edu/~cscott/past_courses/eecs598w14/notes/03_hoeffding.pdf Oppure https://cs229.stanford.edu/extra-notes/hoeffding.pdf.

Non ho bene capito l'utilità se non nel caso Bernoulliano in cui sembra si semplifichi abbastanza questo.

This inequality has been proven quite useful. See Provably Approximately Correct Learning, Tabular Reinforcement Learning.

Hoeffding's Lemma

$$\mathbb{E}[e^{sX}]\le \exp \left(\frac{s^2(b-a{)}^2}{8}\right)$$

Proof of Hoeffding's Inequality

TODO.

Law of Large numbers

Weak Law

La dimostrazione di questo è molto semplice, basta avere Chebicheff

Questa è l'intuizione di quanto presente nell WLLN

Abbiamo mean square convergence.

Abbiamo che vale:

$$\mathbb{P}\left({\left(\frac{S_n-n\bar{X}}{n}\right)}^2>y\right)\le \frac{{\sigma }_X^2}{ny}$$

E poi settando $y={\epsilon }^2$ si può avere il risultato. Nella forma corretta. Vedere capitolo 1.5 in questo.

Si può scrivere:

$$\underset{n\to \infty }{\lim }E\left[{\left(\frac{S_n}{n}-\bar{X}\right)}^2\right]=0$$

In questo senso possiamo dire che la successione $S_n$ arriverà sempre alla media.

Ricordiamo che $S_n=X_1+X_2+\cdots +X_n$. Dove tutte le variabili $X_i$ sono IID con media $\bar{X}$ e varianza ${\sigma }^2$.

Weak law without finite variance

Potremo scrivere

$$\underset{n\to \infty }{\lim }\mathbb{P}\left(\mid \frac{S_n}{n}-E[X]\mid >\epsilon \right)=0$$

Teorema 1.5.3 nelle note. Questa è la convergenza in probabilità della serie di variabili aleatorie. Con strumenti più avanzati è possibile dimostrare anche la convergenza con probabilità 1 anche in casi di varianza infinita. Questa è l'unica differenza con la versione Strong della legge dei grandi numeri.

Convergence types

We need a lot of care when defining the notions of convergence for probability distributions because the same ideas that applied to the real numbers do not apply here anymore. For example, in calculus if we have a sequence $x_1,\dots ,x_n\dots$ such that $\forall i\in \mathbb{N},x_i=x$ for a certain $x$ it's clear that ${\lim }_{n\to \infty }{x}_n=x$, by that definition. The same does not apply if we take a sequence of normally distributed random values $X_1,\dots ,X_n\dots$, this does not converge to the distribution $X\sim \mathcal{N}(0,1)$ in the classical sense, because we can't directly compare them. For instance $P(X_n=X)=0$ because both are continuous random variables, and the probability of it is always zero for the integral has zero length. This is why it's important to distinguish various types of convergence in probability.

Convergence in distribution

Una sequenza di variabili aleatorie $Z_1,Z_2,\dots$ converge in distribuzione se vale

$$\underset{n\to \infty }{\lim }{F}_{Z_n}(z)=F_Z(z)$$

Per ogni $z$ in cui $F_Z(z)$ è continua. Una sequenza di distribuzioni che converge a una distribuzione. Un esempio in cui questo vale è il central limit theorem in cui definiamo

$$Z_n=\frac{S_n-n\bar{X}}{\sigma \sqrt{n}}$$

Converge alla normale, 0, 1 gaussiana. Un altro esempio è la weak law of large numbers, in cui $\frac{S_n}{n}$ converge a $\bar{X}$.

Convergence in probability

Given the sequence of random variables $Z_1,Z_2,\dots$, this converges in probability to $Z$ if the following holds:

$$\underset{n\to \infty }{\lim }P(\mid Z_n-Z\mid >\epsilon )=0$$

So we care about the value of the single probability. Vale anche qui l'esempio della WLLN.

Convergence in mean square

Una sequenza di $Z_1,Z_2,\dots$ converge in mean square a $Z$ se vale

$$\underset{n\to \infty }{\lim }E[(Z_n-Z{)}^2]=0$$

La nota è che Mean Square -> Convergence probability -> Convergence in distribution. This is usually useful just to prove the convergence in probability.

Convergence almost everywhere

(Il prof. lo chiama with probability 1 e secondo lui serve sapere measure theory per poter comprendere la definizione originale).

Definiamo una sequenza $Z_1,Z_2,\dots$ e $\Omega$ il suo spazio campionatorio e sia $Z$ una altra variabile aleatoria, allora la sequenza converge con probabilità 1 se vale

$$\mathbb{P}(\{\omega \in \Omega :\underset{n\to \infty }{\lim }{Z}_n(\omega )=Z(\omega )\})=1$$

Ossia, per definizione di variabile aleatoria $Z_n(\omega )$ è un valore reale, queste sequenze di numeri reali a volte convergono, se convergono vogliamo che il valore sia esattamente $Z(\omega )$. Quello che vogliamo dire con questo è che la probabilità degli elementi dello spazio campionatorio che creano sequenze che convergono è uguale a 1.

Central Limit Theorem

By Lindeberg-Lévy. It is possible to estimate the distribution of the average of the random variable.

The Bernoulli Case

The theorem

$$\underset{n\to \infty }{\lim }\left[\mathbb{P}\left(\frac{S_n-n\bar{X}}{\sqrt{n}\sigma }\le y\right)\right]={\int }_{-\infty }^y\frac{1}{\sqrt{2\pi }}\exp \left(-\frac{x^2}{2}\right)dx$$

Ossia che la sequenza di variabili aleatorie

$$Z_i=\frac{S_i-n\bar{X}}{\sqrt{i}\sigma }$$

Convergerà alla gaussiana normale. È un motivo per cui è una distribuzione molto importante.

Si può anche scrivere con convergenza in distribuzione:

$$\sqrt{n}(\bar{X}-\mu )\stackrel{d}{\to }\mathcal{N}(0,{\sigma }^2)$$

La cosa importante da ricordare è che per distribuzioni con varianza finita avremo una distribuzione normale con varianza zero e concentrata sulla media, mentre per distribuzioni con varianza infinita avremo una distribuzione anche lì con heavy-tail (che è il motivo per cui ha varianza infinita), il che significa che avremo una altra distribuzione con varianza infinita.