Onde está a bomba: Como estimar a probabilidade, dados os totais de linhas e colunas?

14

Esta pergunta é inspirada em um mini-jogo de Pokemon Soulsilver:

Imagine que há 15 bombas escondidas nessa área 5x6 (EDIT: máximo de 1 bomba / célula):

Soma

Agora, como você estimaria a probabilidade de encontrar uma bomba em um campo específico, considerando os totais de linha / coluna?

Se você olhar para a coluna 5 (total de bombas = 5), poderá pensar: Nesta coluna, a chance de encontrar uma bomba na linha 2 é o dobro da chance de encontrar uma na linha 1.

Essa suposição (incorreta) de proporcionalidade direta, que basicamente pode ser descrita como desenhar operações padrão de teste de independência (como no Chi-Square) no contexto errado, levaria às seguintes estimativas:

Chi-Square

Como você pode ver, a proporcionalidade direta leva a estimativas de probabilidade acima de 100%, e mesmo antes disso, estaria errado.

Por isso, realizei uma simulação computacional de todas as permutações possíveis, o que levou a 276 possibilidades únicas de colocar 15 bombas. (dados totais de linha e coluna)

Aqui está a média das 276 soluções: Solução computacional

Esta é a solução correta, mas devido ao trabalho computacional exponencial, eu gostaria de encontrar um método de estimativa.

Minha pergunta agora é: Existe um método estatístico estabelecido para estimar isso? Eu queria saber se este era um problema conhecido, como é chamado e se existem documentos / sites que você poderia recomendar!

KaPy3141
fonte
1
Abordagem rápida e fácil: para um número maior de linhas e colunas, você pode realizar uma simulação de Monte Carlo, onde verificaria a subamostra aleatória das configurações possíveis que é menor que o número total de possibilidades. Daria uma solução aproximada.
Tim
1
Eu não entendo sua solução computacional. Quais são os números nas células? Eles certamente não somam 100%, não é PMF. Eles também não olhar como CDF, a célula direita / inferior não é 100%
Aksakal
2
@Aksakal Estas são as probabilidades marginais de que qualquer célula contém uma bomba. Os números somam 15, o número total de bombas no quadro.
Dougal
2
Se você está assumindo que as duas margens são independentes, é relativamente simples fazer uma amostra da distribuição de tabelas condicionais nas margens (através do algoritmo de Patefield). Isso é implementado na distribuição padrão de R em r2dtable(e também usado por chisq.teste fisher.testem algumas circunstâncias).
Glen_b -Reinstate Monica 24/09/19
2
@ Glen_b Mas no algoritmo de Patefield, o número de eventos por célula não se limita a um.
Jarle Tufto 24/09/19

Respostas:

3

O espaço da solução (configurações válidas de bombas) pode ser visto como o conjunto de gráficos bipartidos com uma determinada sequência de graus. (A grade é a matriz da biadjacência.) A geração de uma distribuição uniforme nesse espaço pode ser abordada usando os métodos de Markov Chain Monte Carlo (MCMC): toda solução pode ser obtida de qualquer outra usando uma sequência de "interruptores", que na sua formulação de quebra-cabeças parece:

(xx)(xx)

Está provado que isso possui uma propriedade de mistura rápida. Portanto, iniciando com qualquer configuração válida e definindo um MCMC em execução por um tempo, você deve terminar com uma aproximação da distribuição uniforme das soluções, que pode ser calculada em termos médios para as probabilidades que procura.

Estou apenas vagamente familiarizado com essas abordagens e seus aspectos computacionais, mas pelo menos dessa maneira você evita enumerar qualquer uma das não soluções.

Um começo para a literatura sobre o 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

