# Relationship Between Martingales and Picking Balls from a Hat

Using Martingales, am trying to prove that the ratio of balls in Polya's Urn (https://en.wikipedia.org/wiki/P%C3%B3lya_urn_model) approaches a Beta Distribution as the number of turns go to infinity. I found a previous question that showed this Polya's urn model - limit distribution , but I want to try and repeat this analysis by myself.

In Polya's Urn, we start with some number of Red Balls and some number of Blue Balls. At each turn, we randomly draw a ball (each ball has equal probability of being selected) and then put it back - along with another ball of the same color.

Suppose:

• At t=0, there are $$m$$ red balls and $$n$$ blue balls
• At t=t, $$k$$ red balls have been chosen

Part 1: In my previous question (Probability of Drawing Balls from a Hat with Changing Number of Balls), I showed that he joint probability of having $$m+k$$ red balls at turn $$t$$ is:

$$P(R_t = m+k) = \binom{t}{k} \cdot \prod_{i=0}^{k-1} \frac{m+i}{m+n+i} \cdot \prod_{j=0}^{t-k-1} \frac{n+j}{m+n+k+j}$$

Part 2: I can also define the ratio of balls at the $$t^{th}$$ turn:

$$R_t = \frac{m+k}{m+n+t}$$

And using this same logic, I can also write an expression for the Expected Value of the Ratio at the $$t^{th}$$ turn:

• For the t+1 turn, we have two possibilities:
• Choose a red ball: probability $$\frac{m+k}{m+n+t}$$, resulting ratio $$\frac{m+k+1}{m+n+t+1}$$
• Choose a blue ball: probability $$\frac{n+t-k}{m+n+t}$$, resulting ratio $$\frac{m+k}{m+n+t+1}$$

The expected ratio at $$t+1$$ given $$k$$ red balls were chosen up to turn $$t$$ is:

$$E(R_{t+1} | k) = \frac{m+k}{m+n+t} \cdot \frac{m+k+1}{m+n+t+1} + \frac{n+t-k}{m+n+t} \cdot \frac{m+k}{m+n+t+1}$$

The above equation was for the situation where exactly $$k$$ red balls were chosen - we need to write the expectation for all possible values of $$k$$. Using the law of total expectation, we can write:

$$E(R_{t+1}) = \sum_{k=0}^t E(R_{t+1} | k) \cdot P(R_t = m+k)$$

Substituting:

\begin{align*} E(R_{t+1}) &= \sum_{k=0}^t \left[ \frac{m+k}{m+n+t} \cdot \frac{m+k+1}{m+n+t+1} + \frac{n+t-k}{m+n+t} \cdot \frac{m+k}{m+n+t+1} \right] \\ &\quad \cdot \binom{t}{k} \cdot \prod_{i=0}^{k-1} \frac{m+i}{m+n+i} \cdot \prod_{j=0}^{t-k-1} \frac{n+j}{m+n+k+j} \end{align*}

Simplification:

\begin{align*} E(R_{t+1}) &= \sum_{k=0}^t \left[ \frac{(m+k)^2 + (m+k)}{(m+n+t)(m+n+t+1)} \right] \\ &\quad \cdot \binom{t}{k} \cdot \prod_{i=0}^{k-1} \frac{m+i}{m+n+i} \cdot \prod_{j=0}^{t-k-1} \frac{n+j}{m+n+k+j} \end{align*}

Part 3: I can also show that the Ratio $$R_t$$ is a Martingale. For $$R_t$$ to be Martingale, the following would have to be true:

$$E[R_{t+1} | R_t] = \frac{m+k}{m+n+t} = R_t$$

To calculate $$E[R_{t+1} | R_t]$$, we need to identify the possibilities at $$t1$$:

• Choose a red ball: probability $$\frac{m+k}{m+n+t}$$
• Choose a blue ball: probability $$\frac{n+t-k}{m+n+t}$$

\begin{align*} E[R_{t+1} | R_t] &= \frac{m+k}{m+n+t} \cdot \frac{m+k+1}{m+n+t+1} + \frac{n+t-k}{m+n+t} \cdot \frac{m+k}{m+n+t+1} \\[10pt] &= \frac{(m+k)(m+k+1)}{(m+n+t)(m+n+t+1)} + \frac{(n+t-k)(m+k)}{(m+n+t)(m+n+t+1)} \\[10pt] &= \frac{(m+k)[(m+k+1) + (n+t-k)]}{(m+n+t)(m+n+t+1)} \\[10pt] &= \frac{(m+k)(m+n+t+1)}{(m+n+t)(m+n+t+1)} \\[10pt] &= \frac{m+k}{m+n+t} \end{align*}

And, earlier, we saw that:

$$R_t = \frac{m+k}{m+n+t}$$

Thus we can see that:

$$E[R_{t+1} | R_t] = \frac{m+k}{m+n+t} = R_t$$

Suggesting that $$R_t$$ is a Martingale.

Here is where I am stuck - can someone please show me how to continue the proof using Martingales?

• I don't think Martingales are a very natural tool for proving the limit distribution. I tend to think of Martingales as more useful in terms of going from $X_n$ for high $n$ down to lower $n$ which would be the opposite. Commented 2 days ago