From Probability with Martingales:

enter image description here

I chose $\mathscr F_n = \sigma(B_1, B_2, ..., B_n)$.

My argument assumes that $E[M_n | \mathscr F_{n-1}] = E[M_n | B_{n-1}]$. I was able to show that $M_{n-1} = E[M_n | B_{n-1}]$.

How does one show that $E[M_n | \mathscr F_{n-1}] = E[M_n | B_{n-1}]$ or $E[M_n | \mathscr F_{n-1}] = M_{n-1}$?

Any chance we have something like $B_n \le B_{n+1}$?

If not, might it help if I define $B_n = X_1 + ... + X_n$ where $X_i$'s are iid Bernoulli conditioned on some probability p (or $\Theta$?) and then use a similar argument to the one here?

  • $\begingroup$ Can you prove that $(B_n)$ is a Markov chain ? In this case, the equality you want to prove is easy to derive. $\endgroup$ Commented Dec 27, 2015 at 10:28
  • $\begingroup$ @StéphaneLaurent You mean prove that $P(B_n = k_n | B_1 = k_1, ..., B_{n-1} = k_{n-1}) = P(B_n = k_n | B_{n-1} = k_{n-1})$ for $k_i \in \{0, 1, ..., n\}$ like here ? $\endgroup$
    – BCLC
    Commented Dec 27, 2015 at 10:40

1 Answer 1


Intuition: this problem illustrates a fairly common strategy for constructing a martingale. First, a collection of random variables $(B_n)_{n\geq 1}$ is generated sequentially, with $B_n$ defined in terms of $B_{n-1}$. The method of construction ensures that, though they are not independent, the dependence structure is relatively simple in that they form a Markov chain. However, typically the conditional expectation requirement for a martingale is not satisfied yet, so we seek functions $f_n$ such that the random variables $M_n=f_n(B_n)$ do satisfy the martingale condition. In this case $f_n(x)=\frac{x+1}{n+2}$.

Showing that we have a Markov chain: To show that $(B_n)_{n\geq 1}$ is a markov chain, we want to show that $$P(B_n = k_n | B_1 = k_1, ..., B_{n-1} = k_{n-1}) = P(B_n = k_n | B_{n-1} = k_{n-1})$$ where the numbers $k_i$ are non-decreasing with $k_i\leq i$.

If we condition on $B_1 = k_1, ..., B_{n-1} = k_{n-1}$ then we know that there are $k_{n-1}+1$ black balls in the urn (out of a total of $n+1$ balls) just after time $n-1$. So the conditional probability that $B_n=k_n$ is either $1-\frac{k_{n-1}+1}{n+1}$ (if $k_n=k_{n-1}$ i.e. white ball chosen) or $\frac{k_{n-1}+1}{n+1}$ (if $k_n=k_{n-1}+1$ i.e. black ball chosen). Now, you might ask, what about our knowledge of $B_1$,$B_2$,...,$B_{n-2}$? Well, yes we know them, but their values don't affect the conditional probabilties we just computed. This is just a consequence of the way the sequence $(B_n)_{n\geq 1}$ is constructed.

If we condition only on $B_{n-1} = k_{n-1}$ then... we obtain exactly the same probabilities! The probabilities are the same because $k_1,...,k_{n-2}$ are irrelevant once we know $k_{n-1}$. So $(B_n)_{n\geq 1}$ is indeed a Markov chain.

Further information: can be found in many places online, for example this document gives a good analysis of Polya's urn.


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.