Information Technology Reference
In-Depth Information
˄
−ₒ
ʘ
0
, where
ʘ
0
has support
1
2
(i)
s
1
{
s
0
,
s
2
}
and assigns each of them the weight
˄
−ₒ
(ii)
s
1
ʘ
1
, where
ʘ
1
has the support
{
s
3
,
s
4
}
, again diving the mass equally
among them.
So there are many possibilities for
ʔ
2
; Lemma
6.1
shows that in fact
ʔ
2
can be of
the form
p
·
ʘ
0
+
(1
−
p
)
·
ʘ
1
(6.12)
for any choice of
p
[0, 1].
Let us consider one possibility, an extreme one where
p
is cho
se
n to be 0; only
the transition (ii) above is used. Here
ʔ
2
∈
1
2
s
4
, and
ʔ
k
ʵ
whenever
k>
2. A simple
calc
ulation shows that in this case the extreme derivative
generated is
ʘ
1
=
is the subdistribution
=
2
ˉ
1
2
s
3
+
1
2
ˉ.
0
which implies that
1
d
(
T
,
Q
2
).
Another possibility for
ʔ
2
is
ʘ
0
, corresponding to the cho
ic
e of
p
∈
A
=
1
in(
6.12
)
1
2
·
1
2
·
above. Continuing
wit
h this derivation leads to
ʔ
3
being
s
1
+
ˉ.
0
; in other
words,
ʔ
3
1
1
s
1
. Now in the generation of
ʔ
4
from
ʔ
3
once more we have to resolve a transition from the nondeterministic state
s
1
,by
choosing some arbitrary
p
=
2
·
ˉ.
0
and
ʔ
3
=
2
·
∈
[0, 1] in (
6.12
). Suppose that each time this arises, we
systematically choose
p
=
1, that is, we ignore completely the transition (ii) above.
Then it is easy to see that the extreme derivative generated is
1
2
k
·
ʘ
0
=
ˉ.
0,
k
≥
1
which simplifies to the distribution
ˉ.
0
. This in turn means that
ˉ
d
(
T
,
Q
2
).
We have seen two possible derivations of extreme deriv
ati
ves from
s
0
. But there
are many others. In general, whenever
ʔ
k
∈
A
is of the form
q
·
s
1
, we have to resolve the
nondeterminism by choosing a
p
[0, 1] in (
6.12
) above; moreover, each such choice
is independent. However, it will foll
ow
from later results, specifically, Corollary
6.4
,
that every extreme derivative
ʔ
of
s
0
is of the form
∈
ʘ
0
+
q
)
ʘ
1
q
·
(1
−
for some choice of
q
∈
[0, 1]; this is explained in Example
6.11
. Consequently, it
={
qˉ
d
(
T
,
Q
2
)
[
2
,1]
follows that
A
|
q
∈
}
.
ˉ
d
(
T
,
a.
0
)
Since
A
={
}
it follows that
d
(
T
,
a.
0
)
d
(
T
,
Q
2
)
d
(
T
,
Q
2
)
d
(
T
,
a.
0
)
.
A
≤
Ho
A
A
≤
Sm
A
Again it is possible to show that these inequalities result from any test
T
and that
therefore we have
a.
0
pmay
Q
2
Q
2
pmust
a.
0
Search WWH ::
Custom Search