org.opentrafficsim.road.gtu.generator

Class MarkovCorrelation<S,I extends Number>

java.lang.Object

org.opentrafficsim.road.gtu.generator.MarkovCorrelation<S,I>

Type Parameters:

S - state type

I - intensity type

public class MarkovCorrelation<S,I extends Number>
extends Object

Markov Chain functionality using state auto-correlations. Rather than specifying a Transition Matrix, this matrix is calculated from a steady-state and from given auto-correlations. Auto-correlation increases the probability that state S returns after state S. Correlation between states can be captured with grouping several states under a super state. This creates a Transition Matrix within a cell of a Transition Matrix. To the super matrix, this is simply a single state-supplying element, applicable to all previous states that are concerned within the element.

This class is oblivious to intensity data of the states, in the sense that it must be provided to draw the next state. This class actually only remembers state auto-correlations. Together with input intensities, a part of the Transition Matrix is calculated on the fly. This flexibility over a fixed Transition Matrix allows 1) dynamic intensities, and 2) a single object of this class to be used for multiple processes in which intensities differ, but correlations are equal. This class is therefore also fairly flexible in terms of which states are concerned. Only states with correlation need to be added. For any state included in the input, for which no correlation is defined, a correlation of 0 is assumed. Reversely, states that are included in the class, but that are not part of the input states, are ignored.

Copyright (c) 2013-2019 Delft University of Technology, PO Box 5, 2600 AA, Delft, the Netherlands. All rights reserved.
BSD-style license. See OpenTrafficSim License.

Version:

$Revision$, $LastChangedDate$, by $Author$, initial version 18 dec. 2017

Author:

Alexander Verbraeck, Peter Knoppers, Wouter Schakel

Constructor Summary

Constructors

Constructor and Description
MarkovCorrelation()

Method Summary

Modifier and Type	Method and Description
void	addState(S state, double correlation) Adds a state to the root group of the Markov Chain.
void	addState(S superState, S state, double correlation) Adds a state to the group of the Markov Chain indicated by a super state.
S	drawState(S previousState, S[] states, I[] steadyState, StreamInterface stream) Draws a next state from this Markov Chain process, with predefined state correlations, but dynamic intensities.
String	toString()

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

MarkovCorrelation

public MarkovCorrelation()

Method Detail

addState

public void addState(S state,
                     double correlation)

Adds a state to the root group of the Markov Chain. The correlation increases the chance that the state will occur after itself. We have:

 p_ii = ss_i + (1 - ss_i) * c_i {eq. 1}
 

where,

   p_ii: the probability state i returns after state i
   ss_i: the steady-state (overall mean) probability of state i
   c_i:  correlation of state i
 

Effective correlations of states depend on correlations of other states as well, so the given correlation is not guaranteed to result. One can easily see this from a system with 2 states: A and B. Suppose B has correlation. In order to maintain the same overall steady-state (occurrence proportion of A and B), it follows that state A also must be seen more frequently to follow itself.

 not correlated:  A B B A A A B A A A B A A B B
 very correlated: A A A A A A A A A B B B B B B (all B's grouped together, hence all A's grouped together and correlated)
 

The effective correlation c_i of any state i can be calculated by reversing equation eq. 1 using for p_ii the effective value after all correlations are applied. The procedure to derive the various probabilities from state i to state j (p_ij) is explained below. The procedure is based on the transition matrix T, in which each value gives the probability that the state changes from i (the row) to state j (the column). Consequently, the values in each row must sum to 1, as each state will be followed by another state.

It is important that the transition matrix T results in a steady-state as provided. In particular we have for steady state S that S*T = S should hold. Suppose we have S = [0.7, 0.2, 0.1] for states A, B and C. Without any correlation this would give the base transition matrix:

     | p_11  p_12  p_13 |   | 0.70  0.20  0.10 |
 T = | p_21  p_22  p_23 | = | 0.70  0.20  0.10 | 
     | p_31  p_32  p_33 |   | 0.70  0.20  0.10 |
 

Our steady-state results as for whatever the previous state was, the steady-state probabilities are applied. Now suppose that state C has a correlation of 0.4. This would give that p_33 := p_33 + (1 - p_33) * c = 0.46. With this increased value, the probabilities of row 3 no longer add up to 1. Hence, p_31 and p_32 should be reduced. However, we require that the same steady-state S is maintained. This will remain the case for as long as T remains a reversible Markov Chain. This means that each state has as much input probability, as it has output probability. A matrix where, except for the values on the diagonal, all column values are equal, is reversible. So the base T without correlation is reversible, and we only need to maintain reversibility. A method to maintain reversibility is to scale symmetric pairs. Hence, if we reduce p_32, we should reduce p_23 by the same factor. Forcing row 3 to sum to 1, and scaling p_31, p_13, p_32 and p_23 by the same factor 0.6 we obtain the third matrix below.

      | 0.70  0.20  0.10 |    | 0.70  0.20  0.10 |    | 0.70  0.20  0.06 |    | 0.74  0.20  0.06 |
 T => | 0.70  0.20  0.10 | => | 0.70  0.20  0.10 | => | 0.70  0.20  0.06 | => | 0.70  0.24  0.06 |
      | 0.70  0.20  0.10 |    | 0.70  0.20  0.46 |    | 0.42  0.12  0.46 |    | 0.42  0.12  0.46 |
 

