2
$\begingroup$

Lets say I am spinning a bottle while sitting in a group of 10 people. I want to know the minimum number of times I would need to spin the bottle to have a 50% chance of hitting everyone in the circle at least once. How would I go about determining this minimum number of spins? Would the method to calculate this change with a very small (say 1%) or large (say 99%) chance, or with a much larger number of people (say 1000)?

I have attempted to look up some formulas but I am really not sure how to model this problem mathematically/in terms of probabilities. I know that it is impossible to determine if the percentage is set to 100% (no guarantee you'll ever hit each unique person). Hopefully this same math question hasn't been duplicated elsewhere with a different framing, the closest I could find was here.

EDIT: A little more searching and apparently this is a well defined problem... It seems searching for it in terms of dice rolls yielded much better results and based on my understanding should be equally applicable (replacing hitting a person with the bottle with getting a certain number on the die).

See here: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem Will update when I think I have a real answer.

$\endgroup$
  • 1
    $\begingroup$ This is related to the coupon collector's problem. With $10$ equally probable values sampled with repetition, you need a sample size of at least $27$ to have a probability of at least $50\%$ of seeing them all (in a sense this is the median compared with a mean of about $29.28968$ and a mode of $23$); at least $13$ to have a probability of at least $1\%$ and at least $66$ to have a probability of at least $99\%$ $\endgroup$ – Henry Dec 19 '16 at 8:06
  • $\begingroup$ Thank you very much for this answer. I have read through the Wikipedia page and I understand how the expected value (what you refer to as the mean) is calculated. I am still, however, a bit fuzzy on how you came up with the number associated with the exact probabilities of 1%, 50% and 99%. I see a reference to Markov and Chebychev probability bounding equations but It is not clear to me how to come up with the answers you did of 27, 13, and 66. $\endgroup$ – scuba Dec 19 '16 at 9:03
1
$\begingroup$

In this answer, it is shown that the probability of not hitting everyone by the $m^\text{th}$ spin would be $$ 1-p=\sum_{k=1}^n(-1)^{k-1}\binom{n}{k}\left(1-\frac kn\right)^m\tag{1} $$ Thus, the probability of hitting everyone by the $m^\text{th}$ spin would be $$ p=\sum_{k=0}^n(-1)^k\binom{n}{k}\left(1-\frac kn\right)^m\tag{2} $$ According to the answer cited above, the expected duration is $nH_n\sim n\log(n)+\gamma n$. If we set $m=n\log(n)+nx$, then $$ \begin{align} p &=\sum_{k=0}^n(-1)^k\binom{n}{k}\left(1-\frac kn\right)^{n\log(n)+nx}\\ &\approx\sum_{k=0}^n(-1)^k\binom{n}{k}\frac1{n^k}e^{-kx}\\ &\approx\sum_{k=0}^n(-1)^k\frac1{k!}e^{-kx}\\[9pt] &=e^{-e^{-x}}\tag{3} \end{align} $$ Therefore, we get the approximation $$ m=n\log(n)-n\log\left(\log\left(\frac1p\right)\right)\tag{4} $$


For $p=1\%$, we need $m\approx n\log(n)-1.52718\,n$.

For $p=50\%$, we need $m\approx n\log(n)+0.366513\,n$.

For $p=99\%$, we need $m\approx n\log(n)+4.60015\,n$.

| cite | improve this answer | |
$\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.