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

  • $\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$ Jul 7 '15 at 19:29
  • $\begingroup$ Probably, it's enough to say that $P\{\text{red ball is drawn}|\mathcal{F_n}\}=X_n$. $\endgroup$
    – d.k.o.
    Jul 7 '15 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$ 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}$

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$ Jul 7 '15 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
    Jul 7 '15 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$ Jul 7 '15 at 19:25
  • $\begingroup$ I mean I misread your answer of course. $\endgroup$ Jul 7 '15 at 19:35
  • $\begingroup$ @SergeyZykov I think we can deduce that $X_n$ is Markov $\endgroup$
    – 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$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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