Urn problem

An urn model is a thought experiment that is used in probability theory and statistics to model different random experiments in a unified and intuitive manner. To a fictitious vessel urn called filled with a certain number of balls, which are then drawn at random. This means that for each train all balls contained in the urn have the same probability of being selected. This allows the determination of interest probabilities are attributed to the solution of combinatorial counting problems.

A distinction draws with replacement, where each ball is put back in the urn after registering again, is not covered by drawings without replacement, in which a ball is drawn once again. Many important probability distributions, such as the binomial distribution, the multinomial distribution, the hypergeometric distribution, the geometric distribution of the negative binomial distribution, or may be derived by means of models urn and illustrated.

• 4.1 Unique Pull
• 4.2 Drag balls of the same color
• 4.3 Pull with compliance with the order
• 4.4 Pull without regard to the order
• 4.5 Summary of events

• 5.1 Number of balls of one color
• 5.2 Waiting time for a number of balls of one color
• 5.3 Number of balls of a color combination

History

Although the concept of the urn model can be traced back to the Old Testament and ancient Greece, is his first explicit mention back in a mathematical context to the Swiss mathematician Jacob Bernoulli. At the beginning of the third part of his famous work Ars Conjectandi from 1713 Bernoulli describes the following problem:

" Someone is after two stones, one black and one white, has placed in an urn for three players A, B, C a price under the condition that the person who should receive it, which first attracts the white stone; but if none of the three player moves the white stone, so also no one receives the prize. First, attracts A and puts the drawn stone back into the urn, then B does the same thing as second, and then follows C in third place. What hopes have three players? "

This is with "hope" the expectancy of a player meant. Bernoulli used in his written works in the Latin language, the terms urna for a ballot box and calculi for scoring markers. Such filled with Loskugeln ballot boxes were among others in the Republic of Venice in the election of the Doge used. The basic idea behind such an urn model was the concept of equal probability of any stone is drawn from the urn for Bernoulli. Based on this, it is now possible earnings expectations three players determine: Player A wins in 50 % of cases, player B in 25% of cases, player C in 12.5 % of cases and none of the three players also in 12.5 % of cases.

Similar urn problems were considered in the 18th century by Daniel Bernoulli and Pierre Remond de Mont Mort. Abraham de Moivre and Thomas Bayes sat down at this time in the context of inferential statistics specifically with the question of whether it is possible close to the proportions of balls in the urn from watching the balls drawn. Almost one hundred years after Bernoulli handle Pierre- Simon Laplace, the idea in his Théorie Analytique the probabilites again and gave a presentation on probability theory on a firm mathematical foundation.

Today urn models are a central part of the basic training in probability theory and statistics.

Models

In an urn there are several balls, which can have different properties, for example, are colored or labeled differently, but are otherwise identical. From this urn, a ball will be taken out and registered. It is assumed that in such a drawing, a ball is selected at random, which means it should not be predictable, which is drawn of the balls. It is further assumed that each ball is drawn with the same probability, since the balls are well mixed and by their nature can not be distinguished. This process of drawing will now be repeated several times, the following two cases can be distinguished:

• Sampling with replacement: each ball is put back in the urn after registering again; the number of balls in the urn so that does not change with multiple draws.
• Sampling without replacement: a once drawn ball is not put back; the number of balls in the urn so that decreases after each draw by one.

Urn models are representative of a large class of random experiments, with urn and balls are replaced with other objects. Examples are:

• Tossing a coin or a cube
• Giving the game cards in a card game
• The drawing of the lottery numbers or other lotteries
• The conduct of gambling, such as Roulette

Below is the particularly clear case of an urn filled with different colored balls is considered.

Result sets

Single pull

In probability theory results, such that a particular ball is drawn, represented by quantities. If some balls in the urn are the same color, it is proving to be beneficial to distinguish the balls from each other. Are located in the urn total balls, then one defines as a result set for drawing a ball

Where the elements of the result set to identify the individual balls. If there are, for example, by three red, one green and two blue balls in the urn, this is how the result set

Describe. Each result, a probability is now assigned. After each ball is drawn with the same probability, is this is a Laplace experiment in which the probability of each element of the result set

Applies. In the above example with six balls so you get the same probability for each ball

Sampling with replacement

As you drag, a plurality of balls, the results are represented by tuples, where the length of the tuple corresponds to the number of draws. Are drawn from the balls in the urn balls with replacement, then the result set has the form

The result set is thus the fold Cartesian product of the result set of a simple drawing. This is also known by a variation with repetition. Since there are for each of the tuple elements opportunities, one obtains for the number of elements of the result set

Be drawn from the urn example with six balls three balls with replacement, then every ball combination has the same probability

This probability is just three times the product of the probabilities during a single drawing.

Sampling without replacement

Even when sampling without replacement, the results are represented by tuples. Are drawn from the balls in the urn balls without replacement, then the result set has the form

The result set now consists of all tuples in which no element of the tuple occurs more than once. It also talks of variation without repetition. Once there are ways for the first tuple element, for the second facility, and so on, we obtain for the number of elements of the result set

The term is called falling factorial with factors from. If from the sample urn with six balls three balls drawn without replacement, then every admissible ball combination has the probability

This probability is just the product of the probabilities at each unique drawing from an urn with six, five and four balls.

Sets of events

Single pull

Events, such as balls that certain colors are drawn, are also shown in probability theory by sets. An event here is simply a subset of the result set, ie. For example, the event that a red or green ball is drawn during a single drawing from the urn example, by

Described. According to the Laplace 's formula then applies to the probability that an event occurs:

Thus, the determination of the probability of an event on the enumerate of results can be attributed. For example, is calculated as the probability that a red or green ball is drawn during a single drawing from the urn example

