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:

- optimisation and search: genetic algorithms, simulated annealing
- machine learning: neural networks
- setting initial states: hill-climbing, relaxation techniques
- simulation: Monte Carlo methods
- digital signal processing: adding resolution to A-to-D, spreadspectrum & CDM (wireless networks)
- user interfaces: random walks through interfaces
- telecommunications routing: avoiding overloading 'best' routes
- network protocols: random standoff after contention
- parallel computing: breaking Byzantine cases
- cryptography: generating keys, primality testing, digital signatures
- databases: query optimisation, approximate aggregate results

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:

- to emulate or create real-world statistical phenomena (e.g. simulation, lotteries, online casinos)
- to reduce computational effort by only considering a subset of the data (e.g. database query optimisation)
- to gain coverage of an infinite or computationally unfeasible space (e.g. continuous variables or NP problems)
- to avoid Byzantine cases (e.g. in routing and some search)

Once one recognises that randomness is so widely used and valuable it is possible to look for new uses:

- visualisation
- by sampling data points it is possible to reduce the computation involved in certain visualisation algorithms
- this also may make features visible that otherwise would be lost in the shear volume of data
- getting samples for visualisation often involves sampling an SQL database. See page on sampling SQL databases for some tricks and techniques for this.
- ray-tracing
- randomly choosing points to trace from in backward tracing allows one to stop when it is necessary to refresh a frame with 'best efforts' results rather than simply, half a frame!
- in scenes with lots of refractive surfaces branching due to partial reflection means the number of paths considered can grow exponentially, but choosing which to follow weighted by proportion of light transmitted/reflected reduces computation per path
- total Monte Carlo search!
- generate and test, but where the generation is entirely random (note that simulated annealing reduces to this when the temperature is very high)
- in virtually any algorithm replace a loop through all cases looking for 'the best' to best of a random sample – in recursive algorithms the effect on time complexity is exponential
- algorithm proof
- sometimes assuming inputs are random can help – showing something 'almost always' works rather than always

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.

- sub-pages on
- my topics pages on
**visualisation** -
**meandeviation.com**my portal on statistics and data-mining including ...- experiments in randomness
- tutorial on statistics with heavy focus on understanding randomness

- G. Ellis and A. Dix (2002).
**density control through random sampling: an architectural perspective.***Proceedings of International Conference on Information Visualisation IV02*, London, UK, IEEE Press.(to appear). [abstract and references] - A. Dix and G. Ellis (2002).
**by chance - enhancing interaction with large data sets through statistical sampling.***Proceedings of Advanced Visual Interfaces AVI2002*, Trento, Italy, ACM Press.(to appear). [abstract, contents and references || draft paper (pdf, 288K)] - A. J. Dix (1990).
**Non-determinism as a paradigm for understanding the user interface.**

In*Formal Methods in Human-Computer Interaction*Eds. H. W. Thimbleby and M. D. Harrison. Cambridge University Press. 97-127 [full paper (html)] - R. Gupta, S. A. Smolka and S. Bhaskar (1994).
**On randomization in sequential and distributed algorithms.**ACM Computing Surveys,**26**(1), (March 1994). pp. 7-86. [ACM digital library (abstract and full paper)]

http://www.hcibook.com/alan/topics/random/ | maintained by Alan Dix |