States and transitions
A journey is a sequence of states in which the probability of the next state depends only on the current one:
Each row of the transition matrix sums to 1.
Absorbing states
Some states never leave: a conversion, a payment. Order the states so that transient states come first. Let Q hold the transitions among transient states and R the transitions from transient to absorbing states.
Nij is the expected number of visits to transient state j starting from i. The row sums of N give the expected number of steps before absorption. Bik is the probability of ending in absorbing state k when starting from i.
A three-state example
Illustrative states: Search (S) and List (L) are transient; Conversion (C) and Exit (E) are absorbing. From S: to L with 0.6 and to E with 0.4. From L: to S with 0.1, to C with 0.3 and to E with 0.6. Then I − Q has determinant 1 − 0.6·0.1 = 0.94, and N = (1/0.94)·[[1, 0.6], [0.1, 1]]. Multiplying by R gives, starting from Search, a probability of conversion of 0.18 / 0.94 ≈ 0.19 and of exit of 0.76 / 0.94 ≈ 0.81. The expected number of steps from Search is (1 + 0.6) / 0.94 ≈ 1.70.
Limits
- The Markov assumption ignores history beyond the current state.
- Estimating transitions needs navigation or collection data, collected with the right consent.
- The probabilities above are invented, not measured.
Background reading
Works by other authors that treat the underlying methods. They are not Menlo Tech publications.
- Norris, J. Markov Chains. Cambridge University Press, 1997.
Related
Case studies