# Unknown number of colours Bernoulli Urn

Okay, so, in the traditional Bernoulli Urn problem, we have an urn with a number N, possibly infinite, of coloured balls, and there are k possible colours. That one I grok.

However, what if I don't actually know what k is? That is, what if I have an urn with N balls and an unknown but finite and strictly positive number of possible colours?

The main question is, in fact, what my priors should be. What's the prior that there is exactly one colour? Exactly two? At least two? How do I update on the relative frequencies of each colour? Is this problem even solvable?

My first lines of thinking are to have a vector of parameters $\vec \theta \in \mathbb R^\infty$ such that the first parameter is the number of colours in the urn (let's call it $\alpha$) and the remaining are the relative frequencies of each colour. If $P(A=n|\vec\theta)$ is the probability that the colour of the next draw will be n given the knowledge contained by $\vec\theta$, we'd have:

• $\vec\theta = (\alpha, p_1, p_2, p_3, ...)$
• $\alpha \in \mathbb N^*$
• $\left(\sum\limits_{n=1}^\infty P(\alpha = n) \right)= 1$
• $\left(\sum\limits_{n=1}^\infty p_n\right) = 1$
• $\forall n > \alpha : p_n = 0$
• $\forall n \in \mathbb N^* : P(A=n|\vec\theta) = p_n$

However, this is just wild speculation on my part. I'm mostly curious about whether this is even in principle solvable. What I'd want to know is a way to compute both the prior and posterior distributions of $P(\vec\theta)$ or, in other words, the pdfs $P(\alpha)$, $P(p_1)$, $P(p_2)$, etc. How to start with them and how to update on them.

-

The problem is solvable. To guide your thinking:

You know:

1. There are $N$ balls in the urn; $N$ is unknown but $1\le N$.
2. There are $k$ colours in the urn; $k$ is unknown but $1\le k \le N$.

That's it, you don't know anything else - so now you need to hypothesize about the distribution of $N$ and $k$ - it is these hypotheses that you will test.

When you draw the first ball and it is color $C_1$ you learn nothing. You can either put it back (Multinomial distribution) or put it aside (Multivariate hypergeometric distribution); the second is more complex but will reject your hypothesis faster.

You draw a second ball; there are 3 possibilities:

1. There isn't one to draw (only if you didn't replace).
2. It is colour $C_2$.
3. It is colour $C_1$ again.

For the Multinormal approach, you can say

1. Can't happen.
2. $2\le N$ and $2\le k \lt N$ with certainty.
3. $1\le N$ and $1\le k \lt N$ with certainty (i.e. no new information).

For the Multivariate hypergeometric approach, you can say

1. $N=1$ and $k=1$ with certainty.
2. $2\le N$ and $2\le k \lt N$ with certainty.
3. $2\le N$ and $1\le k \lt N-1$ with certainty.

Using this you refine your hypotheses and move on.

How likely is it?

Assume you draw $n$ balls with replacement getting $x_i$ balls of colour $i$ with $k$ colours in all. The probability of extracting a ball of colour $i$ is $p_i$ which is equal to the proportion of balls of that colour in the bag and is unknown.

Now,

$$\sum_{i=1}^{k}p_i \le 1$$

With the difference between the total and 1 being the probability of all colours not selected.

And, from the multi normal distribution,

$$p=\prod_{i=1}^k\frac{n!p_i^{x_i}}{x_i!}$$

We know this is maximised when $p_i=\frac{x_i}{n}$ giving

\begin{align} p_{max}&=\prod_{i=1}^k\frac{n!\left(\frac{x_i}{n}\right)^{x_i}}{x_i!}\\ &=\prod_{i=1}^k\frac{n!x_i^{x_i}}{n^nx_i!}\\ \end{align}

Since $\sum_{i=1}^kx_i=n$

Now you could differentiate with respect to each $x_i$ but given that these are discrete a simple difference equation will do. You draw another ball of colour $a$ where $1\le a\le k+1$, what is your new $p_{max}$ and how much is it different from the old?

-
Okay, that's a good start. Let's say we're at the Multinomial approach (i.e. with replacement). Then what is my actual posterior distribution for k? And how do I compute the probabilities $P(C_n)$? That is, after having drawn those balls, how do I update my probabilities? And what should the probability for the next colour be? Usually, $P(A) = (multinomial) p_1^{n_1}p_2^{n_2}p_3^{n_3}...$ but if I don't know how many $p_i$ there are...? –  Pedro Carvalho Dec 6 '13 at 8:03
If you draw $n$ balls and get $k_i$ balls of colour $k_i$, THE most likely distribution will always be the proportions that you have in the sample. This is true irrespective is the relative sizes n or N. –  Dale M Dec 7 '13 at 9:31
Yes, I know, but I want to quantify that. I want to know exactly how much more likely that distribution is, and how confident I should be about that, and how likely are any other distributions. –  Pedro Carvalho Dec 7 '13 at 10:59