In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, a randomization function or randomizing function is an algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

 or procedure

Subroutine

In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....

 that implements a randomly chosen function

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

 between two specific sets, suitable for use in a randomized algorithm

Randomized algorithm

A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...

.

Randomizing functions are related to random number generators and hash function

Hash function

A hash function is any algorithm or subroutine that maps large data sets to smaller data sets, called keys. For example, a single integer can serve as an index to an array...

s, but have somewhat different requirements and uses, and often need specific algorithms.

Uses

Randomizing functions are used to turn algorithms that have good expected

Expected value

In probability theory, the expected value of a random variable is the weighted average of all possible values that this random variable can take on...

 performance for random inputs, into algorithms that have the same performance for any input.

For example, consider a sorting algorithm

Sorting algorithm

In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most-used orders are numerical order and lexicographical order...

 like quicksort, which has small expected running time when the input items are presented in random order, but is very slow when they are presented in certain unfavorable orders. A randomizing function from the integers 1 to n to the integers 1 to n can be used used to rerrange the n input items in "random" order, before calling that algorithm. This modified (randomized) algorithm will have small expected running time, whatever the input order.

Randomness

In theory, randomization functions are assumed to be truly random, and yield an unpredictably different function every time the algorithm is executed. The randomization technique would not work if, at every execution of the algorithm, the randomization function always performed the same mapping, or a mapping entirely determined by some externally observable parameter (such as the program's startup time). With such a "pseudo-randomization" function, one could in principle construct a sequence of calls such that the function would always yield a "bad" case for the underlying deterministic algorithm. For that sequence of calls, the average cost would be closer to the worst-case cost, rather than the average cost for random inputs.

In practice, however, the main concern is that some "bad" cases for the deterministic algorithm may occur in practice much more often than it would be predicted by chance. For example, in a naive variant of quicksort, the worst case is when the input items are already sorted — which is a very common occurrence in many applications. For such algorithms, even a fixed pseudo-random permutation may be good enough. Even though the resulting "pseudo-randomized" algorithm would still have as many "bad" cases as the original, they will be certain peculiar orders that would be quite unlikely to arise in real applications. So, in practice one often uses randomization functions that are derived from pseudo-random number generators, preferably seeded

Random seed

A random seed is a number used to initialize a pseudorandom number generator.The choice of a good random seed is crucial in the field of computer security...

with external "random" data such as the program's startup time.

Uniformity

The uniformity requirements for a randomizing function are usually much weaker than those of hash functions and pseudo-random generators. The minimum requirement is that it maps any input of the deterministic algorithm into a "good" input with a sufficiently high probability. (However, analysis is usually simpler if the randomizing function implements each possible mapping with uniform probability.)