Des structures de données pour des dés chargés ?

Question

Supposons que j'ai un n -un dé chargé sur une face, où chaque face  k a une certaine probabilité  p _{<em>k </em>} d'apparaître quand je le roule. Je suis curieux de savoir s'il existe une bonne structure de données pour stocker ces informations de manière statique (c'est-à-dire pour un ensemble fixe de probabilités), afin de pouvoir simuler efficacement un lancer de dé aléatoire.

Actuellement, j'ai un programme O(lg  n ) pour résoudre ce problème. L'idée est de stocker un tableau de la probabilité cumulative de la première k  côtés pour tous  k puis générer un nombre réel aléatoire dans la plage [0, 1] et effectuer une recherche binaire sur la table pour obtenir le plus grand indice dont la valeur cumulée n'est pas supérieure à la valeur choisie.

J'aime assez cette solution, mais il semble étrange que le runtime ne prenne pas en compte les probabilités. En particulier, dans les cas extrêmes où un côté sort toujours ou que les valeurs sont uniformément distribuées, il est possible de générer le résultat du jet en O(1) en utilisant une approche naïve, alors que ma solution prendra toujours un nombre logarithmique de pas.

Quelqu'un a-t-il des suggestions sur la façon de résoudre ce problème d'une manière qui soit en quelque sorte "adaptative" dans son exécution ?

Mise à jour : Sur la base des réponses à cette question, j'ai rédigé un article décrivant de nombreuses approches de ce problème ainsi que leurs analyses. Il semble que l'implémentation de la méthode des alias par Vose donne ( n ) de prétraitement et O(1) de temps par jet de dé, ce qui est vraiment impressionnant. J'espère que cela constitue un complément utile aux informations contenues dans les réponses !

Answer 1

Vous êtes à la recherche de la méthode d'alias qui fournit un O(1) méthode pour générer une distribution de probabilité discrète fixe (en supposant que vous pouvez accéder aux entrées d'un tableau de longueur n en temps constant) avec une configuration O(n) en une seule fois. Vous pouvez la trouver documentée dans chapitre 3 (PDF) de "Génération de variables aléatoires non-uniformes" par Luc Devroye.

L'idée est de prendre votre tableau de probabilités p _k et produisent trois nouveaux tableaux à n éléments, q _k , a _k et b _k . Chaque q _k est une probabilité comprise entre 0 et 1, et chaque a _k et b _k est un nombre entier compris entre 1 et n.

Nous générons des nombres aléatoires entre 1 et n en générant deux nombres aléatoires, r et s, entre 0 et 1. Soit i = floor(r*N)+1. Si q _i < s alors retourner a _i sinon, retournez b _i . Le travail dans la méthode des alias consiste à trouver comment produire q _k , a _k et b _k .

Answer 2

Utilisez un arbre de recherche binaire équilibré (ou une recherche binaire dans un tableau) et obtenez une complexité O(log n). Ayez un nœud pour chaque résultat de dé et faites en sorte que les clés soient l'intervalle qui déclenchera ce résultat.

function get_result(node, seed):
    if seed < node.interval.start:
        return get_result(node.left_child, seed)
    else if seed < node.interval.end:
        // start <= seed < end
        return node.result
    else:
        return get_result(node.right_child, seed)

L'avantage de cette solution est qu'elle est très simple à mettre en œuvre tout en restant complexe.

Answer 3

Je pense à granuler votre table.

Au lieu d'avoir un tableau avec le cumul pour chaque valeur du dé, vous pourriez créer un tableau d'entiers de longueur xN, où x est idéalement un nombre élevé pour augmenter la précision de la probabilité.

Remplissez ce tableau en utilisant l'indice (normalisé par xN) comme valeur cumulative et, dans chaque "emplacement" du tableau, stockez le lancer de dé éventuel si cet indice apparaît.

Je pourrais peut-être vous expliquer plus facilement avec un exemple :

En utilisant trois dés : P(1) = 0,2, P(2) = 0,5, P(3) = 0,3

Créez un tableau, dans ce cas je vais choisir une longueur simple, disons 10. (c'est-à-dire x = 3,33333)

arr[0] = 1,
arr[1] = 1,
arr[2] = 2,
arr[3] = 2,
arr[4] = 2,
arr[5] = 2,
arr[6] = 2,
arr[7] = 3,
arr[8] = 3,
arr[9] = 3

Ensuite, pour obtenir la probabilité, il suffit de randomiser un nombre entre 0 et 10 et d'accéder simplement à cet indice.

Cette méthode peut perdre en précision, mais en augmentant x, la précision sera suffisante.

Answer 4

Il existe de nombreuses façons de générer un entier aléatoire avec une distribution personnalisée (également connue sous le nom de distribution discrète ). Le choix dépend de nombreux facteurs, notamment du nombre d'entiers parmi lesquels choisir, de la forme de la distribution et de l'évolution de la distribution dans le temps.

Une des façons les plus simples de choisir un entier avec une fonction de pondération personnalisée f(x) est le échantillonnage de rejet méthode. Ce qui suit suppose que la plus haute valeur possible de f est max et chaque poids est égal ou supérieur à 0. La complexité temporelle de l'échantillonnage par rejet est constante en moyenne, mais dépend fortement de la forme de la distribution et peut, dans le pire des cas, s'éterniser. Pour choisir un nombre entier dans [1, k ] en utilisant l'échantillonnage par rejet :

1. Choisissez un entier aléatoire uniforme i dans [1, k ].
2. Avec une probabilité de f(i)/max , retour i . Sinon, passez à l'étape 1. (Par exemple, si tous les poids sont des entiers supérieurs à 0, choisissez un entier aléatoire uniforme dans [1, max ] et si ce nombre est f(i) ou moins, renvoyer i ou sinon, passez à l'étape 1).

D'autres algorithmes ont un temps d'échantillonnage moyen qui ne dépend pas tellement de la distribution (généralement constant ou logarithmique), mais ils nécessitent souvent de précalculer les poids dans une étape de configuration et de les stocker dans une structure de données. Certains d'entre eux sont également économiques en termes de nombre de bits aléatoires qu'ils utilisent en moyenne. Beaucoup de ces algorithmes ont été introduits après 2011, et ils comprennent

• La structure de données succincte de Bringmann-Larsen (" Succinct Sampling from Discrete Distributions ", 2012),
• la recherche multi-niveaux de Yunpeng Tang ("An Empirical Study of Random Sampling Methods for Changing Discrete Distributions", 2019), et
• le site Rouleau à dés à chargement rapide (2020).

D'autres algorithmes comprennent le méthode d'alias (déjà mentionné dans votre article), l'algorithme de Knuth-Yao, la structure de données MVN, et plus encore. Voir ma section " Choix pondéré avec remplacement " pour une enquête.