154
T. Krak
Fig. 5.5 Bayesian network representation of a discrete-time Markov chain {X t } t∈N 0 . Nodes
represent random variables. An incoming arc on a node represents that the distribution of the
corresponding random variable is influenced by the originating node of that arc. Correspondingly,
each node associates a probability distribution to its random variable, conditional on the values of
the random variables of the nodes on which it is dependent as before
non-descendants of X n . This is the general interpretation of the independence
properties of the arcs in a BN. In the special case of Markov chains that we are
considering here, the interpretation vastly simplifies. Notably, the ‘non-parents, nondescendants’ of any node X n are exactly its ‘grandparents’, ‘great-grandparents’ and
so on; it is the set of nodes {X m : m ∈ N 0 , m < n − 1}.
Put differently, the value of X n influences the distribution of all of its descendants
(i.e. the nodes X m , m > n), so long as we do not know the value of any of those
descendants themselves. We will next consider how we can quantify this.
We start by observing that for each node X n , n ∈ N, we have the associated
conditional probability P (X n | X n−1 ). Since the state-space X is taken to be finite,
we can conveniently represent these conditional probabilities in a |X |×|X | matrix.
For any t ∈ N 0 , this matrix T t is defined, for all x, y ∈ X , as
T t (x, y) := P (X t+1 = y | X t = x) ,
(5.3)
where the indexing is taken to be row-first. This matrix T t is called the transition
matrix of the Markov chain at time t. Its elements T t (x, y) are called the transition
probabilities from x to y, and they are the probabilities that a system that is in state x
at time t will be in state y at time t +1. This explains the subscript-indexing, whereby
the matrix T t contains the conditional probabilities associated to node X t+1 .
These transition matrices make it easy to connect back to the probability tree
representation of Markov chains that we encountered earlier:
Proposition 5.1 Let (X ∗
, ≺, p (·) ) be a probability tree that is a Markov chain, and
let T t denote the associated family of transition matrices, as defined above. Then for
all t ∈ N and all w ∈ X ∗ such that |w| = t, it holds that p w (y) = T t (w , y) for
all y ∈ X .
Proof Use Eq. (5.2), Definition 5.5 and Eq. (5.3).
The reason that we represent these probabilities using matrices is that this opens
up the entire toolbox of linear algebra. We will see that this allows us to very
succinctly write down certain relations and properties. For instance, we can now
write the influence of a node on its descendants, using a simple matrix product:
T. Krak
Fig. 5.5 Bayesian network representation of a discrete-time Markov chain {X t } t∈N 0 . Nodes
represent random variables. An incoming arc on a node represents that the distribution of the
corresponding random variable is influenced by the originating node of that arc. Correspondingly,
each node associates a probability distribution to its random variable, conditional on the values of
the random variables of the nodes on which it is dependent as before
non-descendants of X n . This is the general interpretation of the independence
properties of the arcs in a BN. In the special case of Markov chains that we are
considering here, the interpretation vastly simplifies. Notably, the ‘non-parents, nondescendants’ of any node X n are exactly its ‘grandparents’, ‘great-grandparents’ and
so on; it is the set of nodes {X m : m ∈ N 0 , m < n − 1}.
Put differently, the value of X n influences the distribution of all of its descendants
(i.e. the nodes X m , m > n), so long as we do not know the value of any of those
descendants themselves. We will next consider how we can quantify this.
We start by observing that for each node X n , n ∈ N, we have the associated
conditional probability P (X n | X n−1 ). Since the state-space X is taken to be finite,
we can conveniently represent these conditional probabilities in a |X |×|X | matrix.
For any t ∈ N 0 , this matrix T t is defined, for all x, y ∈ X , as
T t (x, y) := P (X t+1 = y | X t = x) ,
(5.3)
where the indexing is taken to be row-first. This matrix T t is called the transition
matrix of the Markov chain at time t. Its elements T t (x, y) are called the transition
probabilities from x to y, and they are the probabilities that a system that is in state x
at time t will be in state y at time t +1. This explains the subscript-indexing, whereby
the matrix T t contains the conditional probabilities associated to node X t+1 .
These transition matrices make it easy to connect back to the probability tree
representation of Markov chains that we encountered earlier:
Proposition 5.1 Let (X ∗
, ≺, p (·) ) be a probability tree that is a Markov chain, and
let T t denote the associated family of transition matrices, as defined above. Then for
all t ∈ N and all w ∈ X ∗ such that |w| = t, it holds that p w (y) = T t (w , y) for
all y ∈ X .
Proof Use Eq. (5.2), Definition 5.5 and Eq. (5.3).
The reason that we represent these probabilities using matrices is that this opens
up the entire toolbox of linear algebra. We will see that this allows us to very
succinctly write down certain relations and properties. For instance, we can now
write the influence of a node on its descendants, using a simple matrix product: