Simuler un dé juste avec un dé biaisé

18

Étant donné un dé biaisé de côté , comment générer uniformément un nombre aléatoire dans la plage ? La distribution de probabilité des faces du dé n'est pas connue, tout ce que l'on sait, c'est que chaque face a une probabilité non nulle et que la distribution de probabilité est la même sur tous les lancers (en particulier, les lancers sont indépendants). Il s'agit de la généralisation évidente de résultats équitables avec une matrice injuste .N[1,N]

En termes informatiques, nous avons un oracle représentant les jets de dés: telle sorte que est non nul et indépendant de . Nous recherchons un algorithme déterministe A qui est paramétré par D (ie A peut faire des appels à D ) telle que P (A () = i) = 1 / N . L'algorithme doit se terminer par la probabilité 1, c'est-à-dire que la probabilité que A passe plus de n appels à D doit converger vers 0 comme n \ vers \ infty .D:N[1,N]pi=P(D(k)=i)kADADP(A()=i)=1/NAnD0n

Pour N=2 (simuler une pièce équitable à partir de tours de pièces avec une pièce biaisée), il existe un algorithme bien connu:

  • Répétez "flip deux fois" jusqu'à ce que les deux lancers donnent des résultats distincts ((têtes, queues) ou (queues, têtes)). En d'autres termes, boucle pour k=0.. jusqu'à D(2k+1)D(2k)
  • Retourne 0 si la dernière paire de flips était (têtes, queues) et 1 si c'était (queues, têtes). En d'autres termes, retournez D(2k)k est l'indice auquel la boucle s'est terminée.

Une façon simpliste de fabriquer un dé sans biais à partir d'un dé biaisé consiste à utiliser la méthode de détournement de pièces pour créer une pièce juste, et construire un dé équitable avec un échantillonnage de rejet, comme dans Unbiasing des séquences . Mais est-ce optimal (pour les valeurs génériques de la distribution de probabilité)?

Plus précisément, ma question est: qu'est-ce qu'un algorithme qui nécessite le plus petit nombre attendu d'appels vers l'oracle ? Si l'ensemble des valeurs attendues accessibles est ouvert, quelle est la limite inférieure et quelle est une classe d'algorithmes qui converge vers cette limite inférieure?

Dans le cas où différentes familles d'algorithmes sont optimales pour différentes distributions de probabilités, concentrons-nous sur des dés presque équitables: je recherche un algorithme ou une famille d'algorithmes optimale pour des distributions telles que i,|pi1/N|<ϵ pour certains ϵ>0 .

