Can I achieve weighted randomness with a function that returns weighted booleans?

I have a method that mimics an unfair coin. You can pass in a percentage, and it tells you whether or not you succeeded by returning a boolean. So if you call it with .25, it’ll return true 25% of the time.

I’m trying to figure out if I can use this function to create a weighted randomness function that works like this: There is a 25% chance it returns x, a 40% chance it returns y, and a 35% chance it returns z. This is just an example. I would want the function to work for an unlimited amount of letters, but the percentages added together should equal 1.

The trick is, I want to be able to think about it the way I just described above. In other words:

result = function ({.25, x}, {.4, y}, {.35, z})

result should be x 25% of the time, and so on. Can I implement this function with my unfairCoin?

---

Here’s how I worded it in a comment below.it might clarify what I’m asking for:

Correct my logic if I’m making a mistake here, but let’s say XY and Z all had .3333… Couldn’t I use my unfair coin to pass in .3333… If that returns true, that means you get X as a result. If it returns false, call my unfair again with .5 if that returns true, return Y, otherwise return Z. If that is correct, I don’t know how to get this working if the numbers AREN’T .3333 and if there’s more than three

Answer

If you have coins with a known probability of heads

Assume you have a function unfairCoin(p), which is a function that produces heads with a known probability p and tails otherwise. For example, it could be implemented like this:

function unfairCoin(p) {
   return Math.random() < p ? True : false;
}

Here is an algorithm that solves your problem given unfairCoin, assuming all the probabilities involved sum to 1:

1. Set cumu to 1.
2. For each item starting with the first:
   1. Get the probability associated with the chosen item (call it p) and accept the item with probability p / cumu (e.g., via unfairCoin(p / cumu)). If the item is accepted, return that item.
   2. If the item was not accepted, subtract p from cumu.

This algorithm’s expected time complexity depends on the order of the probabilities. In general, the algorithm’s time complexity is linear, but if the probabilities are sorted in descending order, the expected time complexity is constant.

EDIT (Jul. 30): As I’ve just found out, this exact algorithm was already described by Keith Schwarz in Darts, Dice, and Coins, in “Simulating a Loaded Die with a Biased Coin”. That page also contains a proof of its correctness.

---

An alternative solution uses rejection sampling, but requires generating a random integer using fair coin tosses:

1. Generate a uniform random integer index in the interval [0, n), where n is the number of items. This can be done, for example, using the Fast Dice Roller by J. Lumbroso, which uses only fair coin tosses (unfairCoin(0.5)); see the code below. Choose the item at the given index (starting at 0).
2. Get the probability associated with the chosen item (call it p) and accept it with probability p (e.g., via unfairCoin(p)). If the item is accepted, return that item; otherwise, go to step 1.

This algorithm’s expected time complexity depends on the difference between the lowest and highest probability.

Given the weights for each item, there are many other ways to make a weighted choice besides the algorithms given earlier; see my note on weighted choice algorithms.

Fast Dice Roller Implementation

The following is JavaScript code that implements the Fast Dice Roller. Note that it uses a rejection event and a loop to ensure it’s unbiased.

function randomInt(minInclusive, maxExclusive) {
 var maxInclusive = (maxExclusive - minInclusive) - 1
 var x = 1
 var y = 0
 while(true) {
    x = x * 2
    var randomBit = Math.random()<0.5 ? 1 : 0
    y = y * 2 + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - 1
      y = y - maxInclusive - 1
    }
 }
}

The following version returns a BigInt, an arbitrary-precision integer supported in recent versions of JavaScript:

function randomInt(minInclusive, maxExclusive) {
 minInclusive=BigInt(minInclusive)
 maxExclusive=BigInt(maxExclusive)
 var maxInclusive = (maxExclusive - minInclusive) - BigInt(1)
 var x = BigInt(1)
 var y = BigInt(0)
 while(true) {
    x = x * BigInt(2)
    var randomBit = BigInt(Math.random()<0.5 ? 1 : 0)
    y = y * BigInt(2) + randomBit
    if(x > maxInclusive) {
      if (y <= maxInclusive) { return y + minInclusive }
      // Rejection
      x = x - maxInclusive - BigInt(1)
      y = y - maxInclusive - BigInt(1)
    }
 }
}

If you have coins with an unknown probability of heads

If on the other hand, you have a function COIN that outputs heads with an unknown probability and tails otherwise, then there are two problems to solve to get to the solution:

1. How to turn a biased coin into a fair coin.
2. How to turn a fair coin into a loaded die.

In other words, the task is to turn a biased coin into a loaded die.

Let’s see how these two problems can be solved.

From biased to fair coins

Assume you have a function COIN() that outputs heads with an unknown probability and tails otherwise. (If the coin is known to have probability 0.5 of producing heads then you already have a fair coin and can skip this step.)

Here we can use von Neumann’s algorithm from 1951 of turning a biased coin into a fair coin. It works like this:

1. Flip COIN() twice.
2. If both results are heads or both are tails, go to step 1.
3. If the first result is heads and the other is tails, take heads as the final result.
4. If the first result is tails and the other is heads, take tails as the final result.

Now we have a fair coin FAIRCOIN().

(Note that there are other ways of producing fair coins this way, collectively called randomness extractors, but the von Neumann method is perhaps the simplest.)

From fair coins to loaded dice

Now, the method to turn fair coins into loaded dice is much more complex. It suffices to say that there are many ways to solve this problem, and the newest of them is called the Fast Loaded Dice Roller, which produces a loaded die using just fair coins (in fact, it uses on average up to 6 fair coin tosses more than the optimal amount to produce each loaded die roll). The algorithm is not exactly trivial to implement, but see my Python implementation and the implementation by the Fast Loaded Dice Roller‘s authors.

Note that to use the Fast Loaded Dice Roller, you need to express each probability as a non-negative integer weight (such as 25, 40, 35 in your example).