1
$\begingroup$

It's well known that a simple but efficient random shuffle algorithm
can permute a vector of $n$ elements in $O(n)$ time.

In the algorithm, we need to pick a value $U$ uniformly at random where $0\leq U\leq 1$.

However, I need a pseudorandom function (or algorithm) so I can re-generate the same permutation over again. ​ Thus, I need to use a pseudorandom function to generate $U\hspace{-0.02 in}$. ​ But the pseudorandom functions usually output an integer but not value $U\hspace{-0.02 in}$, where $0\leq U\leq 1$.


Question: ​ How can we turn the random shuffle into a pseudorandom shuffle?

or

How can we map the output of pseudorandom function to a value in the interval $(0,\hspace{-0.05 in}1)$
such that the value in that range still is a pseudorandom value?

$\endgroup$
  • $\begingroup$ We can do that the exact same way we can do it with a truly random integer. ​ ​ $\endgroup$ – user991 Feb 29 '16 at 13:47
  • $\begingroup$ @RickyDemer It might look trivial to you. But, how can we do it with a cryptographic pseudorandom function (PRF)? The PRF outputs a big integer that is not in range $(0,1)$. Am I missing something? $\endgroup$ – user153465 Feb 29 '16 at 13:50
  • $\begingroup$ We can do it the same way we can do it with a truly random function. ​ ​ (pseudorandomness is completely irrelevant to that.) ​ ​ ​ ​ $\endgroup$ – user991 Feb 29 '16 at 14:00
  • 1
    $\begingroup$ You get $N$ bits $b_1b_2\cdots b_N$ from your pseudorandom generator; if you want a number $U \in [0,1]$ in decimal form, just convert $0,b_1b_2\cdots b_N$ into a decimal number. $\endgroup$ – Geoffroy Couteau Feb 29 '16 at 14:31
  • 2
    $\begingroup$ @RickyDemer: you've missread my comment. I've not written "treat $0,b_1b_2\cdots$ as a decimal number", which would obviously not produce numbers larger than $1/9$, but "convert it into a decimal number". $\endgroup$ – Geoffroy Couteau Feb 29 '16 at 15:58
2
$\begingroup$

It is not possible to generate uniform real number of infinite precision. Therefore, it is not possible to pick a random value $U$ arbitrary precision uniformly at random so that $0 \le U \le 1$, and that any number in the range is possible.

Instead, it is (typically) necessary to generate sequence of uniformly random bits and interpret them as floating point number. For instance, you may generate 32 random bits and represent them as integer and divide the result with 4294967295. [Exception: Some sources have range that is not binary, like ideal dice. They still have limited precision.]

This part actually works the same regardless of if you had truly random source or if you used pseudo random number generator capable of generating bits to generate your random numbers.

However, Fisher-Yates shuffle or Richard Durstenfeld shuffle algorithm you linked to actually does not need arbitrary precision random numbers. It need random numbers, which are in range $0 \le j \le i$. These in theory can be derived from random and uniform arbitrary precision float number between [0, 1), but in practice, you instead need to generate bits (as described above) and use them to select array element to shuffle. Because the range is not always power of two, it is often necessary to use algorithm, which can convert numbers to specific range without generation of bias. FIPS 186-4 provides some algorithms useful to convert bits to arbitrary integer range. See Appendix B.2.1 and B.2.2 for two choices: allowing some bias or testing candidates and rejecting out of range values.

$\endgroup$

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.