# 多类型Moran过程中优势突变固定概率的参数逼近

The multi-type Moran process is an evolutionary process on a connected graph
$G$ in which each vertex has one of $k$ types and, in each step, a vertex $v$
is chosen to reproduce its type to one of its neighbours. The probability of a
vertex $v$ being chosen for reproduction is proportional to the fitness of the
type of $v$. So far, the literature was almost solely concerned with the
$2$-type Moran process in which each vertex is either healthy (type $0$) or a
mutant (type $1$), and the main problem of interest has been the (approximate)
computation of the so-called fixation probability, i.e., the probability that
eventually all vertices are mutants.
In this work we initiate the study of approximating fixation probabilities in
the multi-type Moran process on general graphs. Our main result is an FPTRAS
(fixed-parameter tractable randomised approximation scheme) for computing the
fixation probability of the dominant mutation; the parameter is the number of
types and their fitnesses. In the course of our studies we also provide novel
upper bounds on the expected absorption time, i.e., the time that it takes the
multi-type Moran process to reach a state in which each vertex has the same
type.