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

runs that start with
w
, respectively. When

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

Search Nedrilad ::

Custom Search