“mcs”-2017/6/5一19：42一page vii一#7 vii Contents IV Probability Introduction 729 17 Events and Probability Spaces 731 17.1 Let's Make a Deal 731 17.2 The Four Step Method 732 17.3 Strange Dice 741 17.4 The Birthday Principle 748 17.5 Set Theory and Probability 750 17.6 References 754 18 Conditional Probability 763 18.1 Monty Hall Confusion 763 18.2 Definition and Notation 764 18.3 The Four-Step Method for Conditional Probability 766 18.4 Why Tree Diagrams Work 768 18.5 The Law of Total Probability 776 18.6 Simpson's Paradox 778 18.7 Independence 780 18.8 Mutual Independence 782 18.9 Probability versus Confidence 786 19 Random Variables 815 19.1 Random Variable Examples 815 19.2 Independence 817 19.3 Distribution Functions 819 19.4 Great Expectations 827 19.5 Linearity of Expectation 839 20 Deviation from the Mean 871 20.1 Markov's Theorem 871 20.2 Chebyshev's Theorem 874 20.3 Properties of Variance 878 20.4 Estimation by Random Sampling 884 20.5 Confidence in an Estimation 888 20.6 Sums of Random Variables 889 20.7 Really Great Expectations 899 21 Random Walks 923 21.1 Gambler's Ruin 923
“mcs” — 2017/6/5 — 19:42 — page vii — #7 Contentsvii IV Probability Introduction 729 17 Events and Probability Spaces 731 17.1 Let’s Make a Deal 731 17.2 The Four Step Method 732 17.3 Strange Dice 741 17.4 The Birthday Principle 748 17.5 Set Theory and Probability 750 17.6 References 754 18 Conditional Probability 763 18.1 Monty Hall Confusion 763 18.2 Definition and Notation 764 18.3 The Four-Step Method for Conditional Probability 766 18.4 Why Tree Diagrams Work 768 18.5 The Law of Total Probability 776 18.6 Simpson’s Paradox 778 18.7 Independence 780 18.8 Mutual Independence 782 18.9 Probability versus Confidence 786 19 Random Variables 815 19.1 Random Variable Examples 815 19.2 Independence 817 19.3 Distribution Functions 819 19.4 Great Expectations 827 19.5 Linearity of Expectation 839 20 Deviation from the Mean 871 20.1 Markov’s Theorem 871 20.2 Chebyshev’s Theorem 874 20.3 Properties of Variance 878 20.4 Estimation by Random Sampling 884 20.5 Confidence in an Estimation 888 20.6 Sums of Random Variables 889 20.7 Really Great Expectations 899 21 Random Walks 923 21.1 Gambler’s Ruin 923
“mcs”一2017/6/5一19：42一page viii一#8 vii Contents 21.2 Random Walks on Graphs 933 V Recurrences Introduction 951 22 Recurrences 953 22.1 The Towers of Hanoi 953 22.2 Merge Sort 956 22.3 Linear Recurrences 960 22.4 Divide-and-Conquer Recurrences 967 22.5 A Feel for Recurrences 974 Bibliography 981 Glossary of Symbols 985 Index 989
“mcs” — 2017/6/5 — 19:42 — page viii — #8 Contentsviii 21.2 Random Walks on Graphs 933 V Recurrences Introduction 951 22 Recurrences 953 22.1 The Towers of Hanoi 953 22.2 Merge Sort 956 22.3 Linear Recurrences 960 22.4 Divide-and-Conquer Recurrences 967 22.5 A Feel for Recurrences 974 Bibliography 981 Glossary of Symbols 985 Index 989
“mcs”一2017/6/5一19：42一page1一#9 I Proofs
“mcs” — 2017/6/5 — 19:42 — page 1 — #9 I Proofs
“mcs”-2017/6/5一19：42一page3一#11 Introduction This text explains how to use mathematical models and methods to analyze prob- lems that arise in computer science.Proofs play a central role in this work because the authors share a belief with most mathematicians that proofs are essential for genuine understanding.Proofs also play a growing role in computer science;they are used to certify that software and hardware will always behave correctly,some- thing that no amount of testing can do. Simply put,a proof is a method of establishing truth.Like beauty,"truth"some- times depends on the eye of the beholder,and it should not be surprising that what constitutes a proof differs among fields.For example,in the judicial system,legal truth is decided by a jury based on the allowable evidence presented at trial.In the business world,authoritative truth is specified by a trusted person or organization, or maybe just your boss.In fields such as physics or biology,scientific truth is confirmed by experiment.In statistics,probable truth is established by statistical analysis of sample data. Philosophical proof involves careful exposition and persuasion typically based on a series of small,plausible arguments.The best example begins with"Cogito ergo sum,"a Latin sentence that translates as"I think,therefore I am."This phrase comes from the beginning of a 17th century essay by the mathematician/philosopher, Rene Descartes,and it is one of the most famous quotes in the world:do a web search for it,and you will be flooded with hits. Deducing your existence from the fact that you're thinking about your existence is a pretty cool and persuasive-sounding idea.However,with just a few more lines IActually,only scientific falsehood can be demonstrated by an experiment-when the experiment fails to behave as predicted.But no amount of experiment can confirm that the next experiment won't fail.For this reason,scientists rarely speak of truth,but rather of theories that accurately predict past, and anticipated future,experiments
“mcs” — 2017/6/5 — 19:42 — page 3 — #11 Introduction This text explains how to use mathematical models and methods to analyze problems that arise in computer science. Proofs play a central role in this work because the authors share a belief with most mathematicians that proofs are essential for genuine understanding. Proofs also play a growing role in computer science; they are used to certify that software and hardware will always behave correctly, something that no amount of testing can do. Simply put, a proof is a method of establishing truth. Like beauty, “truth” sometimes depends on the eye of the beholder, and it should not be surprising that what constitutes a proof differs among fields. For example, in the judicial system, legal truth is decided by a jury based on the allowable evidence presented at trial. In the business world, authoritative truth is specified by a trusted person or organization, or maybe just your boss. In fields such as physics or biology, scientific truth is confirmed by experiment.1 In statistics, probable truth is established by statistical analysis of sample data. Philosophical proof involves careful exposition and persuasion typically based on a series of small, plausible arguments. The best example begins with “Cogito ergo sum,” a Latin sentence that translates as “I think, therefore I am.” This phrase comes from the beginning of a 17th century essay by the mathematician/philosopher, Rene Descartes, and it is one of the most famous quotes in the world: do a web ´ search for it, and you will be flooded with hits. Deducing your existence from the fact that you’re thinking about your existence is a pretty cool and persuasive-sounding idea. However, with just a few more lines 1Actually, only scientific falsehood can be demonstrated by an experiment—when the experiment fails to behave as predicted. But no amount of experiment can confirm that the next experiment won’t fail. For this reason, scientists rarely speak of truth, but rather of theories that accurately predict past, and anticipated future, experiments
“mcs”-2017/6/5一19：42一page4一#12 0.1.References of argument in this vein,Descartes goes on to conclude that there is an infinitely beneficent God.Whether or not you believe in an infinitely beneficent God,you'll probably agree that any very short"proof"of God's infinite beneficence is bound to be far-fetched.So even in masterful hands,this approach is not reliable. Mathematics has its own specific notion of "proof." Definition.A mathematical proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. The three key ideas in this definition are highlighted:proposition,logical deduc- tion,and axiom.Chapter 1 examines these three ideas along with some basic ways of organizing proofs.Chapter 2 introduces the Well Ordering Principle,a basic method of proof;later,Chapter 5 introduces the closely related proof method of induction. If you're going to prove a proposition,you'd better have a precise understand- ing of what the proposition means.To avoid ambiguity and uncertain definitions in ordinary language,mathematicians use language very precisely,and they often express propositions using logical formulas;these are the subject of Chapter 3. The first three Chapters assume the reader is familiar with a few mathematical concepts like sets and functions.Chapters 4 and 8 offer a more careful look at such mathematical data types,examining in particular properties and methods for proving things about infinite sets.Chapter 7 goes on to examine recursively defined data types. 0.1 References [141,[49],[1]
“mcs” — 2017/6/5 — 19:42 — page 4 — #12 0.1. References4 of argument in this vein, Descartes goes on to conclude that there is an infinitely beneficent God. Whether or not you believe in an infinitely beneficent God, you’ll probably agree that any very short “proof” of God’s infinite beneficence is bound to be far-fetched. So even in masterful hands, this approach is not reliable. Mathematics has its own specific notion of “proof.” Definition. A mathematical proof of a proposition is a chain of logical deductions leading to the proposition from a base set of axioms. The three key ideas in this definition are highlighted: proposition, logical deduction, and axiom. Chapter 1 examines these three ideas along with some basic ways of organizing proofs. Chapter 2 introduces the Well Ordering Principle, a basic method of proof; later, Chapter 5 introduces the closely related proof method of induction. If you’re going to prove a proposition, you’d better have a precise understanding of what the proposition means. To avoid ambiguity and uncertain definitions in ordinary language, mathematicians use language very precisely, and they often express propositions using logical formulas; these are the subject of Chapter 3. The first three Chapters assume the reader is familiar with a few mathematical concepts like sets and functions. Chapters 4 and 8 offer a more careful look at such mathematical data types, examining in particular properties and methods for proving things about infinite sets. Chapter 7 goes on to examine recursively defined data types. 0.1 References [14], [49], [1]