Fact-checked by Grok 2 weeks ago

Urn problem

In probability theory, the urn problem, also known as the urn model, is a foundational abstraction for representing random sampling and selection processes, where an urn serves as a metaphor for a finite population containing distinguishable objects—typically visualized as balls of different colors or types—from which items are drawn at random, either with replacement (returning the drawn item) or without, to compute probabilities of specific outcomes.^[1] This model simplifies complex probabilistic scenarios by focusing on the composition of the urn and the drawing rules, enabling calculations for events like the sequence of draws or the proportion of types selected.^[2] The urn model has historical roots in early probability work, with basic forms appearing in discussions of combinatorial sampling, but it gained prominence through George Pólya's 1923 introduction of the reinforced variant known as Pólya's urn, which begins with an initial set of balls (e.g., one red and one black) and adds additional balls of the drawn color upon each draw, modeling self-reinforcing processes that lead to exchangeable sequences and limiting proportions following a beta distribution.^[1] Generalized urn models extend this by incorporating multiple colors, variable reinforcement matrices, and removal rules, as in Friedman's urn (where both drawn and undrawn types are reinforced), allowing analysis of Markov chains, martingales, and convergence to stable attractors.^[3] A classical variant, the occupancy urn problem, shifts focus from sampling to distribution: balls are sequentially placed into multiple urns at random, with interest in metrics like the probability of empty urns after m placements into n urns, which underpins occupancy theory and approximations like the coupon collector problem.^[4] Urn models are versatile tools in modern probability and statistics, illustrating core concepts such as conditional probability, Bayes' theorem, the hypergeometric distribution (for without-replacement sampling), and the beta-binomial (for reinforced draws), while finding applications in diverse fields including genetics (modeling allele frequencies), economics (market share dynamics), clinical trials (adaptive designs), and computer science (preferential attachment in networks).^[1] Their analytical tractability—often via generating functions, stochastic approximation, or diffusion limits—makes them enduring for both theoretical advancements and pedagogical purposes, with ongoing research exploring multi-urn interactions and non-constant reinforcements.^[5]

Historical Development

Origins in Classical Probability

Urn problems originated as metaphors for random selection processes in lotteries and elections during the late medieval and early modern periods, providing a tangible analogy for probabilistic events. A prominent historical example is the election of the Doge of Venice, where, starting in 1268, urns filled with balls representing eligible oligarchs were used in multi-stage lot-drawing protocols to select electoral colleges randomly. This method, designed to prevent factional dominance and ensure fairness, involved drawing balls from urns to narrow down candidates from an initial pool of around 480 to a final shortlist, thereby introducing elements of chance into political decision-making.^[6] These urn-based analogies drew early influences from games of chance prevalent in European gambling culture, such as dice and card games, which posed questions about fair division of stakes in interrupted play—known as the problem of points. Addressed by mathematicians like Blaise Pascal and Pierre de Fermat in their 1654 correspondence, such problems highlighted the need for systematic probability calculations in uncertain outcomes, paving the way for urn models to represent equiprobable selections akin to lottery draws.^[7] Jacob Bernoulli formalized the urn problem in his seminal work Ars Conjectandi, published posthumously in 1713, where he employed urns containing pebbles of different colors to explore inverse probability—the inference of an urn's underlying proportions from observed draws. Bernoulli's approach emphasized estimating population characteristics from samples, transforming urns into a cornerstone for inductive reasoning in probability. In this context, he applied the law of large numbers to urn draws, demonstrating that repeated extractions from an urn with unknown black and white pebble ratios would, with sufficient trials, approximate the true proportions reliably.^[8]^[9] This foundational use of urns in Bernoulli's framework influenced subsequent developments, such as Abraham de Moivre's extensions in the early 18th century.^[8]

Key Contributors and Milestones

