Où est la bombe: comment estimer la probabilité, compte tenu des totaux des lignes et des colonnes?

14

Cette question est inspirée d'un mini-jeu de Pokemon Soulsilver:

Imaginez qu'il y ait 15 bombes cachées sur cette zone 5x6 (EDIT: maximum 1 bombe / cellule):

Sommes

Maintenant, comment estimeriez-vous la probabilité de trouver une bombe sur un champ spécifique, compte tenu des totaux des lignes / colonnes?

Si vous regardez la colonne 5 (nombre total de bombes = 5), vous pourriez penser: dans cette colonne, la chance de trouver une bombe dans la ligne 2 est deux fois plus élevée que celle dans la ligne 1.

Cette hypothèse (erronée) de proportionnalité directe, qui peut essentiellement être décrite comme replaçant les opérations standard de test d'indépendance (comme dans le Chi-Square) dans le mauvais contexte, conduirait aux estimations suivantes:

Chi-Square

Comme vous pouvez le voir, la proportionnalité directe conduit à des estimations de probabilité supérieures à 100%, et même avant cela, ce serait faux.

J'ai donc effectué une simulation informatique de toutes les permutations possibles qui a conduit à 276 possibilités uniques de placer 15 bombes. (totaux de ligne et de colonne donnés)

Voici la moyenne des 276 solutions: Solution informatique

C'est la bonne solution, mais en raison du travail de calcul exponentiel, je voudrais trouver une méthode d'estimation.

Ma question est maintenant: existe-t-il une méthode statistique établie pour estimer cela? Je me demandais si c'était un problème connu, comment on l'appelait et s'il y avait des papiers / sites Web que vous pourriez recommander!

KaPy3141
la source
1
Approche rapide et facile: pour un nombre plus élevé de lignes et de colonnes, vous pouvez effectuer une simulation Monte Carlo, où vous vérifierez le sous-échantillon aléatoire des configurations possibles qui est inférieur au nombre total de possibilités. Cela vous donnerait une solution approximative.
Tim
1
Je ne comprends pas votre solution informatique. Quels sont les nombres dans les cellules? Ils ne totalisent certainement pas 100%, ce n'est pas du PMF. Ils ne ressemblent pas non plus à CDF, la cellule droite / inférieure n'est pas à 100%
Aksakal
2
@Aksakal Ce sont les probabilités marginales qu'une cellule donnée contienne une bombe. Les nombres s'ajoutent à 15, le nombre total de bombes sur le plateau.
Dougal
2
Si vous supposez que les deux marges sont indépendantes, il est relativement simple de les échantillonner à partir de la distribution des tables conditionnelles aux marges (via l'algorithme de Patefield). Ceci est implémenté dans la distribution standard de R dans r2dtable(et également utilisé par chisq.testet fisher.testdans certaines circonstances).
Glen_b -Reinstate Monica
2
@Glen_b Mais dans l'algorithme de Patefield, le nombre d'événements par cellule n'est pas limité à un.
Jarle Tufto du

Réponses:

4

L'espace de solution (configurations de bombes valides) peut être considéré comme l'ensemble de graphiques bipartites avec une séquence de degrés donnée. (La grille est la matrice de biadjacence.) La génération d'une distribution uniforme sur cet espace peut être approchée en utilisant les méthodes de Markov Chain Monte Carlo (MCMC): chaque solution peut être obtenue à partir de n'importe quelle autre en utilisant une séquence de «commutateurs», qui dans votre formulation de puzzle ressembler:

(xx)(xx)

Il a été prouvé que cela a une propriété de mélange rapide. Donc, en commençant par toute configuration valide et en configurant un MCMC en cours d'exécution pendant un certain temps, vous devriez vous retrouver avec une approximation de la distribution uniforme sur les solutions, que vous pouvez faire une moyenne point par point pour les probabilités que vous recherchez.

Je ne connais que vaguement ces approches et leurs aspects informatiques, mais au moins de cette façon vous évitez d'énumérer les non-solutions.

Un début de la littérature sur le sujet:
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
la source
Voilà une idée incroyable! Je pense que je comprends! Je mélange à travers toute solution connue pour un nombre défini d'itérations (que je m'attends à trouver dans les articles) et ensuite je fais la moyenne des solutions uniques, en espérant que la plupart d'entre elles soient trouvées. Merci beaucoup!
KaPy3141
2
MCMC est exactement la voie à suivre et j'ai également trouvé ceci: arxiv.org/pdf/1904.03836.pdf
KaPy3141
106
Ce qui suggère que l'énumération suggérée par @Aksakal peut être plus efficace.
Jarle Tufto
@JarleTufto, mais OP dit qu'il n'y a que 276 états uniques (valides); vous les avez tous trouvés!
Ben Reiniger
5

