(***********************************************************************
Mathematica-Compatible Notebook
This notebook can be used on any computer system with Mathematica 3.0,
MathReader 3.0, or any compatible application. The data for the notebook
starts with the line of stars above.
To get the notebook into a Mathematica-compatible application, do one of
the following:
* Save the data starting with the line of stars above into a file
with a name ending in .nb, then open the file inside the application;
* Copy the data starting with the line of stars above to the
clipboard, then use the Paste menu command inside the application.
Data for notebooks contains only printable 7-bit ASCII and can be
sent directly in email or through ftp in text mode. Newlines can be
CR, LF or CRLF (Unix, Macintosh or MS-DOS style).
NOTE: If you modify the data for this notebook not in a Mathematica-
compatible application, you must delete the line below containing the
word CacheID, otherwise Mathematica-compatible applications may try to
use invalid cache data.
For more information on notebooks and Mathematica-compatible
applications, contact Wolfram Research:
web: http://www.wolfram.com
email: info@wolfram.com
phone: +1-217-398-0700 (U.S.)
Notebook reader applications are available free of charge from
Wolfram Research.
***********************************************************************)
(*CacheID: 232*)
(*NotebookFileLineBreakTest
NotebookFileLineBreakTest*)
(*NotebookOptionsPosition[ 25511, 764]*)
(*NotebookOutlinePosition[ 26351, 791]*)
(* CellTagsIndexPosition[ 26307, 787]*)
(*WindowFrame->Normal*)
Notebook[{
Cell[CellGroupData[{
Cell["Markov Chains", "Title",
FontFamily->"Times"],
Cell["by Teresa Anderson", "Subtitle",
FontFamily->"Times"],
Cell["\<\
Final Project
Using Mathematica in the Mathematics Classroom
June, 1998\
\>", "Subsubtitle"],
Cell["\<\
This unit is designed for use in any Algebra class where students \
are familiar with matrices, matrix multiplication, and properties of \
matrices. \
\>", "Text",
FontFamily->"Geneva",
FontSize->10],
Cell[CellGroupData[{
Cell[TextData[StyleBox["Initialization",
FontFamily->"Times",
FontSize->14,
FontSlant->"Italic"]], "Subsection",
FontSize->10,
FontWeight->"Plain"],
Cell["Before proceeding, activate the following code:", "Text"],
Cell[BoxData[
\(<< "\"\)], "Input"],
Cell[BoxData[
\(<< "\"\)], "Input"],
Cell[BoxData[
\($TextStyle = {FontFamily \[Rule] "\", FontSize \[Rule] 12}\)],
"Input"],
Cell[BoxData[
\(\(PD\ = \
Graphics[{RGBColor[1, 0, 0], Text["\", {0, 0}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PDE\ = \ \
Graphics[{RGBColor[1, 0, 0], Text["\<.3\>", {1.3, 1}, {\(-1\), 0}]\n
\t}, AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PDW\ = \ \
Graphics[{RGBColor[1, 0, 0], Text["\<.2\>", {\(-1.3\), 1}, {1, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PDD\ = \ \
Graphics[{RGBColor[1, 0, 0],
Text["\<.5\>", {0, \(-0.8\)}, {0, \(-1\)}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(DD\ = \
Graphics[{RGBColor[1, 0, 0],
Circle[{0, \(-0.25\)}, 0.25, {3 \[Pi]/4, 9 \[Pi]/4}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(DE\ = \
Graphics[{RGBColor[1, 0, 0], Arrow[{0.1, \(-0.1\)}, {2.1, 1.85}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(DW\ = \
Graphics[{RGBColor[1, 0, 0],
Arrow[{\(-0.1\), \(-0.1\)}, {\(-2.1\), 1.85}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PE\ = \ \
Graphics[{RGBColor[0, 0, 1], Text["\", {2, 2.1}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PW\ = \
Graphics[{RGBColor[1, 0, 1], Text["\", {\(-2\), 2.1}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(Downtown\ = {PD, PDE, PDW, PDD, DD, DE, DW, PE, PW}; \)\)], "Input"],
Cell[BoxData[
\(\(PED\ = \ \
Graphics[{RGBColor[0, 0, 1], Text["\<.6\>", { .8, 1}, {0, 0}]\n\t},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PEW\ = \ \
Graphics[{RGBColor[0, 0, 1], Text["\<.2\>", {0, 2.15}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PEE\ = \ \
Graphics[{RGBColor[0, 0, 1], Text["\<.2\>", {2.5, 2.1}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(EE\ = \
Graphics[{RGBColor[0, 0, 1],
Circle[{2.1, 2.1}, 0.25, {5 \[Pi]/4, 11 \[Pi]/4}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(ED\ = \
Graphics[{RGBColor[0, 0, 1], Arrow[{1.9, 1.9}, {0.1, 0.1}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(EW\ = \
Graphics[{RGBColor[0, 0, 1], Arrow[{1.8, 2}, {\(-1.8\), 2}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(Eastside\ = {PD, PED, PEW, PEE, ED, EE, EW, PE, PW}; \)\)], "Input"],
Cell[BoxData[
\(\(PWD\ = \ \
Graphics[{RGBColor[1, 0, 1], Text["\<.3\>", {\(- .8\), 1}, {0, 0}]\n
\t}, AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PWW\ = \ \
Graphics[{RGBColor[1, 0, 1], Text["\<.3\>", {\(-2.5\), 2.1}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(PWE\ = \ \
Graphics[{RGBColor[1, 0, 1], Text["\<.4\>", {0, 1.75}, {0, 0}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(WW\ = \
Graphics[{RGBColor[1, 0, 1],
Circle[{\(-2.1\), 2.1}, 0.25, {\[Pi]/4, 7 \[Pi]/4}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(WD\ = \
Graphics[{RGBColor[1, 0, 1], Arrow[{\(-1.9\), 1.9}, {\(-0.1\), 0.1}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(WE\ = \
Graphics[{RGBColor[1, 0, 1], Arrow[{\(-1.9\), 1.9}, {1.9, 1.9}]},
AspectRatio \[Rule] Automatic]; \)\)], "Input"],
Cell[BoxData[
\(\(Westside\ = {PD, PWD, PWW, PWE, WD, WE, WW, PE, PW}; \)\)], "Input"],
Cell[BoxData[
\(\(T\ = \ {{ .5, .3, .2}, { .6, .2, .2}, { .3, .4, .3}}; \)\)],
"Input"],
Cell[BoxData[
\(\(Taxis\ = \ {{100, 100, 100}}; \)\)], "Input"],
Cell[BoxData[
\(\(WA =
ListPlot[{{1, 3}, {0, 3}, {0, 7}, {3, 7}, {3, 6}},
PlotStyle \[Rule] {PointSize[0.01]}, PlotJoined \[Rule] True,
Axes \[Rule] False, DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WB =
ListPlot[{{2, 3}, {3, 3}, {3, 5}}, PlotStyle \[Rule] {PointSize[0.01]},
PlotJoined \[Rule] True, Axes \[Rule] False,
DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WC =
ListPlot[{{3, 4}, {4, 4}}, PlotStyle \[Rule] {PointSize[0.01]},
PlotJoined \[Rule] True, Axes \[Rule] False,
DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WF =
ListPlot[{{3, 7}, {6, 7}, {6, 4}, {5, 4}},
PlotStyle \[Rule] {PointSize[0.01]}, PlotJoined \[Rule] True,
Axes \[Rule] False, DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WG =
ListPlot[{{6, 7}, {9, 7}, {9, 3}, {8, 3}},
PlotStyle \[Rule] {PointSize[0.01]}, PlotJoined \[Rule] True,
Axes \[Rule] False, DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WH =
ListPlot[{{7, 3}, {6, 3}}, PlotStyle \[Rule] {PointSize[0.01]},
PlotJoined \[Rule] True, Axes \[Rule] False,
DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WI =
ListPlot[{{6, 4}, {6, 2}}, PlotStyle \[Rule] {PointSize[0.01]},
PlotJoined \[Rule] True, Axes \[Rule] False,
DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WJ =
ListPlot[{{6, 1}, {6, 0}}, PlotStyle \[Rule] {PointSize[0.01]},
PlotJoined \[Rule] True, Axes \[Rule] False,
DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(WK =
ListPlot[{{9, 3}, {9, 0}, {0, 0}, {0, 3}},
PlotStyle \[Rule] {PointSize[0.01]}, PlotJoined \[Rule] True,
Axes \[Rule] False, DisplayFunction \[Rule] Identity]; \)\)], "Input"],
Cell[BoxData[
\(\(RA = \ Graphics[Text["\<1\>", {1.5, 5}]]; \)\)], "Input"],
Cell[BoxData[
\(\(RB = \ Graphics[Text["\<2\>", {4.5, 5.5}]]; \)\)], "Input"],
Cell[BoxData[
\(\(RC = \ Graphics[Text["\<3\>", {7.5, 5}]]; \)\)], "Input"],
Cell[BoxData[
\(\(RD = \ Graphics[Text["\<4\>", {7.5, 1.5}]]; \)\)], "Input"],
Cell[BoxData[
\(\(RE = \ Graphics[Text["\<5\>", {3.5, 1.5}]]; \)\)], "Input"],
Cell[BoxData[
\(\(Maze = {WA, WB, WC, WF, WG, WH, WI, WJ, WK}; \)\)], "Input"],
Cell[BoxData[
\(\(Titles = {RA, RB, RC, RD, RE}; \)\)], "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell["Introduction", "Subsection"],
Cell["\<\
Markov chains use probability theory and matrix multiplication to \
model a variety of situations. Let's examine the following situation to see \
how Markov chains work.\
\>", "Text",
FontFamily->"Geneva",
FontSize->12,
FontWeight->"Plain"],
Cell["\<\
A taxi company with 300 cabs serves a city from three dispatch \
centers: Downtown, Eastside, and Westside. The taxi drivers' average pickup \
interval is 20 minutes (the time between picking up one fare and the next) \
and the demand for taxis is the same at all times of day and from day to day. \
Based on records from previous years, the head dispatcher has found that, on \
average, 50% of the fares picked up in the Downtown region go to another \
Downtown location, 30% go to an Eastside address, and the remaining 20% go to \
the Westside. Enter the command which follows for a diagram of this \
information.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(Show[Downtown]; \)\)], "Input"],
Cell["\<\
Eastside fares follow a different pattern: 20% stay on the \
Eastside, 60% go Downtown, and 20% go to the Westside. For a diagram, enter \
the command below.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(Show[Eastside]; \)\)], "Input"],
Cell["\<\
30% of Westside fares stay on the Westside, 40% go to the Eastside, \
and 30% go Downtown as shown in the diagram produced by entering the command \
below.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(Show[Westside]; \)\)], "Input"],
Cell["\<\
By combining the data from all three areas, the dispatcher produces \
diagram of taxi movement through the city; enter the following command to see \
it. \
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(Show[{Downtown, Eastside, Westside}]; \)\)], "Input"],
Cell["\<\
The data can also be displayed in the table. Entering the \
following command will produce the table.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(TableForm[T,
TableHeadings -> {{"\", "\", "\"}, {
"\", "\", "\"}},
TableAlignments -> Center]\)], "Input"],
Cell["\<\
The table can condensed into the matrix T, which will be shown \
below after entering the command. \
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[T]\)], "Input"],
Cell[TextData[{
"Matrix T is called a transition matrix because each entry represents the \
probability of transition from one region to another. For example, ",
Cell[BoxData[
FormBox[
SubscriptBox[
StyleBox["T",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False}], "21"], TraditionalForm]]],
" is the probability of moving from region 2 to region 1; in the context of \
our taxi model, this is the probability that a taxi picking up a fare on the \
Eastside will drop off that fare Downtown. Notice that T does not include \
the identification of the regions; when working with transition matrices it \
is useful have a labeled table (like the one above) at hand for reference."
}], "Text",
FontFamily->"Geneva"],
Cell["\<\
Our taxi model describes a system with a finite number of states - \
the three regions of the city - and probabilities for transitions from each \
state to every other state. These probabilities are constant and independent \
of previous behavior. A transition - picking up a new fare - occurs each \
time the system is observed, and observations occur at regular intervals, \
every 20 minutes in this model. Systems with these characteristics are \
called Markov chains or Markov processes.\
\>", "Text",
FontFamily->"Geneva"],
Cell["\<\
Our transition matrix demonstrates some properties which are common \
to all transition matrices for Markov processes: \
\>", "Text",
FontFamily->"Geneva"],
Cell["\<\
\t1. A transition matrix must be square. (The number of rows and \
number of columns are both the number of states in the system.) \
\>", "Text",\
FontFamily->"Geneva"],
Cell["\<\
\t2. All the entries are between 0 and 1 inclusive. (The entries \
are probabilities which must lie in that interval.)\
\>", "Text",
FontFamily->"Geneva"],
Cell["\<\
\t3. The sum of the entries in any row must be 1. (Each row \
represents probabilities of moving from a particular state to any of the \
states in the system. Since the system is closed and the movement must take \
place, the sum of the probabilities must be 1.)\
\>", "Text",
FontFamily->"Geneva"],
Cell["\<\
\t4. The entries in the matrix are constant. (The Markov chain \
model depends upon the assumption that the transition matrix does not change \
throughout the process.)\
\>", "Text",
FontFamily->"Geneva"]
}, Closed]],
Cell[CellGroupData[{
Cell["Multiple Transitions", "Subsection"],
Cell[CellGroupData[{
Cell["\<\
When the morning drivers go off duty at 2:00 PM, 300 afternoon \
drivers are waiting at the three regional dispatch centers to pick up a cab. \
Because each taxi has picked up 24 fares during the eight hour morning shift, \
there may no longer be 100 taxis in each region; therefore the dispatcher \
must determine how the cabs are distributed at the shift change to optimize \
the assignment of afternoon shift drivers between the three dispatch centers. \
\
\>", "Subsubsection",
FontFamily->"Geneva",
FontWeight->"Plain"],
Cell["\<\
The information presented in the transition matrix, T, allows the \
dispatcher to approximate the distribution of taxis throughout the city. \
Assume the company starts each morning at 6:00 AM with 100 cabs in each of \
the three regions of the city. This can be represented by the matrix Taxis \
which will be shown below after entering the command.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis]\)], "Input"],
Cell["\<\
From the dispatcher's records, it is known that on average 50% of \
the 100 fares which begin Downtown will remain there, 60% of the 100 Eastside \
taxis will pickup fares going Downtown, and 30% of the 100 Westside fares are \
going Downtown. The number of taxis Downtown after the first twenty minutes \
(or after one fare) can be projected by the computation below; click on the \
computation and Enter to complete the calculation.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\( .5*100 + .6*100 + .3*100\)], "Input"],
Cell["\<\
This computation is the result of multiplying the first (and only) \
row in the matrix Taxis by the first column in the transition matrix (which \
contains the probabilities of a fare going Downtown from each of the three \
regions). The estimated number of taxis on the Eastside after one fare can \
be computed in a similar manner using the second column of the transition \
matrix. Thus, the approximate distribution of cabs across the city after \
twenty minutes is the product of the matrix Taxis and the transition matrix. \
The command below will show the results of that computation.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis . T]\)], "Input"],
Cell["\<\
The exact distribution of taxis will vary from day to day; this \
matrix product shows the long term average distribution to be 140 taxis \
downtown, 90 on the Eastside, and 70 on the Westside at 6:20 AM, after one \
fare.
Multiplying the 6:20 AM distribution matrix by the transition matrix, T, will \
give the approximate distribution of taxis after 40 minutes. Enter the \
computation below to see the results.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[{{140, 90, 70}} . T]\)], "Input"],
Cell["\<\
At 6:40 AM, after two fares, there are an estimated 145 taxis \
Downtown, 88 on the Eastside, and 67 cabs on the Westside. Continuing this \
multiplication process through all 24 morning fares will produce the \
projected distribution of cabs at 2:00 PM. If we examine this process more \
closely, a less cumbersome method of computation appears. \
\>", "Text",
FontFamily->"Geneva"],
Cell[TextData[{
"Using only 6 fares to streamline the notation, the necessary matrix \
multiplication is:\n\n {{{{{{Taxis . T} . T} . T} . T} . T} . T}\n \
\nApplication of the associative law of matrix multiplication allows \
this to be rewritten as: \n\n\t{Taxis . {T . {T . {T . {T . {T . \
T}}}}}} = {Taxis . ",
Cell[BoxData[
FormBox[
SuperscriptBox[
StyleBox["T",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False}], "6"], TraditionalForm]]],
"}"
}], "Text",
FontFamily->"Geneva"],
Cell[TextData[{
"Extending this concept to all 24 fares throughout the morning, the \
projected distribution of taxis throughout the city can be found by computing \
{Taxis . ",
Cell[BoxData[
FormBox[
SuperscriptBox[
StyleBox["T",
FontWeight->"Plain",
FontSlant->"Plain",
FontTracking->"Plain",
FontVariations->{"Underline"->False,
"Outline"->False,
"Shadow"->False}], "24"], TraditionalForm]]],
"} which will be found by entering the command below."
}], "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis . MatrixPower[T, 24]]\)], "Input"],
Cell["\<\
Although the dispatcher knows that there will not be exactly \
145.455 taxis near the Downtown center, the resulting distribution matrix \
does provide a basis upon which to make driver assignments. One scheme the \
dispatcher might use is to pre-assign 145 drivers Downtown, 87 to the \
Eastside, 66 to the Westside, and leave 3 drivers as unassigned \"floaters\" \
who would not be given an assignment until the actual distribution of taxis \
at 2:00 PM is known. \
\>", "Text",
FontFamily->"Geneva"]
}, Closed]],
Cell[CellGroupData[{
Cell["\<\
Once the morning shift is over, the taxi company is responsible for \
delivering the drivers to the dispatch center where they began the shift. To \
arrange adequate transportation for the drivers, the dispatcher needs to know \
where the drivers at each center began the shift. Looking only at the \
transition matrix portion of the computation used to determine cab \
distribution at 2:00 PM as written below, can provide the necessary \
information. Enter the command to see the results.\
\>", "Subsubsection",
FontFamily->"Geneva",
FontWeight->"Plain"],
Cell[BoxData[
\(MatrixForm[MatrixPower[T, 24]]\)], "Input"],
Cell["\<\
Approximately 48% of the drivers who started the shift in any \
region will end up Downtown, 29% will end the shift on the Eastside, and 22% \
will be on the Westside at 2:00 PM. Therefore, the dispatcher can estimate \
that transportation will be needed Downtown to take approximately 48 drivers \
(48% of 100) to the Eastside and 48 to the Westside, approximately 29 drivers \
will need to go from the Eastside to Downtown and 29 to the Westside, and the \
Westside dispatch center will deliver approximately 22 drivers Downtown and \
22 to the Eastside.\
\>", "Text",
FontFamily->"Geneva"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell["Long Term Behavior", "Subsection"],
Cell["\<\
In computing the distribution of taxis at various times during the \
morning shift, we saw a significant change of distribution from the 100 taxis \
per region at 6:00 AM to that after one fare. Enter the command below to \
review those results. \
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis . T]\)], "Input"],
Cell["\<\
The next command shows what happens between 6:20 AM and 6:40 AM; \
notice the distribution doesn't change as dramatically as in the first twenty \
minutes.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis . MatrixPower[T, 2]]\)], "Input"],
Cell["\<\
The command below shows the difference in distribution between 6:40 \
AM and 2:00 PM to be very small.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[Taxis . MatrixPower[T, 24]]\)], "Input"],
Cell["\<\
Let's examine what happens to taxi distribution across the city \
between 6:00 AM and 2:00 PM in more detail. The command below will compute \
the approximate distribution of taxis every twenty minutes from 6 AM to 2 PM \
(0600 to 1400 hours in military time).\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(For[i = 0, i < 25,
Print[600 + 100*IntegerPart[i/3] + 60*FractionalPart[i/3],
MatrixForm[Taxis . MatrixPower[T, i]]]; \(i++\)]\n\)\)], "Input"],
Cell["\<\
As you can see, after 8:00 AM the distribution of taxis becomes \
constant and doesn't change with subsequent transitions. When this happens \
in a system represented by a Markov process, the system is said to stabilize \
and the resulting distribution matrix (or vector, since it has only one row) \
is called the stable state vector of the Markov process.\
\>", "Text",
FontFamily->"Geneva"]
}, Closed]],
Cell[CellGroupData[{
Cell["Exercises", "Subsection"],
Cell["\<\
A rat is placed in the maze shown below. During a fixed time \
interval, the rat randomly chooses one of the doors available to it \
(depending upon which room it is in) and moves through that door to the next \
room - it always moves to a new room and never stays where it is. Each \
movement of the rat is taken as a transition in a Markov process in which a \
state is identified with the room the rat is in.\
\>", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(\(Show[Maze, Titles, DisplayFunction \[Rule] $DisplayFunction]; \)\)],
"Input"],
Cell["The first row of the transition matrix is", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(TableForm[{{0, 1/2, 0, 0, 1/2}}, TableHeadings -> Automatic,
TableAlignments -> Center]\)], "Input"],
Cell["1.\tConstruct the entire transition matrix for this process.", "Text",
FontFamily->"Geneva"],
Cell["\<\
2.\tIf the rat starts in room 1, what is the probability that it is \
in room 3 after two transitions? After three transitions?\
\>", "Text",
FontFamily->"Geneva"],
Cell["3.\tDetermine the stable state vector.", "Text",
FontFamily->"Geneva"],
Cell["\<\
4.\tAfter a large number of transitions, what is the probability \
that the rat is in room 4?\
\>", "Text",
FontFamily->"Geneva"],
Cell["\<\
5.\tIn the long run, what percentage of the time will the rat spend \
in rooms 2 or 3?\
\>", "Text",
FontFamily->"Geneva"],
Cell[CellGroupData[{
Cell["Answers", "Subsubsection"],
Cell["1.\tThe transition matrix is:", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[{{0, 1/2, 0, 0, 1/2}, {1/2, 0, 0, 0, 1/2}, {0, 0, 0, 1, 0}, {
0, 0, 1/2, 0, 1/2}, {1/3, 1/3, 0, 1/3, 0}}]\)], "Input"],
Cell["2. \t0; 0.083", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[
N[{{1, 0, 0, 0, 0}} .
MatrixPower[{{0, 1/2, 0, 0, 1/2}, {1/2, 0, 0, 0, 1/2}, {0, 0, 0, 1,
0}, {0, 0, 1/2, 0, 1/2}, {1/3, 1/3, 0, 1/3, 0}}, 2], 3]]\)],
"Input"],
Cell[BoxData[
\(MatrixForm[
N[{{1, 0, 0, 0, 0}} .
MatrixPower[{{0, 1/2, 0, 0, 1/2}, {1/2, 0, 0, 0, 1/2}, {0, 0, 0, 1,
0}, {0, 0, 1/2, 0, 1/2}, {1/3, 1/3, 0, 1/3, 0}}, 3], 3]]\)],
"Input"],
Cell["3.\tThe stable state vector is:", "Text",
FontFamily->"Geneva"],
Cell[BoxData[
\(MatrixForm[
N[{{1, 0, 0, 0, 0}} .
MatrixPower[{{0, 1/2, 0, 0, 1/2}, {1/2, 0, 0, 0, 1/2}, {0, 0, 0, 1,
0}, {0, 0, 1/2, 0, 1/2}, {1/3, 1/3, 0, 1/3, 0}}, 50], 3]]\)],
"Input"],
Cell["4.\t0.2", "Text",
FontFamily->"Geneva"],
Cell["\<\
5.\tThe stable state vector shows the long run probability of being \
in room 2 to be 20% and in room 3 to be 10%. So in the long run, the rat \
will spend 20% + 10%, or 30%, of the time in rooms 2 or 3.\
\>", "Text",
FontFamily->"Geneva"]
}, Closed]]
}, Closed]]
}, Open ]]
},
FrontEndVersion->"Macintosh 3.0",
ScreenRectangle->{{0, 640}, {0, 460}},
WindowSize->{520, 365},
WindowMargins->{{13, Automatic}, {31, Automatic}},
MacintoshSystemPageSetup->"\<\
00/0001804P000000_@2@?omonh35@9B7`<5:@?l0040004/0B`000003509H04/
02d5X5k/02H20@4101P00BL?00400@0000000000000000010000000000000000
0000000000000002000000@210D00000\>"
]
(***********************************************************************
Cached data follows. If you edit this Notebook file directly, not using
Mathematica, you must remove the line containing CacheID at the top of
the file. The cache data will then be recreated when you save this file
from within Mathematica.
***********************************************************************)
(*CellTagsOutline
CellTagsIndex->{}
*)
(*CellTagsIndex
CellTagsIndex->{}
*)
(*NotebookFileOutline
Notebook[{
Cell[CellGroupData[{
Cell[1731, 51, 53, 1, 98, "Title"],
Cell[1787, 54, 61, 1, 61, "Subtitle"],
Cell[1851, 57, 103, 4, 89, "Subsubtitle"],
Cell[1957, 63, 214, 6, 46, "Text"],
Cell[CellGroupData[{
Cell[2196, 73, 157, 5, 45, "Subsection"],
Cell[2356, 80, 63, 0, 30, "Text"],
Cell[2422, 82, 58, 1, 27, "Input"],
Cell[2483, 85, 57, 1, 27, "Input"],
Cell[2543, 88, 103, 2, 27, "Input"],
Cell[2649, 92, 155, 3, 59, "Input"],
Cell[2807, 97, 172, 3, 59, "Input"],
Cell[2982, 102, 166, 3, 59, "Input"],
Cell[3151, 107, 182, 4, 59, "Input"],
Cell[3336, 113, 191, 4, 59, "Input"],
Cell[3530, 119, 161, 3, 59, "Input"],
Cell[3694, 124, 182, 4, 59, "Input"],
Cell[3879, 130, 159, 3, 59, "Input"],
Cell[4041, 135, 162, 3, 59, "Input"],
Cell[4206, 140, 91, 1, 27, "Input"],
Cell[4300, 143, 165, 3, 59, "Input"],
Cell[4468, 148, 162, 3, 59, "Input"],
Cell[4633, 153, 163, 3, 59, "Input"],
Cell[4799, 158, 188, 4, 59, "Input"],
Cell[4990, 164, 155, 3, 59, "Input"],
Cell[5148, 169, 156, 3, 59, "Input"],
Cell[5307, 174, 91, 1, 27, "Input"],
Cell[5401, 177, 172, 3, 59, "Input"],
Cell[5576, 182, 168, 3, 59, "Input"],
Cell[5747, 187, 162, 3, 59, "Input"],
Cell[5912, 192, 189, 4, 59, "Input"],
Cell[6104, 198, 165, 3, 59, "Input"],
Cell[6272, 203, 160, 3, 59, "Input"],
Cell[6435, 208, 91, 1, 27, "Input"],
Cell[6529, 211, 101, 2, 27, "Input"],
Cell[6633, 215, 68, 1, 27, "Input"],
Cell[6704, 218, 235, 4, 59, "Input"],
Cell[6942, 224, 219, 4, 59, "Input"],
Cell[7164, 230, 211, 4, 59, "Input"],
Cell[7378, 236, 227, 4, 59, "Input"],
Cell[7608, 242, 227, 4, 59, "Input"],
Cell[7838, 248, 211, 4, 59, "Input"],
Cell[8052, 254, 211, 4, 59, "Input"],
Cell[8266, 260, 211, 4, 59, "Input"],
Cell[8480, 266, 227, 4, 59, "Input"],
Cell[8710, 272, 79, 1, 27, "Input"],
Cell[8792, 275, 81, 1, 27, "Input"],
Cell[8876, 278, 79, 1, 27, "Input"],
Cell[8958, 281, 81, 1, 27, "Input"],
Cell[9042, 284, 81, 1, 27, "Input"],
Cell[9126, 287, 82, 1, 27, "Input"],
Cell[9211, 290, 68, 1, 27, "Input"]
}, Closed]],
Cell[CellGroupData[{
Cell[9316, 296, 34, 0, 30, "Subsection"],
Cell[9353, 298, 257, 7, 71, "Text"],
Cell[9613, 307, 669, 11, 185, "Text"],
Cell[10285, 320, 53, 1, 27, "Input"],
Cell[10341, 323, 207, 5, 71, "Text"],
Cell[10551, 330, 53, 1, 27, "Input"],
Cell[10607, 333, 203, 5, 71, "Text"],
Cell[10813, 340, 53, 1, 27, "Input"],
Cell[10869, 343, 203, 5, 71, "Text"],
Cell[11075, 350, 75, 1, 27, "Input"],
Cell[11153, 353, 150, 4, 52, "Text"],
Cell[11306, 359, 218, 4, 75, "Input"],
Cell[11527, 365, 147, 4, 52, "Text"],
Cell[11677, 371, 46, 1, 27, "Input"],
Cell[11726, 374, 904, 19, 166, "Text"],
Cell[12633, 395, 543, 9, 147, "Text"],
Cell[13179, 406, 168, 4, 52, "Text"],
Cell[13350, 412, 184, 5, 52, "Text"],
Cell[13537, 419, 168, 4, 52, "Text"],
Cell[13708, 425, 313, 6, 90, "Text"],
Cell[14024, 433, 218, 5, 71, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[14279, 443, 42, 0, 30, "Subsection"],
Cell[CellGroupData[{
Cell[14346, 447, 540, 10, 145, "Subsubsection"],
Cell[14889, 459, 400, 7, 109, "Text"],
Cell[15292, 468, 50, 1, 27, "Input"],
Cell[15345, 471, 483, 8, 147, "Text"],
Cell[15831, 481, 60, 1, 27, "Input"],
Cell[15894, 484, 642, 10, 185, "Text"],
Cell[16539, 496, 54, 1, 27, "Input"],
Cell[16596, 499, 465, 10, 166, "Text"],
Cell[17064, 511, 64, 1, 27, "Input"],
Cell[17131, 514, 397, 7, 128, "Text"],
Cell[17531, 523, 698, 18, 185, "Text"],
Cell[18232, 543, 588, 16, 90, "Text"],
Cell[18823, 561, 71, 1, 27, "Input"],
Cell[18897, 564, 516, 9, 147, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[19450, 578, 574, 10, 148, "Subsubsection"],
Cell[20027, 590, 63, 1, 27, "Input"],
Cell[20093, 593, 605, 10, 166, "Text"]
}, Closed]]
}, Closed]],
Cell[CellGroupData[{
Cell[20747, 609, 40, 0, 30, "Subsection"],
Cell[20790, 611, 296, 6, 90, "Text"],
Cell[21089, 619, 54, 1, 27, "Input"],
Cell[21146, 622, 203, 5, 71, "Text"],
Cell[21352, 629, 70, 1, 27, "Input"],
Cell[21425, 632, 150, 4, 52, "Text"],
Cell[21578, 638, 71, 1, 27, "Input"],
Cell[21652, 641, 309, 6, 90, "Text"],
Cell[21964, 649, 181, 3, 75, "Input"],
Cell[22148, 654, 406, 7, 109, "Text"]
}, Closed]],
Cell[CellGroupData[{
Cell[22591, 666, 31, 0, 30, "Subsection"],
Cell[22625, 668, 462, 8, 128, "Text"],
Cell[23090, 678, 102, 2, 43, "Input"],
Cell[23195, 682, 81, 1, 33, "Text"],
Cell[23279, 685, 127, 2, 43, "Input"],
Cell[23409, 689, 100, 1, 33, "Text"],
Cell[23512, 692, 176, 4, 52, "Text"],
Cell[23691, 698, 78, 1, 33, "Text"],
Cell[23772, 701, 141, 4, 52, "Text"],
Cell[23916, 707, 134, 4, 52, "Text"],
Cell[CellGroupData[{
Cell[24075, 715, 32, 0, 42, "Subsubsection"],
Cell[24110, 717, 69, 1, 33, "Text"],
Cell[24182, 720, 159, 2, 59, "Input"],
Cell[24344, 724, 54, 1, 33, "Text"],
Cell[24401, 727, 228, 5, 91, "Input"],
Cell[24632, 734, 228, 5, 91, "Input"],
Cell[24863, 741, 71, 1, 33, "Text"],
Cell[24937, 744, 229, 5, 91, "Input"],
Cell[25169, 751, 47, 1, 33, "Text"],
Cell[25219, 754, 252, 5, 71, "Text"]
}, Closed]]
}, Closed]]
}, Open ]]
}
]
*)
(***********************************************************************
End of Mathematica Notebook file.
***********************************************************************)