Abraham de Moivre advanced probability theory through his seminal work The Doctrine of Chances (1718), where he extended Bernoulli's ideas to approximate probabilities for large populations using combinatorial methods and early asymptotic analysis, facilitating developments in the normal approximation to the binomial distribution.^[10] This contribution marked a shift toward applying these analogies to complex combinatorial problems beyond simple games of chance. Thomas Bayes further developed inverse inference in his posthumously published essay "An Essay towards Solving a Problem in the Doctrine of Chances" (1763), using a billiard table analogy with balls to represent belief updating through conditional probabilities, which laid the foundation for Bayesian methods in inferring causes from observed effects. In the 19th century, Pierre-Simon Laplace refined these ideas in Bayesian estimation, using urn analogies to model the inversion of probabilities and estimate unknown proportions from samples, as detailed in his Théorie analytique des probabilités (1812).^[11] Laplace's work emphasized the urn model's utility in practical inference, influencing applications in astronomy and demographics by formalizing prior beliefs in probabilistic reasoning. In 1923, Felix Eggenberger and George Pólya introduced the reinforcement-based Pólya urn model in their paper on probability logic in telegraphy failures, which generalized traditional urn schemes by adding balls of the drawn color, modeling contagion and exchangeable sequences in probability. Pólya further elaborated on these concepts in his 1930 paper "Sur quelques points de la théorie des probabilités." Key milestones in urn problem theory thus progressed chronologically: de Moivre's 1718 approximations established descriptive tools for large-scale events; Bayes's 1763 essay pioneered inferential applications; Laplace's 1812 refinements integrated priors for estimation; and the 1923 Pólya-Eggenberger model shifted focus to dynamic reinforcement processes. This timeline reflects the evolution from static descriptive uses in classical probability to dynamic inferential frameworks in modern statistics.

Core Concepts

The Basic Urn Model

The basic urn model in probability theory consists of an urn containing a finite number of balls of distinct types, typically represented by colors or categories, where balls of the same type are indistinguishable and symbolize units from a population.^[12] This setup provides a simple, abstract framework for modeling random selection processes.^[12] In the standard configuration, the urn holds x balls of type A and y balls of type B, yielding a total of N = x + y balls.^[13] The model assumes that balls are drawn uniformly at random, meaning each ball has an equal probability of selection, and that the types are mutually exclusive and exhaustive, encompassing all relevant categories without overlap.^[12] The urn acts as a neutral container to simulate sampling from a finite population, isolating the probabilistic structure from real-world complexities or biases that might affect direct observation.^[12] Jacob Bernoulli utilized this model in Ars Conjectandi (1713) for inference, employing white and black tokens to represent outcomes in estimating unknown ratios.^[13] Variations in urn size and composition, such as adjusting the values of x and y or introducing additional types, allow the model to illustrate diverse sampling scenarios while preserving its foundational simplicity.^[12]

Sampling Procedures

In urn problems, sampling procedures define the mechanisms by which balls are drawn from the urn, directly influencing the dependence structure of the outcomes. The basic urn model consists of an urn containing balls of distinct types, such as colors, from which draws are made according to specified rules.^[14] These procedures typically involve selecting a ball at random, observing its type, and deciding whether to return it to the urn, with the goal of modeling random selection processes.^[15] Sampling with replacement entails drawing a ball, noting its type, and immediately returning it to the urn, thereby maintaining the original composition for all subsequent draws. This approach ensures that each draw is independent of the previous ones, as the probability of selecting any particular type remains constant across trials.^[14] It is commonly employed to simulate scenarios requiring repeated, unaffected selections, such as independent trials in experimental designs.^[15] In contrast, sampling without replacement involves removing the drawn ball from the urn after observation, which alters the urn's composition and makes successive draws dependent, as the probabilities shift based on prior outcomes.^[16] This method is particularly relevant for modeling finite populations where depletion occurs, like selecting items from a limited set without reuse.^[17] For multiple draws, the sequence can be treated as ordered, where the order of selection matters (e.g., distinguishing the first draw from the second), or unordered, focusing solely on the multiset of types obtained regardless of sequence.^[15] Decision rules govern the observation process: typically, only the type (e.g., color) is recorded, and in without-replacement sampling, this observation informs the updated probabilities for future draws by reducing the count of that type.^[14] Single draws represent the simplest case, equivalent to one-step selection, while multiple draws extend to chains of selections, amplifying dependence in without-replacement scenarios.^[16] Practical considerations emphasize achieving true randomness in draws; the urn is often shaken or mixed thoroughly before each selection to ensure uniform probability across all balls.^[15] In without-replacement sampling, this dependence implies that early draws can significantly impact later ones, necessitating careful accounting of the evolving urn state to avoid bias in applications like population surveys.^[17] With replacement, the preserved independence simplifies analysis but may not reflect real-world depletion effects.^[14]

Mathematical Framework

Probability Distributions in Urn Models

In urn models, the binomial distribution emerges from sampling with replacement, where each draw is independent and the composition of the urn remains unchanged. Consider an urn containing N balls, of which x are of type A and y = N - x are of type B. The probability of drawing a type A ball on any single draw is p = x/N. For n independent draws, the number K of type A balls follows a binomial distribution:

