Prove that the sequence is a Martingale.

Question

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.

Answer 1

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