Information Technology Reference
In-Depth Information
Runs of zeros and ones alternate, and we can assume with no loss of generality
that the sequence starts and ends with 1, so we also have
R
1
+
R
2
=1+
R
1
+
R
2
,
(7)
and combining these we obtain
v
=2(
R
1
+
R
2
)+
R
2
+
R
2
−
1
.
(8)
Now
μ
1
=
R
1
+
R
2
since this is the number of runs of ones. Furthermore, the
distance 2 will fail to be realized at
b
i
= 1 if and only if this is immediately
followed by a zero-run of length one; thus from (7) we have
μ
2
=
R
1
+2
R
2
−
R
1
=1+
R
2
+
R
2
,
(9)
therefore
v
=2
μ
1
+
μ
2
−
2
(10)
and the theorem follows.
In fact, the same bound applies to any collection of sets, without the sliding-
window assumption:
Theorem 2.
For any collection of sets
S
with memory bound
v
,
v
+2
3
μ
(
S
)
≤
.
(11)
Proof.
Let
b
i
be the binary sequence corresponding to the set
S
i
, i.e.
b
t
=1if
and only if
i
S
i
+
v−
1
. These are the
only sets which can contain
i
; thus for any distance
d
,atleast
μ
(
S
) of these sets
contain
i
but not
i
+
d
. Thus the sequences
b
i
−
t
∈
S
i
.Consider
v
consecutive sets
S
i
,
···
b
i
+
v−
1
together contain at least
μ
(
S
) realizations of
d
, where in sequence
b
i
+
t
we only count a realization at bit
position
t
.
Similarly, the sequences
b
i
+1
···
b
i
+
v
···
contain at least
μ
(
S
)
different
realiza-
b
i
+
v
+
L−
2
contain
qL
different realizations of
d
.Thusas
L
approaches infinity, the average value of
μ
b
j
(
d
)for
i
1 sequences
b
i
tions of
d
and so, for any
L
,the
v
+
L
−
···
2 approaches (at least)
μ
(
S
). In particular this
holds for
d
=1
,
2. Now from the proof of Theorem 1, we know that
≤
j
≤
i
+
v
+
L
−
2
μ
b
j
(1) +
μ
b
j
(2)
≤
v
+2
for each sequence
b
j
, thus the same must be true of the averages, i.e.
3
μ
(
S
)
≤
v
+2
.
It is not known whether the strength of an arbitrary collection of sets can exceed
the maximum strength achievable by a sliding window. The proof of Theorem 2
shows that if this is the case, we must have a collection of sliding windows in
which the average value of each
μ
d
exceeds the maximum strength of any single
sliding window.
We also have the following relationship among different distances:
