Где находится бомба: как оценить вероятность, исходя из общего количества строк и столбцов?

14

Этот вопрос вдохновлен мини-игрой от Pokemon Soulsilver:

Представьте, что в этой области 5х6 спрятано 15 бомб (РЕДАКТИРОВАТЬ: максимум 1 бомба / клетка):

Суммы

Теперь, как бы вы оценили вероятность найти бомбу на определенном поле, учитывая итоги строки / столбца?

Если вы посмотрите на столбец 5 (всего бомб = 5), то вы можете подумать: в этом столбце шанс найти бомбу в ряду 2 вдвое больше, чем шанс найти бомбу в ряду 1.

Это (неправильное) предположение о прямой пропорциональности, которое в основном можно описать как приведение стандартных операций проверки независимости (как в хи-квадрат) в неправильный контекст, приведет к следующим оценкам:

Хи-квадрат

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

Поэтому я выполнил вычислительное моделирование всех возможных перестановок, которое привело к 276 уникальным возможностям размещения 15 бомб. (заданные итоги по строкам и столбцам)

Вот среднее значение по 276 решениям: Вычислительное решение

Это правильное решение, но из-за экспоненциальной вычислительной работы я хотел бы найти метод оценки.

Мой вопрос сейчас: есть ли установленный статистический метод для оценки этого? Мне было интересно, если это известная проблема, как она называется и есть ли какие-либо документы / сайты, которые вы могли бы порекомендовать!

KaPy3141
источник
1
Быстрый и простой подход: для большего количества строк и столбцов вы можете провести симуляцию по методу Монте-Карло, где вы будете проверять случайную подвыборку возможных конфигураций, которая меньше, чем общее количество возможностей. Это даст вам приблизительное решение.
Тим
1
Я не понимаю вашего вычислительного решения. Какие цифры в клетках? Они, конечно, не складываются до 100%, это не PMF. Они также не похожи на CDF, правая / нижняя ячейка не на 100%
Аксакал
2
@Aksakal Это предельные вероятности того, что любая клетка содержит бомбу. Числа добавляют к 15, общее количество бомб на доске.
Дугал
2
Если вы предполагаете, что эти два поля независимы, то сравнительно просто выбрать из распределения таблиц при условии наличия полей (с помощью алгоритма Пейтфилда). Это реализовано в стандартном распределении R in r2dtable(а также используется chisq.testи fisher.testв некоторых случаях).
Glen_b
2
@Glen_b Но в алгоритме Пейтфилда количество событий на ячейку не ограничивается одним.
Ярле Туфто

Ответы:

4

Пространство решений (действительные конфигурации бомб) можно рассматривать как набор двудольных графов с заданной степенной последовательностью. (Сетка - это матрица двунаправленности.) Для создания равномерного распределения в этом пространстве можно использовать методы Марковской цепочки Монте-Карло (MCMC): любое решение можно получить из любого другого, используя последовательность «переключателей», которая в вашей формулировке головоломки выглядит как:

(xx)(xx)

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

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

Начало литературе по теме:
https://faculty.math.illinois.edu/~mlavrov/seminar/2018-erdos.pdf
https://arxiv.org/pdf/1701.07101.pdf
https: // www. tandfonline.com/doi/abs/10.1198/016214504000001303

Бен Рейнигер
источник
Это удивительная идея! Я думаю, я понял! Я смешиваю любое известное решение для определенного количества итераций (которое я ожидаю найти в статьях), а затем усредняю ​​по уникальным решениям, надеясь, что большинство из них найдены. Спасибо!
KaPy3141,
2
MCMC - это именно то, что нужно, и я также нашел это: arxiv.org/pdf/1904.03836.pdf
KaPy3141,
@ KaPy3141 Для приведенных выше сумм строк и столбцов моя реализация алгоритма прямоугольного цикла (в препринте arxiv) посещает только 276 уникальных состояний, даже если я запускаю алгоритм целых итераций. 106
Ярле Туфто
Что говорит о том, что перечисление, предложенное @Aksakal, может быть более эффективным.
Ярле Туфто
@JarleTufto, но OP говорит, что существует только 276 уникальных (действительных) состояний; Вы нашли их всех!
Бен Рейнигер
5