With multiple contractions, however, the single enumeration of results, for example with the aid of tree diagrams, are very complex. Auxiliaries from the enumerative combinatorics Instead, this is often used.

Drag balls of the same color

First, we consider the event that getting a ball of the same color is drawn in draws. If the number of balls of that color, then apply at a with replacement for the probability of this event

The probability is therefore the -th power of the probability of the one-time draw a ball of that color. With a selection without replacement is obtained instead

For this probability is zero, because no more balls of one color can be drawn, as are present in the urn. For example, the probability that out of the urn example three red balls are drawn at a draw with replacement

And at a draw without replacement

Pull compliance with the order

Different colored balls are drawn, it is to be distinguished when considering the events, if the order in which the beads were drawn to play a role or not. In the first case we also speak of an orderly contraction, in the other from a disordered contraction.

In the following, it is assumed that each color a ball is drawn accurately. Are located in the box of the first color beads, spheres of the second color and so on, so is the probability that a first ball of the first color as a second ball of the second color and so on until the last one of the ball -th color is drawn at a draw with replacement

And at a draw without replacement

For example, the probability that one will be red, one green and one blue ball grown in this order from the urn example, in a drawing with replacement

And at a draw without replacement

Exactly the same probabilities arise when any other order of the balls ( about green, blue, red) is selected.

Pull without regard to the order

If now the exact order in which the balls are drawn, be disregarded, in addition, all permutations of the balls drawn must be considered. This is calculated as the probability that each a ball of different color is drawn at a draw with replacement

And at a draw without replacement

For example, the probability that out of the urn example three different colored balls are drawn at a draw with replacement

And at a draw without replacement

In the more general case in which a plurality of balls of each color are moved, to be viewed with repeating permutations. The number of such permutations is given by multinomial, see the section number of balls of a color combination.

In a drawing with replacement, a re-interpretation of probability in a reduced probability space with elements is possible. In this probability space results are considered equivalent if they emerge by permutation of the balls apart. One speaks here of a combination without repetition. Even in the reduced probability space, all results are equally likely.

Such a reinterpretation is possible also in a draw without replacement, and then you get a reduced probability space with elements. Accordingly, one speaks of a combination with repetition. However, this is not a Laplacian probability space more space, because the probability that two balls are drawn, here is twice as high as that for two of the same beads.

Summary of events

More complex events can often be decomposed into simpler ones, mutually exclusive events. Is a set of events the union of pairwise disjoint events, then the probability of the entire event is the sum of the probabilities of the individual events:

For example, the probability that a ball of the same color is drawn from the urn example, twice in a draw without replacement

Occasionally, it is also effective to count the results not occurred, wherein one uses the formula for the probability of counter:

For example, the probability that the sample is drawn from urn at twice sampling without replacement no green ball

Derived distributions

Events associated quantities, such as the number of solid balls of a particular color or the number of draws until the first time a ball is pulled to a certain color, can be interpreted as discrete random variable. Typically, the probability distribution of such random variables is no longer uniformly distributed, that is, the values ​​that the random variable can assume, no longer have the same probability. Some of these induced urn models probability distributions in statistics have a great importance and have their own names.

Number of balls of one color

In the urn contains balls of one color and balls of other colors. The probability that after contractions just the first color balls are drawn, is at a drawing with replacement

The corresponding probability distribution is called the binomial distribution. With a selection without replacement results in analogous

And the corresponding distribution is called the hypergeometric distribution.

Waiting for a plurality of balls of a color

In the urn are again balls of one color and balls of other colors. The probability that after draws a sphere of the first color after unplugging the -th time last train is at a drawing with replacement

The corresponding probability distribution is called negative binomial distribution and in the special case of geometric distribution. With a selection without replacement results in analogous

And the corresponding distribution is called a negative hypergeometric distribution.

Number of balls of a color combination

In the urn now contains balls of color. The probability that after contractions exactly the color balls were drawn for, is at a draw with replacement:

The corresponding probability distribution is called multinomial distribution. With a selection without replacement results in analogous

And the corresponding distribution is called multivariate hypergeometric distribution.

Other variants

In a Pólya urn model, named after the Hungarian mathematician George Pólya, an exact copy of the ball is placed in the urn after pulling a ball next to the ball itself also. The number of balls in the urn thus grows with each draw by one. In a way, a Pólya urn model can be viewed as the opposite of a draw without replacement. After balls are more often in a frequently occurring color in the drawings, self-reinforcing effects can be modeled by Pólya urn models. An important, derivable by the Pólya - urn model probability distribution is the beta - binomial distribution.

For Pólya urn models there are a number of generalizations, for example by not just one but multiple copies of the drawn ball are placed in the urn. In other versions, a copy of a different colored ball is put back into the box, or in addition completed, instead of the solid sphere.

A further generalization is to use a plurality of boxes which are all filled with balls. A draw will take place in two steps: the first step is randomly one of the urns, then dragged a ball in the second step from the selected urn. In a way, dually are questions regarding the assignment of urns, balls when not pulled, but are randomly distributed over the available polls, see enumerative combinatorics # balls and pockets.

Applications

Urn models help in understanding the following, among other phenomena and problems:

• Birthday paradox: In a class of 23 students have with a probability of over 50 % two have the same birthday.
• Ellsberg paradox: In human decisions which risk may be more accepted than uncertainty.
• St. Petersburg paradox: At a gamble with infinitely large expected payout the subjective profit expectations may still be low.
• Collecting Images Problem: How many randomly drawn collection images are on average needed to get a complete collection?

Applications of urn models are for example:

• The implementation of random sampling in quality control
• Determining the probability of failure of technical systems with multiple components
• The occurrence of insurance claims in an insurance
• The modeling of diffusion processes with the Ehrenfest model