Literature or references on the method

[adomasbaliuka]

Hi, thanks for making this work available!

I'm interested in the coding method you are using. You explain the principle in the README but don't give any references. Are there books/papers/blogs etc. that explain this method in more detail? Does it have a standard name?

I'm also looking at methods related to, e.g., arithmetic coding, to solve similar problems and was wondering how your methd compares.

Thanks a lot!

Just in case you're interested, the problem I'm trying to solve is very closely related. My distribution is not just over two symbols ('0', '1'), but rather over a small set of symbols, e.g., ('00', '01, '10', '11'). I again want to draw large byte-packed blocks from this distribution. Can your method can be adapted/generalized to such a situation?

[daskol]

Thanks for comments. Highly appreciate your interest.

The issue is that the method implemented here is quite naive and reuse some properties of PRNGs. Also, it is mainly focused on fast generation with SIMD instructions and JITed code with LLVM. So, you should likely use generic implementation, TensorFlow/PyTorch or any other library for scientific computations.

Briefly, the method uses all random bits to generate binary variable. So, it is fast but depends on properties of PRNG. It works good enough for my purposes since I needed a lots of samples but quality was not an issue.

In the case of generation of 'binary words' this library can be extending with taking n bits from random source instead of 1 bit per step.

[adomasbaliuka]

Thanks for your answer! I ended up going with a different library (Fast Loaded Dice Roller, from MIT, which is much slower unfortunately) because for me using randomness efficiently is quite important (your approach seems to be extremely fast but wasteful in terms of input randomness).

To make this repository easier to use for others, my recommendation would be to give a small example in the README illustrating the working principle of this method to make it easier to understand (I had to read the C++ code until I understood what the README said). From you answer, I understand that there is no literature one could cite for this method of sampling.

From what I saw in your code, the idea is to write the target binary random variable to be sampled as an algebraic expression (using logical and, negation, potentially logical or) of a number of uniform input binary variables. For example, if Bernoulli(1/8) is required, you take iid random inputs r1, r2, r3 ~ Bernoulli(1/2) and compute target = r1 & r2 & r3 thereby using 3 bits to get one sample from Bernoulli(1/8). When p is not a power of 2, it's possible to do it when also using negation, in addition to logical and.

The Shannon entropy of Bernoulli(1/8) is around 0.54 bits, which means that it's possible to sample from the distribution using around 0.54 bits of random input on average, at least when you need a lot of samples, while your method would always use 3 bits for each sample.