# Polya's urn as a counterexample for the Kolmogorov 0-1 law

Consider a simple formulation for the Polya urn model. An urn contains two balls at time 0, one is white and the other is black. At time $$n\in\mathbb{N}$$, one of the balls is chosen uniformly at random. Another ball of the same color is put into the urn. Let $$X_n$$ be the number of black balls at time $$n$$. My task is to:

1. Give a formal description of the process.
2. Show that $$\lim_{n\to\infty}\frac{X_n}{n+2}$$ exists almost surely and is uniformly random in $$(0,1)$$.
3. Show that $$A:=\left\{\lim_{n\to\infty}\frac{X_n}{n+2}>\frac12\right\}\in\mathcal{T}$$, i.e. $$A$$ is a tail event. Moreover, show that $$P(A)=\frac12$$.

Point 3 is easy to show in my opinion and the last part follows simply by the uniformity of the random variable. I am unsure how to prove 2 and also what is meant exactly by "formal description of the process". Is it enough to give the conditional probabilities of the form $$P(X_{n+1}=k|X_n=l)$$? I understand the proof of almost sure convergence follows easily from the martingale convergence theorem. Is there any other way to prove it without using martingales?

• math.stackexchange.com/questions/1125320/…
– user140541
Commented Nov 22, 2021 at 20:56
• Thank you for the comment and also for the answer. I am specifically interested if there is a proof of the a.s. convergence without using martingale theory. Commented Nov 23, 2021 at 9:51

You need to use a martingale structure to show the almost sure convergence. Specifically, $$\mathsf{E}\!\left[\frac{B_n}{n+2}\mid B_{n-1}\right]=\frac{B_{n-1}}{n+2}\left(1-\frac{B_{n-1}}{n+1}\right)+\frac{B_{n-1}+1}{n+2}\frac{B_{n-1}}{n+1}=\frac{B_{n-1}}{n+1},$$ where $$B_n$$ is the number of black balls after $$n$$ steps ($$X_n$$ in your notation). That is, $$B_n/(n+2)$$ is a bounded martingale (w.r.t. the natural filtration), and thus, it converges almost surely.
As for the asymptotic distribution note that if $$\hat{B}_n$$ denote the number of draws of black balls in $$n$$ trials, then $$B_n=\hat{B}_n+1$$, and $$\mathsf{P}(\hat{B}_n=k)=\frac{k!(n-k)!}{(n+1)!}\times \binom{n}{k}=\frac{1}{n}.$$ Thus, for $$x\in [0,1]$$, $$\mathsf{P}(\hat{B}_n\le nx)=\sum_{k=0}^{\lfloor nx\rfloor}\frac{1}{n}=\frac{\lfloor nx\rfloor}{n}\to x$$ as $$n\to\infty$$. Finally, $$\frac{B_n}{n+2}=\frac{n}{n+2}\times \frac{\hat{B}_n}{n}+\frac{1}{n+2}\xrightarrow{d} \text{U}[0,1].$$