(*^ ::[ Information = "This is a Mathematica Notebook file. It contains ASCII text, and can be transferred by email, ftp, or other text-file transfer utility. It should be read or edited using a copy of Mathematica or MathReader. If you received this as email, use your mail application or copy/paste to save everything from the line containing (*^ down to the line containing ^*) into a plain text file. On some systems you may have to give the file a name ending with ".ma" to allow Mathematica to recognize it as a Notebook. The line below identifies what version of Mathematica created this file, but it can be opened using any other version as well."; FrontEndVersion = "NeXT Mathematica Notebook Front End Version 2.2"; NeXTStandardFontEncoding; fontset = title, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, L1, e8, 24, "Times"; ; fontset = subtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, bold, L1, e6, 18, "Times"; ; fontset = subsubtitle, inactive, noPageBreakBelow, noPageBreakInGroup, nohscroll, preserveAspect, groupLikeTitle, center, M7, italic, L1, e6, 14, "Times"; ; fontset = section, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, grayBox, M22, bold, L1, a20, 18, "Times"; ; fontset = subsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, blackBox, M19, bold, L1, a15, 14, "Times"; ; fontset = subsubsection, inactive, noPageBreakBelow, nohscroll, preserveAspect, groupLikeSection, whiteBox, M18, bold, L1, a12, 12, "Times"; ; fontset = text, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = smalltext, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 10, "Times"; ; fontset = input, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeInput, M42, N23, bold, L1, 12, "Courier"; ; fontset = output, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L-5, 12, "Courier"; ; fontset = message, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = print, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = info, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeOutput, M42, N23, L1, 12, "Courier"; ; fontset = postscript, PostScript, formatAsPostScript, output, inactive, noPageBreakInGroup, nowordwrap, preserveAspect, groupLikeGraphics, M7, l34, w282, h287, L1, 12, "Courier"; ; fontset = name, inactive, noPageBreakInGroup, nohscroll, preserveAspect, M7, italic, B65535, L1, 10, "Times"; ; fontset = header, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, italic, L1, 12, "Times"; ; fontset = leftheader, 12; fontset = footer, inactive, nohscroll, noKeepOnOnePage, preserveAspect, center, M7, italic, L1, 12, "Times"; ; fontset = leftfooter, 12; fontset = help, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = clipboard, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = completions, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12, "Courier"; ; fontset = special1, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special2, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special3, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special4, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; fontset = special5, inactive, nohscroll, noKeepOnOnePage, preserveAspect, M7, L1, 12; paletteColors = 128; magnification = 150; currentKernel; ] :[font = input; Cclosed; preserveAspect; center; startGroup] Markov Chains ;[s] 1:0,0;13,-1; 1:1,21,16,Times,1,24,0,0,0; :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Markov Chains: An Application of Matrix Arithmetic :[font = text; inactive; preserveAspect] 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. In tabular form: Switch from A B A 0.7 0.4 Switch to B 0.3 0.6 Notice that if a0 and b0 are the fractions of the customers using A and B, respectively, in a given quarter, a1 and b1 the fractions of customers using A and B in the next quarter, then our hypotheses say that : a1 = 0.7 a0 + 0.4 b0 b1 = 0.3 a0 + 0.6 b0. There is a matrix multiplication lurking here, namely: {a1 , b1} = {{0.7 , 0.4 }, { 0.3 , 0.6}} . {a0, b0}. For example, let's suppost the initial state is a0 = 0.3, b0 = 0.7. Here's a setup in Mathematica to get the next state: ;[s] 35:0,0;1038,1;1039,2;1045,3;1046,4;1132,5;1133,6;1139,7;1140,8;1238,9;1239,10;1249,11;1250,12;1258,13;1259,14;1263,15;1265,16;1274,17;1275,18;1283,19;1284,20;1346,21;1347,22;1351,23;1352,24;1389,25;1390,26;1393,27;1394,28;1448,29;1449,30;1459,31;1460,32;1487,33;1498,34;1521,-1; 35:1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] a = {{0.7, 0.4}, {0.3, 0.6}} :[font = input; preserveAspect] MatrixForm[a] :[font = input; preserveAspect] x = {0.3, 0.7} :[font = input; preserveAspect] MatrixForm[x] :[font = input; preserveAspect] a . x :[font = text; inactive; preserveAspect] 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 STATE VECTOR of the form X = {a,b} (think of this as a column vector in this situation, so that multiplication by a 2´2 matrix makes sense), where a is the fraction of customers currently using A and b 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 TRANSITION MATRIX of the system. The transition matrix of our example occurs in the preceding equation. Once 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. In 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 k periods, where the number of factors of A is k. Try it out on our example: let's see what the distribution is three years later. ;[s] 19:0,0;305,1;317,2;337,3;338,4;339,5;340,6;425,7;426,8;455,9;456,10;508,11;509,12;949,13;966,14;1371,15;1372,16;1419,17;1420,18;1504,-1; 19:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = input; preserveAspect] a . a . a . x :[font = text; inactive; preserveAspect; endGroup] How about after ten? And what happens if we start with a different state? Something interesting is going on here. What 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 a has a smaller and smaller effect on the state vector. This inspires a definition: a steady state vector for the matrix a is one for which multiplication has no effect whatsoever, that is, a vector v such that a.v = v. Put another way, 0 = v - a . v = (I - a) . v Of 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 ª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 Mathematica, namely, NullSpace[I-a]. Try it. ;[s] 17:0,0;288,1;289,2;378,3;397,4;413,5;414,6;492,7;493,8;505,9;506,10;507,11;509,12;511,13;512,14;1047,15;1058,16;1094,-1; 17:1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,10,8,Times,2,12,0,0,0;1,11,8,Times,0,12,0,0,0; :[font = subsection; inactive; Cclosed; preserveAspect; startGroup] Exercises :[font = input; preserveAspect; leftWrapOffset = 8; fontName = "Times"; endGroup; endGroup] Suppose we have the transition matrix A: æ0.5 0.3 0.3ö A = ç0.1 0.6 0.2÷ è0.4 0.1 0.5ø (1) Given that this is a Markov Chain transition matrix, find all steady states for this matrix. (2) For the initial vectors x0 = {1,0,0} and y0 = {0,0.5,0.5}, follow the Markov process for ten periods. Do these vectors tend towards the steady state? Repeat the above exercise using the matrix B: æ1 0 0 ö B = ç0 0.2 0.7÷ è0 0.8 0.3ø Use the initial vectors above. Can you explain the results ? ;[s] 29:0,0;57,1;58,2;72,3;73,4;87,5;88,6;102,7;103,8;120,9;121,10;135,11;136,12;280,13;281,14;297,15;298,16;514,17;515,18;529,19;530,20;546,21;547,22;559,23;560,24;580,25;581,26;593,27;594,28;664,-1; 29:1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,11,8,Times,64,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0;1,0,0,Symbol,0,12,0,0,0;1,11,8,Times,0,12,0,0,0; ^*)