Там нет уникального решения

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

Присутствие, Независимое, AS 205

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

Если вы знаете FORTRAN, вы можете использовать этот код, который реализует алгоритм AS 205: Ян Сондерс, алгоритм AS 205. Перечисление таблиц R x C с повторными итогами строк, Прикладная статистика, том 33, номер 3, 1984, страницы 340-352. Это связано с алгоритмом Panefield, на который ссылается @Glen_B.

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

Присутствие, не независимое

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

Считает, независимость

Количество проблем позволяет более чем одну бомбу поместили в камеру, конечно. Частный случай независимых строк и столбцов задачи подсчета прост: где и - маргиналы строк и столбцов. Например, строка и столбец , следовательно, вероятность того, что бомба находится в строке 6 и столбце 3, равна . Вы фактически создали этот дистрибутив в своей первой таблице.Pij=Pi×PjPiPjP6=3/15=0.2P3=3/15=0.2P63=0.04

Считает, Не является независимым, Дискретные Копулы

Чтобы решить проблему подсчета, когда строки и столбцы не являются независимыми, мы могли бы применить дискретные связки. У них есть проблемы: они не уникальны. Это не делает их бесполезными. Итак, я бы попробовал применить дискретные связки. Вы можете найти хороший обзор их в Genest, C. и J. Nešlehová (2007). Учебник по связкам для подсчета данных. Эстин Булл. 37 (2), 475–515.

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

пример

Применим к вашим данным данные связки Кимельдорфа и Сэмпсона, снова предположив, что в ячейку можно поместить более одной бомбы. Связка для параметра зависимости определяется как: Вы можете думать о как аналог коэффициента корреляции.θ

C(u,v)=(uθ+uθ1)1/θ
θ

независимый

Давайте начнем со случая слабой зависимости, , где у нас есть следующие вероятности (PMF), и маргинальные PDF также показаны на панелях справа и внизу:θ=0.000001

введите описание изображения здесь

Вы можете видеть, как в столбце 5 вероятность второй строки имеет в два раза большую вероятность, чем первая строка. Это не так, вопреки тому, что вы, казалось, подразумевали в своем вопросе. Разумеется, все вероятности составляют в сумме 100%, также как маргиналы на панелях соответствуют частотам. Например, столбец 5 на нижней панели показывает 1/3, что соответствует заявленным 5 бомбам из общего количества 15, как и ожидалось.

Положительное соотношение

Для более сильной зависимости (положительной корреляции) с имеем следующее:θ=10

введите описание изображения здесь

Отрицательная корреляция

То же самое для более сильной, но отрицательной корреляции (зависимости) :θ=0.2

введите описание изображения здесь

Вы можете видеть, что все вероятности составляют, конечно, 100%. Также вы можете увидеть, как зависимость влияет на форму PMF. Для положительной зависимости (корреляции) вы получите наивысший PMF, сконцентрированный на диагонали, в то время как для отрицательной зависимости он вне диагонали

Аксакал
источник
Большое спасибо за ваш ответ и ваши интересные ссылки на связки! К сожалению, я никогда не использовал связки, поэтому мне будет трудно найти решение, которое будет приводить в действие только 1 бомбу на клетку, но я обязательно попробую, когда у меня будет лучшее понимание!
KaPy3141
@ KaPy3141, я добавил ссылку на код, который можно использовать для решения проблемы. Это в F90, но относительно просто для преобразования в Python с NumPy
Аксакал
Как связки с каким-то параметром являются решением проблемы? Как вы определяете и как вы узнаете, что это ответ (например, странный эффект в вашем ответе состоит в том, что строки с одинаковой предельной вероятностью дают разные вероятности ячейки). Проблема кажется мне комбинаторной. θθ
Секст Эмпирик
Вы должны были бы соответствовать параметрам процесса. Проблема является чисто комбинаторной, если процесс генерации соответствует ей.
Аксакал
4

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


