标题： 在每反应的次常数时间内精确模拟随机化学反应网络 显示英文标题

标题： Exactly simulating stochastic chemical reaction networks in sub-constant time per reaction

摘要： 化学反应网络的模型是自然科学中最古老且研究最广泛和应用最广泛的模型之一。 该模型描述了抽象化学物种之间的反应，例如$A + B \to C$，这表示如果类型为$A$的分子与类型为$B$的分子（反应物）相互作用，它们可能会结合形成类型为$C$的分子（产物）。 模拟（离散、随机）化学反应网络的标准算法是 Gillespie 算法 [JPC 1977]，它一次随机模拟一个反应，因此要模拟$\ell$个连续的反应，需要总运行时间$\Omega(\ell)$。 我们给出了第一个化学反应网络随机模拟算法，可以模拟$\ell$反应，可证明地保持精确的随机动力学（从与Gillespie算法完全相同的分布中采样），同时使用的时间可证明地在$\ell$上是次线性的。 在合理的假设下，当$\ell \ge n^{5/4}$时，我们的算法可以在时间$O(\ell/\sqrt n)$内模拟$\ell$种反应，涉及$n$个总分子，当$n \le \ell \le n^{5/4}$时，可以在时间$O(\ell/n^{2/5})$内完成。 我们的工作适应了Berenbrink、Hammer、Kaaser、Meyer、Penschuck和Tran [ESA 2020]的算法，用于模拟称为群体协议的分布式计算模型，并以一种非常非平凡的方式将其扩展到更一般的化学反应网络设置中。 我们提供了一个Python包作为我们算法的实现，核心逻辑用Rust编写，在实践中表现出惊人的快速性能。 显示英文摘要

摘要： The model of chemical reaction networks is among the oldest and most widely studied and used in natural science. The model describes reactions among abstract chemical species, for instance $A + B \to C$, which indicates that if a molecule of type $A$ interacts with a molecule of type $B$ (the reactants), they may stick together to form a molecule of type $C$ (the product). The standard algorithm for simulating (discrete, stochastic) chemical reaction networks is the Gillespie algorithm [JPC 1977], which stochastically simulates one reaction at a time, so to simulate $\ell$ consecutive reactions, it requires total running time $\Omega(\ell)$. We give the first chemical reaction network stochastic simulation algorithm that can simulate $\ell$ reactions, provably preserving the exact stochastic dynamics (sampling from precisely the same distribution as the Gillespie algorithm), yet using time provably sublinear in $\ell$. Under reasonable assumptions, our algorithm can simulate $\ell$ reactions among $n$ total molecules in time $O(\ell/\sqrt n)$ when $\ell \ge n^{5/4}$, and in time $O(\ell/n^{2/5})$ when $n \le \ell \le n^{5/4}$. Our work adapts an algorithm of Berenbrink, Hammer, Kaaser, Meyer, Penschuck, and Tran [ESA 2020] for simulating the distributed computing model known as population protocols, extending it (in a very nontrivial way) to the more general chemical reaction network setting. We provide an implementation of our algorithm as a Python package, with the core logic implemented in Rust, with remarkably fast performance in practice.