Polya’s urn, martingale, CLT

A problem described here

what do you expect to happen if you had 2 urns with a ball in each one…. and you placed balls in them…. choosing an urn with a probability proportional to the number of balls in each urn…..

intuitively, you’d expect a rich getting richer kind of thing….. or those with more balls getting even ballsier…. [see extreme sports.... those ppl are crazy... and get crazier] but the amazing thing is that you get a uniform distribution….. it’s not even a distribution that peaks at the two ends where there’s 1 ball and n-1 balls in the other….

Well, it’s not that counter-intuitive. Certainly, if you begin with exactly 1 ball in each urn, you end up with a uniform distribution on all outcomes, but the uniformity is kind of an artifact. In fact, the proportion of total balls in one designated urn is a martingale process, which means the proportion of balls at any number of times steps later is expected to be the same as the starting proportion. So, if you do not start with an equal number of balls in the two urns, there is no way that the long-run outcome will be uniformly distributed across the possibilities because that would give a mean proportion value of 1/2.

Furthermore, this means that indeed there is a rich getting richer “kind of thing” going on, if you deviate from equal proportion by chance. This is a weak effect that happens when the balls are few, but it doesn’t mean that the half-half case is somehow a counter-intuitive stable system. The paths that deviate early will indeed tend to go to the rails. It’s just that there are so many central paths that you aren’t likely to deviate proportionally unless it happens early.

What’s more interesting is that there are so many central paths. If you began with 2 and 2 balls, or 10 and 10 balls, you don’t get uniform outcomes, but a centrally peaked distribution around equal proportions. Indeed, if the number of balls is large, then addition of balls to urns one at a time doesn’t even move the drawing probabilities given by existing balls, and so it is reasonable to expect something like the central limit theorem to kick in.

So this is a case of deviation instability fighting with central tendencies of large numbers. To see this, keep the total number of balls the same, and move balls from the urn not chosen to the urn chosen, instead of adding balls to the urn chosen (and hence remove the latter cause from the “fight”), then it will clearly go to the rails.

No comments yet. Be the first.

Leave a reply