1
$\begingroup$

I made an application which approaches Pi by throwing pseudo-random "darts" on a digital dartboard. Each dart is displayed by a black pixel. Just out of pure interest I started wondering how long it'd take for the entire image to be black on average.

The image is $700\times 700$ pixels, so there are $490.000$ possible pixels that can get picked. My question to you is: what is the probability of all pixels being black after 490.000 darts.

$\endgroup$
  • 2
    $\begingroup$ I don't see how the final question relates to your original problem. The probability that $N$ random selections (with replacement) among $N$ values will happen to all be distinct becomes exceedingly small as $N$ grows; so small that you can be sure it won't happen for $N=490\,000$. But this gives you very little information about the question in you first paragraph (except that it will take longer than $N$ trials). Please try to formulate a single question, clearly. $\endgroup$ – Marc van Leeuwen Nov 8 '15 at 8:02
10
$\begingroup$

When the number of pixels and the number of darts are equal, this problem is very simple. In the first throw, you can throw anywhere; in the second throw, you must throw somewhere other than where the first throw was; in the third throw, you must throw somewhere other than where the first two throws were; etc. So assuming the pixel hit by a throw is chosen uniformly among all the sites, the probability of hitting all $N$ pixels in $N$ throws is

$$\frac{N!}{N^N}.$$

Stirling's approximation tells us that this is about $\sqrt{2 \pi N} e^{-N}$ when $N$ is large.

When the number of pixels is larger than the number of throws, the problem is also simple: the answer is just zero.

If there are more throws than pixels, a slightly different approach is warranted. We can introduce the number of throws required to hit all the pixels. This is the number of throws required to hit the first unique pixel, plus the number of throws required to hit the second unique pixel, etc. The total is a sum of $N$ independent geometric random variables, with success probabilities $1,1-1/N,1-2/N,\dots,1/N$.

One can compute various things about this sum, such as its mean and variance. Specifically, the mean is $N \sum_{i=1}^N \frac{1}{i}$ which is asymptotic to $N \log(N)$. The variance is $\sum_{i=1}^{N} \frac{(1-i/N)}{(i/N)^2}$. The leading term of this is $N^2 \sum_{i=1}^{N} \frac{1}{i^2}$, so the overall variance is asymptotic to $\frac{\pi^2}{6} N^2$.

$\endgroup$
9
$\begingroup$

This is the Coupon Collector's problem. If there are $N$ pixels in your image, it will take approximately $N\log N$ dart throws to fill it in completely.

So for $N=490000$, you will need about $6.4$ million dart throws.

$\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.