Random functions typically assign the same priority to each possible choice. In some cases, though, you want to be able to make a random choice while prioritizing some options. For instance, in Project Thoth, we need to prioritize more recent releases of Python packages. We use pseudorandom number calculation to prioritize newer libraries in the exploration phase of Thoth's reinforcement learning algorithm.
This article explores termial random, a specific type of pseudorandom number calculation used in Project Thoth. We'll use the termial-random number generator to select an item from a list, assign the highest probability to the item at index 0, then assign lower probabilities to the following items as the index increases. You can apply the discussion and resources in this article to other Python projects.
Pseudorandom number generation in Python
The Python standard library offers several functions for pseudorandom number generation. For instance, if we want to pick an item randomly from a list, the random.choice method works well:
import random
my_list = [42, 33, 30, 16]
# results in 42 with a probability of 1 / len(my_list)
random.choice(my_list)
Now, let’s say we want to give higher numbers a higher probability of being chosen. In other words, in the my_list example, we want to prioritize 42 over 33, 33 over 30, and 30 over 16.
Weighted random choice in Python
We have four numbers in total in our list, so let’s assign weights to these numbers as shown in Table 1.
| Number | Weight |
|---|---|
| 42 | 4 |
|
33 |
3 |
| 30 | 2 |
| 16 | 1 |
You can think of each weight as a number of "buckets" assigned to the number. In a randomly uniform way, our algorithm tries to hit one bucket. After hitting the bucket, we check which number the bucket corresponds to.
The total number of buckets we can hit is equal to the sum of the weights:
4 + 3 + 2 + 1 = 10
Table 2 shows the probability of hitting each number, based on the buckets assigned to it, where all probabilities total up to 1.0.
| Number | Probability |
|---|---|
| 42 | 4 / 10 = 0.4 |
| 33 |
3 / 10 = 0.3 |
| 30 | 2 / 10 = 0.2 |
| 16 | 1 / 10 = 0.1 |
Termial random number calculation
To generalize this prioritization for n numbers, we can create the following formula that computes the total number of buckets to use for any n:
n? = 1 + 2 + 3 + ... + (n - 2) + (n - 1) + n
We could also write this formula as shown in Figure 1.
The formula is called a termial as an analogy to factorials. The concept is related to triangular numbers.
Computing the termial of n
To compute the termial of n in Python, the simplest implementation is:
termial_of_n = sum(range(1, len(my_list) + 1)) # O(N)
A more efficient calculation uses the binomial coefficient and computes (len(my_list) + 1) over 2:
l = len(my_list)
# (l + 1) over 2 = l! / (2!*(l-2)!) = l * (l - 1) / 2
termial_of_n = ((l*l) + l) >> 1 # O(1)
Finally, we can pick a random (random uniform) bucket from our set of buckets:
import random
choice = random.randrange(termial_of_n)
The result, stored in the variable choice, holds an integer from 0 to 9 (inclusively) and represents an index into the list of the buckets we created earlier, as shown in Table 3.
| Choice | Bucket | Number |
|---|---|---|
| 0 | 1 | 42 |
| 1 | 2 | 42 |
| 2 | 3 | 42 |
| 3 | 4 | 42 |
| 4 | 5 | 33 |
| 5 | 6 | 33 |
| 6 | 7 | 33 |
| 7 | 8 | 30 |
| 8 | 9 | 30 |
| 9 | 10 | 16 |
Termial random with the binomial coefficient
Now, how do we find which number we hit through a randomly picked bucket for any n? Let’s revisit how we computed the termial number of n using the formula based on the binomial coefficient:
l = len(my_list)
termial_of_n = ((l*l) + l) >> 1
Following the definition of the termial function, we know that regardless of n, we always assign one bucket to the number at index n-1, two buckets to the number at index n-2, three buckets to the number at index n-3, and so on, down to the index 0. Using this knowledge, we can transform the binomial coefficient formula to the following equation:
choice = ((i*i) + i) >> 1
The next step is to find i that satisfies the given equation. The equation is a quadratic function described as:
a*(i**2) + b*i + c = 0
The values of our coefficients are:
a = 1/2
b = 1/2
c = -choice
Because choice is expected always to be a non-negative integer (an index into the list of buckets), we can search for a solution that always results in a non-negative integer (reducing one discriminant term that always results in negative i):
import math
# D = b**2 - 4*a*c
# x1 = (-b + math.sqrt(D)) / (2*a)
# x2 = (-b - math.sqrt(D)) / (2*a)
# Given:
# a = 1/2
# b = 1/2
# c = -choice
# D = (1/2)**2 + 4*0.5*choice = 0.25 + 2*choice
i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
The solution has to be rounded using math.floor because it corresponds to the inverted index with respect to n. Because i is inverted, the final solution (index to the original list) is:
my_list[n - 1 - i]
Running the termial-random number generator
Now, let's do the asymptotic complexity analysis, assuming that:
- The
lenfunction can return the length of the list in O(1) time. random.randrangeoperates in O(1) time.- We use the equation based on the binomial coefficient to compute the termial of n.
The whole computation is done in O(1) time and O(1) space.
If we used the sum-based computation of the termial of n, the algorithm would require O(n) time and O(1) space.
The final source code in Python is:
import random
import math
def random_termial(n: int) -> int:
termial_of_n = ((n * n) + n) >> 1
choice = random.randrange(termial_of_n)
i = math.floor(-0.5 + math.sqrt(0.25 + (choice << 1)))
return n - 1 - i
Figure 2 shows the number of hits for n=10 when the termial random generator was run one million times:
The chart shows that, just as we want, index 0 is prioritized most of the time; after that, index 1 is prioritized, and so on. The lowest priority is given to the index 9.
Where to find the termial-random package
The Project Thoth recommendation engine is available in a component called adviser and uses a C extension that implements the termial random calculation. The C extension is available on PyPI as the termial-random package and the source code is hosted in the thoth-station/termial-random repository.
Conclusion
As part of Project Thoth, we are accumulating knowledge to help Python developers create healthy applications. If you would like to follow updates in Project Thoth, feel free to subscribe to our YouTube channel or follow us on the @ThothStation Twitter handle.
Last updated: October 6, 2022