1
$\begingroup$

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?

$\endgroup$

closed as unclear what you're asking by Luke Mathieson, D.W., Raphael Apr 7 '15 at 7:41

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 1
    $\begingroup$ Please restrict yourself to one question per post. Note also that the second question you pose is rather broad/unclear. $\endgroup$ – Raphael Apr 7 '15 at 7:40
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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)$.

$\endgroup$

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