# Martingale convergence theorem in Polya's urn

I want to get checked if my attempt is okay.

First off, let me shortly describe what Polya's urn is:

A certain urn initially contains a red and a blue ball. We now repeatedly do the following : we (uniformly at random) pick a ball from the urn, and then put it back in together with an additional ball of the same colour. Let $$X_n$$ denote the number of red balls and $$Y_n$$ denote the fraction of red balls after we’ve done this $$n$$ times, i.e. $$Y_n = \frac{X_n}{n+2}.$$

And the following is my attempt so far. (let me assume that $$Y_n$$ is a martingale without showing it)

\begin{align*} X_{n+1} &= X_n + 1_{\{\text{n+1^{th} ball is red}\}} \\ X_n &= 1 + \sum_{1\leq i\leq n}1_{\{\text{i^{th} ball is red}\}} \\ \to EX_n &= 1 + \sum_{1\leq i\leq n}E[1_{\{\text{i^{th} ball is red}\}}] = 1 + nE[1_{\{\text{i^{th} ball is red}\}}] = 1 + \frac{n}{2} \end{align*} since the indicator function take only values $$0$$ or $$1$$ with the same probability here (picking either ball has the same probability).

Thus, $$EX_n = 1 + \frac{n}{2} = \frac{n+2}{2}$$, so $$EY_n = \frac{1}{2}$$.

So now we know the expectation of $$Y_n$$, but is it enough to say that $$Y$$ is the uniform distribution on $$[0,1]$$?

(where $$Y_n\xrightarrow[]{a.s.}Y$$ (Martingale convergence theorem))

• If you know that $Y_n$ is a martingale, then obviously $\mathbb E[Y_n]=\mathbb E[Y_0]=1/2$. You're more or less proving that $Y_n$ is a martingale again. Also no, it is not enough, $Z_n:=1/2$ is a martingale with expectation $1/2$. Commented Jun 9, 2020 at 23:47
• @PierrePC Thanks for letting me know. But how did you derive that $\mathbb{E}[Y_n] = \mathbb{E}[Y_0] = 1/2$ by the fact that $Y_n$ is a martingale? Commented Jun 9, 2020 at 23:51
• @PierrePC Also can you explain what I should show/prove in order to show that $Y$ is uniformly distributed on $[0,1]$? Thank you in advance! Commented Jun 9, 2020 at 23:52
• $\mathbb E[Y_{n+1}] = \mathbb E[\mathbb E[Y_{n+1}|\mathcal F_n]] = \mathbb E[Y_n] = \cdots = \mathbb E[Y_0]$. About the uniform distribution of $Y$ in $[0,1]$, I'd have to think about it but I would use very different methods. Commented Jun 10, 2020 at 0:47
• In any case, I don't think this question is research level, and I would advise you to post it on math.SE instead. Commented Jun 10, 2020 at 0:48

The answer is yes, the distribution of $$Y_n$$ converges to the uniform distribution on $$[0,1]$$.
More generally, if we initially have $$r$$ red and $$b$$ blue balls in the urn, then the distribution of the proportion of the red balls in the urn converges to the beta distribution with parameters $$r,b$$; see e.g. Section 4.
Moreover, in your case of $$r=b=1$$, letting $$p_{n,k}:=P(X_n=k),$$ it is easy to check directly by induction on $$n$$, using the recursion $$p_{n,k}=p_{n-1,k}\frac{n+1-k}{n+1}+p_{n-1,k-1}\frac{k-1}{n+1}$$ for natural $$n$$ and $$k$$, that $$p_{n,k}=\frac1{n+1}\,1\big\{k\in\{1,\dots,n+1\}\big\}$$ for $$n=0,1,\dots$$; that is, $$X_n$$ has the discrete uniform distribution on the set $$\{1,\dots,n+1\}$$.
Therefore, it is clear that the distribution of $$Y_n=\frac{X_n}{n+2}$$ converges to the uniform distribution on $$[0,1]$$.