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

多类型Moran过程是一种在连通图$G$上的进化过程，其中每个顶点都有$k$种类型，在每个步骤中，选择一个顶点$v$向其邻居之一复制其类型。选择顶点$v$进行复制的概率与$v$的类型的适应度成比例。迄今为止，文献中几乎仅关注于$2$-type Moran过程，其中每个顶点都是健康的（类型$0$）或突变体（类型$1$），而感兴趣的主要问题是（近似）计算所谓的固定概率，即最终所有顶点都是突变体的概率。

在这项工作中，我们开始研究在一般图上近似计算多类型Moran过程中的固定概率。我们的主要结果是一种固定参数可计算随机近似方案（FPTRAS），用于计算主导突变的固定概率；参数是类型数和它们的适应度。在我们的研究过程中，我们还提供了新的上界，用于预期的吸收时间，即多类型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.
论文链接：http://arxiv.org/pdf/2303.08118v1