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
12S.BussandP.CloteberequiredthatP(π f)=P(f)=P(f π)forallf:[n]→[n]andallone-to-oneπ:[n]→[n].
Thebinomialprocesscanbede nedasaMarkovprocesscontrolledbyfunctionprobabilitiesbylettingP(f)beequalto1/nn,i.e.,eachfunctionisequallylikely.Thehypergeometricprocesscanlikewisebede nedascontrolledbyfunctionprobabilities:namely,tochoosearandomf,chooseuniformlyatrandomaone-to-onefunctionm:
[n]→[2n],andthenchoosefsothatf(x)= m(x)/2 .Inthehypergeometriccase,thefunctionsfdonotallhaveequalprobabilities.
Theorem7.Letamulti-alleleMarkovprocessbecontrolledbyfunctionprobabilitiesandsatisfythemulti-allelemeanandweakvariationconditions.ThentheexpectedcoalescencetimeisO(n).
Proof.ThisisanimmediatecorollaryofTheorem6.Notethattheevolutionthroughaseriesofkgenerationscanberepresentedbyasequenceofkfunctions,f1,...,fk.TheprobabilityofthisevolutionarysequenceistheproductΠiP(fi).ByTheorem6,theexpectedvalueofksuchthatf1,...,fkcausescoalescenceisO(n).
ThefunctionprobabilitymodelforMarkovprocessesisquitegeneral;forinstance,itincludestheexamplesofprocessesforwhichM¨ohle[20,§5]hasprovedcoalescencetheorems(withtheexceptionofthemore-slowlyevolvingMoranmodel).However,asformulatedabove,thefunctionprobabilitymodelappliesmainlytomartingales,espe-ciallyifthefunctionsarerequiredtobeinvariantunderpermutationsoftherangeanddomain.Thisissomewhatunexpectedsince,ifthemeanconditionholds,thefailureofthemartingalepropertywouldbeexpectedtoonlydecreasethemeanstoppingtime.Itwouldbeworthwhiletohavemoregeneraltechniquesforformulatingthetime-reversalofanevolutionaryprocess.
Themethodofduality,usedbyM¨ohle[19],isanothertechniqueforrelatingforwardandbackwardevolutionaryprocesses.
4.Calculatingstoppingtimes
WenowdiscussanalgorithmtocalculatetheexactstoppingtimesforaMarkovchainforparticularvaluesofn.Inaddition,wedevelopsomepropertiesofthestopping
热门文档