Il n'y a pas de solution unique

Je ne pense pas que la vraie distribution de probabilité discrète puisse être récupérée, sauf si vous faites des hypothèses supplémentaires. Votre situation est essentiellement un problème de récupération de la distribution conjointe des marginaux. Il est parfois résolu en utilisant des copules dans l'industrie, par exemple la gestion des risques financiers, mais généralement pour des distributions continues.

Présence, indépendant, AS 205

En cas de problème de présence, pas plus d'une bombe n'est autorisée dans une cellule. Encore une fois, pour le cas particulier de l'indépendance, il existe une solution de calcul relativement efficace.

Si vous connaissez FORTRAN, vous pouvez utiliser ce code qui implémente l'algorithme AS 205: Ian Saunders, l'algorithme AS 205: énumération des tables R x C avec des totaux de lignes répétés, statistiques appliquées, volume 33, numéro 3, 1984, pages 340-352. C'est lié à l'algo de Panefield auquel @Glen_B a fait référence.

Cet algo énumère toutes les tables de présence, c'est à dire passe par toutes les tables possibles où une seule bombe est dans un champ. Il calcule également la multiplicité, c'est-à-dire plusieurs tables qui se ressemblent, et calcule certaines probabilités (pas celles qui vous intéressent). Avec cet algorithme, vous pourrez peut-être exécuter l'énumération complète plus rapidement qu'auparavant.

Présence, non indépendante

L'algorithme AS 205 peut être appliqué à un cas où les lignes et les colonnes ne sont pas indépendantes. Dans ce cas, vous devez appliquer des pondérations différentes à chaque table générée par la logique d'énumération. Le poids dépendra du processus de placement des bombes.

Comtes, indépendance

Pij=Pi×PjPiPjP6=3/15=0.2P3=3/15=0.2P63=0.04

Compte, non indépendant, copules discrètes

Afin de résoudre le problème de comptage lorsque les lignes et les colonnes ne sont pas indépendantes, nous pourrions appliquer des copules discrètes. Ils ont des problèmes: ils ne sont pas uniques. Cela ne les rend cependant pas inutiles. Donc, j'essaierais d'appliquer des copules discrètes. Vous pouvez en trouver un bon aperçu dans Genest, C. et J. Nešlehová (2007). Une introduction aux copules pour les données de comptage. Astin Bull. 37 (2), 475–515.

Les copules peuvent être particulièrement utiles, car elles permettent généralement d'induire explicitement une dépendance ou de l'estimer à partir de données lorsque les données sont disponibles. Je veux dire la dépendance des rangées et des colonnes lors du placement des bombes. Par exemple, cela pourrait être le cas lorsque si la bombe est dans la première rangée, alors il est plus probable qu'elle sera également dans la première colonne.

Exemple

θ

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

Indépendant

θ=0.000001

entrez la description de l'image ici