Ben Reiniger
fonte
Essa é uma ideia incrível! Eu acho que entendi! Misturo qualquer solução conhecida para uma quantidade definida de iterações (que espero encontrar nos documentos) e depois medio sobre as soluções exclusivas, esperando que a maioria delas seja encontrada. Muito obrigado!
KaPy3141 25/09/19
2
O MCMC é exatamente o caminho a seguir e eu também encontrei o seguinte: arxiv.org/pdf/1904.03836.pdf
KaPy3141
@ KaPy3141 Para as somas de linha e coluna acima, minha implementação do algoritmo de loop retângulo (na pré-impressão do arxiv) visita apenas 276 estados únicos, mesmo que eu execute o algoritmo em até iterações. 106
Jarle Tufto 25/09/19
O que sugere que a enumeração sugerida por @Aksakal pode ser mais eficiente.
Jarle Tufto 25/09/19
@JarleTufto, mas o OP diz que existem apenas 276 estados únicos (válidos); você encontrou todos eles!
Ben Reiniger
5

Não há solução única

Eu não acho que a verdadeira distribuição discreta de probabilidade possa ser recuperada, a menos que você faça algumas suposições adicionais. Sua situação é basicamente um problema de recuperar a distribuição conjunta dos marginais. Às vezes, é resolvido usando cópulas na indústria, por exemplo, gerenciamento de risco financeiro, mas geralmente para distribuições contínuas.

Presença, Independente, AS 205

No problema de presença, não é permitido mais do que uma bomba em uma célula. Novamente, para o caso especial de independência, existe uma solução computacional relativamente eficiente.

Se você conhece o FORTRAN, pode usar este código que implementa o algoritmo AS 205: Ian Saunders, algoritmo AS 205: enumeração de tabelas R x C com totais de linhas repetidos, estatísticas aplicadas, volume 33, número 3, 1984, páginas 340-352. Está relacionado ao algo de Panefield a que @Glen_B se referiu.

Esse algo enumera todas as tabelas de presença, ou seja, passa por todas as tabelas possíveis, onde apenas uma bomba está em um campo. Ele também calcula a multiplicidade, ou seja, várias tabelas com a mesma aparência e calcula algumas probabilidades (não aquelas em que você está interessado). Com esse algoritmo, você poderá executar a enumeração completa mais rapidamente do que antes.

Presença, não independente

O algoritmo AS 205 pode ser aplicado a um caso em que as linhas e colunas não são independentes. Nesse caso, você teria que aplicar pesos diferentes a cada tabela gerada pela lógica de enumeração. O peso dependerá do processo de colocação das bombas.

Conta, independência

O problema da contagem permite mais de uma bomba colocada em uma célula, é claro. O caso especial de linhas e colunas de independentes contagem problema é fácil: Pij=Pi×Pj , onde Pi e Pj são marginais de linhas e colunas. Por exemplo, a fila P6=3/15=0.2 e coluna P3=3/15=0.2 , portanto, a probabilidade de que uma bomba está em linha 6 e a coluna 3 éP63=0.04 . Você realmente produziu essa distribuição em sua primeira tabela.

Contagens, Não independentes, Cópulas discretas

Para resolver o problema das contagens em que linhas e colunas não são independentes, podemos aplicar cópulas discretas. Eles têm problemas: não são únicos. Mas não os torna inúteis. Então, eu tentaria aplicar cópulas discretas. Você pode encontrar uma boa visão geral deles em Genest, C. e J. Nešlehová (2007). Uma cartilha sobre cópulas para dados de contagem. Astin Bull. 37 (2), 475-515.

Cópulas podem ser especialmente úteis, pois geralmente permitem induzir dependência explicitamente ou estimar a partir dos dados quando os dados estão disponíveis. Quero dizer a dependência de linhas e colunas ao colocar bombas. Por exemplo, pode ser o caso quando, se a bomba for uma na primeira linha, é mais provável que também seja a primeira coluna.

Exemplo

Vamos aplicar a cópula de Kimeldorf e Sampson aos seus dados, assumindo novamente que mais de uma bomba pode ser colocada em uma célula. A cópula para um parâmetro de dependência θ é definida como:

