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

[_hum_]

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

Два вопроса.
1) Откуда берется выборка $\mathbf{A}_{*}$. Это просто какой-то набор исходов совместного распределения? И чем он больше, тем аккуратнее пересчитываются распределения?

Про выборку и откуда она берется писалось здесь сообщение #673463. На всякий случай, схема такова:

$\mathbf{A}$ -> (прореживание по условию непопадания в одну клетку) -> $\mathbf{A}_{*}$ ->(прореживание по алгоритму) -> $\mathbf{A}_{**}$ ->
-> полагаем $\mathbf{A}_{*} = \mathbf{A}_{**}$ -> (прореживание по алгоритму) -> $\mathbf{A}_{**}$ ->
-> полагаем $\mathbf{A}_{*} = \mathbf{A}_{**}$ -> (прореживание по алгоритму) -> $\mathbf{A}_{**}$ ->
....-> последнюю получившуюся после 200 итераций прореживания выборку $\mathbf{A}_{**}$ выдаем в качестве результата.

Цитата:

2) Я не понял смысл выражений под суммой. Что такое дельта функция я посмотрел в википедии, но смысл использования ее в данном контексте мне не понятен. Почему здесь дельта функция получает два аргумента? Вообще, как она себя ведет в данном случае?

$\delta(i,j)= 1$ , если $i = j$ и $0$ в противном случае (cимвол Кронекера/дельта Кронекера).

По смыслу, формулы - это просто подсчет (относительной) частоты встречаемости в выборке соответствующего значения (оценка вероятности - это частота встречаемости, ведь так? Вы разве по-другому маргинальные вероятности оценивали по выборке?)

[Sinclair]

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

По смыслу, формулы - это просто подсчет (относительной) частоты встречаемости в выборке соответствующего значения (оценка вероятности - это частота встречаемости, ведь так? Вы разве по-другому маргинальные вероятности оценивали по выборке?)

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

[_hum_]

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

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

так это ж нереально на обычном компьютере сделать - он за секунду даже просто пробежаться по всей выборке не сможет...

[Sinclair]

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

так это ж нереально на обычном компьютере сделать - он за секунду даже просто пробежаться по всей выборке не сможет...

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

[_hum_]

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

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

так это ж нереально на обычном компьютере сделать - он за секунду даже просто пробежаться по всей выборке не сможет...

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

Ну, попробуйте, наподобие, берете для требуемого размера выборки $n = 1000$ заводите счетчики $C_B[i], C_W[i], i =1,2,3$, полагая вначале их значения равным тем, которые нужно получить: $ C_B[1] = 500, C_B[2] = 250, C_B[3] = 250,$ $ C_W[1] = 500, C_W[2] = 250, C_W[3] = 250.$

А после начинаете
1) пока все счетчики не равны нулю, выполнять
1.2) генерировать случайную пару $(a_B, a_W), a_B,a_W \in \{1,2,3\}.$
1.3) если $a_B == a_W$, то перейти к п. 1)
1.4) если $(C_B[a_B] == 0)$ ИЛИ $(C_W[a_W]== 0)$, то перейти к п. 1)
1.5) $C_B[a_B] = C_B[a_B] - 1$
1.6) $C_W[a_W] = C_W[a_W] - 1$
1.7) печать $(a_B, a_W)$ как найденного очередного элемента предварительной (неперемешенной) выборки.
2) перемешиваете выборку.