Gilles 'SO- arrête d'être méchant'
la source
Notez qu'il est important de définir soigneusement l'optimum, car par exemple, vous pourriez recevoir un dé complètement équitable, ou un dé ayant , pour , ou tout autre sorte de mourir. Un schéma optimal pour le dé juste ne nécessite qu'un seul jet, alors que pour l'exemple injuste un schéma optimal en requiert plusieurs. En outre, le supremum de l'optimal sur tous les matrices biaisées possibles est probablement illimité. Donc, vous voudrez peut-être introduire un paramètre, et supposons que par exemple. p i = ϵ / ( N - 1 ) i > 1 max i p i1 - ϵp1=1ϵpi=ϵ/(N1)i>1maxipi1ϵ
usul
@usul je ne comprends pas votre commentaire. Il existe des algorithmes plus efficaces pour certaines valeurs de (par exemple, si ), mais je ne demande que des algorithmes qui ne dépendent pas de . Quel est l'intérêt de ? i , p i = 1 / N ( p i ) ϵpii,pi=1/N(pi)ϵ
Gilles 'SO- arrête d'être méchant'
Comment mesurez-vous l'efficacité d'un algorithme qui ne dépend pas du ? Probablement pour un tel algorithme, il n'y a pas de limite supérieure sur le nombre attendu d'appels nécessaires, en prenant mon exemple de biais biaisé avec . C'est ce que j'entends par "le supremum de l'optimal ... est probablement illimité". Donc, si tous les algorithmes peuvent exiger arbitrairement de nombreux lancers de dés dans l'attente, comment pouvons-nous décider lequel est le meilleur? ϵ 0(pi)ϵ0
usul
@usul Il n'y a pas de limite supérieure sur le nombre de lancers, bien sûr, mais je demande la valeur attendue (c'est-à-dire le nombre moyen de lancers). Pour une distribution donnée , la valeur attendue pour l'algorithme qui crée une pièce équitable et l'utilise pour l'échantillonnage de rejet est finie, n'est-ce pas? Il est vrai que l'attente dépend de la distribution, donc différents (familles de) algorithmes pourraient être optimaux pour différentes distributions. Si c'est le cas, disons que je m'intéresse aux dés presque équitables. (pi)
Gilles 'SO- arrête d'être méchant'
Pas exactement la question, mais seriez-vous prêt à rechercher uniquement un résultat proche de l'uniforme (en / distance de variation totale)? Si tel est le cas, en fonction de la garantie que vous demandez à la distribution d'origine, cela est étudié dans un article récent (en soumission), sous le nom "améliorant d'échantillonnage pour l'uniformité" - qui montre notamment que vous pouvez obtenir des nombres de tirages indépendants de pour de distance à distance . N 1 ε ε 1N1εε
Clement C.

Réponses:

3

L'article suivant répond à une variante proche de cette question: La construction efficace d'une séquence aléatoire non biaisée, Elias 1972 .

La question semble être la suivante: étant donné l'accès à cette source indépendante biaisée, émettez une séquence de nombres aléatoires en (notez la différence par rapport à votre question dans laquelle un seul symbole de sortie est demandé). Comme la longueur de la sortie souhaitée va à l'infini, l '"efficacité" du schéma dans le document (qui semble être une généralisation naturelle de von Neumann) passe à , ce qui signifie, je crois, qu'une entrée avec entropie est convertie en une sortie d'entropie approchant .1 h h[1,N]1hh