P(K = k) = \binom{n}{k} p^k (1-p)^{n-k}, \quad k = 0, 1, \dots, n.

This formula arises from combinatorial counting: there are \binom{n}{k} ways to select the positions of the k type A draws among n trials, each sequence having probability p^k (1-p)^{n-k}.^[18] When sampling without replacement from the same urn setup, the draws are dependent, leading to the hypergeometric distribution for the number K of type A balls in n draws. The probability mass function is

P(K = k) = \frac{\binom{x}{k} \binom{y}{n-k}}{\binom{N}{n}}, \quad \max(0, n - y) \leq k \leq \min(n, x).

The derivation relies on combinatorial enumeration: the numerator counts the ways to choose k type A balls from x and n-k type B from y, while the denominator is the total ways to choose any n balls from N. This distribution was first derived in the context of urn problems by Abraham de Moivre in 1711, solving a problem posed by Christiaan Huygens.^[18]^[19] For urns with more than two types, the multinomial distribution generalizes the binomial case under sampling with replacement. Suppose the urn has m types of balls with counts x_i for i = 1, \dots, m, so N = \sum_{i=1}^m x_i and probabilities p_i = x_i / N. In n draws, let K_i be the count for type i, with \sum_{i=1}^m K_i = n. Then,

P(K_1 = k_1, \dots, K_m = k_m) = \frac{n!}{k_1! \cdots k_m!} p_1^{k_1} \cdots p_m^{k_m}.

The derivation follows from multinomial coefficients counting the ways to partition the n draws into groups of sizes k_1, \dots, k_m, multiplied by the product of independent probabilities for each type. This extends the two-type case naturally to multiple categories.^[18] Variants for waiting times in repeated draws with replacement also yield familiar distributions. The geometric distribution describes the number of draws X until the first type A ball, with P(X = k) = (1-p)^{k-1} p for k = 1, 2, \dots, derived by noting that the first k-1 draws must be type B (each with probability $1-p) followed by a type A (probability p). The negative binomial distribution extends this to the number of draws X until the r-th type A ball, with

P(X = k) = \binom{k-1}{r-1} p^r (1-p)^{k-r}, \quad k = r, r+1, \dots,

where the binomial coefficient counts the ways to place the r-1 successes among the first k-1 draws, followed by the r-th success. These arise as limits or special cases of repeated Bernoulli trials modeled via the urn.^[18]

Generalizations and Extensions

One prominent generalization of the basic urn model is Pólya's urn, introduced by Eggenberger and Pólya to model contagious processes such as disease spread. In this scheme, the urn begins with x balls of type A and y balls of type B. A ball is drawn at random, replaced, and supplemented by a additional balls of the same type (with symmetric treatment for both types when a > 0). This reinforcement creates positive dependence among draws, unlike the independence in sampling with replacement. The number of type A balls drawn in n successive draws follows a beta-binomial distribution, which arises as a binomial distribution compounded with a beta prior on the success probability, reflecting the model's Bayesian interpretation.^[20]^[21] Another extension involves mixed replacement schemes, where the replacement rule differs by type to capture asymmetric dynamics. For an urn with x balls of type A (replaced upon drawing) and y balls of type B (removed without replacement), the process simulates scenarios like selective retention. The probability of observing exactly k type A draws in m trials is

P(m,k) = \binom{m}{k} \frac{x^{(k)} y^{(m-k)}}{N^{(m)}}

where N = [x + y](/page/X+Y) and z^{(r)} = z(z-1)\cdots(z-r+1) denotes the falling factorial (with z^{(0)} = 1). This formula accounts for the decreasing total balls due to non-replaced type B draws, yielding a distribution distinct from standard hypergeometric. (Feller, 1950, p. 50) For urns with more than two types, the multivariate hypergeometric distribution generalizes sampling without replacement to c \geq 2 categories. Suppose the urn contains N balls distributed as N_1, N_2, \dots, N_c of each type, with \sum_{i=1}^c N_i = N. Drawing a sample of size n without replacement, the joint probability of drawing k_1, k_2, \dots, k_c balls of each type (where \sum k_i = n) is

P(K_1 = k_1, \dots, K_c = k_c) = \frac{\prod_{i=1}^c \binom{N_i}{k_i}}{\binom{N}{n}}.

