6.1  Error-Free Probabilistic Programs

Randomization is an important programming tool. Intuitively, its power stems from choice. The ability to make "random choices" can be viewed as a derivation of the ability to make "nondeterministic choices."

In the nondeterministic case, each execution of an instruction must choose between a number of options. Some of the options might be "good", and others "bad." The choice must be for a good option, whenever it exists. The problem is that it does not generally seem possible to make nondeterministic choices in an efficient manner.

The options in the case for random choices are similar to those for the nondeterministic case, however, no restriction is made on the nature of the option to be chosen. Instead, each of the good and bad options is assumed to have an equal probability of being chosen. Consequently, the lack of bias among the different options enables the efficient execution of choices. The burden of increasing the probability of obtaining good choices is placed on the programmer.

Here random choices are introduced to programs through random assignment instructions of the form x := random(S), where S can be any finite set. An execution of a random assignment instruction x := random(S) assigns to x an element from S, where each of the elements in S is assumed to have an equal probability of being chosen. Programs with random assignment instructions, and no nondeterministic instructions, are called probabilistic programs.

Each execution sequence of a probabilistic program is assumed to be a computation . On a given input a probabilistic program might have both accepting and nonaccepting computations.

The execution of a random assignment instruction x := random(S) is assumed to take one unit of time under the uniform cost criteria, and |v| + log |S| time under the logarithmic cost criteria. |v| is assumed to be the length of the representation of the value v chosen from S, and |S| is assumed to denote the cardinality of S.

A probabilistic program P is said to have an expected time complexity (x) on input x if (x) is equal to p₀(x) 0 + p₁(x) 1 + p₂(x) 2 + . The function p_i(x) is assumed to be the probability for the program P to have on input x a computation that takes exactly i units of time.

The program P is said to have an expected time complexity (n) if (|x|) (x) for each x.

The following example shows how probabilism can be used to guarantee an improved behavior (on average) for each input.

Example 6.1.1    Consider the deterministic program in Figure 6.1.1

call SELECT(k, S)
procedure SELECT(k,S)
    x   := first element in S
    S1 := { y | y is in S, and y < x }
   n1 := cardinality of the set stored in S1
    S2 := { y | y is in S, and y > x }
   n2 := cardinality of the set stored in S2
    n3 := (cardinality of the set stored in S) - n2
    case
                 k  n1: SELECT(k, S1)
           n3 < k  : SELECT(k - n3, S2)
      n1 < k  n3: x holds the desired element
    end
end                                                                        

Let T(n) denote the time (under the uniform cost criteria) that the program takes to select an element from a set of cardinality n. T(n) satisfies, for some constant c and some integer m < n, the following inequalities.

From the inequalities above

T(n)		T(n - 1) + cn
		T(n - 2) + c
		T(n - 3) + c
		T(1) + c
		cn2.

The time requirement of the program is sensitive to the ordering of the elements in the sets in question. For instance, when searching for the smallest element, O(n) time is sufficient if the elements of the set are given in nondecreasing order. Alternatively, the program uses O(n²) time when the elements are given in nonincreasing order.

This sensitivity to the order of the elements can be eliminated by assigning a random element from S to x, instead of the first element of S. In such a case, the expected time complexity (n) of the program satisfies the following inequalities, for some constant c.

From the inequalities above

(n)		+ cn
		+ + + cn
		+ c(1 - ) + cn
		+ c + cn
		+
		+ + c + cn
		+ 2c + cn
		+ 2c + cn
		+ 3c + cn
		(1) + (n - 1)c + cn
		2cn.

That is, the modified program is probabilistic and its expected time complexity is O(n). For every given input (k, S) with S of cardinality |S|, the probabilistic program is guaranteed to find the kth smallest element in S within O(|S|²) time. However, on average it requires O(|S|) time for a given input.

[next] [front] [up]