So this is sort of a general question but I'll limit the discussion to randomized quicksort to make it clear. Suppose generating "true" random bits is hard, e.g. because it requires measuring something in nature that can be considered essentially "random" like the 50th binary digit after the decimal point in wind speed at some location recorded in miles per hour. Or maybe quantum outcomes observed that can be considered truly random. Whatever. So we do the following: We generate $k$ "truly" random bits and then we re-use these $k$ bits over and over by using a pseudo-random number generator to permute them. In terms of $k$ (the number of initial truly random bits) and in terms of the total count of numbers to be sorted, $n$, and assuming the permutation algorithm of the $k$ initial random bits repeated over and over is known to an adversary, can we assert that an algorithm like quicksort will have good worst-case expected running time, assuming that "random" bits are used in the algorithm in the natural way to choose a pivot? How do $k$ and $n$ play into the worst-case expected running time? If we need $k = \Omega(n \log n)$ initial truly random bits to assure good worst case expected running time, that isn't very interesting. But maybe we can do somewhat ok with asymptotically fewer initial random bits?
-
1$\begingroup$ The idea of taking a relatively small number of random bits and "stretching" them into a longer pseudorandom sequence has definitely been studied. Unfortunately, it's not my field and I can't remember what it's called. $\endgroup$– David RicherbyMay 21, 2015 at 23:35
-
$\begingroup$ Are you asking about theoretical results (what we can prove?) or practical techniques (what will work well in practice, even if we can't prove it?)? The answer will differ according to which you want to know about. $\endgroup$– D.W. ♦May 22, 2015 at 6:12
-
$\begingroup$ @D.W. Empirical results may be interesting and suggest what types of theoretical results can be proven, but I posted in this forum because I'm most interested in the theoretical results, whether they are proven or well-formulated and empirically supported conjectures. $\endgroup$– user2566092May 22, 2015 at 19:57
-
$\begingroup$ OK. Well, in practice, if you have a small random seed (160 bits of true, uniformly random bits), you can stretch it into an arbitrarily long stream of pseudorandom bits that are good enough for use with any randomized algorithm. So, in practice, all you need is 160 bits of randomness; using crypto-strength PRNGs, you can stretch this to an unlimited number of bits that are indistinguishable from truly random (though we can't prove it works). See cs.stackexchange.com/a/41723/755 and cstheory.stackexchange.com/a/29130/5038 and cstheory.stackexchange.com/q/27974/5038. $\endgroup$– D.W. ♦May 23, 2015 at 2:33
2 Answers
The question you're asking deals with the topic of derandomization, and you're proposing a specific technique for derandomization, namely using pseudorandom number generators. There are other techniques suck as using k-wise independent distributions and the method of conditional expectations. The holy grail in the field is proving the conjecture P=BPP, which states (informally) that we can always get rid of randomness, though the resulting algorithm could be slower; more precisely, it states that if you have a randomized polytime algorithm for something, then there exists a deterministic polytime algorithm for the same problem.
In your particular case, you don't need random bits at all, since you can use the linear time median algorithm to guarantee a running time of $O(n\log n)$ for quicksort. The AKS deterministic primality test is likewise a specific derandomization of randomized primality testing. P=BPP, in contrast, gives a general derandomization technique that works for every (polytime) algorithm; ad hoc derandomizations are still meaningful, since they could be more efficient (like in the quicksort example).
-
$\begingroup$ Yes I'm aware of deterministic median finding, so my quicksort question is more a question of what happens if we generate $k$ random bits, and adversary knows our pseudo-random generator that repeatedly permutes the $k$ bits to get enough bits to perform all the pivot selections (where the pivot selection is done according to how many next bits are needed in the "seeded random" bit stream, i.e. $\lceil{\log_2(m)}\rceil$ bits to choose a pivot if we are working with $m$ numbers to sort). As I recall, median finding requires extra memory so only storing $k$ random bits could be advantageous. $\endgroup$ May 22, 2015 at 20:02
-
$\begingroup$ It is very doubtful that this approach results in an $O(n\log n)$ algorithm, since PRNGs are slow. $\endgroup$ May 22, 2015 at 21:55
-
$\begingroup$ I'm assuming that the pseudo-number generator is something simple and something that perhaps cannot really improve the situation that much because the adversary knows exactly what the pseudo-random number generator for permutation is. So it might even be valid to assume that the pseudorandom permuter just returns the $k$ bits in the same order every time. I'm not sure but maybe. If that's the case, then the worst case expected running time in terms of # original random bits $k$ and # numbers $n$ to sort is still an interesting question, ignoring the PRNG since the adversary knows it. $\endgroup$ May 22, 2015 at 22:04
If your adversary knows the $k$ input bits and your PRNG, they can apply the techniques used in McIllroy "A Killer Adversary for Quicksort", Software: Practice & Experience 29:4 (1999), pp. 341-344, and you are toast. How large $k$ has to be to make this infeasible to brute-force is another question.
No, "randomized quicksort" doesn't guarantee anything, it just makes the bad case(s) shift around at random (so it is very unlikely to hit them repeatedly with somewhat repeatable input permutations, as are common in "real world" uses). If you want some sort of guarantee, look for Musser "Introspective Sorting and Selection Algorithms", Software: Practice & Experience 27(8) (1997), pp. 983-993 (Introsort). Most standard C/C++ libraries use some variant of this for sorting.
