Basic Theory
The Model
Pólya's urn scheme is a dichotomous sampling model that generalizes the hypergeometric model (sampling without replacement) and the Bernoulli model (sampling with replacement). Pólya's urn proccess leads to a famous example of a sequence of random variables that is exchangeable, but not independent, and has deep conections with the beta-Bernoulli process.
An urn initially contains red and green balls, where and are positive integers. At each discrete time (trial), a ball is selected from the urn and then returned to the urn along with new balls of the same color. The random process is known as Pólya's urn process, named for George Pólya.
Ordinarily, the parameter is a nonnegative integer. However, the model actually makes sense if is a negative integer, if we interpret this to mean that we remove the balls rather than add them, and assuming that there are enough balls of the proper color in the urn to perform this action.
In terms of the colors of the selected balls, Pólya's urn scheme generalizes the standard models of sampling with and without replacement.
- corresponds to sampling with replacement.
- corresponds to sampling without replacement.
For the most part, we will assume that is nonnegative so that the process can be continued indefinitely. Occasionally we consider the case so that we can interpret the results in terms of sampling without replacement.
The Outcome Variables
Let denote the color of the ball selected at time , where 0 denotes green and 1 denotes red. The basic random process is the sequence of indicator variables , known as the Pólya process.
As with any random process, our first goal is to compute the finite dimensional distributions of . That is, we want to compute the joint distribution of for each . Some additional notation will really help. Recall the generalized permutation formula in our study of combinatorial structures: for and , we defined
Note that the expression has factors, starting with , and with each factor obtained by adding to the previous factor. As usual, we adopt the convention that a product over an empty index set is 1. Hence for every and .
Recall that
- , an ordinary power
- , a descending power
- , an ascending power
The following simple result will turn out to be quite useful.
Suppose that and . Then
Details:
It's just a matter of grouping the factors:
The finite dimensional distributions are easy to compute using the multiplication rule of conditional probability. If we know the contents of the urn at any given time, then the probability of an outcome at the next time is all but trivial.
Let , and let . Then
Details:
By the multiplication rule for conditional probability,
Of course, if we know that the urn has, say, red and green balls at a particular time, then the probability of a red ball on the next draw is while the probability of a green ball is . The right side of the displayed equation above has factors. The denominators are the total number of balls at the times, and form the product . In the numerators, of the factors correspond to probabilities of selecting red balls; these factors form the product . The remaining factors in the numerators correspond to selecting green balls; these factors form the product .
The joint probability in [6] depends on only through the number of red balls in the sample. Thus, the joint distribution is invariant under a permutation of , and hence is an exchangeable sequence of random variables. This means that for each , all permutations of have the same distribution. Of course the joint distribution reduces to the formulas we have obtained earlier in the special cases of sampling with replacement () or sampling without replacement (), although in the latter case we must have . When , the Pólya process is a special case of the beta-Bernoulli process, studied in the chapter on Bernoulli trials.
The Pólya process with parameters is the beta-Bernoulli process with parameters and . That is, for , , and with ,
Details:
From [5] and [6],
and this is the corresponding finite dimensional distribution of the beta-Bernoulli distribution with parameters and .
Recall that the beta-Bernoulli process is obtained, in the usual formulation, by randomizing the success parameter in a Bernoulli trials sequence, giving the success parameter a beta distribution. So specifically, suppose and that random variable has the beta distribution with parameters and . Suppose also that given , the random process is a sequence of Bernoulli trials with success parameter . Then is the Pólya process with parameters . This is a fascinating connection between two processes that at first, seem to have little in common. In fact however, every exchangeable sequence of indicator random variables can be obtained by randomizing the success parameter in a sequence of Bernoulli trials. This is de Finetti's theorem, named for Bruno de Finetti, which is studied in the section on backwards martingales. When , all of the results in this section are special cases of the corresponding results for the beta-Bernoulli process, but it's still interesting to interpret the results in terms of the urn model.
For each
Details:
Since the sequence is exchangeable, has the same distribution as , so . The mean and variance now follow from standard results for indicator variables.
Thus is a sequence of identically distributed variables, quite surprising at first but of course inevitable for any exchangeable sequence. Compare the joint and marginal distributions. Note that is an independent sequence if and only if , when we have simple sampling with replacement. Pólya's urn is one of the most famous examples of a random process in which the outcome variables are exchangeable, but dependent (in general).
Next, let's compute the covariance and correlation of a pair of outcome variables.
Suppose that are distinct. Then
Details:
From [8] and the fact that the variables are exchangeable, . The results now follow from standard formulas for covariance and correlation.
Thus, the variables are positively correlated if , negatively correlated if , and uncorrelated (in fact, independent), if . These results certainly make sense when we recall the dynamics of Pólya's urn. It turns out that in any infinite sequence of exchangeable variables, the variables must be nonnegatively correlated. Here is another result that explores how the variables are related.
Suppose that and . Let . Then
Details:
From [4],
Pólya's urn is described by a sequence of indicator variables. We can study the same derived random processes that we studied with Bernoulli trials: the number of red balls in the first trials, the trial number of the th red ball, and so forth.
The Number of Red Balls
For , the number of red balls selected in the first trials is
so that is the partial sum process associated with .
Note that
- The number of green balls selected in the first trials is .
- The number of red balls in the urn after the first trials is .
- The number of green balls in the urn after the first trials is .
- The number of balls in the urn after the first trials is .
The basic analysis of follows easily from our work with .
The probability density function of is given by
Details:
is the sum of over all with . There are such sequences, and each has the probability given in [5].
The distribution defined by this probability density function is known, appropriately enough, as the Pólya distribution with parameters , , , and . Of course, the distribution reduces to the binomial distribution with parameters and in the case of sampling with replacement () and to the hypergeometric distribution with parameters , , and in the case of sampling without replacement (), although again in this case we need . When , the Póyla distribution is a special case of the beta-binomial distribution.
If then the Pólya distribution with parameters is the beta-binomial distribution with parameters and . That is,
Details:
From [6], is the beta-Bernoulli process with parameters and . So by definition, has the beta-binomial distribution with parameters , , and . A direct proof is also simple using the permutation formula in [5]:
The case where all three parameters are equal is particularly interesting.
If then is uniformly distributed on .
Details:
This follows from [13], since the beta-binomial distribution with parameters , 1, and 1 reduces to the uniform distribution. Specifically, note that , and . So substituting gives
In general, the Pólya family of distributions has a diverse collection of shapes.
Start the simulation of the Pólya Urn Experiment. Vary the parameters and note the shape of the probability density function. In particular, note when the function is skewed, when the function is symmetric, when the function is unimodal, when the function is monotone, and when the function is U-shaped. For various values of the parameters, run the simulation 1000 times and compare the empirical density function to the probability density function.
The Pólya probability density function is
- unimodal if and
- unimodal if and
- U-shaped if and
- U-shaped if and
- increasing if
- decreasing if
Details:
These results follow from [13] by solving the inequality .
Next, let's find the mean and variance. Curiously, the mean does not depend on the parameter .
The mean and variance of the number of red balls selected are
Details:
These results follow from [6] and [7], and basic properties of expected value and variance.
Start the simulation of the Pólya Urn Experiment. Vary the parameters and note the shape and location of the mean standard deviation bar. For various values of the parameters, run the simulation 1000 times and compare the empirical mean and standard deviation to the distribution mean and standard deviation.
Explicitly compute the probability density function, mean, and variance of when , , and for the values of . Sketch the graph of the density function in each case.
Fix , , and , and let . Then
Details:
Note that . The numerator and denominator each have factors. If these factors are grouped into a product of fractions, then the first is . The rest have the form where Each of these converges to 1 as . Part (b) follows by a similar argument. Part (c) follows from (a) and (b) and the complement rule.
So the limiting distribution of as is concentrated on 0 and . The limiting probabilities are just the initial proportion of green and red balls, respectively. Interpret this result in terms of the dynamics of Pólya's urn scheme.
Our next result gives the conditional distribution of given .
Suppose that and . Then
Details:
Let and let . Note that the events over partition the event . Conditioning on ,
But from [10], for every . Hence
The last sum is 1.
In particular, if then . This is Laplace's rule of succession, another interesting connection. The rule is named for Pierre Simon Laplace, and is studied from a different point of view in the section on independence.
The Proportion of Red Balls
Suppose that , so that the process continues indefinitely. For , the proportion of red balls selected in the first trials is
This is an interesting variable, since a little reflection suggests that it may have a limit as . Indeed, if , then is just the sample mean corresponding to Bernoulli trials. Thus, by the law of large numbers, converges to the success parameter as with probability 1. On the other hand, the proportion of red balls in the urn after trials is
When , of course, so that in this case, and have the same limiting behavior. Note that
Since the constant term converges to 0 as and the coefficient of converges to 1 as , it follows that the limits of and as will be the same, if the limit exists, for any mode of convergence: with probability 1, in mean, or in distribution. Here is the general result when .
Suppose that . There exists a random variable having the beta distribution with parameters and such that and as with probability 1 and in mean square, and hence also in distribution.
Details:
As noted earlier, the urn process is equivalent to the beta-Bernoulli process with parameters and . We showed in that section that as with probability 1 and in mean square, where is the beta random variable used in the construction.
In turns out that the random process is a martingale. The theory of martingales provides powerful tools for studying convergence in Pólya's urn process. As an interesting special case, note that if then the limiting distribution is the uniform distribution on .
The Trial Number of the th Red Ball
Suppose again that , so that the process continues indefinitely. For let denote the trial number of the th red ball selected. Thus
Note that takes values in . The random processes and are inverses of each other in a sense.
For with ,
- if and only if
- if and only if and
The probability denisty function of is given by
Details:
We condition on . From [12] and [10],
Of course this probability density function reduces to the negative binomial density function with trial parameter and success parameter when (sampling with replacement). When , the distribution is a special case of the beta-negative binomial distribution.
If then has the beta-negative binomial distribution with parameters , , and . That is,
Details:
As with previous proofs, this result follows since the underlying process is the beta-Bernoulli process with parameters and . The form of the PDF also follows easily from [24] result by dividing the numerator and denominator .
If then
Details:
As in the corresponding proof in [12], the fraction in the PDF of in [25] reduces to , while the binomial coefficient is .
Fix , , and , and let . Then
So the limiting distribution of is concentrated on and . The limiting probabilities at these two points are just the initial proportion of red and green balls, respectively. Interpret this result in terms of the dynamics of Pólya's urn scheme.