```Date: Thu, 18 Jul 1996 00:49:58 -0500 (EST)
Subject: discrete math

Eileen Schoaff
Mathematics Department
Buffalo State College
Buffalo NY   14222
SCHOAFEM@SNYBUFAA.CS.SNYBUF.EDU

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, probabilty, 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.

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?
```

[ Permission pending... ]

[ TOC | Intro. | Resources |Activities | Feedback ]

Back to Main page...