In Feller's book of probability exixt such formulas: a)Placing balls untill for the first time a ball is placed into a cell already occupied:
- The probability of the process termitating at the rth step is:$$((n)r *(r-1))/n^r$$
- The probability that process lasts for more than r steps: $$ (n)r/n^r$$
b)Continue procedure of placing balls as long as this cell remains empty:
- The probability that the process terminates at the rth step: $$ ((n-1)/n)^{r-1} *1/n $$
- Probability that the process lasts for more than r steps:$$(1-1/n)^r$$
Can you please explain how we got formulas? And the examples of their usage. Thank you
I would start with a(2). When you put the first ball in, you have $n$ empty bins out of $n$, so the chance the process continues past the first step is $\frac nn$. When you put the second ball in, the process continues with probability $\frac{n-1}n$. When you put the third in, the chance it continues (assuming you get this far) is $\frac {n-2}n$ because two bins are occupied. The chance you get past the third ball is then $\frac {n(n-1)(n-2}{n^3}$. The same logic says the chance of getting past $r$ balls is $\frac {n(n-1)(n-2)\dots(n-r+1)}{n^r}=\frac{n!}{n^rr!}$ I believe the numerator is what you are calling $(n)r$. The others are done similarly-see if you can.