Information Technology Reference
In-Depth Information
T
1
(
X
)
holds.
We aim to deduce that
T
1
(
X
)
=
w
j
∈
LHS of
τ
1
j
w
j
−
τ
2
j
w
j
X
w
j
∈
X
(
w
j
∈X
1
τ
2
j
w
j
+
w
j
∈X\X
1
≥
τ
1
j
w
j
−
τ
2
j
w
j
)
w
j
∈X
1
≥
τ
1
j
w
j
−
τ
2
j
w
j
−
w
j
since
τ
2
j
≤
1
w
j
∈
X
1
w
j
∈
X
1
w
j
∈X\X
1
>
w
j
∈W\X
w
j
(by Inequality 1). This is the RHS of
T
1
(
X
)
,so
T
1
(
X
)
holds.
Hence the algorithm returns
O
1
in no more than
n
steps (by discovering the status
of some or all elements of
A
) if and only if
T
1
(
X
)
holds. Similarly for
O
2
. Hence
the probability
P
(
X
)
is independent of the order in which the elements of
X
are
considered.
Lemma 2:
Let
X,Y
be
n
-element subsets of
W
which differ only in one element:
X
=
(
X ∩Y
)
∪{w
x
}
and
Y
=
(
X ∩Y
)
∪{w
y
}
with
w
x
>w
y
.Then
P
(
X
)
≥ P
(
Y
)
where
P
(
X
)
,P
(
Y
)
are as defined in Lemma 1.
Proof of Lemma 2:
Let
X
=
where
w
x
>
w
y
. By Lemma 1,
P
(
X
)
and
P
(
Y
)
are well defined. We write
TT,TF,FT,FF
for
the 4 possible values of
{
w
1
, ...w
n−
1
,w
x
}
,
Y
=
{
w
1
, ...w
n−
1
,w
y
}
. For each set
X,Y
,thereare
4
n
possible such as-
signments of truth values, all equally likely by our hypothesis. For example, when
n
=
3, one assignment is
τ
1
j
,τ
2
j
, indicating the first and third attributes are true for
both
O
1
and
O
2
, but the second is true only for
O
2
. If the algorithm terminates for
r
out
of the
4
n
assignments, the probability of termination in at most
n
steps is
r/
4
n
.
Suppose
TT,FT,TT
T
1
(
Y
)
holds for a particular assignment: we will show that it follows that
T
1
(
X
)
holds for that assignment.
τ
2
j
w
j
=
w
j
∈
τ
1
j
w
j
−
(
τ
1
j
−
τ
2
j
)
w
j
+(
τ
1
j
−
τ
2
j
)(
w
x
−
w
y
)
w
j
∈
X
w
j
∈
X
Y
≥
(
τ
1
j
−
τ
2
j
)
w
j
−
(
w
x
−
w
y
)
since
τ
1
j
−
τ
2
j
∈{−
1
,
0
,
1
}
and
w
x
>w
y
.
w
j
∈Y
⎛
⎞
T
1
(
Y
)
=
w
j
∈W\X
⎝
⎠
−
>
w
j
(
w
x
+
w
y
)
by
w
j
so that
T
1
(
X
)
holds.
w
j
∈W\Y
Hence the number
r
X
of assignments for which the algorithm terminates in not more
than
n
steps is at least
r
Y
.
P
(
X
)=
r
X
/
4
n
and
P
(
Y
)=
r
Y
/
4
n
so that
P
(
X
)
≥
P
(
Y
)
as required.
.
Proof of Theorem 1:
Suppose there exists a strategy
R
better than
S
. Then there exists
n
∈
N
such that
R
is more likely to terminate in at most
n
steps than
S
.
Let
X
S
=
{
w
1
,w
2
, ..., w
n
}
, be the set of the largest
n
weights and let
X
R
be the set
of
n
weights used by
R
.