Но опять же, видите, нужно будет перемешивание, а для этого придется лазить по выборке :(

Так что не знаю, чем вам тут еще помочь.

Цитата:

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

Этого я не понимаю. Можете на примере фишек в клетках пояснить?

-- Вс янв 20, 2013 01:27:38 --

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

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

Кстати, в порядке бреда...
От вас же, насколько я понимаю, ожидается функция наподобие GenerateRandomValue(), которая бы при каждом вызове давала бы очередное значение выборки?
Так можно же при первом вызове взять и "быстро" подготовить у себя внутри выборку не слишком большого размера, например (в зависимости от требуемой точности), 5000. А потом просто выплевывать значения из нее. Как дойдете до конца, опять генерируете следующий кусок. И т.д. Если считать, что выборка - это реализация с.в., то объединение лвух выборок в одну ничего не испортят...

[Sinclair]

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

Но опять же, видите, нужно будет перемешивание, а для этого придется лазить по выборке :(

Ну нам придется лазить по выборке величиной в 1000 элементов, а не триллиард, так что все ок.

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

Так что не знаю, чем вам тут еще помочь.

Надо о чем то новом думать. Я сам пятаюсь надумать что-то. Уже много времени на эту задачу потратил. Скоро придется брать хоть какое то решение.

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

Цитата:

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

Этого я не понимаю. Можете на примере фишек в клетках пояснить?

Ну это как раз то, о чем мы говорили. Если события совместные, то генератор тривиален - он просто генерирует каждый элемент вектора независимо по заданным маргинальным распределениям. Если мы вводим запрет находиться для фишек в одной области, например, стоять на одной клетке или стоять на одной линии, то события "фишка Б на клетке 1" и "фишка Ч на клетке 1" становятся несовместными (то же самое с линией - 2 ладьи на одной линии - это несовместные события), то в тех случаях, когда суммарная вероятность попадания в эту область стремится к 1, происходит рассмотренный нами феномен. Например, когда суммарная вероятность попасть в 1ю клетку приближается к 1, то все алгоритмы начинают генерировать смещенное на 7% распределение.
Если, говоря об исходной задаче, на какой то линии вероятность нахождения близка к 1, и на этой линии может стоять только одна ладья - эффект будет тот же, вероятность попадания на эту линию будет уменьшаться.

[_hum_]

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

Ну нам придется лазить по выборке величиной в 1000 элементов, а не триллиард, так что все ок.

Брр...Не понимаю. Может, тогда и техническую сторону проясните - что в конце-концов от вас требуют (в каком виде генератор, с какой спецификацией и требованиями).

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

Например, когда суммарная вероятность попасть в 1ю клетку приближается к 1, то все алгоритмы начинают генерировать смещенное на 7% распределение.

Откуда это? Что под "смещенным распределением" понимается? И откуда число 7%???

[Sinclair]

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

Брр...Не понимаю. Может, тогда и техническую сторону проясните - что в конце-концов от вас требуют (в каком виде генератор, с какой спецификацией и требованиями).

Задача является полным аналогом шахматной доски. Только ее размер может быть где то 40х40 клеток, а ладей может быть 3 или 4.

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

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

Например, когда суммарная вероятность попасть в 1ю клетку приближается к 1, то все алгоритмы начинают генерировать смещенное на 7% распределение.

Откуда это? Что под "смещенным распределением" понимается? И откуда число 7%???

Ну это же та проблема о которой мы весь день говорили сегодня.
post673500.html#p673500 - вот тут, например, я про нее писал.
Это та самая проблема, из за который ваш алгоритм надо делать итерационным, и из за который он не выдает нужные распределения сразу.

[_hum_]

Я про техническую сторону вашей задачи спрашивал - в каком виде вам ее надо представить: в виде функции на ПК, генерирующей очередное значение с ограничением по памяти во столько, по времени во столько или что?

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

Цитата:

Откуда это? Что под "смещенным распределением" понимается? И откуда число 7%???

Ну это же та проблема о которой мы весь день говорили сегодня.
post673500.html#p673500 - вот тут, например, я про нее писал.
Это та самая проблема, из за который ваш алгоритм надо делать итерационным, и из за который он не выдает нужные распределения сразу.

Мы же с тем давно разобрались. Там алгоритм неправильный был, потому он давал вообще некорректные результаты, зачем к нему возвращаться. Мы же его давно уже заменили итерационным, в котором прореживание осуществляется по процедуре в сообщении #673834 и выполнение по схеме в сообщении #673933. С ним проблемы со "смещенностью" есть? Если да, то объясните понятие "смещенности" на его примере.

[Sinclair]

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

Я про техническую сторону вашей задачи спрашивал - в каком виде вам ее надо представить: в виде функции на ПК, генерирующей очередное значение с ограничением по памяти во столько, по времени во столько или что?

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

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

Мы же с тем давно разобрались. Там алгоритм неправильный был, потому он давал вообще некорректные результаты, зачем к нему возвращаться. Мы же его давно уже заменили итерационным, в котором прореживание осуществляется по процедуре в сообщении #673834 и выполнение по схеме в сообщении #673933. С ним проблемы со "смещенностью" есть? Если да, то объясните понятие "смещенности" на его примере.

Ну как, неправильный. Он был бы правильным, не будь запрета ставить две фишки на одну клетку. И все остальные генераторы в треде имели ту же ошибку. Я просто рассматриваю это как отдельную проблему. Вы предпочитаете рассматривать оба условия наравне, и просто искать удовлетворяющее их решение, а неудовлетворяющее считать просто ошибкой. Я все надеюсь решить эту проблему каким-то универсальным, отдельным от остального решения способом. Это был бы лучший вариант.
Что до итерационного решения - я не знаю, применимо ли оно к исходной задаче, нет смысла это выяснять, поскольку оно нереализуемо технически. Я подумал над этим некоторое время. Думаю, что применимо. То есть, если бы у нас было время на создание генератора - скорее всего оно бы подошло. Может проблему к коэффициэнтом С не так уж сложно побороть, как мне кажется.

[_hum_]

Ясно. Ну, как говорится, чем могли...

На всякий случай выкладываю свой код на Mathematica, Sinclair5.nb

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

Может проблему к коэффициэнтом С не так уж сложно побороть, как мне кажется.

Если вы о той константе C, что в алгоритме прореживания, то вроде ж уже обсуждали этот вопрос:

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

Откуда большое С? Во-первых, оно на каждой итерации разное, а во-вторых, чем ближе текущее маргинальное к заданному, тем оно меньше.

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

[Sinclair]

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

Ясно. Ну, как говорится, чем могли...

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

Идея простейшая:
1) Берем ваш исходный алгоритм режекции безо всяких итераций, и получаем выдаваемую им последовательность. Она получится смещенной, как уже было показано выше.

Теперь вопрос в том, каков характер этого смещения. Исходя из высказанной тут post673609.html#p673609 идее о том, что

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

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

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

можно заметить, что проблема состоит в том, что в конечной выборке находятся исходы, "тянущие" вниз вероятность связанных с ними исходов из областей несовместности с суммарной вероятностью близкой к 1. Решение, очевидно, состоит в том, чтобы перечислить эти области (их не может быть много, так как если в одной области суммарная вероятность близка к 1, то другим областям ее остается мало) и после получения конечной выборки можно просто проверить какова частота исходов, относящихся к этим областям. Если она отстает от теоретической - выкинуть нужное колличество исходов из других областей, чтобы приблизиться к исходным распределениям.
т.е.
2) Найти суммарную вероятность в каждой области несовместности.
То есть, для примера с фишками, где областью несовместности является одна клетка - найти суммарную вероятность для всех клеток. Это для данного примера будет 100/50/50. Область несовместности с близкой к 1 вероятностью - клетка 1.
Для исходной задачи сложнее, там областью несовместности являются две линии, пересекающиеся в клетке, где стоит лдья. Но, тем не менее, и это легко вычислимо.
3) Оставить "проблемные" зоны несовместности - те, где суммарная вероятность близка к 1.
4) Просеять результаты еще раз. Пропускать через новый фильтр те, которые увеличивают вероятность в проблемных зонах, а остальные пропускать только в том случае, если их добавление не не уменьшает вероятность в проблемных зонах ниже теоретической.
То есть, в случае с фишками мы не будем пропускать исходы (2, 3) и (3, 2), так как их добавление уменьшит вероятность проблемной зоны - 1й клетки ниже теоретической.
Таким образом - нам не нужны итерации, C всегда умеренное, затраты минимальны.
Сейчас я думаю над тем, все ли правильно в данном алгоритме.
Вроде выглядит состоятельным.

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

