Transcription of 4 Absorbing Markov Chains - SSCC - Home
1 Last revised: 8 February 20094 Absorbing Markov ChainsSo far, we have focused onregularMarkov Chains for which the transition matrixPis primitive. Because primitivity requiresP(i, i)<1 for every statei, regular chainsnever get stuck in a particular state. However, other Markov Chains may have oneor moreabsorbing states. By definition, stateiis Absorbing whenP(i, i) = 1 (andhenceP(i, j) = 0 for allj6=i). In turn, the chain itself is called anabsorbing chainwhen it satisfies two conditions. First, the chain has at least one Absorbing , it is possible to transition from each non- Absorbing state to some absorbingstate (perhaps in multiple steps).
2 Consequently, the chain is eventually absorbed into one of these chapter focuses on Absorbing Markov Chains , developing some special anal-ysis of this type of chain . We begin with a simple social-psychological application,and then consider a more elaborate model of network Conformity to group pressureIn a famous psychology experiment, Asch (1951) examined the degree to which peopleconform to group pressure. Ostensibly, the experiment concerned visual subject was led into a room and seated with some other participants. The experi-menter presented them with a simple visual task to determine which of three lineswas the same length as a reference line.
3 In sequence, each participant was asked togive his response, with the subject answering last. The task was designed so that thecorrect response was obvious. However, unbeknownst to the subject, all of the otherparticipants were confederates of the experimenter, and had been instructed to givethe same incorrect answer. Thus, when it was finally the subject s turn to answer,the subject had to choose whether to give the correct answer (ignoring pressure toconform to the group) or the incorrect answer (giving into this pressure).After recording the responses, the experimenter presented another similar task,and participants again answered sequentially with the subject going last.
4 In oneversion of this experiment (reported by Cohen 1958), this procedure was repeated 35times in all. Thus, for each subject, the data might consist of a sequence of responsessuch asaababbaabbbabbbaaabbabbbbbbbbbbbbbbbbb bbbbbbb1We ve already seen one example of an Absorbing state at the end of Chapter 2. In the mover-stayer model, any individual who is a stayer (occupying some Absorbing stateiS) never changesstate. However, in that example, the chain itself was not Absorbing because it was not possible totransition (even indirectly) from any of the non- Absorbing (mover) states to some Absorbing (stayer)state.
5 The general observation is that a Markov chain can be neither regular nor Absorbing . Wewill develop a more complete typology of states and Chains in Chapter the correct answer (against the group) andbdenotes the incorrectanswer (with the group). This experiment was repeated with other subjects, each ofwhom generated his own response sequence. While hypothetical, the sequence aboveillustrates a common pattern. Namely, most subjects initially waver betweena s andb s, but eventually lock into a single response (with some subjects choosingaandothers choosingb).What type of process might generate such sequences?
6 A regular Markov chaincould potentially produce the initial portion (when subjects appear to be alternatingstochastically between responses) but cannot account for the final portion (when theprocess seems to have been absorbed ). To reconcile these observations, Cohen(1958) proposed a Markov chain model with 4 states:1permanent non-conformist2permanent conformist3temporary non-conformist4temporary conformistObservationally, subjects in state 1 or 3 give responsea, while subjects in state 2 or 4give responseb. But in Cohen s model, states 1 and 2 are Absorbing , while transitionscan occur from state 3 to 1 or 4, and from state 4 to 3 or 2.
7 More precisely, usingthe experimental data, Cohen estimated the transition matrixP= 0 which can be represented as the transition diagram -- ???? it is possible to transition from each of the non- Absorbing states (3 and 4)into an Absorbing state (1 or 2), this Markov chain is of the type of Markov chain ( , regular or Absorbing ), we can con-tinue to apply the matrix analysis developed in Chapter That is, for any Markov2In this example, it is possible to move directly from each non- Absorbing state to some absorbingstate. But the definition of an Absorbing chain merely requires indirect (multi-step) ,Pt(i, j) can always be interpreted as the probability that the process thatoccupied stateiin period 0 will occupy statejin periodt.
8 Thus, the followingcomputations reveal the (probabilistic) future of the chain .>> P = [1 0 0 0; 0 1 0 0; .06 0 .63 .31; 0 .05 .46 .49]P = 0 0 00 0 0 >> P^2ans = 0 0 00 0 >> P^3ans = 0 0 00 0 >> P^10ans = 0 0 00 0 >> P^100ans = 0 0 00 0 >> P^1000ans = 0 0 00 0
9 Cohen (1958), we might assume that subjects began the experiment inone of the non- Absorbing states. In the short run after only 2 or 3 responses most subjects would still occupy one of the non- Absorbing states. For instance,consider a subject who was initially a temporary non-conformist (state 3). For thethird response, she has a chance of being a temporary non-conformist and chance of being a temporary conformist (state 4).But in the long run after many responses each subject will eventually be-come either a permanent non-conformist (state 1) or a permanent conformist (state2).
10 In particular, if she was initially a temporary non-conformist (state 3), the sub-ject has a chance of ending up as a permanent non-conformist and a of ending up a permanent conformist. If she was initially a temporary con-formist (state 4), she has a chance of ending up a permanent non-conformistand a chance of ending up as a permanent conformist. This illustrates animportant general result: the limiting distribution for an Absorbing chain typicallydepends on the initial state of the process. In contrast, the Theorem from Chapter 1guarantees that the limiting distribution for a regular chain does not depend on theintial Analysis of expected time until absorptionFollowing the preceding example, the transition matrix for any Absorbing chain canbe written in the canonical formP=[I0R Q]
