Omnium Gatherum

Praemissa propositio . Consider k threads independently selecting one item each from a collection of n items. The probability that at least one thread selects a particular item is one minus the probability that every thread selects an item other than that:

1 - {(\frac{n - 1}{n})}^{k}

Utile theorema . When $k ≪ n$ , this is approximately $k / n$ .

1 - {(1 - 1 / n)}^{k} \sim k / n

Ratio demonstrandi . When k = 1, this is exact:

1 - (1 - 1 / n) = 1 - 1 + 1 / n = 1 / n

Considering k = 2 and k = 3 gives the general idea of an argument. We first reärrange

1 - k / n \sim {(1 - 1 / n)}^{k}

and then expand:

{(1 - 1 / n)}^{2} = 1 - 2 / n + 1 / n^{2}

{(1 - 1 / n)}^{3} = (1 - 2 / n + 1 / n^{2}) (1 - 1 / n) = 1 - 3 / n + 3 / n^{2} - 1 / n^{3} .

Here we can see the origin of the $- k / n$ term,

(1 - (k - 1) / n + · · ·) (1 - 1 / n)

= 1 \times 1 + 1 \times (- 1 / n) + (- (k - 1) / n) \times 1 + · · ·

and it appears that simply applying the binomial theorem will suffice.

{(1 - 1 / n)}^{k} = (\binom{k}{0}) 1^{k} {(- 1 / n)}^{0} + (\binom{k}{1}) 1^{k - 1} {(- 1 / n)}^{1}

+ (\binom{k}{2}) 1^{k - 2} {(- 1 / n)}^{2} + (\binom{k}{3}) 1^{k - 3} {(- 1 / n)}^{3} + · · ·

= 1 - \frac{k}{n} + \frac{k (k - 1)}{2} \frac{1}{n^{2}} - \frac{k (k - 1) (k - 2)}{6} \frac{1}{n^{3}} + · · ·

to-do finish proof and remark this can be used to calculate chance of collision
(the size of the error term relative to k/n can be made as small as desired, less than ε, by choosing a sufficiently small k/n)