Bits of entropy needed to choose a random element from a list?

Question

Suppose I want to choose a random element from a list of size $2^n$, for any integer $n$. (Here, random is to mean an equal probability of selecting every item.) My intuition says I'd need $n$ bits of entropy. For example, for a list of size 64, I'd need 6 bits of entropy.

However, how many bits of entropy would I need to choose a random element from a list that's sized something other than $2^n$? For example, for a list of size 3, or 10?

My intuition says that I'd need to find $n$ such that $2^n$ is a multiple of list size, to ensure equal probability of selecting every item. (This is true for all lists sized $2^n$.) However, that doesn't seem to work in practice: there does not appear to be any $n$ such that $2^n$ that divides evenly into 3 or 10.

Answer 1

One can achieve this with a technique called Knuth Yao sampling. It:

1. Allows you to sample from any distribution $X$ of finite support (say where the function $f(i, s) = \text{the }i\text{th bit of }\Pr_X[X = s]$ is efficiently computable)
2. Using on average $\leq H(X) + 2$ bits of entropy, where $H(X)$ is the entropy of the distribution under consideration.

One can then replace $X$ with your distribution (say uniform on $3^n$ elements) to get the result. I'll quickly describe how Knuth-Yao sampling works for the rest of the answer.

Knuth Yao sampling works by constructing a certain (usually infinite) binary tree, and executing an unbiased random walk on it. Leaf nodes of the tree are labelled by elements on the underlying probability distribution, and when you hit a leaf node you terminate the walk and output that that element as your sample.

Why should this work? The basic idea is to put at leaf labelled $s$ at depth $i$ iff $f(i, s) = 1$. Then the following facts can be combined to show that the distribution of outputs of the sampler is precisely $X$:

1. The probability of reaching any particular node during an unbiased walk of a binary tree is $1/2^i$, where $i$ is the depth of the node
2. Therefore, the probability the sampler ends in a leaf labelled by $s$ at depth $i$ is $f(i, s)/2^i$ (if $f(i, s) = 0$, there are no such leaves, otherwise there is precisely 1).
3. The sampler can enter at most one leaf (it terminates after), so they form a set of independent events.

Then one has that:

\begin{align*} \Pr[\text{KY sampler outputs }s]&= \sum_{i = 0}^\infty \Pr[\text{KY sampler outputs }s\text{ in depth }i]\\ &=\sum_{i = 0}^\infty f(i, s) / 2^i\\ &= \Pr[X = s] \end{align*}

Showing that the average entropy usage is bounded by $H(X)+2$ requires a fairly careful argument, which you can find in Knuth and Yao's intial paper (which is actually quite hard to get ahold of, but can be found in one of Knuth's collections of selected papers (Selected Papers on Analysis of Algorithms, entry 34 The Complexity of Nonuniform Random Number Generation).

Answer 2

You would need $ \log_2 N$ bits of entropy. So from a formal point of view, from a list of 10 elements, you would need $3.321928$ bits of entropy.

However, if you actually want to fetch a random element (with an equiprobable probability) using N random bits, you will need a scaling.

A naive approach would be to fetch $n$ bits, obtaining $r \in [0, 2^n)$ and just fetching the element $r \pmod N$. This provides a random element, but not all elements are equally likely to be chosen.

An option would be to fetch element $r$ if $r < N$ and start again otherwise, although this is would be unbounded. A more optimal approach is described by Doctor Jacques on MathForum (credit goes to random.org FAQ 2.10 for finding the link), where you accumulate the remainder to form a new number, which requires less random bits, although still unbounded.

Answer 3

For example, for a list of size 64, I'd need 6 bits of entropy.

Yes, you simply need a random index for that, so $2^6=64$ seems right. However, that assumes that you can somehow map the bits of entropy directly to the bits making up the index, which is tricky to say the least if you have a number of bits larger than $n$ containing $n$ bits of entropy.

However, how many bits of entropy would I need to choose a random element from a list that's sized something other than $2^n$? For example, for a list of size 3, or 10?

You'd need a partial amount of random bits for that, as you need a random index in [0, 3) for a list with size 3 and [0, 10) for size 10. To be precise you'd need $\log_2n$ bits of entropy. Now the mapping gets even worse of course, unless your bits of entropy are in the form of a number within [0, 3) or well distributed in [0, x) where x is a multiple of 3.

However, that doesn't seem to work in practice: there does not appear to be any $n$ such that $2^n$ that divides evenly into 3 or 10.

Correct. So the best / usual way is to have, say 128 bits of entropy, feed it into a PRNG and then extract the random indices from that, e.g. using rejection sampling. That also remediates the problem having $n$ bits of entropy that isn't well distributed.

Answer 4

My intuition says that I'd need to find $n$ such that $2^n$ is a multiple of list size, to ensure equal probability of selecting every item.

First of all: The number of bits generated by some source of randomness is not necessarily an integer number.

Example: If you roll a dice $n$ times, you'll get $(n\log_2{6}) = 2.5849_\cdots n$ bits of randomness. This is an irrational number.

I'm sure that there are also sources of randomness in a computer system, which can be read by a software, that behave like the dice providing an irrational number of bits when being read.

However, how many bits of entropy would I need to choose a random element from a list that's sized something other than $2^n$?

Using a dice you could do this the following way: You want to pick one of 5 elements using a dice. You roll the dice. If the 6 falls, you roll the dice again. If the 6 falls again, you roll the dice a third time ... until the result is one of the numbers 1 to 5.

However, whatever you do, hypothetically you'll will require an infinite number of dice rolls if the number of list elements has other prime factors than 2 and 3. (In the example: If you always roll the 6, you will keep on rolling the dice endlessly.)

The same is of course true if your source of randomness returns $m$ instead of 6 different values (for example $m=2^n$): If the number of list elements has prime factors that $m$ does not have, you might require an infinite amount of random data (in the worst case) if you want to have exactly the same probability for all list elements.

Proof:

Let's say you found a method to select one list element by not reading more than $k$ elements from your source of randomness. (Example: You have found a method to select one list element using no more than $k$ dice rolls.)

Then you can simply continue reading data until $k$ elements are read. (Example: If you need less than $k$ dice rolls, you simply continue rolling the dice ignoring the result until you rolled the dice exactly $k$ times.)

This means that you also have a method to select one list element by reading exactly $k$ elements from the source of randomness.

However, after reading $k$ elements from the source of randomness, you have one of $m^k$ different results. (Example: After rolling the dice $k$ times, you have one of $6^k$ different results.)

If you select one of $i$ elements using a random number in the range $1_\cdots m^k$ and $m^k$ is not a multiple of $i$, not all elements in the list will have the same probability. If $i$ has prime factors $m$ does not have, $m^k$ cannot be a multiple of $i$.

However, that doesn't seem to work in practice ...

However, this is a hypothetical question, not a practical one:

In practice, sources of randomness are not ideal: If you use a dice (as an example), the probability will not be $\frac{1}{6}$ for each number, but it will be $\frac{101}{600}$ for one number and $\frac{99}{600}$ for another number.

The same is true for other sources of randomness: Sound cards, temperature sensors ... and whatever sources of randomness exist.

In practice, you would select one of 10 elements the following way if your source of randomness returns an integer number of bits:

Generate a number in the range $0_\cdots (2^{20}-1)$ and calculate modulo 10. Because $2^{20}\text{ mod }10 = 6$, the probability of the list elements $0_\cdots 5$ would be a little higher than for list elements $6_\cdots 9$ assuming an ideal source of randomness.

However, this effect is negligable when considering that the source of randomness is also not ideal.