На всякий случай выкладываю свой код на Mathematica, Sinclair5.nb

Спасибо, что серьезно решаете эту задачу. Я бы еще неизвестно сколько решал ее без ваших идей.

[Deggial]

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

После чего генерируем произвольные исходы, оставляя исходы, содержание фишку на 1й клетке с веротяность 1(вероятность того, что мы не отсеим этот исход по фишке, стоящей на 1й клетке)*0.01(вероятность того, что мы не отсеим этот исход по фишке, стоящей на второй клетке)/0.01(максимальная вероятность неотсеивания исхода) = 1, а исходы без фишки на 1й клетке отсеивая в 99% случаев (1 - 0.01*0.01/0.01).

Sinclair, замечание за неоформление формул ТеХом. Согласно правилам форума, формулы следует писать ТеХом. Инструкции по оформлению формул здесь или здесь (или в этом видеоролике).

[_hum_]

Sinclair, еще раз повторю - первоначальный алгоритм просеивания (без итераций) некорректен - он дает неверные маргинальные распределения, и не столько потому, что "не может обнаружить событий с нулевой вероятностью", а потому, что при формировании нужного маргинального распределения одной компоненты отбрасываются(не отбрасываются) реализации, которые НЕ НУЖНО(НУЖНО) отбрасывать для формирования маргинального распределения другой компоненты (сродни "перетягиванию одеяла")! Потому и необходимы итерации, чтобы как-то "прийти к общему знаменателю". Чтобы убедиться в этом, возьмите, например, в качестве маргинальных $(0.3,0.4,0.3)$ [ для этого случая в совместном распределении уже не нужно, чтобы обязательно были значения с нулевыми вероятностями (исключая диагональные)] и примените алгоритм без итераций - убедитесь, что результат будет неверным.

