2
$\begingroup$

$n$ balls are placed into $d$ boxes at random, with all $d^n$ possibilities equally likely. Assume $d>8$, let $X$ be the number of empty boxes.

My question is: if we say $D$ is the event that no box receives more than 1 ball. Fix $a \in (0,1)$. If both $n,d \rightarrow \infty$ together, what relation must they satisfy in order to have $P(D) \rightarrow a$?

I haven't figured out the expression of $P(D)$. Any hints would be appreciated.

$\endgroup$
1
$\begingroup$

Hint: The total number of ways that no box contains more than $1$ ball after all $n$ balls have been placed is the number of distinct $d$-long words containing $n$ ones (representing balls) and $d-n$ zeros (representing no balls). You then need to divide through the total number of possibilities to find $P(D)$. Do you know the stars and bars technique?

Edit: Stars and bars is a counting technique in which you use stars $*$ and bars $|$ to reformulate a problem into something you know. In this question we want to calculate the number of ways we can place $n$ balls in $d$ boxes. To count this we consider star and bar sequences where the bars represent sectioning off parts of our sequence into 'boxes'. The stars represent 'balls'.

The first thing we note is that to section of our sequence to $d$ parts, we need $d-1$ bars. For example if $d=5$, (I've labelled the boxes/spaces between the bars)

$$1|2|3|4|5.$$

As you can see, there are $5$ boxes/sections but only $4$ bars used.

Now we can places the $n$ stars into the sequence of $d-1$ bars. This will give a sequence that looks something like (in the case $d=5,n=6$)

$$ **|*||***|.$$

As the sectioned off parts of the sequence represent boxes and the stars represent the balls, the above sequence overall represents there being $2$ balls in box one, $1$ in box two, $0$ in box three, $3$ in box four and $0$ in box five.

We note that for general $n,d$ there is a sequence of stars and bars that represents a given combination of $m$ balls in $d$ bins. Also, given a sequence of stars and bars there is a analogous balls in bin combination. Hence there is a bijection between sequences containing $d-1$ bars and $n$ stars and the number of ways we can place $n$ balls in $d$ boxes. These are therefore both given by

$$ {n+d-1 \choose n}.$$

Can you continue from here? You should have found that $$P(D) = \frac{{d \choose n}}{{n+d-1 \choose n}}.$$

$\endgroup$
  • $\begingroup$ Sorry, I don't know about stars and bars. $\endgroup$ – Wendy Wang Aug 14 '16 at 22:46
  • $\begingroup$ It's a useful technique - have a search online. I'd add an edit to my answer, but I'm on my phone and it's about to run out of battery. I'll update my answer when I next have access to a computer. $\endgroup$ – Zestylemonzi Aug 14 '16 at 22:51
  • $\begingroup$ Ok, I will. Thank you! $\endgroup$ – Wendy Wang Aug 14 '16 at 23:27
  • $\begingroup$ Hope this edit helps :) $\endgroup$ – Zestylemonzi Aug 15 '16 at 8:52

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.