An Extension of the Nested Partitions Method
EBERT BREA
vector,
in

this

case,

π vector.
Proposition 6
Suppose

that

Conditions

2

and

3

hold,
and
let

π(0)

=

Pr{D(0)

=

0}−

be

the

probability

that

the
MINPMC
visits

the

state

D(0)

=

d(0)˜

,

which

of

course
always
occurs

by

the

starting

of

the

MINP

method;

or

by
backtracking
operations,

which

can

be

eventually

carried
out
by

the

algorithm.

Then
π()
=



π(0),
if
∈−

{0,1};
π(0)
Q1
j=1
p
(j,j+1)
j
, if
∈−

{2,...,k}ˆ

,
(32)
where:
π(0)
=
1
2+
Pkˆ
=2
Q1
j=1
p
(j,j+1)
j
;
(33)
and
p

(j,j+1)
j
is

given

by

(22).
Proof. By
induction,

we

have
π()
=

π(0)
Y1
j=0
p
(j,j+1)
j
,∈−N+.
(34)
We
besides

know,
Xkˆ
=0
π()
=

1.
(35)
Substituting
(34)

in

(35),

and

knowing

that

p
because
(0,1)
0
=
1
of

(22),

we

therefore

deduce
2π(0)
+
Xkˆ
=2
π(0)
Y1
j=1
p
(j,j+1)
j
=
1.
(36)
Solving
(36)

for

π(0),

we

effortlessly

obtain
π(0)
=
1
2+
Pkˆ
=2
Q1
j=1
p
(j,j+1)
j
.
(37)
Knowing
that

p

(j,j+1)
j
is

estimated

by

Proposition

5,

and
using
both

(34)

and

(37)

the

proof

is

completed.
For
almost

ending

this

analysis,

we

apply

the

above
results
and

(30)

together

for

getting

our

mathematical
expression
of

the

probability

distribution

function

of

the
MINPMC
states,

yielding
π(k)
=
X1
=0
π(0)
δ[k ]

+
Xkˆ
=2
π(0)
Y1
j=1
p
(j,j+1)
j
δ[k ],
k ∈−Z.
(38)
The
results

heretofore

obtained

allow

us

to

describe
the
behavior

of

the

MINP

method,

which

is

a

nonho-
mogeneous
Markov

chain

with

a

conditional

geometric
distribution
of

states

given

by

(38).
Finally,
we

shall

make

the

follows

statements

for

justi-
fying
our

approach:

By

Proposition

4

and

taking

into
account
that

σ(k)

⊆−σ(k),˜

we

can

assert

that

for

each
k ∈−N,
Vσ(k)]

≥−V[σ(k)],

and

besides,

by

(21)

we
have
that

Vσ(k)]

≥−Vσ(k +1)],

what

would

allow

us

to
say
as

a

reasonable

conjecture,

that

the

MINP

method
concentrates
its

finding

better

promising

regions

during
the
progress

of

its

iterative

process,

due

to

the

fact

of

the
continuous
process

of

reduction

of

the

baggy

hull

of

the
identified
promising

region.
vi.
OPERATING THE MINP METHOD
In
this

section,

we

shall

show

a

main

software

that
will
operate

the

MINP

method

for

taking

the

collec-
tion
of

the

performance

measurements:

η()(p,n,m);
λ()(p,n,m);
and

q()(p,n,m)

from

each

th

indepen-
dent
replication

of

the

MINP

method

is

depicted

in

Figure
10.
As
is

shown

in

Figure

10

on

page

129,

the

MINP

method
is
called

for

being

r-times

executed

with

different

random
seed
each,

thus

achieving

r

independent

runs

for

taking
i.d.d.
unknown

function

empirical

distribution

of

the
performance
measurements,

when

it

is

used

for

globally
solving
Problem

1.
Revista
TEKHNÉ

No

25.1
Semestre
octubre-febrero

2022
ISSN
electrónico:

2790-5195
ISSN:
1316-3930
128