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.


4 Answers 4


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}$

This leads to the following:

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

  • $\begingroup$ @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? $\endgroup$
    – zesy
    Commented Jul 7, 2015 at 18:46
  • $\begingroup$ 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! $\endgroup$
    – Kolmo
    Commented Jul 7, 2015 at 19:16
  • 2
    $\begingroup$ 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? $\endgroup$
    – zesy
    Commented Jul 7, 2015 at 19:25
  • $\begingroup$ I mean I misread your answer of course. $\endgroup$
    – zesy
    Commented Jul 7, 2015 at 19:35
  • $\begingroup$ @SergeyZykov I think we can deduce that $X_n$ is Markov $\endgroup$
    – BCLC
    Commented Dec 27, 2015 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$$


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

  • $\begingroup$ 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. $\endgroup$
    – zesy
    Commented Jul 7, 2015 at 19:29
  • $\begingroup$ Probably, it's enough to say that $P\{\text{red ball is drawn}|\mathcal{F_n}\}=X_n$. $\endgroup$
    – user140541
    Commented Jul 7, 2015 at 20:00
  • $\begingroup$ But then we are with the second solution to this question, and my comment to the solution (see below) applies. $\endgroup$
    – zesy
    Commented Jul 7, 2015 at 20:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .