Information Technology Reference
In-Depth Information
probability of going from state
i
to the other states. The matrix is called the
transition matrix, denoted by
Π
. The general term of that matrix is defined
as
x
(
k
)=
i
]
using the conditional probability formalism. For instance, the transition ma-
trix of the random walk on the triangle is
Π
ij
=
P
[
x
(
k
+1)=
j
|
⎛
⎝
⎞
⎠
0
.
9
.
1
0
.
10
.
9
0
.
9
.
10
Π
=
.
One can check that the stationary distribution is invariant under the ap-
plication of the transition matrix. Actually, 1 is an eigenvalue of any transition
matrix. It can be shown that the magnitude of any eigenvalue is smaller than
or equal to 1. For instance, in our example, the eigenvalues of the transition
matrix
Π
are (approximately) 1,
−
0
,
5+0
.
6928i and
−
0, 5
−
0, 6928i. The
uniform distribution can readily be checked to be invariant.
⎛
⎞
0
.
9
.
1
0
.
10
.
9
0
.
9
.
10
1
/
3
/
3
/
3
=
1
/
3
/
3
/
3
.
⎝
⎠
The invariant distribution plays the same role as the equilibrium state of
deterministic dynamics. In statistical physics it is termed precisely equilibrium
state (see, for instance, Gibbs state in statistical physics).
Here is another example of dynamics on the triangle that exhibits symme-
try breaking. The evolution function
f
is defined by
f
(
a
)=
a, f
(
b
)=
a, f
(
c
)=
a.
Then, the transition matrix is
⎛
⎝
⎞
⎠
100
0
.
90
.
1
0
.
9
.
10
Π
=
.
and its stationary distribution is (1, 0, 0). In
that case, the equilibrium state is deterministic although the dynamics is
stochastic.
Of course, a state noise can be introduced into the controlled dynamical
system as well. In that case, the transition probability from state
x
(
k
) to state
x
(
k
+ 1) depends on the control
u
(
k
) which is applied at time
k
.
For instance, in the case of the labyrinth that was presented at the begin-
ning of this section,
f
(13
,
N) = 13. If we introduce a uniformly distributed
error probability of 0.1 for the control system, then
f
(13
,
N) is a random
variable that takes the values 13, 12 and 14 with probabilities 0.9, 0.05, 0.05
respectively.
Its spectrum is
{
1
,
0
.
1
}
Search WWH ::
Custom Search