# Show rigorously that Pólya urn describes a martingale

We work with the famous Pólya urn problem. At the beginning one has $r$ red balls and $b$ blue ball in the urn. After each draw we add $t$ balls of the same color in the urn.

$(X_n)_{n \in \mathbb N}$ is the share of red balls in the urn after $n$-th draw. I need to show that $(X_n)_{n \in \mathbb N}$ is a martingale rigorously (i.e. using only theorems and without imagination power based on real world experience).

I select a filtration $(\mathcal F_n)_{n \in \mathbb N}=\sigma (X_1,...,X_n)$.

I need to show that $E(X_{n+1}|\sigma (X_1,...,X_n))=X_n$

$E(X_{n+1}|\sigma (X_1,...,X_n))=E(\frac{lX_n+S}{l+t}|\sigma (X_1,...,X_n))=\frac{lX_n}{l+t}+\frac{E(S|\sigma (X_1,...,X_n))}{l+t}$ where $l$ is the number of balls in the urn after $n$-th draw and $S$ is the number of balls added after $n+1$-th draw (random variable), the last step is possible because $X_n$ is $\sigma (X_1,...,X_n)$ measurable.

Further $E(S|\sigma (X_1,...,X_n))=tE(\mathcal I\{$read ball at $n+1$-th draw$\}|\sigma (X_1,...,X_n))$

How do I take it from here?

Please note that I saw The Pólya urn model describes a martingale, and I do not consider it rigorous enough.

Actually, you may want to account for the underlying random process...

Let $$\{U_n\}_{n=0}^\infty$$ be a sequence of i.i.d. uniform random variables on $$[0,1]$$. Let $$r_n$$ denote the number of red balls at time $$n$$ and $$l_n=r+g+t\cdot n$$. Then

$$X_n=\frac{r_n}{l_n}\quad\text{and}\quad r_{n+1}=r_n1\{U_{n+1}>X_n\}+(r_n+t)1\{U_{n+1}\le X_n\}.$$

Letting $$\mathcal{F}_n:=\sigma(U_1,\dots,U_n)$$, one gets

\begin{align} \mathsf{E}[X_{n+1}\mid\mathcal{F}_n]&=\mathsf{E}\!\left[\frac{r_n}{l_n+t}\times 1\{U_{n+1}>X_n\}+\frac{r_n+t}{l_n+t}\times 1\{U_{n+1}\le X_n\} \mid\mathcal{F}_n\right] \\ &=\frac{r_n}{l_n+t}\mathsf{E}\!\left[1\{U_{n+1}>X_n\}\mid\mathcal{F}_n\right]+ \frac{r_n+t}{l_n+t}\mathsf{E}\left[1\{U_{n+1}\le X_n\}\mid\mathcal{F}_n\right] \\ &=\frac{r_n}{l_n+t}\left(1-\frac{r_n}{l_n}\right)+ \frac{r_n+t}{l_n+t}\left(\frac{r_n}{l_n}\right)=X_n \end{align}

because $$r_n$$ and $$X_n$$ are $$\mathcal{F}_n$$-measurable, and $$U_{n+1}$$ is independent of $$\mathcal{F}_n$$.

• Most likely the answer is correct, but I can not appreciate it because I am not familiar with the (functional) monotone class theorem. It just has not been covered in the course yet. But according to the course I am supposed to be able to solve the problem. So I guess I am expected to solve it without the theorem. – Sergey Zykov Jul 7 '15 at 19:29
• Probably, it's enough to say that $P\{\text{red ball is drawn}|\mathcal{F_n}\}=X_n$. – d.k.o. Jul 7 '15 at 20:00
• But then we are with the second solution to this question, and my comment to the solution (see below) applies. – Sergey Zykov Jul 7 '15 at 20:06

Firstly if you want to prove it properly you need to show the process is adapdet and integrable. I will skip this.

For the remaining property set the following:

$l_n= b+r+ n t$ the number of balls prior the n+1th extraction; $A_n$ the event: the n+1th extraction is red.

Then $X_n$ can be expressed recursively by $X_{n+1}= \frac{l_n X_n +t}{l_{n+1}} I_{A_n} + \frac{l_n X_n }{l_{n+1}} I_{A_n^c}$

$$E[X_{n+1}|F_n] = E[X_{n+1} I_{A_n}|F_n] + E[X_{n+1} I_{A_n^c}|F_n] = E[\frac{l_n X_n +t}{l_{n+1}} I_{A_n}|F_n] + E[\frac{l_n X_n }{l_{n+1}} I_{A_n^c}|F_n]= \frac{l_n X_n +t}{l_{n+1}} X_n + \frac{l_n X_n }{l_{n+1}} (1-X_n)=X_n \frac{l_n+t}{l_{n+1}}=X_n$$

• @Komo It is not clear to me what happens to $E[I_{A_n}|F_n]$ at some point in your last equation. It looks like you think that $E[I_{A_n}|F_n]=1$, why? – Sergey Zykov Jul 7 '15 at 18:46
• I dont see the whole expression on my phone (why? I will query with Admins). But $E[I_{A_n}|F_n]=X_n$ that is what the process models! – Kolmo Jul 7 '15 at 19:16
• Sorry, I indeed misread your equation. You do say that $E[I_{A_n}|F_n]=X_n$, but then I have another question, why $E[I_{A_n}|F_n]=X_n$. To prove it I would need to show that $\int_{A}I_{A_n}dP=\int_{A}X_ndP, \forall A \in F_n$. How can one show that? – Sergey Zykov Jul 7 '15 at 19:25
• I mean I misread your answer of course. – Sergey Zykov Jul 7 '15 at 19:35
• @SergeyZykov I think we can deduce that $X_n$ is Markov – BCLC Dec 27 '15 at 12:37

