Problem 666

Polymorphic Bacteria

Members of a species of bacteria occur in two different types: $\alpha$ and $\beta$. Individual bacteria are capable of multiplying and mutating between the types according to the following rules:

Every minute, each individual will simultaneously undergo some kind of transformation.
Each individual $A$ of type $\alpha$ will, independently, do one of the following (at random with equal probability):
- clone itself, resulting in a new bacterium of type $\alpha$ (alongside $A$ who remains)
- split into $3$ new bacteria of type $\beta$ (replacing $A$)
Each individual $B$ of type $\beta$ will, independently, do one of the following (at random with equal probability):
- spawn a new bacterium of type $\alpha$ (alongside $B$ who remains)
- die

If a population starts with a single bacterium of type $\alpha$, then it can be shown that there is a $0.07243802$ probability that the population will eventually die out, and a $0.92756198$ probability that the population will last forever. These probabilities are given rounded to $8$ decimal places.

Now consider another species of bacteria, $S_{k,m}$ (where $k$ and $m$ are positive integers), which occurs in $k$ different types $\alpha_i$ for $0\le i< k$. The rules governing this species’ lifecycle involve the sequence $r_n$ defined by:
$r_0 = 306$
$r_{n+1} = r_n^2 \bmod 10\ 007$

Every minute, for each $i$, each bacterium $A$ of type $\alpha_i$ will independently choose an integer $j$ uniformly at random in the range $0\le j<m$. What it then does depends on $q = r_{im+j} \bmod 5$:

If $q=0$, $A$ dies.
If $q=1$, $A$ clones itself, resulting in a new bacterium of type $\alpha_i$ (alongside $A$ who remains).
If $q=2$, $A$ mutates, changing into type $\alpha_{(2i) \bmod k}$.
If $q=3$, $A$ splits into 3 new bacteria of type $\alpha_{(i^2+1) \bmod k}$ (replacing $A$).
If $q=4$, $A$ spawns a new bacterium of type $\alpha_{(i+1) \bmod k}$ (alongside $A$ who remains).

In fact, our original species was none other than $S_{2,2}$, with $\alpha=\alpha_0$ and $\beta=\alpha_1$.

Let $P_{k,m}$ be the probability that a population of species $S_{k,m}$, starting with a single bacterium of type $\alpha_0$, will eventually die out. So $P_{2,2} = 0.07243802$. You are also given that $P_{4,3} = 0.18554021$ and $P_{10,5} = 0.53466253$, all rounded to $8$ decimal places.

Find $P_{500,10}$, and give your answer rounded to $8$ decimal places.

多态细菌

某种细菌有两种表现形态：$\alpha$型和$\beta$型。每个细菌个体都拥有增殖和在两种形态间突变的能力，但这种能力受到以下规则的约束：

每一分钟，每个细菌个体都必定在同一时间进行变形。
每个$\alpha$型细菌个体$A$会随机进行以下两种变形之一，不同个体之间对变形的选择是独立且等概率的：
- 克隆本身从而创造一个新的$\alpha$型细菌（并保留$A$）
- 分裂成$3$个新的$\beta$型细菌（并取代$A$）
每个$\beta$型细菌个体$B$会随机进行以下两种变形之一，不同个体之间对变形的选择是独立且等概率的：
- 生成一个新的$\alpha$型细菌（并保留$B$）
- 死亡

如果一个细胞族群一开始只包含一个$\alpha$型细菌，可以算出，有$0.07243802$的概率这个族群会最终全部死亡，而有$0.92756198$的概率这个族群将永远存续下去，上述概率均保留$8$位小数。

现在考虑另一种细菌$S_{k,m}$（其中$k$和$m$均为正整数），这种细菌有$k$种不同的形态，分别用$\alpha_i$表示，其中$0\le i<k$。这种细菌的生命周期取决于如下定义的序列$r_n$:
$r_0 = 306$
$r_{n+1} = r_n^2 \bmod 10\ 007$

每一分钟，每个$\alpha_i$型的细菌个体$A$会独立地在$0\le j<m$的范围内均匀随机地选择一个整数$j$，并根据$q = r_{im+j} \bmod 5$选择其行动：:

如果$q=0$，则$A$死亡。
如果$q=1$，则$A$克隆本身从而创造一个新的$\alpha_i$型细菌（并保留$A$）。
如果$q=2$，$A$突变成为$\alpha_{(2i) \bmod k}$型细菌。
如果$q=3$，$A$分裂成$3$个新的$\alpha_{(i^2+1) \bmod k}$型细菌（并取代$A$）。
如果$q=4$，$A$生成一个新的$\alpha_{(i+1) \bmod k}$型细菌（并保留$A$）。

事实上，我们最初考虑的那种细菌可以被表示为$S_{2,2}$，其中$\alpha=\alpha_0$而$\beta=\alpha_1$。

考虑一个$S_{k,m}$细胞族群，一开始族群只包含一个$\alpha_0$型细菌，记$P_{k,m}$为该族群最终全部死亡的概率。已知$P_{2,2} = 0.07243802$，$P_{4,3} = 0.18554021$，$P_{10,5} = 0.53466253$，均保留$8$位小数。

求$P_{500,10}$，并将你的答案保留$8$位小数。