La question semble beaucoup mieux se comporter lorsqu'elle est formulée de cette façon, plutôt que de demander un seul chiffre de sortie, parce que, par exemple, si nous tirons échantillons et obtenons une sortie avec beaucoup d'informations (par exemple, tous les symboles d'entrée sont distincts) , alors nous pouvons utiliser toutes ces informations pour produire de nombreux symboles de sortie, alors qu'avec la question telle que formulée ici, toute information au-delà de celle utilisée pour produire un symbole de sortie est perdue.NNN

Je crois que le schéma prend à plusieurs reprises tirages, examine la séquence et lui mappe certaines sorties ou la chaîne vide. Peut-être existe-t-il un moyen d'améliorer le schéma de votre question en examinant les préfixes et en vous arrêtant si nous avons "suffisamment" d'informations pour afficher un symbole? Je ne sais pas.N

usul
la source
Je n'ai pas cherché de travaux ultérieurs ou de travaux citant le document, donc je ne sais pas mais peut-être que quelqu'un a amélioré le schéma, en a proposé un autre, a répondu à votre question, etc.
usul
2

La méthode que vous décrivez pour généralise. Nous utilisons que toutes les permutations de sont également probables même avec une matrice biaisée (puisque les rouleaux sont indépendants). Par conséquent, nous pouvons continuer à rouler jusqu'à ce que nous voyions une telle permutation comme les derniers rouleaux et sortir le dernier rouleau.[ 1 .. N ] NN=2[1..N]N

Une analyse générale est délicate; il est clair, cependant, que le nombre attendu de rouleaux croît rapidement en car la probabilité de voir une permutation à une étape donnée est faible (et non indépendante des étapes avant et après, donc délicate). Il est toutefois supérieur à pour fixe , de sorte que la procédure se termine presque sûrement (c'est-à-dire avec probabilité ).0 N 1N0N1

Pour fixe, nous pouvons construire une chaîne de Markov sur l'ensemble des vecteurs Parikh qui se résument à , résumant les résultats des derniers rouleaux, et déterminer le nombre attendu d'étapes jusqu'à ce que nous atteignions pour la première fois . C'est suffisant car toutes les permutations qui partagent un vecteur Parikh sont également probables; les chaînes et les calculs sont plus simples de cette façon.N N ( 1 , , 1 )NNN(1,,1)

Supposons que nous sommes en état avec . Ensuite, la probabilité de gagner un élément (ie le prochain lancer est ) est toujours donnée parn i = 1 v iN i iv=(v1,,vN)i=1nviNii

Pr[gain i]=pi .

D'un autre côté, la possibilité de supprimer un élément de l'histoire est donnée pari

Prv[drop i]=viN

chaque fois que (et sinon) précisément parce que toutes les permutations avec le vecteur de Parikh sont également probables. Ces probabilités sont indépendantes (puisque les rôles sont indépendants), nous pouvons donc calculer les probabilités de transition comme suit:0 vi=1nvi=N0v

Pr[v(v1,,vj+1,,vN)]={Pr[gain j],v<N0, else,Pr[v(v1,,vi1,vj+1,,vN)]={0,v<Nvi=0vj=NPrv[drop i]Pr[gain j], else andPr[vv]={0,v<Nvi0Prv[drop i]Pr[gain i], else;

toutes les autres probabilités de transition sont nulles. Le seul état absorbant est , le vecteur Parikh de toutes les permutations de .[ 1 .. N ](1,,1)[1..N]

Pour la chaîne de Markov résultante¹ estN=2

Chaîne de Markov pour N = 2
[ source ]

avec nombre prévu d'étapes jusqu'à absorption

Esteps=2p0p12+i3(p0i1p1+p1i1p0)i=1p0+p02p0p02,

en utilisant pour simplification que . Si maintenant, comme suggéré, pour certains , alorsp 0 = 1p1=1p0ϵ[0,1p0=12±ϵϵ[0,12)

Esteps=3+4ϵ214ϵ2 .

Pour et les distributions uniformes (le meilleur des cas), j'ai effectué les calculs avec l'algèbre informatique²; comme l'espace d'état explose rapidement, des valeurs plus grandes sont difficiles à évaluer. Les résultats (arrondis vers le haut) sontN6

NormalPlot LogPlot
Les graphiques montrent en fonction de ; à gauche un tracé régulier et à droite un tracé logarithmique.NEstepsN

La croissance semble être exponentielle mais les valeurs sont trop faibles pour donner de bonnes estimations.

Quant à la stabilité face aux perturbations du on peut regarder la situation pour : N = 3piN=3

Nombre prévu d'étapes pour N = 3 et choix différents
Le graphique montre en fonction de et ; naturellement, .p 0 p 1 p 2 = 1 - p 0 - p 1Estepsp0p1p2=1p0p1

En supposant des images similaires pour un plus grand (le noyau se bloque en calculant les résultats symboliques même pour ), le nombre prévu d'étapes semble être assez stable pour tous, sauf les choix les plus extrêmes (presque tout ou aucune masse à certains ).N = 4 p iNN=4pi

A titre de comparaison, simuler une pièce de monnaie (par exemple en attribuant les résultats de la matrice à et aussi uniformément que possible), l'utiliser pour simuler une pièce de monnaie équitable et enfin effectuer un échantillonnage par rejet au niveau du bit nécessite au plus0 1ϵ01

2logN3+4ϵ214ϵ2

vous attendez - vous devriez probablement vous en tenir à cela.


  1. Comme la chaîne absorbe en les bords marqués en gris ne sont jamais traversés et n'influencent pas les calculs. Je les inclue uniquement à des fins d'exhaustivité et d'illustration.(11)
  2. Implémentation dans Mathematica 10 ( Notebook , Bare Source ); désolé, c'est ce que je sais pour ce genre de problèmes.
Raphael
la source
1

Juste un petit commentaire concernant le cas . Prenez un grand nombre et échantillonnez lancers du dé. Si vous avez têtes, vous pouvez extraire bits. En supposant que le dé est biaisé , la quantité moyenne d'informations est Pour obtenir cette estimation, utilisez le fait que la variable binomiale est concentrée autour de avec l'estimation . Lorsque devient plus grand, nous obtenons le taux optimal deN=2mmklog(mk)p

k=0mpk(1p)mk(mk)log(mk)mh(p).
k=pmlog(mk)mh(k/m)mh(p) par pièce (c'est optimal pour des raisons de théorie de l'information, par exemple la propriété d'équipartition asymptotique).

Vous pouvez utiliser la même méthode pour le général et vous obtiendrez probablement le même . Ces algorithmes ne sont optimaux que dans la limite, et il peut y avoir des algorithmes atteignant la limite plus rapidement que ceux-ci. En fait, j'ai négligé de calculer la vitesse de convergence - cela pourrait être un exercice intéressant.H ( p )NH(p)

Yuval Filmus
la source
1

Je risquerais la réponse suivante.

Le cas spécifique de 2 que vous avez mentionné ci-dessus est le cas spécifique de l'expansion (où est prob de tête et prob de queue) qui vous donne un terme Cela signifie que vous pouvez obtenir pour un cas et pour l'autre cas. Vous devrez répéter l'échantillonnage jusqu'à ce que vous voyiez ou (tête-queue ou queue-tête) En les utilisant comme simulation, vous donnerez une probabilité égale. p q 2 p q p q q p p q q p(p+q)2pq2pqpqqppqqp

Lorsque vous avez l'expansion qui vous donne le terme . Dans ce cas, vous faites la même chose, en échantillonnant jusqu'à ce que vous voyiez les 3 résultats , , dans un certain ordre dans 3 essais consécutifs.( p + q + r ) 3 p q r q p rN=3(p+q+r)3pqrqpr

La même chose s'applique au cas général. En réfléchissant bien, je dois dire que le cas de 2 est le meilleur cas où l'on peut régler les choses dans l'extension. Lorsque il existe 6 séquences différentes pour et il existe de nombreux autres termes dans l'expansion. Je me sentirais assez mal à l'aise avec d'autres termes où il y a beaucoup plus de résultats.p q rN=3pqr

.

Supplémentaire:

Cela me fait penser à l'idée de simplement échantillonner beaucoup pour estimer la probabilité de chaque résultat des dés. Dans ce cas le plus simple d'un modèle à une couche sans couche cachée (un modèle connu), nous pouvons établir une limite pour conclure que l'estimation converge rapidement. En fait, la limite de Chernoff nous montre que l'erreur diminue de façon exponentielle à mesure que l'échantillonnage augmente (linéairement).

Maintenant qu'une bonne estimation des probabilités pour chaque côté des dés est connue, il existe de nombreuses options. Une option est que nous pouvons refaire l'expansion ci-dessus, mais cette fois, nous pouvons potentiellement utiliser de nombreux autres termes dans l'expansion qui ont la même valeur que (ou tout terme qui vous utilisez comme séquence basée). Ce sera un peu plus efficace car plus de termes dans l'expansion seront utilisés. Mais j'avoue que je ne sais pas si cela se traduira par le plus petit nombre d'appels à l'oracle pour avoir une garantie sur les conditions préalables (telles que le paramètre de confiance), si elles sont données.i=1i=npi

Néanmoins, cette approche est une réponse à différentes saveurs de la question. La question demande une parfaite impartialité garantie au prix d'un échantillonnage potentiellement important (quoique de faible probabilité). Cette approche utilise uniquement un échantillonnage fini avec un paramètre lié à la confiance. Je ne pense donc pas que cette approche soit appropriée à cette question même si elle est très intéressante.

InforméA
la source