tgen::miniblog(1): uniform generation implies distinct generation

This is a blog 1 of a series of blogs about algorithmic challenges I came across when creating tgen.

In this blog we will tackle:

1. Generate $k$ uniformly random distinct integers in the range $[\text{left}, \text{right}]$;
2. Generate $k$ uniformly random distinct strings with $n$ characters in $[\texttt{a}, \texttt{z}]$.

Let’s assume we have a function next(left, right), which I will call the inner generation, that returns a uniformly random integer in the range $[\text{left}, \text{right}]$. A trivial algorithm is:

std::vector<int> seq;
std::set<int> s;
while (s.size() < k) {
    int x = next(left, right);
    if (s.insert(x).second)
        seq.push_back(x);
}
return seq;

Algorithm 1: distinct generation.

Surprisingly, this simple algorithm is both uniform and fast.

It is easy to see that this algorithm returns a uniform sequence of $k$ distinct integers in the range, that is, every sequence of $k$ distinct integers in the list is equally likely to be generated (the proof is left as an exercise).

However, bounding the time complexity is a little more involved. If $k$ is relatively small compared to the total number of elements, we can expect this to be fast. But there is actually a worst-case expected bound we can prove without that assumption.

Theorem 1: Algorithm 1 runs in $\mathcal O(T \cdot k \log k + k \log^2 k)$ expected time, if the inner generation is uniform and takes $\mathcal O(T)$ time.

Proof: Let $N$ be the total number of elements that can be generated (in our example, $N = \text{right} - \text{left} + 1$). Let’s try to bound the number of iterations $L_i$ required for the $\texttt{while}$ loop when the set has $i$ elements ($0 \leq i \lt k$). On that moment, the probability of generating a new element is

assuming our generation is uniform (out of $N$ possible values, $N - i$ yields a new one). Since draws are independent, we can calculate the expected value $\mathbb E[L_i]$ in the following way. We either succeed in the first try (1 iteration), with probability $p_i$, or we fail and need to repeat (1 extra iteration), with probability $1 - p_i$. So the expected value must satisfy:

Solving for $\mathbb E[L_i]$, we get

Adding the expected cost for every $0 \leq i \lt k$, we get

This last inequality is implied from $k \leq N$. Finally,

This last identity is well known from the harmonic series. To finish off, each iteration of the $\texttt{while}$ loop has cost $\mathcal O(T + \log k)$, from generating plus the binary search tree. Multiplying by that, we get the final time complexity.

What this means for us is: if we have any universe set $U$, as long as we have an algorithm to generate a uniform element from $U$ in $\mathcal O(T)$ time, we can easily create an algorithm that generates distinct elements from $U$, and each generated element will have amortized expected cost $\mathcal O(T \cdot \log k + \log^2 k)$, if $k$ distinct elements will be generated in total.

In other words, uniform generation implies distinct generation, with only a logarithmic factor overhead. Pretty cool, right?

Finally, we address problem (2). We can use the same strategy, and the inner generation will just be a for loop that chooses each character from $[\texttt{a}, \texttt{z}]$ independently. The amortized expected time complexity for generating each string will then be $\mathcal O(n \log k + \log^2 k)$.

References

Coupon collector’s problem: https://en.wikipedia.org/wiki/Coupon_collector%27s_problem