9
$\begingroup$

If I have an one-bit uniform random generator, how can I use it to generate a permutation uniformly for the sequence {1, 2, ..., n}.

I have a solution: run the one-bit random generator n*n times to decide if each pair of elements will be exchanged.

The complexity is O(n*n).

I want to know if there more efficiency solution? What is the lower bound for this problem?

Improve this question
$\endgroup$
10
  • 6
    $\begingroup$ BTW I don't think this is research-level, sounds like a homework exercise $\endgroup$
    – Sasho Nikolov
    Commented Jun 30, 2012 at 18:31
  • 2
    $\begingroup$ There is no algorithm that generates a random permutation uniformly using at most $N$ bits that always succeeds (for every $N$ and $n > 2$). An algorithm can either generate a random permutation only approximately uniformly (with an arbitrary precision) or generate a random permutation truly uniformly but fail with some small probability. $\endgroup$
    – Yury
    Commented Jun 30, 2012 at 19:10
  • 2
    $\begingroup$ Downvoted for scope. $\endgroup$
    – Josephine Moeller
    Commented Jun 30, 2012 at 20:38
  • 4
    $\begingroup$ @JohnMoeller: Only if $n$ is a power of $2$, and this is the heart of the original question. You can't choose uniformly from $\{0,1,2\}$ with two coin flips. You can, however, choose uniformly from $\{0,1,2\}$ with 3 expected flips. $\endgroup$
    – Jeffε
    Commented Jun 30, 2012 at 22:47
  • 3
    $\begingroup$ @aelgundy: The statement "the lower bound is $O(n\log n)$" is formally meaningless. ("Up to 50% off or more!") You meant $\Omega(n\log n)$. $\endgroup$
    – Jeffε
    Commented Jun 30, 2012 at 22:48

1 Answer 1

Reset to default
22
$\begingroup$

Your solution does not work (or I don't understand it): the resulting permutation would not be uniformly random.

To Sasho Nikolov, this is a research topic and is actually the topic (among others) of a paper I have recently submitted, where I provide an optimal algorithm. I can give you an idea of the lower bound. Indeed, you would have to distinguish between n! different permutations, so theoretically you would need at least log2(n!) bits exactly. But Knuth and Yao show in their seminal paper ("The complexity of nonuniform random number"), that because of "rounding errors" (to simplify), the actually random-bit complexity is between log2(n!) and log2(n!) + 2, that those are the best bounds, and in addition they provide an exact expression in terms of entropy of the distribution (in this case the uniform distribution).

It can (and has) been shown that the exact complexity involves fluctuations periodic in log2(n), much like the average complexity of divide-and-conquer algorithms such as QuickSort. (Such details are routinely hidden by the traditional sledge-hammer approach known as the "Master theorem" :-).

The (optimal) expected number of random bits (y-axis) needed to distinguish between N (x-axis) choices.

Now, supposing you have your random number X, the bijection between the number and the corresponding permutation is a subproblem of what is more largely referred to as "unranking". Martinez and Molinero have devised a nice general framework based on a popular random generation framework introduced by Wilf and Nijenhuis and formalized by Flajolet et al.. But for permutations it is a much simpler problem: you consider the factorial-base expansion of X to get the random integers needed for the Fisher-Yates algorithm. See the following for more info:

http://en.wikipedia.org/wiki/Factorial_number_system

http://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle

EDIT: added the image which shows the optimal number of expected random bits needed to distinguish between N choices.

Improve this answer
$\endgroup$
5
  • $\begingroup$ I'll remove my downvote of the question when and if the question is edited. The system has locked in my vote otherwise. Good explanation. $\endgroup$
    – Josephine Moeller
    Commented Jul 1, 2012 at 3:04
  • 3
    $\begingroup$ This is a nice answer. Maybe I misunderstood the question. I suspected that the exact randomness needed is a non-trivial question, but my impression was that the OP was asking about an algorithm optimal up to constants (and with the caveats of approximate uniformity due to rounding as you and Yuri pointed out), which is easier. $\endgroup$
    – Sasho Nikolov
    Commented Jul 1, 2012 at 3:23
  • $\begingroup$ @SashoNikolov: understandable :-) this is a topic that interests me so I chose to answer without using the Big-O notations which the asker used suggesting he might only be interested in an order. I added a plot to show the fluctuations. $\endgroup$
    – Jérémie
    Commented Jul 1, 2012 at 3:48
  • $\begingroup$ I thought your answer had some great insight that I hadn't really cared to think about before. $\endgroup$
    – Josephine Moeller
    Commented Jul 1, 2012 at 21:39
  • $\begingroup$ The paper referenced was Optimal Discrete Uniform Generation from Coin Flips, and Applications, I’m guessing? $\endgroup$
    – jbapple
    Commented Oct 23, 2019 at 15:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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