Генератор для 3х зависимых дискретных величин.

[Sinclair]

_hum_ в сообщении #673498 писал(а):

"прореживающий алгоритм дает нужные маргинальные распределения"

Это не так. Указаная мною ошибка приводит к отклонению в маргинальных вероятностях генератора. Ваш алгоритм для примера с фишками не создаст генератор, выдающий те же маргинальные вероятности, что были на входе. Как, впрочем, и любой другой из перечисленных алгоритмов.
Так что противоречия нет.
За счет того, что этот алгоритм не сможет занулить совместную вероятность некоторых исходов, которые должны иметь нулевую совместную вероятностью - он "займет" немного веоятности в остальных местах. Вот в чем проблема. Вот почему не получится 50%. Как я рассчитал выше, у клетки 1 будет примерно 7% разницы между исходными маргинальными вероятностями, и выдаваемыми генератором.

-- 19.01.2013, 02:30 --

_hum_ в сообщении #673498 писал(а):

Я к тому, что либо прореживающий алгоритм дает неверные маргинальные распределения, либо получающаяся после него выборка является выборкой совместного распределения, удовлетворяющего ВСЕМ условиям (и следствиям из них). Третьего не дано.

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

[_hum_]

Sinclair в сообщении #673500 писал(а):

Ваш алгоритм для примера с фишками не создаст генератор, выдающий те же маргинальные вероятности, что были на входе.

Ну наконец-то, дошли до сути. Это значит, что в нем ошибка, и что он неверно работает. Зачем же тогда было говорить, что все ОК.
Вот теперь давайте разбираться, что же там не проходит. Начав с:

_hum_ в сообщении #673479 писал(а):

не мешало бы проверить, являются ли пары $(x,y)$, как ожидалось, равномерно распределенными в области $G_g$.

[Sinclair]

_hum_ в сообщении #673479 писал(а):

не мешало бы проверить, являются ли пары $(x,y)$, как ожидалось, равномерно распределенными в области $G_g$.

Да, конечно. По самому характеру генерации они распределены равномерно.

[_hum_]

Не, не теоретически, а экспериментально (порой ошибки скрываются там, где казалось, все очевидно).

Потому как, если оно равномерно распределено, то либо неверны Утверждения 1,2, либо мы их неправильно применяем.

[Sinclair]

_hum_ в сообщении #673502 писал(а):

Это значит, что в нем ошибка, и что он неверно работает. Зачем же тогда было говорить, что все ОК.
Вот теперь давайте разбираться, что же там не проходит. Начав с:

Мне кажется, что начинать разбираться надо с указанного мною местонахождения ошибки. Я выделил ее в рафинированном виде так, чтобы ничего другого в задаче не было. Рассмотрите пример с фишкой. Там легко и просто увидеть, почему происходит отклонение - алгоритм не может понять, что исход с ненулевыми маргинальными вероятностями должен иметь нулевую совместную вероятность, и распределяет совместную вероятность поровну между тем исходом, который вообще должен отсутствовать в сгенерированной выборке, и теми четырьмя, которые могут туда попасть.

[_hum_]

ок. спокойной ночи.

П.С.

Sinclair в сообщении #673507 писал(а):

Там легко и просто увидеть, почему происходит отклонение - алгоритм не может понять, что исход с ненулевыми маргинальными вероятностями должен иметь нулевую совместную вероятность, и распределяет совместную вероятность поровну между тем исходом, который вообще должен отсутствовать в сгенерированной выборке, и теми четырьмя, которые могут туда попасть.

Вопрос: почему? В том варианте, как я себе продумывал применение режект- метода, такого быть не должно. Потому и надо искать, в каком месте его применение оказывается некорректным.

[Sinclair]

_hum_ в сообщении #673508 писал(а):

ок. спокойной ночи.

ОК. Спасибо. Я в любом случае уже не слежу за ходом мысли.
Но хотя бы для себя я сам разобрался что тут как.
Я завтра буду разбирать, какие утверждения чему противоречат.

[_hum_]

