0%

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

$r_0 = 306$
$r_{n+1} = r_n^2 \bmod 10,007$

• 如果$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$）。