生成随机列联表的有效方法？

Question

生成随机列联表的有效方法是什么？列联表被定义为矩形矩阵，使得每行的和是固定的，并且每列的和是固定的，但只要每行和列的和是正确的，单个元素就可以是任何元素。

请注意，生成随机列联表非常容易，但我正在寻找比朴素算法更有效的算法。

Answer 1

查看R的networksis包的代码可能会有所帮助。我相信高效的计算需要花哨的Markov Chain sequential importance resampling技术，所以如果可以避免的话，您可能希望避免重新实现它。

编辑:相关论文为Chen, Diaconis, Holmes, and Liu (2005)。用作者的话说，“我们的方法与其他现有的基于蒙特卡洛的算法相比是有利的，有时比其他算法更有效几个数量级。”

Answer 2

对我来说，这听起来像是constraint satisfaction problem。

基本上，您可以从某个点开始，从一组允许的值中随机选择一个单元格的值。然后，为同一行/列中的所有单元格更新合格值集，并选择下一个单元格(根据您正在使用的CSP启发式)，以(随机)从其合格值集中为其分配一个值。同样，您还必须更新同一行/列中所有单元格的合格值集。如果您遇到一个单元格，其中包含一组空的合格值，则必须进行回溯。

但是，“合格值集”的概念可能很难在数据结构中表示，这取决于您允许的值范围。

Answer 3

这个问题的一种解决方案是用R实现的算法AS159。这是论文

Patefield，W. M. (1981) Algorithm AS159。一种生成给定行和列合计的r x c表的有效方法。应用统计学30，91-97。

你可以按照这个link来实现算法。如果您习惯于使用R，则可以简单地使用它的r2dtable函数。

该算法可用于生成R的chisq.test函数中卡方检验的蒙特卡罗p值。请注意，chisq.test不调用r2dtable，而是AS159算法的直接C版本。