This model applies to multi-category populations, such as ecological sampling or quality control, preserving the without-replacement structure while extending to higher dimensions. Marginal distributions for individual types reduce to the univariate hypergeometric./12%3A_Finite_Sampling_Models/12.03%3A_The_Multivariate_Hypergeometric_Distribution) Considering limits as the urn size grows infinite provides connections to broader probabilistic structures, particularly exchangeability. In Pólya's urn, the sequence of draw colors forms an exchangeable process, meaning any permutation of outcomes has identical distribution. De Finetti's theorem asserts that any infinite exchangeable sequence of binary random variables is a mixture of i.i.d. Bernoulli sequences, with the mixing measure given by a beta distribution in the Pólya case; this links the finite urn dynamics to infinite exchangeable limits.^[22] Key derivations for Pólya's urn involve recursive probability updates and martingale properties. The probability of drawing type A at step t+1 given previous outcomes simplifies due to the model's exchangeability, yielding P(A_{t+1} = A \mid \mathcal{F}_t) = \frac{x + a S_t}{N + a t}, where S_t is the number of prior type A draws and \mathcal{F}_t the history up to t. The proportion of type A balls, Y_t = \frac{x + a S_t}{N + a t}, forms a bounded martingale, converging almost surely to a beta(x/a, y/a) random variable by the martingale convergence theorem, ensuring long-run stability despite reinforcement. These properties underpin asymptotic analyses and extensions to multi-type urns.^[23]

Notable Examples

Simple Sampling Problems

Simple sampling problems in urn models provide foundational illustrations of probability principles, using basic setups with balls of distinct types drawn from a finite collection. These scenarios assume uniform randomness in draws and focus on direct calculations without complicating factors like reinforcement. In the simplest case, consider an urn containing N balls, of which x are of type A (e.g., red) and N - x are of type B (e.g., blue). The probability of drawing a single type A ball is the direct proportion P(\text{A}) = \frac{x}{N}.^[15] For multiple draws with replacement, where each drawn ball is returned to the urn before the next draw, the outcomes are independent. The expected number of type A balls in n draws is thus n \cdot \frac{x}{N}.^[15] Sampling without replacement introduces dependence between draws, as the urn's composition changes after each selection. The probability of drawing n type A balls in succession is the product of decreasing ratios:

P(\text{all A}) = \frac{x}{N} \cdot \frac{x-1}{N-1} \cdot \ldots \cdot \frac{x-n+1}{N-n+1}.

This follows the hypergeometric distribution for the number of type A balls in a fixed sample size.^[15] A notable variant is Bertrand's box paradox, which extends the urn concept to multiple urns (or boxes) with fixed compositions to explore conditional probability. Three boxes contain: one with two gold coins (GG), one with two silver coins (SS), and one with one gold and one silver (GS). A box is selected at random, and a gold coin is drawn from it. The probability that the other coin in the selected box is also gold is \frac{2}{3}, as there are two ways to draw a gold from the GG box but only one from the GS box, out of three equally likely gold draws overall. To compute these probabilities manually, consider a small urn with 3 red and 2 blue balls (N=5, x=3). A probability tree for two draws without replacement branches from the first draw: probability of red first is \frac{3}{5}, then red second is \frac{2}{4} = \frac{1}{2} (joint \frac{3}{5} \cdot \frac{1}{2} = \frac{3}{10}); blue first is \frac{2}{5}, then red second is \frac{3}{4} (joint \frac{2}{5} \cdot \frac{3}{4} = \frac{3}{10}). Summing paths yields the probability of exactly one red in two draws as \frac{6}{10} = \frac{3}{5}.^[15]

Advanced Urn Variants

