(*********************************************************************** Mathematica-Compatible Notebook This notebook can be used on any computer system with Mathematica 4.0, MathReader 4.0, or any compatible application. The data for the notebook starts with the line containing 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[ 11590, 328]*) (*NotebookOutlinePosition[ 12464, 359]*) (* CellTagsIndexPosition[ 12420, 355]*) (*WindowFrame->Normal*) Notebook[{ Cell[CellGroupData[{ Cell[TextData[StyleBox["Markov Chains", FontFamily->"Times", FontSize->24]], "Input", TextAlignment->Center, ImageRegion->{{-0, 1}, {0, 1}}], Cell[BoxData[{ \(Author : \ Thomas\ Shores\), "\[IndentingNewLine]", \(University\ of\ Nebraska\), "\[IndentingNewLine]", \(Send\ comments\ \(to : \ tshores@math . unl . edu\)\)}], "Input", FontFamily->"Helvetica", FontWeight->"Plain", FontVariations->{"CompatibilityType"->0}], Cell[CellGroupData[{ Cell["Markov Chains: An Application of Matrix Arithmetic", "Subsection", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "We are going to illustrate the idea of a Markov chain by way of an \ example: Suppose two toothpaste companies compete for customers in a fixed \ market in which each customer uses either Brand A or Brand B. Suppose also \ that a market analysis shows that the buying habits of the customers fit the \ following pattern in the quarters that were analyzed: each quarter (three \ month period) 30% of A users will switch to B while the rest stay with A. \ Moreover, 40% of B users will switch to A in a given quarter, while the \ remaining B users will stay with B. If we assume that this pattern does not \ vary from quarter to quarter, we have an example of a Markov chain model. \n\n\ In tabular form: Switch from\n \ A B\n \ A 0.7 0.4\n\t\tSwitch to \n \ B 0.3 0.6\n \ \n Notice that if a", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " and b", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " are the fractions of the customers using A and B, respectively, in a \ given quarter, a", StyleBox["1", FontVariations->{"CompatibilityType"->"Subscript"}], " and b", StyleBox["1", FontVariations->{"CompatibilityType"->"Subscript"}], " the fractions of customers using A and B in the next quarter, then our \ hypotheses say that :\n\n\ta", StyleBox["1", FontVariations->{"CompatibilityType"->"Subscript"}], " = 0.7 a", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " + 0.4 b", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " \n\tb", StyleBox["1 ", FontVariations->{"CompatibilityType"->"Subscript"}], " = 0.3 a", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " + 0.6 b", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], ".\n\nThere is a matrix multiplication lurking here, namely: \n{a", StyleBox["1", FontVariations->{"CompatibilityType"->"Subscript"}], " , b", StyleBox["1", FontVariations->{"CompatibilityType"->"Subscript"}], "} = {{0.7 , 0.4 }, { 0.3 , 0.6}} . {a", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], ", b", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], "}.\n\nFor example, let's suppost the initial state is a", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " = 0.3, b", StyleBox["0", FontVariations->{"CompatibilityType"->"Subscript"}], " = 0.7. Here's a setup in ", StyleBox["Mathematica", FontSlant->"Italic"], " to get the next state:" }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["a = {{0.7, 0.4}, {0.3, 0.6}}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MatrixForm[a]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["x = {0.3, 0.7}", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["MatrixForm[x]", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell["a . x", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "The preceding example illustrates the basic ingredients of a Markov chain: \ first, every element of the system we are studying is in exactly one of a \ fixed number of states (in our example, each customer uses either A or B). \ Notice that in any given quarter, the system can be completely described by \ a ", StyleBox["STATE VECTOR", FontSlant->"Italic"], " of the form X = {", StyleBox["a", FontSlant->"Italic"], ",", StyleBox["b", FontSlant->"Italic"], "} (think of this as a column vector in this situation, so that \ multiplication by a 2", "\[Cross]", "2 matrix makes sense), where ", StyleBox["a", FontSlant->"Italic"], " is the fraction of customers currently using A and ", StyleBox["b", FontSlant->"Italic"], " the fraction of customers currently using B. Observe that the sum of \ these numbers must be 1. The second condition for a Markov chain model is \ that the transition from one state to the next state (in our case, the \ transition from the state in one quarter to the next) is effected by \ multiplying the current state vector by a fixed square matrix with this \ property: each column of the matrix is a state vector; this matrix is called \ the ", StyleBox["TRANSITION MATRIX", FontSlant->"Italic"], " of the system. The transition matrix of our example occurs in the \ preceding equation. \n\nOnce you have a transition matrix A for a Markov \ chain, it is very easy to predict what happens to a given state vector X \ after one period: the next state is simply A . X. \n\nIn fact, it is easy \ to extend this idea to any number of periods: The state vector X is \ transformed into A . A . ... . A . X after ", StyleBox["k", FontSlant->"Italic"], " periods, where the number of factors of A is ", StyleBox["k", FontSlant->"Italic"], ".\nTry it out on our example: let's see what the distribution is three \ years later." }], "Text", ImageRegion->{{-0, 1}, {0, 1}}], Cell["a . a . a . x", "Input", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ "How about after ten? And what happens if we start with a different state? \ Something interesting is going on here.\n\t\nWhat seems to be happening is \ that no matter where we start, the states tend towards some common value. In \ other words, as we move along, multiplication by the matrix ", StyleBox["a", FontSlant->"Italic"], " has a smaller and smaller effect on the state vector. This inspires a \ definition: a ", StyleBox["steady state vector", FontSlant->"Italic"], " for the matrix ", StyleBox["a", FontSlant->"Italic"], " is one for which multiplication has no effect whatsoever, that is, a \ vector ", StyleBox["v", FontSlant->"Italic"], " such that ", StyleBox["a", FontSlant->"Italic"], ".", StyleBox["v ", FontSlant->"Italic"], "= ", StyleBox["v", FontSlant->"Italic"], ". Put another way, \n\t\n\t0 = v - a . v = (I - a) . v\n\t\nOf course, \ its important that we be able to find a steady state vector whose entries add \ up to 1 and are nonnegative; otherwise, the vector cannot be a \ \[OpenCurlyDoubleQuote]state'' for the Markov chain. Actually, it is \ sufficient that the entries of the vector be nonnegative with at least one \ positive entry, for then all we have to do is to divide the vector by the sum \ of its coordinates to get a state vector in the sense of Markov chains. For \ this, you are going to need a new command from ", StyleBox["Mathematica", FontSlant->"Italic"], ", namely, NullSpace[I-a]. Try it. " }], "Text", ImageRegion->{{-0, 1}, {0, 1}}] }, Closed]], Cell[CellGroupData[{ Cell["Exercises", "Subsection", ImageRegion->{{-0, 1}, {0, 1}}], Cell[TextData[{ StyleBox["Suppose we have the transition matrix A:\n ", FontWeight->"Plain"], StyleBox["\:f2e6", FontWeight->"Plain"], StyleBox["0.5 0.3 0.3", FontWeight->"Plain"], StyleBox["\:f2f6", FontWeight->"Plain"], StyleBox["\n A = ", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["0.1 0.6 0.2", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox["\n ", FontWeight->"Plain"], StyleBox["\:f2e8", FontWeight->"Plain"], StyleBox["0.4 0.1 0.5", FontWeight->"Plain"], StyleBox["\:f2f8", FontWeight->"Plain"], StyleBox["\n (1) Given that this is a Markov Chain transition matrix, find \ all steady states for\n this matrix.\n (2) For the initial \ vectors x", FontWeight->"Plain"], StyleBox["0", FontWeight->"Plain", FontVariations->{"CompatibilityType"->"Subscript"}], StyleBox[" = {1,0,0} and y", FontWeight->"Plain"], StyleBox["0", FontWeight->"Plain", FontVariations->{"CompatibilityType"->"Subscript"}], StyleBox[" = {0,0.5,0.5}, follow the Markov process\n for ten \ periods. Do these vectors tend towards the steady state?\n \n \ \nRepeat the above exercise using the matrix B:\n \ ", FontWeight->"Plain"], StyleBox["\:f2e6", FontWeight->"Plain"], StyleBox["1 0 0 ", FontWeight->"Plain"], StyleBox["\:f2f6", FontWeight->"Plain"], StyleBox[" \n B = ", FontWeight->"Plain"], StyleBox["\:f2e7", FontWeight->"Plain"], StyleBox["0 0.2 0.7", FontWeight->"Plain"], StyleBox["\:f2f7", FontWeight->"Plain"], StyleBox[" \n ", FontWeight->"Plain"], StyleBox["\:f2e8", FontWeight->"Plain"], StyleBox["0 0.8 0.3", FontWeight->"Plain"], StyleBox["\:f2f8", FontWeight->"Plain"], StyleBox[" \nUse the initial vectors above. Can you explain the \ results ?\n", FontWeight->"Plain"] }], "Input", CellMargins->{{8, Inherited}, {Inherited, Inherited}}, ImageRegion->{{-0, 1}, {0, 1}}, FontFamily->"Times"] }, Closed]] }, Closed]] }, FrontEndVersion->"4.0 for X", ScreenRectangle->{{0, 1152}, {0, 864}}, WindowToolbars->{}, CellGrouping->Manual, WindowSize->{520, 600}, WindowMargins->{{Automatic, 308}, {104, Automatic}}, PrivateNotebookOptions->{"ColorPalette"->{RGBColor, -1}}, ShowCellLabel->True, ShowCellTags->False, RenderingOptions->{"ObjectDithering"->True, "RasterDithering"->False}, Magnification->1.5 ] (*********************************************************************** 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[1739, 51, 148, 4, 69, "Input"], Cell[1890, 57, 297, 6, 94, "Input"], Cell[CellGroupData[{ Cell[2212, 67, 106, 1, 102, "Subsection"], Cell[2321, 70, 2932, 69, 70, "Text"], Cell[5256, 141, 79, 1, 70, "Input"], Cell[5338, 144, 64, 1, 70, "Input"], Cell[5405, 147, 65, 1, 70, "Input"], Cell[5473, 150, 64, 1, 70, "Input"], Cell[5540, 153, 56, 1, 70, "Input"], Cell[5599, 156, 2003, 46, 70, "Text"], Cell[7605, 204, 64, 1, 70, "Input"], Cell[7672, 207, 1592, 39, 70, "Text"] }, Closed]], Cell[CellGroupData[{ Cell[9301, 251, 65, 1, 46, "Subsection"], Cell[9369, 254, 2193, 70, 70, "Input"] }, Closed]] }, Closed]] } ] *) (*********************************************************************** End of Mathematica Notebook file. ***********************************************************************)