Problem 666

Polymorphic Bacteria

Members of a species of bacteria occur in two different types: $α$ and $β$ . 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 $α$ will, independently, do one of the following (at random with equal probability):
- clone itself, resulting in a new bacterium of type $α$ (alongside $A$ who remains)
- split into $3$ new bacteria of type $β$ (replacing $A$ )
Each individual $B$ of type $β$ will, independently, do one of the following (at random with equal probability):
- spawn a new bacterium of type $α$ (alongside $B$ who remains)
- die

If a population starts with a single bacterium of type $α$ , 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 $α_{i}$ for $0 \leq i < k$ . The rules governing this species’ lifecycle involve the sequence $r_{n}$ defined by:
$r_{0} = 306$
$r_{n + 1} = r_{n}^{2} mod 10 007$

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

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

In fact, our original species was none other than $S_{2, 2}$ , with $α = α_{0}$ and $β = α_{1}$ .

Let $P_{k, m}$ be the probability that a population of species $S_{k, m}$ , starting with a single bacterium of type $α_{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.

多态细菌

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

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

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

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

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

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

事实上，我们最初考虑的那种细菌可以被表示为 $S_{2, 2}$ ，其中 $α = α_{0}$ 而 $β = α_{1}$ 。

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

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