Since I'm new here, I cannot make comments yet. But, answering @Sergey and @BCLC, we can see that $$I_{A_n} = 1, \mbox{with probability} X_n; \quad 0, \mbox{with probability } (1-X_n)$$

So, given $F_n$ (loosely, given $X_n$) we can see that $I_{A_n} \sim Bin(1,X_n)$.

Therefore, $E[I_{A_n}|F_n]=1 \cdot X_n + 0 \cdot (1-X_n) = X_n$.

Coming a little late to the party, I would operate closely to what @d.k.o did with the underlying random process, only I will prove that: $$E(X_{n+1}|\sigma (X_1,...,X_n))=X_n$$ directly without using the lemma he quotes.

Using your notations, let $$F_n = \sigma (X_1,...,X_n)$$ and $$\{U_n\}_{n=0}^\infty$$ be a sequence of i.i.d. uniform random variables on $$[0,1]$$ and define: $$Y_n = 1\{U_n \leq X_{n-1}\}$$ that is 1 if the ball drawn in the n-th trial is red, and zero otherwise.

We have $$X_0 = \frac{r}{r + b}$$, and: $$X_n = \frac{r + t.\sum_{i=1}^{n} Y_i}{r + b + t.n}$$

First, we have that $$\forall i \in [1, 2,..., n]: Y_i \in \sigma(X_1, X_2, ..., X_n) = F_n$$.

So one gets: $$E(X_{n+1}|F_n)= E(\frac{r + t.\sum_{i=1}^{n+1} Y_i}{r + b + t.(n + 1)}|F_n)=\frac{r + t.\sum_{i=1}^{n} Y_i}{r + b + t.(n+1)} + \frac{t.E(Y_{n+1}|F_n)}{r+b+t.(n+1)}$$.

Now we want to prove that: $$E(Y_{n+1}|F_n) = X_n$$.

We're gonna prove that $$\forall B \in F_n$$: $$E(Y_{n+1}.\mathbf{1}_ {B}) = E(X_n.\mathbf{1}_ {B})$$, which is a caracterisation of the conditionnal expectation of a random variable with respect to a given sigma algebra.

First let's consider: $$W_n = \{(w_1, w_2,..., w_n): \forall i\in [1,...,n], w_i\in \{0,1\} \}$$ and define:

$$\forall w\in W_n : B_w = \{Y_1=w_1, Y_2=w_2,...,Y_n=w_n \}$$. Note that $$\forall w_1 \neq w_2 , B_{w_1} \bigcap B_{w_2} = \varnothing$$

$$\forall w\in W_n$$:

$$Y_{n+1}.\mathbf{1}_ {B_w} = 1\{U_{n+1} \leq \frac{r + t.\sum_{i=1}^{n} Y_i}{r + b + t.n}\}.1\{Y_1=w_1, Y_2=w_2,...,Y_n=w_n \} = 1\{U_{n+1} \leq \frac{r + t.\sum_{i=1}^{n} w_i}{r + b + t.n}\} = 1\{U_{n+1} \leq p_w \}$$

So $$Y_{n+1}.\mathbf{1}_ {B_w}$$ follows a binomial law of parameter: $$p_w = \frac{r + t.\sum_{i=1}^{n} w_i}{r + b + t.n}$$

$$\implies E(Y_{n+1}.\mathbf{1}_ {B_w}) = \frac{r + t.\sum_{i=1}^{n} w_i}{r + b + t.n} = E(\frac{r + t.\sum_{i=1}^{n} Y_i}{r + b + t.n}.1\{Y_1=w_1, Y_2=w_2,...,Y_n=w_n \}) = E(X_n.\mathbf{1}_ {B_w})$$

Now since $$\{B_w, w\in W_n\}$$ is the set of all the smallest elements of $$F_n = \sigma(X_1,X_2,...,X_n)$$, for any $$B\in F_n$$ there are $$(w_1,w_2,...,w_p) \in W_n$$ sucht that: $$B = \bigcup_{i=1}^{p} B_{w_i} , B_{w_i}\bigcap B_{w_j} = \varnothing, \forall i \neq j.$$

So one gets: $$\mathbf{1}_ {B} = \sum_{i = 1}^p \mathbf{1}_ {B_{w_i}}$$ and by linearity of the expectation:

$$E(Y_{n+1}.\mathbf{1}_ {B}) = \sum_{i=1}^p E(Y_{n+1}.\mathbf{1}_ {B_{w_i}}) = \sum_{i=1}^p E(X_n.\mathbf{1}_ {B_{w_i}}) = E(X_n.\mathbf{1}_ {B})$$

So we get that:

$$E(Y_{n+1}|F_n) = X_n$$

and plugging it in the first computation gives:

$$E(X_{n+1}|F_n)= E(\frac{r + t.\sum_{i=1}^{n+1} Y_i}{r + b + t.(n + 1)}|F_n)=\frac{r + t.\sum_{i=1}^{n} Y_i}{r + b + t.(n+1)} + \frac{t.X_n}{r+b+t.(n+1)} = \frac{r + b + t.n}{r + b + t.(n+1)}X_n + \frac{t.X_n}{r+b+t.(n+1)} = X_n$$