We develop a new, self-contained proof that the expected number of generations required for gene allele fixation or extinction in a population of size n is O(n) under general assumptions. The proof relies on a discrete Markov chain analysis. We further dev
Fisher-Wrightandcoalescenceproblems15Proof.(ofProposition8).SupposethatA=(A0,...,An),A=Dalsosatis estheequation(4),hence,A0=0=An,soA0=D0,An=Dn.De neC=(C0,...,Cn)byCi=Ai Di.ItfollowsthatC0=0=Cnandfor0<i<n,
Ci=n
j=0n j=0mi,j·(Aj Dj)=mi,jCj.
Inotherwords,C=MC.Byinductiononk,C=MkC.Bytakingthelimitask→∞,C=M∞C.Then,byLemma11,Cisthezerovector;i.e.,A=D.
Proposition8establishedtheuniquenessofasolutiontoequation(4).Thenextpropositionestablishestheexistenceofasolutionandwillformthebasisofouralgo-rithmforcomputingmeanstoppingtimesforparticularvaluesofn.
De neE(s)=(E0,...,En)bysettingEi=0for0≤i≤n,and
0ifi∈{0,n}(s+1)Ei= 1+ nmE(s)if0<i<n.i,jjj=0(s)(s)(0)(5)
Thisismoresuccinctlyexpressedbylettingones=(0,1,1,...,1,1,0)bethecolumnvectoroflengthn+1,consistingof1’s,withtheexceptionofthe rstandlastcoordi-nates,andde ning
E(0)
E(s+1)==(0,0,...,0,0)ones+ME(s).(6)
Proposition12.IfMsatis esthemeanconditionand0andnaretheonlyabsorbingstates,thenthesequence(E(s))sis,ineachcomponent,nondecreasingandbounded.ThelimitE(∞)satis es(4)andhenceequalsthevectorDofmeanstoppingtimes.Proof.WeproveEi
E0(0)(s+1)(0)≥Ei(1)
(s)(s)foralli,byinductionons.Forthebasecase,(0)(1)=E0(1)=0=En(s+1)
(s)=Eninductivecase,Eihypothesis,Ej EiandEi=0<1=Eifor0<i<n.Forthe n 1(s)(s 1)= Ej),wherebytheinductionj=1mi,j(Ej
(s) Ej(s 1)≥0.Since0≤mi,j≤1,theclaimfollows.≤Lfor0≤i≤nWenowshowtheexistenceofanupperboundLsuchthatEi
ands≥0.ByLemma10,forr= ,thereisan >0,sothat
mi,0+mi,n≥ ,(r)(r)
热门文档