Mathematics for Computer Science pot

Eric Lehman and Tom Leighton

Mathematics for Computer Science

Eric Lehman and Tom Leighton

2004

Contents

1 What is a Proof? 15

1.1 Propositions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2 Axioms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

1.3 Logical Deductions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4 Examples of Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.4.1 A Tautology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21

1.4.2 A Proof by Contradiction . . . . . . . . . . . . . . . . . . . . . . . . . 22

2 Induction I 23

2.1 A Warmup Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.2 Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

2.3 Using Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

2.4 A Divisibility Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

2.5 A Faulty Induction Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

2.6 Courtyard Tiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31

2.7 Another Faulty Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

3 Induction II 35

3.1 Good Proofs and Bad Proofs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

3.2 A Puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3.3 Unstacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.1 Strong Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.3.2 Analyzing the Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

3

4 CONTENTS

4 Number Theory I 45

4.1 A Theory of the Integers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2 Divisibility . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

4.2.1 Turing’s Code (Version 1.0) . . . . . . . . . . . . . . . . . . . . . . . . 47

4.2.2 The Division Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . 50

4.2.3 Breaking Turing’s Code . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3 Modular Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.1 Congruence and Remainders . . . . . . . . . . . . . . . . . . . . . . . 51

4.3.2 Facts about rem and mod . . . . . . . . . . . . . . . . . . . . . . . . . 52

4.3.3 Turing’s Code (Version 2.0) . . . . . . . . . . . . . . . . . . . . . . . . 54

4.3.4 Cancellation Modulo a Prime . . . . . . . . . . . . . . . . . . . . . . . 55

4.3.5 Multiplicative Inverses . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

4.3.6 Fermat’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57

4.3.7 Finding Inverses with Fermat’s Theorem . . . . . . . . . . . . . . . . 58

4.3.8 Breaking Turing’s Code— Again . . . . . . . . . . . . . . . . . . . . . 58

5 Number Theory II 61

5.1 Die Hard . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61

5.1.1 Death by Induction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

5.1.2 A General Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63

5.1.3 The Greatest Common Divisor . . . . . . . . . . . . . . . . . . . . . . 64

5.1.4 Properties of the Greatest Common Divisor . . . . . . . . . . . . . . . 65

5.2 The Fundamental Theorem of Arithemtic . . . . . . . . . . . . . . . . . . . . 67

5.3 Arithmetic with an Arbitrary Modulus . . . . . . . . . . . . . . . . . . . . . . 68

5.3.1 Relative Primality and Phi . . . . . . . . . . . . . . . . . . . . . . . . . 68

5.3.2 Generalizing to an Arbitrary Modulus . . . . . . . . . . . . . . . . . . 70

5.3.3 Euler’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

6 Graph Theory 73

6.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73

6.1.1 Definitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

6.1.2 Sex in America . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74

CONTENTS 5

6.1.3 Graph Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76

6.1.4 Applications of Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.1.5 Some Common Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 77

6.1.6 Isomorphism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79

6.2 Connectivity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

6.2.1 A Simple Connectivity Theorem . . . . . . . . . . . . . . . . . . . . . 80

6.2.2 Distance and Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

6.2.3 Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.3 Adjacency Matrices . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83

6.4 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84

6.4.1 Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

6.4.2 Tree Variations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87

7 Graph Theory II 89

7.1 Coloring Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89

7.1.1 k-Coloring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.1.2 Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

7.2 Planar Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91

7.2.1 Euler’s Formula . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93

7.2.2 Classifying Polyhedra . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

7.3 Hall’s Marriage Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95

7.3.1 A Formal Statement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97

8 Communication Networks 99

8.1 Complete Binary Tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 99

8.1.1 Latency and Diameter . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

8.1.2 Switch Size . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.1.3 Switch Count . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.1.4 Congestion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101

8.2 2-D Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103

8.3 Butterfly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104

8.4 Benes Network ˘ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106

6 CONTENTS

9 Relations 111

9.0.1 Relations on One Set . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111

9.0.2 Relations and Directed Graphs . . . . . . . . . . . . . . . . . . . . . . 112

9.1 Properties of Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

9.2 Equivalence Relations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.2.1 Partitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113

9.3 Partial Orders . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114

9.3.1 Directed Acyclic Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . 116

9.3.2 Partial Orders and Total Orders . . . . . . . . . . . . . . . . . . . . . . 116

10 Sums, Approximations, and Asymptotics 119

10.1 The Value of an Annuity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119

10.1.1 The Future Value of Money . . . . . . . . . . . . . . . . . . . . . . . . 119

