# Alternative ways of sampling from a distribution

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.

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.