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

[ewert]

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

Проблема не такая простая, как казалось.

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

[TOTAL]

Евгений Машеров в сообщении #672259 писал(а):

А собственно? Есть ли проблема?

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

[nikvic]

Sinclair
Можно ли трактовать задачу следующим образом.
Имееется три распределения клеток (извлекаются статистикой). Требуется найти какое-либо совместное распределение с указанным дополнительным свойством.

[Sinclair]

Евгений Машеров в сообщении #672259 писал(а):

А собственно? Есть ли проблема?
Имеется статистика по попаданию отдельных ладей в данные клетки. Она, очевидно, отражает только "небьющие" конфигурации. Генерируем случайное размещение с данными вероятностями. Получаем либо битие, либо небитие. В случае, если битие - генерация неудачна, сбрасывается и повторяется опыт вплоть до умпеха. В случае если небитие - сгенерировано расположение в точности с заданными вероятностями, "по построению". Может, и не надо мудрить?

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

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

Вот если у нас на одной линии (в рамках данного примера для упрощения представим, что ладьи бьют только по горизонтали, и их две) находятся клетки, совокупная вероятность нахождения в которых красной ладьи равна .3, и совокупная вероятность нахождения зеленой ладьи равна .3. С учетом отбракованых вариантов, вероятность нахождения ладей на этой линии изменится до .21 и .21 соответственно. То есть, будут отбракованы варианты, при которых ладьи одновременно выпадают на этой линии. Если же на другой линии совокупные вероятности нахождения красной и зеленой ладей равны .1 и .1 соответственно, то после отбраковки эти вероятности будут равны .09 и .09. Поскольку 0.21/0.09 не равно 0.3/0.1, мы видим, что вероятности меняются неравномерно. То есть, генерируются результаты с другим распределением.

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

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

Предположим, что у нас есть клетка, на которой красная и зеленая ладья находятся с вероятностью .5, а желтая - 0, при этом на остальных клетках строки и столбца все вероятности равны нулю. Понятно, что в данном случае на этом месте обязана стоять либо красная ладья, либо зеленая - иначе совокупная вероятность нахождения здесь будет меньше 1. Но пока ни при одном из методов генерации (включая этот) данная проблема не решена. То есть, чем ближе на каком то столбце/строке совокупная вероятность нахождения всех ладей к 1, тем больше отклоняются распределения.
Этот момент мне кажется самой серьезной из имеющихся проблем.

тоже не решена.

[TOTAL]

Противоречивыми могут быть сами требуемые распределения. Пусть доска 2 на 2, две ладьи, хотим получить вероятность обнаружить белую и черную ладью на (1,1) равную 0.7, а на (2,2) равную 0.3. Это противеречивое, невыполнимое требование.

-- Ср янв 16, 2013 13:52:56 --

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

Предположим, что у нас есть клетка, на которой красная и зеленая ладья находятся с вероятностью .5, а желтая - 0, при этом на остальных клетках строки и столбца все вероятности равны нулю. Понятно, что в данном случае на этом месте обязана стоять либо красная ладья, либо зеленая - иначе совокупная вероятность нахождения здесь будет меньше 1.

Не обязана стоять там ладья.

[Sinclair]

TOTAL в сообщении #672264 писал(а):

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

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

Про какую совокупную вероятность говорите, не вижу проблемы.

Вот смотрите. У нас есть клетка, вероятность нахождения на которой красной и зеленой ладей равно .5. Поскольку обе ладьи одновременно на ней находиться не могут, это означает, что если возникнет ситуация, при которой на данной клетке нет ни одной ладьи - значит либо красная ладья, либо зеленая, либо обе принципиально не могут достичь на данной клетке вероятности нахождения .5, так как одновременно они там находиться не могут, а если в половине случаев там стоит одна ладья, то другая принципиально имеет в своем распоряжении только половину случаев, когда она может там стоять. Если она там стоит реже - ее вероятность нахождения там меньше .5.

-- 16.01.2013, 12:56 --

ewert в сообщении #672265 писал(а):

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

Проблема не такая простая, как казалось.

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

Я не пытаюсь ничего замолчать. Я просто не понимаю, о чем вы спрашиваете. И я не понимаю, какое таинственное распределение вы упоминаете.
Есть распределение совокупности из 3х ладей. Это распределение мне не известно, я его не скрываю. Но известны распределения его компонент, и тип зависимости между ними. Пользуясь этой информацией надо создать генератор распределения совокупности из 3х ладей. Я вижу себе это так. Если вам кажется, что я что-то умолчал - скажите что именно.

-- 16.01.2013, 12:58 --

nikvic в сообщении #672268 писал(а):

Sinclair
Можно ли трактовать задачу следующим образом.
Имееется три распределения клеток (извлекаются статистикой). Требуется найти какое-либо совместное распределение с указанным дополнительным свойством.

Да, именно так. Я именно об этом говорю.
Если точнее - находить распределение не обязательно, надо построить его генератор.

[Евгений Машеров]

А зачем Вам при сборе статистики учитывать отбракованные варианты?
У Вас же наблюдаемы только неотбраковываемые.

[ewert]

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

известны распределения его компонент, и тип зависимости между ними

Приведите хоть одну конкретную постановку задачи. И что такое "тип зависимости"?...

[TOTAL]

Увеличить вероятность для клетки, с которой ладья отбраковалась. Это чем плохо?

[Sinclair]

TOTAL в сообщении #672272 писал(а):

Противоречивыми могут быть сами требуемые распределения. Пусть доска 2 на 2, две ладьи, хотим получить вероятность обнаружить белую и черную ладью на (1,1) равную 0.7, а на (2,2) равную 0.3. Это противеречивое, невыполнимое требование.

