Fact-checked by Grok 2 weeks ago

Pólya urn model

The is a fundamental in , introduced by Felix Eggenberger and in to model contagious phenomena such as the spread of infectious diseases. In its classic two-color formulation, the model begins with an containing a finite number of and balls, say \alpha > 0 and \beta > 0 ; at each step, a is drawn uniformly at random, replaced in the urn along with one additional of the same color, and the process continues indefinitely. This simple reinforcement rule generates a sequence of draws that exhibits positive dependence, where the probability of drawing a particular color increases with each success, leading to a martingale property for the proportion of balls of each color. A hallmark result is that the limiting proportion of red balls, as the number of draws tends to infinity, converges to a following a with parameters \alpha and \beta, which captures the model's inherent randomness and exchangeability. The finite-time distribution of the number of red balls after n draws follows a , linking the model directly to where the serves as a for the likelihood. Generalizations extend the model to multiple colors via a replacement matrix specifying additions of each color upon one, yielding limits from the or deterministic proportions under certain conditions, such as in Friedman's urn variant where convergence occurs to 1/2 . These extensions, developed in works by Athreya and Karlin in the and , preserve the core reinforcement dynamics while accommodating broader scenarios. Beyond its probabilistic foundations, the Pólya urn model has influenced diverse fields, including nonparametric Bayesian inference through connections to the , clinical trial designs for adaptive randomization, and algorithms in such as preferential attachment models for random graphs and networks. In and , it simulates evolutionary reinforcement and dynamics, respectively, highlighting its versatility as a for self-reinforcing random processes. The model's analytical tractability, via embedding in continuous-time processes or martingale methods, continues to drive research into its asymptotic behaviors and infinite-dimensional variants.

History and Motivation

Origins and Early Ideas

The urn model has roots in the early development of , where it served as a concrete analogy for random selection and estimation. In 1713, introduced one of the first explicit uses of s in his seminal work , employing drawings of calculi from an urn to illustrate mechanisms of and to estimate underlying proportions in populations, such as the likelihood of future outcomes based on observed draws. This approach contrasted with deterministic methods and laid foundational ideas for modeling through repeated sampling. By the early 19th century, advanced these concepts significantly in his Théorie analytique des probabilités (1812), where urn models featured prominently in discussions of and inference. Laplace's , applied to problems like predicting the sunrise, imagined an urn filled with an unknown proportion of "success" and "failure" balls, assuming a uniform distribution over possible compositions; each updated the estimate, foreshadowing dynamics by treating draws as accumulating that effectively "bolsters" the likelihood of similar future events. This Bayesian-like updating via urn marked a shift toward models that incorporated historical data in a cumulative manner, influencing later statistical thought. In the late 19th and early 20th centuries, urn models evolved to handle sampling with replacement, distinguishing them from non-reinforcement schemes like the , which modeled fixed-composition draws without alteration. These developments gained traction in for simulating exchangeable sequences and contagion phenomena, where outcomes influenced subsequent probabilities. Notably, in 1917 utilized urn schemes to analyze sequential ball exchanges, deriving distributions for chained processes that captured interdependent events, such as spreading influences in probabilistic chains. Around 1920, emerging reinforcement ideas appeared in , where urns began to represent risk propagation in contexts, like the of claims or branching losses, moving beyond static sampling to dynamic models that amplified observed patterns. Initial explorations, including the collaboration between Eggenberger and , introduced the reinforcement urn model in their 1923 paper "Über die Statistik Verketteter Vorgänge," published in Zeitschrift für Angewandte Mathematik und Mechanik, to model phenomena such as the spread of infectious diseases. These works addressed real-world dependencies in statistical applications.

Pólya's Formalization

