Let $[n] = \{1, 2, \dots, n\}$. Suppose we have a subset $S$ of $[n]$ of size $k$.

Can we sample one element uniformly at random from $[n] \setminus S$ in $O(k)$ time?

It's okay to use $O(n)$ auxiliary memory assumed to be initialized with zeros, as long as your algorithm can run and clean up back to the initial zero state all in $O(k)$ time.

  • $\begingroup$ It should be clearer if the problem is stated as, "Let $[n] = \{1, 2, \dots, n\}$. Suppose we have a subset $S$ of $[n]$ of size $k$. Assume we can test whether a number is in $S$ in $O(1)$ time (For example, when $S$ is given as a hashset). Can we sample one element uniformly at random from $[n] \setminus S$ in $O(k)$ time?". There is no need to involve the "reversible" business, which is not very well-defined here, anyway. $\endgroup$
    – John L.
    Dec 24 '20 at 5:15
  • $\begingroup$ @JohnL. How is it not well-defined? E.g. it works for my answer where we can initialize some buffer $A[i] = 0$ for $|A| = n$ once, and then for every call of the algorithm we set $A[i] = 1$ for $i \in S$ before the algorithm starts, giving us $A[i]$ as our $O(1)$ check, and then reverse back to the initial state by setting $A[i] = 0$ for $i \in S$. $\endgroup$
    – orlp
    Dec 24 '20 at 13:15
  • $\begingroup$ what I meant is that "algorithm reversible in $O(k)$" is not a common term. It is not immediate clear how to properly define "reversible" in formal terms. For example, how should memory usage be restricted when we try to return to "some specified initial state" (or is it "the given initial state"?). When it is OK to use $O(n)$ memory, does it include input memory or not? It occurs to me that my statement of the problem is clearer in precondition without the clutter of "reversible". $\endgroup$
    – John L.
    Dec 24 '20 at 19:34
  • $\begingroup$ Even if we can define "reversible" in formal terms, it is hardly necessary here. $\endgroup$
    – John L.
    Dec 24 '20 at 19:39
  • $\begingroup$ "we can initialize some buffer $A[i]=0$ for $|A|=n$ once". Is the following algorithm allowed? Initialize a 1-indexed buffer $B$ for $|B|=n-k$ by the following procedure once. Initialize $i$ and $j$ to 1. While $j \le n$, do the following two operations. First, if $j\not\in S$, let $B[i]=j$; else increase $i$. Second, increase $j$ by 1. Once that initialization is done, sampling is easy. Sample a random integer $q$ from $[n-k]$. Return $B[q]$. (The initialization of an all-zero buffer of size $n$ takes $O(n)$ time by most of today's computers, I believe.) $\endgroup$
    – John L.
    Dec 24 '20 at 20:05

Yes actually, and it's quite simple.

  1. Sample a random integer $q$ from $[n-k]$.
  2. Initialize $c = |\{x \in S \mid x \leq q\}|$.
  3. While $c > 0$, let $q \leftarrow q + 1$ and if $q \notin S$ decrement $c$.
  4. Return $q$.

This works because steps 2 and 3 forms a bijective mapping from $[n -k]$ to $[n] \setminus S$. Finally the algorithm runs in $O(k)$ because it's possible to check if $q \notin S$ in $O(1)$ time either by using a $O(n)$ memory bitset or a hash table and both steps $2$ and $3$ take at most $k$ steps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.