Polya Urn - formulas

Question

I am trying to understand Dirichlet processes and Polya's Urn, following this excellent article.

One thing that I am struggling with, is to understand in the example below what why the number of balls of color x is exactly equal to the dispersion parameter $\alpha$ times $G_0(x)$. Let me know if someone can give a numerical exampe to help me understand.

Polya Urn Model: We start with an urn containing $α G_0(x)$ balls of “color” x , for each possible value of x. ($G_0$ is our base distribution, and $G_0(x)$ is the probability of sampling x from $G_0$). Note that these are possibly fractional balls.

At each time step, draw a ball from the urn, note its color, and then drop both the original ball plus a new ball of the same color back into the urn.

Answer 1

I find the notion of $\alpha G_0(x)$ initial balls of color $x$ confusing and potentially misleading. I like another version of the urn better, similar to the one described on Wikipedia.

Let's assume that the color palette of the balls is greyscale: 0 is black, 1 is white, and any fractional value in between indicates a shade of grey. Hence, our sampling space is the real interval $[0,1]$. $G_0$ is defined over such interval. For example, let's take the uniform distribution that assigns equal density to all points in $[0,1]$, i.e. $f_{G_0} = \mathbf{1}_{[0,1]}$.

At the beginning, the urn is filled with $\alpha$ balls of a special color, red. Repeatedly, we draw a ball from the urn. If the ball is red, we sample a shade of grey $x_i$ from $G_0$ (uniform in our case) and place the red ball and the ball of the new color back in the urn. If the color of the ball we draw is not red, we place two balls of that shade of grey back in the urn.

The first ball we draw will always be red. Say that we draw $x_1=0.5$ as the color of the ball that we put back in the urn along with the red ball. At the next timestep, we will draw a red ball with probability $\frac{\alpha}{1+\alpha}$ and a ball of color $0.5$ with probability $\frac{1}{1+\alpha}$.

This is equivalent to the Chinese Restaurant Process, where each table is assigned to a color. We, the manager, seat each new customer to an already "opened" table with probability proportional to the number of customers already sitting at such table, and with probability proportional to $\alpha$ we start a new table.

Answer 2

I think this interpretation of $\alpha G_{0}(x)$ as the number of balls of color $x$ is not entirely accurate. As I understand it, the purpose of using the Polya Urn scheme is to find the probability of drawing a ball of color $x_{i}$ in your next draw. I will be using the more usual $\theta_{i}$ instead of $x_{i}$.

Assume a base distribution $G_{0}$. Usually, this is taken as a normal distribution. From this distribution, sample a ball of color $\theta_{1}$ (imagining for a moment that colors are normally distributed.) That is, $\theta_{1} \sim G_{0}$.

Next, you select your next color based on the probability $G(\theta_{2}) = \displaystyle \frac{\alpha G_{0}(\theta_{2}) + \sum_{i=1}^{N} \delta(\theta_2=\theta_{i})}{\alpha + N}$. Here $G(\theta_{2})$ is the probability of having a ball with color $\theta_{2}$. The term $\alpha G_{0}(\theta_{2})$ is your base distribution modified by the concentration parameter $\alpha$. If you choose $\alpha$ to be a very small number, $\alpha G_{0}(\theta)$ will be a sparse distribution (with very few peaks). A very large $\alpha$ makes your distribution look like a uniform distribution (e.g. all values are equally likely.) Notice that $\alpha G_{0}(\theta)$ describes the modified base distribution and $\alpha G_{0}(\theta_{2})$ describes the probability of a ball with a specific color $\theta_{2}$.

The second term $\sum_{i=1}^{N} \delta(\theta_2=\theta_{i})$ is responsible for the "rich gets richer" effect often associated with the Polya Urn procedure. This is counting the number of balls with color $\theta_{2}$ that are already inside the urn and increases the probability of drawing the same color again.

After you have calculated $G(\theta)$ for your available colors, this is, the probabilities $G(\theta_{2}=\text{red})$, $G(\theta_{2}=\text{blue})$, etc, it is possible to sample from this distribution and obtain the next color $\theta_{2}$. Iterate this step again and again for $\theta_{3}, \theta_{4}, ...$ and the resulting probability distribution $G(\theta)$ will be distributed as a Dirichlet process $G(\theta) \sim DP(\alpha, G_{0})$.

To emphasize this point, the concentration parameter modifies the probability of drawing a given color. It also changes, after many iterations, the distributions $G$ sampled from the Dirichlet process $DP(\alpha, G_{0})$.