Why does randomness work in numerical algorithms?

Question

There are successful numerical algorithms that involves a sequence of random numbers, like Monte Carlo methods or simulated annealing. I can follow the lines of proofs of their convergence, and actually see them work. However I sometimes find it paradoxical that it is useful to deliberately add an unpredictable factor into a process, while we have the opportunity to have the full control over it. Could you give an intuitive explanation for this?

Answer 1

If one had infinite computing capacity, then you would be right that randomness would not be useful (unless an adversary also had access to randomness - see below), and it would always be better to maintain full control of one's parameters. ("God does not need to play dice".) However, our computing capacity is limited, and randomness offers a way to stretch that capacity further (though it is an important open problem to quantify exactly how much randomness actually stretches our capacity; see the discussion on P=BPP in other comments).

Let's give a simple example. Suppose one is playing the following game with a computer. This computer uses some (deterministic) algorithm to generate 1000 "bad" numbers from 1 to 1 million. Meanwhile, you pick your own number from 1 to 1 million. If you pick one of the bad numbers, you lose; otherwise, you win. You get to see the computer's algorithm in advance.

With infinite computing capacity, you have a strategy which is 100% guaranteed to succeed: you run the computer's algorithm, find all the bad numbers, and pick a number not chosen by the computer.

But there is a much lazier strategy that requires no computing power: just pick a number randomly, and one has a 99.9% chance of winning.

[Note also that if the computer used a randomised algorithm instead of a deterministic one, then there is no longer any 100% winning strategy for you, even with infinite computing power, though the random strategy works just fine. This is another indication of the power of randomness.]

Many randomised algorithms work, roughly speaking, by reducing the given problem to some version of the above game. For instance, Monte Carlo integration using a set of points to sample the function might give satisfactory levels of accuracy for all but a tiny fraction of the possible choices of sample points. With infinite computing capacity, one could locate all the bad configurations of sample points and then find a configuration which is guaranteed to give a good level of accuracy, but this is a lot of work - more work, in fact, than just doing classical numerical integration. Instead, one takes the lazy way out and picks the sample points randomly. (Well, in practice, one picks the points pseudorandomly instead of randomly, because true randomness is very hard to capture by a computer; this is a subtle issue - again related to P=BPP - that I don't want to get into here.)

Answer 2

Imagine you are looking for a structure with certain properties, within a universe of possible structures. It is sometimes (perhaps "often"?) the case that the structures you can actually explicitly build form a tiny fraction of that universe, but on the other hand they all fail to have the property you seek.

So, if you wanted to write a program to generate "good" structures, you could either work really hard and find a way of explicitly constructing them, or you could simply choose a structure at random (assuming you have a good way of doing this), check if it "good", and repeat if not.

A classic example: expander graph. It's ridiculously easy to create one by just choosing a graph at random. Explicit constructions, on the other hand, are far from trivial.

It is an open problem whether this really helps, from the perspective of complexity theory. People have found clever "derandomization" schemes that essentially convert a random algorithm to a deterministic one. It is still not known if what you can do in a reasonable time with randomization (RP) is really more than what you can do in a reasonable time without access to randomness (P), and I think most people believe that it's not - in other words, randomness doesn't really "work".

Answer 3

I'm not sure whether this is the kind of answer you are looking for, but in some cases, you are guaranteed a certain probability of success if you choose your parameter randomly, but there is no known procedure to choose a good parameter. The best example of this is Primality testing, where you can prove that at least 1/2 of the possible witnesses for primality work.

Answer 4

This isn't a complete answer, but I've found it useful to think in this way in the past. Part of the reason that randomness is "better" -- though, again, certainly not all of it -- is just due to the way that we quantify how good or bad algorithms are.

So it should be a familiar fact that there are algorithms that do really well most of the time, but which don't do well in the worst case. Two everyday examples are quicksort and the simplex algorithm. The reason for this is that these algorithms aren't as sensitive as they could be to certain kinds of changes in the data, so an adversary who's trying to make your algorithm run slow has a lot of "room to work." But a uniform distribution (or something morally equivalent, or lots of distributions that arise in the real world) isn't adversarial.

So what random algorithms let you do is take a single instance of a problem, and instead sample from a distribution of a bunch of instances of another, related problem, so you get to work (to a certain degree) with average-case complexity instead of with worst-case. Another way of thinking about it: your adversary from before could create hard instances since he knew what your algorithm would do in advance, and he had sneaky ways of making the problem harder without your algorithm noticing until it was too late. But now he doesn't know what the algorithm will do -- it's random! So creating a hard instance seems pretty much hopeless.

Most of the rest of the advantage of random algorithms -- the "real advantage," if you will -- comes from what Alon said above. There are certain desirable properties which seem to be correlated with "high-complexity" strings or distributions, which by definition can't be reached quickly and deterministically. This is closely related to the efficacy of the probabilistic method in combinatorics.

Answer 5

In addition to various reasonable general things described by other people, you might want to learn about the formalization of the notion of randomness: the BPP complexity class.

It's interesting that most computer scientists believe P = BPP. This equality means that (at least theoretically) one can rewrite all algorithms using randomness as the algorithms not using randomness. But it's not proven.

For example, existence of strong pseudorandom generators (link to my MO question) implies P = BPP. But that is in itself a big problem.

So it's very hard to prove the theorem eiher way. Of course, when people tried to prove P = BPP or its converse, they had lots of explanations as to why their theorem is true. None of those explanations is completely successful but they could answer your question about the idea of randomness.

Answer 6

There are alternatives to random methods that try to keep the advantages of random methods and improve on them.

Quasi-Monte Carlo methods are deterministic. They depend on sequences that are more evenly distributed than truly random sequences. (Ironically, they look more like what most people expect from randomness. True randomness looks too clumpy to untrained eyes. See these graphs.)

For some numerical integration problems, QMC methods outperform MC methods. Art Owen published some papers on this. QMC works best when a the effective dimension of a problem is lower than the full dimension. For example, a problem that depends 500 variables but 20 of those variables are much more important than the rest.

QMC methods don't easily provide error estimates. To get around this, sometimes people combine QMC with MC. They may take a QMC grid of points and jiggle it randomly. On some problems, this hybrid approach works better than either approach separately.

Answer 7

There are many reasons that randomness is associated with some numerical algorithms. An example I can think of off the top, that is of particular interest to me, is optimization through genetic algorithms (which involve a significant amount of randomness, I can give further description if necessary, for now I'll keep things succinct).

These algorithms are often used for optimization problems where the space of solutions is either

A) very large B) hard to compute known successful optimization algorithms, either because of high dimension or because the algorithm is NP-Complete or something to that effect.

