![](https://csdnimg.cn/release/download_crawler_static/15476267/bg4.jpg)
780 IEEE TRANSACTIONS ON EVOLUTIONARY COMPUTATION, VOL. 19, NO. 6, DECEMBER 2015
where π
φ
t
(y) = π
t
(φ
−1
(y)) =
x∈φ
−1
(y)
π
t
(x),wehave
E[[ τ | ξ
0
∼ π
0
]] ≤ (or ≥)E[[ τ
| ξ
0
∼ π
φ
0
]] + ρ.
For proving the theorem, we define the intermediate Markov
chain ξ
k
for k ∈{0, 1,...}. Denote the one-step transition of
ξ as tr, and the one-step transition of ξ
as tr
, ξ
k
is a Markov
chain that:
1) is initially in the state space X and has the same initial
state distribution as ξ , i.e., π
k
0
= π
0
;
2) uses transition tr at time {0, 1,...,k − 1} if k > 0, i.e.,
it is identical to the chain ξ at the first k steps;
3) switches to the state space Y at time k, which is by
mapping the distribution π
k
of states over X to the
distribution π
φ
k
of states over Y via φ;
4) uses transition tr
from time k, i.e., it then acts like the
chain ξ
from time 0.
For the intermediate Markov chain ξ
k
, its first hitting event
τ
k
is counted as ξ
k
t
∈ X
∗
for t = 0, 1,...,k − 1 and as
ξ
k
t
∈ Y
∗
for t ≥ k. Therefore, the first hitting event of ξ
0
is
thesameasξ
and ξ
∞
is the same as ξ .
Lemma 2: Given two absorbing Markov chains ξ ∈ X and
ξ
∈ Y , and a right-aligned mapping φ : X → Y,letτ and
τ
denote the hitting events of ξ and ξ
, respectively, and let
π
t
denote the distribution of ξ
t
, we have for the hitting events
τ
k
of the intermediate chain ξ
k
with any k ∈{0, 1,...} that
E[[ τ
k
| ξ
k
0
∼ π
0
]] = k −
k−1
t=0
π
t
X
∗
+
x∈X ,y∈Y
π
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
= x
·
E[[ τ
|ξ
0
= y]]
−
x∈X
∗
,y∈Y
π
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
=x
·
E[[ τ
|ξ
0
= y]] .
Proof: Let π
k
denote the distribution of ξ
k
. For the chain
ξ
k
at time k − 1, since it will be mapped into the space Y
from time k via φ, by Lemma 1,wehave
E[[ τ
k
| ξ
k
k−1
∼ π
k
k−1
]] = 1 − π
k
k−1
X
∗
+
x∈X −X
∗
,y∈Y
π
k
k−1
(x)P
ξ
k
k
= y|ξ
k
k−1
= x
E[[ τ
k
|ξ
k
k
= y]] .
The chain ξ
k
at time k − 1 acts like the chain ξ , thus
P(ξ
k
k
= y|ξ
k
k−1
= x) = P(ξ
k
∈ φ
−1
(y)|ξ
k−1
= x). It acts like
the chain ξ
from time k, thus E[[ τ
k
|ξ
k
k
= y]] = E[[ τ
|ξ
0
= y]] .
We, then have
E[[ τ
k
| ξ
k
k−1
∼ π
k
k−1
]] = 1 − π
k
k−1
X
∗
+
x∈X ,y∈Y
π
k
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
= x
E[[ τ
|ξ
0
= y]]
−
x∈X
∗
,y∈Y
π
k
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
=x
E[[ τ
|ξ
0
=y]] .
(2)
Note that the last minus term of (2) is necessary, because
that if ξ
k
k−1
∈ X
∗
the chain should stop running, but the right-
aligned mapping may map states in X
∗
to Y −Y
∗
and continue
running the chain ξ
, which is excluded by the last minus term.
By Lemma 1, we have that
E[[ τ
k
| ξ
k
0
∼ π
k
0
]] = 1 − π
k
0
X
∗
+ E[[ τ
k
| ξ
k
1
∼ π
k
1
]] = ... = (k − 1)
−
k−2
t=0
π
k
t
X
∗
+ E[[ τ
k
| ξ
k
k−1
∼ π
k
k−1
]].
Applying (2) to the last term, results in that
E[[ τ
k
| ξ
k
0
∼ π
k
0
]] = k −
k−1
t=0
π
k
t
X
∗
+
x∈X ,y∈Y
π
k
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
= x
E[[ τ
|ξ
0
= y]]
−
x∈X
∗
,y∈Y
π
k
k−1
(x)P
ξ
k
∈φ
−1
(y)|ξ
k−1
= x
E[[ τ
|ξ
0
=y]] .
For any t < k, since the chain ξ
k
and ξ are identical before
the time k,wehaveπ
k
t
= π
t
, applying which obtains the
lemma.
Proof of Theorem 1 (“≤” case):
Firstly, we prove the “≤” case which requires a right-aligned
mapping.
For any t < k, since the chain ξ
k
and ξ are identical before
the time k,wehaveπ
t
= π
k
t
, and thus
∀t < k : π
k
t
(X
∗
) = π
t
X
∗
≥ π
t
φ
−1
Y
∗
= π
φ
t
Y
∗
(3)
since φ is right-aligned and thus φ
−1
(Y
∗
) ⊆ X
∗
.
We prove the theorem by induction on the k of the
intermediate Markov chain ξ
k
.
1) Initialization is to prove the case k = 0, which is trivial
since ξ
0
= ξ
and thus E[[ τ
0
| ξ
0
0
∼ π
0
]] = E[[ τ
| ξ
0
∼ π
φ
0
]].
2) Inductive hypothesis assumes that for all
k ≤ K − 1 (K ≥ 1)
E[[ τ
k
| ξ
k
0
∼ π
0
]] ≤ E[[ τ
| ξ
0
∼ π
φ
0
]] +
k−1
t=0
ρ
t
we are going to prove
E[[ τ
K
| ξ
K
0
∼ π
0
]] ≤ E[[ τ
| ξ
0
∼ π
φ
0
]] +
K−1
t=0
ρ
t
. (4)
Applying Lemma 2
E[[ τ
K
| ξ
K
0
∼ π
0
]] = K −
K−1
t=0
π
t
X
∗
+
x∈X ,y∈Y
π
K−1
(x) P
ξ
K
∈ φ
−1
(y)|ξ
K−1
= x
E[[ τ
|ξ
0
= y]]
−
x∈X
∗
,y∈Y
π
K−1
(x) P
ξ
K
∈ φ
−1
(y)|ξ
K−1
= x
E[[ τ
|ξ
0
= y]]