Topics in Finite Mathematics
Topics in Finite Mathematics MATH 210
Popular in Course
Popular in Mathematics (M)
This 20 page Class Notes was uploaded by Zechariah Hilpert on Thursday September 17, 2015. The Class Notes belongs to MATH 210 at University of Wisconsin - Madison taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/205286/math-210-university-of-wisconsin-madison in Mathematics (M) at University of Wisconsin - Madison.
Reviews for Topics in Finite Mathematics
Report this Material
What is Karma?
Karma is the currency of StudySoup.
Date Created: 09/17/15
MATH 210 7 Lecture 1 Finite Mathematics Semester I 2007 2008 CONTINUOUS RANDOM VARIABLES This handout augments the material in Section 43 of the text Often7 a random variable X has a continuum of possible values7 rather than taking values from a nite set7 and the probability that X is equal to any speci c value is zero In theory7 X may take on any real number as a value7 although in practice7 we often have some bounded range into which were 100 sure that X will fall For example7 if X represents the weight of a random human in pounds7 we dont have a nite list of possible values of X lt7s fairly safe to say that Pr0 S X S 10000 1 Its also safe to say that the probability that you weigh a speci c value7 say7 exactly 1652319493214 pounds7 is essentially zero in symbols7 PrlX a 0 for each a Let fx be a function such that f 2 0 for all z and the total area between the z axis and the graph of f is exactly 1 We say that a random variable X has probability density function f if PrX a is always 07 and7 when a lt b7 Pra S X S b is the area bounded by the z axis7 the graph of f7 and the lines z a and z b l 2 i In this picture7 we de ne fx to be 2z371z2 for 72 S x S 3 and 0 for other values Then the area under the entire curve f is 17 and Pr1 S X S 2 is exactly 032096 you can see by eye that the shaded area is approximately 13 the total area Unfortunately7 to actually compute these values7 you have to be able to compute the area under a curve given a formula for the curve You learn that in calculus take Math 211 In this course7 well only study examples where you can compute the area either by elementary geometry see the example below7 or by using the table in Appendix A of the text for the standard normal curve see Section 43 for examples H174 You know how to compute the area of a rectangle so you should be able to answer questions based on the de nition 0 ifxlt0 04 if0 xlt2 02 if2 xlt3 0 if3 z Let fx Let X be a random variable with probability density function f Then nd 1 Pr1Xlt2 5 PrX2lX21 2 Prngl 6 PrX21lX 2 3 PrX 215 7 PrX 25 l X 215 4 Pr1 X 3 8 PrX215lX 25 04 i 02 l l 1 1 2 3 When you7re given a problem like this you should check that the total area under f is really equal to 1 Otherwise the problem is meaningless Most practical problems result in a density function which is curvy and we wont discuss that in this course unless its the normal distribution function A problem which would result in this particular f is Imagine a 10 mile long straight road in the desert with two bars along it 7 one at the 3 mile mark and one at the 7 mile mark You7re dropped at random along this road Then the random variable X is your distance to the closest bar ZI 8 017 0 a S Xlld a S X 1le ama U 1le HWle 9 0 Jemsuv 17 0 60 117 0 90 S We em OS ei umoel Z OX I e pue e ueqoei 170 gtlt 90 e 10 uoiun sq s1 siqL on JSMSUV 9010 H 01 533 9 to Equally likely outcomes all the wi are equal Then PTE Chapter 2 Probabilities Counting 1 Probabilities Sample space 5 consists of all possible outcomes of an experiment An event E is a subset of S We can even have that E S or E g In a sample space S with n outcomes 017 M On7 we assign a probability to S by assigning a number wi 2 0 to each outcome 01 of S such that wl wn 1 Then wi is called the weight of Oi If E is an event of S then PTE is the sum of the probabilities of the outcomes in E Fact 0 S PTE S 1 for all events E Also7 PT 07 PTS l M n5 Examples of equally likely outcomes a fair coin7 b fair die7 c choosing from a deck of cards PTE PTE 1 2 Permutations Permutation An ordered sequence of T different elements of X Two permutations are the same if they contain exactly the same elements in exactly the same order In other words7 two permutations are different if either they have dif ferent elements7 or ii they have the same elements but in a different order PnT number of permutations of T elements taken from a set with n elements PnT Pnn nl Permutation Principle The number of permutations of T objects selected from a set of n distinct objects is nl PnTnniln7TlW 01 H to H g 3 Combinations i Combinations Cn7 T ways of selecting T objects from given n distinct objects7 Where the order in Which we select them does not matter To get permutations choose T objects from given n objects Without order7 ii permute the selected T objectsi i PnT CTL77 PTT CTL77 Tl i CTL77 i If the sample space is split into different cases7 then the number of out comes of each case should be added If the experiment consists of stages7 the numbers of results at each stage are multiplied because of the multi plication principlei Chapter 5 Systems of Linear Equations 1 9 9 539 N533 HF HO For any numbers A B C with A and B not both zero at the same time the set of points zy Ax By C is a line If 11 yl and zgy2 are two points on this line then we say call this set of points the line through rhyl and 12y2 and we have that A11 Byl CAzg Byg C The equation Ax By C is called the equation of a line If a line has equation Ax by C with A f 0 then it intersects the z axis in exactly one point which is called the x interceptl Similarly if B 0 it intersects the y axis in exactly one point the y interceptl The line Ax by C has an x intercept if A f 0 and the x intercept is CAl The line has a y intercept if B 0 and the y intercept is CBi Another way to do this To nd the x intercept put y 0 in the equation and nd the value of x To nd the y intercept put I 0 in the equation and nd the value of y Let AzBy C be a line passing through the points 11 yl and 12 y2i If 11 f 12 then we say that the slope m of the line is y27y1 m i 12 11 If 12 11 and yg a y1 then the line is vertical and we say that the slope is not de ned The slope of a line does not depend in which points 11 yl and zgy2 we choose When the slope of a line is m 0 then the line is horizontal If B 0 the slope of the line Ax By C is m igi If B 0 then the slope is not de ne Two lines are parallel if they have the same slope or if the slope is unde ned for both Another form of the equation of a line is y mz 12 where m is the slope and b is the y interceptl The solution of a system of linear equations is their point of intersectioni If two lines have the same slope and their equations are not multiples of each other then they are parallel so they do not have a common point of intersection Therefore the system of equations does not have a solution ii If two lines have the same slope and their equations are multiples of each other then they are the same line so they have in nitely many solutions H 533 to 9 9 To solve systems of 2 equations with two unknowns 1 Method of elimination Multiply one of the equations by a multiple of the other in such a way so that when you add them one of the unknowns disappears Then you can nd the other unknown ll Method of substitution Solve the rst equations in terms of one of the unknowns and replace that unknown in the second equation A system of equations that has at least one solution is called consistent and one with no solutions is called inconsistent Theorem on transforming systems of equations If a system of equations is transformed into a new system by any of the following operations a lnterchange 2 equations b Multiply any equation by a nonzero number c Replace any equation by the sum of that equation and a multiple of any other equation then the set of solutions of the transformed system is the same as the set of solutions of the original system A matrix is in reduced form if it has the following properties a The entry in the rst row and rst column of the coefficient matrix is l and te rst nonzero entry in each row is l b If a column of the coefficient matrix contains a leading 1 then all other entries in that column are c s you move rom e o r1g roug e co umns o e coe c1en A f lftt 39htth hth l fth f 39 t matrix the le ing is occur in successive rows In particular all rows with only 0s are at the bottom of the matrix In this case we can nd the solutions of the new system easily Algorithm for solving a system of linear equations a Form the augmented matrix b Use row operations to transform the augmented matrix into reduced form c lnterpret the reduced form to obtain information about the solution set i If there is a row with zeros to the left of the vertical line and a nonzero entry to the right then the system has no solutions If the system has n equations in n variables and the reduced form has a leading l in each row then there is a unique solution If a consistent system has n variables and the reduced form has 16 k lt n nonzero rows then there are in nitely many solutions in n 7 k of the variables can be speci ed arbitrarily 17 To transform the augmented matrix into reduced form Multiply rst row accordingly to get a 1 in the rst spot switch rows to get a nonzero number there if necessary Add or subtract a multiple of the rst row to the other rows to create zeros everywhere else in the rst column Now multiply the second row accordingly to get a 1 in the second spot of the main diagona l Keep the second row xed and add or subtract multiples of it to the other rows to get zeros everywhere else in the second column Repeat as many times as necessary 1 to bk 539 Chapter 3 Probability Measures Preliminaries A map f X A Y is a function that takes an element of the set X to an element of the set Y We write 01 for the set of real numbers between 0 and 1 So a map f X A 01 takes an element of X and gives it a value between 0 and 1 Probability measure Idea If we have a sample space S a collection of outcomes we want to assign to each outcome 01 a weight PTOZ39 wi with 0 S wi S 1 that decribes the frequence of appearance of the outcome Oi We want the sum of all the weights in S to be equal to 1 This way we also give a weight to every event in the sample space For example the event E 01 02 gets the weight PTE wl 112 Observe that we also have 0 S PTE S 1 Now let us make this more formal We let PT be a map from the collection 8 of all events subsets of S 0 01 PT S A 01 that takes the event E to sum of probabilities of outcomes in E We call the map PT the probability measure We require PT to satisfy the following axioms a For every event E we must have 0 S PTE S 1 b PTS 1 c If EZ Ej ie EZ and Ej are disjoint then PTEZ39 U Ej PT PTEJ39 From the last axiom we can also prove that a PT 0 b If E1E2 M Ek are pairwise disjoint ie any two of them are dis joint then PTE1 U E2 U U Ek PTE1 PTE2 PTEk RemaTk 1f PTE 0 then that does not imply that E PTE UF PTE PTF 7 PTE PTEUFUG PTEPTFPTG 7PTE F 7PTEQG 7PTF G PTE Fm G If A and B are events in the sample space S of an experiment and PT E f 0 then the conditional probability of event A given B is PTA B T PTAB P B on F1 9 50 H O H H H CA3 The events A and B are independent if PTA B PTAPTB This turns out to be the same as PTAB PTA When the outcomes of our space are equally likely we can write PTAB PrA B B PH This way we do not need to calculate Stochastic Process an experiment which consists of multiple subexperi ments To nd the probability of an event in this case we do the following a Draw a tree diagram assign probabilities to each branch of the tree b Find the probability of an outcome by multiplying the branches of the tree that give us that outcome c Add all the probabilities of the outcomes of the event we need Bayes Probabilities The idea is to nd PTBA assuming that we know PTAB Simple Bayes Formula PTBA m General Bayes Formula Let S be a sample space and 51 52 M 5k is a partition lf PTSZ39 gt 0 and the event A has PTA gt 0 then PTAS PTS A51PT51 PTASQPTSQ PTAS PTS Hwy PT Section 35 Bernoulli trials Bernoulli trial an experiment with two possible outcomes success and failure Bernoulli process a sequence of identical Bernoulli trials Any trial in the Bernoulli process is independent from any of the others If you have a Bernoulli process with n trials with success probability p and failure probability 4 l 7p then the probability of obtaining exactly 7 successes is PT7 successes in n trials CnTqu Example For a fair coin p q so the probability of obtaining 7 Cn7 times heads is 2 In a Bernoulli process with n trials PT0 successes PTl successes PT11 successes l H 3 9 7 Cf 03 5 00 Math 210 Worksheet 5 Let Pr be a probability measure on S with EF C S Assume that PrE lF PrFlE g7 and PrlE U F 2 Find PHELPHF7 and PTE Let Pr be a probability measure on S with E F G C S Assume that they satisfy PrE o F m G 02 PrE 055 PrF 055 PrGl 0757 PrE o F 085 PrE o G 085 PrF o G 09 Find PrE o F m G You roll two fair dice7 and add up the two numbers7 so the number you roll is between 2 and 12 Let E be the even the number you roll is between 3 and 12 Let F be the event the number you roll is between 2 and 11 Find PrlElFl and PrFlE Consider the following experiment You repeatedly roll a die7 and STOP when either your die comes up 1 07quot your die comes up 2 07quot the product of all the numbers you have rolled is 10 or larger Find the sample space of this experiment You can either draw a tree here7 or you can just list all the possible outcomes An unfair die has probabilities w1w2w3w4w5w6 of coming up 17273747576 re spectively Assume that 1 and 2 are equally likely7 and 3 and 4 are equally likely7 and 5 and 6 are equally likely Also assume that 4 is twice as likely as 27 and 6 is twice as likely as 4 Find the probability that the number you roll is 4 or larger A standard deck of cards has 52 cards Out of this hand7 you randomly deal a bridge hand consisting of 13 cards What is the probability your hand contains exactly 2 of some suit7 exactly 3 of some other suit7 and exactly 4 from the remain ing 2 suits For example7 you could get 2 clubs7 3 diamonds7 4 hearts7 4 spades7 or 2 hearts7 3 spades7 4 diamonds7 4 clubs7 or etc Your answer should be of the fo you dont have to simplify it You may use the factoriall symbol in writing your answer Consider the following experiment Keep tossing a fair coin until you7ve tossed either two heads or three tails So7 you will toss 2737 or 4 times Find the probability that your last toss is a tail Solve the system of equations 1x 3y 52 8 3x 6y 92 12 2z3y3210 There is a unique solution here 9 H O H D H CO Say which of the following transition matrices A Markov chain has three states State 1 State 2 and State 3 It has the transition matrix P shown below Find the vector W of stable probabilities so WP There is a unique solution here quotU H HOOCTJ ixa39onio NHM is regular and explain why one is regular and one is not 12 88 0 0 0 77 23 0 P 0 0 12 88 25 0 0 75 13 31 56 0 Q7 0 29 71 0 12 47 41 0 28 0 11 61 7 The Wonder Widget Corporation can a ord payments of 2000 per month to amortize a loan The rate of interest for companies with credit ratings similar to that of Wonder Widget is 9 perent per year How large a loan can the company a ord if the loan is amortized over 5 years Over 10 years The Fast Haul Trucking Company can arrange to make sinking fund payments of 6000 semiannually The best interest rate it can receive on its money is 10 percent per year compounded semiannually How many periods are necessary for Fast Haul to accumulate 100000 The lnterstate Bran Muf n Company decides to raise funds for expansion by issuing zero coupon notes payable in 5 years The offering price is 800 for a 1000 note If such a note is purchased and held to maturity what is the annual percentage yield to the investor Henry has won a 100 000 prize in the lottery and he plans to set aside a portion of his winnings for his daugter7s college education She will begin college in 12 years He sets aside 20000 and deposits it in an account which pays interest at a rate of 45 percent compounded quarterly a How much will be available in 12 years b If he withdraws 5000 each year for 4 years starting at the end of year 12 how much remains in the account after the last withdrawal An amount of 10 000 is to be invested for 5 years ls it more pro table to invest it in an account which pays 6 percent per year compounded daily or in an account which pays 625 percent per year compounded quarterly 16 Solve the following system of equations using a matrix 33y323w3u12 7y27w72u72 3z2yz4w75u72 72z72y4272w72u4 75x4y7322w7u714 There is a unique solution here 17 10 points A Markov chain has three states State 1 State 2 State 3 Assume that it has the transition probabilities given by the diagram below and that it is known to be in State 2 on the initial observation Find the probability that it is in each of the States 123 after two transitions 4 18 Using the inverse of a matrix solve the system of equations 19 D O abci2d9 2a73b7504d79 3ab74072d4 72b 40 2d 9 Find the monthly payments that are necessary to amortize a loan of 25 000 over 5 years with interest at 7 annual rate Here you may leave your answer as an arithmetical expression without evaluating it You need to have some money ve years from now so you put money in a sinking fund depositing monthly into an account which pays 8 interest annual rate compounded quarterly Each month you deposit 50 How much money will you have at the end of the ve years Here you may leave your answer as an arithmetical expression without evaluating it 3 D H D D LetP 0 0 1 Let P andX Show that X1310 X 0 1 0 Find a vector X that satis es XP X 25 25 5 Find a 2 gtlt 2 matrix B such that AB C where 10 77 722 15 1 A 73 i2 4andClt Draw the diagram for the Markov chain which has the transition matrix 3 3 2 2 i 67 0 0 33 0 0 1 0 0 1 0 0 ls P is regular or not Why or why not If it is regular then what is the vector of stable probabilities c If it is regular in which state is the system most likely to be in the long run Find the matrix P2 of two transition probabilities If our initial state is State 1 nd the probability of being in State 2 after 3 transitions ls P the matrix of an absorbing Markov chain If yes then nd the fundamental matrix and the expected number of times of passing through a nonabsorbing state before reaching an absorbing one if we are initially in State 2 Answer the same questions for the Markov chain with transition matrix 3 3 2 2 67 0 0 33 Q 7 0 1 0 0 0 0 1 0 Say which of the following transition matrices correspond to an absorbing Markov chain and explain why Write the ones that correspond to an absorbing Markov chain in canonical form and nd the fundamental matrix 1000 0001 P 0010 l0100l 4 5 01 009910 Q 052480 0 0 01 090811 010 0 R130087 0001 26 Determine which of the experiments in gures 81 82 and 84 of the book are D D 3 3 K O H Markov chains Why is your claim true Let k be a number and let 1 1 2 A 1 0 k 0 1 0 Which of the following is a true statement The matrix A has an inverse for all values of k b The matrix A has an inverse for no values of k c The matrix A has an inverse for all k except k 2 d The matrix A has an inverse for all k except k 1 Let A B and C be 2 gtlt 2 matrices and suppose 2 1 2 6 A73 1 and Clt1 73 a Find B such that AB C b Find B such that EA C Two fair dice one red and one green are rolled A random variable X is de ned as follows a If the number on the red die is 1 then X the number on the green die b If the number on the red die is not 1 then for each result on the green die X the number on the red die plus 2 Find the expected value of X When a certain basketball player makes a shot she is three times as likely to make her next shot as to miss her next shot On the other hand if she misses a shot she misses the next shot with probability 7 Assuming he shooting obeys the rules of a Markov chain how likely is she to make her 100th shot of the season A random variable X has the density function shown below Find the expected value variance and standard deviation of X You may leave the result for 0X in terms of a square root D Value of X Probability 20 3 10 2 0 15 10 1 20 15 30 1 Solve the system of equations 3x 7 ay 7b 74axibya H N 9 9 03m F1 9 to Chapter 4 Random Variables Random variable on a sample space S a function that for each element of 5 it gives you a real number It gives use exactly one number for every element of 5 Example You roll the die in a casino and you get 12 if you roll 1 or 2 60 if you roll 3 and 10 if you get 45 or 6 Binomial random variable if you have a Bernoulli process then you de ne a random variable X to be the number of successes Then it is called a binomial random variable The probability density function or simply density function of a random variable X If X can take the values X1X2 Xk then the probability density function is a function f that assigns probabilities pi to the values Xj In other words fX1 p1 PTX X1 fX2 p2 PTX X2 M fXk pk PTX Xk If X is a random variable that takes the values X1 M Xk with probabilities In M pk respectively then the expected value of X or expectation or mean of X is M Ele 11101 12102 1km An easy way to remember the notation E stands for 7Expected value7 and M which is the Greek letter that corresponds to m stands for 7Mean7 Variance VaTX p1zl 7 m2 p2zg 7 m2 pkzk 7 M Standard deviation aX VaTX An easy way to remember the notation Var stands for 7Variance7 and a which is the Greek letter corresponding to 8 stands for 7Standard de viation7 Theorem Bernoulli If n number of trials p probability of heads 4 l 7 p probability of tails If X number of Heads and Y number of Tails then i Ele n10 iiEYl n47 iiiVarle npqy iV0le xnqu lf Z aXbY where X Y Z are random variables and a b are numbers then EZ aEX bEY Standard normal random variable the usual bell curve It has the following properties i The probability that Z takes a value between a and b is the are under the standard normal curve between 2 a and 2 12 ii PTZ 2 0 05 and PTZ S 0 05 iii For every real number a gt 0 PT7a Z 0PT0 Z a H 53 iv For every real number a we have PTZ a 0i lfabgt0thenPTa Z bPT0 Z b7PT0 Z ai i A random variable X is called normal if there are numbers M and a gt 0 Xiu such that Z is the standard normal random variable Then M is the mean of X and a is the standard deviation of Xi i The standard normal random variable has mean 0 and standard deviation If X is a normal random variable With mean M and standard deviation 0 and Z is the standard normal random variable7 then for every a lt b we have PTangbPTngng a a If X is a Bernoulli random variable7 then PTaXb p wSZSW a a NE 539 533 F1 9 Chapter 7 Linear Programming Modeling and Graphical Solution Linear Programming Models The inequalities that specify permissible values of the variables are the constraints of the problem In this setting the constraints will always be inequalities The set of points satisfying the constraints of the problem is called the feasibleset for the problem The function to be maximized or minimized is known as the objective function for the problem A set of points in the plane is bounded if it is contained in some circle centered at 0 0 Otherwise it is called unbounded A point T is a corner point of a feasible set for a linear programming model if every line segment that is contained in the set and contains T it has it as one of its endpoints Let F be the feasible set for a linear programming problem F f g and let f be the objective function a If F is bounded then f attains its maximum value at a corner point of F and its minimum value at a corner point of F b If F is unbounded and has at least one corner point then exactly one of the following holds i f attains its maximum at a corner point of F ii f takes arbitrarily large positive values on F C The above statement is true if you replace 7maximum7 with 7mini mum Solution Method for Linear Programmind Problems Graph the feasible set for the problem Determine the coordinates of each of the corner points of the feasible set Evaluate the objective function at each corner point Select the point T where you get the largest of these values if the problem is to maximize the objective function or the smallest one if it is to minimize the objective function i If the feasible set is bounded then the value selected is the so lution of the problem iii If the feasible set is unbounded and if the problem has a solution7 then the value selected is the solution To see if the problem has a solution in the unbounded case7 try to nd a larger respectively7 smaller value of the objective function on other points of the feasible set Some good candidates are points on the boundary lines Whose intersection is the point Ti H 539 N533 9 3 HH OH 590 Chapter 3 Probability Measures Probability measure Assigns a number to each event of the sample space called the probability of the event We must have that o 0 S PTE S 1 for every E C S o PTS 1 0 If E and F are disjoint then PTE U F PTE PTF PTE sum of probabilities of outcomes in E PT For any event E we have PTE 17 PTE 0 1f E1 m En are pairwise disjoint events then PTE1 U E2 U U En PTE1 PTE2 PTEn PTE UF PTE PTF 7 PTE PTEUFUG PTEPTFPTG 7PTE F 7PTEQG 7PTF G PTE Fm G If A and B are events in the sample space S of an experiment and PT E f 0 then the conditional probability of event A given B is PTA B T PTAB P B The events A and B are independent if PTA N B PTAPTB If we have an experiment consisting of subexperiments you can nd the probability measure of an outcome by multiplying the conditional prob ability assigned to each of the branches of the path in the tree diagram that leads to the outcome Bernoulli trial an experiment with two possible outcomes Bernoulli process sequence of repetitions of the same Bernoulli trial If you have a Bernoulli process with n subexperiments with success proba bility p and failure probability 4 1 7p then the probability of obtaining exactly T successes is PTr successes CnTqun T Example For a fair coin p q so the probability of obtaining T CnT times heads is 2 In a Bernoulli process with n trials PT0 successes PT1 successes PT n successes 1