6

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

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

4

4 回答 4

6

查看 R 的networksis包的代码可能会有所帮助。我相信高效的计算需要花哨的马尔可夫链顺序重要性重采样技术，因此如果可以避免，您可能希望避免重新实现它。

编辑：相关论文是Chen, Diaconis, Holmes, and Liu (2005)。用作者的话来说，“[o]ur 方法与其他现有的基于 Monte Carlo 的算法相比具有优势，有时效率要高几个数量级。”

于 2009-06-04T06:05:02.550 回答
1

对我来说，这听起来像是一个约束满足问题（CSP）。

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

但是，“一组合格值”的概念可能难以在数据结构中表示，具体取决于您允许的值范围。

于 2009-06-04T05:06:34.723 回答
0

我不确定你的天真算法是什么。这是我首先想到的：

m\cdot n具有线性约束的变量m+n导致解空间具有(m-1)\cdot(n-1)-1自由度的期望。

假设我们刚开始选择那么多随机数。

  a11 a12 ... a1[n-1] b
  a21 a22 ... a2[n-1] x2-x1+b
  ……………………
a[m-1]1 a[m-1]2 ... df
   c y2-y1+c ... ge

定义常数x_i=\sum_{j=1}^{n-1}a_{i,j}和y_j=\sum_{i=1}^{m-1}a_{i,j}。

这导致对变量b、c、d、e、f、g的以下约束：

x_1+b=\sum_{j=1}^{n-2}a_{m-1,j}+d+f=(m-2)\cdot(c-y_1)+\sum_{\i=1 }^{m-2}y_i+g+e
y_1+c=\sum_{i=1}^{m-2}a_{j,n-1}+d+g=(n-2)\cdot(c-x_1)+\sum_{j=1} ^{n-2}x_j+f+e

这是一个有 6 个变量的线性系统。它可能有一个独特的解决方案……我明天会解决这个问题。（目前缺少 Maple 或其他计算机代数系统。）

于 2009-06-04T06:02:34.223 回答
0

解决这个问题并在 R 中实现的方法是算法 AS159。这是纸

Patefield, WM (1981) 算法 AS159。一种生成具有给定行和列总计的 rxc 表的有效方法。应用统计 30, 91-97。

您可以点击此链接了解算法的实现。如果您习惯于使用 R，则可以简单地使用它的r2dtable功能。

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

于 2017-08-02T19:22:56.313 回答