Instatistics, anexchangeable sequence of random variables (also sometimesinterchangeable)^[1] is a sequenceX₁, X₂, X₃, ... (which may be finitely or infinitely long) whosejoint probability distribution does not change when the positions in the sequence in which finitely many of them appear are altered. In other words, the joint distribution is invariant to finite permutation. Thus, for example the sequences

${\displaystyle X_1,X_2,X_3,X_4,X_5,X_6\text{ and }{X}_3,X_6,X_1,X_5,X_2,X_4}$

both have the same joint probability distribution.

It is closely related to the use ofindependent and identically distributed random variables in statistical models. Exchangeable sequences of random variables arise in cases ofsimple random sampling.

Formally, anexchangeable sequence of random variables is a finite or infinite sequenceX₁, X₂, X₃, … ofrandom variables such that for any finitepermutation σ of the indices 1, 2, 3, … (the permutation acts on only finitely many indices, with the rest fixed) thejoint probability distribution of the permuted sequence

${\displaystyle X_{\sigma (1)},X_{\sigma (2)},X_{\sigma (3)},\dots }$

is the same as the joint probability distribution of the original sequence.^[1][2] A sequenceE₁,E₂,E₃, … of events is said to be exchangeable iff the sequence of itsindicator functions is exchangeable.

The distribution functionF_X1, …,Xn(x₁, …,x_n) of a finite sequence of exchangeable random variables is symmetric in its argumentsx₁, …,x_n.Olav Kallenberg provided an appropriate definition of exchangeability for continuous-time stochastic processes.^[3][4]

The concept was introduced byWilliam Ernest Johnson in his 1924 bookLogic, Part III: The Logical Foundations of Science.^[5] Exchangeability is equivalent to the concept ofstatistical control introduced byWalter Shewhart also in 1924.^[6][7]

The property of exchangeability is closely related to the use ofindependent and identically distributed (i.i.d.) random variables in statistical models.^[8] A sequence of random variables that are 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.

Mixtures of exchangeable sequences (in particular, sequences of i.i.d. variables) are exchangeable. The converse can be established for infinite sequences, through an importantrepresentation theorem byBruno de Finetti (later extended by other probability theorists such asHalmos andSavage).^[9] The extended versions of the theorem show that in any infinite sequence of exchangeable random variables, the random variables are conditionally i.i.d., 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 isstrictly stationary and so alaw of large numbers in the form ofBirkhoff–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 toBruno de Finetti’s development ofpredictive inference and toBayesian statistics. It can also be shown to be a useful foundational assumption infrequentist statistics and to link the two paradigms.^[10]

The representation theorem: This statement is based on the presentation in O’Neill (2009) in the references below. Given an infinite sequence of random variables${\displaystyle \mathbf{X}=(X_1,X_2,X_3,\dots )}$ we define the limitingempirical distribution function${\displaystyle F_{\mathbf{X}}}$ by

${\displaystyle F_{\mathbf{X}}(x)=\underset{n\to \mathrm{\infty }}{lim}\frac{1}{n}\sum _{i=1}^{n}I(X_i\le x).}$

(This is theCesàro limit of the indicator functions. In cases where the Cesàro limit does not exist this function can actually be defined as theBanach 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.) This means that for any vector of random variables in the sequence we have joint distribution function given by

${\displaystyle Pr(X_1\le x_1,X_2\le x_2,\dots ,X_n\le x_n)=\int \prod _{i=1}^n{F}_{\mathbf{X}}(x_i)dP(F_{\mathbf{X}}).}$

If the distribution function${\displaystyle F_{\mathbf{X}}}$ is indexed by another parameter${\displaystyle \theta }$ then (with densities appropriately defined) we have

