Choosing a discrete non-uniform distribution for generating random integers

Question

I have a list $l$ containing integers in the range $[1,max]$

On list $l$ I do an operation $isPresent(x)$ which return true if x is present in $l$.

I generate $x$ using the function $nextX()$ which generates the next $x$ on the fly using some random distribution

List $l$ and function $isPresent(x)$ put together is a system where list $l$ is a customized data structure similar to a binary search tree and $isPresent(x)$ is a new a algorithm similar to a binary search algorithm which efficiently operates on the data structure.

I want to test the performance of this system against known search trees and search algorithms.

The current method I'm using to benchmark these systems is, I generate a random workload. I populate the list $l$ with uniform random numbers in the range $[1,max]$. Then I generate a uniform random number $x$ using $nextX()$ and pass it to the function $isPresent(x)$. I do $k$ such operations. Here the function $nextX()$ just calls $rand()$ to get the next random number.

What I wanted to try is a skewed workload. I tried to use Poisson distribution in $nextX()$ to generate $x$ (Using Poisson distribution to generate random integers) with $mu$ as max/1.1 but the standard deviation is small and the numbers generated are clustered close to $max$. I want to choose a discrete distribution other than uniform distribution but the values generated should roughly cover the whole range $[1,max]$

Another workload which I want to generate should have the below property.

The function $nextX()$ should return an integer in the range $[1,max]$. If I call $nextX$ function $k$ times, some of the $k$ integers should be random but there can be a period where some of them could be a sorted sequence (ascending or desending)

For example, if $max=32$, then calling $nextX()$ 18 times can return 17,11,23,5,7,17,23,30,2,31,17,1,19,14,8,6,5,2

Here the first 3 integers are random followed by a sorted sequence of random length 5, followed by a random sequence of integers of length 4 followed by a reverse sorted sequence of random length 6

I can achieve this by generating 18 sorted numbers and them randomly choosing number of partitions and on each partition I can randomly choose to shuffle them. But the problem with this is it needs lot of storage and the value of $k$ which represents the number of times the function $nextX()$ is invoked is very large so I want to generate this skewed distribution on the fly.

Background:

The reason I look to generate such a sequence is that an unbalanced binary search tree works well for random distribution as the height of the tree is close to $O(log(n))$. For sorted sequence the height can go as high as $O(n)$. In practice both are never the case. Workloads tend to be random with occasional sorted sequences interleaved.

Answer 1

Just throwing an idea out, but I guess you could try using something simmilar to a Hidden Markov model, or some kind of a mixture model.

In the case of the first workflow, you could for example get a set of standard distributions like poisson, binomial, uniform, geometric and so on. Then at each step you first randomly choose from which distribution you will draw at this step, and draw a sample from a chosen distribution. Of course you can have many copies of the same distribution in the set you're drawing from, but with different parameters (like many binomial distributions with different means). This should give you some more interesting multimodal distributions which are still easy to sample from.

In the case of the second workflow, maybe try something HMM-alike. Remember the state you're in (increasing sequence, decreasing sequence, random noise). At each step you jump from one state to other states with some probability (you can compute the stationary distribution of your markov chain to control how long on avarege you will stay in each state). If you're in random noise state, just choose the next sample from some distribution of your choice. If you're in "increasing" or "decreasing" states, draw a random positive number (probably from geometric or poisson distribution), and add or substract it from the previous one (this is why I said it's HMM-alike, not a HMM, the observations are not exactly conditionally independent).

Hope that helps, cheers.

Answer 2

Since under-dispersion is the primary reason the Poisson distribution doesn't fit your use, I'd suggest the negative binomial distribution. Once you determine the parameters that yield the rough shape you're looking for, it should be straight-forward to truncate the distribution's support to $[1, max]$ by setting $P(X = x) = 0$ for all integers outside of $[1, max]$, and $$\frac{f(x)}{\sum_{k=1}^{max}f(k)}$$ where $f$ is the PMF of the negative binomial.

You could use this distribution, I believe, to solve your second workload: Write truncatedNegBinom(min, max, params) such that it returns a random integer from a truncated negative binomial distribution like the above. Then write a second function randomSequence(length), e.g. in Python:

def randomSequence(length, mode = "random"):
    seq = []
    for i in range(length):
        if mode == "random":
            seq.append(truncatedNegBinom(1, max, params))
        if mode == "increasing":
            seq.append(truncatedNegBinom(seq[-1] + 1, max, params))
        if mode == "decreasing":
            seq.append(truncatedNegBinom(1, seq[-1] - 1, params))
    return seq

You'd also have to build in some exception handling, since the above would break when, for example, mode == 'increasing' and seq[-1] + 1 > max. For more on how to sample from an arbitrary discrete distribution, check this question.