Journal article:
Samuel R. Buss and Peter Clote
"Solving the Fisher-Wright and coalescence problems with a
discrete Markov chain analysis"
Advances in Probability Theory 36, 4 (2004)
1175–1197.
Download: postscript or PDF.
We develop a new, self-contained proof,
based on a discrete Markov chain analysis, that the expected number of
generations required for gene allele fixation or extinction in a population of
size n is O(n) under the assumption of neutral selection. Such problems,
collectively known as the Fisher-Wright problem, had previously been shown to
have expected linear time solutions; previous proofs were technically quite
difficult and based on an approximation of the discrete Fisher-Wright problem
by a continuous model involving the diffusion equation
(Fisher~\cite{fisher:1930}, Wright~\cite{wright:1945,wright:1949},
Kimura~\cite{kimura:1955,kimura:1962,kimura:1964},
Watterson~\cite{watterson:1962}, Ewens~\cite{ewens:1963}). In contrast, our new
proof is direct, self-contained, and relies on a discrete Markov chain
analysis. We further develop an algorithm to compute the expected
fixation/extinction time to any desired precision.
Our proofs establish O(nH(p)) as the expected time for
gene allele fixation or extinction for the Fisher-Wright problem where the gene
occurs with frequency p and H(p) is the entropy function. We introduce a weaker
hypothesis on the standard deviation and prove an expected time of O(n\cdot
\sqrt{p(1-p)}) for fixation or extinction under this weaker hypothesis. Thus,
the expected time bound of O(n) for fixation or extinction holds in a wider
range of situations than have been considered previously.
Additionally, we study the coalescence problem and prove
that the expected time for allele fixation or extinction in a population of
size n with n distinct alleles is O(n). Similar bounds are
well-known from coalescent theory for the Fisher-Wright model; however, our
results apply to a broader range of reproduction models that satisfy our mean
condition and weak variation condition.