# Random generator considerations in the design of randomized algorithms

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. Although it is proved that for all $0 < \delta \leq \frac{1}{2}$ the identities BPP = $\delta$-BPP and RP = $\delta$-RP hold, it is not true that the original algorithm used for a prefect random source can be directly used also for a $\delta$-random source. Instead, some simulation has to be done. This simulation is polynomial, but the resulting algorithm is not so efficient as the original one.

Moreover, as to my knowledge, the random generators used in practice are usually not even $\delta$-sources, but pseudo-random sources that can behave extremely badly in the worst case.

According to Wikipedia:

In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

In fact, the implementations of randomized algorithms that I have seen up to now were mere implementations of the algorithms for perfect random sources run with the use of pseudorandom sources.

My question is, if there is any justification of this common practice. Is there any reason to expect that in most cases the algorithm will return a correct result (with the probabilities as in BPP resp. RP)? How can the "approximation" mentioned in the quotation from Wikipedia be formalized? Can the deviation mentioned be somehow estimated, at least in the expected case? Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Or are there any other similar considerations?

$cat /dev/urandom  • Well, I have never studied these matters in detail. But one of the motivations for my question has been that Papadimitriou (in his book Computational Complexity) mentions that random generators used in cryptography are provably terrible for randomized algorithms (of course, this may be only a theoretical issue). That is, I understand it like that the randomized algorithm becomes stochastic with some unknown properties but still sufficient for practice... – 042 May 3 '13 at 6:14 • @042, do you have a direct quote? I'm not familiar with that line of argument. – D.W. May 3 '13 at 6:35 • I have to apologize, since I have found that the remark in Papadimitriou is a little bit misleading - although it may evoke that cryptographic random generators are wrong, the remark applies only to the commonly used congruential generators that are not good also from the cryptographic viewpoint. So I have to take my comment back. – 042 May 3 '13 at 8:49 It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. I have to disagree. What a good pseudurandom sequence ensemble gives you is a guarantee on the performance of the algorithm run a random sequence from the ensemble, compared to a trully random sequence. If you don't have such a guarantee, you can't conclude that the algorithm will work poorly - you just don't know. Is there any justification of this common practice? It works. Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Complexity theory suffers from two shortcomings. The first one is that it is very hard to prove anything (for example, P vs. NP is open). The second one is that it is mostly concerned with worst-case analysis. Put together, these two limitations rule out complexity theory as a good model for the behavior of algorithms in practice. • Yes, I guess you are right, but what I am interested in is whether there are any theoretical guarantees (either in the worst case or in the expected case). To the first point of your answer: randomized algorithms (as far as I know) provide worst-case guarantees (i.e., the probability of error is at most$\varepsilon\$ on every input). This seems to be violated for randomized algorithms run on pseudorandom sources. That is (as to my poor knowledge), the randomized algorithm is turned into a sort of stochastic algorithm. – 042 May 3 '13 at 6:09