Esta pregunta está inspirada en un mini-juego de Pokemon Soulsilver:

Imagine que hay 15 bombas ocultas en esta área de 5x6 (EDITAR: máximo 1 bomba / celda):

Ahora, ¿cómo calcularía la probabilidad de encontrar una bomba en un campo específico, dados los totales de fila / columna?

Si observa la columna 5 (bombas totales = 5), entonces podría pensar: dentro de esta columna, la posibilidad de encontrar una bomba en la fila 2 es el doble de la posibilidad de encontrar una en la fila 1.

Este supuesto (incorrecto) de proporcionalidad directa, que básicamente se puede describir como dibujar operaciones estándar de prueba de independencia (como en Chi-Square) en el contexto incorrecto, conduciría a las siguientes estimaciones:

Como puede ver, la proporcionalidad directa conduce a estimaciones de probabilidad superiores al 100%, e incluso antes de eso, estaría mal.

Así que realicé una simulación computacional de todas las permutaciones posibles que condujo a 276 posibilidades únicas de colocar 15 bombas. (totales de fila y columna dados)

Aquí está el promedio sobre las 276 soluciones:

Esta es la solución correcta, pero debido al trabajo computacional exponencial, me gustaría encontrar un método de estimación.

Mi pregunta ahora es: ¿Existe un método estadístico establecido para estimar esto? Me preguntaba si este era un problema conocido, cómo se llama y si hay documentos / sitios web que podría recomendar.

El espacio de solución (configuraciones de bomba válidas) puede verse como el conjunto de gráficos bipartitos con una secuencia de grados dada. (La cuadrícula es la matriz de biadjacencia). La generación de una distribución uniforme en ese espacio se puede abordar utilizando los métodos de Markov Chain Monte Carlo (MCMC): cada solución se puede obtener de cualquier otra mediante una secuencia de "interruptores", que en su formulación de rompecabezas parece:

$$\begin{pmatrix} x & - \\ - & x \end{pmatrix} \to \begin{pmatrix} - & x \\ x & - \end{pmatrix}$$

Se ha demostrado que esto tiene una propiedad de mezcla rápida. Entonces, comenzando con cualquier configuración válida y configurando un MCMC que se ejecute por un tiempo, debe terminar con una aproximación de la distribución uniforme en las soluciones, que puede promediar puntualmente para las probabilidades que está buscando.

Solo estoy vagamente familiarizado con estos enfoques y sus aspectos computacionales, pero al menos de esta manera evitas enumerar cualquiera de las no soluciones.

Un comienzo a la literatura sobre el tema:
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

No hay una solución única

No creo que se pueda recuperar la verdadera distribución de probabilidad discreta, a menos que haga algunas suposiciones adicionales. Su situación es básicamente un problema de recuperación de la distribución conjunta de los marginales. A veces se resuelve mediante el uso de cópulas en la industria, por ejemplo, la gestión de riesgos financieros, pero generalmente para distribuciones continuas.

Presencia, independiente, AS 205

En el problema de presencia, no se permite más de una bomba en una celda. Nuevamente, para el caso especial de independencia, existe una solución computacional relativamente eficiente.

Si conoce FORTRAN, puede usar este código que implementa el Algoritmo AS 205: Ian Saunders, Algoritmo AS 205: Enumeración de tablas R x C con totales repetidos de fila, Estadísticas aplicadas, Volumen 33, Número 3, 1984, páginas 340-352. Está relacionado con algo de Panefield al que @Glen_B se refirió.

Este algo enumera todas las tablas de presencia, es decir, pasa por todas las tablas posibles donde solo hay una bomba en un campo. También calcula la multiplicidad, es decir, varias tablas que se ven iguales, y calcula algunas probabilidades (no las que le interesan). Con este algoritmo, puede ejecutar la enumeración completa más rápido que antes.

Presencia, no independiente

El algoritmo AS 205 se puede aplicar a un caso donde las filas y columnas no son independientes. En este caso, tendría que aplicar diferentes pesos a cada tabla generada por la lógica de enumeración. El peso dependerá del proceso de colocación de bombas.

Condes, independencia

$P_i^j=P_i\times P^j$$P_i$$P^j$$P_6=3/15=0.2$$P^3=3/15=0.2$$P_6^3=0.04$

Cuenta, no independiente, cópulas discretas

Para resolver el problema de conteo donde las filas y columnas no son independientes, podríamos aplicar cópulas discretas. Tienen problemas: no son únicos. Sin embargo, no los hace inútiles. Entonces, trataría de aplicar cópulas discretas. Puede encontrar una buena descripción de ellos en Genest, C. y J. Nešlehová (2007). Una cartilla sobre cópulas para datos de conteo. Astin Bull. 37 (2), 475–515.