Точное решение существует, но оно требует большого объема вычислений

Как вы указали в своем вопросе, вы можете выполнить вычислительный поиск по всем возможным распределениям, чтобы определить распределения, которые соответствуют итоговым значениям строки и столбца. Мы можем действовать формально следующим образом. Предположим, что мы имеем дело с сеткой и мы выделяем бомб с помощью простой случайной выборки без замены (поэтому каждая ячейка не может содержать более одной бомбы).n×mb

Пусть будет вектором индикаторных переменных, указывающих, присутствует ли бомба в каждой ячейке, и пусть обозначают соответствующий вектор сумм строк и столбцов. Определите функцию , которая сопоставляет вектор распределения с суммами строк и столбцов.x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs

Цель состоит в том, чтобы определить вероятность каждого вектора распределения при условии знания сумм строк и столбцов. При простой случайной выборке мы имеем , поэтому условная вероятность интереса равна:P(x)1

P(x|s)=P(x,s)P(s)=P(x)I(S(x)=s)xP(x)I(S(x)=s)=I(S(x)=s)xI(S(x)=s)=1|Xs|I(S(x)=s)=U(x|Xs),

где - это множество всех векторов размещения, совместимых с вектором . Это показывает, что (при простой случайной выборке бомб) мы имеем . То есть условное распределение вектора распределения для бомб является равномерным по набору всех векторов распределения, совместимых с наблюдаемыми итогами строк и столбцов. Предельная вероятность бомбы в данной ячейке может быть получена путем маргинализации по этому совместному распределению:Xs{x{0,1}nm|S(x)=s}sx|sU(Xs)

P(xij=1|s)=x:xij=1U(x|Xs)=|XijXs||Xs|.

где - это набор всех векторов выделения с бомбой в ячейке в й строке и м столбце. Теперь в вашей конкретной задаче вы вычислили множество и обнаружили, что , поэтому условная вероятность векторов распределения является одинаковой по всему набору распределений, который вы вычислили (при условии, что вы сделали это правильно). Это точное решение проблемы. Однако вычисление множества требует больших вычислительных ресурсов, поэтому вычисление этого решения может стать невозможным, когда ,Xij{x{0,1}nm|xij=1}ijXs|Xs|=276Xsnmили стать больше.b


В поисках хороших методов оценки

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

Наивный эмпирический оценщик: Оценщик, который вы предложили и использовали в своей зеленой таблице:

P^(xij=1|s)=ribcjbb=ricjb.

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

Бен - Восстановить Монику
источник
Большое спасибо за ваш подробный ответ! На самом деле, на моем зеленом графике уже есть значения до 133%. Приятно знать, что не существует популярного метода для этой проблемы, и это приемлемо для экспериментов на себе! Моя самая точная оценка похожа на «зеленый» подход, но вместо распределения бомб, пропорциональных P (строка) / сумма (P (строки)) * P (c) / сумма (P (столбцы)), я использую мнимый P (r) / (1-P (r)) / сумма (строки) и затем вернуть продукт обратно: P (реальный) = P (imag) / (1 + P (imag). Это заставляет P <1. Теперь, я думаю, мне просто нужно в вычислительном отношении обеспечить (слегка нарушенные) суммы строк / столбцов
KaPy3141,
@ KaPy3141, вы можете использовать значение, которое определенная бомба находится в ячейке (которая не имеет проблемы быть выше 1), а затем описать проблему как вытягивание 15 бомб из этого распределения с условием, что каждая ячейка имеет только значения 0 или 1 (рисунок без замены). Это даст вам вероятность, которая не превышает 1.
Секст Эмпирик