Introduction to Algorithms. (2nd edition) Thomas Cormen_ Charles Leiserson_ Ronad Rivest (811417), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

For example, indicator randomvariables give us a simple way to arrive at the result of equation (C.36). In this equation, wecompute the number of heads in n coin flips by considering separately the probability ofobtaining 0 heads, 1 heads, 2 heads, etc. However, the simpler method proposed in equation(C.37) actually implicitly uses indicator random variables. Making this argument moreexplicit, we can let Xi be the indicator random variable associated with the event in which theith flip comes up heads. Letting Yi be the random variable denoting the outcome of the ith flip,we have that Xi = I{Yi = H}.

Let X be the random variable denoting the total number of headsin the n coin flips, so thatWe wish to compute the expected number of heads, so we take the expectation of both sidesof the above equation to obtainThe left side of the above equation is the expectation of the sum of n random variables. ByLemma 5.1, we can easily compute the expectation of each of the random variables. Byequation (C.20)-linearity of expectation-it is easy to compute the expectation of the sum: itequals the sum of the expectations of the n random variables. Linearity of expectation makesthe use of indicator random variables a powerful analytical technique; it applies even whenthere is dependence among the random variables. We now can easily compute the expectednumber of heads:Thus, compared to the method used in equation (C.36), indicator random variables greatlysimplify the calculation.

We shall use indicator random variables throughout this book.Analysis of the hiring problem using indicator random variablesReturning to the hiring problem, we now wish to compute the expected number of times thatwe hire a new office assistant. In order to use a probabilistic analysis, we assume that thecandidates arrive in a random order, as discussed in the previous section.

(We shall see inSection 5.3 how to remove this assumption.) Let X be the random variable whose value equalsthe number of times we hire a new office assistant. We could then apply the definition ofexpected value from equation (C.19) to obtainbut this calculation would be cumbersome. We shall instead use indicator random variables togreatly simplify the calculation.To use indicator random variables, instead of computing E[X] by defining one variableassociated with the number of times we hire a new office assistant, we define n variablesrelated to whether or not each particular candidate is hired. In particular, we let Xi be theindicator random variable associated with the event in which the ith candidate is hired.

Thus,(5.2)and(5.3)By Lemma 5.1, we have thatE[Xi] = Pr {candidate i is hired},and we must therefore compute the probability that lines 5-6 of HIRE-ASSISTANT areexecuted.Candidate i is hired, in line 5, exactly when candidate i is better than each of candidates 1through i - 1. Because we have assumed that the candidates arrive in a random order, the firsti candidates have appeared in a random order. Any one of these first i candidates is equallylikely to be the best-qualified so far.

Candidate i has a probability of 1/i of being betterqualified than candidates 1 through i - 1 and thus a probability of 1/i of being hired. ByLemma 5.1, we conclude that(5.4)Now we can compute E[X]:(5.5)(5.6)Even though we interview n people, we only actually hire approximately ln n of them, onaverage. We summarize this result in the following lemma.Lemma 5.2Assuming that the candidates are presented in a random order, algorithm HIRE-ASSISTANThas a total hiring cost of O(ch ln n).Proof The bound follows immediately from our definition of the hiring cost and equation(5.6).The expected interview cost is a significant improvement over the worst-case hiring cost ofO(nch).Exercises 5.2-1In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what isthe probability that you will hire exactly one time? What is the probability that you will hireexactly n times?Exercises 5.2-2In HIRE-ASSISTANT, assuming that the candidates are presented in a random order, what isthe probability that you will hire exactly twice?Exercises 5.2-3Use indicator random variables to compute the expected value of the sum of n dice.Exercises 5.2-4Use indicator random variables to solve the following problem, which is known as the hatcheck problem.

Each of n customers gives a hat to a hat-check person at a restaurant. The hatcheck person gives the hats back to the customers in a random order. What is the expectednumber of customers that get back their own hat?Exercises 5.2-5Let A[1 .. n] be an array of n distinct numbers. If i < j and A[i] > A[j], then the pair (i, j) iscalled an inversion of A. (See Problem 2-4 for more on inversions.) Suppose that eachelement of A is chosen randomly, independently, and uniformly from the range 1 through n.Use indicator random variables to compute the expected number of inversions.5.3 Randomized algorithmsIn the previous section, we showed how knowing a distribution on the inputs can help us toanalyze the average-case behavior of an algorithm. Many times, we do not have suchknowledge and no average-case analysis is possible. As mentioned in Section 5.1, we may beable to use a randomized algorithm.For a problem such as the hiring problem, in which it is helpful to assume that allpermutations of the input are equally likely, a probabilistic analysis will guide thedevelopment of a randomized algorithm.

Instead of assuming a distribution of inputs, weimpose a distribution. In particular, before running the algorithm, we randomly permute thecandidates in order to enforce the property that every permutation is equally likely. Thismodification does not change our expectation of hiring a new office assistant roughly ln ntimes. It means, however, that for any input we expect this to be the case, rather than forinputs drawn from a particular distribution.We now explore the distinction between probabilistic analysis and randomized algorithmsfurther. In Section 5.2, we claimed that, assuming that the candidates are presented in arandom order, the expected number of times we hire a new office assistant is about ln n.

Notethat the algorithm here is deterministic; for any particular input, the number of times a newoffice assistant is hired will always be the same. Furthermore, the number of times we hire anew office assistant differs for different inputs, and it depends on the ranks of the variouscandidates. Since this number depends only on the ranks of the candidates, we can represent aparticular input by listing, in order, the ranks of the candidates, i.e., <rank(1), rank(2), ...,rank(n)>.

Given the rank list A1 = <1, 2, 3, 4, 5, 6, 7, 8, 9, 10>, a new office assistant willalways be hired 10 times, since each successive candidate is better than the previous one, andlines 5-6 will be executed in each iteration of the algorithm. Given the list of ranks A2 = <10,9, 8, 7, 6, 5, 4, 3, 2, 1>, a new office assistant will be hired only once, in the first iteration.Given a list of ranks A3= <5, 2, 1, 8, 4, 7, 10, 9, 3, 6>, a new office assistant will be hiredthree times, upon interviewing the candidates with ranks 5, 8, and 10. Recalling that the costof our algorithm is dependent on how many times we hire a new office assistant, we see thatthere are expensive inputs, such as A1, inexpensive inputs, such as A2, and moderatelyexpensive inputs, such as A3.Consider, on the other hand, the randomized algorithm that first permutes the candidates andthen determines the best candidate.

In this case, the randomization is in the algorithm, not inthe input distribution. Given a particular input, say A3 above, we cannot say how many timesthe maximum will be updated, because this quantity differs with each run of the algorithm.The first time we run the algorithm on A3, it may produce the permutation A1 and perform 10updates, while the second time we run the algorithm, we may produce the permutation A2 andperform only one update. The third time we run it, we may perform some other number ofupdates. Each time we run the algorithm, the execution depends on the random choices madeand is likely to differ from the previous execution of the algorithm.

Характеристики

Список файлов книги