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]]
剩余15页未读，继续阅读
weixin_38661939
- 粉丝: 5
- 资源: 950
我的内容管理
展开
最新资源
- 贵州煤矿矿井水分类与处理策略：悬浮物、酸性与非酸性
- 醛固酮增多症肾上腺静脉采样对比：ACTH后LR-CAV的最优评估
- 开源云连接传感器监控平台：农业土壤湿度远程监测
- 母婴用品企业年度生产计划线性规划优化模型：实证与应用
- 井下智能变电站：Rogowski线圈电流检测系统的研发与性能验证
- 霍州矿区煤巷稳定性分析及支护策略
- ARM嵌入式系统远程软件更新方案：基于TFTP协议
- 煤炭选煤中汞分布规律与洗选脱汞效果
- 提升码垛机器人性能：拉格朗日动力学模型与滑模模糊控制的应用
- 增强现实技术提升学前手写教学：设计与开发案例
- 不规则工作面沉陷三角剖分算法提升与应用
- 卡尔曼滤波在瞬变电磁干扰压制中的应用研究
- 煤矿安全能力研究：理论与系统构建
- LonWorks总线技术在斜巷运输车辆定位与跑车防护中的应用
- 神东煤炭集团高效煤粉锅炉系统：节能环保新实践
- Ti/SnO2+Sb2Ox/PbO2电极分形维数与电催化性能研究
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