In Pólya's urn model, an urn initially contains one red ball and one white ball. At each step, a ball is drawn at random, observed, replaced, and an additional ball of the same color is added. After n such draws, the number of red balls drawn, denoted Y_n, follows a uniform distribution over \{0, 1, \dots, n\}, with P(Y_n = k) = \frac{1}{n+1} for each k. This counterintuitive uniformity arises because the model induces exchangeability in the sequence of draws, where every specific sequence with k reds and n-k whites has equal probability \prod_{i=0}^{k-1} \frac{1+i}{2+i} \prod_{j=0}^{n-k-1} \frac{1+j}{2+k+j}, which simplifies identically across orders.^[24] As n \to \infty, the proportion of red balls in the urn converges almost surely to a random limit distributed as Uniform[0,1], reflecting the model's reinforcement mechanism that preserves initial symmetry.^[24] An urn adaptation of the Boy or Girl paradox illustrates conditional probability with labeled balls. Suppose an urn contains two balls, each independently painted gold (representing "boy") or black (representing "girl") with probability $1/2. The possible configurations are GG, GB, BG, BB, each with probability $1/4, but GB and BG are indistinguishable as mixed. A ball is drawn at random and observed to be gold; the conditional probability that both are gold is then $1/3, as the gold observation equally likely comes from GG (two golds) or the mixed cases (one gold each), weighting the mixed twice as heavily.^[25] This labeled-ball setup mirrors the paradox's reliance on how information is revealed, emphasizing that the probability hinges on the sampling mechanism rather than naive symmetry.^[25] In the multivariate urn case, models extend to three or more types, such as trinomial outcomes with red, white, and blue balls. Starting with one ball of each of d colors and adding one of the drawn color per step, the joint counts after n draws follow a Dirichlet-multinomial distribution, generalizing the beta-binomial.^[3] For d=3, the probability of specific counts (k_1, k_2, k_3) with k_1 + k_2 + k_3 = n is \frac{n!}{k_1! k_2! k_3!} \frac{\Gamma(3) \Gamma(1+k_1) \Gamma(1+k_2) \Gamma(1+k_3)}{\Gamma(3+n) \Gamma(1)^3}, which integrates to marginals uniform over partitions for equal initials.^[26] The limiting proportions converge to a Dirichlet(1,1,1) distribution, uniform on the 2-simplex \{ (p_1,p_2,p_3) : p_i \geq 0, \sum p_i =1 \}, capturing trinomial reinforcement where draws favor observed types.^[26] Urn models also reveal paradoxes like the inspection paradox in sequential draws. When modeling renewal processes via an urn where balls represent interarrival intervals drawn sequentially without replacement, a randomly inspected draw (e.g., at a fixed time) tends to select a longer interval due to length-biased sampling, with expected length E[L^2]/E[L] exceeding the typical E[L].^[27] In sequential urn sampling, this manifests as oversampling extended runs of the same color, where the inspected run's length distribution is size-biased, leading to counterintuitive overestimation of average run duration.^[27]

Applications

In Statistics and Inference

Urn models serve as foundational tools in statistical inference, particularly for estimating unknown population parameters from finite samples without replacement. In the context of inverse probability, pioneered by Pierre-Simon Laplace, these models enable the estimation of the proportion \theta = x/N, where x is the unknown number of favorable items (e.g., white balls) in a total population of N items, based on observed draws. Laplace applied Bayes' rule with a uniform prior over possible values of x (from 0 to N), yielding a posterior distribution proportional to the hypergeometric likelihood of observing k favorable outcomes in n draws. This approach, detailed in his 1774 memoir, provides a principled way to invert observed data to infer underlying causes or proportions, such as estimating the likelihood of future events like sunrises from historical records.^[28]^[29] For frequentist inference, urn models underpin confidence intervals for population proportions via the hypergeometric distribution, which exactly describes sampling without replacement. When estimating \theta = x/N from k observed successes in n draws, exact confidence intervals can be constructed by inverting the hypergeometric cumulative distribution function, ensuring coverage probabilities that account for the finite population correction. Methods like the Clopper-Pearson interval, adapted for hypergeometric settings, provide conservative bounds that guarantee at least the nominal coverage level (e.g., 95%), avoiding overestimation of precision in small or finite populations. These intervals are particularly valuable in quality control or ecological sampling, where the total population size N is known but the proportion of interest is not. Bayesian updating in urn models is vividly illustrated by Pólya's urn scheme, where sequential draws reinforce beliefs about underlying proportions, mirroring the revision of posterior distributions. Starting with an urn containing a balls of one type and b of another (reflecting a beta prior on the success probability), each draw of a ball is followed by replacing it along with an additional ball of the same type, leading to a reinforcement process. This setup induces a beta-binomial marginal distribution for the number of successes, with the posterior after observations updating as in standard conjugate Bayesian inference for binomial data, but adapted for the urn's self-reinforcing dynamic. The process, formalized by Eggenberger and Pólya in 1923 and interpreted Bayesianly by Blackwell and MacQueen in 1973, elegantly demonstrates how prior beliefs evolve with data in finite sampling scenarios. Urn models also facilitate hypothesis testing for homogeneity, or equality of proportions, by leveraging statistics derived from hypergeometric sampling. To test whether two subpopulations have the same proportion of favorable items, the observed contingency table frequencies are modeled as a hypergeometric draw from a combined urn, with deviations assessed via exact p-values or approximations like the chi-squared statistic under the null of homogeneity. Fisher's exact test, introduced in 1922, computes the probability of the observed or more extreme tables under this null, providing a distribution-free method for small samples where asymptotic assumptions fail. This urn-based framework ensures precise control of Type I error in finite populations, as seen in applications to genetic association studies or randomized experiments. In modern nonparametric Bayesian statistics, urn models extend to metaphorically represent complex prior processes, notably the Dirichlet process introduced by Ferguson in 1973. Here, an urn scheme—often a Pólya-like reinforcement with a base measure—generates exchangeable sequences that underlie infinite mixture models, allowing inference on unknown numbers of latent categories without parametric assumptions. This connection bridges classical urn sampling to contemporary methods like Dirichlet process mixtures for clustering or density estimation, where sequential "draws" update beliefs about the data-generating distribution in an adaptive, infinite-dimensional manner.

