Berkeley COMPSCI 70  Lecture Notes (6 pages)
Previewing pages 1, 2 of 6 page document View the full content.Lecture Notes
Previewing pages 1, 2 of actual document.
View the full content.View Full Document
Lecture Notes
0 0 78 views
Lecture Notes
 Pages:
 6
 School:
 University of California, Berkeley
 Course:
 Compsci 70  Discrete Mathematics and Probability Theory
Discrete Mathematics and Probability Theory Documents

2 pages

7 pages

2 pages

2 pages

9 pages

3 pages

7 pages

2 pages

7 pages

3 pages

4 pages

8 pages

2 pages

CS70 Review  Logic and Induction
5 pages

Administrivia, Course Overview, Bad Proofs, Knights and Knaves, Quantifiers
3 pages

7 pages

Stable Marriage — An Application of Proof Techniques to Algorithmic Analysis
6 pages

15 pages

2 pages

2 pages

7 pages

3 pages

6 pages

7 pages

Randomized algorithms  a virtual chapter
5 pages

2 pages

7 pages

3 pages

2 pages

2 pages

2 pages

2 pages

12 pages

4 pages

100 pages

7 pages

6 pages

9 pages

2 pages

6 pages

2 pages

3 pages

4 pages

2 pages

2 pages

6 pages

2 pages

145 pages

2 pages

2 pages

2 pages

2 pages

4 pages

6 pages

2 pages

4 pages

3 pages

9 pages

2 pages

3 pages

Random Variables and Expectation
6 pages

6 pages

3 pages

6 pages

7 pages

Computability, Quantum Factoring
7 pages

Topics: Administrivia, Simple Induction, Bad Proofs, Strong Induction
3 pages

4 pages

8 pages

4 pages

7 pages

7 pages

2 pages

2 pages

7 pages

3 pages

6 pages

2 pages

10 pages

10 pages

10 pages

6 pages

9 pages

10 pages

9 pages

6 pages

7 pages

6 pages

8 pages

5 pages

7 pages

8 pages

5 pages

8 pages

7 pages

10 pages

7 pages

5 pages
Sign up for free to view:
 This document and 3 million+ documents and flashcards
 High quality study guides, lecture notes, practice exams
 Course Packets handpicked by editors offering a comprehensive review of your courses
 Better Grades Guaranteed
Unformatted text preview:
CS 70 Fall 2003 Discrete Mathematics for CS Wagner Lecture 17 Introduction to Probability The topic for the third and final major portion of the course is Probability We will aim to make sense of statements such as the following 1 There is a 30 chance of a magnitude 8 earthquake in Northern California before 2030 2 The average time between system failures is about three days 3 The chance of getting a flush in a five card poker hand is about 2 in 1000 4 In this load balancing scheme the probability that any processor has to deal with more than twelve requests for service is negligible Implicit in all such statements is the notion of an underlying probability space This may be the result of some model we build of the real world as in 1 and 2 above or of a random experiment that we have ourselves constructed as in 3 and 4 above None of these statements makes sense unless we specify the probability space we are talking about for this reason statements like 1 which are typically made without this context are almost content free Probability spaces Every probability space is based on a random experiment such as rolling a die shuffling a deck of cards picking a number assigning jobs to processors running a system etc Rather than attempt to define experiment directly we shall define it by its set of possible outcomes which we call a sample space Note that all outcomes must be disjoint and they must cover all possibilities Definition 17 1 sample space The sample space of an experiment is the set of all possible outcomes An outcome is often called a sample point or atomic event Definition 17 2 probability space A probability space is a sample space together with a probability Pr for each sample point such that 0 Pr 1 for all Pr 1 i e the sum of the probabilities of all outcomes is 1 Strictly speaking what we have defined above is a restricted set of probability spaces known as discrete spaces this means that the set of sample points is either finite or countably infinite such
View Full Document