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 the complement of the probability that every thread selects an item 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}$$

More precisely, the relative difference between these can be made arbitrarily small by decreasing k or increasing n. This can be seen here.

Sometimes this approximation is more useful in a reärranged form:

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

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

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

From here on, we will assume that k is greater than one.

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,

$$(1-(\mathrm{k}-1)/\mathrm{n}+\text{· · ·})(1-1/\mathrm{n})$$ $$=1\times 1+1\times (-1/\mathrm{n})+(-(\mathrm{k}-1)/\mathrm{n})\times 1+\text{· · ·}$$

and indeed, 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{. . .}\text{.}$$

The absolute error term is

$${\mathrm{E}}_{\text{abs}}=\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{· · ·}$$

and the relative error term ${\mathrm{E}}_{\text{rel}}={\mathrm{E}}_{\text{abs}}/(\mathrm{k}/\mathrm{n})$ is

$${\mathrm{E}}_{\text{rel}}=\frac{\mathrm{k}-1}{2\mathrm{n}}-\frac{(\mathrm{k}-1)(\mathrm{k}-2)}{6{\mathrm{n}}^2}+\text{. . .}\text{.}$$

We need to show that, for any ε less than one, the relative error is less than ε when n is $\mathrm{k}/\mathrm{\epsilon }$.

$$\mathrm{\epsilon }>\frac{\mathrm{k}-1}{2\mathrm{k}}\mathrm{\epsilon }-\frac{(\mathrm{k}-1)(\mathrm{k}-2)}{6{\mathrm{k}}^2}{\mathrm{\epsilon }}^2+\text{· · ·}$$ $$1>\frac{\mathrm{k}-1}{2\mathrm{k}}-\frac{\mathrm{k}-1}{2\mathrm{k}}\frac{\mathrm{k}-2}{3\mathrm{k}}\mathrm{\epsilon }+\text{· · ·}$$

Each term on the right-hand is larger than the succeeding term, and since the signs alternate, each term is also larger than the succeeding series.

Lemma. Suppose that $$\text{· · ·}>{\mathrm{x}}_2>{\mathrm{x}}_1>{\mathrm{x}}_0>0\text{.}$$ Then ${\mathrm{x}}_1-{\mathrm{x}}_0>0$ and ${\mathrm{x}}_2>{\mathrm{x}}_1-{\mathrm{x}}_0$ , because ${\mathrm{x}}_2>{\mathrm{x}}_1$ and ${\mathrm{x}}_1>{\mathrm{x}}_1-{\mathrm{x}}_0$ . $${\mathrm{x}}_2>{\mathrm{x}}_1-{\mathrm{x}}_0>0$$ $${\mathrm{x}}_3>{\mathrm{x}}_2-({\mathrm{x}}_1-{\mathrm{x}}_0)>0$$ $${\mathrm{x}}_4>{\mathrm{x}}_3-({\mathrm{x}}_2-({\mathrm{x}}_1-{\mathrm{x}}_0))>0$$ Inductively, we have that $${\mathrm{x}}_{\mathrm{n}}>{\mathrm{x}}_{(\mathrm{n}-1)}-{\mathrm{x}}_{(\mathrm{n}-2)}+{\mathrm{x}}_{(\mathrm{n}-3)}-\text{· · ·}>0\text{.}$$

And so we conclude that

$$1>\frac{\mathrm{k}-1}{2\mathrm{k}}-\frac{\mathrm{k}-1}{2\mathrm{k}}\frac{\mathrm{k}-2}{3\mathrm{k}}\mathrm{\epsilon }+\text{. . .}∎$$

---

Praemissa propositio . Consider k threads independently selecting one item each from a collection of n items. The probability that two or more threads select a particular item is the complement of the probability that ⌜every thread selects an item other than that or exactly one thread selects the item⌝ :

$$1-({\left(\frac{\mathrm{n}-1}{\mathrm{n}}\right)}^{\mathrm{k}}+\frac{\mathrm{k}}{\mathrm{n}}{\left(\frac{\mathrm{n}-1}{\mathrm{n}}\right)}^{\mathrm{k}-1})$$ $$=1-{\left(\frac{\mathrm{n}-1}{\mathrm{n}}\right)}^{\mathrm{k}}(1+\frac{\mathrm{k}}{\mathrm{n}}\frac{\mathrm{n}}{\mathrm{n}-1})$$ $$=1-(1+\frac{\mathrm{k}}{\mathrm{n}-1}){\left(\frac{\mathrm{n}-1}{\mathrm{n}}\right)}^{\mathrm{k}}\text{.}$$

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

$$\frac{1}{2}\frac{\mathrm{k}(\mathrm{k}-1)}{\mathrm{n}(\mathrm{n}-1)}\text{.}$$

Admonitio . This is different than the probability of a collision occurring, that is, the prob­a­bility of two or more threads selecting the same item (where the selected item may be any item rather than a particular item).

---

Praemissa propositio . Suppose there are k threads selecting openings (and playing out games from them) and that these threads cannot communicate. How do we avoid collisions (book exits being selected by more than one thread) while also having randomized and uniform coverage? Broadly speaking, we simply make the space of possible book exits to sample from large enough that the chance of a collision is low.

