0
$\begingroup$

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))

Thank you for your help in advance!

$\endgroup$
6
  • $\begingroup$ 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$. $\endgroup$
    – Pierre PC
    Commented Jun 9, 2020 at 23:47
  • $\begingroup$ @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? $\endgroup$ Commented Jun 9, 2020 at 23:51
  • $\begingroup$ @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! $\endgroup$ Commented Jun 9, 2020 at 23:52
  • 1
    $\begingroup$ $\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. $\endgroup$
    – Pierre PC
    Commented Jun 10, 2020 at 0:47
  • 2
    $\begingroup$ In any case, I don't think this question is research level, and I would advise you to post it on math.SE instead. $\endgroup$
    – Pierre PC
    Commented Jun 10, 2020 at 0:48

1 Answer 1

2
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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