Exchangeable random variables: Difference between revisions

Revision as of 00:40, 26 July 2017

Latest revision as of 20:51, 5 March 2025

(42 intermediate revisions by 26 users not shown)

Line 1:

{{Short description|Concept in statistics}}

In [[statistics]], an '''exchangeable sequence of random variables''' (also sometimes '''interchangeable''')<ref name="ChowTeicher"/> 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]].

In [[statistics]], an '''exchangeable sequence of random variables''' (also sometimes '''interchangeable''')<ref name="ChowTeicher"/> is a sequence ''X''₁,&nbsp;''X''₂,&nbsp;''X''₃,&nbsp;... (which may be finitely or infinitely long) whose [[joint 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

: <math> X_1, X_2, X_3, X_4, X_5, X_6 \quad \text{ and } \quad X_3, X_6, X_1, X_5, X_2, X_4 </math>

both have the same joint probability distribution.

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]].

== Definition ==

Formally, an '''exchangeable sequence of random variables''' is a finite or infinite sequence ''X''₁,&nbsp;''X''₂,&nbsp;''X''₃,&nbsp;... of [[random variable]]s 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

Formally, an '''exchangeable sequence of random variables'''

is a finite or infinite sequence ''X''₁,&nbsp;''X''₂,&nbsp;''X''₃,&nbsp;... of [[random variable]]s 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

:<math> X_{\sigma(1)}, X_{\sigma(2)}, X_{\sigma(3)}, \dots</math>

Line 10 ⟶ 16:

* Chow, Yuan Shih and Teicher, Henry, ''Probability theory. Independence, interchangeability, martingales,'' Springer Texts in Statistics, 3rd ed., Springer, New York, 1997. xxii+488 pp.&nbsp;{{ISBN|0-387-98228-0}}</ref><ref>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.&nbsp;1–198, Springer, Berlin, 1985. {{ISBN|978-3-540-15203-3}} {{doi|10.1007/BFb0099421}}</ref>

