Information Technology Reference
In-Depth Information
performed “independently” with regard to all the possible differences that have
already appeared in MDT. Even if the constraints are not independent, we can
over-estimate the situation and we may assume they are so. Specifically, we are
trying to estimate the number of
m
×
t
modular sonar sequences that can be
constructed from a given
m
×
(
t
−
1) modular sonar sequence by adjoining one
last symbol. It would be equal to the size of the set
S
(
m, t
) of GOOD symbols
for
f
(
t
). Thus, the goal is to estimate or to give some bound on
|
S
(
m, t
)
|
when
we are given an
m
1) modular sonar sequence.
We will make some reasonable assumptions under which we could recursively
estimate the number
N
(
m, t
)of
m
×
(
t
−
×
t
modular sonar sequences as the number
N
(
m, t
.
Obviously, there are
N
(
m,
1) =
m
sequences of size
m
−
1) of
m
×
(
t
−
1) sequences times
|
S
(
m, t
)
|
×
1. For 2
≤
t
≤
m
+1,
we need to estimate the fraction
p
(
m, t
)=
|
S
(
m, t
)
|
/m
. We claim that
2
p
(
m, t
)
≈
q
(
m, t, h
)
,
for 2
≤
t
≤
m
+1
,
(4)
h
=1
where
m
(
t
−
2
h
)
t
q
(
m, t, h
)
≈
1
−
h
+1)
2
,
for 1
≤
h
≤
2
.
(5)
(
m
−
From the value given in (4), we may obtain the following:
N
(
m,
1) =
m,
N
(
m, n
)
≈
N
(
m, n
−
1)
mp
(
m, n
)
n
=
m
n
p
(
m, t
)
,
2
≤
n
≤
m
+1
.
(6)
t
=1
The key to the derivation of (6) is to identify the quantities
p
(
m, t
)and
q
(
m, t, h
)
as certain probabilities of related models which simulate the back-track algo-
rithm of the search. The probability model in reality must consist of a set of
events, each of whose probabilities are heavily inter-dependent with one an-
other. To make things simple, we use three assumptions discussed below so that
the dependence disappears, and the result becomes a simple multiplication of
individual probabilities. In doing so, we will adjust a bit further so that the ap-
proximation becomes reasonably meaningful. The value
p
(
m, t
) will be identified
with the probability that an arbitrarily selected symbol at position
t
satisfies
DMDP with respect to all the previous entries of the MDT constructed so far.
The first assumption is given as follows:
Assumption 1.
For any
m
and
t
,thevalue
p
(
m, t
) remains the same no matter
which
m
×
(
t
−
1) modular sonar sequence might be given.
Taking Assumption 1 into account, we will have a sequence of length
t
with
probability
p
(
m, t
) given ANY sequence of length
t
1. The second assumption
enablesustofactor
p
(
m, t
) as a product of some individual probabilities:
−
