1
$\begingroup$

I have recently been working on some numerical algorithm that required me to pick a random element $r_i$ from a finite set $R$ with probability $p_i$. This is a fairly standard procedure and many programming languages have in-build methods that perform such sampling (e.g. sample(elements,probs) in Julia). My question is about alternative ways of performing this sampling and in what sense they are mathematically equivalent (if so), specifically in the language of information theory.

Consider, for instance, the following 2 algorithms for sampling from a set $R$ with probabilities $\{p_i\}$.

1 - order the elements of the set from $1$ to $N$ and construct cumulative probabilities $\rho_i$ accordingly (they are defined as $\rho_i = \sum_{j=1}^i p_i$). Now generate a random number $\epsilon$ in $[0,\rho_N[$ and find the cumulative probability larger than $\epsilon$ with lowest index. The element associated with that cumulative probability is our pick.

2 - pick one of the $N$ elements uniformly at random (call it $r_i$). Generate a random number $\epsilon$ in $[0,1[$. If $\epsilon \leq p_i/\max(\{p\})$, the site initially picked is our final pick. Otherwise, go back to the uniform random pick and repeat until the condition is satisfied.

The main differences I can see between the two methods are: a) the number of random numbers being generated, b) the second method involving the possibility of "throwing away" some of the elements picked until some condition is satisfied. I am particularly interested in the number of times the random number generator is called and the number of questions we have to ask about it (e.g. is it larger/smaller than something else).

Possible approach: in the language of information theory we can quantify the amount of information associated with random pick with probability $p_i$ by evaluating its information content $I_i = -p_i \log (p_i)$. I can see how the RNG calls we perform work as a sort of currency that we can spend by asking questions about the numbers being generated. For example, algorithm 1 involves the generation of a single random number and a series of yes/no questions each "producing" an amount of information smaller than or equal to $-\log(\rho_i)$ (depending on whether we have already asked some yes/no question about the number). I would expect that these contributions sum up to $-log(p_i)$ and to the entropy of the discrete distribution, on average. On the other hand, algorithm 2 involves a random pick from N equiprobable options, which corresponds to an information content of $-1/N \log (1/N)$. This "more infomation" than actually required to sample the (non-uniform) discrete distribution, so in the next step we "throw away" some of the information.

I am looking for a consistent language to make sense of the equivalence of these methods and the sense in which the RNG currency is "invested" in order to sample the distribution with the aim of expressing the efficiency with which different methods perform such activity.

$\endgroup$

1 Answer 1

2
$\begingroup$

You've described two commonly used techniques- the first one is the "inverse CDF technique" and the second one is an "acceptance-rejection technique." The inverse CDF technique needs only one uniformly distributed random number for each $X$ generated, while the second technique always needs at least one uniform random number and may end up using more of them (it's a good exercise to work out the expected number of tries until you accept the generated number- it will certainly be greater than one.)

In terms of calls to the random number generator, the inverse CDF method is clearly more efficient. However, depending on the expense of generating a uniform random number and the expense of finding $r_{i}$ in the first method, the inverse CDF method might require more computational effort.

There can be other important considerations in choosing between these methods. For example, the inverse CDF approach is much better suited for use within variance reduction schemes like Common Random Numbers (CRN) and Antithetic Variates (AV).

There are many textbooks that discuss these issues. I'd encourage you to look at the textbook on Simulating Modeling & Analysis by Law and Kelton.

$\endgroup$
2
  • $\begingroup$ Thank you for pointing me to the relevant literature, I had only come across these two alternative techniques in this paper by P. Hanusse. I will look into the reference you provided with attention. However, I should point out that my question was about the sense in which two approaches to sampling are mathematically (perhaps information-theoretically) equivalent, rather than the specific characteristics of each such approach. Anyway, Law and Kelton may hold the answer. $\endgroup$
    – Ludens
    Commented Sep 3, 2018 at 14:03
  • $\begingroup$ Yes, you'll find derivations of the method in the textbook by Law and Kelton. $\endgroup$ Commented Sep 3, 2018 at 15:07

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .