Wegener I. Complexity Theory. Exploring the Limits of Efficient Algorithms

Подождите немного. Документ загружается.

282 A Appendix

log log n,

log n, log

n, log

n, ...

,n,nlog n, n log n log log n, n log

n, n

1+ε

,...

, 2

εn

, 2

For a sum of constantly many orders of magnitude, one summand of which

grows asymptotically faster than the others, the order of magnitude is that of

this fastest growing summand. So, for example,

log

n +10n

/log n +5n

has the order of magnitude of n

/log n. For summands of the form c · n

, i.e.,

for polynomials, the order of magnitude is precisely the order of magnitude

of the term with the largest exponent.

Further simplifying, we obtain the following notions: A function f : N →

is called

• logarithmic if f = O(log n);

• polylogarithmic if f = O(log

n)forsomek ∈ N, i.e., if asymptotically f

grows no faster than a polynomial in log n;

• linear, quadratic,orcubic if f = O(n), f = O(n

), or f = O(n

);

• quasi-linear if f = O(n log

n)forsomek ∈ N;

• polynomially bounded (or sometimes just polynomial)iff = O(n

)for

some k ∈ N;

• superpolynomial if f = Ω(n

) for every k ∈ N, i.e., if f grows faster than

any polynomial;

• subexponential if f = O(2

) for every ε>0;

• exponential if f = Ω(2

)forsomeε>0; and

• strictly exponential if f = Ω(2

εn

)forsomeε>0.

It is important to note in this context that superpolynomial, exponential,

and strictly exponential denote lower bounds while the other terms refer to

upper bounds. So, for example, n

is cubic (more precisely we could say that

“n

grows asymptotically no faster than cubic”). If we want to express a lower

bound, we can say that an algorithm requires at least cubic computation time.

Functions like n

log n

that are superpolynomial but subexponential are called

quasi-polynomial.

If computation times depend on two or more parameters, we can still use

O-notation. For example, f(n, m)=O(nm

+ n

log m), if there is a constant

c such that f (n, m)/(nm

+ n

log m) ≤ c for all n, m ∈ N.

For probabilities p(n), it often matters how fast these converge to 0 or 1.

In the second case, we can consider how fast q(n):=1− p(n) converges to 0.

By deﬁnition p(n)=o(1) if and only if p(n) converges to 0. This is true even

A.2 Results from Probability Theory 283

for functions like 1/ log n and 1/(log log n) which become small “very slowly”.

We will call p(n)

• polynomially small if p(n)=O(n

−ε

)forsomeε>0;

• exponentially small if p(n)=O(2

−n

)forsomeε>0; and

• strictly exponentially small if p(n)=O(2

−εn

)forsomeε>0.

The last of these can be expressed as 2

−Ω(n)

,whereΩ(n) expresses a lower

bound but 2

−Ω(n)

expresses an upper bound.

A.2 Results from Probability Theory

Since we view randomization as a key concept, we will need a few results from

probability theory. There are, of course, many textbooks that contain these

results. But since we will consider here only the special cases that we actually

need, we can choose a simpler and more intuitive introduction to probability

theory.

For a random experiment we let S denote the sample space, that is, the set

of all possible outcomes of the experiment. We can restrict ourselves to the

cases where S is either ﬁnite (S = {s

,...,s

}) or countably inﬁnite (S =

,...}). In the ﬁrst case the corresponding index set is I = {1,...,m},

and in the second case I = N.Aprobability distribution p assigns to each

outcome s

for i ∈ I a probability p

≥ 0. The sum of all the probabilities p

for i ∈ I must have the value 1.

An event A is a subset of the sample space S, i.e., a set of outcomes

: i ∈ I

} for some I

⊆ I. The probability of an event A is denoted

Prob(A) and is simply the sum of all p

for i ∈ I

. In particular, Prob(∅)=0

and Prob(S) = 1 for any probability distribution. Important statements con-

cerning the probability of a union of events follow directly from this deﬁnition.

Remark A.2.1. A collection of events A

for j ∈ J is called pairwise disjoint

if A

∩ A



= ∅ whenever j = j



. For pairwise disjoint events A

we have

Prob

⎛

⎝



j∈J

⎞

⎠



j∈J

Prob(A

) .

More generally, even if the events A

are not pairwise disjoint we still have

Prob

⎛

⎝



j∈J

⎞

⎠

≤



j∈J

Prob(A

) .

The following images can be helpful. We can imagine a square with sides

of length 1. Each outcome s

is represented as a subregion R

of the square

with area p

such that the regions are disjoint for distinct outcomes. Area

284 A Appendix

and probability are both measures. Events are now regions of the square, and

the areas of these regions are equal to the sum of the areas of the outcomes

they contain. It is clear that the areas of disjoint events add, and that in the

general case, the sum of the areas forms an upper bound, since there may

be some “overlap” that causes some outcomes to be “double counted”. Our

random experiment is now equivalent to the random selection of a point in

the square. If this point belongs to R

, then the outcome is s

What changes if we know that event B has occurred? All outcomes s

/∈ B

are now impossible and so have probability 0, while the outcomes s

∈ B

remain possible. So we obtain a new probability distribution q.Fors

/∈ B,

q(s

) = 0. This means that the sum of all q

for s

∈ B must have the value 1.

The relative probabilities of the outcomes s

∈ B should not change just

because we know that B has occurred, so q

= p

. Therefore, for some

constant λ

= λp

and



i∈I

=1.

From this it follows that

λ =





i∈I







i∈I



=1/ Prob(B) .

So we deﬁne the conditional probability q by

⎧

⎨

⎩

Prob(B)

if s

∈ B

0 otherwise.

For an event A we obtain

q(A)=



i∈I



i∈I

∩I

/ Prob(B)=

Prob(A ∩ B)

Prob(B)

For the conditional probability that A occurs under the assumption that B

has occurred, the notation Prob(A | B) (read the probability of A given B)is

used. So we have

Prob(A | B):=Prob(A ∩ B)/ Prob(B) .

This deﬁnition only makes sense when Prob(B) > 0, since condition B can

only occur if Prob(B) > 0. Often the equivalent equation

Prob(A ∩ B)=Prob(A | B) · Prob(B)

A.2 Results from Probability Theory 285

is used. This equation can be used even if Prob(B) = 0. Although Prob(A | B)

is not formally deﬁned in this case, we still interpret Prob(A | B) · Prob(B)

as 0.

If Prob(A | B)=Prob(A), then the probability of the event A does not

depend on whether or not B has occurred. In this case the events A and B are

said to be independent events. This condition is equivalent to Prob(A ∩ B)=

Prob(A) · Prob(B) and also to Prob(B | A)=Prob(B)ifProb(A) > 0and

Prob(B) > 0. The equation Prob(A ∩ B)=Prob(A) · Prob(B) shows that the

term independence is in fact symmetric with respect to A and B.EventsA

for j ∈ J are called completely independent if for all J



⊆ J,

Prob

⎛

⎝

j∈J



⎞

⎠

j∈J



Prob(A

)

holds.

To this point we have derived conditional probability from the probability

distribution p. Often we will go in the other direction. If we know the proba-

bility distribution of some statistic like income for every state, and we know

the number of residents in each state (or even just the relative populations

of the states), then we can determine the probability distribution for the en-

tire country by taking the weighted sum of the regional probabilities. This

idea can be carried over to probability and leads to the so-called law of total

probability.

Theorem A.2.2. Let B

(j ∈ J) be a partition of the sample space S. Then

Prob(A)=



j∈J

Prob(A | B

) · Prob(B

) .

Proof. The proof follows by simple computation.

Prob(A | B

) · Prob(B

)=Prob(A ∩ B

)

and so by Remark A.2.1 we have



j∈J

Prob(A | B

) · Prob(B



j∈J

Prob(A ∩ B

)=Prob





j∈J

(A ∩ B

)



=Prob



A ∩

j∈J



=Prob(A) . 

Now we come to the central notion of a random variable.Formally,thisis

simply a function X : S → R. So one random variable on the sample space

of all people could assign to each person his or her height; another random

variable could assign each person his or her weight. But random variables are

more than just functions, since every probability distribution p on the sample

space S induces a probability distribution on the range of X as follows:

286 A Appendix

Prob(X = t):=Prob({s

| X(s

)=t}) .

So the probability that X takes on the value t is simply the probability of

the set of all outcomes that are mapped to t by X. While we usually can’t

“do calculations” on a sample space, we can with random variables. Before we

introduce the parameters of random variables, we want to derive the deﬁni-

tion of independent random variables from the notion of independent random

events. Two random variables X and Y on the probability space (S, p) (i.e.,

a sample space S and a probability distribution p on that sample space) are

called independent if the events {X ∈ A} := {s

| X(s

) ∈ A} and {Y ∈ B}

are independent for all A, B ⊆ R. A set of random variables {X

| i ∈ I} is

called completely independent if the events {X

∈ A

} for i ∈ I are completely

independent for all events A

⊆ R. The set of random variables {X

| i ∈ I}

is pairwise independent if for any events A

⊆ R and any i = j, the events

∈ A

} and {X

∈ A

} are independent.

The most important parameter of a random variable is its expected value

(or mean value) E(X) deﬁned by

E(X):=



t∈im(X)

t · Prob(X = t) ,

where im(X) denotes the image of the sample space under the function X.

This deﬁnition presents no problems if im(X) is ﬁnite (so, in particular, when-

ever S is ﬁnite). For countably inﬁnite images the inﬁnite series in the def-

inition above is only deﬁned if the series converges absolutely. This will not

cause us any problems, however, since when we deal with computation times,

the terms of the series will all be positive and we will also allow an expected

value of ∞. Average-case runtime, as deﬁned in Chapter 2, is an expected

value where the input x with |x| = n is chosen randomly. For the expected

runtime of a randomized algorithm the input x is ﬁxed and the expected

value is taken with respect to the random bits that are used by the algorithm.

Since we have deﬁned conditional probability, we can also talk about con-

ditional expected value E(X | A) with respect to the conditional probability

Prob(X = t | A).

Expected value allows for easy computations.

Remark A.2.3. If X is a 0-1 random variable (i.e., im(X) is the set {0, 1}),

then

E(X)=Prob(X =1).

Proof. The claim follows directly from the deﬁnition:

E(X)=0· Prob(X =0)+1· Prob(X =1)=Prob(X =1). 

This very simple observation is extremely helpful, since it allows us to

switch back and forth between probability and expected value. Furthermore,

expected value is linear. This can be explained simply. If we consider the

A.2 Results from Probability Theory 287

balances in the accounts of a bank’s customers as random variables (based on

a random selection of a customer), and every balance is reduced by a factor of

1.95583 (to convert from German marks to euros), then the average balance

will be reduced by this same factor. (Here we see a diﬀerence between theory

and application, since in practice small diﬀerences occur due to the rounding

of each balance to the nearest euro cent.) If two banks merge and the two

accounts of each customer (perhaps with a balance of 0 for one or the other

bank) are combined, then the mean balance after the merger will be the sum

of the mean balances of the two banks separately. We will show that this holds

in general for any random variables deﬁned on the same probability space.

Theorem A.2.4. Let X and Y be random variables on the same probability

space. Then

1. E(a · X)=a · E(X) for a ∈ R,and

2. E(X + Y )=E(X)+E(Y ).

Proof. Here we use a description of expected value that goes back to the indi-

vidual outcomes of the sample space. Let (S, p) be the underlying probability

space. Then

E(X)=



i∈I

X(s

) · p

This equation follows from the deﬁnition of E(X), since Prob(X = t)isthe

sum of all p

with X(s

)=t. It follows that

E(a · X)=



i∈I

(a · X)(s

) · p

= a



i∈I

X(s

) · p

= a · E(X)

and

E(X +Y )=



i∈I

(X +Y )(s

)·p



i∈I

X(s

)·p



i∈I

Y (s

)·p

=E(X)+E(Y ) .



On the other hand, it is not in general the case that E(X·Y )=E(X)·E(Y ).

This can be shown by means of a simple example. Let S = {s

}, p

= p

1/2, X(s

)=0,X(s

) = 2, and Y = X.ThenX ·Y (s

)=0andX·Y (s

)=4.

It follows that E(X · Y ) = 2, but E(X) · E(Y )=1· 1 = 1. The reason is that

in our example X and Y are not independent.

Theorem A.2.5. If X and Y are independent random variables on the same

sample space, then

E(X · Y )=E(X) · E(Y ) .

Proof. As in the proof of Theorem A.2.4, we have

E(X · Y )=



i∈I

X(s

) · Y (s

) · p

288 A Appendix

We partition I into disjoint sets I(t, u):={i | X(s

)=t, Y (s

)=u}.From

this it follows that

E(X · Y )=



t,u



i∈I(t,u)

t · u · p



t,u

t · u



i∈I(t,u)



t,u

t · u · Prob(X = t, Y = u).

Now we can take advantage of the independence of X and Y and obtain

E(X · Y )=



t,u

t · u · Prob(X = t) · Prob(Y = u)





t · Prob(X = t)







u · Prob(Y = u)



=E(X) · E(Y ).



The claim of Theorem A.2.5 can be illustrated as follows. If we assume

that weight and account balance are independent, then the mean balance is

the same for every weight, and so the mean product of account balance and

weight is the product of the mean account balance and the mean weight.

This example also shows that data from everyday life typically only lead to

“almost independent” random variables. But we can design experiments with

coin tosses so that the results are “genuinely independent”.

The expected value reduces the random variable to its weighted mean, and

so expresses only a portion of the information contained in a random variable

and its probability distribution. The mean annual income in two countries

can be the same, for example, while the income disparity in one country

may be small and in the other country much larger. So we are interested

in the random variable Y = |X − E(X)|, which measures the distance of a

random variable from its expected value. The kth central moment of X is

E(|X − E(X)|

). The larger k is the more heavily larger deviations from the

mean are weighted. Based on the discussion above, we might expected that the

ﬁrst central moment would be the most important, but it is computationally

inconvenient because the function |X| is not diﬀerentiable. As a standard

measure of deviation from the expected value, the second central moment is

usually used. It is called the variance of the random variable X and denoted

by V (X):=E((X − E(X))

). Since X

= |X|

, we can drop the absolute

value. Directly from the deﬁnition we obtain the following results.

Theorem A.2.6. Let X be a random variable such that | E(X)| < ∞, then

V (X)=E(X

) − E(X)

and for any a ∈ R,

V (aX)=a

· V (X) .

A.2 Results from Probability Theory 289

Proof. The condition | E(X)| < ∞ guarantees that on the right side of the

ﬁrst claim we do not have the undeﬁned quantity ∞−∞. Then, since E(X)

is a constant factor, by linearity of expected value we have

V (X)=E((X − E(X))

)=E(X

− 2 · X · E(X)+E(X)

)

