Model Settings

Suppose we have an urn with \(a\) black balls (denoted as \(1\)), and white balls (denoted as \(0\)). For each trail, we randomly draw one from the urn and then put back a copy of what was sampled(“over-replacing”), and thus, we have:

\[ P(X_1=1)=\frac{a}{a+b},P(X_1=0)=\frac{b}{a+b}, \] and \[ P(X_n=x_n|X_1=x_1,\cdots,X_{n-1}=x_{n-1})\\=(\frac{a+\sum_{i=1}^{n-1}x_{i}}{a+b+n-1})^{x_n}(\frac{b+\sum_{i=1}^{n-1}\bar x_{i}}{a+b+n-1})^{\bar x_n}, \] where \(X_1,\cdots,X_n\) are the results of each sampling which can be viewed as Bernoulli trails and \(x_i\in\{0,1\}\), \(\bar x_i=1-x_i\), \(\forall i=1,2,\cdots,n\).

Joint Probability Distribution

Now, we have a problem: what is the joint distribution of \(X_1,\cdots,X_n\)?

\[ \begin{aligned} &P(X_1=x_1,\cdots,X_n=x_n)\\ =&P(X_1=x_1)P(X_2=x_2|X_1=x_1)\cdots P(X_n=x_n|X_1=x_1,\cdots,X_{n-1}=x_{n-1})\\ =&\frac{[a^{x_1}(a+x_1)^{x_2}\cdots(a+x_1+\cdots+x_{n-1})^{x_n}][b^{\bar x_1}(b+\bar x_1)^{\bar x_2}\cdots (b+\bar x_1+\cdots+\bar x_{n-1})^{\bar x_n}]}{(a+b)(a+b+1)\cdots(a+b+n-1)}\\ =&\frac{[a(a+1)\cdots(a+\sum_{i=1}^{n}x_i-1)][b(b+1)\cdots(b+ \sum_{i=1}^{n}\bar x_i-1)]}{(a+b)(a+b+1)\cdots(a+b+n-1)}\\ =&\frac{[\Gamma(a+\sum_{i=1}^{n}x_i)/\Gamma(a)][\Gamma(b+\sum_{i=1}^{n}\bar x_i)/\Gamma(b)]}{\Gamma(a+b+n)/\Gamma(a+b)}\\ =&\frac{\Gamma(a+b)\Gamma(a+\sum_{i=1}^{n}x_i)\Gamma(b+n-\sum_{i=1}^{n}x_i)}{\Gamma(a+b+n)\Gamma(a)\Gamma(b)}. \end{aligned} \] We can see that this is a function with respect to \(\sum_{i=1}^nx_i\).

Exchangability

Let \(\pi=(\pi_1,\cdots,\pi_n)\) be a fixed permutation of \(\{1,2,\cdots,n\}\), and \(Y=(Y_1,\cdots,Y_n):=(X_{\pi_1},\cdots,X_{\pi_n})\). It means that \(Y=\{Y_1,\cdots,Y_n\}\) is a permutation of \(X=\{X_1,\cdots,X_n\}\).

Our problem is: what is the probability distribution \(P(Y_1=y_1,\cdots,Y_n=y_n)\)?

We define \(\phi=\{\phi_1,\cdots,\phi_n\}\), satisfying \(\phi_i=j\iff\pi_j=i\), and then we have

\[ \begin{aligned} P(Y_1=y_1,\cdots,Y_n=y_n)&=P(X_1=y_{\phi_1},\cdots,X_n=y_{\phi_n})\\ &=f(\sum_{i=1}^ny_{\phi_i})\\ &=P(X_1=y_1,\cdots,X_n=y_n). \end{aligned} \]

Definition If the distribution of \(X_\pi\) is the same as \(X\) for any permutation \(\pi\), then we say \(X\) is exchangeable.

Note: de Finetti viewed the exchangeability as an important way to express uncertainty.

A Fact about Identical Distribution

Exchangeable \(\Rightarrow\) Marginally identically distributed.

A Toy Example

\[ \begin{aligned} P(X_m=1)&=\sum_{x:x_m=1} P(X_1=x_1,\cdots,X_n=x_n)\\ &=\sum_{x:x_m=1}P(X_1=x_m,\cdots,X_m=x_1,\cdots,X_n=x_n)\\ &=P(X_1=1). \end{aligned} \] It means that \(X_1\) and \(X_m\) are (marginally) identically distributed.

2-Stage Experiment

Settings

\(Z\sim f\), \(X|Z=z\sim g\) other distribution.(Hierarchical model)

Fact

Mixture of conditional i.i.d. random variables are exchangable.

Example

If we have \(X=(X_1,\cdots,X_n)\), and \((X_i|Z=z)\sim \mathrm{Beroulli}(z)\), and \(X_1,X_2,\cdots,X_n\) are i.i.d..

  1. If \(Z\) satisfies \(P(Z=0.1)=P(Z=0.9)=\frac{1}{2}\), then we have \[ \begin{aligned} P(X=x)&=\frac{1}{2}P(X=x|Z=0.1)+\frac{1}{2}P(X=x|Z=0.9)\\ &=\frac{1}{2}(\frac{1}{10})^{\sum x_i}(\frac{9}{10})^{n-\sum x_i}+\frac{1}{2}(\frac{9}{10})^{\sum x_i}(\frac{1}{10})^{n-\sum x_i} \end{aligned} \]

  2. If \(Z\sim \mathrm{Beta}(a,b)\), which means the pdf \(f(z)=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}z^{a-1}(1-z)^{b-1}\), then

\[ P(X=x)=\int_0^1P(X=x|Z=z)dz=\frac{\Gamma(a+b)}{\Gamma(a)\Gamma(b)}\cdot\frac{\Gamma(a+\sum x_i)\Gamma(b+n-\sum x_i)}{\Gamma(a+b+n)}. \]

It is easy to see that the Polya urn model \(\mathrm{Polya}(a,b)\) is a Beta mixture of i.i.d. Bernoulli’s.

de Finetti Theorem

For \(X_1,\cdots,X_n\), they are exchageable if and only if \(\exists Z\sim p(z)\), such that \(X_i\)’s are i.i.d conditional on \(Z\).

Moreover, we have \[\lim_{n\to\infty}\frac{1}{n}\sum_{i=1}^n X_i=Z\ (\mathrm{a.s.}).\]

For extensions, see Hewitt-Sevage.