设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投稿
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
PureMathematicsnØêÆ,2021,11(12),2023-2030
PublishedOnlineDecember2021inHans.http://www.hanspub.org/journal/pm
https://doi.org/10.12677/pm.2021.1112226
@ÏÊŽ½n3‘ÅiÄ¥A^
ëëë
®é܌Ƨên†‰ÆïÄ§®
ÂvFϵ2021c117F¶¹^Fϵ2021c128F¶uÙFϵ2021c1215F
Á‡
DiaconisÚFill|^@ÏÊŽ½n,‰ÑZ
+
þ‘Å iÄÂñ²-©Ù„ÝOžÑy
†Ø§©Ø=Åù‡†Ø§…|^MarkovØªÚ@ÏÊŽ½n§•‰ÑZ
+
þ
‘ÅiÄÂñ²-©Ù„ÝO"
'…c
‘Åiħ@ÏÊŽ½n§r²-éó§‘Å››§‘ÅüN
TheApplicationoftheEarlyStopping
TheoreminRandomWalk
PanZhao
InstituteofFundamentalandInterdisciplinarySciences,BeijingUnionUniversity,Beijing
Received:Nov.7
th
,2021;accepted:Dec.8
th
,2021;published:Dec.15
th
,2021
Abstract
Byusingtheearlystoppingtheorem,DiaconisandFillmadeamistakewhendealing
withtheconvergencetostationarityforarandomwalk.Inthepaper,wenotonly
©ÙÚ^:ë.@ÏÊŽ½n3‘ÅiÄ¥A^[J].nØêÆ,2021,11(12):2023-2030.
DOI:10.12677/pm.2021.1112226
ë
correctthemistake,butalsogivethespeedestimationofconvergencetostationarity
fortherandomwalk,byusingtheMarkovinequationandtheearlystoppingtheorem.
Keywords
RandomWalk,TheEarlyStoppingTheorem,StrongStationaryDuality,
StochasticallyDominate,StochasticallyMonotone
Copyright
c
2021byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense (CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.ÚóÚ̇(J
DiaconisÚFill[1]JÑr²-éó(SSD)´ïÄê¼óÂñ„Ý˜‡kåóä.·‚Œ
±ÏL•N´ïÄéóó5Oê¼óÂñ²-©ÙÂñ„Ý.SSD äkéõ-‡A
^,äNŒë•©z[2–5].éuG˜m•lÑ8œ/,DiaconisÚFill[1]‰Ñ˜‡ESSD
ó•{.AO/,ék•SG˜m,DiaconisÚFill3[1]¥‰Ñ˜‡N´¦SSDó
œ/.3dœ/¥,3žm_ê¼ó´‘ÅüNbe,¦‚3Ó˜‡G˜meESSDó.
DiaconisÚFill[6]ò ù«AÏœ/í2Œê,SG˜mZ
+
þlÑžmê¼ó,E
ÙSSDó.¦‚|^@ÏÊŽ½n,ÏLïÄéóóÂ¥ž©Ù5Oê¼óÂñ²-©Ù
Âñ„Ý.Ù¥,¦‚313!‰ÑZ
+
þ‘ÅiÄù‡~f¥,Ñy†Ø,©Ø=Å
ù‡†Ø,…|^MarkovØªÚ@ÏÊŽ½n,•‰Ñ‘ÅiÄÂñ²-©Ù„Ý
O.
-X=(X
n
)
n≥0
•±E={0,1,...}•G˜mlÑžmê¼ó,=£Ý•P,d[7]•,
P´‘ÅüN…=é?¿y∈E,
P
z≥y
P(x,z) 'ux´üN4O.w,,P´‘ÅüN
,dué?¿y∈E,
P
z≤y
P(x,z)'uxüN4~.
©-E= {0,1,...},E
∗
= E∪{∞}.-X= (X
n
)
n≥0
•½Â3Vǘm(Ω,F,P)þlÑ
žmê¼ó,Щ©Ù•π
0
,=£Ý•P.·‚{üP•X∼(π
0
,P).·‚Äk5QãDiaconis
ÚFill[6]¥k'SSDó•359A^5̇(J.
½½½nnn1.[6]XJ-X∼(π
0
,P)•˜‡ØŒ,š±Ï,H{lÑžmê¼ó,²-©Ù•π,
G˜m•E.½ÂPžm_•
←−
P(x,y)=
π(y)
π(x)
P(y,x),-H(x)=
P
y∈E:y≤x
π(y),x∈E
∗
;
g(x)=
π
0
(x)
π(x)
,x∈E.@o,'u'éÝ:Λ(x
∗
,x)=I
(x≤x
∗
)
π(x)
H(x
∗
)
,x
∗
∈E
∗
,x∈E,•3±E
∗
•
DOI:10.12677/pm.2021.11122262024nØêÆ
ë
G˜mSSDóX
∗
∼(π
∗
0
,P
∗
)¿©7‡^‡´±eü‡^‡Óž¤á
(a)
π
0
(x)
π(x)
'uxüN4~;
(b)
←−
P´‘ÅüN.
dž,SSDóX
∗
∼(π
∗
0
,P
∗
)d±e•˜û½:
π
∗
0
(x
∗
) = H(x
∗
)
h
π
0
(x
∗
)
π(x
∗
)
−
π
0
(x
∗
+1)
π(x
∗
+1)
i
,x
∗
∈E,
π
∗
0
(∞) =lim
x→∞
π
0
(x)
π(x)
;
P
∗
(x
∗
,y
∗
) =
H(y
∗
)
H(x
∗
)
h
P
y
∗
(
←−
X
1
≤x
∗
)−P
y
∗
+1
(
←−
X
1
≤x
∗
)
i
,x
∗
∈E
∗
,y
∗
∈E,
P
∗
(x
∗
,∞) =
1
H(x
∗
)
lim
y→∞
P
y
(
←−
X
1
≤x
∗
),x
∗
∈E
∗
.
½ÂC•kπ
n
−πk:= max
A⊂E
|π
n
(A)−π(A)|,Ù¥π
n
´X
n
©Ù.@ÏÊŽ½nŒ
±ÏL©ÛSSDóÂ¥ž©Ù5Oê¼óÂñ²-©ÙÂñ„Ý.DiaconisÚFill[6]
ò§äNA^½n1¥ê¼ó,XeíØ.
íííØØØ1.[6]éu½n1¥ó(X
∗
,X),-T
∗
•X
∗
ÄgÂ¥{x
∗
,x
∗
+1,...}∪{∞}Â¥ž,@
o
kπ
n
−πk≤(1−H(x
∗
))+H(x
∗
)P{T
∗
>n}.
duéóóÂ¥ž©ÙØN´OŽ,DiaconisÚFill[6]‰ÑXe‘ÅŒ'Ún,^§5O
éóóÂ¥ž©Ù.
ÚÚÚnnn1.[6]eP
1
ÚP
2
•½Â3E
∗
þ=£¼ê,KXeü‡^‡d:
(a)é?¿0 ≤x
1
≤x
2
≤∞,y∈E
∗
,k
P
0≤z≤y
P
1
(x
1
,z) ≥
P
0≤z≤y
P
2
(x
2
,z);
(b)®•VÇÿÝπ
(1)
0
Úπ
(2)
0
÷v:é?¿y∈E
∗
,k
P
0≤z≤y
π
(1)
0
(z)≥
P
0≤z≤y
π
(2)
0
(z),@
o•3½Â3ƒÓVǘmþê¼óX
(i)
=(X
(i)
n
)
n≥0
∼(π
(i)
0
,P
i
),i=1,2,¦é?¿
n≥0,kX
(1)
n
≤X
(2)
n
.
^‡(a)½(b)¤áž,¡P
2
‘Å››P
1
,P•P
1
≤P
2
.
ÚÚÚnnn2.[6]-P
1
ÚP
2
•½Â3E
∗
þ=£¼ê,XJ
(a)P
1
½P
2
´‘ÅüN;
(b)é?¿x,y∈E
∗
,k
P
0≤z≤y
P
1
(x,z) ≥
P
0≤z≤y
P
2
(x,z).
DOI:10.12677/pm.2021.11122262025nØêÆ
ë
@o,P
1
≤P
2
.
bü‡ê¼óX
(i)
∼(π
(i)
0
,P
i
),i=1,2,÷vé?¿y∈E
∗
,k
P
0≤z≤y
π
(1)
0
(z)≥
P
0≤z≤y
π
(2)
0
(z),¿…P
1
≤P
2
,@od‘ÅŒ'Ún1,P(T
2
>n)≤P(T
1
>n),n≥0.Ù¥,T
i
•X
(i)
ÄgÂ¥{x,x+1,...}∪{∞}Â¥ž,Ïd,XJŽ|^‘ÅŒ'Ún5OéóóÄ
gÂ¥ž©Ù,'…´Ï阇´u©Ûê¼ó,¦éóó‘Å››§.[6]¥¤Þk'‘
ÅiÄ~f,3Ïéù‡éóó‘Å››ê¼óžÑy†Ø.
[6]¥¤Þ‘ÅiÄ.Xe.
-X∼P•lÑžm{ü‘ÅiÄ,G˜m•E= {0,1,2,···}.-0 <p<1,q:= 1−p,
¿…,é?¿0 <x<∞,k
P(x,x−1) = q,P(x,x) = 0,P(x,x+1) = p;
P(0,0) = q,P(0,1) = p.
(1)
duP(x,x+1)+P(x+1,x) ≤1,Tó´‘ÅüN.´•Tóš±Ï.b0 <p<
1
2
,K
Tó~ˆ,²-©Ù•:π(x) = (1−p/q)(p/q)
x
,x∈E.H(x
∗
) =
P
y≤x
∗
π(y) = 1−(p/q)
x
∗
+1
.
d[6]•,bóXl0Ñu,Kd½n1•,éóó•´l0Ñu)«ó,¿…=£Ý
P
∗
Xe:é?¿0 <x
∗
<∞,k
P
∗
(x
∗
,x
∗
−1) =
H(x
∗
−1)
H(x
∗
)
p,P
∗
(x
∗
,x
∗
)
∗
= 0,P
∗
(x
∗
,x
∗
+1) =
H(x
∗
+1)
H(x
∗
)
q;
P
∗
(0,0) = 0,P
∗
(0,1) =1.
½Â=£ÝP
0
•:é?¿0 <x<∞,k
P
0
(x,x−1) = p,P
0
(x,x) = 0,P
0
(x,x+1) = q;
P
0
(0,0) = 0,P
0
(0,1) = 1.
[6]¥•Ñ:éóó‘Å››±P
0
•=£Ý‘ÅiÄ,´·‚uyù´†Ø.Ï•
P
0
(0,0) ≤P
∗
(1,0),¿Ø÷v‘ÅŒ'Ún1¥(a).
e5,·‚ÄkÏééóó‘Å››‘ÅiÄ,,^[6]¥•{5O¤Ïé‘Å
iÄÄgÂ¥ž©Ù,?O‘ÅiÄÄgÂ¥ž©Ù,l3C¿Âe‰Ñ‘ÅiÄ
Âñ„ÝO.,,·‚•Œ|^MarkovØª5O¤Ïé‘Åi ÄÄgÂ¥ž©Ù,l
|^@ÏÊŽ½n‰Ñ‘ÅiÄÂñ„ÝO,Xe(J.
-0 <<1,p/q:= 1−,dxeL«Œu½ux•ê.·‚̇½nXe.
½½½nnn2.b‘ÅiÄX=£Ý P•(1),¿…0<p≤
1
3
,>0.XJn=d
c

2
e,Ù¥c>1,
@o
kπ
n
−πk≤
1
√
c

1+
1
2
lnc+
√
6

.
DOI:10.12677/pm.2021.11122262026nØêÆ
ë
½½½nnn3.b‘ÅiÄX=£Ý P•(1),¿…0<p<
1
2
,>0.XJn=d
c

2
e,Ù¥c>1,
@o
kπ
n
−πk≤
1
c

√
c+
1
4
(lnc)
2
−
1
2
lnc

.
2.½n2y²
½Â=£ÝP
1
•:é?¿0 <x<∞,k
P
1
(x,x−1) =
1
3
,P
1
(x,x) = 0,P
1
(x,x+1) =
2
3
;
P
1
(0,0) =
1
3
,P
1
(0,1) =
2
3
.
Ï•é?¿x≥0,kP
1
(x,x+1)+P
1
(x+1,x) ≤1,¤±P
1
´‘ÅüN.Ï•0 <p≤
1
3
,¤
± é?¿x,y∈E,k
P
0≤z≤y
P
1
(x,z)≥
P
0≤z≤y
P
∗
(x,z).d‘ÅŒ'Ún2•,P
∗
‘ Å››
P
1
,=P
1
≤P
∗
.
·‚e¡Ï阇•N´©Û{üé¡‘ÅiÄýéŠL§,¦§P
1
››,,ÒŒ
±d[6]¥•{,=|^[8]¥Berry-Esseen ½n,5O§ÄgÂ¥ž©Ù.bÕáÓ©
Ù‘ÅCþS{Y
i
: i≥1}÷v
P{Y
i
= −1}= P{Y
i
= 1}=
1
3
;
P{Y
i
= 0}=
1
3
.
½ÂV
0
:= 0,V
n
:=
P
n
i=1
Y
i
,@o(V
n
)
n≥0
´½Â3Zþ{üé¡‘ÅiÄ,§=£ÝP
v
X
e:é?¿x,y∈Z,k
P
v
(x,x−1) = P
v
(x,x+1)=
1
3
;
P
v
(x,x) =
1
3
.
w,,V
n
Ï"Ú•©O•E(V
n
) = 0,D(V
n
) =
2n
3
.
5¿(|V
n
|)
n≥0
´±E•G˜mlÑžmê¼ó,§=£ÝP
|v|
Xe:é?¿
0 <x<∞,k
P
|v|
(x,x−1) = P
|v|
(x,x+1) =
1
3
,P
|v|
(x,x) =
1
3
,0 <x<∞;
P
|v|
(0,1) =
2
3
,P
|v|
(0,0) =
1
3
.
Ï•P
1
´‘ ÅüN,¿… é?¿x,y∈E,k
P
0≤z≤y
P
|v|
(x,z)≥
P
0≤z≤y
P
1
(x,z).d‘ÅŒ
'Ún2•,P
1
‘Å››P
|v|
,=P
|v|
≤P
1
.qP
1
≤P
∗
,¤±P
|v|
≤P
∗
.-T
∗
,T
|v|
©O•éóó
Ú(|V
n
|)
n≥0
ÄgÂ¥{x
∗
,x
∗
+1,...}Â¥ž,Ké?¿n≥0,kP(T
∗
>n) ≤P(T
|v|
>n).
e5·‚òY[6]¥y²g´,|^@ÏÊŽ½n,‰Ñ‘ÅiÄÂñ²-©Ù„Ý
DOI:10.12677/pm.2021.11122262027nØêÆ
ë
O.Àx
∗
= db/e−1,1−H(x
∗
) ≤e
−b
.
-Z•IO‘ÅCþ,C≤0.7655•[8]¥Û~ê.duD(V
n
)=
2n
3
,
0
:=
P
n
i=1
E|Y
i
|
3
(
√
D(V
n
))
3
=
q
3
2n
,Àn= dc/
2
e,x
∗
= db/e−1,Kd[8]¥Berry-Esseen ½n,k
P(T
∗
>n)≤P(T
|v|
>n) ≤P{|V
n
|<x
∗
}
≤P

|Z|<x
∗
r
3
2n

+2C
0
≤P

|Z|<
b
q
2c
3

+
r
6
c
≤
b+
√
6
√
c
.
Ïd,
kπ
n
−πk≤e
−b
+
b+
√
6
√
c
.
XJc>1,ÏLÀb=
1
2
lnc,·‚
kπ
n
−πk≤
1
√
c

1+
1
2
lnc+
√
6

.
3.½n3y²
½Â=£ÝP
2
•:é?¿0 <x<∞,k
P
2
(x,x−1) = p,P
2
(x,x) = 0,P
2
(x,x+1) = q;
P
2
(0,0) = p,P
1
(0,1) = q.
d½n2y²•,P
2
≤P
∗
.-
e
X=(
e
X
n
)
n≥0
•l0Ñu{üé¡‘ÅiÄ,Ù=£Ý
e
P•:
é?¿0 <x<∞,k
e
P(x,x−1) =
1
2
,
e
P(x,x) = 0,
e
P(x,x+1)=
1
2
;
e
P(0,0) =
1
2
,
e
P(0,1) =
1
2
.
Ï•0<p<
1
2
,¤±é?¿x,y∈E,k
P
0≤z≤y
e
P(x,z)≥
P
0≤z≤y
P
2
(x,z).d ‘ÅŒ'Ún2
•,
e
P≤P
2
.qP
2
≤P
∗
,¤±
e
P≤P
∗
.-T
∗
,
e
T©O•éóóÚ
e
XÄgÂ¥{x
∗
,x
∗
+1,...}Â
¥ž,Ké?¿n≥0,kP(T
∗
>n) ≤P(
e
T>n).dMarkovØª•,P(
e
T>n)≤
E
e
T
n
.e¡·
‚ÏLOŽE
e
T,5OP(T
∗
>n).
w,,
e
P´ØŒ,š±Ï.d[7],½Â
e
P(i,j) :=ep
ij
,ep
(k)
n
:=
P
k
j=0
ep
nj
Ú
e
F
(i)
i
:= 1,
e
F
(i)
n
:=
1
ep
n,n+1
n−1
X
k=i
ep
(k)
n
e
F
(i)
k
,n>i≥0.
DOI:10.12677/pm.2021.11122262028nØêÆ
ë
d[[7],½n2]•,
e
P´~ˆ…=
P
∞
n=0
e
F
(0)
n
=∞.N´¦,é?¿n≥0,k
e
F
(0)
n
=
1,
P
∞
n=0
e
F
(0)
n
= ∞.Ïd,
e
P´~ˆ.Ï•
e
PØŒ,š±Ï,~ˆ,d[[7],½n5]•,
E
0
eσ
x
∗
=
x
∗
−1
X
k=0
ev
k
.
Ù¥,ev
k
=
P
k
j=0
e
F
(j)
k
ep
j,j+1
,eσ
x
∗
= inf{n≥1 :
e
X
n
= x
∗
}.
5¿
e
T=eσ
x
∗
,ÏdE
e
T= E eσ
x
∗
.Ï•
e
F
(i)
i
= 1,¤±,
e
F
(i)
i+1
=
1
ep
i+1,i+2
i
X
k=i
ep
(k)
i+1
e
F
(i)
k
=
1
ep
i+1,i+2
ep
i+1,i
e
F
(i)
i
= 1.
Ón,Œ¦:
e
F
(i)
i+2
= 1.Ïd,8BŒ,
e
F
(i)
n
= 1,1 ≤i≤n.
E
0
eσ
x
∗
=
x
∗
−1
X
k=0
ev
k
=
x
∗
−1
X
k=0
k
X
j=0
e
F
(j)
k
ep
j,j+1
=
x
∗
−1
X
k=0
2(k+1) = (x
∗
)
2
+x
∗
.
Ïd,E
0
e
T= E
0
eσ
x
∗
= (x
∗
)
2
+x
∗
.Àx
∗
= db/e−1,1−H(x
∗
) ≤e
−b
.Àn= dc/
2
e,k
kπ
n
−πk≤1−H(x
∗
)+H(x
∗
)P
0
(T
∗
>n)
≤e
−b
+
E
0
e
T
n
≤e
−b
+
(x
∗
)
2
+x
∗
n
=e
−b
+
(d
b

e)
2
−d
b

e
d
c

2
e
≤e
−b
+
b
2
+b
c
.
XJc>1,ÏLÀb=
1
2
lnc,·‚
kπ
n
−πk≤
1
c

√
c+
1
4
(lnc)
2
−
1
2
lnc

.
Ä7‘8
®½g,‰ÆÄ7]Ï‘8(1194022),®éÜŒÆ<âr`ÀOy(BPHR2020EZ01)Ú
ZB10202001.
ë•©z
[1]Diaconis,P.andFill,J.A.(1990)StrongStationaryTimesviaaNewFormofDuality.The
AnnalsofProbability,18,1483-1522.https://doi.org/10.1214/aop/1176990628
DOI:10.12677/pm.2021.11122262029nØêÆ
ë
[2]Diaconis, P. andMiclo, L. (2009)On Timesto Quasi-Stationarity for Birthand DeathProcess-
es. JournalofTheoreticalProbability, 22, 558-586. https://doi.org/10.1007/s10959-009-0234-6
[3]Diaconis,P. andSaloff-Coste,L.(2006) SeparationCut-Offs forBirthandDeath Chains.The
AnnalsofAppliedProbability,16,2098-2122.https://doi.org/10.1214/105051606000000501
[4]Fill, J.A. (2009)The Passage Time Distribution for a Birth-and-DeathChain:Strong Station-
aryDualityGivesaFirstStochasticProof.JournalofTheoreticalProbability,22,543-557.
https://doi.org/10.1007/s10959-009-0235-5
[5]Fill,J.A.andKahn,J.(2013)ComparisonInequalitiesandFastest-MixingMarkovChains.
TheAnnalsofAppliedProbability,23,1778-1816.https://doi.org/10.1214/12-AAP886
[6]Diaconis,P.andFill,J.A.(1990)ExamplesfortheTheoryofStrongStationaryDualitywith
Countable StateSpaces. ProbabilityintheEngineeringandInformationalSciences, 4, 157-180.
https://doi.org/10.1017/S0269964800001522
[7]x¬¬,oÜ,Ü{Ÿ,ë.lÑžmü)L§OOK[J].®“‰ŒÆÆ(g ,‰Æ
‡),2015,51(3):227-235.
[8]Shiganov,I.S.(1986)RefinementoftheUpperBoundoftheConstantintheCentralLimit
Theorem.JournalofSovietMathematics, 35, 2545-2550.https://doi.org/10.1007/BF01121471
DOI:10.12677/pm.2021.11122262030nØêÆ

版权所有：汉斯出版社 (Hans Publishers) Copyright © 2021 Hans Publishers Inc. All rights reserved.