Structure de données pour les dés chargés?

Supposons que j'ai un dé chargé à n côtés où chaque côté k a une certaine probabilité p _k de remonter quand je le lance. Je suis curieux de savoir s'il existe un bon algorithme pour stocker ces informations de manière statique (c'est-à-dire pour un ensemble fixe de probabilités) afin de pouvoir simuler efficacement un jet aléatoire du dé.

Actuellement, j'ai une solution O (lg n) pour ce problème. L'idée est de stocker une table de la probabilité cumulée des k premiers côtés pour tous les k, de générer un nombre réel aléatoire dans la plage [0, 1) et d'effectuer une recherche binaire sur la table pour obtenir le plus grand index dont le cumul la valeur n'est pas supérieure à la valeur choisie. J'aime plutôt 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é monte toujours ou que les valeurs sont uniformément réparties, il est possible de générer le résultat du roulement dans O (1) en utilisant une approche naïve, bien que ma solution prendra toujours logarithmicallh de nombreuses étapes.

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

EDIT : 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 par Vose de la méthode d'alias donne Θ (n) temps de prétraitement et O (1) temps par jet de dé, ce qui est vraiment impressionnant. J'espère que c'est un ajout utile aux informations contenues dans les réponses!

Vous recherchez la méthode d'alias qui fournit une méthode O (1) 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) unique . Vous pouvez le trouver documenté au chapitre 3 (PDF) de "Génération de Variations Aléatoires Non Uniformes" de Luc Devroye.

L'idée est de prendre votre tableau de probabilités p _k et de produire trois nouveaux tableaux à n éléments, q _k , a _k et b _k . Chaque q _k est une probabilité entre 0 et 1, et chaque a _k et b _k est un entier 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 retourne a _i sinon retourne b _i . Le travail dans la méthode des alias consiste à trouver comment produire q _k , a _k et b _k .

Utilisez un arbre de recherche binaire équilibré (ou une recherche binaire dans un tableau) et obtenez la complexité O (log n). Avoir un nœud pour chaque résultat de dé et avoir les clés comme 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)

La bonne chose à propos de cette solution est qu'elle est très simple à mettre en œuvre mais qu'elle présente toujours une bonne complexité.

Je pense à granuler votre tableau.

Au lieu d'avoir un tableau avec le cumul pour chaque valeur de dé, vous pouvez 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'index (normalisé par xN) comme valeur cumulative et, dans chaque «emplacement» du tableau, stockez le jet de dés potentiel si cet index apparaît.

Peut-être pourrais-je 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 choisirai 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 index.

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

Il existe de nombreuses façons de générer un entier aléatoire avec une distribution personnalisée (également appelée distribution discrète ). Le choix dépend de nombreux facteurs, y compris le nombre d'entiers parmi lesquels choisir, la forme de la distribution et si la distribution changera au fil du temps.

L'un des moyens les plus simples de choisir un entier avec une fonction de pondération personnalisée f(x)est la méthode d' échantillonnage par rejet . Ce qui suit suppose que la valeur la plus élevée possible de fest max. La complexité temporelle de l'échantillonnage de rejet est constante en moyenne, mais dépend fortement de la forme de la distribution et présente le pire des cas de fonctionner éternellement. Pour choisir un entier dans [1, k] à l’aide de l’échantillonnage par rejet:

1. Choisissez un entier aléatoire uniforme idans [1, k].
2. Avec probabilité f(i)/max, revenez i. 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 constante ou logarithmique), mais vous obligent souvent à précalculer les poids dans une étape de configuration et à 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. Bon nombre de ces algorithmes ont été introduits après 2011 et incluent:

• la structure succincte des données 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 rouleau de dés à chargement rapide (2020).

D'autres algorithmes incluent la méthode d'alias (déjà mentionnée dans votre article), l'algorithme Knuth – Yao, la structure de données MVN, etc. Voir ma section « Une note sur les algorithmes de choix pondérés » pour une enquête.