About being able to sample a permutation of a finite set uniformly at random [closed]

Question

I was looking at this question.

• So if I understand the above discussion right then it concludes that if say one had access to an oracle which can uniformly at random sample from a finite set then one can't using this uniformly at random sample a permutation of another finite set (chosen may be adversarially) and also have the algorithm be guaranteed to halt.

  Is the above summary right? Is there a reference to a proof of the above?

• Is there a fundamental understanding of this impossibility?

• If one is allowed say (1) exponential space or (2) the oracle was picking the numbers with some bias then can we get across this impossibility?

• What are the consequences if hypothetically one could do the above?

Answer 1

Claim. Given access to finitely many samples of the uniform distribution over $\{1,\ldots,N\}$, you can sample uniformly from $\{1,\ldots,M\}$ iff $M \mid N^k$ (read: $M$ divides $N^k$) for some $k$.

Proof. Suppose first that $M \mid N^k$ for some $k$. Combine $k$ samples of $\{1,\ldots,N\}$ to get a uniform sample $x$ of $\{1,\ldots,N^k\}$, and return $x \pmod{M}$, which is understood to return a value in $\{1,\ldots,M\}$ rather than the more usual $\{0,\ldots,M-1\}$. There are exactly $N^k/M$ preimages of each $y \in \{1,\ldots,M\}$, namely $y,y+M,y+2M,\ldots,y+(N^k/M-1)M$. Therefore $x \pmod{M}$ is a uniform sample from $\{1,\ldots,M\}$.

Suppose next that using $k$ samples you can sample uniformly from $\{1,\ldots,M\}$. As before, we can think of the $k$ samples as a uniform sample from $\{1,\ldots,N^k\}$. Let $A$ be the preimage of $1$, that is the set of $x \in \{1,\ldots,N^k\}$ which cause the algorithm to return $1$. Since the algorithm returns $1$ with probability $1/M$, we must have $|A|/N^k = 1/M$ and so $|A| = N^k/M$, which can only happen if $M \mid N^k$. $\qquad\square$

Sampling a permutation on $M$ elements is the same as sampling a number in the range $\{1,\ldots,M!\}$. This is possible using finitely many samples from $\{1,\ldots,N\}$ if and only if $M! \mid N^k$ for some $k$.

This proof is quite elementary, so you can probably find many references, though none are really needed.

Answer 2

No, the summary is not correct. Your "if...then...." statement cannot possibly be correct, as we do know ways to sample a permutation of a finite set uniformly at random (under reasonable assumptions). For instance, one method is to repeatedly ($n$ times) sample without replacement. What that question is saying is that there is no number $t$ such that we can say with sure that the algorithm will terminate after at most $t$ steps; there will always be some tiny chance it takes longer than $t$ steps. However, the probability it will take longer than $cn^2$ steps (say) is exponentially small in $c$, so this is basically just a theoretical quibble -- for all practical purposes, the running time is $O(n^2)$.