# Characterising Infinite Exchangeability by Positive Correlation

## Exchangeable sequence

An (infinite) sequence of random variables $X_1, X_2, \ldots$ is said to be an exchangeable process, if its probability law is invariant under permutation of indices, i.e. $\forall N$ and permutation $\pi$

$$
\mathbb{P}(X_1=x_1, X_2=x_2, \ldots, X_N=x_n) = P(X_{\pi(1)}=x_{\pi(1)}, X_{\pi(2)}=x_{\pi(2)}, \ldots, X_N=x_{\pi(N)})
$$

Exchangeable sequences are an important generalisation of i.i.d. (independent and identically distributed) sequences, and they are fundamentally interesting as a motivation for Bayesian analysis: See e.g. ([O'Neill 2009](https://www.jstor.org/stable/27919725?seq=1#metadata_info_tab_contents)).

A central result relating to exchangeable sequences is de Finetti's theorem (see e.g. [Serafino, 2016](http://philsci-archive.pitt.edu/12059/)) which states that infinitely exchangeable sequencces can always be decomposed as mixtures of i.i.d. sequences.

Informally, if $p$ denotes the joint distribution of $X_1,
\ldots, X_N$ the de Finetti decomposition looks like this:

$$
p(x_1, \ldots, x_N) = \int \prod_n p(x_{n=1}^N \vert \theta) d\pi(\theta)
$$

## Relationship with positive correlation

If a sequence is infinitely exchangeable, it implies positive correlation. Below is a proof sketch using the de Finetti decomposition:

\begin{align}
\mathbb{Cov}[X_i, X_j] &= \mathbb{E}[X_iX_j] \\
&= \sum_{x_i}\sum_{x_j}x_ix_j\mathbb{E}_\theta[p(x_i\vert \theta)p(x_j\vert \theta)] \\
&= \mathbb{E}_\theta[\sum_{x_i}\sum_{x_j}x_ix_jp(x_i\vert \theta)p(x_j\vert \theta)] \\
&= \mathbb{E}_\theta[\sum_{x_i}x_ip(x_i\vert \theta)\sum_{x_j}x_jp(x_j\vert \theta)]\\
&= \mathbb{E}_\theta[\mathbb{E}[X_i\vert \theta]^2]\\
&= \mathbb{V}[\mathbb{E}[X\vert F_X]] \geq 0
\end{align}

This result is proved in ([O'Neill 2009](https://www.jstor.org/stable/27919725?seq=1#metadata_info_tab_contents)), not sure if there's an earlier reference.

### Remark 1: finite exchangeability

Finite exchangeability is like exchangeability but defined for only a finite tuple $X_1, \ldots, X_N$ of random variables. It's a weaker property than (infinite) exchangeability and does not imply the existence of a Finetti decomposition. I will say a finite sequence $X_1, \ldots, X_N$ is infinitely exchangeable if it can be (infinitely) extended to an exchangeable infinite sequence. Not all finite exchangeable sequences are infinitely exchangeable. For more discussion on finite vs infinite exchangeable sequences see ([Diaconis and Freedman, 1980](https://projecteuclid.org/journals/annals-of-probability/volume-8/issue-4/Finite-Exchangeable-Sequences/10.1214/aop/1176994663.full)).

Finite exchangeability also doesn't guarantee non-negative covariance structure stated above. There's a simple example of a finite exchangeable sequence that infinitely exchangeable and has negative correlations. consider an urn with N balls in them, K blue and N-K red. We draw N balls from the urn without replacement (i.e. take all of them out in a random order). This sequence of lenght $N$ satisfies the finite exchangeability property, but there's no way to extend it to a sequence of length $N+1$ without breaking exchangeability.

If you convert the red balls to $+1$s and the blue balls to $-1$ the resulting sequence has negative covariance: if the first ball you draw is red, there are now fewer red balls left in the urn, so the probability of drawing red balls decreases.

## Remark: non-negative correlations are not sufficient

We have seen that non-negative covariance is a necessary consequence of infinite exchangeability. But is it sufficient? No.

To see this, consider the urn example from above. But now you convert red balls to $+1$ with probability $0.5$ and $-1$ with probability $0.5$, red balls to $+2$ with probability $0.5$ and $-2$ with probability $0.5$. In this resulting sequence, all covariances are $0$, but the process is still not extendable to a longer exchangeable sequence.

## Conjecture: Characterising infinite exchangeability

So just requiring $\mathbb{Cov}[X_1, X_2]\geq 0$ is not sufficient to characterise all infinitely exchangeable sequences, mainly because covariances capture only linear dependencies. Oerhaps a replacing the linear covariances with a stronger notion of 'non-negative relationship' could do the trick:

*Conjecture:* Let $X_1, \ldots, X_N$ be a (finite) exchangeable sequencec of random variables. The sequence can be extended into an infinitely exchangeabe sequence if and only if $\forall f$ measurable: $\mathbb{Cov}[f(X_1), f(X_2)]\geq 0$.

Proving one direction is trivial: if $f$ is a measurable function and $\{X_n\}_{n\in\mathbb{N}}$ is infinitely exchangeable, $\{f(X_n)\}_{n\in\mathbb{N}}$ is also infinitely exchangeable. Therefore $\mathbb{Cov}[f(X_1), f(X_2)]\geq 0$ must hold.

Not immediately clear how to prove the other direction.

## Remark: using characteristic RKHS

One can probably relax the "all measurable $f$" condition with "for all $f$ drawn from a sufficiently rich function class $\mathcal{F}$". One possible choice is a reproducing kernel Hilbert space as is done in [Gretton et al 2005](https://www.jmlr.org/papers/volume6/gretton05a/gretton05a.pdf). It is likely that

$$
\inf_{f\in H, \|f\|_\mathcal{H}=1} \mathbb{Cov}[f(X_1), f(X_2)]
$$

has an interpretation as the smallest eigenvalue of some cross-covariance operator or something along those lines, or equivalently that the condition for 'generalized positive covariance' becomes a condition that an operator is positive semi-definite.

## Implications

If one could characterise infinite exchangeability in terms of non-negative covariances, that would be first of all very interesting, as it might lead to possible generalisations of the Bayesian paradigm.

Secondly, it may provide a way of constructing flexible probabilistic models (parametric families of probability distributions) that are always exchangeable, which would be very useful in practicec.

## Extensions

it would be interesting to also characterise partially exchangeable sequences ([Diaconis and Freedman, 1980b](https://projecteuclid.org/journals/annals-of-probability/volume-8/issue-1/De-Finettis-Theorem-for-Markov-Chains/10.1214/aop/1176994828.full)) in a similar way.