5
$\begingroup$

There are 10 numbered from 1 to 10 marbles. The marbles are placed in an opaque bag and shuffled. One random marble is taken out, its number is written on a piece of paper, marble is then returned to the bag, marbles are shuffled again. Procedure is repeated, until 25 records are accumulated on the paper.

Question №1: what is the probability that paper now contains all numbers from 1 to 10, at least once?

Q №2: what is the average amount of numbers to be written in such a manner, until all numbers from 1 to 10 are recorded at least once?

P.S. I found correct numbers by using the Monte Carlo method, but interested in purely mathematical solution.

Update Since asking this, I've questioned friends and collegues, tried to receive correct solution for #1 at different websites, but it all failed for me. The Emperor of Ice Cream's answer, simply doesn't seem to be entirely correct, as it's outcome is fairly far from my simulation results (which was conducted again on rewired algorithm, only to see the same outcome).

$\endgroup$

1 Answer 1

1
$\begingroup$

We can set our probability space to be the set of functions from $[1,2,3\dots 25]$ to $[1,2,3\dots 10]$. We want to find the probability we get a surjective function. Using the twelvefold way there are $10! S(25,10)$ of these. Hence the probability is $\frac{10!S(25,10)}{10^{25}}\approx 0.437$


For the second question this is the coupon collector problem, answered brilliantly by Henning Makholm here.


Initially I misunderstood the second question and calculated the average number of different coupons you will draw:

$$\dfrac{\sum\limits_{i=1}^{10}i(\binom{10}{i}i!S(25,i))}{10^{25}}\approx$$

This is because there are $\binom{10}{i}i!S(25,i)$ functions which have a range with size $i$. This is because there are $\binom{10}{i}$ ways to select the range. And after this we use the same argument as above, because all functions are surjective on their image.

$\endgroup$
3
  • $\begingroup$ Could there be some minor error? My simulation on 100k iterations resulted with ~0.48 $\endgroup$
    – AlexTR
    Feb 24, 2015 at 16:09
  • $\begingroup$ It's possible, I'm going to run the number again once I finish downloading sage on my computer $\endgroup$
    – Asinomás
    Feb 24, 2015 at 16:12
  • $\begingroup$ The second solution is sure totally correct, thank you :) $\endgroup$
    – AlexTR
    Feb 24, 2015 at 17:44

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.