Information Technology Reference
In-Depth Information
0
1/9
8/9
0
k=3
˄
˄
1/16
k=4
s
3/4
k=2
15/16
˄
1/4
˄
k=5
0
24/25
1/25
0
Fig. 6.4
Infinitely branching flower. There are two states
s
and
0
. To diverge from
s
with probability
1
−
1
/k
, start at “petal”
k
and take successive
˄
-loops anti-clockwise from there. Yet, although
divergence with arbitrarily high probability is present, complete probability-1 divergence is nowhere
possible. Either infinite states or infinite branching is necessary for this anomaly
Example 6.14
(Revisiting Example
6.5
) The pLTS in Example
6.5
is an infinite
state system over states
s
k
for all
k
2, where the probability of convergence is 1
/k
from any state
s
k
, thus a situation where distillation of divergence fails because all
the states partially diverge, yet there is no single state that wholly diverges.
≥
Example 6.15
Consider the finite state but infinitely branching pLTS described in
Fig.
6.4
; this consists of two states
s
and
0
together with a
k
-indexed set of transitions
˄
−ₒ
k
([[
0
]]
1
/k
2
s
↕
s
)
for
k
≥
2,
(6.20)
This pLTS is obtained from the infinite state pLTS described in Example
6.5
by
identifying all of the states
s
i
and replacing the state
a.
0
with
0
.
Search WWH ::
Custom Search