# Prove that the sequence is a Martingale.

Consider an urn that initially contains b black balls and w white balls. At every iteration, we draw a random ball is chosen and the chosen ball is replaced by c > 1 balls of the same color. Let $$X_i$$ denote the fraction of black balls after i-th draw. Prove that $$X_0$$, $$X_1$$, . . . is a martingale.

Let $$d=c-1$$. Let $$k=b+w$$ be the initial number of balls. Then $$X_{n}(k+dn)$$ is the number of black balls at the $$n$$-th step. Therefore, \begin{align*} \mathbb{E}\left[X_{n+1}\mid X_{n}\right] & =X_{n}\frac{X_{n}\left(k+dn\right)+d}{k+d\left(n+1\right)}+\left(1-X_{n}\right)\frac{X_{n}\left(k+dn\right)}{k+d\left(n+1\right)}\\ & =X_{n}\left[\frac{X_{n}\left(k+dn\right)}{k+d\left(n+1\right)}+\frac{d}{k+d\left(n+1\right)}\right]+\left(1-X_{n}\right)\frac{X_{n}\left(k+dn\right)}{k+d\left(n+1\right)}\\ & =X_{n}\left[\frac{d}{k+d\left(n+1\right)}+\frac{\left(k+dn\right)}{k+d\left(n+1\right)}\right]\\ & =X_{n}. \end{align*}
• A little doubt, I thought we have to prove that E[$X_{n+1}$|$X_n$,$X_{n-1}$,...,$X_1$] = $X_n$, Why haven't you considered the previous $X_i$'s? Am I missing something? I asked cause we have been taught that way. – mskanyal Apr 29 '19 at 3:14
• In our case, $\mathbb{E}[X_{n+1} \mid X_n, X_{n-1}, \ldots, X_0] = \mathbb{E}[X_{n+1} \mid X_n]$ since you don't get any additional information from knowing the previous states. In particular, this is a Markov chain. – parsiad Apr 29 '19 at 3:45