Omnium Gatherum

Consider k threads accessing concurrently a data structure with n entries. The probability that at least one thread access a particular entry is one minus the probability that every thread accesses an entry other than that:

$$1-{\left(\frac{\mathrm{n}-1}{\mathrm{n}}\right)}^{\mathrm{k}}$$

Utile theorema . When $\mathrm{k}\ll \mathrm{n}$, this is approximately $\mathrm{k}/\mathrm{n}$.

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

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

$$1-(1-1/\mathrm{n})=1-1+1/\mathrm{n}=1/\mathrm{n}$$

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

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

and then expand:

$${(1-1/\mathrm{n})}^2=1-2/\mathrm{n}+1/{\mathrm{n}}^2$$ $${(1-1/\mathrm{n})}^3=(1-2/\mathrm{n}+1/{\mathrm{n}}^2)(1-1/\mathrm{n})=1-3/\mathrm{n}+3/{\mathrm{n}}^2-1/{\mathrm{n}}^3\text{.}$$

Here we can see the origin of the $-\mathrm{k}/\mathrm{n}$ term, and it appears that simply applying the binomial theorem will suffice.

$${(1-1/\mathrm{n})}^{\mathrm{k}}=\left(\genfrac{}{}{0ex}{}{\mathrm{k}}{0}\right)1^{\mathrm{k}}{(-1/\mathrm{n})}^0+\left(\genfrac{}{}{0ex}{}{\mathrm{k}}{1}\right)1^{\mathrm{k}-1}{(-1/\mathrm{n})}^1$$ $$+\left(\genfrac{}{}{0ex}{}{\mathrm{k}}{2}\right)1^{\mathrm{k}-2}{(-1/\mathrm{n})}^2+\left(\genfrac{}{}{0ex}{}{\mathrm{k}}{3}\right)1^{\mathrm{k}-3}{(-1/\mathrm{n})}^3+\text{· · ·}$$ $$=1-\frac{\mathrm{k}}{\mathrm{n}}+\frac{\mathrm{k}(\mathrm{k}-1)}{2}\frac{1}{{\mathrm{n}}^2}-\frac{\mathrm{k}(\mathrm{k}-1)(\mathrm{k}-2)}{6}\frac{1}{{\mathrm{n}}^3}+\text{· · ·}$$

to-do finish proof and remark this can be used to calculate chance of collision