=E(X

) − 2 · E(X) · E(X)+E(E(X)

Finally, for each constant a ∈ R,E(a)=a, since we are dealing with a

“random” variable that always takes on the value a. So E(E(X)

)=E(X)

and we obtain the ﬁrst claim.

For the second claim we apply the ﬁrst statement and use the equations

E((aX)

)=a

· E(X

)andE(aX)

= a

· E(X)

. 

Since V (2·X)=4·V (X) and not 2·V (X), it is not generally the case that

V (X + Y )=V (X)+V (Y ). This is the case, however, if the random variables

are independent.

Theorem A.2.7. For pairwise independent random variables X

,...,X

have

V (X

+ ···+ X

)=V (X

)+···+ V (X

) .

Proof. The statement follows by simple computation. We have





1≤i≤n









1≤i≤n

− E





1≤i≤n











1≤i≤n

−



1≤i≤n

E(X

)









1≤i,j≤n

· X

− 2



1≤i,j≤n

· E(X



1≤i,j≤n

E(X

) · E(X

)





1≤i,j≤n



E(X

· X

) − 2 · E(X

) · E(X

)+E(X

) · E(X

)



By Theorem A.2.5 it follows from the independence of X

and X

,that

E(X

· X

)=E(X

) · E(X

), and so the summands for all i = j equal0.For

i = j we obtain E(X

) − E(X

)

and thus V (X

). This proves the theorem.



The law of total probability can be extended to a statement about condi-

tional expected value. Recall that E(X | A) is the expected value of X with

respect to the probability distribution Prob(·|A).

Theorem A.2.8. Let {B

| j ∈ J} be a partition of the sample space S,and

let X be a random variable. Then

E(X)=



j∈J

E(X | B

) · Prob(B

) .

290 A Appendix

Proof. From the deﬁnitions we have

E(X)=



i∈I

X(s

) · p(s

)

and

E(X | B

) · Prob(B



i∈I

X(s

) · Prob(s

| B

) · Prob(B

)



i∈I

X(s

) · Prob({s

}∩B

Since the sets B

form a partition of the sample space, s

is in exactly one of

these sets, so



j∈J

Prob({s

}∩B

)=p(s

) .



j∈J

E(X | B

) · Prob(B



j∈J



i∈I

X(s

) · Prob({s

}∩B

)



i∈I

⎛

⎝

X(s

) ·



j∈J

Prob({s

}∩B

)

⎞

⎠



i∈I

X(s

) · p(s

)

=E(X) .



This statement is not surprising. If we want to measure the mean weight

of residents of a certain country, we can do this for each of several regions

separately and then form a weighted sum, using the population proportions

of the regions as weights.

Finally, we need a statement with which we can prove that the probability

of “large” deviations from the expected value is “small”. One very simple but

extremely useful statement that makes this possible is the Markov Inequality.

If we know that the mean annual income of a population is 40000 euros, then

we can conclude from this that at most 4% of the population has an annual

income that exceeds one million euros. For this to be the case we must make

the assumption that there are no negative incomes. If more than 4% of the

population earns at least one million euros, then these people alone contribute

more than 0.04 · 10

= 40000 to the weighted mean. Since we have excluded

the possibility of negative incomes, the mean income must be greater than

40000 euros. The Markov Inequality is a generalization of this result.

Theorem A.2.9 (Markov Inequality). Let X ≥ 0.Thenforallt>0,

Prob(X ≥ t) ≤ E(X)/t .

A.2 Results from Probability Theory 291

Proof. We deﬁne a random variable Y on the same sample space that X is

deﬁned on as follows:

Y (s

):=

⎧

⎨

⎩

t if X(s

) ≥ t

0 otherwise.

By deﬁnition Y (s

) ≤ X(s

) for all i and therefore Y ≤ X. By the deﬁnition

of expected value this implies that E(Y ) ≤ E(X). Similarly, it follows from

the deﬁnitions of expected value and of Y that

E(Y )=0· Prob(X<t)+t · Prob(X ≥ t)

= t · Prob(X ≥ t).

Putting these together we have

E(X) ≥ E(Y )=t · Prob(X ≥ t) . 

It is not so impressive that the Markov Inequality implies that at most 4%

of the population can have an annual income in excess of one million euros.

We suspect that the actual portion is much less. We obtain better estimates if

we apply the Markov Inequality to specially chosen random variables. Using

the random variable |X − E(X)|

, for example, we obtain

Prob



|X − E(X)|

≥ t



≤ E



|X − E(X)|



or since |X − E(X)|

≥ t

and |X − E(X)|≥t are equivalent,

Prob (|X − E(X)|≥t) ≤ E



|X − E(X)|



When computing E



|X − E(X)|



,ask increases, values of the random vari-

ables |X − E(X)| that are smaller than 1 are weighted less heavily, and values

that are greater than 1 are weighted more heavily. It is also worth noting that

the denominator t

changes with k. So it is very possible that we will achieve

better results with larger values of k. For the case k = 2, the result is known

as the Chebychev Inequality.

Corollary A.2.10 (Chebychev Inequality). For al l t>0,

Prob (|X − E(X)|≥t) ≤ V (X)/t

. 

We now consider n independent coin tosses and want to investigate the

random variable that counts the number of heads. Let X

,...,X

be random

variables with Prob(X

=0)=Prob(X

=1)=1/2. Then X

measures

the number of successes (tosses that result in heads) in the ith coin toss

and X := X

+ ···+ X

measures the total number of successes. Note that

= X

.ByRemarkA.2.3,E(X

)=E(X

)=1/2, and by Theorem A.2.6,

V (X

)=1/2 − (1/2)

=1/4. By Theorem A.2.4 and Theorem A.2.7, E(X)=

n/2andV (X)=n/4. Our goal is to show that for any constant ε>0,