Einstein said "God doesn't play dice". Whether or not Einstein's theological insight equaled his cosmological genius, it is clear in so many areas that randomness is not only unavoidable, but often desirable.
For many years I've been collecting examples of where randomness makes the insoluble soluble, the intractable tractable and the impossible possible. For the omniscient and omnipotent, randomness is an optional extra, for the finite and fallible, it is an essential part of our theoretical and practical armoury.
This is not least true in computing. Traditional algorithms are deterministic, attempting to find the unique or the best solution. In contrast, one of the characteristics of 'modern' algorithmics (modern here really goes back at least 30 years!), including neural networks, genetic algorithms and simulated annealing, makes heavy use of randomness. These algorithms are non-deterministic and find 'a solution' rather than ';the solution' and 'good' rather than 'best'. Because of this more relaxed and inexact approach to solutions these algorithms can tackle problems that are otherwise intractable including NP-hard ones. One trades quality for computation, in some cases as a simple cost-benefit tradeoff, in others because the computation for the exact solution would be impossible.
Recently I've been working with Geoff Ellis on the use of randomness in visualisation and he has found yet more examples of positive uses of randomness in the computational world.
Sometimes computation is used to remove or ameliorate unwanted randomness, for example noise reduction in DSP, and statistical processing of real world data. However, there are yet more examples where randomness is deliberately introduced into algorithms:
For more about this see page on randomness on computing or Gupta, Smolka and Bhaskar's ACM Computer Surveys article "On randomization in sequential and distributed algorithms".
Randomness is used in various ways:
Once one recognises that randomness is so widely used and valuable it is possible to look for new uses:
Randomness and non-determinism are clearly related, but not synonymous - random phenomena are by their nature non-deterministic, but not vice versa. For example, a non-deterministic set of 100 coins might all be heads, but it would be unlikely (but not impossible) to have 100 heads if the coins were selected randomly. Non-determinism says there is no understood or known pattern to the choice, random says the individual choices are unknown but as a whole there are statistical properties.
Non-determinism is also very important in computation: non-deterministic automata have greater computational power than their deterministic counterparts (that is, if one allows then to be oracular!), non-deterministic specifications mean one can leave decisions to more appropriate points in the design cycle.
Note that designing where some inputs are non-deterministic encourages one to make systems that are robust to absolutely any input including the impossibly unlikely. Regarding the input as random and statistical mean we can not worry about very unlikely outcomes (for example, all the telephone days for a day arriving within the same minute). The former is useful for security if an attacker can manipulate inputs to make them Byzantine, the latter for balancing economics of algorithm complexity against likelihood of bad cases.
In previous work I've also looked at ways of using non-determinism as a deliberate design mechanism in user interfaces.
| http://www.hcibook.com/alan/topics/random/ | maintained by Alan Dix |