Markov Chains

1 1 Markov ChainslPROPERTIESlREGULAR Markov CHAINSlABSORBING Markov CHAINSP roperties of Markov Chains Introduction Transition & State Matrices Powers of Matrices Applications2 Andrei Markov1856 -- 1922 Examples of Stochastic Processes1)Stock Market UP DOWN UNCHANGED2)Brand Loyalty:Stay with brand ASwitch to brand ASwitch away from brand A3)Brownian MotionProduct LoyaltyA marketing campaign has the effect that:80 % of consumers who use brand A stay with it (so 20% switch away from it)60 % consumers who use other brands switch to brand AWhat happens in the long run?Problem: FEEDBACK!

2 3 State transition diagramAA A A current statenext stateTo determine what happens, we need to know the current state, that is the percentage of consumers buying brand A Before the marketing campaign, brand A had a 10% market share:A A S0= [ ]Initial State Probability MatrixProbability that a randomly picked consumer buys brand A , does not buy brand A4AA 1A 2A2A 2A2A 2A2A of switching to A after one week of marketing:P(A1) = P(A0and A1)+P(A 0 and A1)= P(A0)P(A1|A0)+P(A 0)P(A1|A 0)= * + * = State Matrix:A A S1= [ ] == ] [PSS015If the marketing campaign keeps having the same effect week after week, then the same matrix P applies each week:After week 1:S1= [ ]After week 2:S2= S1P = (S0P)P = S0P2S2 = [ ] = == P2 Markov Chains or Processes Sequence of trial with a constant transition matrix P No memory (P does not change, we do not know whether or how many times P has already been applied)6A Markov process has nstates if there are npossible outcomes.

3 In this case each state matrix has nentries, that is each state matrix is a 1 x k-th state matrix is the result of applying the transition matrix P ktimes to an initial matrix [ skn] where skiis the proportion of the population in state iafter transition matrix P is a constant square matrix ( n x n if there are n states) where the (i,j)-th element (i-th row, j-th column) gives the probability of transition from state ito state all entries are between 0 and 1,0 pij 1and all rows add up to 1,p11+p12+..+p1n=17k01-kk3020232001201PS PS PPS PS SPS PPS PS S PS S=========Long Run Behavior of P = = = = = Run Behavior of S] [ S] [ S164==Running the marketing campaign for a long time is in-effective, after 4 weeks already are buying brand A.

4 In the next 12 weeks only more switch to brand that these numbers are overly accurate, the model can NOTbe that P always exist? NO! = = = = =+0110 P 1001 P 0110 P1001 P0110 P12k2k32 Better question: When does P exist?9 Regular Markov ChainsnSTATIONARY MATRICESnREGULAR MARKOVCHAINSnAPPLICATIONSnAPPROXIMATIONS R ecall: Brand Switch ExampleA:80% stay with Brand A20% switch to another Brand (A )A :60% Move to A (from A )40% do not move (still use another brand) = ' AAPA A'10 Initial Market ShareA : 10%A.

5 90%S0 = [ ]S1= S0P = [ ]S2= S0P2= [ ]S4= [ ]S10= [ ]S20= [ ]In the Long RunS = [ ] Stationary State Matrix[][] =SPStationary = Nothing Changes11 Stationary State MatrixThe state matrix S=[ sn] is astationary state matrixfor a Markovchain with transition matrix P ifSP = SWhere si>0 and s1+s2+ .. +sn= :nAre stationary state matrices unique?nAre stationary state matrices attractive?nWhat is attracted?nCan we tell by looking at P?12 Regular Matrices Regular Markov ChainsA transition matrix P is regularif some power of P has only positive ( strictly greater than zero ) regular Markov Chainis one that hasa regular transition matrix of regular matrices = =.

6 PP = = ..PP13 Examples Of Regular Markov may leave out loops of zero 1 Let P be a transition matrix for a regular Markov chain (A) There is a unique stationary matrix S, solution ofSP=S(B) Given any initial state S0the state matrices Skapproach the stationary matrix S(C) The matrices Pkapproach a limiting matrix ,whereeach row of is equal to the stationary matrix S. PPExample 2(Insurance Statistics)23%of drivers involved in an accident are involved in an accident in the following year (A)11%of drivers not involved in an accident are involvedin an accident in the following year (A )AA 2 (continued)If 5% of all drivers had an accident one year, what isthe probability that a driver, picked at random, has anaccident in the following year?

7 This Ayear A = [ ]S1= S0P = [ ], Prob(accident)= yearExample 2 (continued)What about the long run behavior? What percentageof drivers will have an accident in a given year? Since all entries in P are greater than 0, this is a regular Markov chain and thus has a steady state: = = = of drivers will have an solutionBy Theorem 1 part (A): Solve the equation S=SP[][] ) ( s1s 1,ss where,ssS12111111221221121212121= = = = = += =+=+= =++= ==+=Absorbing Markov ChainsnAbsorbing States and ChainsnStandard FormnLimiting MatrixnApproximations17 DefinitionA state is absorbing if, once the state is entered, it is impossible to leave arrow leaving the state to other state4 One arrow returning to state itself with 1 Example number on an entering arrow gives the probability of entering that state from the state where the arrow you are at A then you stay therewith probability 1, that is for sure.

8 Since all arrows leaving add up to 1, there is no other arrow leaving ExampleTo AB CA 1 0 0 0 = : Rows add to 1 Absorbingstates havea 1and 0 sin theircorresponding :From A to A is 1 From A to B or C it is 0A is absorbing19 Theorem 1:A state in a Markov chain is absorbingifand only if the row corresponding to the state has a 1 on the main diagonaland0 s everywhere versus StationaryAbsorbing does NOTimply that the states approacha stationary state. Recall a previous example: == = =+1000100011000100010010101002122nnPPPPP ,,So an absorbing state does not mean the matrix powers approach a limiting matrix20 What went wrong?

9 ACB111B is absorbing, but A and C keep flipping Definition:A Markov chain is an absorbingchainif 1)There is at least one absorbing state2)It is possible to go from each non absorbing state to at least one absorbing state in at a finite number of steps21 Another Definition:A transition matrix for an absorbing Markov Chainis in standardformif the rows and columns are labeled so that all the absorbing states precede allthe non absorbing states: QRNAAbsNAAbs0I .. Iis the identity = :(contd.) = Matrix:If P is the matrix of an absorbing Markov chain andP is in standard form, then there is a limiting matrix()Matrix lFundamenta and whereincreases, k as that such 1Q-I00I = = FFRPP PPk QRNAAbsNAAbs0I.

10 23 More Examples: = = = =..)( ,.. ,.QQR = = = = = 0010010011122025050050450500505050150500 501PF ,FR ,..).)(.(..Without the Theorem: = = = ,..PPP