Suppose we want to generate g book exits (play out g games) in total, or g / k games per thread. Let s be a multiplier, so that that the number of possible book exits to pick from is g × s. Then the fraction of the space g × s that each thread will explore is

$$\mathrm{p}=\frac{\mathrm{g}/\mathrm{k}}{\mathrm{g}\times \mathrm{s}}=1/(\mathrm{k}\times \mathrm{s})\text{.}$$

For any particular thread, and any particular book exit, this is the probability that the thread will pick that book exit. For convenience, let’s also define $\mathrm{q}=1-\mathrm{p}$, which is the probability that a particular thread does not pick a particular book exit. The probability that a particular book exit is picked by any thread is

$$\mathrm{a}=1-{\mathrm{q}}^{\mathrm{k}}$$

and the probability that a particular book exit is picked by exactly one thread is

$$\mathrm{u}=\mathrm{k}\times \mathrm{p}\times {\mathrm{q}}^{\mathrm{k}-1}\text{.}$$

Then the probability that a particular book exit is picked by exactly one thread given that it was picked is u / a.

Quite happily, u / a rapidly converges to a limit as k increases, which follows from our approximation. We first substitute the definitions of u, p, q, and a to obtain

$$\mathrm{u}/\mathrm{a}=\frac{\mathrm{k}}{\mathrm{k}\times \mathrm{s}}\times \frac{{(1-1/(\mathrm{k}\times \mathrm{s}))}^{\mathrm{k}-1}}{1-{(1-1/(\mathrm{k}\times \mathrm{s}))}^{\mathrm{k}}}\text{.}$$

Then we have

$$\mathrm{u}/\mathrm{a}\sim \frac{1}{\mathrm{s}}\times \frac{1-(\mathrm{k}-1)/(\mathrm{k}\times \mathrm{s})}{\mathrm{k}/(\mathrm{k}\times \mathrm{s})}=1-\frac{\mathrm{k}-1}{\mathrm{k}}\times \frac{1}{\mathrm{s}}$$

when $\mathrm{k}\times \mathrm{s}\gg \mathrm{k}$, or more simply, when $\mathrm{s}\gg 1$.

When $\mathrm{k}\gg 1$, this is approximately $1-1/\mathrm{s}$.

Alternatively, we might instead write

$$\mathrm{u}/\mathrm{a}=\frac{1}{\mathrm{s}\times (1-1/(\mathrm{k}\mathrm{s}))}\times \frac{{(1-1/(\mathrm{k}\mathrm{s}))}^{\mathrm{k}}}{1-{(1-1/(\mathrm{k}\mathrm{s}))}^{\mathrm{k}}}$$

and then

$$\mathrm{u}/\mathrm{a}\sim \frac{1}{\mathrm{s}\times (1-1/(\mathrm{k}\mathrm{s}))}\times \frac{1-1/\mathrm{s}}{1/\mathrm{s}}=\frac{1-1/\mathrm{s}}{1-1/(\mathrm{k}\mathrm{s})}$$ $$=\frac{\mathrm{s}-1}{\mathrm{s}-1/\mathrm{k}}$$

and once again, when $\mathrm{k}\gg 1$, this is approximately $(\mathrm{s}-1)/\mathrm{s}=1-1/\mathrm{s}$. However, these are fairly poor approximations; an approximation like $1-1/(2\mathrm{s})$ works much better.

We might try repeating the same procedure above using

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

and derive

$$\mathrm{u}/\mathrm{a}\sim \frac{\mathrm{s}-1+1/(2\mathrm{s})}{\mathrm{s}-\mathrm{½}}$$

when $\mathrm{k}\gg 1$, which is an improvement, but still worse than $1-1/(2\mathrm{s})$.

We can instead take a different tack.

Utile theorema . The probability that a particular item (of k × s items) is selected by exactly one thread (of k threads) given that it was selected by any thread is

$$\frac{1}{\mathrm{s}}\times \frac{{(1-1/(\mathrm{k}\times \mathrm{s}))}^{\mathrm{k}-1}}{1-{(1-1/(\mathrm{k}\times \mathrm{s}))}^{\mathrm{k}}}\text{.}$$

When $\mathrm{s}\gg 1$, this is approximately

$$1-\frac{1}{2\mathrm{s}}\times \frac{\mathrm{k}-1}{\mathrm{k}-1/\mathrm{s}}\text{,}$$

or simply $1-1/(2\mathrm{s})$ when $\mathrm{k}\gg 1$ .

Ratio demonstrandi . Let us rewrite the expression as

$$(\star )\frac{1}{\mathrm{s}}\times \frac{1}{1-\frac{1}{\mathrm{s}\mathrm{k}}}\times \frac{{(1-\frac{1}{\mathrm{s}\mathrm{k}})}^{\mathrm{k}}}{1-{(1-\frac{1}{\mathrm{s}\mathrm{k}})}^{\mathrm{k}}}$$

and consider the rightmost term

