1
$\begingroup$

You have exactly $n^2$ balls each one of which can be colored in one of $n^2$ ways. That is total colors is $n^2$ but I am not saying all the $n^{2}$ balls are distinctly colored. However assume each ball can be given a color $i$ with probability $\frac{1}{n^2}$ (uniform probability of assignment of colors). You pick $n^{b}$ balls without replacement. What is the probability that atleast $n^{a}$ balls are of the same color with $0 < a < b \leq 2$? Floor any real numbers to get integers - in any case - I am looking for asymptotic bounds.

$\endgroup$
  • $\begingroup$ could you elaborate? $\endgroup$ – Turbo Jul 29 '13 at 17:34
  • 2
    $\begingroup$ Are $a$, $b$, and $n$ exponents? Are we to assume that $a$ and $b$ are either $0$,$1$, or $2$, or can they be arbitrary real numbers? $\endgroup$ – Omnomnomnom Jul 29 '13 at 18:32
  • $\begingroup$ What do you mean? All $a,b,n$ are variables. If it helps analysis, you could substitute constants. $\endgroup$ – Turbo Jul 29 '13 at 18:35
  • $\begingroup$ Is $a=1.5$ allowed? $\endgroup$ – Tomas Jul 29 '13 at 20:23
1
$\begingroup$

Presumably you are drawing with replacement. We assume you want exactly $n^a$ that match, with the rest non-matching. If you just want at least $n^a$, you have to sum over $n^a$ up to $n^b$. If $2n^a \gt n^b$ it is easier, as you can't get two sets of the same color. There are $(n^2)^{(n^b)}$ ordered draws. To get $n^a$ that match, you can choose the positions of the matching ones in ${n^b \choose n^a}$ ways, the color in $n^2$ ways, and the remaining colors in $(n^2-1)^{(n^b-n^a)}$ ways. So we have a probability of $$\frac {{n^b \choose n^a}n^2(n^2-1)^{(n^b-n^a)}}{(n^2)^{(n^b)}}$$ This will overcount if $2n^a \le n^b$ because times you get two groups of $n^a$ are counted twice and so on. There is no magic in making everything powers of $n$-you could as easily use $a,b,n$ for the numbers. It should be clear how to modify the expression to do that.

$\endgroup$
  • $\begingroup$ I do not want replacement. $\endgroup$ – Turbo Jul 30 '13 at 0:22
  • 1
    $\begingroup$ If you don't want replacement, you can't get more than one ball of a given color. The probability is zero. $\endgroup$ – Ross Millikan Jul 30 '13 at 0:26
  • 1
    $\begingroup$ Then you have to specify the distribution. If the colors are randomly picked, you will have a Poisson distribution with mean $1$. About $\frac 1e$ of the colors will be absent, about $\frac 1e$ will have only one marble, others will have a few more. The chance of getting any reasonable number of matches is still very small. $\endgroup$ – Ross Millikan Jul 30 '13 at 13:24
  • 1
    $\begingroup$ That was the random pick I describe above. $\endgroup$ – Ross Millikan Jul 30 '13 at 13:34
  • 1
    $\begingroup$ I had some exponents backwards, now fixed. The top exponent in the denominator is $b$, not $a$ (and not $2$). Basically, you have so many colors (assuming $n$ isn't too small) that you can't get very many matches. $\endgroup$ – Ross Millikan Jul 30 '13 at 14:26
0
$\begingroup$

Note that you don't have to account for initially choosing the $n^b$ balls out of $n^2$. In particular, we could start with just $n^b$ balls and ask what is the probability that at least $n^a$ have the same color. Let $X$ denote the number of sets of $n^a$ balls of the same color, so we wish to bound the probability that $X$ is at least 1. So \begin{align*} P(X \geq 1) \leq E[X] &= \sum_{A : |A|=n^a} P(\text{the balls of }A\text{ are mono colored}) \end{align*} For any specific such set of balls $A$, note that this probability is exactly $$\left( \frac{1}{n^2} \right)^{|A|-1},$$ since the first ball can be any color, but each of the following balls of $A$ must be the same as the first one.

Hence \begin{align*} P(X \geq 1) &\leq {n^b \choose n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \leq \left( \frac{e n^b}{n^a} \right)^{n^a} \left( \frac{1}{n^2} \right)^{n^a-1} \\& \leq n^2 \left( \frac{e n^b}{n^a n^2} \right)^{n^a}=\exp \left( -n^a(2-b+a)\ln n+o(n^a \ln n)\right). \end{align*}

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.