MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $g, r, a, b$ be positive integers. In Friedman's urn model we have an urn with $r$ red and $g$ green balls in it. In each step we take one ball out of urn, register its color and return it to the urn. Additionally, we put $a$ more balls of this color and $b$ more balls of the other color.

Let $X_n$ be the relative amount of green balls in the box after $n$-th step. It can be proven (e.g. Richard Durrett, Probability: Theory and Examples, pages 254-255) that $$\lim_{n\to\infty}X_n = \frac12\quad\text{a.e.}$$ If one thinks about this statement for a second it would most probably strike him as extremely counter-intuitive. The proof cited above make use of square integrable martingales, and unfortunately doesn't seem to give intuitive explanation of this phenomena. I'm looking for an explanation which would explain on some heuristic level why this result is in some sense logical. An idea for more intuitive proof would also definitely be helpful.

I would also like to note that if we take $b=0$ the model becomes well-known Polya-Eggenberger urn model for which we have $$\lim_{n\to\infty}X_n\sim B\left(\frac{g}{a}, \frac{r}{a}\right).$$

share|cite|improve this question
Why do you register the color of the ball you took out? – Mariano Suárez-Alvarez Jul 9 '10 at 16:36
@Mariano: in order to determine which color gets a balls and which color gets b balls. – Qiaochu Yuan Jul 9 '10 at 17:55
up vote 4 down vote accepted

You might be interested in the article by David A. Freedman on Friedman's urn. He reports a simple and intuitive proof due to Ornstein, which only uses the strong law of large numbers.

In his notation the urn contains $W_n$ white balls and $B_n$ black balls at time $n$, $a$ and $b$ have the same meaning as in the question.

D. Ornstein has obtained this very intuitive proof that $(W_n + B_n)^{-1}W_n$ converges to $1/2$ with probability 1 for $b > 0$. Suppose first $a > b$. If $0 \leq x \leq 1$ and $$\mathbb P\left\{\limsup \frac{W_n}{W_n + B_n} \leq x\right\} = 1,$$ by an easy variation of the Strong Law, with probability 1, in $N$ trials there will be at most $Nx + o(N)$ drawings of a white ball; so at least $N(1 - x) - o(N)$ drawings of black. Therefore, with probability 1, $\limsup (W_n+ B_n)^{-1}B_n$ is bounded above by $$\lim\limits_{N\to\infty}\frac{a[Nx + o(N)] + b[N(1 - x) - o(N)]}{N(a + b)}=\frac{b+(a-b)x}{a+b}.$$ Starting with $x = 1$ and iterating, $$\mathbb P\left\{\limsup \frac{W_n}{W_n + B_n} \leq \frac{1}{2}\right\} = 1$$ follows. Interchange white and black to complete the proof for $a > b$. If $a < b$, and $$\mathbb P\{\limsup (W_n + B_n)^{-1}W_n \leq x\} = 1,$$ then a similar argument shows $$\mathbb P\left\{\limsup\frac{B_n}{W_n + B_n} < \frac{a+(b-a)x}{a + b}\right\}=1$$ The argument proceeds as before, except both colors must be considered simultaneously.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.