$$\frac{{(1-1/(\mathrm{s}\mathrm{k}))}^{\mathrm{k}}}{1-{(1-1/(\mathrm{s}\mathrm{k}))}^{\mathrm{k}}}$$

in isolation.

We first rewrite this term further as

$$(\text{†})\frac{1}{1-{(1-1/(\mathrm{s}\mathrm{k}))}^{\mathrm{k}}}-1\text{.}$$ Æquatio. For any z, $\frac{\mathrm{z}}{1-\mathrm{z}}=\frac{1}{1-\mathrm{z}}-1$ by the following sequence of rewrites: $$\frac{\mathrm{z}}{1-\mathrm{z}}=\frac{1-(1-\mathrm{z})}{1-\mathrm{z}}=\frac{1}{1-\mathrm{z}}-\frac{1-\mathrm{z}}{1-\mathrm{z}}=\frac{1}{1-\mathrm{z}}-1\text{.}$$

The subterm ${(1-1/(\mathrm{s}\mathrm{k}))}^{\mathrm{k}}$ can be rewritten as

$$\frac{{(\mathrm{s}\mathrm{k}-1)}^{\mathrm{k}}}{{(\mathrm{s}\mathrm{k})}^{\mathrm{k}}}$$

and then we replace ${(\mathrm{s}\mathrm{k}-1)}^{\mathrm{k}}$ with its binomial expansion:

$$\frac{{(\mathrm{s}\mathrm{k}-1)}^{\mathrm{k}}}{{(\mathrm{s}\mathrm{k})}^{\mathrm{k}}}=\frac{1}{{\mathrm{s}}^{\mathrm{k}}{\mathrm{k}}^{\mathrm{k}}}({\mathrm{s}}^{\mathrm{k}}{\mathrm{k}}^{\mathrm{k}}-{\mathrm{s}}^{\mathrm{k}-1}{\mathrm{k}}^{\mathrm{k}}+\frac{1}{2}\frac{\mathrm{k}-1}{\mathrm{k}}{\mathrm{s}}^{\mathrm{k}-2}{\mathrm{k}}^{\mathrm{k}}-\text{· · ·})$$ $$=1-\frac{1}{\mathrm{s}}+\frac{1}{2}\frac{\mathrm{k}-1}{\mathrm{k}}\frac{1}{{\mathrm{s}}^2}-\text{· · ·}$$

(The elaboration of the binomial expansion has been omitted for brevity.) We create an approximation of the subterm by truncating the series. Substituting this in † gives us

$$\frac{1}{1-(1-\frac{1}{\mathrm{s}}+\frac{1}{2}\frac{\mathrm{k}-1}{\mathrm{k}}\frac{1}{{\mathrm{s}}^2})}-1$$ $$=\frac{1}{\frac{1}{\mathrm{s}}-\frac{1}{2}\frac{\mathrm{k}-1}{\mathrm{k}}\frac{1}{{\mathrm{s}}^2}}-1$$ $$=\frac{2\mathrm{k}{\mathrm{s}}^2}{2\mathrm{k}\mathrm{s}-\mathrm{k}+1}-1$$ $$=\frac{2\mathrm{k}{\mathrm{s}}^2-2\mathrm{k}\mathrm{s}+\mathrm{k}-1}{2\mathrm{k}\mathrm{s}-\mathrm{k}+1}$$

which is exactly

$$\mathrm{s}-\frac{1}{\mathrm{s}}-\frac{1}{2\mathrm{k}}\text{.}$$

(The steps of polynomial division have been omitted for brevity.)

We now substitute this in ⋆ and proceed to simplify:

$$\sim \frac{1}{\mathrm{s}}\times \frac{1}{1-1/(\mathrm{s}\mathrm{k})}\times (\mathrm{s}-\frac{1}{2}-\frac{1}{2\mathrm{k}})$$ $$=\frac{\mathrm{k}}{\mathrm{s}\mathrm{k}-1}(\mathrm{s}-\frac{1}{2}-\frac{1}{2\mathrm{k}})$$ $$=\frac{\mathrm{s}\mathrm{k}-\mathrm{k}/2-1/2}{\mathrm{s}\mathrm{k}-1}$$ $$=\frac{\mathrm{s}\mathrm{k}-1-\mathrm{k}/2+1/2}{\mathrm{s}\mathrm{k}-1}$$ $$=1-\frac{1}{2}\frac{\mathrm{k}-1}{\mathrm{s}\mathrm{k}-1}=1-\frac{1}{2}\frac{1}{\mathrm{s}}\frac{\mathrm{s}\mathrm{k}-\mathrm{s}}{\mathrm{s}\mathrm{k}-1}$$ $$=1-\frac{1}{2\mathrm{s}}\frac{\mathrm{k}-1}{\mathrm{k}-1/\mathrm{s}}∎$$

Annotatio . By inspection, we can see that the probability of uniqueness is 0.95 around s = 10; in other words, for each book exit, the probability that the book exit is duplicated is less than 5% when s = 10, and this is true independent of the number of threads, k, and the total number of games, g, we want to play. (The chance of duplication is even less when k is small.)