# Generate non-uniform random numbers

19 Sep 2018### 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:

### 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*):

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:

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*) :

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.