16.322 Stochastic Estimation and Control, Fall 2004 Prof vander velde Lecture 1 e-reginisites 6.041-Probabilistic systems of the subject(topics) 1. Brief review of probability a. Example applications 2. Brief review of random variables a. Example applications 3. Brief review of random processes a. Classical description b. State space description ener erin 5. Optimum control system design 7. Kalman filtering a. Discrete time b. Continuous time Textbook Brown,RGand.YC. Hwang. Introduction to Random Signals and Applied Kalman filtering Course administration All important material presented in class Read text and other references for perspective Do the suggested problems for practice-no credit is offered for these Two (2)hour-long quizzes will be held in-class-open book One(1)three hour final exam-open book
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde Lecture 1 Pre-requisites 6.041 – Probabilistic systems Summary of the subject (topics) 1. Brief review of probability a. Example applications 2. Brief review of random variables a. Example applications 3. Brief review of random processes a. Classical description b. State space description 4. Wiener filtering 5. Optimum control system design 6. Estimation 7. Kalman filtering a. Discrete time b. Continuous time Textbook • Brown, R.G. and P.Y.C. Hwang. Introduction to Random Signals and Applied Kalman Filtering. Course Administration • All important material presented in class • Read text and other references for perspective • Do the suggested problems for practice – no credit is offered for these • Two (2) hour-long quizzes will be held in-class – open book • One (1) three hour final exam – open book Page 1 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof vander velde Brief Introduction to Probability Reference 1. Papoulis Probability, Random Variables, and Stochastic Processes. (Best for probability and random variables Define the model of uncertainty -the random experiment Discrete sample space Continuous sample space ole Out not ts, but A probability function must be defined over the sample space of the random Events are associated with collections or sets, of these outcomes Events aB Page 2 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde Brief Introduction to Probability References: 1. Papoulis. Probability, Random Variables, and Stochastic Processes. (Best for probability and random variables) Define the model of uncertainty – the random experiment. Discrete sample space Continuous sample space Outcomes are points, spanning sample Outcomes are not points, but span a space continuum A probability function must be defined over the sample space of the random experiment. Events are associated with collections, or sets, of these outcomes. Events A,B Page 2 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof vander velde Compound Events A+B+C,or"i means the event A occurs, or B occurs, or C occurs, or any combination of them occur ABC. and" means the event a and b and c occur A, not, means the event a does not occur; Complementary event A A+B+C Venn diagram Probability Functions The probability measure of an event is the integral of the probability function over the set of outcomes favorable to the event. One definition: P(E)=lim n(E) 月→∞ Properties of probability functions P(empty set)=0 P(sample space)=1 0≤P(E)<1 Basic axiom of probability: Probabilities for the sum of mutually exclusive events dd P(A+B+C)=P(A)+P(B)+P(C) Page 3 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde Compound Events A+B+C, “or”; means the event A occurs, or B occurs, or C occurs, or any combination of them occur ABC, “and”; means the event A and B and C occur A , “not”; means the event A does not occur; Complementary event Venn diagram Probability Functions The probability measure of an event is the integral of the probability function over the set of outcomes favorable to the event. One definition: n E () = lim ( ) PE n→∞ N Properties of probability functions: P(empty set) = 0 P(sample space) = 1 0 ≤ P E( ) < 1 Basic axiom of probability: Probabilities for the sum of mutually exclusive events add. PA B C ( + + ) = PA ( ( ( ) + PB ) + PC ) Page 3 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof vander velde A Mutually exclusive events Example: Rolling a fair die Fair means all faces are equally likely. There are 6 of them. They are mutually exclusive and their probabilities must sum to 1. Therefore, P(each face) P( even number)=P(2+4+6)=P(2)+P(4)+Pb/1111 6662 Independence: Definition of independence is probabilities of joint events multiply P(ABC.)=P(A)P(B)P(C) This is consistent with our intuitive notion of independence: the occurrence of A has no influence on the likelihood of the occurrence of b etc P(AB)=P(AP(B) Example: Rolling two dice Consider the two dice independent P(sum of dots is 4)=P(1, 3+2, 2 +3, 1) P(1,3)+P(2, 2)+P(3, 1)mutually exclusive P(I)P(3)+P(2)P(2)+P(3)(I) independent 6(666)6(6)3612 Page 4 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde Mutually exclusive events Example: Rolling a fair die “Fair” means all faces are equally likely. There are 6 of them. They are mutually exclusive and their probabilities must sum to 1. Therefore, P(each 1 face) = . 6 1111 P(even number) = P(2 + +4 6) = P(2) + P(4) + P(6) = + + = 666 2 Independence: Definition of independence is probabilities of joint events multiply. P ABC ( ( ) ( ) ( ...) = P A P B P C )... This is consistent with our intuitive notion of independence: the occurrence of A has no influence on the likelihood of the occurrence of B, etc. P AB ( ( ) ( ) = PAPB ) Example: Rolling two dice Consider the two dice independent. P(sum of dots is 4) = P(1, 3 + 2, 2 + 3,1) = P(1, 3) + P(2, 2) + P(3,1) mutually exclusive = P P (1) (3) + P(2)P(2) + P(3)P(1) independent 11 ⎛ ⎞ 11 ⎛ ⎞ 1 1⎛ ⎞ 3 1 = ⎜ ⎟ + ⎜ ⎟ + ⎜ ⎟ = = 66 ⎝ ⎠ 66 ⎝ ⎠ 6 6⎝ ⎠ 36 12 Page 4 of 7
16. 322 Stochastic Estimation and Control. Fall 2004 Prof vander velde Any situation where there are N outcomes, equally likely and mutually exclusive may be treated the same way The probability of each event if there are N mutually exclusive, equally likely events possible Mutually exclusive: P(∑E)=∑P Equally likely: p,=p P(∑E)=P(S)=∑p =∑P(E) P If a certain compound event E can occur in n(E) different ways, all mutually exclusive and equally likely, then P(E=n(E)P(each) n(E) number of ways e occurs number of possible outcomes Some combinatorial analvsis Given a population of n elements, take a sample of size r. How many different samples of that kind are there? We must specify in what way the sample is taken: with replacement (repetitions possible)or without replacement(no repetitions). We can do this either with or without regard for order The difficulty when you do repetitions is that some orderings give you a different sample but others do not. E.g. 7-5-2-5 is distinct from 2-5-7-5, but when he 5's are swapped the outcome is the same 1. The number of different samples of size r from a population of n in sampling without replacement but with regard to order is n(n-1)(n-2).(n-r+1)= (n-r)! Page 5 of7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde Any situation where there are N outcomes, equally likely and mutually exclusive may be treated the same way. The probability of each event if there are N mutually exclusive, equally likely events possible: Mutually exclusive: P(∑E ) = ∑ p i i i i Equally likely: p = p i P S( ) = 1 : P(∑E ) = P S( ) = ∑ p i i all i all i N = ∑P E( )i i=1 = Np = 1 1 p = N If a certain compound event E can occur in n(E) different ways, all mutually exclusive and equally likely, then P E( ( ) ) = nEP (each) nE ( ) = N number of ways E occurs = number of possible outcomes Some Combinatorial Analysis Given a population of n elements, take a sample of size r. How many different samples of that kind are there? We must specify in what way the sample is taken: with replacement (repetitions possible) or without replacement (no repetitions). We can do this either with or without regard for order. The difficulty when you do repetitions is that some orderings give you a different sample, but others do not. E.g. 7-5-2-5 is distinct from 2-5-7-5, but when the 5’s are swapped the outcome is the same. 1. The number of different samples of size r from a population of n in sampling without replacement but with regard to order is: n! n n( −1)(n − 2)...(n − +r 1) = (n r − )! Page 5 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. VanderⅤelde 2. The number of orderings of r elements is r(r-1)(r-2).(1)=r! 3. The number of different samples of size r from a population of n in sampling without replacement and without regard for order is x= number without regard for order r!= number of orderings of each number with regard for order (n-r)! !(n-r) Example: Massachusetts Megabucks Lottery Choose 6 numbers from 42 without replacement without regard for order 42! number of megabucks bets =5,245,786 6)6!(36)! called the binomial coefficient and is abbreviated sober of ways in which The last fraction-which may be described as the numb objects can be selected from n without regard for order and without repetitions is Binomial coefficient r!(n-r)! It's name is derived from Newtons binomial formula, where it forms the coefficient of the rth term of the expansion for(1+x) A useful estimate when calculating factorials is Stirlings Formula n(2 The symbol means the ratio of the two sides tends toward unity. It is read as asymptotic. While the absolute error tends to oo, the relative error tends to zero Page 6 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde 2. The number of orderings of r elements is: r r( −1)(r − 2)...(1) = r! 3. The number of different samples of size r from a population of n in sampling without replacement and without regard for order is: n! x r⋅ =! , where (n r − )! x ≡ number without regard for order r! ≡ number of orderings of each n! ≡ number with regard for order (n r − )! n! n ⎛ ⎞ n x = = Cr = ⎜ ⎟ r n r !( − )! r⎝ ⎠ Example: Massachusetts Megabucks Lottery Choose 6 numbers from 42 without replacement without regard for order. ⎛ 42⎞ 42! number of megabucks bets = = = 5, 245, 786 ⎜ ⎟ ⎝ 6 ⎠ 6!(36)! The last fraction – which may be described as the number of ways in which r objects can be selected from n without regard for order and without repetitions is ⎛ ⎞ n called the binomial coefficient and is abbreviated ⎜ ⎟. r⎝ ⎠ Binomial coefficient: ⎛ ⎞ n n! = r⎝ ⎠ r n r )! ⎜ ⎟ !( − It’s name is derived from Newton’s binomial formula, where it forms the n coefficient of the rth term of the expansion for (1 + x) : n n ⎛ ⎞ n r (1 + x) = ∑⎜ ⎟ x r r=0 ⎝ ⎠ A useful estimate when calculating factorials is Stirling’s Formula: ⎛ 1 ⎞ ⎜ n+ n! ∼ 2π n⎝ 2 ⎠ ⎟ e−n The symbol ‘~’ means the ratio of the two sides tends toward unity. It is read as asymptotic. While the absolute error tends to ∞ , the relative error tends to zero. Page 6 of 7
16. 322 Stochastic Estimation and Control. Fall 2004 Prof vander velde 8 10 0.8 100 0.08 Page 7 of 7
16.322 Stochastic Estimation and Control, Fall 2004 Prof. Vander Velde n % error 1 8 10 0.8 100 0.08 Page 7 of 7