Urn problem
Encyclopedia
In probability
and statistics
, an urn problem is an idealized mental exercise
in which some objects of real interest (such as atoms, people, cars, etc.) are represented as colored balls in an urn
or other container.
One pretends to draw (remove) one or more balls from the urn;
the goal is to determine the probability of drawing one color or another,
or some other properties.
An urn model is either a set of probabilities that describe events within an urn problem, or it is a probability distribution
, or a family of such distributions, of random variable
s associated with urn problems.
, the urn contains x white and y black balls; one ball is drawn randomly from the urn and its color observed; it is then placed back in the urn, and the selection process is repeated.
Possible questions that can be answered in this model are:
problem, and was a topic of research in the eighteenth century, attracting the attention of Abraham de Moivre
and Thomas Bayes
.
Bernoulli's inspiration may have been lotteries
, election
s, or games of chance which involved drawing balls from a container, and it has been asserted that
Probability
Probability is ordinarily used to describe an attitude of mind towards some proposition of whose truth we arenot certain. The proposition of interest is usually of the form "Will a specific event occur?" The attitude of mind is of the form "How certain are we that the event will occur?" The...
and statistics
Statistics
Statistics is the study of the collection, organization, analysis, and interpretation of data. It deals with all aspects of this, including the planning of data collection in terms of the design of surveys and experiments....
, an urn problem is an idealized mental exercise
Thought experiment
A thought experiment or Gedankenexperiment considers some hypothesis, theory, or principle for the purpose of thinking through its consequences...
in which some objects of real interest (such as atoms, people, cars, etc.) are represented as colored balls in an urn
Urn
An urn is a vase, ordinarily covered, that usually has a narrowed neck above a footed pedestal. "Knife urns" placed on pedestals flanking a dining-room sideboard were an English innovation for high-style dining rooms of the late 1760s...
or other container.
One pretends to draw (remove) one or more balls from the urn;
the goal is to determine the probability of drawing one color or another,
or some other properties.
An urn model is either a set of probabilities that describe events within an urn problem, or it is a probability distribution
Probability distribution
In probability theory, a probability mass, probability density, or probability distribution is a function that describes the probability of a random variable taking certain values....
, or a family of such distributions, of random variable
Random variable
In probability and statistics, a random variable or stochastic variable is, roughly speaking, a variable whose value results from a measurement on some type of random process. Formally, it is a function from a probability space, typically to the real numbers, which is measurable functionmeasurable...
s associated with urn problems.
Basic urn model
In this basic urn model in probability theoryProbability theory
Probability theory is the branch of mathematics concerned with analysis of random phenomena. The central objects of probability theory are random variables, stochastic processes, and events: mathematical abstractions of non-deterministic events or measured quantities that may either be single...
, the urn contains x white and y black balls; one ball is drawn randomly from the urn and its color observed; it is then placed back in the urn, and the selection process is repeated.
Possible questions that can be answered in this model are:
- can I infer the proportion of white and black balls from n observations ? With what degree of confidence ?
- knowing x and y, what is the probability of drawing a specific sequence (e.g. one white followed by one black)?
- if I only observe n white balls, how sure can I be that there are no black balls?
Other models
Many other variations exist:- the urn could have numbered balls instead of colored ones
- balls may not be returned to the urns once drawn.
Examples of urn problems
- binomial distribution: the distribution of the number of successful draws (trials), eg. extraction of white ball, given n draws with replacement in an urn with black and white balls.
- beta-binomial distribution: the distribution of the number of successful draws (trials), eg. extraction of white ball, given n draws with replacement in an urn with black and white balls when every time a white ball is observed, an additional white ball is added to the urn and every time a black ball is observed, an additional black ball is added to the urn.
- Multinomial distribution: the urn contains balls in several separate colours (agents).
- Hypergeometric distribution: the balls are not returned to the urn once extracted (without replacement).
- Multivariate hypergeometric distribution: the multiple coloured balls are not returned.
- geometric distribution: number of draws before the first successful (correctly colored) draw.
- negative binomial distributionNegative binomial distributionIn probability theory and statistics, the negative binomial distribution is a discrete probability distribution of the number of successes in a sequence of Bernoulli trials before a specified number of failures occur...
: number of draws before a certain number of failures (incorrectly colored draws) occurs. - Polya distribution - Polya urn modelPolya urn modelIn statistics, a Polya urn model , named after George Pólya, is a type of statistical model used as an idealized mental exercise to understand the nature of certain statistical distributions.In an urn model, objects of real interest are represented as colored balls in an urn or...
: an urn initially contains r red and b blue marbles. One marble is chosen randomly from the urn. The marble is then put back into the urn together with another marble of the same colour. Hence, the number of total marbles in the urn grows. Let Xn be the number of red marbles in the urn after n iterationIterative methodIn computational mathematics, an iterative method is a mathematical procedure that generates a sequence of improving approximate solutions for a class of problems. A specific implementation of an iterative method, including the termination criteria, is an algorithm of the iterative method...
s of this procedure, and let Yn=Xn/(n+r+b). Then the sequence { Yn : n = 1, 2, 3, ... } is a martingaleMartingale (probability theory)In probability theory, a martingale is a model of a fair game where no knowledge of past events can help to predict future winnings. In particular, a martingale is a sequence of random variables for which, at a particular time in the realized sequence, the expectation of the next value in the...
and converges to the beta distribution. - Statistical physicsStatistical physicsStatistical physics is the branch of physics that uses methods of probability theory and statistics, and particularly the mathematical tools for dealing with large populations and approximations, in solving physical problems. It can describe a wide variety of fields with an inherently stochastic...
: derivation of energy and velocity distributions - The Ellsberg paradoxEllsberg paradoxThe Ellsberg paradox is a paradox in decision theory and experimental economics in which people's choices violate the expected utility hypothesis.An alternate viewpoint is that expected utility theory does not properly describe actual human choices...
Historical remarks
In Ars conjectandi (1713), Bernoulli considered the problem of determining, given a number of pebbles drawn from an urn, the proportions of different colored pebbles with the urn. This problem was known as the inverse probabilityInverse probability
In probability theory, inverse probability is an obsolete term for the probability distribution of an unobserved variable.Today, the problem of determining an unobserved variable is called inferential statistics, the method of inverse probability is called Bayesian probability, the "distribution"...
problem, and was a topic of research in the eighteenth century, attracting the attention of Abraham de Moivre
Abraham de Moivre
Abraham de Moivre was a French mathematician famous for de Moivre's formula, which links complex numbers and trigonometry, and for his work on the normal distribution and probability theory. He was a friend of Isaac Newton, Edmund Halley, and James Stirling...
and Thomas Bayes
Thomas Bayes
Thomas Bayes was an English mathematician and Presbyterian minister, known for having formulated a specific case of the theorem that bears his name: Bayes' theorem...
.
Bernoulli's inspiration may have been lotteries
Lottery
A lottery is a form of gambling which involves the drawing of lots for a prize.Lottery is outlawed by some governments, while others endorse it to the extent of organizing a national or state lottery. It is common to find some degree of regulation of lottery by governments...
, election
Election
An election is a formal decision-making process by which a population chooses an individual to hold public office. Elections have been the usual mechanism by which modern representative democracy operates since the 17th century. Elections may fill offices in the legislature, sometimes in the...
s, or games of chance which involved drawing balls from a container, and it has been asserted that
Elections in medieval and renaissance VeniceVeniceVenice is a city in northern Italy which is renowned for the beauty of its setting, its architecture and its artworks. It is the capital of the Veneto region...
, including that of the dogeDoge of VeniceThe Doge of Venice , often mistranslated Duke was the chief magistrate and leader of the Most Serene Republic of Venice for over a thousand years. Doges of Venice were elected for life by the city-state's aristocracy. Commonly the person selected as Doge was the shrewdest elder in the city...
, often included the choice of electors by lot, using balls of different colors drawn from an urn..
See also
- Coin-tossing problems
- Coupon collector's problemCoupon collector's problemIn probability theory, the coupon collector's problem describes the "collect all coupons and win" contests. It asks the following question: Suppose that there are n coupons, from which coupons are being collected with replacement...
- Noncentral hypergeometric distributionsNoncentral hypergeometric distributionsIn statistics, the hypergeometric distribution is the discrete probability distribution generated by picking colored balls at random from an urn without replacement....
- Multivariate Pólya distributionMultivariate Polya distributionThe multivariate Pólya distribution, named after George Pólya, also called the Dirichlet compound multinomial distribution, is a compound probability distribution, where a probability vector p is drawn from a Dirichlet distribution with parameter vector \alpha, and a set of discrete samples is...
Further reading
- Johnson, N.L.; Kotz, S. (1977) Urn Models and Their Application: An Approach to Modern Discrete Probability Theory, Wiley ISBN 0471446300
- Mahmoud , Hosam M.(2008) Polya Urn Models, Chapman & Hall/CRC. ISBN 1420059831