George Pólya (1887–1985), a Hungarian mathematician renowned for his contributions to probability, analysis, and combinatorics, further developed the urn model during his professorship at ETH Zurich, where he served from 1914 to 1940. Born in Budapest, Pólya earned his doctorate from the University of Budapest in 1912 before joining the Swiss institution, which became a hub for his influential work in applied mathematics. In his 1930 paper "Sur quelques points de la théorie des probabilités," published in the Annales de l'Institut Henri Poincaré, Pólya provided a detailed mathematical analysis of the urn model originally introduced with Eggenberger in 1923, focusing on "contagious" distributions in probability theory, where outcomes reinforce themselves over successive trials. This work built on the self-reinforcing processes motivated by the need to model phenomena exhibiting contagion, such as the spread of diseases or the evolution of linguistic preferences, and extended to trends in markets through mechanisms of preferential reinforcement. Pólya's key results in the 1930 paper included deriving an integral representation using the to express the of the proportion of balls of a given color, highlighting the model's deep connection to continuous probability. He established the urn scheme as a analog to the , where the limiting proportion of one color converges to a , providing a bridge between sampling and continuous priors. Additionally, Pólya proved the exchangeability of the of draws—meaning the joint probability of any finite depends only on the counts of each color, not their —laying the groundwork for understanding the model's and its role in de Finetti's representation theorem for infinite exchangeable sequences.

Model Definition

Basic Setup

The Pólya urn model is a foundational in , originally proposed to model phenomena exhibiting reinforcement, such as the spread of contagious diseases. In its standard two-color form, the model begins with an containing a finite number of balls of two distinct colors, typically denoted as and . Specifically, the urn is initialized with \alpha balls and \beta balls, where \alpha > 0 and \beta > 0 are positive integers representing the initial counts of each color. Key parameters define the model's structure: the total number of initial balls is s = \alpha + \beta, and a reinforcement parameter \delta governs the addition of balls following each draw, with the standard case setting \delta = 1 to add one ball of the drawn color alongside replacing the drawn ball. This setup ensures the urn's composition evolves dynamically while maintaining a positive total ball count. After n draws, the urn's state is tracked using notation R_n for the number of red balls and B_n for the number of black balls, yielding a total of s + n\delta balls. A generalization of the basic setup allows \delta \neq 1, where \delta can be any positive (or even negative under conditions ensuring non-negative ball counts), enabling broader applications while preserving the core mechanism; however, the standard \delta = 1 case remains the primary focus for classical analysis.

Drawing and Reinforcement Process

The drawing and reinforcement process in the Pólya urn model begins with an urn containing an initial of balls of different colors, typically denoted as red and black for simplicity, with positive integers \alpha red balls and \beta black balls. At each discrete time step n = 1, 2, \dots, a single ball is drawn uniformly at random from the urn, its color is observed, and the ball is returned to the urn along with \delta additional balls of the same color, where \delta > 0 is a fixed parameter. This addition increases the total number of balls by \delta at each step, altering the composition and thereby the probabilities for future draws. The process was originally introduced to model phenomena, such as the spread of diseases, where the reinforcement mimics self-reinforcing growth. The sequence of draws generated by this procedure is denoted as X_1, X_2, \dots, X_n, \dots, where X_i represents the color (e.g., ) of the ball drawn at the i-th step. Let R_n and B_n denote the number of red and black balls, respectively, after n draws; initially, R_0 = \alpha and B_0 = \beta. If X_n = , then R_{n} = R_{n-1} + \delta and B_n = B_{n-1}; otherwise, B_n = B_{n-1} + \delta and R_n = R_{n-1}. The probability of drawing at step n is R_{n-1} / (R_{n-1} + B_{n-1}), and similarly for . This iterative ensures that the urn's composition evolves dynamically, with draws becoming increasingly likely to favor colors that have appeared more frequently earlier in the sequence. To illustrate, consider an urn starting with 1 red ball and 1 black ball (\alpha = \beta = 1), with \delta = 1. The total number of balls is initially 2. At the first draw, the probability of red or black is $1/2 each. Suppose a red ball is drawn: it is replaced along with 1 additional red ball, resulting in 2 red balls and 1 black ball (total 3 balls). At the second draw, the probability of red is now $2/3 and black $1/3. If black is then drawn, the urn becomes 2 red and 2 black (total 4 balls). Subsequent draws continue this reinforcement, potentially leading to paths where one color dominates early and persists. The drawing and reinforcement process constitutes a , where the state at each step is defined by the current counts of each color (e.g., (R_n, B_n)), and the transition probabilities depend solely on this state. However, the states exhibit dependence across the sequence due to the cumulative , as prior draws influence the evolving composition and thus future transition probabilities.

Fundamental Properties

Exact Probability Distributions

