Un multinomial (1 / n,…, 1 / n) peut-il être caractérisé comme un Dirichlet discrétisé (1, .., 1)?

24

Cette question est donc un peu compliquée, mais je vais inclure des graphiques colorés pour compenser cela! D'abord le contexte puis les questions.

Contexte

Supposons que vous ayez une distribution multinomiale à n dimensions avec des probailites égales sur les n catégories. Soit π=(π1,,πn) les comptes normalisés ( c ) de cette distribution, c'est-à-dire:

(c1,,cn)Multinomial(1/n,,1/n)πi=cin

Maintenant, la distribution sur π a un support sur le n simplex mais avec des étapes discrètes. Par exemple, avec n=3 cette distribution a le support suivant (les points rouges):

entrez la description de l'image ici

Une autre distribution avec un support similaire est la distribution de Dirichlet à n dimensions ( 1 , , 1 ) , c'est-à-dire une distribution uniforme sur le simplexe unitaire. Par exemple, voici des tirages aléatoires à partir d'un Dirichlet en 3 dimensions ( 1 , 1 , 1 ) :Dirichlet(1,,1)Dirichlet(1,1,1)

entrez la description de l'image ici

J'avais maintenant l'idée que la distribution de partir de la distribution multinomiale ( 1 / n , , 1 / n ) pouvait être caractérisée comme des tirages d'un Dirichlet ( 1 , , 1 ) qui sont discrétisés vers le support discret de π . La discrétisation que j'avais en tête (et qui semble bien fonctionner) est de prendre chaque point du simplexe et de le "arrondir" au point le plus proche qui est dans le support de ππMultinomial(1/n,,1/n)Dirichlet(1,,1)ππ. Pour le simplexe tridimensionnel, vous obtenez la partition suivante où les points de chaque zone colorée doivent «arrondir» au point rouge le plus proche:

entrez la description de l'image ici

Puisque la distribution de Dirichlet est uniforme, la densité / probabilité résultante pour chacun des points est proportionnelle à la surface / au volume qui est "arrondi" à chaque point. Pour les cas bidimensionnels et tridimensionnels, ces probabilités sont:

entrez la description de l'image ici ( ces probabilités proviennent de simulations de Monte Carlo )

Il semble donc que, au moins pour les dimensions 2 et 3, la distribution de probabilité résultante de la discrétisation de de cette manière particulière soit la même que la distribution de probabilité pour π . C'est le résultat normalisé d'une distribution multinomiale ( 1 / n , , 1 / n ) . J'ai également essayé en 4 dimensions et cela semble fonctionner.Dirichlet(1,,1)πMultinomial(1/n,,1/n)

Des questions)

Donc ma principale question est:

