Carstens C J
School of Mathematical and Geospatial Sciences, RMIT University, Melbourne, Victoria 3000, Australia.
Phys Rev E Stat Nonlin Soft Matter Phys. 2015 Apr;91(4):042812. doi: 10.1103/PhysRevE.91.042812. Epub 2015 Apr 29.
Randomization of binary matrices has become one of the most important quantitative tools in modern computational biology. The equivalent problem of generating random directed networks with fixed degree sequences has also attracted a lot of attention. However, it is very challenging to generate truly unbiased random matrices with fixed row and column sums. Strona et al. [Nat. Commun. 5, 4114 (2014)] introduce the innovative Curveball algorithm and give numerical support for the proposition that it generates truly random matrices. In this paper, we present a rigorous proof of convergence to the uniform distribution. Furthermore, we show the Curveball algorithm must include certain failed trades to ensure uniform sampling.
二元矩阵的随机化已成为现代计算生物学中最重要的定量工具之一。生成具有固定度序列的随机有向网络的等效问题也引起了广泛关注。然而，生成具有固定行和列和的真正无偏随机矩阵极具挑战性。斯特罗纳等人[《自然·通讯》5, 4114 (2014)]介绍了创新的Curveball算法，并为其生成真正随机矩阵的命题提供了数值支持。在本文中，我们给出了收敛到均匀分布的严格证明。此外，我们表明Curveball算法必须包含某些失败交易以确保均匀采样。
