Polya's urn (martingale)

Suppose you have an urn containing one red ball and one green ball. You draw one at random; if the ball is red, put it back in the urn with an additional red ball , otherwise put it back and add a green ball . Repeat this procedure and let the random variable $X_n$ be the number of red balls in the urn after n draws. Let $Y_n=\frac{1}{n+2}X_n$. Find $\mathbb{\mathbb{\textrm{E}}}\left(Y_{n}\right)$ and prove that $Y_n$ is a martingale with respect to $X_n$.

MY ATTEMPT:

We have $\mathbb{\mathbb{\textrm{E}}}\left(\left.X_{n+1}\right|X_{n}\right)=X_{n}+\dfrac{X_{n}}{n+2}=\dfrac{n+3}{n+2}X_{n}$, so

$\mathbb{\mathbb{\textrm{E}}}\left(\left.Y_{n+1}\right|X_{n}\right)=\dfrac{1}{n+3}\mathbb{\mathbb{\textrm{E}}}\left(\left.X_{n+1}\right|X_{n}\right)=\dfrac{1}{n+3}\cdot\dfrac{n+3}{n+2}X_{n}=\dfrac{1}{n+2}\cdot X_{n}=Y_{n}$

It's ok?

And, can you help me to find $\mathbb{\mathbb{\textrm{E}}}\left(Y_{n}\right)$?

• The martingale property is $E(Y_{n+1}\mid X_0,\dots, X_n)=Y_n$, not $E(Y_{n+1}\mid X_n)=Y_n$.
– user940
Nov 22, 2015 at 16:54
• @ByronSchmuland But above calculations stay the same. In particular, $E[R_{n+1}|X_n,...,X_1]=X_n/(n+2).$
– ir7
Nov 23, 2015 at 4:28
• @ir7 So OP has to prove $Y_n$ has Markov property?
– BCLC
Dec 27, 2015 at 12:32
• @BCLC It's already done, but not said explicitly. The way to prove Markov property is indeed to calculate the conditional expectation on all variables (history). If we get lucky and the expression we obtain as result is only dependent on the latest variable, then we are done. The two conditional expectations (one on all variables, the other on the latest) are equal.
– ir7
Dec 30, 2015 at 13:15
• @ir7 How to go about showing $E[R_{n+1} | X_n, ..., X_1] = \frac{X_n}{n+2}$? If $| X_n$ only, then fine. But with all the others...?
– BCLC
Dec 30, 2015 at 21:57

Looks good, as indeed $$X_{n+1} = X_n + R_{n+1},$$ where $R_{i}$ denotes the indicator variable that takes value $1$ if color of the $i$-th ball extracted is red, and $0$ if green. By definition we have that the urn contains $X_n$ red and $n+2-X_n$ green balls after $n$ extractions. Then the conditional probability given $X_n$ of a red ball on the $n+1$-th extraction (equal to the conditional expectation given $X_n$ of $R_{n+1}$ that we need) is $$\frac{X_n}{n+2}=Y_n.$$ We also observe that $$X_n = 1+\sum_{i=1}^n R_i.$$ Taking expectation we get: $$\mathbf{E}\left[ X_n\right] = 1+\sum_{i=1}^n \mathbf{E}\left[ R_i\right].$$ As all $R_i$ have the same distribution as $R_1$, we get: $$\mathbf{E}\left[ R_i\right] = \mathbf{E}\left[ R_1\right] =\frac{1}{2},$$ for all $i\in \{1,\ldots , n\}$. Our indicator variables have the same distribution due to the fact that the sequence of variables $R_1,\ldots, R_n$ is exchangeable, as its joint distribution
$$\mathbf{P}\left(R_1=c_1,\ldots, R_n=c_n\right)$$ $$= \mathbf{P}\left(R_1=c_1\right)\mathbf{P}\left(R_2=c_2 | R_1=c_1\right) \ldots\mathbf{P}\left(R_n=c_n | R_1=c_1,\ldots, R_{n-1}=c_{n-1}\right)$$ $$= \frac{c!(n-c)!}{(n+1)!}$$ depends on $c_1,\ldots,c_n$ only through the number of red balls $c$, $c=c_1+\ldots + c_n$.

To conclude, we have $\mathbf{E}[X_n]=(n+2)/2$, so $$\mathbf{E}[Y_n]=1/2.$$ This can also be seen directly as we already know that $Y_n$ is a martingale, so (proof here) $$\mathbf{E}[Y_n]=\mathbf{E}[Y_{n-1}]=\ldots = \mathbf{E}[Y_1]=1/2.$$

• Then $\mathbf{E}\left[ X_n\right] = \frac{n}{2}$. And therefore, $\mathbf{E}\left[ Y_n\right] = \frac{1}{n+2} \frac{n}{2}$. It's ok?? Nov 21, 2015 at 11:44
• Sorry, I think I forgot the existing red ball in the urn.
– ir7
Nov 23, 2015 at 3:25
• Also, note Byron Schmuland's comment. But the calculations look the same whether conditioning on X_n only or on all X_n,...,X_1 (unless I'm missing something).
– ir7
Nov 23, 2015 at 3:34
• How do the $R_i$'s have the same distribution?
– BCLC
Dec 27, 2015 at 12:33
• @BCLC For an exchangeable vector, however one permutes its components, we get new vectors with exactly the same JOINT pdf. So, no matter which variable sits, say, in the first position we'll calculate its (marginal) pdf by integrating that common joint pdf in exactly the same way.
– ir7
Dec 30, 2015 at 12:56