5
$\begingroup$

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.

$\endgroup$
6
  • 3
    $\begingroup$ In practice, if random bits are cheap, you'd just sample from a list of 4 or 16, and if the sample is outside the list bounds, try again. $\endgroup$ – user253751 Sep 1 '20 at 10:24
  • $\begingroup$ @Philip "how many" on average or worst case? $\endgroup$ – ngn Sep 1 '20 at 13:47
  • $\begingroup$ @ngn worst case. :) $\endgroup$ – Philip Sep 1 '20 at 17:35
  • 2
    $\begingroup$ @Philip bad news then: all answers are wrong and the number of bits you need is potentially infinite $\endgroup$ – ngn Sep 1 '20 at 18:19
  • 1
    $\begingroup$ It's infinite if you need perfectly uniform sampling. If you're ok with a tiny amount of non-uniformness, then you can limit it to a relatively small number, depending on how non-uniform is ok. $\endgroup$ – Mooing Duck Sep 1 '20 at 19:26
7
$\begingroup$

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).

$\endgroup$
5
$\begingroup$

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 \ mod \ 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 http://mathforum.org/library/drmath/view/65653.html (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.

$\endgroup$
2
  • 1
    $\begingroup$ Your answer suggests that the number of bits of entropy are well distributed in a same size number of bits (which could be true, or not). Otherwise, the final part describes rejection sampling. You might be interested in my RNG-BC which uses a bitwise method of minimizing the amount of random bits required using rejection sampling, by the way (shameless plug). $\endgroup$ – Maarten Bodewes Sep 1 '20 at 0:08
  • $\begingroup$ I guess your project is similar to what Jacques decribed on that post. I implemented something like that ~7 years ago, although your implementation might be bette And yes, I was assuming those are "well-distributed random bits". $\endgroup$ – Ángel Sep 1 '20 at 0:34
2
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ This answer should emphasize two caveats --- 1. You only require an infinite amount of entropy in the "worst case". There are quite efficient techniques with good "average case" entropy usage (although the difference between worst case entropy usage and average case entropy usage can become a side channel, so should be thought about carefully). $\endgroup$ – Mark Sep 1 '20 at 19:47
  • $\begingroup$ 2. You can reduce the infinite amount of entropy usage to an arbitrary finite number by approximating the distribution you're sampling from. In particular, for any distribution $X$ and $\lambda \in\mathbb{N}$ there exists a distribution $\tilde{X}$ such that $\Delta(X, \tilde{X}) \leq |\mathsf{supp}(X)|/2^\lambda$, and sampling from $\tilde{X}$ requires (worst case) $\lambda$ bits of entropy. Technically the term $|\mathsf{supp}(X)|$ is actually "the number of elements of $X$ that occur with probability $>2^{-\lambda}$, and you can $\endgroup$ – Mark Sep 1 '20 at 19:48
  • $\begingroup$ get the distribution $\tilde{X}$ by truncating a fixed-precision representation of the probabilities of elements in $X$. $\endgroup$ – Mark Sep 1 '20 at 19:48
  • $\begingroup$ @Mark Thanks for the clarification. (My native language is not English, so) I understood the question in a way that the user is asking for the "worst case" number of bits required, not for the "average" number of bits required. $\endgroup$ – Martin Rosenau Sep 2 '20 at 5:52
  • $\begingroup$ No problem. As mentioned, via truncation you can still get worst-case finite results. There are actually a few ways to cut down the number of random bits needed worst-case that I'm vaguely in the process of writing up, but nothing ready for eprint now. $\endgroup$ – Mark Sep 2 '20 at 14:50

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.