Generate non-uniform random numbers

Problem statement

Write a function that takes two arguments, an array of numbers (to choose from) and an array of doubles (probability of each choice), and produces non-uniform random number (eq. chosen from the first array) according to the corresponding probability in the second array.

EXAMPLE:

  Input: s = [3,5,7,11], p = [9/18,6/18,2/18,1/18]

  Output: 3 (5, 7 or 11)

Solution

Here is the actual code of the algorithm that implements a solution of a non-uniform random generator to yield next number using the specified sequence of possible numbers and list of probabilities:

/// Generates a non-uniform random number from the specified sequence
/// and using the specified probability.
///
/// - Parameter s: A sequence to generate numbers from.
/// - Parameter p: A specification (eq. probabilities) for the random generator.
public func next(s: [Int], p: [Double]) -> Int {
    // Prepare state of the algorithm
    var sum = 0.0, seq = [Double](repeating: 0, count: p.count)
    // Compute a list of endpoints from the original specification
    for i in 0...p.count - 1 {
        // Define the current endpoint's boundary
        seq[i] = sum
        // Update boundary of the next endpoint
        sum += p[i]
    }
    // Generate random double number from the specified range 
    let rx = Double.random(in: 0...1)
    // Search for the closest endpoint using approximation 
    let nx = search(seq, rx)
    // Here is our answer
    return s[nx]
}

Following is a helper function that implements binary search algorithm to find an answer using approximation technique, eq. if the specified value doesn’t have an exact match the algorithm choses an element that is closest to the one being searched for:

/// Binary search implementation with quirks, eq. returns either
/// the exact match or the closest element within the specified
/// range (approximation).
///
/// - Parameter seq: A sequence used to search for the specified value.
/// - Parameter v: An actual value to search for in the sequence.
func search(_ seq: [Double], _ v: Double) -> Int {
    // Prepare state of the algorithm
    var lo = 0, hi = seq.count - 1
    // Keep iterating while operating within the boundaries
    while hi >= lo {
        // Compute position & query value of the element in the middle
        let mid = lo + (hi - lo) / 2, vv = seq[mid]
        // Is this an exact match?
        if vv == v { return mid }
        // Swith to the left part of the sequence
        if vv > v { hi = mid - 1 }
        // Switch to the right part of the sequence
        else { lo = mid + 1 }
    }
    // Choose the closest approximate element in the sequence
    return min(lo, abs(hi))
}

Following is an example that the code performs as advertised and establish a baseline for any improvement work in the future:

Generate non-uniform random numbers test assertions

Bits & pieces

This coding challenge introduces a few very interesting techniques that implement core parts of the algorithm that generates non-uniform random number according to the specification provided by the user.

Lets get started!

The first statement initializes sum and seq variables that are used to translate sequence of probabilities into a sequence of intervals (eq. endpoints) in 0...1 range:

// Prepare state of the algorithm
var sum = 0.0, seq = [Double](repeating: 0, count: p.count)

Next snippet is a loop to iterate over the probabilities, convert each into an interval and save it into seq variable that keeps intervals of the computation:

// Compute a list of endpoints from the original specification
for i in 0...p.count - 1 {
    ... inner block of code ...
}

Following statement, the first in the loop to save current value of sum into seq array of intervals:

// Define the current endpoint's boundary
seq[i] = sum

This statement, last in the intervals translation loop, adds the current probability to sum variable to make it into an interval (eq. previous interval is followed by the next one):

// Update boundary of the next endpoint
sum += p[i]

Following picture is a visual representation of how seq variable would look like after the transformation is completed for the input specified in the original example (big dots happen to be the endpoints of the intervals and values of seq):

Non-uniform random number specification

Now, to help you understand better how these somewhat abstract intervals can be translated into an actual choice that the generator would have to make when invoked, here is another imagery that maps every interval into the corresponding number from the original number sequence:

Number sequence random generator view

Next statement generates a random number with floating point in 0...1 range (inclusive) that represents our generator’s choice of the next randomly chosen number and since our constraint is to provide non-uniform random number we make it biased towards the interval it corresponds to:

// Generate random double number from the specified range 
let rx = Double.random(in: 0...1)

For the sake of clarity, lets make an assumption that this time rx variable has been populated with the value of 0.375 and the next picture outlines how our non-uniform random number generator would make a decision about which number (in this case 3) to return based on the current value of rx variable (marked by big red dot) :

How generator makes decision to pick a number

Following statement performs a binary search using the helper function that either returns the exact match or an element that is the closest to the value being searched:

// Search for the closest endpoint using approximation 
let nx = search(seq, rx)

Finally, once the index of corresponding interval is found, it is now time to return the answer to the calling code that corresponds to the next non-uniform random number chosen by our generator:

// Here is our answer
return s[nx]

That’s all folks! 🍯

Here is a Swift playground for this article at Github: Generate non-uniform random numbers.