Probability and Algorithms (1992) / Chapter Skim
Currently Skimming:
1 Introduction
1 Introduction
Pages 1-16
The Chapter Skim interface presents what we've algorithmically identified as the most significant single chunk of text within every page in the chapter.
Select key terms on the right to highlight them within pages of the chapter.
From page 1... ...
Michael Steele, University of Pennsylvania and David Aldous, University of California at Berkeley The theory of algorithms has undergone an extraordinarily vigorous development over the last 20 years, and probability theory has emerged as one of its most vital partners. University courses, research monographs, and specialized journals have been developed to serve this partnership, yet there is still a need to communicate the progress in this area to the wider audience of computer scientists, mathematicians, and individuals who have a stake in the contributions that mathematical research can make to technology.
|
From page 2... ...
I-! Probabilistic Algorithms I.~.1 Everyday Examples Before developing more serious examples that require detailed mathematical description, it seems useful to provide a couple of everyday analogies.
|
From page 3... ...
The larger idea onto which this flavor of application can be attached might be caned "randomization to avoid special coincidences." Mathematicians can find analogs of this phenomenon in many other fields, and, as more technical examples wiD illustrate later, there are more profound consequences to the idea than are done justice to by this first quick, everyday example. Our second everyday example involves opinion polls.
|
From page 4... ...
The point is not even to recall the often missed subtlety that the required sample size depends only on the precision required, and not on the size of the population about which the inference is being made; though it is interesting that the senators from Rhode Island find it as costly to obtain information about the voting populace of that state as it is for the National Committee to get the corresponding information about the nation as whole. The point is rather to see that the sampling techniques of political poUsters are actually probabilistic algorithms; one uses exogenous randomization to obtain an approximation to a problem that would be prohibitively expensive to answer exactly.
|
From page 5... ...
I.~.2 Hashing Some of the earliest examples of probabilistic algorithms were invented in the context of storage algorithms, and one of most influential of the ideas to be developed to speed up the access of stored information is hashing. This device is used in many important computational contexts and even lives at the heart of some computer operating systems.
|
From page 6... ...
,n. Thus, the mathematical analysis of the performance of hashing with linear probing can be done under the assumption that the hashed values of the m items are independent uniform random variables.
|
From page 7... ...
There is a known tessellation in O(nIogn) steps, improvede deterministic algorithm for computing the and in the worst case this order cannot be For the special case where S consists of the vertices of a convex polygon, a simple probabilistic algorithm is available.
|
From page 8... ...
Note the simplicity of the randomization: it is hard to imagine a simple deterministic algorithm performing so well. 1.~.5 Random Constructions A surprising connection between mathematical probability and the theory of algorithms is the idea of proving mathematical results about random objects by studying the behavior of an algorithm for constructing the random object.
|
From page 9... ...
After n arrivals, the pattern of mathematicians (labeled by arrival order) at tables can be regarded as the cycle representation of a permutation, and it is easy to see that the sequential uniform random choices create a uniform random permutation.
|
From page 10... ...
the situation is better. but still it may i.2 Probabilistic Analysis of Algorithms 1.2.1 Sample Analyses: The Assignment Problem Probabilistic analysis is inevitably mathematical, so no everyday example can help illustrate this second of the great gates through which probability theory enters the theory of algorithms.
|
From page 11... ...
For the simple and global greedy algorithms for the assignment problem, the running time analysis does not depend on probability theory, so we will consider it first. Because one can find the smallest element in a list of k items in time that
|
From page 12... ...
assignment cost An that is obtained using the simple greedy algorithm. Because the expected value of the minimum of k independent, uniformly distributed random variables is exactly equal to 1/(k + 1)
|
From page 13... ...
. The punchline is that even though the global greedy algorithm takes a little more time to compute and seems to be a more powerful strategy, the value of the assignment that it yields is typically no better than that one gets by the simple greedy strategy.
|
From page 14... ...
This analysis provides the basis of a number of insights into the behavior of the Quicksort process. Although we are more concerned with the pointers it provides about basic theoretical structures, it is worth noting quickly that our analysis already suggests when Quicksort will perform poorly.
|
From page 15... ...
(1992) , Backwards analysis of randomized geometric algorithms, in New Trends in Discrete and Computational Geometry, J
|
Key Terms
This material may be derived from roughly machine-read images, and so is provided only to facilitate research.
More
information on Chapter Skim is available.