146
T. Krak
We next need some notation and definitions for ‘partial paths’, which in this
setting are also called situations. As before, a (full) path is a map ω : N 0 → X .
In contrast, a situation is defined as a (finite length) prefix of such a path. In other
words, a situation is an element of a set X n , for some n ∈ N. If w ∈ X n , n ∈ N,
is a situation, we write w i for its (i + 1)-th coordinate, i ∈ {0, . . . , n − 1}, and we
say that its length is |w| = n. Note that the indexing over the coordinates is taken to
start from zero rather than one—this is done for notational consistency with paths
ω. Since we will need to refer to it so often, we introduce the shorthand notation
w for the last element of w; so if w has length n, then w := w n−1 . The set of all
non-empty situations is X ∗ := ∪ n∈N X n , and we define X ∗
:= {} ∪ X ∗ , where
we add the empty situation denoted by .
As a final point in this notational digression, for any s, t ∈ N 0 such that s ≤ t,
we will introduce the shorthand notation s : t to denote the sequence of time points
s, . . . , t. Using our previously introduced notation, we can then write X s:t for the
random variables at these time points. Furthermore, for any n ∈ N 0 and any situation
w ∈ X n+1 , we can then use the previously introduced notation to write X 0:n = w;
this is understood to mean that the random variables at time points 0, . . . , n obtained
the states corresponding to the situation w.
We endow the set X ∗
with the prefix order, denoted ≺, which is a partial order
such that ≺ v for all v ∈ X ∗ and for all v, w ∈ X ∗ with lengths n = |v|
and m = |w|, it holds that v ≺ w if and only if n < m and v i = w i for all
i ∈ {0, . . . , n − 1}. This is just a rigorous but somewhat obfuscated way of saying
that v ≺ w if ‘v is the beginning of w’ or ‘w is what you can get if v happens first,
and then some other things happen’ or, indeed, ‘v is a prefix of w’.
The important thing to notice is that the ordered set (X ∗
, ≺) induces a graphical
tree structure, with all the situations as its vertices. This tree is what is known as
the event tree. It has as its root, and, for all v, w ∈ X ∗
, w is a descendant of v
exactly if v ≺ w. An example of such a tree is shown in Fig. 5.1, which (partially)
shows the event tree corresponding to a binary state-space X = {a, b}.
Such an event tree can be turned into an intuitive representation of a stochastic
process by augmenting it into a probability tree. This is done by assigning to each
situation w ∈ X ∗
in the tree a local model p w , which is a probability mass function
on X ; that is, it is a map p w : X → R ≥0 such that
x∈X p w (x) = 1. An example
of this is again illustrated in Fig. 5.1.
Definition 5.2 (Probability tree) A probability tree is a tuple (X ∗
, ≺, p (·) ),
where X ∗
is the set of all situations, ≺ is the prefix order on X ∗
and p (·) :
X ∗
× X → R ≥0 represents all local models, so that
x∈X p w (x) = 1 for all
w ∈ X ∗
.
The mechanism by which a stochastic process obtains a certain realisation
ω ∈ Ω can now be interpreted as performing a weighted, random walk along
this probability tree, starting from . Following the tree in Fig. 5.1, this is done
as follows: from , we transition either to a, with probability p (a), or to b, with
probability p (b). Suppose we transition to a. From this new situation, the next step
will take us either to aa, with probability p a (a), or to ab, with probability p a (b).
T. Krak
We next need some notation and definitions for ‘partial paths’, which in this
setting are also called situations. As before, a (full) path is a map ω : N 0 → X .
In contrast, a situation is defined as a (finite length) prefix of such a path. In other
words, a situation is an element of a set X n , for some n ∈ N. If w ∈ X n , n ∈ N,
is a situation, we write w i for its (i + 1)-th coordinate, i ∈ {0, . . . , n − 1}, and we
say that its length is |w| = n. Note that the indexing over the coordinates is taken to
start from zero rather than one—this is done for notational consistency with paths
ω. Since we will need to refer to it so often, we introduce the shorthand notation
w for the last element of w; so if w has length n, then w := w n−1 . The set of all
non-empty situations is X ∗ := ∪ n∈N X n , and we define X ∗
:= {} ∪ X ∗ , where
we add the empty situation denoted by .
As a final point in this notational digression, for any s, t ∈ N 0 such that s ≤ t,
we will introduce the shorthand notation s : t to denote the sequence of time points
s, . . . , t. Using our previously introduced notation, we can then write X s:t for the
random variables at these time points. Furthermore, for any n ∈ N 0 and any situation
w ∈ X n+1 , we can then use the previously introduced notation to write X 0:n = w;
this is understood to mean that the random variables at time points 0, . . . , n obtained
the states corresponding to the situation w.
We endow the set X ∗
with the prefix order, denoted ≺, which is a partial order
such that ≺ v for all v ∈ X ∗ and for all v, w ∈ X ∗ with lengths n = |v|
and m = |w|, it holds that v ≺ w if and only if n < m and v i = w i for all
i ∈ {0, . . . , n − 1}. This is just a rigorous but somewhat obfuscated way of saying
that v ≺ w if ‘v is the beginning of w’ or ‘w is what you can get if v happens first,
and then some other things happen’ or, indeed, ‘v is a prefix of w’.
The important thing to notice is that the ordered set (X ∗
, ≺) induces a graphical
tree structure, with all the situations as its vertices. This tree is what is known as
the event tree. It has as its root, and, for all v, w ∈ X ∗
, w is a descendant of v
exactly if v ≺ w. An example of such a tree is shown in Fig. 5.1, which (partially)
shows the event tree corresponding to a binary state-space X = {a, b}.
Such an event tree can be turned into an intuitive representation of a stochastic
process by augmenting it into a probability tree. This is done by assigning to each
situation w ∈ X ∗
in the tree a local model p w , which is a probability mass function
on X ; that is, it is a map p w : X → R ≥0 such that
x∈X p w (x) = 1. An example
of this is again illustrated in Fig. 5.1.
Definition 5.2 (Probability tree) A probability tree is a tuple (X ∗
, ≺, p (·) ),
where X ∗
is the set of all situations, ≺ is the prefix order on X ∗
and p (·) :
X ∗
× X → R ≥0 represents all local models, so that
x∈X p w (x) = 1 for all
w ∈ X ∗
.
The mechanism by which a stochastic process obtains a certain realisation
ω ∈ Ω can now be interpreted as performing a weighted, random walk along
this probability tree, starting from . Following the tree in Fig. 5.1, this is done
as follows: from , we transition either to a, with probability p (a), or to b, with
probability p (b). Suppose we transition to a. From this new situation, the next step
will take us either to aa, with probability p a (a), or to ab, with probability p a (b).