Transition graph

A simple transition graph with two nodes. The adjacency matrix of the graph is . Since all entries are greater than 0 and all line sums are 1, it is line stochastic . ${\displaystyle A={\begin{bmatrix}0.3&0.7\\0.4&0.6\\\end{bmatrix}}}$

Transition graphs are special directed graphs with edge weights that establish a connection between stochastics and graph theory . They are particularly suitable for the clear representation of time-discrete, homogeneous Markov chains .

definition

A directed and edge-weighted graph is called a transition graph if the edge weights of the edges starting from each node are greater than 0 and add up to 1: ${\displaystyle G}$ ${\displaystyle i}$ ${\displaystyle i}$

${\displaystyle \sum _{j\in N_{G}^{+}(i)}c_{ij}=1}$.

Here is the successor set of nodes , i.e. the set of all nodes that can be reached by outgoing edges. ${\displaystyle N_{G}^{+}(i)}$ ${\displaystyle i}$ ${\displaystyle i}$

Equivalent to this is that the graph is an adjacency graph of a row-stochastic matrix . ${\displaystyle G}$

use

Transition graphs serve for the clear representation of homogeneous Markov chains with finite state space in discrete time . Each node corresponds to a state of the system and the edge weights are the transition probabilities between the states. Then there is exactly the probability to change from state to state . Some properties of the Markov chain can be found directly in the transition graph: ${\displaystyle c_{ij}}$ ${\displaystyle i}$ ${\displaystyle j}$

• The transition graph is strongly connected if and only if the Markov chain is irreducible .
• The state is the state of accessible if there is an available path in the transition graph. ${\displaystyle j}$ ${\displaystyle i}$ ${\displaystyle i-j}$
• Two states i and j communicate if and only if both a -path and a -path exist in the transition graph. ${\displaystyle i-j}$ ${\displaystyle j-i}$
• If the transition graph is bipartite , then every state of the Markov chain has an even period .
• If the transition graph is bipartite and connected, then the Markov chain has an even period.

Application example

With the help of transition graphs, the choice and purchase behavior can be visualized. The percentage of re-and changing voters is shown. Related to the above figure would 60% of the party or the product A remain faithful and change 40% to party or product e. The number of re-voters for party or product E is 30%, the number of alternate voters is 70%. However, the transition graph becomes quite confusing from four parties or products.

literature

• Hans-Otto Georgii: Stochastics . Introduction to probability theory and statistics. 4th edition. Walter de Gruyter, Berlin 2009, ISBN 978-3-11-021526-7 , doi : 10.1515 / 9783110215274 .
• Marion Patyna, Klaus Schilling: Lineare Algebra: Multistage Processes - Matrix Calculation, Eins Verlag Cologne, 1st edition 2011, pp. 104–118, ISBN 978-3-427-04440-6 .