10.1.2 A Geometric Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 120

10.1.3 Return of the Annuity Problem . . . . . . . . . . . . . . . . . . . . . . 121

10.1.4 Infinite Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122

10.2 Variants of Geometric Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123

10.3 Sums of Powers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

10.4 Approximating Sums . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 126

10.4.1 Integration Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

10.4.2 Taylor’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 128

10.4.3 Back to the Sum . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130

10.4.4 Another Integration Example . . . . . . . . . . . . . . . . . . . . . . . 131

11 Sums, Approximations, and Asymptotics II 133

11.1 Block Stacking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

11.1.1 Harmonic Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

11.2 Products . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

11.3 Asymptotic Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138

CONTENTS 7

12 Recurrences I 143

12.1 The Towers of Hanoi . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143

12.1.1 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 144

12.1.2 A Lower Bound for Towers of Hanoi . . . . . . . . . . . . . . . . . . . 145

12.1.3 Guess-and-Verify . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 146

12.1.4 The Plug-and-Chug Method . . . . . . . . . . . . . . . . . . . . . . . 147

12.2 Merge Sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

12.2.1 The Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149

12.2.2 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

12.2.3 Solving the Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 150

12.3 More Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

12.3.1 A Speedy Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152

12.3.2 A Verification Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 153

12.3.3 A False Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 154

12.3.4 Altering the Number of Subproblems . . . . . . . . . . . . . . . . . . 155

12.4 The Akra-Bazzi Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

12.4.1 Solving Divide and Conquer Recurrences . . . . . . . . . . . . . . . . 156

13 Recurrences II 159

13.1 Asymptotic Notation and Induction . . . . . . . . . . . . . . . . . . . . . . . 159

13.2 Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

13.2.1 Graduate Student Job Prospects . . . . . . . . . . . . . . . . . . . . . 160

13.2.2 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161

13.2.3 Solving the Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

13.2.4 Job Prospects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164

13.3 General Linear Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . . 165

13.3.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

13.4 Inhomogeneous Recurrences . . . . . . . . . . . . . . . . . . . . . . . . . . . 167

13.4.1 An Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168

13.4.2 How to Guess a Particular Solution . . . . . . . . . . . . . . . . . . . 169

8 CONTENTS

14 Counting I 173

14.1 Counting One Thing by Counting Another . . . . . . . . . . . . . . . . . . . 174

14.1.1 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174

14.1.2 Bijections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175

14.1.3 The Bijection Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 176

14.1.4 Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 177

14.2 Two Basic Counting Rules . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

14.2.1 The Sum Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 178

14.2.2 The Product Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 179

14.2.3 Putting Rules Together . . . . . . . . . . . . . . . . . . . . . . . . . . . 180

14.3 More Functions: Injections and Surjections . . . . . . . . . . . . . . . . . . . 181

14.3.1 The Pigeonhole Principle . . . . . . . . . . . . . . . . . . . . . . . . . 182

15 Counting II 187

15.1 The Generalized Product Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . 188

15.1.1 Defective Dollars . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

15.1.2 A Chess Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 189

15.1.3 Permutations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 190

15.2 The Division Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 191

15.2.1 Another Chess Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 191

15.2.2 Knights of the Round Table . . . . . . . . . . . . . . . . . . . . . . . . 192

15.3 Inclusion-Exclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 193

15.3.1 Union of Two Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194

15.3.2 Union of Three Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 195

15.3.3 Union of n Sets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 196

15.4 The Grand Scheme for Counting . . . . . . . . . . . . . . . . . . . . . . . . . 197

16 Counting III 201

16.1 The Bookkeeper Rule . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

16.1.1 20-Mile Walks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

16.1.2 Bit Sequences . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202

16.1.3 k-element Subsets of an n-element Set . . . . . . . . . . . . . . . . . . 202

CONTENTS 9

16.1.4 An Alternative Derivation . . . . . . . . . . . . . . . . . . . . . . . . . 203

16.1.5 Word of Caution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

16.2 Binomial Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203

16.3 Poker Hands . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 204

16.3.1 Hands with a Four-of-a-Kind . . . . . . . . . . . . . . . . . . . . . . . 205

16.3.2 Hands with a Full House . . . . . . . . . . . . . . . . . . . . . . . . . 205

16.3.3 Hands with Two Pairs . . . . . . . . . . . . . . . . . . . . . . . . . . . 206

16.3.4 Hands with Every Suit . . . . . . . . . . . . . . . . . . . . . . . . . . . 208

16.4 Magic Trick . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

16.4.1 The Secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209