Lors de la discrétisation d'un Dirichlet uniforme de cette manière particulière, la relation avec un valable pour d'autres dimensions? La relation est-elle valable du tout? (J'ai seulement essayé cela en utilisant la simulation Monte Carlo ...)Multinomial(1/n,,1/n)

De plus, je me demande:

  • Si cette relation est vraie, est-ce un résultat connu? Et y a-t-il une source que je peux citer pour cela?
  • Si cette discrétisation d'un Dirichlet uniforme n'a pas cette relation avec le Multinomial. Y a-t-il une construction similaire qui a?

Un certain contexte

Ma raison de poser cette question est que je regarde la similitude entre le Bootstrap non paramétrique et le Bootstrap bayésien, et puis cela est apparu. J'ai également remarqué que le motif sur les zones colorées du simplexe tridimensionnel ci-dessus ressemble (et devrait être) un diagramme de Voronoi. Une façon (j'espère) que vous pouvez y penser est une séquence du Triangle / Simpex de Pascal ( http://www.math.rutgers.edu/~erowland/pascalssimplices.html ). Où la taille des zones colorées suit la deuxième rangée du triangle de Pascal dans le cas 2D, la troisième rangée du tétraèdre Pascal dans le cas 3D, et ainsi de suite. Cela expliquerait le lien avec la distribution multinomiale, mais ici je suis vraiment en eau profonde ...

Rasmus Bååth
la source
2
amusement! (Comme d'habitude.) Mais la connexion aux chaussettes me manque.
Xi'an
Eh bien, j'ai commencé à dessiner des chaussettes avec remplacement. Mais ensuite j'ai commencé à penser au Boostrap Bayésien, une chose a conduit à l'autre, et c'est comme ça que je me suis retrouvé ici :)
Rasmus Bååth
2
@ Xi'an c'est peut-être des chaussettes plutôt que des chiots qui devraient devenir la mascotte bayésienne?
Tim

Réponses:

14

Ces deux distributions sont différentes pour tout .n4

Notation

Je vais redimensionner votre simplexe d'un facteur , de sorte que les points du réseau aient des coordonnées entières. Cela ne change rien, je pense juste que cela rend la notation un peu moins lourde.n

Soit le ( n - 1 ) -simplex, donné comme la coque convexe des points ( n , 0 , , 0 ) , ..., ( 0 , , 0 , n ) dans R n . En d'autres termes, ce sont les points où toutes les coordonnées sont non négatives et où la somme des coordonnées est égale à n .S(n1)(n,0,,0)(0,,0,n)Rnn

Soit l'ensemble des points du réseau , c'est-à-dire les points en S où toutes les coordonnées sont intégrales.ΛS

Si est un point de réseau, nous laissons V P désigner sa cellule de Voronoï , définie comme les points de S qui sont (strictement) plus proches de P que de tout autre point de Λ .PVPSPΛ

Nous mettons deux distributions de probabilité que nous pouvons mettre sur . La première est la distribution multinomiale, où le point ( un 1 , . . . , Un n ) a la probabilité 2 - n n ! / ( a 1 ! a n ! ) . L'autre nous appellerons le modèle Dirichlet , et il attribue à chaque P X une probabilité proportionnelle au volume de V P .Λ(a1,...,an)2nn!/(a1!an!)PΛVP

Justification très informelle

Je prétends que le modèle multinomial et le modèle de Dirichlet donnent des distributions différentes sur , chaque fois que n 4 .Λn4

Pour voir cela, considérons le cas , et les points A = ( 2 , 2 , 0 , 0 ) et B = ( 3 , 1 , 0 , 0 ) . Je prétends que V A et V B sont congruents via une translation par le vecteur ( 1 , - 1 , 0 , 0 ) . Cela signifie que V A et V Bn=4A=(2,2,0,0)B=(3,1,0,0)VAVB(1,1,0,0)VAVBont le même volume, et donc que et B ont la même probabilité dans le modèle de Dirichlet. En revanche, dans le modèle multinomial, elles ont des probabilités différentes ( 2 - 44 ! / ( 2 ! 2 ! ) Et 2 - 44 ! / 3 ! ), Et il s'ensuit que les distributions ne peuvent pas être égales.AB2-44!/(2!2!)2-44!/3!

Le fait que et V B sont congruents découle de l'affirmation plausible mais non évidente (et quelque peu vague) suivante:VUNEVB

Allégation plausible : la forme et la taille de ne sont affectées que par les "voisins immédiats" de P , (c'est-à-dire les points dans Λ qui diffèrent de P par un vecteur qui ressemble ( 1 , - 1 , 0 , , 0 ) , où le 1 et le - 1 peuvent être ailleurs)VPPΛP(1,-1,0,,0)1-1

Il est facile de voir que les configurations des "voisins immédiats" de et B sont les mêmes, et il s'ensuit alors que V A et V B sont congruents.UNEBVUNEVB

Dans le cas , on peut jouer le même jeu, avec A = ( 2 , 2 , n - 4 , 0 , , 0 ) et B = ( 3 , 1 , n - 4 , 0 , , 0 ) , par exemple.n5UNE=(2,2,n-4,0,,0)B=(3,1,n-4,0,,0)

Je ne pense pas que cette affirmation soit complètement évidente, et je ne vais pas le prouver, au lieu d'une stratégie légèrement différente. Cependant, je pense que c'est une réponse plus intuitive pour expliquer pourquoi les distributions sont différentes pour .n4

Une preuve rigoureuse

Prenez et B comme dans la justification informelle ci-dessus. Il suffit de prouver que V A et V B sont congruents.UNEBVUNEVB

Étant donné , nous définirons W P comme suit: W P est l'ensemble des points ( x 1 , , x n ) S , pour lesquels max 1 i n ( a i - p i ) - min 1 i n ( a iP=(p1,,pn)ΛWPWP(X1,,Xn)S . (De manière plus digestible: Soit v i = a i - p i . W P est l'ensemble des points pour lesquels la différence entre le plus haut et le plus bas v i est inférieure à 1.)max1jen(uneje-pje)-min1jen(uneje-pje)<1vje=uneje-pjeWPvje

Nous allons montrer que .VP=WP

Étape 1

Revendication: .VPWP

Ceci est assez facile: Supposons que est pas en W P . Soit v i = x i - p i , et supposons (sans perte de généralité) que v 1 = max 1 i n v i , v 2 = min 1 i n v i . v 1 - v 2X=(X1,,Xn)WPvje=Xje-pjev1=max1jenvjev2=min1jenvje Puisquen i = 1 v i = 0 , nous savons également que v 1 > 0 > v 2 .v1-v21je=1nvje=0v1>0>v2

Soit maintenant . Puisque P et X ont tous deux des coordonnées non négatives, il en est de même de Q , et il s'ensuit que Q S , et donc Q Λ . Par contre, d i s t 2 ( X , P ) - d i s t 2Q=(p1+1,p2-1,p3,,pn)PXQQSQΛ . Ainsi, X est au moins aussi proche de Q à P ,sorte que X V P . Cela montre (en prenant des compléments) quedist2(X,P)dist2(X,Q)=v12+v22(1v1)2(1+v2)2=2+2(v1v2)0XQPXVP .VpWP

Étape 2

Affirmation : Les sont disjoints deux à deux.WP

Supposons le contraire. Soient et Q = ( q 1 , ... , q n ) soient des points distincts en Λ , et que X W PW Q . Puisque P et Q sont distincts et tous deux dans Λ , il doit y avoir un indice ip iq i + 1 et un oùP=(p1,,pn)Q=(q1,,qn)ΛXWPWQPQΛipiqi+1 . Sans perte de généralité, nous supposons que p 1q 1 + 1 et p 2q 2 - 1 . En réorganisant et en additionnant, nous obtenons q 1 - p 1 + p 2 - q 22 .piqi1p1q1+1p2q2-1q1-p1+p2-q22

Considérez maintenant les nombres et x 2 . Du fait que X W P , nous avons x 1 - p 1 - ( x 2 - p 2 ) < 1 . De même, X W Q implique que x 2 - q 2 - ( x 1 - q 1 ) < 1 . En les additionnant ensemble, nous obtenons q 1 - pX1X2XWPX1-p1-(X2-p2)<1XWQX2-q2-(X1-q1)<1 , et nous avons une contradiction.q1-p1+p2-q2<2

Étape 3

Nous avons montré que , et que les W P sont disjoints. Le V P couvre S jusqu'à un ensemble de mesure zéro, et il s'ensuit que W P = V P (jusqu'à un ensemble de mesure zéro). [Puisque W P et V P sont tous deux ouverts, nous avons en fait W P = V P exactement, mais ce n'est pas essentiel.]VPWPWPVPSWP=VPWPVPWP=VP

Maintenant, nous avons presque terminé. Considérons les points et B = ( 3 , 1 , n - 4 , 0 , , 0 ) . Il est facile de voir que W A et W B sont congruents et se traduisent l'un l'autre: la seule façon dont ils pourraient différer, c'est si la frontière de S (autre que les faces sur lesquelles AUNE=(2,2,n-4,0,,0)B=(3,1,n-4,0,,0)WUNEWBSUNEet mentent tous les deux) `` couperaient '' W A ou W B mais pas l'autre. Mais pour atteindre une telle partie de la frontière de S , nous aurions besoin de changer une coordonnée de A ou B d'au moins 1, ce qui serait suffisant pour garantir de nous sortir de W A et W B de toute façon. Ainsi, même si S semble différent des points de vue A et B , les différences sont trop éloignées pour être captées par les définitions de W A et W B , et donc WBWUNEWBSUNEBWUNEWBSUNEBWUNEWB et W B sont congruents.WUNEWB

Il s'ensuit alors que et V B ont le même volume, et donc le modèle de Dirichlet leur attribue la même probabilité, même s'ils ont des probabilités différentes dans le modèle multinomial.VUNEVB

ZH Liu
la source
Wow, rigoureux! Merci! Donc, la légère correspondance que j'espérais était accidentelle, je suppose ...
Rasmus Bååth