[Sinclair]

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

Sinclair, еще раз повторю - первоначальный алгоритм просеивания (без итераций) некорректен - он дает неверные маргинальные распределения, и не столько потому, что "не может обнаружить событий с нулевой вероятностью", а потому, что при формировании нужного маргинального распределения одной компоненты отбрасываются(не отбрасываются) реализации, которые НЕ НУЖНО(НУЖНО) отбрасывать для формирования маргинального распределения другой компоненты (сродни "перетягиванию одеяла")! Потому и необходимы итерации, чтобы как-то "прийти к общему знаменателю". Чтобы убедиться в этом, возьмите, например, в качестве маргинальных $(0.3,0.4,0.3)$ [ для этого случая в совместном распределении уже не нужно, чтобы обязательно были значения с нулевыми вероятностями (исключая диагональные)] и примените алгоритм без итераций - убедитесь, что результат будет неверным.

Я еще вчера прочитал этот ваш пост. В общем, я понял написанное.
Ощутил печаль. И думал снова пол ночи, что можно сделать.
Набрел на такой алгоритм:
1) Генерируем ряд исходов по маргинальным распределениям, безо всяких отсевов.
Часть исходов будут недопустимыми (ладьи на одной линии).
Выделяем их в отдельную группу.

Смотрим на получившееся распределение отсеянных вариантов. Если мы подберем соответствующее колличество допустимых вариантов, как можно ближе соответствующих этому распределению - то получившиеся маргинальные распределения будет теми же, которые получились бы при генерации, если бы несовместных исходов не было вовсе.
2) Подбираем совместные исходы, соответствующих "отбракованному распределению". Как это сделать - отдельный разговор

3) Получившееся распределение будет болеть той же болезнью, что и остальные алгоритмы (про нулевую совместную вероятность). Решать его надо, как я придумал позапрошлой ночью: post674071.html#p674071 (просевом окончательной выборки)

Как не трудно заметить, это разновидность второго алгоритма из оппоста, который всплывал несоклько раз по ходу треда.

Теперь, надо описать подалгоритм генерации допустимых исходов по отбракованному распределению (расписать пункт 2 приведенного выше алгоритма). Сначала для случаев, когда нельзя стоять на одной клетке, а на одной линии можно:
Сразу оговоримся, что это будет особое распределение. Оно будет целочисленным. Каждый раз, когда мы будем получать на 1м шаге вышеприведенного алгоритма недопустимый исхода вида (a, b, c), где a будет равно b, или b равно с, или a равно с, мы будем увеличивать на 1 реализацию a маргинального спектра первой фишки, на 1 реализацию b второй фишки, и на 1 реализацию с третьей.
То есть, это просто более удобное представление распределения для моей задачи. Ну чтобы не путаться с терминологией, можно называть это "спектром".
Если мы будем просто генерировать исходы по этому спектру - мы будем получать еще больше "коллизий", чем при исходной генерации. Потому мы сделаем следующее:
a) просуммируем спектры для всех фишек.
b) найдем элемент суммарного спектра с самым большим значением. Его нужно тратить в первую очередь, чтобы минимизировать число коллизий.
c) посмотрим, какой из маргинальных спектров имеет наиболее колличество этих элементов. Возьмем его. Это будет позиция фишки, соответствующей этому спектру.
d) теперь надо выбрать позицию следующей фишки. В общем, выбираем ее так же, только с запретом занимать уже занятую позицию. Берем суммарные маргинальные спектры оставшихся фишек, откидываем занятый вариант, берем максимальный элемент, смотрим, какой спект внес больший вклад в эту позицию, и это и будет позиция соответствующей этому спектру фишки.
e) с последней фишкой и вовсе все просто - берем из ее спектра самый большой неиспользованный элемент.
f) перейдем на начало, пока спектры не нулевые
Данный алгоритм будет "тратить" изначально наиболее склонные к коллизиям области спектра.
Если мы доходим до коллизии - останавливаем алгоритм, и остаток отбрасываем со словами - "мы сделали все, что могли". Впрочем, мне кажется, что коллизии при этом алгоритме возникнут не может. Но точного доказательства нет.

Я, вообще, понимаю, что описал сумбурно. Но я надеюсь, что идею можно уловить.

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