(A sequence ''E''₁, ''E''₂, ''E''₃, ... of events is said to be exchangeable precisely if the sequence of its [[indicator function]]s is exchangeable.) The distribution function ''F''_{''X''_''1'',...,''X''_''n''}(''x''₁, ..., ''x''_''n'') of a finite sequence of exchangeable random variables is symmetric in its arguments {{nowrap|''x''₁, ... , ''x''_''n''.}} [[Olav Kallenberg]] provided an appropriate definition of exchangeability for continuous-time stochastic processes.<ref>{{cite journal | last=Diaconis| first=Persi | authorlinkauthor-link=Persi Diaconis | title=Book review: ''Probabilistic symmetries and invariance principles'' (Olav Kallenberg, Springer, New York, 2005) | journal=Bulletin of the AmerericanAmerican Mathematical Society (|series=New Series) | volume=46 | year=2009 | issue=4 | doi=10.1090/S0273-0979-09-01262-2 | url=http://www.ams.org/journals/bull/2009-46-04/S0273-0979-09-01262-2/home.html | pages=691–696 | mr=2525743| doi-access=free }}</ref><ref name="Kallenberg" >[[Olav Kallenberg|Kallenberg, O.]], ''Probabilistic symmetries and invariance principles''. Springer-Verlag, New York (2005). 510 pp.&nbsp;{{ISBN|0-387-25115-4}}.</ref>

== History ==

The concept was introduced by [[William Ernest Johnson]] in his 1924 book ''Logic, Part III: The Logical Foundations of Science''.<ref>Zabell{{ (cite journal | title=Predicting the unpredictable | year=1992) | journal=Synthese | volume=90 | issue=2 | page=205 | doi=10.1007/bf00485351 | last1=Zabell | first1=S. L. | s2cid=9416747 }}</ref> Exchangeability is equivalent to the concept of [[statistical control]] introduced by [[Walter Shewhart]] also in 1924.<ref>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.</ref><ref>Bergman, B. (2009) "Conceptualistic Pragmatism: A framework for Bayesian analysis?", ''IIE Transactions'', '''41''', 86–93</ref>

== 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|independent and identically distributed]] (i.i.d.) random variables in statistical models.<ref>{{cite book A|last1=Cordani sequence|first1=L. ofK. random|last2=Wechsler variables|first2=S. that|year=2006 are|chapter=Teaching [[independentindependence and identicallyexchangeability |title=Proceedings of the International Conference on Teaching Statistics |___location=Den Haag |publisher=International Association for Statistical Education |chapter-distributedurl=https://iase-web.org/documents/papers/icots7/3I1_CORD.pdf?1402524964 }}</ref> A sequence of random variables|independent andthat identically-distributed]]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.

MoreoverMixtures of exchangeable sequences (in particular, thesequences of i.i.d. variables) are exchangeable. The converse can be established for infinite sequences, through an important [[de Finetti's theorem|representation theorem]] by [[Bruno de Finetti]] (later extended by other probability theorists such as [[Paul Halmos|Halmos]] and [[Leonard Jimmie Savage|Savage]]).<ref>{{cite book |first=P. |last=Diaconis |authorlink=Persi Diaconis |chapter=Recent Progress on de Finetti's Notions of Exchangeability |pages=111–125 |year=1988 |title=Bayesian Statistics |volume=3 |editor1-first=J. M. |editor1-last=Bernardo |editor1-link=José-Miguel Bernardo |editor2-first=M. H. |editor2-last=DeGroot |editor3-first=D. V. |editor3-last=Lindley |editor4-first=A. F. M. |editor4-last=Smith |display-editors=1 |publisher=Oxford University Press |isbn=0-19-852220-7 }}</ref> 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 random variables|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 — whilesequences—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.<ref name="ChowTeicher"/>

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-KhinchinBirkhoff–Khinchin theorem]] applies.<ref name="Kallenberg"/> 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|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.<ref name="O'Neill">{{cite journal |last=O'Neill |first=B. |year=2009 |title=Exchangeability, Correlation and Bayes' Effect |journal=International Statistical Review |volume=77 |issue=2 |pages=241–250 |doi=10.1111/j.1751-5823.2008.00059.x }}</ref>

* O'Neill, B. (2009) Exchangeability, Correlation and Bayes' Effect. ''International Statistical Review'' '''77(2)''', pp. 241-250.</ref>

'''The Representationrepresentation Theoremtheorem:''' This statement is based on the presentation in O'Neill (2009) in references below. Given an infinite sequence of random variables <math>\boldmathbf{X}=(X_1,X_2,X_3,...\ldots)</math> we define the limiting [[empirical distribution function]] <math>F_\boldmathbf{X}</math> by:

::::: <math>F_\boldmathbf{X}(x) = \lim_{n\to\infty} \frac{1}{n} \sum_{i=1}^n I(X_i \le x).</math>

(This is the [[Cesaro summation|CesaroCesàro limit]] of the indicator functions. In cases where the CesaroCesàro 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 <math>\bold{X}</math> is exchangeable then the elements of <math>\bold{X} | F_\bold{X}</math> are independent with distribution function <math>F_\bold{X}</math>. This means that for any vector of random variables in the sequence we have joint distribution function given by:

::::: <math>\Pr (X_1 \le x_1,X_2 \le x_2,...\ldots,X_n \le x_n) = \int \prod_{i=1}^n F_\boldmathbf{X}(x_i)\,dP(F_\boldmathbf{X}).</math>

If the distribution function <math>F_\boldmathbf{X}</math> is indexed by another parameter <math>\theta</math> then (with densities appropriately defined) we have:

::::: <math>p(p_{X_1,X_2,...\ldots,X_n}(x_1,\ldots,x_n) = \int \prod_{i=1}^n p(p_{X_i|}(x_i\mid\theta)\,dP(\theta).</math>

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 a [[finite 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.

== Covariance and Correlationcorrelation ==

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.<ref name="O'Neill"/> 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.

<br>'''Covariance for exchangeable sequences (infinite):''' If the sequence <math>X_1,X_2,X_3,...\ldots</math> is exchangeable, then:

::::: <math> \operatorname{cov} (X_i,X_j) = \operatorname{var} (\operatorname{E}(X_i|\mid F_\boldmathbf{X})) = \operatorname{var} (\operatorname{E}(X_i|\mid\theta)) \ge 0 \quad\text{for }i \ne j.</math>

<br>'''Covariance for exchangeable sequences (finite):''' If <math>X_1,X_2,...\ldots,X_n</math> is exchangeable with <math>\sigma^2 = \operatorname{var} (X_i)</math>, then:

::::: <math> \operatorname{cov} (X_i,X_j) \ge - \frac{\sigma^2}{n-1} \quad\text{for }i \ne j.</math>

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

:: <math>

\begin{align}

0 & \le \operatorname{var}(X_1 + \cdots + X_n) \\

Line 64 ⟶ 69:

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.

<br>Equality of the lower bound for finite sequences is achieved in a simple urn model: An urn contains 1 red marble and ''n''&nbsp;&minus;&nbsp;1 green marbles, and these are sampled without replacement until the urn is empty. Let ''X''_''i''&nbsp;=&nbsp;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.<ref>{{cite book|title=Limit theorems for sums of exchangeable random&nbsp;variables|first1=Robert Lee|last1=Taylor|first2=Peter Z.|last2=Daffer|first3=Ronald F.|last3=Patterson|mr=|ref=harv|publisher=Rowman and Allanheld|url=https://books.google.com/books?id=6RaoAAAAIAAJ|year=1985|pages=1–152|isbn=9780847674350}}</ref>

== Examples ==

* Any [[convex combination]] or [[mixture distribution]] of [[iid]] sequences of random variables is exchangeable. A converse proposition is [[de Finetti's theorem]].<ref>Spizzichino, Fabio ''Subjective probability models for lifetimes''. Monographs on Statistics and Applied Probability, 91. ''Chapman & Hall/CRC'', Boca Raton, FL, 2001. xx+248 pp.&nbsp;{{ISBN|1-58488-060-0}}

</ref>

* Suppose an [[urn model|urn]] contains ''<math>n''</math> red and ''<math>m''</math> blue marbles. Suppose marbles are drawn without replacement until the urn is empty. Let ''X''<submath>''i''X_i</submath> be the indicator random variable of the event that the ''<math>i''</math>-th marble drawn is red. Then {''X''<sub>''i''</submath>\left\{ X_i \right\}<sub>''_{i''=1,...'' \dots, n''+m}</submath> is an exchangeable sequence. This sequence cannot be extended to any longer exchangeable sequence.

* Suppose an urn contains <math>n</math> red and <math>m</math> blue marbles. Further suppose a marble is drawn from the urn and then replaced, with an extra marble of the same colour. Let <math>X_i</math> be the indicator random variable of the event that the <math>i</math>-th marble drawn is red. Then <math>\left\{ X_i \right\}_{i\in \N}</math> is an exchangeable sequence. This model is called [[Polya's urn]].

* Let <math>(X, Y)</math> have a [[bivariate normal distribution]] with parameters <math>\mu = 0</math>, <math>\sigma_x = \sigma_y = 1</math> and an arbitrary [[Pearson product-moment correlation coefficient|correlation coefficient]] <math>\rho\in (-1, 1)</math>. The random variables <math>X</math> and <math>Y</math> are then exchangeable, but independent only if <math>\rho=0</math>. The [[density function]] is <math>p(x, y) = p(y, x) \propto \exp\left[-\frac{1}{2(1-\rho^2)}(x^2+y^2-2\rho xy)\right].</math>

Line 78 ⟶ 84:

Exchangeable random variables arise in the study of [[U statistic]]s, particularly in the Hoeffding decomposition.<ref>{{cite book |last=Borovskikh | first=Yu. V. | title=''U''-statistics in Banach spaces | publisher=VSP | ___location=Utrecht | year=1996 | pages=365–376 | isbn=90-6764-200-2 | mr=1419498|chapter=Chapter 10 Dependent variables}}</ref>

Exchangeability is a key assumption of the distribution-free inference method of [[conformal prediction]].<ref>{{cite journal |first1=Glenn |last1=Shafer |first2=Vladimir |last2=Vovk |title=A Tutorial on Conformal Prediction |journal=Journal of Machine Learning Research |volume=9 |year=2008 |pages=371–421 |url=https://www.jmlr.org/papers/v9/shafer08a.html }}</ref>

==See also==

* [[De Finetti theorem]]

* [[Resampling (statistics)#Permutation tests|Permutation tests]], a statistical test based on exchanging between groups

* [[UHewitt-statisticSavage zero-one law]]

* [[Resampling (statistics)|Resampling]]

* [[{{sectionlink|Resampling (statistics)#Permutation tests|Permutation tests]]}}, a statistical testtests based on exchanging between groups

==Notes References ==

{{Reflist}}

<references/>

== BibliographyFurther reading ==

* 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.&nbsp;1–198, Springer, Berlin, 1985. {{ISBN|978-3-540-15203-3}} {{doi|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

* {{cite book |last=Borovskikh | first=Yu. V. | title=''U''-statistics in Banach spaces | publisher=VSP | ___location=Utrecht | year=1996 | pages=xii+420 | isbn=90-6764-200-2 | mr=1419498 }}

* Chow, Yuan Shih and Teicher, Henry, ''Probability theory. Independence, interchangeability, martingales,'' Springer Texts in Statistics, 3rd ed., Springer, New York, 1997. xxii+488 pp.&nbsp;{{ISBN|0-387-98228-0}}

* {{cite book |last=Dawid |first=A. Philip |chapter=Exchangeability and its ramifications |pages=19–30 |title=Bayesian Theory and Applications |editor-first=Paul |editor-last=Damien |editor2-first=Petros |editor2-last=Dellaportas |editor3-first=Nicholas G. |editor3-last=Polson |editor4-first=David A. |editor4-last=Stephens |display-editors=1 |publisher=Oxford University Press |year=2013 |isbn=978-0-19-969560-7 }}

* {{cite journal | last=Diaconis| first=Persi | authorlink=Persi Diaconis | title=Book review: ''Probabilistic symmetries and invariance principles'' (Olav Kallenberg, Springer, New York, 2005) | journal=Bulletin of the Amererican Mathematical Society (New Series) | volume=46 | year=2009 | issue=4 | doi=10.1090/S0273-0979-09-01262-2 | url=http://www.ams.org/journals/bull/2009-46-04/S0273-0979-09-01262-2/home.html | pages=691–696 | mr=2525743}}

* [[Olav Kallenberg|Kallenberg, O.]], ''Probabilistic symmetries and invariance principles''. Springer-Verlag, New York (2005). 510 pp.&nbsp;{{ISBN|0-387-25115-4}}.

* Kingman, J. F. C., ''Uses of exchangeability'', Ann. Probability 6 (1978) 83&ndash;197 {{MR|494344}} {{JSTOR|2243211}}

* O'Neill, B. (2009) Exchangeability, Correlation and Bayes' Effect. ''International Statistical Review'' '''77(2)''', pp.&nbsp;241–250. {{ISBN|978-3-540-15203-3}} {{doi|10.1111/j.1751-5823.2008.00059.x}}

* {{cite book|title=Limit theorems for sums of exchangeable random&nbsp;variables|first1=Robert Lee|last1=Taylor|first2=Peter Z.|last2=Daffer|first3=Ronald F.|last3=Patterson|mr=|ref=harv|publisher=Rowman and Allanheld|url=https://books.google.com/books?id=6RaoAAAAIAAJ|year=1985|pages=1–152|isbn=9780847674350}}

* Zabell, S. L. (1988) "Symmetry and its discontents", in Skyrms, B. & Harper, W. L. ''Causation, Chance and Credence, ''pp''155-190, Kluwer

* {{ cite journal | author=&mdash; | title=Predicting the unpredictable | year=1992 | journal=Synthese | volume=90 | page=205 | doi=10.1007/bf00485351}}

{{DEFAULTSORT:Exchangeable Random Variables}}