In the standard Pólya urn model, where the urn initially contains \alpha > 0 balls and \beta > 0 balls with total s = \alpha + \beta, and each draw of a color adds \delta > 0 additional balls of that color, the probability of any specific of n draws with exactly k draws is of the order of the colors. This probability is given by P(X_1, \dots, X_n) = \frac{\prod_{i=0}^{k-1} (\alpha + i\delta) \cdot \prod_{j=0}^{n-k-1} (\beta + j\delta)}{\prod_{m=0}^{n-1} (s + m\delta)}, where X_i denotes the color drawn at step i ( or ), for any with k reds. This formula arises from the sequential multiplication of conditional probabilities at each draw, which telescopes in a manner that depends only on the counts of each color, not their positions. The of the number of red draws K_n in n steps, or equivalently the number of red balls R_{n+1} = \alpha + K_n \delta after n draws, follows a . Specifically, P(K_n = k) = \binom{n}{k} \frac{ \prod_{i=0}^{k-1} (\alpha + i\delta) \cdot \prod_{j=0}^{n-k-1} (\beta + j\delta) }{ \prod_{m=0}^{n-1} (s + m\delta) }, for k = 0, 1, \dots, n. This distribution generalizes the and reflects the reinforcement mechanism's effect on variance, which is higher than in the independent case. A notable special case occurs when \delta = 1, \alpha = \beta = 1, corresponding to starting with one ball of each color and adding one matching ball per draw. Here, the number of red draws K_n is uniformly distributed: P(K_n = k) = \frac{1}{n+1}, \quad k = 0, 1, \dots, n. This uniformity stems from the beta-binomial form with parameters \alpha = \beta = 1, where the beta prior is uniform on [0,1], leading to equal probabilities across all possible counts.

Uniformity and Symmetry Results

The Pólya urn model demonstrates a fundamental through the exchangeability of its draw s, meaning that the joint probability of any finite of colors depends solely on the counts of each color rather than their specific . This order-independence stems from the mechanism, where the probability of drawing a sequence with a fixed number of red and black balls is identical regardless of , as the sequential probabilities to the same value: for k red draws in n total draws starting from one of each color, the marginal probability of exactly k reds is \frac{1}{n+1}. This property renders the of indicators for red draws infinitely exchangeable, a hallmark of the model's symmetric structure first noted in the foundational work on linked processes. In the two-color setup with one and one black ball initially (parameters a=1, b=1) and by adding one ball of the drawn color (c=1), the manifests strikingly in the of the empirical proportion of draws after n draws. Specifically, the number of draws, denoted K_n, follows a : P(K_n = k) = \frac{1}{n+1} for k = 0, 1, \dots, n. Consequently, the empirical proportion \frac{K_n}{n} is ly distributed over the set \left{ \frac{0}{n}, \frac{1}{n}, \dots, \frac{n}{n} \right}. This outcome arises directly from the exchangeability, as each possible of k and n-k black draws is equally likely. This uniformity has profound interpretive implications for prediction within the model. The that the next draw is red, given the first n draws with k reds, equals the current empirical proportion \frac{k}{n}, reflecting the martingale nature of the proportion process. In the standard (1,1,1) initialization, this predictive rule specializes to \frac{k+1}{n+2}, which aligns precisely with Laplace's for estimating success probabilities under a uniform prior. Pólya highlighted this symmetric predictive consistency in his 1923 analysis, underscoring the model's utility in capturing without order bias.

Asymptotic Behavior

Limiting Proportions

In the Pólya urn model, the proportion of red balls after n draws is defined as \Theta_n = R_n / (s + n \delta), where R_n denotes the number of red balls, s = \alpha + \beta is the initial total number of balls, \alpha and \beta are the initial numbers of red and black balls, respectively, and \delta > 0 is the number of additional balls of the drawn color added at each step. The sequence (\Theta_n)_{n \geq 0} forms a bounded martingale with respect to the natural filtration generated by the draws, since the expected proportion after the next draw equals the current proportion: \mathbb{E}[\Theta_{n+1} \mid \mathcal{F}_n] = \Theta_n, where \mathcal{F}_n is the sigma-algebra up to step n. By Doob's martingale convergence theorem, \Theta_n converges to a random limit \Theta as n \to \infty. The limiting proportion \Theta follows a Beta distribution with parameters \alpha / \delta and \beta / \delta, i.e., \Theta \sim \mathrm{Beta}(\alpha / \delta, \beta / \delta). This random limit arises from the reinforcement dynamics of the model, often described as the "rich get richer" phenomenon, where early draws influence long-term composition probabilistically. A sketch of the proof relies on the martingale property and boundedness ensuring almost sure , with the Beta distribution emerging from the explicit form of the transition probabilities and invariance of the marginal distribution of \Theta_n. The randomness of \Theta implies persistent uncertainty in the asymptotic proportion, but the scale of fluctuations around this limit decreases with variance on the order of $1/n, reflecting the stabilizing effect of repeated reinforcements.