16.4.2 The Real Secret . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211

16.4.3 Same Trick with Four Cards? . . . . . . . . . . . . . . . . . . . . . . . 212

16.5 Combinatorial Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212

16.5.1 Boxing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213

16.5.2 Combinatorial Proof . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214

17 Generating Functions 217

17.1 Generating Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217

17.2 Operations on Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 218

17.2.1 Scaling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218

17.2.2 Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

17.2.3 Right Shifting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

17.2.4 Differentiation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221

17.3 The Fibonacci Sequence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

17.3.1 Finding a Generating Function . . . . . . . . . . . . . . . . . . . . . . 222

17.3.2 Finding a Closed Form . . . . . . . . . . . . . . . . . . . . . . . . . . . 224

17.4 Counting with Generating Functions . . . . . . . . . . . . . . . . . . . . . . . 225

17.4.1 Choosing Distinct Items from a Set . . . . . . . . . . . . . . . . . . . . 225

17.4.2 Building Generating Functions that Count . . . . . . . . . . . . . . . 225

17.4.3 Choosing Items with Repetition . . . . . . . . . . . . . . . . . . . . . 227

17.5 An “Impossible” Counting Problem . . . . . . . . . . . . . . . . . . . . . . . 229

10 CONTENTS

18 Introduction to Probability 231

18.1 Monty Hall . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231

18.1.1 The Four-Step Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

18.1.2 Clarifying the Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . 232

18.1.3 Step 1: Find the Sample Space . . . . . . . . . . . . . . . . . . . . . . . 233

18.1.4 Step 2: Define Events of Interest . . . . . . . . . . . . . . . . . . . . . 235

18.1.5 Step 3: Determine Outcome Probabilities . . . . . . . . . . . . . . . . 236

18.1.6 Step 4: Compute Event Probabilities . . . . . . . . . . . . . . . . . . . 239

18.1.7 An Alternative Interpretation of the Monty Hall Problem . . . . . . . 240

18.2 Strange Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 240

18.2.1 Analysis of Strange Dice . . . . . . . . . . . . . . . . . . . . . . . . . . 241

19 Conditional Probability 245

19.1 The Halting Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

19.1.1 Solution to the Halting Problem . . . . . . . . . . . . . . . . . . . . . 246

19.1.2 Why Tree Diagrams Work . . . . . . . . . . . . . . . . . . . . . . . . . 248

19.2 A Posteriori Probabilities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 250

19.2.1 A Coin Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251

19.2.2 A Variant of the Two Coins Problem . . . . . . . . . . . . . . . . . . . 252

19.3 Medical Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 254

19.4 Conditional Probability Pitfalls . . . . . . . . . . . . . . . . . . . . . . . . . . 256

19.4.1 Carnival Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256

19.4.2 Other Identities . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 258

19.4.3 Discrimination Lawsuit . . . . . . . . . . . . . . . . . . . . . . . . . . 258

19.4.4 On-Time Airlines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 260

20 Independence 261

20.1 Independent Events . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

20.1.1 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261

20.1.2 Working with Independence . . . . . . . . . . . . . . . . . . . . . . . 262

20.1.3 Some Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262

20.1.4 An Experiment with Two Coins . . . . . . . . . . . . . . . . . . . . . 263

CONTENTS 11

20.1.5 A Variation of the Two-Coin Experiment . . . . . . . . . . . . . . . . 264

20.2 Mutual Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 266

20.2.1 DNA Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267

20.2.2 Pairwise Independence . . . . . . . . . . . . . . . . . . . . . . . . . . 268

20.3 The Birthday Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

20.3.1 The Four-Step Method . . . . . . . . . . . . . . . . . . . . . . . . . . . 270

20.3.2 An Alternative Approach . . . . . . . . . . . . . . . . . . . . . . . . . 272

20.3.3 An Upper Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

20.3.4 A Lower Bound . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274

20.3.5 The Birthday Principle . . . . . . . . . . . . . . . . . . . . . . . . . . . 275

21 Random Variables 277

21.1 Random Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277

21.1.1 Indicator Random Variables . . . . . . . . . . . . . . . . . . . . . . . . 278

21.1.2 Random Variables and Events . . . . . . . . . . . . . . . . . . . . . . 278

21.1.3 Conditional Probability . . . . . . . . . . . . . . . . . . . . . . . . . . 279

21.1.4 Independence . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 280

21.1.5 An Example with Dice . . . . . . . . . . . . . . . . . . . . . . . . . . . 281

21.2 Probability Distributions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282

21.2.1 Bernoulli Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