In Other Fields

In decision theory, urn models illustrate ambiguity aversion through scenarios like the Ellsberg paradox, where individuals prefer bets on urns with known compositions over those with unknown but identical expected values, highlighting deviations from expected utility theory due to uncertainty about probabilities. This setup uses two urns—one with a fixed ratio of red and black balls (known risk) and another with an unknown ratio (ambiguity)—to demonstrate how people avoid the ambiguous option, even when objective probabilities match, as evidenced in experimental preferences for known-risk gambles. In statistical physics, Pólya's urn model serves as an analogy for contagion processes and branching phenomena, such as the spread of infections or particle interactions in networks, where drawing a "colored" ball reinforces similar outcomes, mimicking self-reinforcing growth.^[30] For instance, interacting Pólya urns with finite memory model epidemic dynamics on graphs, capturing spatial and temporal contagion where each node's urn evolves based on neighboring draws, leading to power-law distributions in infection clusters.^[31] Similarly, continuous-time variants extend the model to branching processes, representing gamma-distributed offspring in physical systems like neutron chains or molecular clustering.^[32] Recent extensions as of 2025 use urn models to simulate discrete-time quantum walks, providing a classical analogy for quantum probability processes in computational physics.^[33] In computer science, urn schemes underpin random graph generation, particularly through preferential attachment mechanisms that produce scale-free networks by assigning "balls" to vertices proportional to their degree, favoring connections to high-degree nodes.^[34] This Pólya-inspired process starts with an initial graph and iteratively adds vertices linked to existing ones via urn draws, yielding degree distributions with heavy tails akin to real-world networks like the internet or citation graphs.^[35] Generalizations allow weighted attachments, enabling models of directed or multilayer graphs while preserving the "rich-get-richer" dynamics.^[36] In economics, reinforced urn processes model market share evolution, where consumer choices draw from an urn representing product alternatives, adding balls for chosen options to simulate increasing returns and path dependence.^[1] For example, in a basic Pólya urn setup for duopoly markets, initial market shares determine long-run dominance via a Dirichlet-distributed limit, explaining phenomena like first-mover advantages where early leads amplify over time through positive feedback.^[37] Extensions incorporate quality differences or entry barriers, showing how reinforcement can lock in inefficient equilibria despite superior alternatives.^[38] As of 2025, generalized Pólya urns have been applied to model wealth growth through wages and capital returns, analyzing inequality dynamics.^[38] Modern applications in machine learning leverage Pólya urns for topic modeling, enhancing latent Dirichlet allocation (LDA) variants by introducing sparsity and parallelization in sampling word-topic assignments.^[35] The Pólya urn LDA sampler replaces traditional Gibbs methods with urn-based draws that enforce double sparsity—over topics and words—reducing computational costs for large corpora while maintaining the model's generative interpretation of documents as mixtures of topics. Further adaptations, such as weighted urn schemes, optimize topic coherence by self-reinforcing semantically related terms, improving interpretability in natural language processing tasks like document clustering.^[39] Generalized urns also address limitations in standard LDA by incorporating hierarchical structures for better handling of correlated topics.^[40] Emerging uses as of 2025 include urn models in sports analytics, such as analyzing football pass sequences with Pólya urns to model player interactions and team dynamics.^[41]

References