Convergence to Beta Distribution

In the Pólya urn model with initial α red balls, β black balls, and reinforcement parameter δ > 0, the proportion of red balls Θ_n after n draws converges in distribution to a Beta(α/δ, β/δ) random variable as n → ∞. This limiting distribution arises from the martingale property of the proportions and the reinforcement mechanism, which preserves exchangeability in the sequence of draws. The of the limiting Θ is given by f(\theta) = \frac{\Gamma\left(\frac{\alpha + \beta}{\delta}\right)}{\Gamma\left(\frac{\alpha}{\delta}\right) \Gamma\left(\frac{\beta}{\delta}\right)} \theta^{\frac{\alpha}{\delta} - 1} (1 - \theta)^{\frac{\beta}{\delta} - 1}, \quad 0 < \theta < 1. This form reflects the generalization of the uniform distribution on [0,1] to the more flexible Beta family, parameterized by the scaled initial counts. The expected value of the limiting proportion is E[Θ] = α / (α + β), which matches the initial proportion and remains constant across all n due to the martingale structure. The variance is Var[Θ] = \frac{\alpha \beta \delta}{(\alpha + \beta)^2 (\alpha + \beta + \delta)}, providing a measure of uncertainty that stabilizes in the limit and depends on the reinforcement strength δ. These moments are independent of n in the asymptotic regime and quantify the persistence induced by the model. In the standard case where α = β = δ = 1, the limiting distribution is uniform on [0,1], consistent with the model's symmetry and uniformity properties for equal initial conditions. This special case underscores the urn's role in generating equitable long-term outcomes under balanced starts. The convergence to the Beta distribution provides a foundational justification for employing the as a conjugate prior in Bayesian inference for binomial proportions, as the urn's reinforcement mirrors sequential posterior updating with Beta priors and Bernoulli likelihoods.

Interpretations and Applications

Statistical and Bayesian Interpretations

The Pólya urn model provides a concrete urn-based simulation of Bayesian inference for a binary outcome process, where the proportion of balls of each color represents the state of belief about an unknown success probability p. Specifically, starting with \alpha red balls and \beta black balls corresponds to drawing p from a Beta(\alpha, \beta) prior distribution, with each draw updating the urn by adding one more ball of the drawn color, equivalent to observing a success or failure in a Bernoulli trial and reinforcing the posterior Beta distribution accordingly. After n draws resulting in r red balls, the posterior is Beta(\alpha + r, \beta + n - r), mirroring the conjugate update in Bayesian statistics for binomial likelihoods. This setup yields a predictive distribution for the next draw that aligns directly with Bayesian learning: the probability of drawing a red ball on the subsequent step equals the posterior mean \frac{\alpha + r}{\alpha + \beta + n}, which embodies the reinforcement mechanism as iterative belief updating based on observed data. The overall sequence of draws generated by the urn is exchangeable, meaning the joint probability depends only on the counts of each color, not their order, which facilitates the model's use as a generative process for such sequences in . Furthermore, the marginal distribution of the number of red balls in n draws follows a beta-binomial distribution, making the Pólya urn a natural mechanism for modeling overdispersed binomial data where the success probability varies according to a beta prior, rather than being fixed. Historically, the model, introduced by Eggenberger and Pólya in 1923 to describe contagious processes, predated the mid-20th-century revival of Bayesian methods but resonates with de Finetti's 1930s foundational work on subjective probability and exchangeability, providing an intuitive precursor to modern Bayesian conjugate priors.

Real-World and Modern Applications