Vous pouvez voir comment dans la colonne 5 la probabilité de la deuxième ligne a une probabilité deux fois plus élevée que la première ligne. Ce n'est pas faux contrairement à ce que vous sembliez impliquer dans votre question. Toutes les probabilités s'additionnent à 100%, bien sûr, tout comme les marginaux sur les panneaux correspondent aux fréquences. Par exemple, la colonne 5 dans le panneau inférieur montre 1/3 ce qui correspond aux 5 bombes déclarées sur un total de 15 comme prévu.

Correlation positive

θ=10

entrez la description de l'image ici

Corrélation négative

θ=0.2

entrez la description de l'image ici

Vous pouvez voir que toutes les probabilités totalisent 100%, bien sûr. En outre, vous pouvez voir comment la dépendance affecte la forme du PMF. Pour la dépendance positive (corrélation), vous obtenez le PMF le plus élevé concentré sur la diagonale, tandis que pour la dépendance négative, il est hors diagonale

Aksakal
la source
Merci beaucoup pour votre réponse et vos liens intéressants vers les copules! Malheureusement, je n'ai jamais utilisé de copules, il sera donc difficile pour moi de trouver une solution qui n'impose qu'une seule bombe par cellule, mais j'essaierai certainement une fois que j'aurai une meilleure compréhension!
KaPy3141
@ KaPy3141, j'ai ajouté une référence au code que vous pouvez utiliser pour résoudre le problème. C'est en F90, mais relativement simple à convertir en Python avec numpy
Aksakal
θθ
Vous devez adapter les paramètres au processus. Le problème est purement combinatoire si le processus de génération y est cohérent.
Aksakal
4

Votre question n'est pas claire, mais je vais supposer que les bombes sont initialement distribuées via un échantillonnage aléatoire simple sans remplacement sur les cellules (donc une cellule ne peut pas contenir plus d'une bombe). La question que vous avez soulevée demande essentiellement le développement d'une méthode d'estimation pour une distribution de probabilité qui peut être calculée exactement (en théorie), mais qui devient impossible à calculer pour de grandes valeurs de paramètres.


La solution exacte existe, mais elle nécessite beaucoup de calculs

n×mb

x=(x1,...,xnm)s=(r1,...,rn,c1,...,cm)S:xs, qui mappe du vecteur d'allocation aux sommes de ligne et de colonne.

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). C'est-à-dire que la distribution conditionnelle du vecteur d'allocation pour les bombes est uniforme sur l'ensemble de tous les vecteurs d'allocation compatibles avec les totaux de lignes et de colonnes observés. La probabilité marginale d'une bombe dans une cellule donnée peut alors être obtenue en marginalisant sur cette distribution conjointe:

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

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


Recherche de bonnes méthodes d'estimation

Xs

L'estimateur empirique naïf: l'estimateur que vous avez proposé et utilisé dans votre tableau vert est:

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

b

Ben - Réintègre Monica
la source
Merci beaucoup pour votre réponse détaillée! En fait, dans ma carte verte, il y a déjà des valeurs allant jusqu'à 133%. Il est bon de savoir qu'il n'y a pas de méthode populaire pour ce problème et qu'il est acceptable d'expérimenter par soi-même! Mon estimateur le plus précis est similaire à l'approche "verte", mais au lieu d'attribuer les bombes proportionnelles à P (ligne) / somme (P (lignes)) * P (c) / somme (P (cols)), j'utilise un imaginaire P (r) / (1-P (r)) / somme (lignes) et ensuite ramener le produit: P (réel) = P (imag) / (1 + P (imag). Cela force P <1. Maintenant, je suppose que je dois juste appliquer par calcul les sommes (légèrement violées) de ligne / colonne
KaPy3141
@ KaPy3141, vous pouvez utiliser la valeur d'une bombe spécifique dans une cellule (qui n'a pas le problème d'être au-dessus de 1), puis décrire le problème comme un tirage de 15 bombes de cette distribution à condition que chaque cellule ne dispose que valeurs 0 ou 1 (dessin sans remplacement). Cela vous donnera une probabilité qui ne dépasse pas 1.
Sextus Empiricus