[1]
[PDF] A survey of random processes with reinforcement - arXiv
Section 2 provides an overview of the basic models, primarily urn models, and corresponding known methods of analysis. Section 3 is devoted to urn models, ...
[2]
[PDF] Introduction to Probability, Statistics and Random Processes ...
Find the probability that both these balls will be white. 4 / 11. Page 5. More examples. The urn problem (1). Let the urn contain 3 white balls and 4 black ...
[3]
[PDF] This chapter discusses Pólya's urn process and some ... - Penn Math
An urn contains R red balls and B black balls. A ball is drawn from the urn and replaced in the urn along with A balls of the same color.
[4]
[PDF] ON A CLASSICAL PROBLEM OF PROBABILITY THEORY b We ...
We consider the following classical “urn-problem”. Suppose that there are 71 urns given, and that balls are placed at random in these urns one after.
[5]
[PDF] Urn Models, Replicator Processes, and Random Genetic Drift
Sep 6, 2022 · Under the assumption that the expected number of balls being added always exceeds the expected number of balls being removed whenever balls are ...
[6]
[PDF] Electing the Doge of Venice: analysis of a 13th Century protocol
Jul 12, 2007 · voting theory, leader election,. Venice. This paper discusses the protocol used for electing the Doge of Venice between 1268 and the end of the ...
[7]
The Origin of Probability and The Problem of Points
Indeed, many mathematicians chose problems that arose specifically with relation to gambling as examples to study in regard to the computation of probabilities.
[8]
[PDF] The Significance of Jacob Bernoulli's Ars Conjectandi - Glenn Shafer
If there are no relevant limiting frequencies in a problem, it is not, according to the frequentists, a problem for probability. This would have astounded Jacob ...Missing: urn inverse
[9]
Turning points: Bernoulli's golden theorem - Raper - 2018
Jul 26, 2018 · Simon Raper begins a new series on key moments in the history of statistics, starting in seventeenth-century Switzerland with theologian-turned-mathematician ...
[10]
[PDF] Probability Theory and Interpretations
❑ Jacob Bernoulli worked on the subject from 1685 to his death in. 1705. His Ars Conjectandi , the first systematic and analytically ... the equation of inverse ...
[11]
[PDF] Laplace-a pioneer of statistical inference - WordPress.com
Laplace's inverse probability theory was based on the urn model. It was the model that mathematicians and statisticians subsequently applied throughout the.Missing: analogies | Show results with:analogies
[12]
[PDF] The Urn Model, Simula6on, and Resampling methods
Jul 21, 2012 · Why use the Urn Model? • Connects sta6s6cal techniques,. – Hypothesis Tests. – Confidence Interval to underlying chance process. • If clear on ...Missing: definition | Show results with:definition
[13]
[PDF] Law of Large Numbers The Bernoulli family is the most
Bernoulli's version of the law focused on proportions of success and failure, especially on the ratio of success to failures. For example, the theoretical ...
[14]
[PDF] Probability and Statistics: The Science of Uncertainty
It is important that students acquire a sound mathematical foundation in the basic techniques of probability and statistics, which we believe this book will ...
[15]
[PDF] 1957-feller-anintroductiontoprobabilitytheoryanditsapplications-1.pdf
... FELLER - An Introduction to Probability Theory and Its Applications,. VolumeI, Third Edition. FELLER - An Introduction to Probability Theory and Its Applica ...
[16]
[PDF] Introduction to Probability - Yale Statistics and Data Science
... Feller's classic text, An Introduction to Probability Theory and Its. Applications. This book had its start with a course given jointly at Dartmouth College ...
[17]
The Hypergeometric Distribution
### Procedural Description of Sampling Without Replacement in Urn Model
[18]
[PDF] Introduction to Probability Theory and Its Applications
FELLER · An Introduction to Probability Theory and Its Applications,. Volume ... Urn Models. 118. ·. 3. Stochastic Independence. 125. 4. Product Spaces ...
[19]
[PDF] Uses of the Hypergeometric Distribution for Determining Survival or ...
In 1711, De Moivre solved “Huygens' fourth proposed problem” and his solution gave the probability of selecting x white and c-x black balls from a population ...
[20]
Über die Statistik verketteter Vorgänge - Eggenberger - 1923 - ZAMM
Über die Statistik verketteter Vorgänge. F. Eggenberger,. F. Eggenberger. Zürich. Search for more papers by this author · G. Pólya, ... Download PDF. back ...
[21]
8. Pólya's Urn Process - Random Services
Pólya's urn process involves drawing a ball from an urn, returning it with new balls of the same color. It generalizes hypergeometric and Bernoulli models.Missing: source | Show results with:source
[22]
[PDF] Exchangeability and de Finetti's Theorem
Apr 26, 2007 · If X1,...,Xn,... are independent and identically distributed, they are exchangeable, but not conversely.Missing: limits | Show results with:limits
[23]
A martingale approach for Pólya urn processes - Project Euclid
This paper is devoted to a direct martingale approach for Pólya urn models asymptotic behaviour. A Pólya process is said to be small when the ratio of its ...
[24]
[PDF] Polya's Urn and the Beta-Bernoulli Process - UChicago Math
Aug 13, 2025 · In addition, Polya's Urn is a multivariate distribution whose variables are exchangeable but not independent.
[25]
[PDF] Polya's urn and martingales - staff.math.su.se
May 19, 2021 · The above property is known as the martingale property, and a sequence ... usually referred to as the continuity property of probability measures.Missing: recursive | Show results with:recursive
[26]
[PDF] On Reinforcement-Depletion Compartmental Urn Models
In this section we treat the special case of one stage of reinforcement and depletion. The analysis is based on the following sampling problem: suppose that we ...
[27]
Boy or Girl
Imagine somebody selecting two balls (with replacement) from an urn containing an equal number of white and black balls. If you see the colour of the first ball ...
[28]
[PDF] Pólya-splitting distributions as stationary solutions of multivariate ...
Dec 7, 2022 · Abstract Multivariate count distributions are crucial for the inference of eco- logical processes underpinning biodiversity.<|separator|>
[29]
Sampling Bias and the Inspection Paradox - jstor
These examples of sampling bias are a special case of the well-known inspection paradox in ... successive yarn lengths are independent and identically distributed ...Missing: sequential | Show results with:sequential
[30]
[PDF] Memoir on the probability of the causes of events - University of York
LAPLACE'S 1774 MEMOIR event given the causes, and the probability of the existence of each of these is equal to the probability of the event given that ...
[31]
Laplace's 1774 Memoir on Inverse Probability - jstor
Abstract. Laplace's first major article on mathematical statistics was pub- lished in 1774. It is arguably the most influential article in this field to.
[32]
[PDF] A Finite Memory Interacting P´olya Contagion Network and its ... - arXiv
Dec 21, 2021 · The objective is to model the spread of infection (commonly referred to as contagion) through this interacting Pólya urn network, where each ...
[33]
A Finite Memory Interacting Pólya Contagion Network and Its ...
We introduce a new model for contagion spread using a network of interacting finite memory two-color Pólya urns.
[34]
[PDF] The continuous-time triangular Pólya process
Jan 2, 2017 · Keywords Urn · Pólya urn · Pólya process · Branching process · Gamma distribution · ... Ehrenfest (1907), where the authors used urns as models ...
[35]
On a preferential attachment and generalized Pólya's urn model
We study a general preferential attachment and Pólya's urn model. At each step a new vertex is introduced, which can be connected to at most one.
[36]
[PDF] P´olya Urn Latent Dirichlet Allocation: a doubly sparse massively ...
Abstract—Latent Dirichlet Allocation (LDA) is a topic model widely used in natural language processing and machine learning. Most approaches to training the ...
[37]
Generating Preferential Attachment Graphs via a Pólya Urn ... - arXiv
Jan 17, 2024 · Preferential attachment graphs are an important class of randomly generated graphs which are often used to capture the “rich gets richer” ...Missing: schemes | Show results with:schemes
[38]
First mover or higher quality? Optimal product strategy in markets ...
Oct 26, 2017 · In this paper, we test that intuition within a generalized Pólya urn model. We find that if we assume constant feedbacks, in the long run, ...
[39]
Wages and capital returns in a generalized Pólya urn
Dec 16, 2024 · In this paper we study this phenomenon using a new extension of Pólya's urn, modelling wealth growth through wages and capital returns.
[40]
[PDF] Review Topic Discovery with Phrases using the Pólya Urn Model
We start by briefly reviewing the Latent Dirichlet Allocation (LDA) model (Blei et al., 2003). Then we describe the simple Pólya urn (SPU) model, which is ...
[41]
[PDF] Optimizing Semantic Coherence in Topic Models - David Mimno
This new topic model retains the document– topic component of standard LDA, but replaces the usual Pólya urn topic–word component with a gen- eralized Pólya urn ...