The Pólya urn model has been applied to model genetic drift in population genetics, approximating processes like the Moran model where allele frequencies evolve through random reinforcement akin to drawing and adding balls of the same color. In this context, the model captures the stochastic fixation or loss of alleles in finite populations under neutrality, with the urn's composition representing the gene pool and draws simulating reproductive success. In linguistics, the model describes word frequency evolution through reinforcement, where repeated use of a word increases its future likelihood, mirroring cultural transmission and lexical drift. For instance, simulations using Pólya urn dynamics have shown how stochastic reinforcement and imitation lead to predictable patterns in language variation, such as shifts in vocabulary usage over generations. Similarly, in market share dynamics, the model illustrates "rich-get-richer" effects, where dominant products gain disproportionate adoption, as seen in empirical analyses of innovation diffusion data from consumer markets. Modern applications extend to machine learning, particularly in multi-armed bandits for reinforcement learning, where Pólya urn processes model self-reinforcing user preferences in sequential decision-making under uncertainty. Variants like Thompson sampling leverage the urn's beta distribution limits to balance exploration and exploitation, achieving logarithmic regret in stochastic settings. In ecology, the Hoppe urn—a Pólya-like scheme—facilitates species sampling models, estimating biodiversity patterns under neutral theory; extensions in the 2000s and beyond have validated these against empirical abundance data from tropical forests, confirming power-law species distributions. Network growth models link preferential attachment to Pólya urn reinforcement, generating scale-free topologies similar to the Barabási–Albert process, with recent generalizations using expanding colors to simulate evolving connectivity in social and biological networks. In 2020s AI applications, generalized urn models support sequential decisions in areas like viral genomics, where martingale methods analyze long-term convergence, and recommender systems, where they model collaborative filtering and enhance novelty discovery. As of 2025, further applications include modeling football pass networks in sports analytics and structurally balanced growing networks. Computational simulations in data science, often via agent-based extensions, empirically validate these dynamics against real-world datasets, such as novelty emergence in innovation networks, demonstrating improved fit over baseline models through parameter tuning on observed interaction frequencies.

Generalizations and Variants

Multivariate Pólya Urns

The general multivariate Pólya urn model, also known as the Pólya-Eggenberger urn, extends the classical setup to c \geq 2 colors using a replacement matrix A = (a_{ij})_{1 \leq i,j \leq c}, where a_{ij} \in \mathbb{R} specifies the number of balls of color i added when a ball of color j is drawn. The urn starts with initial counts \alpha = (\alpha_1, \dots, \alpha_c) where \alpha_i \geq 0 and \sum \alpha_i > 0. Upon drawing a ball of color j, it is replaced along with a_{ij} balls of each color i. The behavior depends on the matrix A: if A is diagonal with positive entries (independent ), the proportions converge to a ; in balanced cases (e.g., constant row sums), convergence is to deterministic limits. This framework, analyzed by Athreya and Karlin in the 1960s and 1970s, encompasses many variants. In the special case of independent reinforcement, the matrix is diagonal with a_{ii} = \delta > 0 for all i and a_{ij} = 0 otherwise, and the urn contains initial \alpha_i > 0 balls of color i for i = 1, \dots, c, with total initial balls s = \sum_{i=1}^c \alpha_i. At each step, a ball is drawn uniformly at random from the urn, replaced, and supplemented by \delta > 0 additional balls of the same color. This reinforcement mechanism promotes the persistence of drawn colors, generalizing the contagion-like behavior observed in the bivariate case. Consider a sequence of n draws resulting in k_i balls of color i, where \sum_{i=1}^c k_i = n. The probability of any specific such sequence is order-independent and given by P(\text{sequence}) = \frac{\prod_{i=1}^c \prod_{j=0}^{k_i - 1} (\alpha_i + j \delta)}{\prod_{m=0}^{n-1} (s + m \delta)}, reflecting the exchangeability of . The joint of the counts (K_1, \dots, K_c) follows the Dirichlet-multinomial distribution, which arises as a compound of the multinomial likelihood with a on the color proportions. This underpins Bayesian nonparametric models for categorical , where the \alpha_i prior beliefs about color frequencies. As n \to \infty, the proportions of balls of each color, defined as P_{n,i} = \frac{\alpha_i + \delta K_i}{s + n \delta} for i = 1, \dots, c, converge to a random (P_1, \dots, P_c) distributed according to the with parameters (\alpha_1 / \delta, \dots, \alpha_c / \delta). This limiting behavior captures the martingale property of the proportions and aligns the urn dynamics with the de Finetti representation of exchangeable sequences in multiple dimensions. The multivariate Pólya urn also connects to partition structures in probability, particularly through its equivalence to the Chinese restaurant process (CRP) for generating exchangeable random . In this linkage, the urn's total initial mass parameter \theta = s / \delta serves as the concentration parameter of the CRP, governing the trade-off between reinforcing existing tables (colors) and starting new ones, with applications in clustering and species sampling models.