Granted, if the problem is NP-Complete, asymptotically the genetic algorithm is also NP-complete, but in certain cases these methods do particularly well.

Are there particular algorithms you were interested in? That's just the first example I thought of and can explain in a bit of detail.

EDIT: Response to a Comment:

While it is true that we have machines that can compute functions explicitly, and so if we had infinite time and infinite resources probabilistic methods would not be particularly helpful, we are in fact limited by speed and resources of a computer.

One example: Tracking facial feature change and movement is a problem that has come up in computer science. This can be restated as determining the intrinsic dimension of a high dimensional space, thus producing a low dimensional manifold embedded in the high dimensional space. However, it turns out that the randomly checking certain parts of the expected manifold for certain characteristics actually is faster (in practice, not asymptotically) then doing the full calculation on the manifold.

A Note: We always need to remember that in numerical analysis we are working in discrete spaces, and there is often no way to make purely analytical checks to speed up matters, AND we may not have an analytical model for our particular situation. Thus in order to completely calculate something it often requires iteration over every point in the space, or quite a few of them. Any process which can reduce this amount of computation, and do so with relatively good accuracy, is a definite bonus.

Hope that helps!

Answer 8

The clue of success of Monte Carlo method and other probabilistic algorithms is, that after You consider proper bounds ( for example You control that Your parameters describing are on hipersurface of constant energy) then other possibilities are fully exchangeable and equivalent from te point of view of the target of the problem formulation. That means: all system states You drawing are in fact equivalent if on surface of bounds. So if You want to compute some quantity for them, You may pick it in probabilistic way, and You only should take care about bounds.

For example if You construct expander graph for given graph family ( which is bound condition) then You may replace deterministic search algorithm by stochastic motion on it and results will be as good as deterministic search on beginning graph. That is because every vertex in our graph family is "near" some expander graph vertex so all of them are not-so-far-placed vertexes as counting from expander graph. If some of them would be to-far-placed Your algorithm will have lack of efficiency but expander graph definition protect You from that situation! So every vertex in computable equivalent, comparable distance from some edges of expander graphs.

Another example: If You want to compute some minima in optimisation problem, You may try to search by deterministic algorithm but when You find a way to produce by probabilistic way points on proper surface, then it will work as well as deterministic one. That is because If You draws starting points for computing gradients, for every point on "surface" there is a set of near points which are "typical" and may give You better solution that first one. The only point for which it is not true is this You are looking for! Of course, You may consider case when for given starting point every point in its neighbourhood is wrong-one but here regularity conditions for function You try to optimise protect You from that situation. Of course in general case it may be not so easy, for example trying to find minima of function which is non-deferential everywhere is not so easy, but even then it is easier in probabilistic way b betting the points....