Date: Jul 17, 1996 8:49 PM Author: Eileen Schoaff Subject: Discrete Math The following is a set of projects that I use in my discrete mathematics course. I teach 11th grade students in a gifted math project. The material is not difficult and with graphing calculators, the computations are not hard. This includes simulations, probability, matrices, graphing, and recurrence relations. Both the students and I enjoyed their presentations. They worked in groups of four for 2 hours and then made a 5-10 minute presentation of their results. Some brought props and acted out the story. MARKOV CHAINS (This material comes from a variety of sources, including a presentation by Frank Pitonyak at the NCTM conference in San Diego, Ralston and Maurer's Discrete Algorithmic Mathematics, and Kenneth Bogart's Discrete Mathematics. Hardly anything is original to me. This activity integrates three areas of discrete mathematics -- recurrence relations, matrices, and graph theory.) A stochastic process is one that has a finite number of outcomes (or states) and the outcome (or state) occurs with a specific probability. For example, the following are examples of stochastic processes: % tossing a coin four times, % picking four marbles without replacement from a jar containing six green and four blue marbles, and % having two people toss a ball four times where they have the option of tossing straight up or to the other person. In the first example, the probability of getting a head on the first toss is 0.5. Likewise the probability of a head on each succeeding toss is 0.5 and is independent of any of the tosses before it. In the second example, the probability of getting a green marble on the first draw is 6/10. The probability of a green on the second draw is 5/9 or 6/9, depending on what the first draw was. The probability of a green on the third draw is either 6/8, 5/8, or 4/8 depending on the first two draws. The probability of a green on the fourth draw depends on all the preceding draws. In the third example, the probability that the ball is in the hands of person A or B depends only on the immediately previous trial and the behavior of the ball handler. If the outcome (or state) of a stochastic process depends at most on the immediately preceding trial, then it is called a Markov Chain (named after Andrei Markov, a Russian mathematician.) Of the experiments described above, only the first and third describe Markov Chains. These situations can be represented in various ways -- as a digraph (arrows with associated weights), as a linked recurrence relation (f(n) depends on f(n-1) and g(n-1)), and as a matrix (where entry ij is the probability of going from state i to state j). One way to find probabilities in a Markov Chain after several steps is by using a probability tree. These, however, can become rather unwieldy when you get beyond two or three steps. What we want to do is to create an n by n matrix containing the probabilities: Next State A B C A | | Current State B | | C | | This is called the Transition Matrix. The value in position AA is the probability of going from A to A. Likewise, the value in position AB is the probability of going from A to B, and so on. Each row consists of non-negative values whose sum is equal to one, which qualifies it as a stochastic matrix. A second 1 by n matrix, called the Initial State Matrix, holds the starting position. For example, an initial state matrix might be [0 0 1], which indicates that the starting position is C. The product of the initial state matrix times the transition matrix yields the probability of the second step. Continued multiplications by the transition matrix yield probabilities for subsequent steps. In addition, regular stochastic matrices converge when raised to a sufficiently high power. They reach a steady state or equilibrium. This state can also be calculated algebraically by setting f(n) = f(n-1) = f and g(n) = g(n-1) = g. Solving the system of equations for f and g gives the probabilities for equilibrium. To determine the expected number of times something occurs before equilibrium, eliminate the row(s) and column(s) from T that are the terminating conditions. For example, if when you get to A you stay there, then delete row A and column A from the above matrix. This matrix is Q. I is the corresponding identity matrix. Calculate I-Q, then find the inverse of that matrix. The entry in row i column j is the expected number of times you end up in state j before reaching the absorbing state, given that you started in state i. If you start at C and you want to know how many times you end up at B before you stop, the value will be in row C column B. If you start at C and you want to know how many times you change to anywhere before you stop, sum the entries in row C. 1. Business Inventory Trusty Rent-A-Car has offices in New York City and Los Angeles. It allows customers to make local rentals or one-way rentals to the other location. Each month, it finds that half the cars that start the month in NYC end it in LA, and one third of the cars that start the month in LA end it in NYC. If at the start of operations Trusty has 1000 cars in each city, what can it expect n months later? Let N(n) be the number of cars in New York at the beginning of month n, with the start of operations considered to be the beginning of month 0. Define L(n) similarly. You will have a pair of linked recurrence relations because each variable depends on previous values of the other variable as well as of itself. a. Write the linked recurrence relation for N(n) based on N(n-1) and L(n-1). Similarly write the linked recurrence relation for L(n). In this case, L(0) = N(0) = 1000. Although individual cars will keep moving from NYC to LA and back, the number of cars in each place might stabilize, or the agency gains equilibrium. If equilibrium is attained, then N(n-1) = N(n) = N and L(n-1) = L(n) = L. Determine values for N and L when equilibrium is achieved. b. Create a 2x2 matrix called B as follows: Next Month N L This Month N | | L | | where the rows are N and L and the columns are N and L. (Note b(NN) = fraction of cars starting and ending in NYC.) Create a 1x2 matrix A = [.5 .5] which indicates the original distribution of half the cars in each location. Multiply AB. Multiply the answer times B. Keep multiplying by B. Eventually the matrix product will stabilize. Compare this answer with the answer to (c). b. Suppose the initial distribution is different from 1000 cars in each location. Modify the values in matrix A to indicate a different distribution (remember the two numbers must add up to 1) and repeat the multiplications in (d). Explain your results. c. Forget about matrix A and just take B and raise it to some power, such as 20. What do you see? What does that tell you about the significance of A? For what value of n does B^n stabilize? d. Suppose Los Angeles suffers an earthquake and becomes less popular. Trusty Rent-a-Car now finds that only 1/4 the cars in NYC end up in LA the next month, whereas 4/5 the cars rented in LA and end up in NYC. Revise the linked recurrence relations in (a) and solve for the new values. 2. Distributing Populations Developing countries have a problem with too many people moving to the cities. Country X does a study and finds that, in a given year, 10% of the rural population moves to a city, but only 1% of the urban population goes back to the country. Let U(n) be the number of people in an urban setting at the beginning of year n, with the start of the study considered to be the beginning of year 0. Define R(n) similarly. You will have a pair of linked recurrence relations because each variable depends on previous values of the other variable as well as of itself. a. Write the linked recurrence relation for U(n) based on U(n-1) and R(n-1). Similarly write the linked recurrence relation for R(n). Assume that initially, U(0) = R(0) = 50%. Although individuals will keep moving from urban to rural settings and back, the number of people in each place might stabilize and the country gain equilibrium. If equilibrium is attained, then U(n-1) = U(n) = U and R(n-1) = R(n) = R. Determine values for U and R when equilibrium is achieved. b. Create a 2x2 matrix B as follows: Next Year U R This Year U | | R | | where the rows are U and R and the columns are U and R. (Note b(UU) = fraction of population starting and ending in urban setting.) Create a 1x2 matrix A = [.5 .5] which indicates the original distribution of half the population in each location. Multiply AB. Multiply the answer times B. Keep multiplying by B. Eventually the matrix product will stabilize. Compare this answer with the answer to (c). c. Suppose the initial distribution is different from 50% people in each location. Modify the values in matrix A to indicate a different distribution (remember the two numbers must add up to 1) and repeat the multiplications in (d). Explain your results. d. Suppose an epidemic breaks out and the risk of contagion is significantly higher in the cities. Surveys now find that only 5% of the rural population moves to a city, but 15% of the urban population moves to the country. Revise the linked recurrence relations in (a) and solve for the new values. 3. Tylenol's Comeback Several years ago the makers of Tylenol were devastated when someone, tampering with Tylenol bottles, create a nationwide scare. Sales of Tylenol, the number-one seller among acetaminophens, declined to almost zero. The company removed all supplies of Tylenol from the shelves nationwide and designed new tamper proof packaging. When the scare was over, Tylenol soon became the number-one seller again. How could this occur? Most analysts believe it was a result of the intense loyalty of Tylenol users. Assume that for any purchase 70% of Tylenol users are loyal and will not switch. Similarly, assume that 40% of those using Brand X will not switch. Further, assume that when Tylenol returned to the market with new packaging their market share was effectively 0%. a. Write the linked recurrence relation for the percent of people purchasing Tylenol after n months T(n) based on T(n-1) and X(n-1). Similarly write the linked recurrence relation for X(n). Assume that initially, T(0) = 0% and X(0) = 100%. Although individuals will keep changing to Tylenol or Brand X, the number of people purchasing each product might stabilize and the market gain equilibrium. If equilibrium is attained, then T(n-1) = T(n) = T and X(n-1) = X(n) = X. Solve algebraically. b. Create a 2x2 matrix B as follows: Next Purchase T X Current Purchase T | | X | | where the rows are T and X and the columns are T and X. (Note b(TT) = fraction of purchasers starting and ending with Tylenol.) Create a 1x2 matrix A = [0 1] which indicates the original distribution of market share. Multiply AB. Multiply the answer times B. Keep multiplying by B. Eventually the matrix product will stabilize. What does this show? c. Suppose the initial market share is different from 0% for Tylenol. (Perhaps some true believers hoarded their Tylenol supply.) Modify the values in matrix A to indicate a different distribution (remember the two numbers must add up to 1) and repeat the multiplications in (c). Explain your results. d. Suppose a second scare occurs and several people suddenly die after taking Tylenol. Surveys now find that only 60% of the Tylenol users will not switch, but 55% of the Brand X users will not switch. Revise the linked recurrence relations in (a) and solve for the new values. 4. Predicting the Weather Suppose a weather forecaster has collected data to predict whether tomorrow will be sunny (S), cloudy (C), or rainy (R), given todayUs weather conditions. % If today is sunny, then tomorrow the probabilities are 70% for S, 20% for C, and 10% for R. % If today is cloudy, then the probabilities for tomorrow are 30% for S, 60% for C, and 10% for R. % If today is cloudy, then the probabilities for tomorrow are 25% for S, 20% for C, and 55% for R. a. Create a 3x3 matrix where the rows indicate the current situation and the columns indicate tomorrow's weather. S C R S | | B = C | | R | | For example the first row would be 0.7 0.2 0.1. Now create a 1x3 matrix A to indicate today's weather. Suppose today is sunny, then A = [1 0 0]. b. Multiply AB to determine the probabilities for tomorrowUs weather. Multiply by B again to determine the weather for 2 days from now. Repeat this so that you have a set of probabilities for the next 5 days. c. Keep multiplying by B. Eventually the matrix product will stabilize. What does this show? d. Change today's weather to indicate a rainy day in matrix A. Repeat the multiplication in (b) to formulate a 5-day forecast. e. Forget about matrix A and just take B and raise it to some power, such as 20. What do you see? What does that tell you about the significance of A? For what value of n does B^n stabilize? Once it stabilizes it no longer forecasts the weather, but rather tells you about the climate. f. Create a matrix that would be appropriate for Buffalo, NY. You may want to include snow as well as rain. Decide on today's weather and illustrate a 5-day forecast. 5. Genetics A given plant species has red, pink, or white flowers according to the genotypes RR, RW, and WW respectively. If each genotype is crossed with a pink flowering plant (genotype RW), the transition matrix is as follows: Next generation Red Pink White Red 0.5 0.5 0 This generation Pink 0.25 0.5 0.25 White 0 0.5 0.5 (These numbers are determined as follows: RR x RW yields RR, RW, RR, and RW. RW x RW yields RR, RW, WR, WW. WW x RW yields WR, WW, WR, and WW.) Assume the plants of each generation are crossed only with pink plants to produce the next generation. a. This matrix is B. Now create a 1x3 matrix A to indicate the initial distribution of genotypes. Assume the initial distribution is 70% Red, 10% Pink, and 20% White. b. Multiply AB to determine the distribution for the next generation. Multiply the answer times B. Keep multiplying by B. Eventually the matrix product will stabilize. What does this show? What will be the eventual distribution of genotypes after many generations? c. Suppose the initial distribution is different. Modify the values in matrix A to indicate a different distribution (remember the three numbers must add up to 1) and repeat the multiplications in (b). Explain your results. d. Suppose we decide to cross plants of each generation with only white plants. Create a transition matrix for this situation. (To figure the probabilities, recall that RR x WW yields RW all the time. Calculate the other probabilities.) Use the same initial distribution of genotypes and determine the eventual distribution after many generations. 6. Ball Toss Experiment Two people are tossing a ball to each other. A person may toss the ball up and catch it themselves or throw it to the other person. The probability the ball is in the hands of person A or B depends only on the immediately previous trial. a. Have two people toss the ball 50 times so you can get some empirical probabilities. Choose one person to be A and one to be B. A third person should tally where the ball is, while a fourth person calls out what is happening. The tally sheet is as follows: A to A _____ A to B _____ B to B _____ B to A _____ (Hint: it is very boring if each person does each type of toss half the time.) Total each category. Total the first 2 and the second 2. Now P(AA) = (total A to A)/(total of first 2 categories) . Similarly calculate P(AB), P(BB), and P(BA). b. Construct a probability tree showing the first 3 tosses. Assume you start by giving the ball to A. What is the probability of the ball being in A's hand after 3 tosses? Construct a second tree with the ball starting with B. Similarly find the probability of the ball being in A's hand after 3 tosses. c. Construct a weighted digraph of the situation. On each arrow, write the probabilities. d. Express the probabilities as a transition matrix T. In location AA put the probability A tosses the ball to herself. In AB put the probability A tosses the ball to B. Next Toss A B Now A | | B | | Next suppose the ball is in the hands of A at first. This can be represented by the Initial State Matrix as S = [1 0]. Multiply ST to determine the probability for the location of the ball after the first toss. Multiply the answer times T two more times. This should match the results from the probability tree after 3 tosses. e. Keep multiplying by T. Eventually the matrix product will stabilize. What does this show? What will be the eventual location of the ball after many tosses? f. Suppose the initial situation is different. Modify the values in matrix S to indicate the ball starting with B and repeat the multiplications in (d). Explain your results. g. Forget about matrix S and just take T and raise it to some power, such as 20. What do you see? What does that tell you about the significance of S? For what value of n does T^n stabilize? 7. Barbecue Begging A puppy smells a number of neighbors barbecuing. One unsupervised grill is two houses downhill from his yard, and another unsupervised grill is three houses uphill from his yard. Because so many people are barbecuing, he goes randomly from house to house in search of food, going downhill with twice the probability that he goes uphill. We record his progress from house to house, using 0 to stand for one unsupervised grill, 2 to stand for his yard, and 5 to stand for the other unsupervised grill. a. Construct a weighted digraph of the situation. On each arrow, write the probabilities that the puppy will follow that path. Assuming that the puppy will stop and eat if and when he finds unsupervised food, you would put a loop at 5 with probability 1 and a loop at 0 with probability 1. b. Write a matrix T of transition probabilities of going from one house to another. The first row would be 1 0 0 0 0 0 to indicate that if the puppy gets to house 0 he will stay there. In position 1, 0 put the probability the puppy will go from house 1 to house 0. Next House 0 1 2 3 4 5 0 | | 1 | | Now 2 | | 3 | | 4 | | 5 | | Next create the Initial State Matrix as S = [0 0 1 0 0 0] indicating the puppy started at house 2. Multiply ST to determine the probability for the location of the puppy after the first move. c. Find the probability of the puppy going from his yard to the grill down the hill in two, three, or four moves. To make reading the results easier, you may want to set the mode to 2 digits. d. Keep multiplying by T. Eventually the matrix product will stabilize. What does this show? What will be the eventual location of the puppy after many moves? e. What is the expected number of houses the dog will visit before finding food? 8. Gambling Game In a gambling game (such as coin flipping for a dollar a flip), your total fortune can go up one dollar or down one dollar (each with probability 1/2) at each stage. Suppose you begin with 3 dollars and your opponent begins with 2. a. Construct a weighted digraph of the situation. The states are your total fortune, either 0, 1, 2, 3, 4, or 5 dollars. The probability of going from state k to state k + 1 or k - 1 is 1/2 unless k = 0 or k = 5. On each arrow, write the probabilities that you will gain a dollar or lose a dollar. Since the game is over if you reach either 0 or 5, you would put a loop at 5 with probability 1 and a loop at 0 with probability 1. b. Write a matrix T of transition probabilities of going from one amount of money to another. The first row would be 1 0 0 0 0 0 to indicate that if you get to $0 the game will be over. In position 1, 0 put the probability you will go from $1 to $0. Next Amount 0 1 2 3 4 5 0 | | 1 | | Current 2 | | 3 | | 4 | | 5 | | Next create the Initial State Matrix as S = [0 0 0 1 0 0] indicating you started with $3. Multiply ST to determine the probability for the amount of money you have after the first flip. c. Determine the probability that you win your opponent's entire fortune by the time four coins have been flipped. d. Keep multiplying by T. Eventually the matrix product will stabilize. What does this show? What will be the eventual outcome of the game after many flips? e. How many coin flips should we expect before someone wins the game? 9. Mouse Maze We place a mouse in the maze consisting of a square cut into quarters. The upper left quarter is chamber 1, lower left is 2, lower right is 3, upper right is 4. There is 1 passageway between chamber 1 and chamber 4, 2 passageways between chamber 1 and chamber 2, 2 passageways between chamber 2 and chamber 3, and 1 passageway between chamber 3 and chamber 4. The maze has food in chamber 4. The maze is designed so that the odor of the food pervades all the chambers. The hypothesis to be tested is that after some practice the mouse will move directly to and remain in chamber 4. At the opposite extreme is the possibility that no matter how many times the mouse is placed in the maze, it moves randomly through the maze until it encounters the food. If the mouse chooses an opening at random and moves through it, then we expect that the mouse will be equally likely to pick any opening in the chamber it is in. Thus, for example, we expect the probability of moving from chamber 1 to chamber 4 to be 1/3 because there are three passageways from chamber 1 and one of these leads to chamber 4. We expect the probability of moving from chamber 1 to chamber 3 to be 0, because there is no passageway between chambers 1 and 3. a. From this diagram, draw a weighted digraph. You draw an edge of weight 1 from vertex 4 to itself to signify that (because of the food) the mouse stays in chamber 4 if it gets there. (We observe the mouse when it changes chambers or is eating.) b. From this digraph, write a matrix T of transition probabilities of going from one chamber to another. The entry in row 1 column 4 would be the probability the mouse goes from chamber 1 to chamber 4, which is 1/3. Next Chamber 1 2 3 4 1 | | Current 2 | | 3 | | 4 | | c. Use this matrix to determine the probability that the mouse moves from chamber 2 to chamber 4 in one or two movements. To do this, you need to create the Initial State Matrix as S = [0 1 0 0] indicating you started the mouse in chamber 2. Multiply ST to determine the probability for the mouse's location after the first observation. Keep multiplying by T to get subsequent observations. d. What is the probability that after placing the mouse in chamber 2 and making two, four, or eight observations, we find the mouse in chamber 2 again? e. What is the expected number of times the mouse in the maze will change chambers before finding food, given that we start the mouse in chamber 2? 10. Amusement Park An amusement park has five adult attractions -- Roller coaster, Flume, Wheel, Smasher, and Crunch. Two of these, the exciting Roller coaster and Flume, are usually the last attractions visited before people leave the park. There is a path between the Roller coaster and Flume, Roller coaster and Wheel, Roller coaster and Smasher, Flume and Wheel, Flume and Crunch, Smasher and Wheel, Wheel and Crunch. a. Assuming that people are equally likely to take any path leaving an attraction and that 25% of the people who ride the Roller coaster or the Flume then leave the park, draw the weighted graph that shows the five attractions and the exit and shows the probability that someone at one vertex goes to any other vertex. Assume that someone who has exited the park does not return. b. From this digraph, write a matrix T of transition probabilities for going from one attraction to another. E stands for exit, R for roller coaster, etc. The entries in row E would be 1 0 0 0 0 0 to indicate that someone who exited the park did not return. Next Attraction E R F C W S E | | R | | Current F | | C | | W | | S | | c. Use this matrix to determine the probability that a person who rides the roller coaster rides it once again after four changes of rides. To do this, you need to create the Initial State Matrix as S = [0 1 0 0 0 0] indicating you started on the roller coaster. Multiply ST to determine the probability for the next ride. Keep multiplying by T to get subsequent observations. d. What is the probability that someone who is now riding the roller coaster rides the wheel after changing rides four times? e. Find the expected number of times that someone who is now riding the roller coaster rides the wheel before leaving the park. f. Find the expected number of rides that a person who is now riding the roller coaster rides on any ride whatsoever before leaving the park. 11. Temperature Control A computer is monitoring the temperature changes in a controlled process whose temperature must remain in the range between 20{ C and 26{ C. If the temperature reaches 20{ C or 26{ C, the computer stops the process. The temperature-measuring device measures only integer temperatures. The heating system has the property that, during any minute, the temperature is equally likely to go up one degree, down one degree, or stay the same. a. Draw a digraph of this situation. The states would be the range of temperatures from 20 to 26. Any number between 21 and 25, inclusive, has two arrows and a loop. The end temperatures would have only a loop with weight 1, indicating that the process stops. b. From this digraph, write a matrix T of transition probabilities for going from one temperature to another. The entries in row 20 would be 1 0 0 0 0 0 0 to indicate that the process stopped. Next Temperature 20 21 22 23 24 25 26 20 | | 21 | | Current 22 | | 23 | | 24 | | 25 | | 26 | | c. Use this matrix to determine the probability that the process stops at 26{ C within four minutes, given that the room is at 24{ C initially. To do this, you need to create the Initial State Matrix as S = [0 0 0 0 1 0 0] indicating you started at 24{ C. Multiply ST to determine the probability for the temperature for the next minute. Keep multiplying by T to get subsequent observations. d. How many minutes should we expect the computer to allow the process to continue, given an initial temperature of 24{ C. e. Suppose we change the initial room temperature to 22{ C. Redo the calculations in (c) and (d). Are the results the same? Why or why not? f. Keep multiplying by T. Eventually the matrix product will stabilize. What does this show? What will be the eventual outcome of the process after many minutes?