### Exchangeability

In statistics, an **exchangeable sequence of random variables** (also sometimes **interchangeable**)^{[1]} is a sequence such that future samples behave like earlier samples, meaning formally that any order (of a finite number of samples) is equally likely. This formalizes the notion of "the future being predictable on the basis of past experience." It is closely related to the use of independent and identically-distributed random variables in statistical models. Exchangeable sequences of random variables arise in cases of simple random sampling.

## Contents

## Definition

Formally, an **exchangeable sequence of random variables**
is a finite or infinite sequence *X*_{1}, *X*_{2}, *X*_{3}, ... of random variables such that for any finite permutation σ of the indices 1, 2, 3, ..., (the permutation acts on only finitely many indices, with the rest fixed), the joint probability distribution of the permuted sequence

- $X\_\{\backslash sigma(1)\},\; X\_\{\backslash sigma(2)\},\; X\_\{\backslash sigma(3)\},\; \backslash dots$

is the same as the joint probability distribution of the original sequence.^{[1]}^{[2]}

(A sequence *E*_{1}, *E*_{2}, *E*_{3}, ... of events is said to be exchangeable precisely if the sequence of its indicator functions is exchangeable.) The distribution function *F*_{X1,...,Xn}(*x*_{1}, ... ,*x*_{n}) of a finite sequence of exchangeable random variables is symmetric in its arguments *x*_{1}, ... ,*x*_{n}. Olav Kallenberg provided an appropriate definition of exchangeability for continuous-time stochastic processes.^{[3]}^{[4]}

## History

The concept was introduced by William Ernest Johnson in his 1924 book *Logic, Part III: The Logical Foundations of Science*.^{[5]} Exchangeability is equivalent to the concept of statistical control introduced by Walter Shewhart also in 1924.^{[6]}^{[7]}

## Exchangeability and the i.i.d statistical model

The property of exchangeability is closely related to the use of independent and identically-distributed random variables in statistical models. A sequence of random variables that are independent and identically-distributed (i.i.d), conditional on some underlying distributional form is exchangeable. This follows directly from the structure of the joint probability distribution generated by the i.i.d form.