Related Urn Schemes

The Friedman urn model, introduced by Bernard Friedman in 1949, modifies the standard by adding balls of the opposite color upon drawing, incorporating negative reinforcement that promotes between colors. In this scheme, starting with white and black balls, drawing a white ball leads to adding white and black balls in specified proportions, resulting in asymptotic proportions that converge to a balanced state rather than the martingale behavior of the Pólya model. This leads to limiting distributions where the proportion of each color approaches 1/2 under symmetric rules, contrasting with the Pólya urn's adherence to initial ratios. The Hoppe urn, proposed by F. M. Hoppe in 1984, extends the Pólya dynamics to model species sampling in and serves as a constructive representation for the in Bayesian nonparametrics. It begins with a single special "immigrant" ball of mass α representing potential new types, alongside no other balls initially; upon drawing the special ball, a new color is introduced with one ball added, while drawing an existing color reinforces it by adding another ball of that type. This process generates exchangeable sequences where the probability of novel types follows the Ewens sampling formula, enabling the urn to accommodate an unbounded number of categories dynamically. The Ehrenfest urn model, developed by Paul and Tatiana Ehrenfest in 1907, models by maintaining a fixed total number of balls distributed between two urns, simulating gas molecule exchanges without net addition or removal. At each step, a ball is selected uniformly from all balls across both urns and moved to the other urn, resulting in a that exhibits ergodic behavior and converges to a . This fixed-volume constraint distinguishes it from expansive urns like Pólya's, providing a discrete analogy for thermodynamic where increases toward . Wallenius' noncentral hypergeometric distribution arises from an urn scheme with biased sampling without replacement, where balls of different colors have unequal drawing probabilities due to varying weights or biases. In this model, n balls are drawn sequentially from an urn containing two types, with the probability of drawing a ball of a given type proportional to its weight times the remaining count, leading to a distribution that accounts for competition and depletion effects. Unlike the central hypergeometric's equal bias, Wallenius' version, formalized in 1963, produces skewed outcomes that model real-world scenarios like biased contests or ecological sampling. Modern variants of Pólya-like urns include reinforced random walks, where edge weights on a are updated proportionally to traversal frequencies, akin to urn , leading to localization or delocalization depending on the . These models, surveyed by Robin Pemantle in , embed urn dynamics into path selections and exhibit asymptotic behaviors like convergence to Gibbs measures on . In contexts, urn schemes inspire algorithms with history-dependent rewards, such as Polya decision processes that update beliefs via urn compositions to balance exploration and exploitation. Pólya trees, developed in the early 1990s for Bayesian nonparametrics, generalize urn reinforcement to hierarchical partitions of the , constructing prior distributions over densities via nested beta reinforcements at each level. Introduced by Mauldin et al. in 1992 and extended by Lavine, these trees allow flexible, data-dependent partitioning without assuming a fixed number of categories, converging to arbitrary continuous distributions under suitable centering. Variants like optional Pólya trees, proposed by and in 2002, incorporate random partitions to mitigate dependence on fixed grids, enhancing adaptability in .

Connections to Probability Theory

Exchangeability in Sequences

