Generating a transition probability matrix in excel

[abberyfarm]

Hi there,

I have a difficult problem.

Would anybody know if or how excel can be used to generate a transition probability matrix of data. It is to be used in a markov chain analysis later but I just wish to find out if excel can be used for now.

I'm thinking maybe it could be done with a pivot table or perhaps an add-in has been developed to do this already.

I have time, speed and acceleration data for a car in three columns. I'm trying to generate a 2 dimensional transition probability matrix of velocity and acceleration.

The concept is given a particular speed and acceleration I want to be able to look at the matrix and identify the most likely (probable) speed and acceleration that could occur next.

I have attached two pictures which illustrate the concept here. It is a secure file sharing site.

http://www.sendspace.com/file/3h7j49
http://www.sendspace.com/file/44myq4
http://www.sendspace.com/file/fo0fnz

I also attached a sample data file if anyone has an idea and wants to experiment

Appreciate any input

John

 

[baitmaster]

I can't read your files because access is blocked by IT policy where I am, but this is definitely possible using Excel

There are various statistical packages that may well cover some of this, but I suspect you would benefit from writing your own piece of code to do this

As I understand it, you presumeably want to use VBA to create your probability matrix, not to use a matrix that you create manually in order to calculate other things... if that makes sense...

To do this, you can generate random values, compare them with probabilities of occurence of certain events, and use IF statements to decide outcomes in different iterations of your calculation. You can do this using either VBA or formulas

To get better responses, you need to tell us the actual algorithm you want to step through. We need the sequence of questions you want your calculation to perform, how many times you want to perform it etc etc

 

[shg]

Perhaps you could upload the files to a site that doesn't prompt people to download executable files and codecs for movies. I'd suggest box.net.

 

[shg]

Also, if you're slicing at fixed time intervals, aren't speed (scalar velocity) and scalar acceleration redundant? If you know the one, you know the other (without benefit of having seen your data).

 

[abberyfarm]

Hi Guys,

Thanks for the reply.

I’ve moved the images to a different site, which does not require them to be downloaded. You can view them online. Hopefully the IT policy will allow you to connect.

http://imageshack.us/photo/my-images/830/excel1.png/
http://imageshack.us/photo/my-images/191/excel2.png/

Yes, I would like to use VBA to create the transition matrix. I have an OK understanding of it but would not be capable of writing code to do this task.

To generate the transition matrix, there are a few steps which I think would be best tacked individually in order to break the problem down into more manageable chunks.

The first step would be to create frequency matrices. A frequency matrix would keep track of how often each future state occurs for a given current state. A state is a speed, acceleration point i.e. the first state in the sample data is (0, 0.0). By capturing all possible future states for a given current state, the probability of transition between two states could be calculated. We can leave the transition matrix for the time being.

At the end of the process every possible state reflected in the dataset would have it’s own frequency matrix that reflects how frequently future states occurred based on a given current state.

So for example, consider the frequency matrix for state (5,0.3), if a cycle is at a state of 5 km/hr speed and 0.3 m2/s acceleration, there was one instance where the next state was 1 km/hr speed and -1.1 m2/s acceleration, and there were two instances where the next state was 2 km/hr speed and -0.8 m2/s acceleration.

So to start with I think it would be best to get this working - If this is even possible with VBA?

The logical steps to follow I imagine would be something like this
1. For the first state create a frequency matrix (0,0), then search down through the list to see if state (0,0) occurs again, if it does occur then note the state immediately following it and go to the frequency matrix and update it, then go back to the list and continue on looking for (0,0), if it occurs again do the same. If it only only occurs once then mark 1 in the frequency matrix.
2. Move to the second state and repeat the process.
3. Continue until the last state on the list.

I understand this is a big task and I would really appreciate you help with this.

Thank you in advance

 

[shg]

I would make a collection of unique states and number them 1 to N, and use something (a comma-separated string?) that lists the following states, and then process those into an array suitable for lookup by a random number.

What's the purpose of all this?

 

[abberyfarm]

Hello thanks for the reply,

Well I doing a Markov Chain analysis http://en.wikipedia.org/wiki/Markov_chain on data that I've collected. But in order to do this you must first generate transition probability matrices.

It is easier to generate frequency matrices first and then convert them to transition matrices. The frequency matrices are the hard part.

