12

What would be the common way of estimating MC transition matrix given the timeseries?

Is there R function for doing that?

user333
  • 6,621
  • 17
  • 44
  • 54

3 Answers3

16

Since the time series is discrete valued, you can estimate the transition probabilities by the sample proportions. Let $Y_{t}$ be the state of the process at time $t$, ${\bf P}$ be the transition matrix then

$$ {\bf P}_{ij} = P(Y_{t} = j | Y_{t-1} = i) $$

Since this is a markov chain, this probability depends only on $Y_{t-1}$, so it can be estimated by the sample proportion. Let $n_{ik}$ be the number of times that the process moved from state $i$ to $k$. Then,

$$ \hat{{\bf P}}_{ij} = \frac{ n_{ij} }{ \sum_{k=1}^{m} n_{ik} } $$

where $m$ is the number of possible states ($m=5$ in your case). The denominator, $\sum_{k=1}^{m} n_{ik}$, is the total number of movements out of state $i$. Estimating the entries in this way actually corresponds to the maximum likelihood estimator of the transition matrix, viewing the outcomes as multinomial, conditioned on $Y_{t-1}$.

Edit: This does assume that you have the time series observed at evenly spaced intervals. Otherwise, the transition probabilities would also depend on the time lag (even if they are still markovian).

Macro
  • 40,561
  • 8
  • 143
  • 148
  • 6
    I hear what you are saying. Basically observed frequencies will be my matrix... In simle words! – user333 Aug 16 '11 at 18:36
  • How about continuous state space ? Althou I'm struggling a bit to understand the concept? – user333 Aug 16 '11 at 19:58
  • 2
    For a continuous state space the problem becomes much more complicated, as you then need to estimate a *transition function* rather than a matrix. In that case, since the marginal probability of being in any particular state is 0 (similarly to how the probability of taking any particular point in the sample space is 0 for any continuous distribution) what I've described above doesn't make sense. In the continuous case I believe the estimate of the transition function is the solution to a set of differential equations (I'm not very familiar with this so someone please correct me if I'm wrong) – Macro Aug 17 '11 at 01:03
  • Does this method not assume 1 continuous observation, rather than many as per the post beneath? For example imagine E was an absorbing state... Then this would not be revealed here surely? – HCAI Sep 12 '12 at 23:52
6

It is very, with the hypothesis that your time series is stationary :

To simplify the excellent answer of Macro

Here you have your time series with 5 states : A, B, C, D, E

AAAEDDDCBEEEDBADBECADAAAACCCDDE

You just have to count first the transitions : - leaving A : 9 transitions Among those 9 transitions, 5 are A->A, 0 A->B, 1 A->C, 2 A->D, 1 A->E So the first line of your transition probability matrix is [5/9 0 1/9 2/9 1/9]

You do that counting for each state, and then obtain your 5x5 matrix.

Mickaël S
  • 1,258
  • 3
  • 10
  • 6
  • Great example, thank you. So Markov Chains concern themselves only with the number of transitions, not their placement, correct? For example, would `AAABBBA` have a a same matrix as `ABBBAAA`? – Marcin Aug 17 '11 at 13:25
  • yes, with Markov chain if you have the same number of transition you will have the same matrix. It is a good question. Even is you not have the exact same sequence you have the same "behavior" and that is the most important in modeling, if you want to repeat the exact same sequence why modeling? Just repeat your data. – Mickaël S Aug 17 '11 at 18:09
  • Is there another method of counting transitions that is position aware? I'm doing research on password cracking, so it'd be nice to have a method of assessing what is the most likely next character to occur. The problem with passwords is that people tend to follow rules like putting *'s at the start and end of the password, or finishing a password with a 1, so it's not just the transitions that count, but also their location. – Marcin Aug 17 '11 at 18:41
  • ok, i didn't think about that case, are you sure that Markov Chain is the best way to do what you want to do? If you think so, what are your state (each character is a state)? And how do you plan to calculate the transition? How do you plan to use the markov chain? – Mickaël S Aug 17 '11 at 18:57
2

the function markovchainFit from markovchain package deals with your problem.

Giorgio Spedicato
  • 3,444
  • 4
  • 29
  • 39