Las cópulas pueden ser especialmente útiles, ya que generalmente permiten inducir explícitamente la dependencia o estimarla a partir de los datos cuando los datos están disponibles. Me refiero a la dependencia de filas y columnas al colocar bombas. Por ejemplo, podría ser el caso cuando si la bomba es una en la primera fila, entonces es más probable que también sea una en la primera columna.

Ejemplo

$\theta$

$$C(u,v)=(u^{-\theta}+u^{-\theta}-1)^{-1/\theta}$$ $\theta$

Independiente

$\theta=0.000001$

Puede ver cómo en la columna 5 la probabilidad de la segunda fila tiene una probabilidad dos veces mayor que la primera fila. Esto no está mal, al contrario de lo que parecía implicar en su pregunta. Todas las probabilidades suman 100%, por supuesto, al igual que los márgenes en los paneles coinciden con las frecuencias. Por ejemplo, la columna 5 en el panel inferior muestra 1/3 que corresponde a 5 bombas declaradas del total de 15 como se esperaba.

Correlacion positiva

$\theta=10$

Correlación negativa

$\theta=-0.2$

Puede ver que todas las probabilidades suman 100%, por supuesto. Además, puede ver cómo la dependencia afecta la forma del PMF. Para la dependencia positiva (correlación) se obtiene el mayor PMF concentrado en la diagonal, mientras que para la dependencia negativa está fuera de la diagonal

Su pregunta no deja esto claro, pero voy a suponer que las bombas se distribuyen inicialmente mediante muestreo aleatorio simple sin reemplazo sobre las celdas (por lo que una celda no puede contener más de una bomba). La pregunta que ha planteado es esencialmente el desarrollo de un método de estimación para una distribución de probabilidad que pueda calcularse exactamente (en teoría), pero que no sea computacionalmente factible para calcular valores de parámetros grandes.

---

La solución exacta existe, pero es computacionalmente intensiva

$n \times m$$b$

$\mathbf{x} = (x_1,...,x_{nm})$$\mathbf{s} = (r_1, ..., r_n, c_1, ..., c_m)$$S: \mathbf{x} \mapsto \mathbf{s}$, que se asigna desde el vector de asignación a las sumas de fila y columna.

$\mathbb{P}(\mathbf{x}) \propto 1$

$$\begin{equation} \begin{aligned} \mathbb{P}(\mathbf{x} | \mathbf{s}) = \frac{\mathbb{P}(\mathbf{x}, \mathbf{s})}{\mathbb{P}(\mathbf{s})} &= \frac{\mathbb{P}(\mathbf{x}) \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s})}{\sum_\mathbf{x} \mathbb{P}(\mathbf{x}) \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s})} \\[6pt] &= \frac{\mathbb{I}(S(\mathbf{x}) = \mathbf{s})}{\sum_\mathbf{x} \mathbb{I}(S(\mathbf{x}) = \mathbf{s})} \\[6pt] &= \frac{1}{|\mathscr{X}_\mathbf{s}|} \cdot \mathbb{I}(S(\mathbf{x}) = \mathbf{s}) \\[6pt] &= \text{U}(\mathbf{x} | \mathscr{X}_\mathbf{s}), \\[6pt] \end{aligned} \end{equation}$$

$\mathscr{X}_\mathbf{s} \equiv \{ \mathbf{x} \in \{ 0, 1\}^{nm} | S(\mathbf{x}) = \mathbf{s} \}$$\mathbf{s}$$\mathbf{x} | \mathbf{s} \sim \text{U}(\mathscr{X}_\mathbf{s})$. Es decir, la distribución condicional del vector de asignación para las bombas es uniforme sobre el conjunto de todos los vectores de asignación compatibles con los totales observados de fila y columna. La probabilidad marginal de una bomba en una celda dada se puede obtener al marginar sobre esta distribución conjunta:

$$\begin{equation} \begin{aligned} \mathbb{P}(x_{ij} = 1 | \mathbf{s}) = \sum_{\mathbf{x}: x_{ij} = 1} \text{U}(\mathbf{x} | \mathscr{X}_\mathbf{s}) = \frac{|\mathscr{X}_{ij} \cap \mathscr{X}_\mathbf{s}|}{|\mathscr{X}_\mathbf{s}|}. \end{aligned} \end{equation}$$

$\mathscr{X}_{ij} \equiv \{ \mathbf{x} \in \{ 0, 1\}^{nm} | x_{ij} = 1 \}$$i$$j$$\mathscr{X}_\mathbf{s}$$|\mathscr{X}_\mathbf{s}| = 276$$\mathscr{X}_\mathbf{s}$$n$$m$$b$

---

Buscando buenos métodos de estimación

$\mathscr{X}_\mathbf{s}$

El ingenuo estimador empírico: el estimador que ha propuesto y utilizado en su tabla verde es:

$$\hat{\mathbb{P}}(x_{ij} = 1 | \mathbf{s}) = \frac{r_i}{b} \cdot \frac{c_j}{b} \cdot b = \frac{r_i \cdot c_j}{b}.$$

$b$