Game Development Reference
In-Depth Information
we also use M + to denote the set M \{
. The length of a given word w
is denoted by len ( w ), where len ( ε ) = 0 and the length of an infinite word
is
ε
}
. The individual letters in w are denoted by w (0) ,w (1) ,... , and for
every infinite word w and every i
0weuse w i to denote the infinite word
w ( i ) ,w ( i +1) ,...
A transition system is a pair T =( S,→ ), where S is a finite or countably
infinite set of states and −→⊆S × S a transition relation such that for
every s ∈ S there is at least one outgoing transition (i.e., a transition of the
form s
t ). We say that
T
is finitely branching if every s
S has only
finitely many outgoing transitions. A path in
T
is a finite or infinite word
w over S such that w ( i )
i<len ( w ). A run is an
infinite path. The sets of all finite paths and all runs in
w ( i +1) for every 0
T
are denoted by
Fpath (
T
) and Run (
T
), respectively. Similarly, for a given w
Fpath (
T
), we
use Fpath (
,w ) to denote the sets of all finite paths and all
T
,w ) and Run (
T
is clear from the context, it is
usually omitted (for example, we write just Run instead of Run (
T
T
)).
Probability spaces
Let A be a finite or countably infinite set. A probability distribution on
A is a function μ : A
[0 , 1] such that a∈A μ ( a )=1. A distribution μ is
rational if μ ( a ) is rational for every a
A , positive if μ ( a ) > 0 for every
a
A , and Dirac if μ ( a ) = 1 for some a
A . A Dirac distribution μ where
μ ( a ) = 1 is also denoted by μ a or just a .
LetΩbeasetof elementary events .A σ -field over Ω is a set
2 Ω
that includes Ω and is closed under complement and countable union.
A measurable space is a pair (Ω ,
F⊆
F
) where
F
is a σ -field over Ω. An
F
-measurable function over (Ω ,
F
) is a function f
R
such that
f 1 ( I )
∈F
for every interval I in
R
.
Example 5.1
be the least
σ -field over Run containing all basic cylinders Run ( w ) where w
Let
T
=( S,
) be a transition system. Let
B
Fpath
(i.e.,
is the Borel σ -field generated by open sets in the Cantor topology
on Run ). Then ( Run,
B
B
) is a measurable space, and the elements of
B
are
called Borel sets of runs.
The Borel σ -field
B
contains many interesting elements. For example,
let s, t
S and let Reach ( s, t ) be the set of all runs initiated in s which
visit t . Obviously, Reach ( s, t ) is the union of all basic cylinders Run ( w ) where
w
. Similarly, one can
show that the set of all runs initiated in s that visit t infinitely often is Borel.
Fpath ( s ) and w visits t , and hence Reach ( s, t )
∈B