Convert non-uniform pseudorandom generation to uniform?

user_8153553 0
Viewed 132

Lets say I have a function which is non uniform and generates elements in the set A. I have a set B that has the probability of generation of each element in A. Is there any way I can make the non uniform pseudorandom function behave like a uniform pseudorandom function.

math random optimization algorithm
2 Answers

Sure. An easy way to generate an element from A with uniform probability:

  1. Assign a number to each element of A
  2. For each element of A, generate a corresponding random element, and note its corresponding number
  3. Select the element of A with the smallest random number. If there's a tie, repeat with the elements that are tied for first.

An efficient way is to encode a stream of random (non-uniform) elements with a range coder according to the given probabilities. This will generate a stream of uniform random bits. You can then decode this assuming equal probabilities for all symbols to get uniformly distributed elements of A. See: https://en.wikipedia.org/wiki/Range_encoding

Another way to generate the uniform random stream of bits is to calculate the entropy of your random source, and then divide the output into chunks and hash with a cryptographic hash function like SHA-1. The chunks should be big enough to provide more bits of entropy than the bit length of the hash function. This method could be safer in real life, because it works even if you are wrong about the symbol distribution produced by your generator. See: https://en.wikipedia.org/wiki/Entropy_(information_theory)

user_54835260

Let me suggest a simple algorithm, where you don't need to know the probabilities that each element in A is chosen (set B in your question). I assume that each element in A has a known order (for example, each element is a number).

There are two parts to the algorithm. The first is an algorithm to generate unbiased random bits. We'll call it "RandomBit()" (Morina et al. 2019).

  1. Draw one independent element from A, call it X, and then draw another independent element from A, call it Y.
  2. If X is less than Y, return 0. If Y is less than X, return 1. If neither is the case, go to step 1.

This works because independent pairs of independent draws from A are statistically indifferent (Montes Gutiérrez 2014, De Schuymer et al. 2003); see the appendix to my Note on Randomness Extraction for details.

Next is an algorithm to generate a uniform random number in [0, 1]. All you have to do is "juxtapose enough random binary digits" (von Neumann 1951): Add RandomBit()/2 + RandomBit()/4 + RandomBit()/8 + ....

If your non-uniform distribution is the normal distribution, see the following question on Cross Validated for further tricks: https://stats.stackexchange.com/questions/117689

REFERENCES:

  • Von Neumann, J., "Various techniques used in connection with random digits", J. Res. Nat. Bur. Stand. Appl. Math. Series 3, 36-38 (1951).
  • Morina, G., Łatuszyński, K., et al., "From the Bernoulli Factory to a Dice Enterprise via Perfect Sampling of Markov Chains", arXiv:1912.09229 [math.PR], 2019.
  • Montes Gutiérrez, I., "Comparison of alternatives under uncertainty and imprecision", doctoral thesis, Universidad de Oviedo, 2014.
  • De Schuymer, Bart, Hans De Meyer, and Bernard De Baets. "A fuzzy approach to stochastic dominance of random variables", in International Fuzzy Systems Association World Congress 2003.
user_8157240
Related