6.042J / 18.062J Mathematics for Computer Science (SMA 5512), Fall 2002

Course Notes 15 - Milestones of Probability Theory.pdf......Page 0
What is a Proof?......Page 1
Propositions......Page 2
Axioms......Page 3
Logical Deductions......Page 4
Good Proofs and Bad Proofs......Page 5
The Induction Axiom......Page 7
Proof Format......Page 9
A Fibonacci Identity......Page 10
Geometry......Page 11
The Fate of Computer Science at MIT......Page 12
A False Proof......Page 14
The Strong Induction Axiom......Page 15
Postage Stamp Example......Page 16
Induction with nonzero base cases......Page 17
Winning the Game of Nim......Page 18
Induction, Strong Induction, and Least Number Principle......Page 19
Least Number Principle......Page 20
Properties of Relations......Page 23
Boolean Matrices......Page 24
Digraphs......Page 25
Composition......Page 26
Computing Composition and Path Lengths......Page 27
The Symmetric Closure......Page 29
The transitive closure......Page 30
Equivalence Relations and Partitions......Page 31
Partial Orders......Page 33
Directed Acyclic Graphs......Page 35
Topological Sorting......Page 36
Parallel Task Scheduling......Page 37
Increasing and Decreasing Sequences......Page 39
Not Simple Graphs......Page 41
Graphs in the Real World......Page 43
Graph Isomorphism......Page 44
Vertex Degree......Page 45
Chromatic Number......Page 46
Paths in Graphs......Page 47
Adjacency Matrices......Page 48
Connectedness......Page 49
Trees......Page 52
Euler Tours......Page 55
Hamiltonian Circuits......Page 56
Die Hard......Page 58
Basic definitions......Page 59
Examples......Page 60
Executions of state machines......Page 61
Reachability and Invariants......Page 62
The Robot......Page 63
Sequential algorithm examples......Page 64
The Euclidean Algorithm......Page 65
Termination of GCD......Page 66
Fast Exponentiation......Page 67
Extended GCD......Page 68
Derived Variables......Page 69
The Stable Marriage Problem......Page 70
The Problem......Page 71
The State Machine Model......Page 73
They All Live Happily Every After…......Page 75
…And the Boys Live Especially Happily......Page 76
Another Robot......Page 77
Well-founded Partial Orders......Page 79
Terminating Games of Perfect Information......Page 81
Recursive Definitions......Page 85
Structural Induction on Recursive Data Type Definitions......Page 89
Induction on Trees......Page 90
Some Recursively Defined Functions......Page 92
Recursive Function Definitions......Page 93
Proving Properties of Recursive Functions......Page 94
Recursive Functions on Natural Numbers......Page 95
Ill-formed Definitions......Page 96
Induction in Computer Science......Page 97
Annuities......Page 98
The Value of an Annuity......Page 99
The Sum of a Geometric Series......Page 100
Infinite Geometric Series......Page 101
Examples......Page 102
Related Sums......Page 103
Formalizing the Problem......Page 104
Evaluating the Sum---The Integral Method......Page 107
More about Harmonic Numbers......Page 108
Finding Summation Formulas......Page 109
Double Sums......Page 110
Stirling\'s Approximation......Page 111
Little Oh......Page 113
Big Oh......Page 115
Theta......Page 116
The Exponential Fiasco......Page 117
Equality Blunder......Page 118
Matchings as Bijections......Page 119
Counting Functions......Page 120
The Pigeonhole Principle......Page 121
20 Questions and Binary Search......Page 122
Example: Weighing Coins......Page 123
The Sum Rule......Page 125
Inclusion-Exclusion Principle (special cases)......Page 126
Inclusion-Exclusion Principle (general case)......Page 128
Counting Primes......Page 129
Products of Sets......Page 131
Tree Diagrams......Page 133
A Problem Getting Dressed......Page 134
Playoff Outcomes......Page 135
Simple Permutations......Page 136
A Lower Bound for Sorting......Page 137
r-Permutations......Page 139
The Division Rule......Page 140
Combinations......Page 142
The number of r-Combinations (Binomial Coefficients)......Page 143
Some interesting special cases......Page 144
Hands with Four-of-a-Kind......Page 145
Hands with Two Pairs......Page 146
Four different ranks......Page 148
Reminders......Page 149
How the Trick Works......Page 150
Same Trick with 4 Cards?......Page 151
Hall\'s Theorem applied to the Magic Trick......Page 152
Hall\'s Marriage Theorem......Page 153
Proof of Hall\'s Theorem by Induction [Optional]......Page 154
Properties of Binomial Coefficients......Page 155
The Binomial Theorem......Page 159
Principle of Inclusion and Exclusion......Page 160
Counting r-Permutations with Repetition......Page 161
Permutations with Limited Repetition......Page 162
Multinomial Coefficients......Page 163
Counting r-Combinations with Repetition......Page 164
Triple-Scoop Ice Cream Cones......Page 165
Balls and Bins......Page 166
r-Combinations with at Least One of Each Item......Page 167
r-Combinations with Limited Repetition......Page 168
Data Compression [Optional]......Page 169
Modelling Experimental Events......Page 171
The Monty Hall Problem......Page 173
Assumptions......Page 175
Assigning Probabilities to Outcomes......Page 176
Intransitive Dice......Page 178
Basic Laws of Probability......Page 181
Carnival Dice......Page 183
More Intransitive Dice [Optional]......Page 184
Derangements [Optional]......Page 185
Conditional Probability......Page 186
Conditional Probability Examples......Page 187
A Two-out-of-Three Series......Page 188
An a posteriori Probability......Page 190
A Problem with Two Coins [Optional]......Page 191
A Variant of the Two Coins Problem [Optional]......Page 192
Medical Testing......Page 193
Confusion about Monty Hall......Page 195
Discrimination Lawsuit......Page 196
A false analysis......Page 197
The Law of Total Probability......Page 198
On-Time Airlines......Page 199
Probability that the First Player Wins......Page 200
The Sample Space......Page 201
The Definition......Page 202
The Independent Product Rule......Page 203
Disjoint Events vs. Independent Events......Page 204
An Experiment with Two Coins......Page 205
A Variation of the Two-Coin Experiment......Page 206
Example: Blood Evidence......Page 207
Definition of Mutual Independence......Page 208
A Red Sox Streak [Optional]......Page 209
An Experiment with Three Coins......Page 210
Pairwise Independence......Page 211
Solution......Page 212
Approximating the Answer to the Birthday Problem......Page 214
The Birthday Principle......Page 215
Random Variables......Page 216
Probability of Events Defined by a Random Variable......Page 217
Proving that Two Random Variables are Not Independent......Page 219
A Dice Example......Page 220
Mutual Independence......Page 221
Bernoulli Distribution......Page 222
Binomial Distribution......Page 223
A Winning Strategy......Page 224
The Space Station Mir......Page 226
Leader Election......Page 227
The Shape of the Binomial Distribution......Page 228
The tails......Page 229
25 Heads in 100 Tosses......Page 231
Transmission Across a Noisy Channel......Page 232
Two Equivalent Definitions......Page 233
Expected Value of One Die......Page 234
Modified Carnival Dice......Page 235
Expectation of Natural Number-valued Variables......Page 236
Mean Time to Failure......Page 237
An Expectation Paradox......Page 238
Expectation of a Sum......Page 240
The Hat-Check Problem......Page 241
The Chinese Appetizer Problem......Page 242
Expectation of a Binomial Distribution......Page 243
Conditional Expectation......Page 244
The Product of Independent Expectations......Page 245
A RISC Paradox......Page 246
A Probabilistic Interpretation......Page 247
A Simpler Example [Optional]......Page 249
Convergence Conditions for Infinite Linearity......Page 250
Solution to the Paradox......Page 251
Random Length Sums......Page 252
The Sample Space......Page 255
The Expected Number of Tries......Page 256
The Expected Number of Steps......Page 257
A Better Way to Build Systems......Page 258
What the Mean Means......Page 259
The Weak Law of Large Numbers......Page 260
Markov\'s Theorem......Page 261
Examples of Markov\'s Theorem......Page 262
Why R Must be Nonnegative......Page 263
Using Markov To Analyze Non-Random Events [Optional]......Page 264
Chebyshev\'s Theorem......Page 265
Example: Gambling Games......Page 266
Standard Deviation......Page 267
An Alternative Definition of Variance......Page 268
Expectation Squared [Optional]......Page 269
Dealing with Constants......Page 270
Variance of a Sum......Page 271
Variance of a Binomial Distribution......Page 272
I.Q. Example......Page 273
Estimation from Repeated Trials......Page 274
Birthdays again......Page 276
Size of a Poll......Page 277
Confidence Levels......Page 278
Better Polling......Page 279
Proof of the Weak Law......Page 280
Random Walks and Gamblers\' Ruin......Page 281
The Unbiased Game......Page 283
A Recurrence for the Probability of Winning......Page 285
Intuition......Page 287
Duration of an Biased Walk......Page 289
Duration of an Unbiased Walk......Page 290
Quit While You Are Ahead......Page 291
Infinite Expectation......Page 292
The Probability of at Least One Event......Page 293
Probability of at least k events......Page 295
Example: Pick 4......Page 296
The constant in the exponent......Page 297
Proof of the Bound......Page 298
How to Build One Switch......Page 299
A Generalized Chernoff Bound......Page 300
Review of Markov, Chebyshev, Chernoff and Binomial bounds......Page 301
Poisson Random Variables......Page 303
Properties of the Poisson Distribution......Page 305
The Central Limit Theorem......Page 306
Strong Law of Large Numbers [Optional]......Page 308
A Failure of the Strong Law......Page 309