C(u,v)=(uθ+uθ1)1/θ
Você pode pensar em θ como um análogo do coeficiente de correlação.

Independente

θ=0.000001

enter image description here

Você pode ver como na coluna 5 a probabilidade da segunda linha tem uma probabilidade duas vezes maior que a primeira linha. Isso não é errado, ao contrário do que você parecia sugerir na sua pergunta. Todas as probabilidades somam 100%, é claro, assim como os marginais nos painéis correspondem às frequências. Por exemplo, a coluna 5 no painel inferior mostra 1/3, o que corresponde às 5 bombas indicadas do total de 15, conforme o esperado.

Correlação positiva

θ=10

enter image description here

Correlação negativa

θ=-0,2

enter image description here

Você pode ver que todas as probabilidades somam 100%, é claro. Além disso, você pode ver como a dependência afeta a forma do PMF. Para dependência positiva (correlação), você obtém o PMF mais alto concentrado na diagonal, enquanto que para a dependência negativa é fora da diagonal

Aksakal
fonte
Muito obrigado pela sua resposta e seus links interessantes para cópulas! Infelizmente, nunca usei cópulas, por isso será difícil encontrar uma solução que aplique apenas 1 bomba por célula, mas definitivamente tentarei quando tiver um melhor entendimento!
KaPy3141
@ KaPy3141, adicionei referência ao código que você pode usar para resolver o problema. É no F90, mas relativamente simples para converter em Python com numpy
Aksakal
θθ
Você precisaria ajustar os parâmetros ao processo. O problema é puramente combinatório se o processo de geração for consistente com ele.
Aksakal
4

Sua pergunta não deixa isso claro, mas vou assumir que as bombas são inicialmente distribuídas por amostragem aleatória simples sem substituição pelas células (para que uma célula não possa conter mais de uma bomba). A questão que você levantou está essencialmente solicitando o desenvolvimento de um método de estimativa para uma distribuição de probabilidade que possa ser computada exatamente (em teoria), mas que se torne computacionalmente inviável para calcular valores de parâmetros grandes.


A solução exata existe, mas é computacionalmente intensiva

n×mb

x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs, que mapeia do vetor de alocação para as somas de linha e coluna.

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). Ou seja, a distribuição condicional do vetor de alocação para as bombas é uniforme sobre o conjunto de todos os vetores de alocação compatíveis com os totais de linha e coluna observados. A probabilidade marginal de uma bomba em uma determinada célula pode ser obtida marginalizando esta distribuição conjunta:

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

Xij{x{0,1}nm|xij=1}ijXs|Xs|=276Xsnmb


Procurando bons métodos de estimativa

Xs

O estimador empírico ingênuo: O estimador que você propôs e usou em sua tabela verde é:

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

b

Restabelecer Monica
fonte
Muito obrigado pela sua resposta detalhada! Na verdade, no meu gráfico verde, já existem valores de até 133%. É bom saber que não existe um método popular para esse problema e é aceitável experimentar por si mesmo! Meu estimador mais preciso é semelhante à abordagem "verde", mas, em vez de alocar as bombas proporcionais a P (linha) / soma (P (linhas)) * P (c) / soma (P (cols)), uso um imaginário P (r) / (1-P (r)) / soma (linhas) e depois devolve o produto: P (real) = P (imag) / (1 + P (imag). Isso força P <1. agora eu acho, eu só preciso computacionalmente fazer cumprir as (ligeiramente violados) somas de linha / coluna.
KaPy3141
@ KaPy3141 você pode usar o valor de uma bomba específica em uma célula (que não tem o problema de estar acima de 1) e depois descrever o problema como um empate de 15 bombas dessa distribuição, com a condição de que cada célula tenha apenas valores 0 ou 1 (desenho sem substituição). Isso fornecerá a você uma probabilidade que não exceda 1. #
Sextus