Class MarkovCorrelation<S,I extends Number>
- java.lang.Object
-
- org.opentrafficsim.road.gtu.generator.MarkovCorrelation<S,I>
-
- Type Parameters:
S
- state typeI
- 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-2022 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 Description MarkovCorrelation()
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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()
-
-
-
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 equationeq. 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:- Increase p_ii to p_ii + (1-p_ii) * c_i.
- Reduce p_ij for all j unequal to i such that row i sums to 1, use one factor f for all.
- Reduce p_ji for all j unequal to i to maintain reversibility. Use factor f again.
- Set all p_jj for all j unequal to i such that row j sums to 1.
eq. 1
.
See also "Construction of Transition Matrices of Reversible Markov Chains" by Qian Jiang.- Parameters:
state
- S; statecorrelation
- double; correlation- Throws:
IllegalArgumentException
- if correlation is not within the range (-1 ... 1), or the state is already definedNullPointerException
- 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 usinggetState()
.
- Parameters:
superState
- S; state of groupstate
- S; state to addcorrelation
- double; correlation- Throws:
IllegalArgumentException
- if correlation is not within the range (0 ... 1), the state is already defined, or superState is not yet a stateNullPointerException
- 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 statestates
- S[]; set of states to considersteadyState
- I[]; current steady-state intensities of the statesstream
- StreamInterface; to draw random numbers- Returns:
- S; next state
- Throws:
IllegalArgumentException
- if number of states is not the same as the stead-state lengthNullPointerException
- if states, steadyState or stream is null
-
-