21.2.2 Uniform Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284

21.2.3 The Numbers Game . . . . . . . . . . . . . . . . . . . . . . . . . . . . 285

21.2.4 Binomial Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . 287

21.2.5 Approximating the Cumulative Binomial Distribution Function . . . 290

21.3 Philosophy of Polling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 291

22 Expected Value I 293

22.1 Betting on Coins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293

22.2 Equivalent Definitions of Expectation . . . . . . . . . . . . . . . . . . . . . . 296

22.2.1 Mean Time to Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297

22.2.2 Making a Baby Girl . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

22.3 An Expectation Paradox . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 298

12 CONTENTS

22.4 Linearity of Expectation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 300

22.4.1 Expected Value of Two Dice . . . . . . . . . . . . . . . . . . . . . . . . 301

22.4.2 The Hat-Check Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 302

22.4.3 The Chinese Appetizer Problem . . . . . . . . . . . . . . . . . . . . . 303

23 Expected Value II 305

23.1 The Expected Number of Events that Happen . . . . . . . . . . . . . . . . . . 305

23.1.1 A Coin Problem— the Easy Way . . . . . . . . . . . . . . . . . . . . . 306

23.1.2 The Hard Way . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 306

23.2 The Coupon Collector Problem . . . . . . . . . . . . . . . . . . . . . . . . . . 307

23.2.1 A Solution Using Linearity of Expectation . . . . . . . . . . . . . . . 307

23.3 Expected Value of a Product . . . . . . . . . . . . . . . . . . . . . . . . . . . . 309

23.3.1 The Product of Two Independent Dice . . . . . . . . . . . . . . . . . . 309

23.3.2 The Product of Two Dependent Dice . . . . . . . . . . . . . . . . . . . 310

23.3.3 Corollaries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 310

24 Weird Happenings 315

24.1 The New Grading Policy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

24.1.1 Markov’s Inequality . . . . . . . . . . . . . . . . . . . . . . . . . . . . 316

24.1.2 Limitations of the Markov Inequality . . . . . . . . . . . . . . . . . . 317

24.2 The Tip of the Tail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 317

24.2.1 Upper Bound: The Union Bound . . . . . . . . . . . . . . . . . . . . . 318

24.2.2 Lower Bound: “Murphy’s Law” . . . . . . . . . . . . . . . . . . . . . 318

24.2.3 The Big Picture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319

24.3 Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320

24.3.1 MIT Admissions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 321

24.3.2 Proving Chernoff Bounds . . . . . . . . . . . . . . . . . . . . . . . . . 322

24.4 Hashing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 324

24.4.1 The First Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

24.4.2 N Records in N Bins . . . . . . . . . . . . . . . . . . . . . . . . . . . . 325

24.4.3 All Bins Full . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326

CONTENTS 13

25 Random Walks 327

25.1 A Bug’s Life . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327

25.1.1 A Simpler Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 328

25.1.2 A Big Island . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 329

25.1.3 Life Expectancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332

25.2 The Gambler’s Ruin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 334

25.2.1 Finding a Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

25.2.2 Solving the Recurrence . . . . . . . . . . . . . . . . . . . . . . . . . . . 335

25.2.3 Interpreting the Solution . . . . . . . . . . . . . . . . . . . . . . . . . . 337

25.2.4 Some Intuition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

25.3 Pass the Broccoli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 338

14 CONTENTS

Chapter 1

What is a Proof?

A proof is a method of establishing truth. This is done in many different ways in everyday

life:

Jury trial. Truth is ascertained by twelve people selected at random.

Word of God. Truth is ascertained by communication with God, perhaps via a third party.

Experimental science. The truth is guessed and the hypothesis is confirmed or refuted

by experiments.

Sampling. The truth is obtained by statistical analysis of many bits of evidence. For

example, public opinion is obtained by polling only a representative sample.

Inner conviction. “My program is perfect. I know this to be true.”

“I don‘t see why not...” Claim something is true and then shift the burden of proof to

anyone who disagrees with you.

Intimidation. Truth is asserted by someone with whom disagrement seems unwise.

Mathematics its own notion of “proof”. In mathematics, a proof is a verification of

a proposition by a chain of logical deductions from a base set of axioms. Each of the

three highlighted terms in this definition is discussed in a section below. The last section

contains some complete examples of proofs.

1.1 Propositions

A proposition is a statement that is either true or false. This definition sounds very general

and is a little vague, but it does exclude sentences such as, “What’s a surjection, again?”

and “Learn logarithms!” Here are some examples of propositions.