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

 

[abberyfarm]

Thank you

I'll try it now

 

[abberyfarm]

Hello,

I want to thank your help yesterday and effort you have gone to understand what I'm trying do.

You may have a point about acceleration being redundant, it makes sense but I'm not sure.

I'm going to investigate both methods now of just using speed as a state but I also want to look at it with the two states, acceleration and speed.

Here is the reasoning behind it (this is not my theory)

The states required to satisfy the Markov property are determined based on the assumption that vehicle dynamics can be simplified using the following dynamic equation.

Fnet = Fprop - Frr - Fwr - Fgr = me x aveh = me x Vveh

where Fnet is the net force applied to the vehicle, Fporp is the propulsion force from the powertrain, Frr is the rolling resistance force, Fwr is the wind resistance force, Fgr is the grade resistance force and all other external forces applied to the vehicle, me is the equivalent vehicle mass, vveh is the vehicle velocity, and aveh is the vehicle acceleration. In the equation,
vehicle dynamics can be represented using two states, which are vehicle velocity and acceleration. Thus, we select them as the states for the Markov chain.

Here is a graphical representation of the process I'm trying to achieve. This is a secure site.

http://imageshack.us/photo/my-images/269/mw1.png/
http://imageshack.us/photo/my-images/535/mw2ey.png/

I am intending to a matrix as large as this, I have a few hundred thousand rows of data.

So I am wondering is it possible to use your method to generate the transition matrix for two states?

I would be grateful if you could help me out with the code.

Thank you

 

[shg]

Speed and velocity could well be independent, but not yours -- you CALCULATED acceleration as the change in speed, which adds no new information.

Suggest you talk to your prof and ask him what his expectation is.

 

[abberyfarm]

Hello,

I think acceleration might have to be taken into account.

I've collected lots of speed data from cars and I'm trying to generate one drive cycle to represent all the data that I've collected.

I'm just doing my own research, my professor would not know about this topic.

You see in the pictures, the probability of selecting the next speed, acceleration value differs depending on the the current speed, acceleration values.

For example, the probability of moving from (42,0.4) to (43,0.6) is 0.1687 and there is a probability of 0.0120 of moving to (43, 0.8).

What do you think?

Could you help me out with the code please and I let you know the outcome.

Your probably correct but I just want to check it out.

 

[shg]

The situation is no different whether you have one state variable or several.

States can be enumerated 0, 1, 2, ..., N, where each state represents a vector of state variables {speed, acceleration, weather, the price of snow cones, ...}. The 'vector' in the example is a single variable, speed, that is the same as the state number.

If the variables are continuous (versus assuming discrete values), then you need to bin each variable so that states with speed = 1mph, for example, really means speeds in the right-open interval [0.5, 1.5). Otherwise you end up with a lot of minimally-distinguishable states, and few (or no) repetitions of state transitions on which you can build a model.

Once you get a list of distinct states, you end up with the exact same format as in my example, with the only difference being that state doesn't mean just speed, it refers to a vector of state variables. That doesn't affect the rest of the example.

 

[abberyfarm]

Hello shg,

Thank you for you help with this markov chain problem a few months ago. It has been working great since.

I was wondering would you know how I could I specify the first state say for instance 0 and the next state would then be based on the TPM?

Thank you

John

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)

 

[abberyfarm]

Hi,

Apologies I don't mean to be bugging you but would you have any thoughts on how the function to select the next state in the markov chain could be modified so that you could specify the first state.

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

Many thanks

 

[shg]

Put the initial state in X2.

 

[abberyfarm]

OK thanks very much.

 

[abberyfarm]

Hello shg,

Thanks again for your help with the markov chain functions.

I have one further question, if you don't mind?

How could I simulate more states? The formula stops at the last row of the transition matrix, but how could I get it simulate more states for example 100 steps.

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))

Thanks for you help