# Birthday problem variation with balls and bins

Balls are thrown randomly and uniformly into $$n$$ bins up until one bin has 3 balls. Let there be $$T=T(n)$$ be the number of throws we made until the occasion occurs. I am to assume $$n$$ is large and requested to find $$f(n)$$ so that the probability:

$$P(T > 0.1f(n))$$ Is close to 1 (for example bigger than 0.9999) and the probability: $$P(T > 10f(n))$$ Is close to 0 (for example smaller than 0.001)

Our hint was to investigate the random variable, when throwing $$m$$ balls $$X(m)$$ is the number of triplets $$[i,j,k] \subset [1,2,...,m]$$ so that the $$i,j,k$$ balls thrown fall in the same bin.

I have tried doing something similar to the birthday problem by defining a uniform random variable $$X_i$$ over $$i \in [1,...,n]$$ so its basically if there is a ball in the $$i$$ bin. then I made another variable $$Y_i,_j,_k =\begin{cases} 1, & \text{X_i = X_j = X_k} \\0, & \text{otherwise}\end{cases}$$ And then went on to calculate the expected value. Overall I received the result $${m \choose 3}*\frac{1}{n^2}$$ but the results don't match the definition of $$X(m)$$.

I am really kind of lost as this was the main way I felt might work, where am I wrong in this, whether its my way of thought or just my math, all help would be appreciated.

p.s. this is a homework question but the due date already passed

• "one bin > has $3$ balls" looks like a typo. – saulspatz Dec 21 '18 at 16:29
• Hey, thanks i edited – LonelyStudent Dec 21 '18 at 16:43

You are asked to get the number of balls right within a factor of $$10$$ so we can be rather rough. If $$n$$ is fairly large you will have a Poisson distribution of the number of balls in each bin. If we throw $$k$$ balls the parameter in the Poisson distribution is $$\lambda=\frac kn$$. We want to choose this so there is a reasonable chance that at least one bin has three balls. The chance a given bin has three balls is $$\frac {\lambda^3e^{-\lambda}}{3!}$$. Since there are $$n$$ bins, we want this to be about $$\frac 1n$$ So (using $$=$$ instead of $$\approx$$) we have $$\frac {\lambda^3e^{-\lambda}}{3!}=\frac 1n\\ \frac {(\frac kn)^3e^{-\frac kn}}{3!}=\frac 1n\\ e^{-\frac kn}=\frac {6n^2}{k^3}$$ I did an approximate solution of this for $$n$$ from $$5$$ to $$65$$ in steps of $$5$$ in a spreadsheet. The graph is below. • Your approach is not so different. You are saying that any given set of three balls has $\frac 1{n^2}$ chance of hitting the same bin. There are about $\frac {k^3}6$ sets of three balls. That gives the same combination as on my right side. I think your logic would then be to set that to $1$, while I use a number somewhat less than $1$, but not so much. You would then say $k=\sqrt{6n^2}$ – Ross Millikan Dec 22 '18 at 2:23
• First of all thank you, second I tried doing what you said and reducing the number to 1 by $k = \sqrt{(6n^2)}$ but I cant seem to relate it to a function like requested in the question, when I use for example $n=10$ while making the function $f(n) = \sqrt{(6n^2)}$ then the result $P(T > 0.1f(n))$ isnt really like expected because the number of balls must be larger then about $0.1*8.4$ – LonelyStudent Dec 22 '18 at 15:52
• What you would have to do would be to make an argument that involves approximations, bound those approximations, and show that the product means the error is less than a factor of $10$. Maybe you have three approximations, each of which can be wrong by a factor $2$. The product is then good to a factor $8$, which is good enough. I don't see a way there. – Ross Millikan Dec 23 '18 at 17:06