Эффективный способ создания случайных таблиц непредвиденных обстоятельств? - PullRequest
Новая
       16

Эффективный способ создания случайных таблиц непредвиденных обстоятельств?

6 голосов
/ 04 июня 2009

Каков эффективный способ создания таблицы случайных обстоятельств? Таблица сопряженности определена как прямоугольная матрица, так что сумма каждой строки является фиксированной, а сумма каждого столбца фиксированной, но отдельные элементы могут быть любыми, если сумма каждой строки и столбца является правильной.

Обратите внимание, что генерировать случайные таблицы непредвиденных обстоятельств очень просто, но я ищу что-то более эффективное, чем простой алгоритм.

Ответы [ 4 ]

6 голосов
/ 04 июня 2009

Может быть полезно посмотреть на код пакета networksis для R. Я считаю, что для эффективных вычислений требуются причудливые методы последовательной значимости по цепочке Маркова , поэтому, возможно, вы захотите избежать переопределения этого, если сможете этого избежать.

Редактировать: Соответствующий документ: Чен, Диаконис, Холмс и Лю (2005) . По словам авторов, «наш метод выгодно отличается от других существующих методов Монте-Карло. алгоритмы, а иногда и на несколько порядков более эффективны. "

1 голос
/ 04 июня 2009

Для меня это звучит как проблема удовлетворения ограничений (CSP).

Обычно вы начинаете с некоторой точки и выбираете значение ячейки случайным образом из набора допустимых значений. Затем вы обновляете наборы допустимых значений для всех ячеек в той же строке / столбце и выбираете следующую ячейку (в соответствии с используемой вами эвристикой CSP), чтобы (случайным образом) присвоить значение снова из его набора допустимых значений. Опять же, вам также необходимо обновить наборы допустимых значений для всех ячеек в одной строке / столбце. В случае, если вы встретите ячейку с пустым набором допустимых значений, вы должны будете вернуться назад.

Однако понятие «набор допустимых значений» может быть трудно представить в структуре данных в зависимости от диапазона значений, которые вы допускаете.

0 голосов
/ 02 августа 2017

Решением этой проблемы, реализованным в R, является Алгоритм AS159 . Вот бумага

Пейтфилд, У. М. (1981) Алгоритм AS159. Эффективный метод генерации r x c таблиц с заданными суммами строк и столбцов. Прикладная статистика 30, 91–97.

Вы можете перейти по этой ссылке для реализации алгоритма. Если вы привыкли работать с R, вы можете просто использовать для этого функцию r2dtable.

Этот алгоритм может использоваться для генерации p-значений Монте-Карло для критерия хи-квадрат, полученного в функции R chisq.test. Обратите внимание, что chisq.test вызывает не r2dtable, а прямую C версию алгоритма AS159.

0 голосов
/ 04 июня 2009

Я не уверен, каков твой наивный алгоритм. Вот первое, о чем я думаю:

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 ...    d    f
   c    y2-y1+c ...    g    e

Определите константы 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 , г :

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 переменных. , вероятно, имеет уникальное решение & hellip; Я буду работать над этим завтра. (Отсутствие системы Maple или других систем компьютерной алгебры на данный момент.)

...