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-Wrightandcoalescenceproblems13timethatareneededlaterfortheproofsofthestoppingtimetheorems.
Onemightthinktotryrunningrandomtrialstotrytodeterminestoppingtimesexperimentally.Thisturnsouttobedi cultsincethestoppingtimeshaveafairlylargestandarddeviationandalargenumberoftrialsareneededtoaccuratelymeasurethestoppingtime.Instead,wedescribeaniterativealgorithmthatconvergestothevaluesDi,thestoppingtimesforapopulationofsizenthatstartswithiindividualswithalleleAandtherestwitha.
LetMkbethek-thpoweroftheMarkovchainmatrixM.TheentriesofMkaredenotedbymi,jandaretransitionprobabilitiesfork-generationsteps.WeletM∞
k∞equalthelimitofMkask→∞;itsentriesarem∞arei,j=limkmi,j.MandM(k)(k)
alsostochasticmatrices.Astatei0∈Qissaidtobeabsorbingifmi0,i0=1.Statejissaidtobeaccessiblefromstatei,orequivalentlyicanreachj,ifthereexiststforwhichmi,j>0.Themeanconditionand(weak)variationconditionimplythat0andnaretheonlyabsorbingstates.
ItiscommontoanalyzeMarkovchainsusingeigenvaluesandeigenvectorsofthetransitionmatrixM.Indeed,thishasbeendonebyFeller[8]forthebinomialproba-bilitiesandbyCannings[3]formoregeneraltransitionmatricesundertheassumptionofexchangeability.Wewillnotuseeigenvectorsoreigenvalueshowever.
ForaMarkovchainMwithstatesetQ={0,...,n},de nethemeanstoppingtimevectorD=(D0,...,Dn)sothatDiistheexpectednumberoftransitionsbeforeM,startinginstatei,entersanabsorbingstate.Since0andnwillbetheonlyabsorbingstates,D0=0=Dn.Fromstatei,inonesteptheMarkovchainmakesatransitiontostatejwithprobabilitymi,j,hence 0Di= 1+ nmDi,jjj=0(t)ifi∈{0,n}if0<i<n.(4)Proposition8.IfM=(mi,j)satis esthemeanconditionand0andnaretheonlyabsorbingstates,thenthereisatmostonevectorDwhichsatis es(4).
BeforeprovingProposition8,weestablishthefollowingthreelemmas.(ResultssimilartoLemmas9and10canbefoundinM¨ohle[19].)
Lemma9.SupposethatMsatis esthemeanconditionandthat0andnaretheonlyabsorbingstates.
热门文档