As we reduce p_13 and p_23, we also reduce the probability sums of rows 1 and 2. These reductions can be compensated by increasing the values on the diagonals, as is done in the fourth matrix. Note that changing the diagonal values does not affect reversibility. For example, 0.7*0.74 + 0.2*0.70 + 0.1*0.42 = 0.7 for the first column.

Changing the diagonal values p_11 and p_22 as the result of correlation for state C, shows that correlation of one state automatically introduces correlation at other states, as should also intuitively occur from the A-B example. The procedure can be started with the base T from steady-state S and can be repeated for each state i with correlation:

1. Increase p_ii to p_ii + (1-p_ii) * c_i.
2. Reduce p_ij for all j unequal to i such that row i sums to 1, use one factor f for all.
3. Reduce p_ji for all j unequal to i to maintain reversibility. Use factor f again.
4. Set all p_jj for all j unequal to i such that row j sums to 1.

Knowing that each value p_ij gets reduced for correlation of state i and j, and realizing that the reduction factors f equal (1 - c_i) and (1 - c_j) respectively, the effective correlation can be calculated by adding all reductions in a row to the diagonal value p_ii and using eq. 1.

See also "Construction of Transition Matrices of Reversible Markov Chains" by Qian Jiang.

Parameters:

state - S; state

correlation - double; correlation

Throws:

IllegalArgumentException - if correlation is not within the range (-1 ... 1), or the state is already defined

NullPointerException - if state is null

addState

public void addState(S superState,
                     S state,
                     double correlation)

Adds a state to the group of the Markov Chain indicated by a super state. If the super state is not yet placed in a sub-group, the sub-group is created. Grouping is useful to let a set of states correlate to any other of the states in the set. For example, after state A, both states A and B can occur with some correlation, while state C is not correlated to states A and B. The same correlation is applied when the previous state was B, as it is also part of the same group.

To explain sub-groups, suppose we have the following 3-state matrix in which the super state s_2 is located (this can be the root matrix, or any sub-matrix). In this matrix, state s_2 is replaced by a matrix S_2.

       s_1   s_2   s_3             s_1   S_2   s_3
 s_1 | p_11  p_12  p_13 |    s_1 | p_11  p_12  p_13 |
 s_2 | p_21  p_22  p_23 | => S_2 | p_21  p_22  p_23 |
 s_3 | p_31  p_32  p_33 |    s_3 | p_31  p_32  p_33 |
 

From the level of this matrix, nothing changes. Whenever the prior state was any of those inside S_2, row 2 is applied to determine the next state. If the next state is matrix S_2, the state is further specified by S_2. Matrix S_2 itself will be:

       s_2   s_4
 s_2 | p_22' p_24 |
 s_4 | p_42  p_44 |
 

It will thus result in either state s_2 or state s_4. More states can now be added to S_2, using the same super state s_2. In case the prior state was either s_1 or s_3, i.e. no state included in the sub-group, the matrix of the sub-group defaults to fractions based on the steady-state only. Correlations are then also ignored.

Correlation of s_2 is applied to the whole group, and all other states of the group can be seen as sub-types of the group's super state. Correlations as considered inside the group (c'_2 and c'_4) are mapped from the range c_2 to 1. So, c'_2 = 0, meaning that within the group there is no further correlation for the super state. Sub states, who are required to have an equal or larger correlation than the super state of the group, map linearly between c_2 and 1.

If the super state is only a virtual layer that should not in itself be a valid state of the system, it can simply be excluded from obtaining a new state using getState().

Parameters:

superState - S; state of group

state - S; state to add

correlation - double; correlation

Throws:

IllegalArgumentException - if correlation is not within the range (0 ... 1), the state is already defined, or superState is not yet a state

NullPointerException - if an input is null

drawState

public S drawState(S previousState,
                   S[] states,
                   I[] steadyState,
                   StreamInterface stream)

Draws a next state from this Markov Chain process, with predefined state correlations, but dynamic intensities. Any states that are present in the underlying Transition Matrix, but not present in the given states, are ignored. States that are not present in the underlying Transition Matrix, are added to it with a correlation of 0.

Parameters:

previousState - S; previous state

states - S[]; set of states to consider

steadyState - I[]; current steady-state intensities of the states

stream - StreamInterface; to draw random numbers

Returns:

S; next state

Throws:

IllegalArgumentException - if number of states is not the same as the stead-state length

NullPointerException - if states, steadyState or stream is null

toString

public String toString()

Overrides:

toString in class Object