# Characterising Exchangeability by Correlations

A sequence $X_1, \ldots, X_N$ of random variables is finite exchangeable if for all permutations $\pi$

$$
P(X_1=x_1,\ldots,X_N=x_n) = P(X_1 = x_{\pi(1)},\ldots,X_N = x_{\pi(N)})
$$

An infinite collection of RVs $X_1, X_2, \ldots$ is infinite exchangeable, if for any $N$, $X_1, \ldots, X_N$ is exchangeable.

## Extending finite exch. sequences

Any finite subset of an exchangeable sequence is finite exchangeability. A natural question to ask is whether a finite exchangeable sequence of length $N$ can be extended to an infinitely exchangeable sequence.

The answer is: not always. The typical example is this. Take a bag of $N$ balls, $k$ of them blue, $N-k$ of them red. We draw from the bag **without** replacement $N$-times, and then note down the colours, $0$ for blue, $1$ for red. The resulting sequence of $0$s and $1$s displays finite exchangeability, however, there is no way to extend this sequence to be infinite exchangeable (homework to prove this).

Notice that the above sequence displays negative correlations. If we know that the first ball was blue, that decreases the probability that the next ball is blue, because there are now fewer blue balls in the bag. On the other hand, exchangeable sequences generally display non-negative correlation.

So: Not all finite exchangeable sequences can be extended to be infinitely exchangeable.

### Conjecture 1:

A finite exchangeable sequence of random variables $X_1, \ldots, X_N$ can be extended to an infinite exchangeable sequence if and only if

$$
\forall f\in\mathcal{F}, \mathbb{E}[X_1]=0: \mathbb{E}\left[f(X_1)f(X_2)\right] \geq 0
$$

for some suitably rich family of functions $\mathcal{F}$, such as members of a characteristic RKHS ([Sriperumbudur, 2011](https://jmlr.org/papers/volume12/sriperumbudur11a/sriperumbudur11a.pdf)).

## Partial exchangeability

Another interesting class of distributions are partially exchangeable sequences. A sequence of discrete random variables $X_1, \ldots, X_N$ is partially exchangeable if for all $x_1, \ldots, x_N$ and all transition-preserving permutation $\pi$ we have that
$P(X_1=x_1,\ldots,X_N=x_n) = P(X_1 = x_{\pi(1)},\ldots,X_N = x_{\pi(1)})$

A permutation $\pi$ preserves transitions if

$$
\forall i,j: \sum_{n=1}^{N-1} \mathrm{1}_{ [x_n=i]} \mathrm{1}_{[x_{n+1} = j]} =
\sum_{n=1}^{N-1} \mathrm{1}_{ [x_{\pi(n)}=i]} \mathrm{1}_{[x_{\pi(n+1)} = j]}
$$

where $1$ is the indicator function. These types of sequences are of interest because they can always be represented as a mixture of Markov-chains.

### Extending finite partially exchangeable sequences

One can ask the same kind of question as before, about partially exchangeable sequences. Are there finite p.e. sequences that can't be extended infinitely to p.e. sequences?

I believe it's possible to use a similar construction to what we did before. I came up with this, perhaps it appears somewhere, and it may be wrong:

Again, consider a bag of $N$ balls, some blue and some red. We draw all the N balls randomly without replacement, so we have a permutation of them. We start by setting $X_0=1$ ($X_0$ is not considered part of the sequence). Then for each blue ball, we set $X_n = -X_{n-1}$ and for each red ball we set $X_n = X_{n-1}$. I believe this sequence will satisfy finite partial exchangeability, but cannot be extended to an infinite partially exchangeable sequence. Notice also the following.

$$
\mathbb{E}[X_{i+1}X_{j+1}\vert X_i = X_j] < 0
$$

This is because, if $X_{i+1}$ has the same sign as $X_i$, that makes it less likely that $X_{j+1}$ has the same sign as $X_j$ because there are fewer red balls left in the bag. So the probability that $X_{i+1}$ and $X_{j+1}$ have opposite signs is higher than $0.5$.

### Conjecture 2

It is possible to characterise infinite p.e. sequences as follows:

A finite partially exchangeable sequence of random variables $X_1, \ldots, X_N$ can be extended to an infinite partially exchangeable sequence if and only if

\begin{align}
&\forall i,j, \vert i - j\vert>1\\
&\forall f\in\mathcal{F}:\\
&\mathbb{Cov}[f(X_{i+1})f(X_{j+1})\vert X_i = X_j] \geq 0
\end{align}

for some suitably rich family of functions $\mathcal{F}$, such as members of a characteristic RKHS.