We deal with the many aspects of randomness which are involved in the design and analysis of algorithms. One way to attack a hard problem is to investigate discrete stochastic models which represent a random distribution on all possible inputs to an algorithm. Such models enable us to judge an algorithmic approach based on its average performance, avoiding the often over-pessimistic conclusions of worst-case paradigms. On the other hand, a thorough understanding is required of the structural properties an input has with high probability.
The investigation of such typical properties often reveals phase transitions. If the probability model is changed along an (imaginary) time axis, at certain points new properties emerge, whereas others disappear. The understanding of this "evolution" is essential in order to adapt such a model to a given situation, e.g. in the simulation of complex networks in information technology, or large data bases in bioinformatics.
Deutsch