Your concept sounds good. Unfortunately I do not have sufficient knowledge of vba to write code to do this.

Would you be prepared to attempt it? I can help you where ever I can.

I would be very grateful.

John

 

[abberyfarm]

Hey guys,

I thought this was an independent site, just to let you know I've cross posted this question on another site. Sorry about this.

Here is the link

http://www.excelforum.com/excel-programming/791268-generating-frequency-matrices-in-excel.html

 

[shg]

       -B- --C-- --D--- E ---F--- G -H- -I- -J- -K- -L- -M- N -O- P --Q-- --R-- --S-- --T-- --U-- --V-- W --X---
   2    s  km/hr m/s/s    To \ Fr    0   1   2   3   4   5    Sum      0     1     2     3     4     5    0.6559
   3    1     0   0.00         0     -   -   1   -   -   -     1                0.00                           2
   4    2     1   0.28         1     1   -   1   -   -   1     3    0.00        0.33              0.67         2
   5    3     4   0.83         2     1   -   -   -   1   3     5    0.00                    0.20  0.40         5
   6    4     5   0.28         3     -   1   1   -   -   -     2          0.00  0.50                           2
   7    5     2  -0.83         4     -   2   1   1   -   -     4          0.00  0.50  0.75                     2
   8    6     4   0.56         5     -   -   -   1   3   -     4                      0.00  0.25               4
   9    7     5   0.28                                                                                          
  10    8     1  -1.11                                                                                          
  11    9     4   0.83                                                                                          
  12   10     2  -0.56                                                                                          
  13   11     1  -0.28                                                                                          
  14   12     3   0.56                                                                                          
  15   13     4   0.28                                                                                          
  16   14     5   0.28                                                                                          
  17   15     2  -0.83                                                                                          
  18   16     0  -0.56                                                                                          
  19   17     2   0.56                                                                                          
  20   18     3   0.28                                                                                          
  21   19     5   0.56                                                                                          
  22   20     2  -0.83

B:D is your input data. Col D, acceleration, is wholly redundant; it is just the computed acceleration between adjacent states.

The frequency table is in H:M, with this formula in H3 and across and down:

=COUNTIFS($C$3:$C$21, H$2, $C$4:$C$22, $F3)

O3 and down sums the number of state transitions:

=SUM(H3:M3)

Q:V is the transition matrix with this in Q3 and across and down:

=IF(H3=0, "", SUM($G3:G3)/$O3)

X2 is a random rumber, and X3 and down use it and the transition matrix to select the next state:

=INDEX($Q$2:$V$2, MATCH(X$2, Q3:V3))

 

[shg]

Oops, frequency table was reversed:

       -B-- --C-- --D--- E --F-- G -H- -I- -J- -K- -L- -M- N -O- P --Q-- --R-- --S-- --T-- --U-- --V-- W --X---
   2   Time State m/s/s    Fr\To    0   1   2   3   4   5    Sum      0     1     2     3     4     5    0.8166
   3     1     0   0.00       0     -   1   1   -   -   -     2          0.00  0.50                           2
   4     2     1   0.28       1     -   -   -   1   2   -     3                      0.00  0.33               4
   5     3     4   0.83       2     1   1   -   1   1   -     4    0.00  0.25        0.50  0.75               4
   6     4     5   0.28       3     -   -   -   -   1   1     2                            0.00  0.50         5
   7     5     2  -0.83       4     -   -   1   -   -   3     4                0.00              0.25         5
   8     6     4   0.56       5     -   1   3   -   -   -     4          0.00  0.25                           2
   9     7     5   0.28                                                                                        
  10     8     1  -1.11                                                                                        
  11     9     4   0.83                                                                                        
  12    10     2  -0.56                                                                                        
  13    11     1  -0.28                                                                                        
  14    12     3   0.56                                                                                        
  15    13     4   0.28                                                                                        
  16    14     5   0.28                                                                                        
  17    15     2  -0.83                                                                                        
  18    16     0  -0.56                                                                                        
  19    17     2   0.56                                                                                        
  20    18     3   0.28                                                                                        
  21    19     5   0.56                                                                                        
  22    20     2  -0.83

Formula in H3 and across and down should be

=COUNTIFS($C$3:$C$21, $F3, $C$4:$C$22, H$2)