Information Technology Reference
In-Depth Information
Assumption 2.
In figuring out the size
, the number of constraints
(DMDP) is independent with the depth parameter
h
(in the definition of
DMDP) when a suitable range for
h
is taken into consideration.
|
S
(
m, t
)
|
Following Assumption 2,
p
(
m, t
) is a product of probabilities of individual events
related to the depth parameter
h
of a given MDT. Note that the RHS of (4) is
the product of
q
(
m, t, h
)'s in the range of
h
from 1 to
t
.Thevalue
q
(
m, t, h
)
will be identified with the probability that an arbitrarily selected symbol at
position
t
satisfies DMDP of level
h
deep of the entries of the MDT constructed
so far. This quantity is still too complicated to calculate exactly, and we need
the following third assumption:
2
Assumption 3.
The probability
q
(
m, t, h
) can be approximated as the condi-
tional probability that an arbitrarily selected symbol at position
t
satisfies
DMDP of level
h
deep with regard to the entries of the MDT constructed so
far, given the condition that it satisfies all the DMDP of level
k<h
deep.
Under Assumption 3, the value
q
(
m, t, h
) can be approximated as the conditional
probability that there is no
j
such that
h<j<t
and
f
(
t
)
− f
(
t − h
)=
f
(
j
)
−
f
(
j
−
h
)(mod
m
), given the condition that, for each and every
k
with
1
k
)
(mod
m
). To find this conditional probability and show that it is given as in RHS
of (5), we claim that the complementary event has an approximated probability
≤
k<h
, there is no
j
such that
k<j<t
and
f
(
t
)
−
f
(
t
−
k
)=
f
(
j
)
−
f
(
j
−
(
t
−
2
h
)
m
1
−
q
(
m, t, h
)
≈
h
+1)
·
h
+1)
.
(7)
(
m
−
(
m
−
We may easily determine an upper and lower bound on 1
q
(
m, t, h
)whichis
the fraction of symbols that violates DMDP. Recall that the current position is
t
, and we are given a sequence of length
t
−
−
1 and the corresponding MDT of
depth
t
(
h
+ 1) symbols which violate DMDP for fixed
h
.Itis
just the number of entries of MDT at level
h
deep. Thus, at most
−
2. There are
t
−
t
−
(
h
+1)
m
of
A
m
t−
(
h
+1)
m
will be BAD for
f
(
t
)fromrow
h
of MDT, and hence,
is an upper bound
on 1
q
(
m, t, h
). When we use Fact 1 and Assumption 3, we see that there are
at least
−
t−
(
h
+1)
−
(
h−
1)
m−
t−
2
h
m−h
+1
1
symbols (shaded area of the row
h
in Fig. 1, for example, and using Fact 1) have
already been taken care of with regard to the DMDP of level
k<h
deep. Thus,
t−
2
h
m−h
+1
=
of
A
m
, which will be BAD for
f
(
t
), since
h
−
(
h−
1)
is a lower bound on 1
−
q
(
m, t, h
). Therefore, we have
t
−
2
h
t
−
(
h
+1)
m
h
+1
≤
1
−
q
(
m, t, h
)
≤
.
m
−
By carefully examining the situation further, we have chosen a factor as shown
in (7) and obtained the result given in (5).
In order to check the validity of the estimated number
N
(
m, n
)of
m
n
modular sonar sequences, we have done a second round search for the values
N
(
m, n
)for
m
up to 14 and
n
up to
m
+ 1. These are shown in Table 2 with the
calculated number from (5). Further, this relation is plotted in Fig. 2.
×