А-аа, кажется, понял, в чем ошибка. Если мозг еще не бредит, то суть в следующем: если бы условие на отбрасывание проверялось только для одной компоненты, например, для черной фишки, то для этого цвета получалась бы нужная маргинальная плотность. А так есть еще и второе условие для другого цвета - белого, которое может "забраковывать" варианты, которые были "одобрены" первым условием, тем самым "деформируя" первое маргинальное распределение. И наоборот. Получается, эти два условия для каждого цвета "интерферируют", портя маргинальные распределения друг друга :(

Как вариант надо продумывать, можно ли их "править" так, чтобы не было "интерференции".

[Yu_K]

(Оффтоп)

[Sinclair]

_hum_ в сообщении #673511 писал(а):

А-аа, кажется, понял, в чем ошибка. Если мозг еще не бредит, то суть в следующем: если бы условие на отбрасывание проверялось только для одной компоненты, например, для черной фишки, то для этого цвета получалась бы нужная маргинальная плотность. А так есть еще и второе условие для другого цвета - белого, которое может "забраковывать" варианты, которые были "одобрены" первым условием, тем самым "деформируя" первое маргинальное распределение. И наоборот. Получается, эти два условия для каждого цвета "интерферируют", портя маргинальные распределения друг друга :(

Как вариант надо продумывать, можно ли их "править" так, чтобы не было "интерференции".

Дело не в этом, если я понимаю правильно.
Рассматриваем исходы примера с фишками:
(1, 2), (1, 3), (2, 1), (3, 1) - Это исходы Группы A. Исходы, содержащие фишку на первой клетке.
(2, 3), (3, 2) - Это исходы группы B. Исходы, у которых на первой клетке фишки нет.
Проблема в том, что для получения нужных маргинальных распределений нам нужно, чтобы вероятность отсеивания исходов группы B была 100% вне зависимости от того, как просериваются исходы группы A. Даже если каким-то образом мы учитываем то, о чем вы сказали, и при рассмотрении исхода группы A не проводится прореживание по фишке, стоящей не на первой клетке - даже в этом случае полного отсутствия прореженности нужная вероятность не достигается за счет того, что мы допускаем исходы группы B.

Дело в том, что в ходе просеивания понизить вероятность конкретного исхода можно не только путем его избыточного прореживания, но и путем недостаточного прореживания конкурирующих исходов, произведения маргинальных вероятностей компонентов которых больше совместной вероятности.

Алгоритм знает, что для клеток 2 и 3 маргинальные вероятности должны быть 25%, но он не знает, что эти 25% должны достигаться за счет исходов группы A, он считает исходы группы B столь же достойными того, чтобы принимать участие в формировании маргинальной вероятности 25% для 2й и 3й клеток.

Вот в чем проблема.

[_hum_]

Sinclair в сообщении #673609 писал(а):

Дело не в этом, если я понимаю правильно.

Sinclair, еще раз. Я привел подход с применением режект-метода к решению вашей задачи, который, если бы он был полностью корректным, давал нужный результат. Вы заметили, что этот подход изначально не может давать нужные маргинальные распределения. Отсюда вытекало, что он в чем-то некорректен. Осталось найти, в чем именно. Это место было найдено - взаимное влияние просеивания, которое я не учел. Вот и все.
Грубо говоря, мы оба привели контраргументы к применению этого метода, только вы опирались на "следствие", а я на "причину".

[Sinclair]

_hum_ в сообщении #673629 писал(а):

Sinclair в сообщении #673609 писал(а):

Дело не в этом, если я понимаю правильно.

Sinclair, еще раз. Я привел подход с применением режект-метода к решению вашей задачи, который, если бы он был полностью корректным, давал нужный результат. Вы заметили, что этот подход изначально не может давать нужные маргинальные распределения. Отсюда вытекало, что он в чем-то некорректен. Осталось найти, в чем именно. Это место было найдено - взаимное влияние просеивания, которое я не учел. Вот и все.
Грубо говоря, мы оба привели контраргументы к применению этого метода, только вы опирались на "следствие", а я на "причину".

В общем, я так и не понял до конца, в чем было недопонимание, но так или иначе проблема понятна. К сожалению, эта же самая проблема будет присуща всем упомянутым методам.
Пока у меня нет нормальных идей, как ее победить.
Но наверное надо первым делом определить условия, при которых условие "фишки не могут стоять на одной клетке" сдвигают совокупную вероятность клеток, не затронутых напрямую этим условием. Я пока в этом направлении думаю.

[_hum_]

Sinclair в сообщении #673635 писал(а):

Но наверное надо первым делом определить условия, при которых условие "фишки не могут стоять на одной клетке" сдвигают совокупную вероятность клеток, не затронутых напрямую этим условием. Я пока в этом направлении думаю.

А может, все-таки попробовать подумать в сторону "итераций", "покоординатного спуска" и т.п.? То есть, организовать какую-нибудь последовательность прореживаний, например, на первом шаге прореживание с получением маргинального для первой компоненты, на втором - для второй, на третьем - снова для первой и т.д. Тогда бы гипотетически могла появиться возможность того, о чем вы говорили - все больше и больше могли бы начать отсеиваться варианты с $(2,3)$, $(3,2)$, что в пределе дало бы нужные нулевые вероятности.

Или, например, попробовать выполнять прореживание сразу по двум компонентам, но отбрасывать только те варианты, которые обе компоненты "забраковали". И тоже повторять эту процедуру итерационно.

[Sinclair]

_hum_ в сообщении #673648 писал(а):

Sinclair в сообщении #673635 писал(а):

Но наверное надо первым делом определить условия, при которых условие "фишки не могут стоять на одной клетке" сдвигают совокупную вероятность клеток, не затронутых напрямую этим условием. Я пока в этом направлении думаю.

А может, все-таки попробовать подумать в сторону "итераций", "покоординатного спуска" и т.п.? То есть, организовать какую-нибудь последовательность прореживаний, например, на первом шаге прореживание с получением маргинального для первой компоненты, на втором - для второй, на третьем - снова для первой и т.д. Тогда бы гипотетически могла появиться возможность того, о чем вы говорили - все больше и больше могли бы начать отсеиваться варианты с $(2,3)$, $(3,2)$, что в пределе дало бы нужные нулевые вероятности.

Я думаю над этим сейчас. Судя по всему, в уме я могу представить решение этим методом упрощенной задачи (про фишки):
Предположим, исход, по фишке, стоящей на 1й клетке отсеиваться не будет вовсе, а по фишке, стоящей на 2й или 3й клетке он будет отсеиваться с большой вероятностью, например, 99%.
В таком случае исходы (2, 3) и (3, 2) будут отсеиваться в 100 раз чаще, чем исходы, в которых одна из фишек стоит на 1м месте.
То есть, это решение, судя по всему, дает в пределе нужное решение.
Правда, сразу видны недостатки:
1) во-первых, по мере уменьшения маргинальной вероятности 2й и 3й клеток, у нас будет браковаться все больше подходящих нам исходов. В приведенном мною примере 99 исходов (1, 2) из 100 будут отсеиваться.
2) во-вторых, я не знаю, подойдет ли это решение для исходной задачи с доской. Интуитивно пока похоже на то, что подойдет (но первый недостаток сохранится)

[nikvic]

Всё это выглядит как задача линейного программирования - неотрицательность вероятностей, около 200 линейных уравнений (64*3-2?). Но уж больно много переменных... Зато ищем не экстремум, а какое-нибудь решение
Правда, может оказаться, что таковых вообще нет.

Представим, что у нас есть много решений, но с другими распределениями. Их смесь (линейная комбинация с весами >=0 суммой 1) - тоже решение. Если повезёт, удастся найти смесь с нужными распределениями.
Эти решения можно пытаться искать и случайно, каждый раз распределяя вероятности позиций по относительно небольшому множеству допустимых ячеек, порядка нескольких сотен.
Стратегия отбора - пытаться вычитанием из уже достигнутого результата приблизить к равномерным распределениям...