From Polya urns to the OK Corral

A new postdoc here, Punyaslok Purkayastha, pointed out to me a Probability Surveys paper by Robin Pemantle on random processes with reinforcement, and I’ve been reading through it in spare moments (usually on the bus). I have had a problem knocking about my head that is related (Ram Rajagopal and I thought we could do in our spare time but we never managed to find enough time to work on it). All this stuff is pretty well-known already, but I thought it was a nice story.

A Polya urn process starts by taking an urn with R_0 = a red balls and B_0 = b black balls at time 0. For each time t \ge 1, draw a ball uniformly from the balls in the urn and then replace it together with another ball of the same color. Let X_n be the sequence of colors that you draw, where red is 0 and black is 1. So with probability R_n / (R_n + B_n) we have X_n = 0. The urn is updated according to R_{n+1} = R_n + 1(X_n = 0) and B_{n+1} = B_n + 1(X_n = 1).`

To figure out the asymptotic behavior of this process, just note that the sequence of colors is exchangeable. If x_1^n has k 1’s in it, then

\mathbb{P}(X_0^{n} = x_0^n) = \frac{ \prod_{i = 0}^{k-1} (a + i) \prod_{i=0}^{n-k-1} (b + i)}{ \prod_{i=0}^{n-1} (a + b + i) }

From this it is clear that the probability of seeing $x_1^n$ only depends on its type (empirical distribution, for non-information theorists). Since the sequence is exchangeable, de Finetti’s Theorem shows that the fraction of red balls W_n = R_n/(R_n + B_n) converges almost surely to a random variable W, and the limit of the formula above shows that the limit is a beta distribution with parameters (a,b):

f_W(w) = \frac{\Gamma(a+b)}{\Gamma(a) \Gamma(b)} w^{a-1} (1 - w)^{b-1}

A more general process is the Friedman urn process, in which you add \alpha balls of the same color you drew and \beta balls of the opposite color. If \alpha > \beta > 0 then Freedman (different spelling, different guy) showed that the proportion of red balls tends almost surely to 1/2. This happens because the evolution ends up looking like a symmetric two-state Markov chain, which has (1/2, 1/2) as its stationary distribution. Note here that the limiting fraction is almost surely constant, as opposed to there being a limiting distribution, as in the Polya process.

Let’s look at a special case where instead of adding a ball of the same color that you drew, you only add a ball of the opposite color (which is a Friedman process with parameters (0,1)). Freedman’s result doesn’t apply here, but Kingman has a nice paper (which I am reading now) relating this process to a third process: the OK Corral process.

In the OK Corral process, say we start with (c,d) good and bad cowboys. We choose one cowboy uniformly at random and then he kills a cowboy on the opposite side. This process continues until one side has all been shot. This process is precisely the time reversal of the special Friedman urn process above. If we let S_N denote the number of surviving cowboys after the process terminates when we start with (N,N), Kingman proves that

V_N = \frac{3S_N^4}{2N^3}

converges to a gamma distribution with parameter 1/2:

f_V(v) = v^{-1/2} e^{-v}/\Gamma(1/2)

The weird thing about this is that the scaling is N^{3/4} to get an asymptotic distribution.

Kingman and Volkov extend the analysis by embedding the urns into birth processes, which is another technique for balls-into-bins with feedback of urns with reinforcement. But that’s another story for another time (but maybe not another blog post, this one took a bit longer than I expected).


2 thoughts on “From Polya urns to the OK Corral

  1. In the Polya urn process, the unconditional probability P{X_n = 0} is a/(a+b), isn’t it, even though the urn has R_n red balls and B_n black balls? For example, after one draw, the urn contains a+1 red balls with probability a/(a+b), and b+1 black balls with probability b/(a+b), and so the probability of a red ball on the second draw is

    [(a+1)/(a+b+1)]a/(a+b) + [a/(a+b+1)]b/(a+b)

    = a/(a+b).

    I have three bags full of wool

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.