In probability theory, a sequence of random variables X_1, X_2, \dots, X_n taking values in a (such as colors) is said to be exchangeable if its is invariant under any of the indices, meaning P(X_1 = x_1, \dots, X_n = x_n) = P(X_1 = x_{\pi(1)}, \dots, X_n = x_{\pi(n)}) for any permutation \pi. This property implies that the order of observations does not affect their joint likelihood, capturing a form of in dependent random variables. The Pólya urn model generates exchangeable sequences of draws through its reinforcement mechanism, where the probability of drawing a particular color at each step depends solely on the current composition of the , which evolves based on cumulative counts rather than the specific order of previous draws. For a two-color starting with a > 0 balls of color A and b > 0 balls of color B, and adding \alpha > 0 balls of the drawn color after each draw, the sequence of indicators X_i (e.g., 1 for A, 0 for B) is exchangeable because the joint for any finite n depends only on the total number of A's drawn, k = \sum_{i=1}^n X_i, and not on their positions. Specifically, this joint probability is given by P(X_1 = x_1, \dots, X_n = x_n) = \frac{a^{(k)} b^{(n-k)}}{(a+b)^{(n)}} where u^{(m)} = u(u+\alpha)\cdots(u+(m-1)\alpha) denotes the rising factorial (Pochhammer symbol) with step size \alpha, ensuring symmetry under permutation since only k appears in the expression. To establish exchangeability, one can use induction on n. For the base case n=1, the probability is trivially symmetric: P(X_1 = 1) = a/(a+b). Assuming the statement holds for n-1, the conditional probability at step n reinforces the previous counts, yielding a joint probability for n draws that again depends only on the total count k, preserving invariance under permutations of the full sequence via the inductive hypothesis and the urn's update rule. This construction extends to the infinite sequence \{X_i\}_{i=1}^\infty, which is infinitely exchangeable, with the directing measure (de Finetti measure) following a beta distribution \text{Beta}(a/\alpha, b/\alpha) for the two-color case. In the multivariate setting with d \geq 2 colors and initial counts a_j > 0 for color j = 1, \dots, d, adding \alpha > 0 balls of the drawn color each time, the resulting sequence is similarly exchangeable, as the joint probabilities depend only on the vector of counts for each color. For infinite exchangeability, the de Finetti measure is then the with parameters (a_1/\alpha, \dots, a_d/\alpha), generalizing the beta case and reflecting the model's symmetry across multiple categories.

de Finetti's Theorem and Representations

establishes a fundamental connection between exchangeable sequences and models in . Specifically, for an infinite of random variables X_1, X_2, \dots that is exchangeable, the states that there exists a F on [0, 1] such that the joint is given by p(x_1, \dots, x_n) = \int_0^1 \theta^{t_n} (1 - \theta)^{n - t_n} \, dF(\theta), where t_n = \sum_{i=1}^n x_i, representing the as a of independent and identically distributed (i.i.d.) trials with success probability \theta, where \theta is drawn from F. This mixing measure F corresponds to the distribution of the limiting frequency Y = \lim_{n \to \infty} \frac{1}{n} \sum_{i=1}^n X_i. In the context of the Pólya urn model, the sequence of draws generates an exchangeable binary sequence whose de Finetti measure is a beta distribution. Starting with \alpha balls of one color (say, success) and \beta balls of the other (failure), and adding \delta balls of the drawn color each time, the urn process simulates the mixture where \Theta \sim \text{Beta}(\alpha/\delta, \beta/\delta) and, conditionally, X_i \mid \Theta = \theta \sim \text{Bernoulli}(\theta) independently. The proportion of success balls converges almost surely to \Theta, yielding the joint distribution P(Y_n = y) = \binom{n}{y} \frac{B(\alpha/\delta + y, \beta/\delta + n - y)}{B(\alpha/\delta, \beta/\delta)}, where B is the beta function, equivalent to the beta-binomial under this mixture. Thus, the Pólya urn provides an explicit constructive realization of de Finetti's representation for exchangeable binary sequences. This connection extends to the multivariate case, where a Pólya urn with multiple colors produces an exchangeable sequence over a finite set of categories, with the de Finetti measure being a Dirichlet distribution. For an urn starting with \alpha_i > 0 balls of color i for i = 1, \dots, k, and adding one ball of the drawn color each time, the vector of color proportions converges almost surely to a \text{Dirichlet}(\alpha_1, \dots, \alpha_k) random variable, serving as the mixing measure for conditionally i.i.d. multinomial draws. Notably, the Pólya urn model, introduced by Eggenberger and Pólya in 1923, predates de Finetti's 1931 theorem by several years and offers a constructive proof of its representation for such exchangeable sequences. The urn framework further generalizes to nonparametric Bayesian settings via the Dirichlet process, where an urn with a continuum of colors (or a special "new color" ball) generates exchangeable sequences over an infinite-dimensional space. In this scheme, starting with \alpha special balls representing draws from a base measure H, and reinforcing observed colors while introducing new ones proportional to \alpha, the process yields a de Finetti measure that is a Dirichlet process \text{DP}(\alpha H), foundational for nonparametric Bayes models like infinite mixture models.