${\displaystyle p_{X_1,\dots ,X_n}(x_1,\dots ,x_n)=\int \prod _{i=1}^n{p}_{X_i}(x_i\mid \theta )dP(\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).

Note that not all finite exchangeable sequences are mixtures of i.i.d.. To see this, consider sampling without replacement from afinite set until no elements are left. The resulting sequence is exchangeable, but not a mixture of i.i.d.. Indeed, conditioned on all other elements in the sequence, the remaining element is known.

Exchangeable sequences have some basiccovariance 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.^[10] 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${\displaystyle X_1,X_2,X_3,\dots }$ is exchangeable, then

${\displaystyle \mathrm{cov}(X_i,X_j)=\mathrm{var}(\mathrm{E}(X_i\mid F_{\mathbf{X}}))=\mathrm{var}(\mathrm{E}(X_i\mid \theta ))\ge 0\text{for }i\ne j.}$

Covariance for exchangeable sequences (finite): If${\displaystyle X_1,X_2,\dots ,X_n}$ is exchangeable with${\displaystyle {\sigma }^2=\mathrm{var}(X_i)}$, then

${\displaystyle \mathrm{cov}(X_i,X_j)\ge -\frac{{\sigma }^2}{n-1}\text{for }i\ne j.}$

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

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 andn − 1 green marbles, and these are sampled without replacement until the urn is empty. LetX_i = 1 if the red marble is drawn on thei-th trial and 0 otherwise. A finite sequence that achieves the lower covariance bound cannot be extended to a longer exchangeable sequence.^[11]

• Anyconvex combination ormixture distribution ofiid sequences of random variables is exchangeable. A converse proposition isde Finetti's theorem.^[12]
• Suppose anurn contains${\displaystyle n}$ red and${\displaystyle m}$ blue marbles. Suppose marbles are drawn without replacement until the urn is empty. Let${\displaystyle X_i}$ be the indicator random variable of the event that the${\displaystyle i}$-th marble drawn is red. Then${\displaystyle {\left\{X_i\right\}}_{i=1,\dots ,n+m}}$ is an exchangeable sequence. This sequence cannot be extended to any longer exchangeable sequence.
• Suppose an urn contains${\displaystyle n}$ red and${\displaystyle m}$ blue marbles. Further suppose a marble is drawn from the urn and then replaced, with an extra marble of the same colour. Let${\displaystyle X_i}$ be the indicator random variable of the event that the${\displaystyle i}$-th marble drawn is red. Then${\displaystyle {\left\{X_i\right\}}_{i\in \mathbb{N}}}$ is an exchangeable sequence. This model is calledPolya's urn.
• Let${\displaystyle (X,Y)}$ have abivariate normal distribution with parameters${\displaystyle \mu =0}$,${\displaystyle {\sigma }_x={\sigma }_y=1}$ and an arbitrarycorrelation coefficient${\displaystyle \rho \in (-1,1)}$. The random variables${\displaystyle X}$ and${\displaystyle Y}$ are then exchangeable, but independent only if${\displaystyle \rho =0}$. Thedensity function is${\displaystyle p(x,y)=p(y,x)\propto \exp \left[-\frac{1}{2(1-{\rho }^2)}(x^2+y^2-2\rho xy)\right].}$

Thevon Neumann extractor is arandomness extractor that depends on exchangeability: it gives a method to take an exchangeable sequence of 0s and 1s (Bernoulli trials), with some probabilityp of 0 and${\displaystyle 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${\displaystyle 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 ofU statistics, particularly in the Hoeffding decomposition.^[13]

Exchangeability is a key assumption of the distribution-free inference method ofconformal prediction.^[14]

• De Finetti theorem
• Hewitt-Savage zero-one law
• Resampling
• Resampling (statistics) § Permutation tests, statistical tests based on exchanging between groups

• 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.ISBN 978-3-540-15203-3doi:10.1007/BFb0099421
• 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
• Dawid, A. Philip (2013). "Exchangeability and its ramifications". In Damien, Paul; et al. (eds.).Bayesian Theory and Applications. Oxford University Press. pp. 19–30.ISBN 978-0-19-969560-7.
• 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–197MR 0494344JSTOR 2243211
• O'Neill, B. (2009) Exchangeability, Correlation and Bayes' Effect.International Statistical Review77(2), pp. 241–250.ISBN 978-3-540-15203-3doi:10.1111/j.1751-5823.2008.00059.x
• Taylor, Robert Lee; Daffer, Peter Z.; Patterson, Ronald F. (1985).Limit theorems for sums of exchangeable random variables. Rowman and Allanheld. pp. 1–152.ISBN 9780847674350.

• Statistical randomness
• Types of probability distributions

• Articles with short description
• Short description is different from Wikidata