Seeking help creating a transition probability matrix for a markov chain

Hello,

I was hoping that somebody might be able to help me out in creating a transition probability matrix?

I normally use excel for statistical modelling but this particular problem takes hours to execute using spreadsheets and it is too large and complicated for a spreadsheet .

I have created a variables called 'data' and it contains velocity and acceleration data in 2 columns.

For example

Vel Acc
1   0.28
2   0.28
2   0.00
3   0.28
5   0.56
6   0.28

I was hoping to create a transition probability matrix of the probability of transition from one velocity acceleration pair to another. First of all you would create a frequency matrix counting all the transitions from one velocity acceleration pair to another and convert to a transition probability matrix by dividing by the row total.

Here is a graphical illustration of the matrix.

I would be very grateful if somebody had the time to help me with this. I'm trying to develop my matlab stills but would appreciate if somebody could show me how they would approach the problem.

Kind regards

Answer 1

[Roger Stafford]

It would be very similar to the solution I gave in your earlier posting. Let VA be your list of velocities and accelerations.

 [uv,~,nv] = unique(VA(:,1));
 [ua,~,na] = unique(VA(:,2));
 F = accumarray([nv,na],1,[length(nv),length(na)]);
 T = bsxfun(@rdivide,F,sum(F,2));

Again, the rows would correspond to velocity values in uv and the columns to corresponding accelerations in ua.

[John]

Hello Roger,

Thank you very much for your time this evening, it is much appreciated.

I'll test this out now and see how I get on. I have some studying to do!

Take care

[John]

Hello Roger,

I have tested the code. It is great, I have been trying to do this all week on my own. Can I ask what might seem like a silly question, T is the transition matrix but how can you tell what velocity/acceleration a particular cell is referring to? I'm having trouble reading it.

Are the variables na and nv the matrix's row and column's labels?

Here is some processed data if it helps.

https://dl.dropbox.com/u/54057365/All/VA.mat

Just in relation to simulating a markov chain in the other post that you helped me with. Say for example my initial state was 0,0 (Vel,Acc) and I wanted to simulate 100 steps.

I would do T^100, but how could I record the individual values at each step so that I could plot a graph at the end of the simulated profile.

 Kind Regards

John

[Roger Stafford]

My apologies, John. My thinking wasn't clear on this problem. Ignore the code I wrote above and replace it with the following:

 [u,~,n] = unique(data,'rows');
 N = length(n);
 F = accumarray([n(1:N-1),n(2:N)],1,[N,N]);
 T = bsxfun(@rdivide,F,sum(F,2));

The relationship between entries in T and velocity/acceleration pairs is this. An element T(n1,n2) = p means that the conditional probability of a transition from the velocity/acceleration pair at u(n1,:) to the pair at u(n2,:) is p.

In other words if you were to list all the possible N velocity/acceleration pairs in lexicographical order along the row side and along the column top of T you would have an N x N transition matrix between all these pairs of velocity/acceleration pairs.

[John]

Hello Roger,

Thank you for your help. Apologies for not describing the problem correctly in the first instance.

I tried the code with the sample data provided. The matrix is 222x222 but there are only 107 unique velocity/acceleration pairs listed in lexicographical order hence I am unsure as how to read the matrix.

Apologies for asking such a simple question but am I missing something?

Also could I ask you, if you think that the code below is suitable for simulating a markov chain.

Sean de Wolski another member in the forum suggested it to me but he was unsure if it was the correct method.

 Use a for-loop to loop n times for length you want. S

transC = [zeros(size(trans,1),1), cumsum(trans,2)]; %cumulative sum of rows, we will use this to decide on the next step.
n = 10;
states = zeros(1,n); %storage of states
states(1) = 1; %start at state 1 (or whatever)
for ii = 2:n
   %Generate a random number and figure out where it falls in the cumulative sum of that state's trasition matrix row
   [~,states(ii)] = histc(rand,transC(states(ii-1),:));
end

Kind regards

[Roger Stafford]

I set N to the wrong value. It should be the length of u, not the length of n. As it was you should have gotten NaNs on the last 115 rows when normalizing them. Again my apologies. Here is the corrected code. Let me know if there are any further errors.

 [u,~,n] = unique(data,'rows');
 N = length(u);
 F = accumarray([n(1:end-1),n(2:end)],1,[N,N]);
 T = bsxfun(@rdivide,F,sum(F,2));

Yes, Sean's code looks valid to me. He correctly uses 'histc' to choose the next state rather than the more inefficient 'find'. I probably would have generated all the 'rand' values in a vector at one time and then used elements from that vector in 'histc' sequentially in the for-loop but I think it makes little difference.

[John]

Hello Roger,

Thank you very much for your assistance and for commenting on Sean's code.

All the best

[Sri Santhosh]

Hello John

Have u succeeded in creating a transition probability matrix for state vectors velocity and acceleration? I am working on the similar task. However, By using the above code provided by Roger, I cannot generate a correct matrix. Could anyone help me?

[Attilio Pittelli]

Hi, i'm still getting a row of NaN, but not at the last row. Could you tell me why?

Thank you

Answer 2

[shahab anjum]

please help me too if i have 1000x286 matrix how can i calculate the transistion and emission probabilites of that matrix plz

help