Безусловно, можно создать невозможное распределение. Но поскольку в нашем случае распределение апостериорное, то такой ситуации не возникнет.

TOTAL в сообщении #672272 писал(а):

Не обязана стоять там ладья.

Ок. Сформулирую так - вероятность ненахождения там ладьи должна равняться нулю.
Давайте рассмотрим два события - первое - нахождение на клетке красной ладьи, второе - нахождение на этой же клетке зеленой ладьи. Эти события несовместные. Вероятность каждого - .5. Значит вероятность либо одного, либо другого - их сумма, то есть 1.

-- 16.01.2013, 13:04 --

Евгений Машеров в сообщении #672276 писал(а):

А зачем Вам при сборе статистики учитывать отбракованные варианты?
У Вас же наблюдаемы только неотбраковываемые.

Учитывать отбракованные нужно не при сборе статистики, а при генерации. Да, я наблюдаю только неотбракованные варианты. А при генерации отбраковываю еще раз. В этом проблема.

-- 16.01.2013, 13:08 --

ewert в сообщении #672277 писал(а):

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

известны распределения его компонент, и тип зависимости между ними

Приведите хоть одну конкретную постановку задачи. И что такое "тип зависимости"?...

Я не понимаю, что вы от меня хотите.
Конкретная задача - создание генератора.
"Тип зависимости" - это закономерность, которая накладывается на независимые случайные величины, при объединении их в одну случайную величину. Это не математический, а скорее интуитивный термин, если вы об этом.

[ИСН]

1. Собираем статистику одночастичных распределений.
2. Генерируем по ним конфигурации, с отбрасыванием.
3. Смотрим, какие теперь получились одночастичные распределения и как они отличаются от нужных.
4. Корректируем в противоположную сторону те распределения, по которым генерировали.
5. goto 2.
Чем плохо?
Тем, что:
6. В столбцах, где суммарная вероятность близка к 1, наш процесс задерёт плотность одночастичных распределений тоже близко к 1, отбрасывать придётся большинство, и процесс генерации чертовски замедлится.
Так?

[Sinclair]

TOTAL в сообщении #672278 писал(а):

Увеличить вероятность для клетки, с которой ладья отбраковалась. Это чем плохо?

Для того, чтобы объяснить, чем это плохо, я должен сначала объяснить тот пример, в котором две ладьи имеют вероятность нахождения .5 (каждая) ка одной и той же клетке.
Увеличение вероятности отбраковавшейся клетки в принципе не способна решить данную проблему. Всегда будет существовать ненулевая вероятность того, что приведенная мною клетка (с совокупной вероятностью нахождения 1) будет пустая.
Я думаю, что стоит развивать способ решения через вероятность непопадания ладьи на данную клетку, и ее модификации при последовательной генерации. Пока я дальше не продвинулся.
Впрочем, конечно, все варианты надо рассмотреть.

[TOTAL]

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

TOTAL в сообщении #672278 писал(а):

Увеличить вероятность для клетки, с которой ладья отбраковалась. Это чем плохо?

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

Вы сами сказали, что вероятности получены экспериментально, поэтому реализуемы. Неужели практически можно наблюдать по 0.5 для двух ладей на одной клетке? Или это теоретическая боязнь?

[Sinclair]

ИСН в сообщении #672283 писал(а):

1. Собираем статистику одночастичных распределений.
2. Генерируем по ним конфигурации, с отбрасыванием.
3. Смотрим, какие теперь получились одночастичные распределения и как они отличаются от нужных.
4. Корректируем в противоположную сторону те распределения, по которым генерировали.
5. goto 2.
Чем плохо?
Тем, что:
6. В столбцах, где суммарная вероятность близка к 1, наш процесс задерёт плотность одночастичных распределений тоже близко к 1, отбрасывать придётся большинство, и процесс генерации чертовски замедлится.
Так?

Нет. Проблема более глубокая. Смотрите. Рассмотрим упрощенный вариант:
У нас есть 3 ладьи, но которые бьют только по столбцу, но не по строке.
У нас есть 2 столбца, на каждом из которых совокупная вероятность нахождения одной из 3х ладей равна 1. Еще одна еденица вероятности распределена по оставшимся клеткам доски. Не важно, сколько мы подгоняем процесс генерации. В любом случае, у нас произойдет одно из следующих событий:
Либо вероятности нахождения ладей за пределами данных столбцов будут не нулевыми, и сможет произойти событие с ненулевой вероятностью, при котором все ладьи сгенерируются за пределами этих столбцов (хотя оба столбца должны быть заняты с вероятностью 1), либо все вероятности за пределами этих столбцов занулятся. Но тогда возникает вопрос - куда ставить третью ладью? Информация об оставшемся распределении просто потеряется.
Да, и кроме того, по мере задирания вероятности нахождения отдельных ладей в 1 по конкретным столбцам - распределение ладей по этим столбцам тоже потеряется - у каждой из них будет равная вероятность попасть туда.
Вообще, столбцы - это просто одномерный случай. Лучше переформулировать задачу в одномерном виде: Просто есть 8 клеток и распределение по ним 3х ладей, которые просто не могут занимать одно место.

-- 16.01.2013, 13:26 --

TOTAL в сообщении #672285 писал(а):

Вы сами сказали, что вероятности получены экспериментально, поэтому реализуемы. Неужели практически можно наблюдать по 0.5 для двух ладей на одной клетке? Или это теоретическая боязнь?

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

[TOTAL]

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

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

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

-- Ср янв 16, 2013 14:44:13 --

А такой вариант.

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

Очередность ладей случайна.