Moreover, the converse can be established for infinite sequences, through a celebrated representation theorem by Bruno de Finetti (later extended by other probability theorists such as Halmos and Savage). The extended versions of the theorem show that in any infinite sequence of exchangeable random variables, the random variables are conditionally independent and identically-distributed, given the underlying distributional form. This theorem is stated briefly below. (De Finetti's original theorem only showed this to be true for random indicator variables, but this was later extended to encompass all sequences of random variables.) Another way of putting this is that de Finetti's theorem characterizes exchangeable sequences as mixtures of i.i.d sequences — while an exchangeable sequence need not itself be unconditionally i.i.d, it can be expressed as a mixture of underlying i.i.d sequences.^{[1]}

This means that infinite sequences of exchangeable random variables can be regarded equivalently as sequences of conditionally i.i.d random variables, based on some underlying distributional form. (Note that this equivalence does not quite hold for finite exchangeability. However, for finite vectors of random variables there is a close approximation to the i.i.d model.) An infinite exchangeable sequence is strictly stationary and so a law of large numbers in the form of Birkhoff-Khinchin theorem applies.^{[4]} This means that the underlying distribution can be given an operational interpretation as the limiting empirical distribution of the sequence of values. The close relationship between exchangeable sequences of random variables and the i.i.d form means that the latter can be justified on the basis of infinite exchangeability. This notion is central to Bruno de Finetti's development of predictive inference and to Bayesian statistics. It can also be shown to be a useful foundational assumption in frequentist statistics and to link the two paradigms.^{[8]}

**The Representation Theorem:** This statement is based on the presentation in O'Neill (2009) in references below. Given an infinite sequence of random variables $\backslash bold\{X\}=(X\_1,X\_2,X\_3,...)$ we define the limiting empirical distribution function $F\_\backslash bold\{X\}$ by:

- $F\_\backslash bold\{X\}(x)\; =\; \backslash lim\_\{n\backslash to\backslash infty\}\; \backslash frac\{1\}\{n\}\; \backslash sum\_\{i=1\}^n\; I(X\_i\; \backslash le\; x).$

(This is the Cesaro limit of the indicator functions. In cases where the Cesaro limit does not exist this function can actually be defined as the Banach limit of the indicator functions, which is an extension of this limit. This latter limit always exists for sums of indicator functions, so that the empirical distribution is always well-defined.) If the sequence $\backslash bold\{X\}$ is exchangeable then the elements of $\backslash bold\{X\}\; |\; F\_\backslash bold\{X\}$ are independent with distribution function $F\_\backslash bold\{X\}$. This means that for any vector of random variables in the sequence we have joint distribution function given by:

- $\backslash Pr\; (X\_1\; \backslash le\; x\_1,X\_2\; \backslash le\; x\_2,...,X\_n\; \backslash le\; x\_n)\; =\; \backslash int\; \backslash prod\_\{i=1\}^n\; F(x\_i|\backslash theta)\backslash ,dP(F).$

If the distribution function $F\_\backslash bold\{X\}$ is indexed by another parameter $\backslash theta$ then (with densities appropriately defined) we have:

- $p(X\_1,X\_2,...,X\_n)\; =\; \backslash int\; \backslash prod\_\{i=1\}^n\; p(X\_i|\backslash theta)\backslash ,dP(\backslash theta).$

These equations show the joint distribution or density characterised as a mixture distribution based on the underlying limiting empirical distribution (or a parameter indexing this distribution).

## Covariance and Correlation

Exchangeable sequences have some basic covariance and correlation properties which mean that they are generally positively correlated. For infinite sequences of exchangeable random variables, the covariance between the random variables is equal to the variance of the mean of the underlying distribution function.^{[8]} For finite exchangeable sequences the covariance is also a fixed value which does not depend on the particular random variables in the sequence. There is a weaker lower bound than for infinite exchangeability and it is possible for negative correlation to exist.

**Covariance for exchangeable sequences (infinite):** If the sequence $X\_1,X\_2,X\_3,...$ is exchangeable then:

- $\backslash operatorname\{cov\}\; (X\_i,X\_j)\; =\; \backslash operatorname\{var\}\; (\backslash operatorname\{E\}(X\_i|F\_\backslash bold\{X\}))\; =\; \backslash operatorname\{var\}\; (\backslash operatorname\{E\}(X\_i|\backslash theta))\; \backslash ge\; 0\; \backslash quad\backslash text\{for\; \}i\; \backslash ne\; j.$

**Covariance for exchangeable sequences (finite):** If $X\_1,X\_2,...,X\_n$ is exchangeable with $\backslash sigma^2\; =\; \backslash operatorname\{var\}\; (X\_i)$ then:

- $\backslash operatorname\{cov\}\; (X\_i,X\_j)\; \backslash ge\; -\; \backslash frac\{\backslash sigma^2\}\{n-1\}\; \backslash quad\backslash text\{for\; \}i\; \backslash ne\; j.$

The finite sequence result may be proved as follows. Using the fact that the values are exchangeable we have:

- $$

\begin{align} 0 & \le \operatorname{var}(X_1 + \cdots + X_n) \\ & = \operatorname{var}(X_1) + \cdots + \operatorname{var}(X_n) + \underbrace{\operatorname{cov}(X_1,X_2) + \cdots\quad{}}_\text{all ordered pairs} \\ & = n\sigma^2 + n(n-1)\operatorname{cov}(X_1,X_2). \end{align}

We can then solve the inequality for the covariance yielding the stated lower bound. The non-negativity of the covariance for the infinite sequence can then be obtained as a limiting result from this finite sequence result.

Equality of the lower bound for finite sequences is achieved in a simple urn model: An urn contains 1 red marble and *n* − 1 green marbles, and these are sampled without replacement until the urn is empty. Let *X*_{i} = 1 if the red marble is drawn on the *i*th trial and 0 otherwise. A finite sequence that achieves the lower covariance bound cannot be extended to a longer exchangeable sequence.^{[9]}

## Examples

- Any convex combination or mixture distribution of iid sequences of random variables is exchangeable. A converse proposition is de Finetti's theorem.
^{[10]} - Suppose an urn, such as a Polya urn, contains
*n*red and*m*blue marbles. Suppose marbles are drawn without replacement until the urn is empty. Let*X*_{i}be the indicator random variable of the event that the*i*th marble drawn is red. Then {*X*_{i}}_{i=1,...n}is an exchangeable sequence. This sequence cannot be extended to any longer exchangeable sequence.

- Let $(X,\; Y)$ have a bivariate normal distribution with parameters $\backslash mu\; =\; 0$, $\backslash sigma\_x\; =\; \backslash sigma\_y\; =\; 1$ and an arbitrary correlation coefficient $\backslash rho\backslash in\; (-1,\; 1)$. The random variables $X$ and $Y$ are then exchangeable, but independent only if $\backslash rho=0$. The density function is $p(x,\; y)\; =\; p(y,\; x)\; \backslash propto\; \backslash exp\backslash left[-\backslash frac\{1\}\{2(1-\backslash rho^2)\}(x^2+y^2-2\backslash rho\; xy)\backslash right].$

## Applications

The von Neumann extractor is a randomness extractor that depends on exchangeability: it gives a method to take an exchangeable sequence of 0s and 1s (Bernoulli trials), with some probability *p* of 0 and $q=1-p$ of 1, and produce a (shorter) exchangeable sequence of 0s and 1s with probability 1/2.

Partition the sequence into non-overlapping pairs: if the two elements of the pair are equal (00 or 11), discard it; if the two elements of the pair are unequal (01 or 10), keep the first. This yields a sequence of Bernoulli trials with $p=1/2,$ as, by exchangeability, the odds of a given pair being 01 or 10 are equal.

Exchangeable random variables arise in the study of U statistics, particularly in the Hoeffding decomposition.^{[11]}

## See also

- Permutation tests, a statistical test based on exchanging between groups
- U-statistic

## Notes

## Bibliography

- Aldous, David J.,
*Exchangeability and related topics*, in: École d'Été de Probabilités de Saint-Flour XIII — 1983, Lecture Notes in Math. 1117, pp. 1–198, Springer, Berlin, 1985. 10.1007/BFb0099421 - Barlow, R. E. & Irony, T. Z. (1992) "Foundations of statistical quality control" in Ghosh, M. & Pathak, P.K. (eds.)
*Current Issues in Statistical Inference: Essays in Honor of D. Basu*, Hayward, CA: Institute of Mathematical Statistics, 99-112. - Bergman, B. (2009) "Conceptualistic Pragmatism: A framework for Bayesian analysis?",
*IIE Transactions*,**41**, 86–93 -
- Chow, Yuan Shih and Teicher, Henry,
*Probability theory. Independence, interchangeability, martingales,*Springer Texts in Statistics, 3rd ed., Springer, New York, 1997. xxii+488 pp. ISBN 0-387-98228-0 -
- Kallenberg, O.,
*Probabilistic symmetries and invariance principles*. Springer-Verlag, New York (2005). 510 pp. ISBN 0-387-25115-4. - Kingman, J. F. C.,
*Uses of exchangeability*, Ann. Probability 6 (1978) 83–197 2243211 - O'Neill, B. (2009) Exchangeability, Correlation and Bayes' Effect.
*International Statistical Review***77(2)**, pp. 241–250. 10.1111/j.1751-5823.2008.00059.x -
- Zabell, S. L. (1988) "Symmetry and its discontents", in Skyrms, B. & Harper, W. L.
*Causation, Chance and Credence,*pp*155-190, Kluwer* -