Comment générer des nombres basés sur une distribution discrète arbitraire?

28

Par exemple, j'ai un ensemble de nombres que je veux générer. Disons qu'ils sont étiquetés de 1 à 3 comme suit.

1: 4%, 2: 50%, 3: 46%

Fondamentalement, les pourcentages sont des probabilités d'apparaître dans la sortie du générateur de nombres aléatoires. J'ai un générateur de nombres pesudorandom qui générera une distribution uniforme dans l'intervalle [0, 1]. Y a-t-il une manière de faire ça?

Il n'y a pas de limites sur le nombre d'éléments que je peux avoir, mais le% totalisera 100%.

distributions FurtiveFelon
la source

2

Je pourrais suggérer de spécifier "... distributions discrètes arbitraires" dans le titre, si telle est votre question. Le cas continu est différent.

David M Kaplan

3

Une manière générique consiste à effectuer une recherche binaire dans une liste des probabilités cumulatives, qui dans cet exemple serait . En moyenne, cela prend sondes par événement de génération. Si aucune probabilité n'est extrêmement faible, vous pouvez obtenir des performances en créant un vecteur de valeurs également espacées dans et (dans une étape de pré-calcul) en attribuant un résultat à chaque valeur. Par exemple, dans cet exemple, vous pouvez créer le vecteur (avec 2 et 3). Générez un uniforme, multipliez par 100 et indexez dans ce vecteur: c'est fait.

(0, 0.04, 0.54, 1.0)

$(0,0.04,0.54,1.0)$

\log (n) / 2

$\log(n)/2$

O (1)

$O(1)$

[0, 1]

$[0,1]$

(1, 1, 1, 1, 2, \dots, 2, 3, \dots, 3)

$(1,1,1,1,2,\ldots,2,3,\ldots,3)$

50

$50$

46

$46$

blanc

Voir aussi ici

Glen_b -Reinstate Monica

Ce lien "ici" renvoie en fait à cette question, @Glen_b ... erreur de copier-coller?

buruzaemon

@buruzaemon merci oui c'était une erreur; Je l'ai corrigé.

Glen_b -Reinstate Monica

26

L'un des meilleurs algorithmes d'échantillonnage à partir d'une distribution discrète est la méthode des alias .

La méthode des alias pré-calcule (efficacement) une structure de données bidimensionnelle pour partitionner un rectangle en zones proportionnelles aux probabilités.

Dans ce schéma à partir du site référencé, un rectangle de hauteur de l' unité a été divisée en quatre types de régions - comme différenciées par la couleur - dans les proportions , , et , en afin d'échantillonner à plusieurs reprises à partir d'une distribution discrète avec ces probabilités. Les bandes verticales ont une largeur (unité) constante. Chacun est divisé en une ou deux pièces seulement. Les identités des pièces et les emplacements des divisions verticales sont stockés dans des tableaux accessibles via l'index des colonnes. $1/2$ $1/3$ $1/12$ $1/12$

Le tableau peut être échantillonné en deux étapes simples (une pour chaque coordonnée) nécessitant de générer seulement deux valeurs uniformes indépendantes et calcul . Cela améliore le calcul nécessaire pour inverser le CDF discret comme décrit dans d'autres réponses ici. $O(1)$ $O(\log(n))$

Lucas
la source

2

Cet algorithme n'est meilleur que si les probabilités sont peu coûteuses à calculer. Par exemple, si

est énorme, il vaut mieux ne pas construire l'arbre entier.

n

$n$

probabilitéislogic

3

+1 Jusqu'à présent, c'est la seule réponse à suggérer et à décrire un algorithme efficace.

whuber

19

Vous pouvez le faire facilement dans R, spécifiez simplement la taille dont vous avez besoin:

sample(x=c(1,2,3), size=1000, replace=TRUE, prob=c(.04,.50,.46))

Dominic Comtois
la source

3

Personnellement, je préférerais un algorithme (ou quelque part pour apprendre les connaissances nécessaires), car j'essaie d'incorporer cela dans une application que je construis :) Merci beaucoup pour votre réponse cependant :)

FurtiveFelon

Hmmm ok ... En savoir un peu plus sur ce que vous voulez faire nous aiderait à vous guider. Pouvez-vous nous en dire plus? (But, contexte, etc.)

Dominic Comtois

C'est pour voter. Par exemple, j'ai un tas de photos et je ne peux en montrer que 6 à un utilisateur à la fois, je voudrais incorporer le "meilleur" à un utilisateur à la fois, et l'utilisateur peut voter pour ou contre chaque photo . La solution la plus simple qui pourrait fonctionner en ce moment est le schéma que j'ai décrit (chaque numéro représente une photo, chaque vote vers le bas diminuerait la probabilité sur cette photo et augmenterait sur tout le reste)

FurtiveFelon

1

@furtivefelon, vous pouvez toujours porter le code à partir de R, o comprendre l'algorithme à partir du code et le réimplémenter.

mpiktas

Je pense que vous pourriez obtenir de bons (meilleurs) conseils sur Stack Overflow, car il existe probablement des solutions bien connues à cet effet spécifique. Je suggère également d'inclure les informations de votre dernier commentaire directement dans votre question.

Dominic Comtois

19

Dans votre exemple, disons que vous dessinez votre valeur uniforme pseudo-aléatoire [0,1] et appelez-la U. Puis sortez:

1 si U <0,04

2 si U> = 0,04 et U <0,54

3 si U> = 0,54

Si les% spécifiés sont a, b, ..., sortez simplement

valeur 1 si U

valeur 2 si U> = a et U <(a + b)

etc.

Essentiellement, nous mappons le% en sous-ensembles de [0,1], et nous savons que la probabilité qu'une valeur aléatoire uniforme tombe dans n'importe quelle plage est simplement la longueur de cette plage. La mise en ordre des plages semble la façon la plus simple, sinon unique, de le faire. Cela suppose que vous posez des questions sur les distributions discrètes uniquement; pour continu, peut faire quelque chose comme "échantillonnage de rejet" ( entrée Wikipedia ).

David M Kaplan
la source

8

L'algorithme est plus rapide si vous triez les catégories par ordre décroissant de probabilité. De cette façon, vous effectuez moins de tests (en moyenne) par nombre aléatoire généré.

jbowman

1

Juste pour ajouter une note rapide sur le tri - cela ne sera efficace que si vous le faites une fois au début d'un schéma d'échantillonnage - donc cela ne fonctionnera pas bien dans les cas où les probabilités sont elles-mêmes échantillonnées dans le cadre d'un schéma global plus large ( ex.

puis

). En triant dans ce cas, vous ajoutez l'opération de tri à chaque itération d'échantillonnage - qui ajoutera

p_{j} \sim Dist

$p_{j}\sim\text{Dist}$

P r (Y = j) = p_{j}

$Pr(Y=j)=p_{j}$

O (n \log (n))

$O(n\log(n))$ temps à chaque itération. Cependant, il peut être utile de trier par une approximation approximative de la taille des probabilités au début dans ce cas.

Probabilogic

4

Supposons qu'il y ait résultats discrets possibles. Vous divisez l'intervalle en sous-intervalles en fonction de la fonction de masse de probabilité cumulative, , pour donner l' intervalle partitionné $m$ $[0,1]$ $F$ $(0,1)$

I_{1} \cup I_{2} \cup \dots \cup I_{m}

$I_{1} \cup I_{2} \cup \cdots \cup I_{m}$

où et . Dans votre exemple, et $I_{j} = (F(j-1), F(j))$ $F(0) \equiv 0$ $m = 3$

I_{1} = (0, .04), I_{2} = (.04, .54), I_{3} = (.54, 1)

$I_1 = (0,.04), \ \ \ \ \ I_2 = (.04,.54), \ \ \ \ \ I_3 = (.54,1)$

puisque et et . $F(1) = .04$ $F(2) = .54$ $F(3) = 1$

Ensuite, vous pouvez générer avec la distribution utilisant l'algorithme suivant: $X$ $F$

(1) générer $U \sim {\rm Uniform}(0,1)$

(2) Si , alors . $U \in I_{j}$ $X = j$

Cette étape peut être accomplie en regardant si est inférieur à chacune des probabilités cumulatives et en voyant où le point de changement (de à ) se produit, ce qui devrait être une question d'utilisation d'un opérateur booléen dans le langage de programmation que vous utilisez et trouver où le premier se produit dans le vecteur. $U$ TRUEFALSEFALSE

Notez que sera dans exactement l'un des intervalles car ils sont disjoints et partitionnent . $U$ $I_{j}$ $[0,1]$

Macro
la source

Ces intervalles ne devraient-ils pas tous être à moitié fermés? Sinon, les frontières entre les intervalles ne sont pas incluses.

{[0, 0.04), [0.04, 0.54), [0.54, 1]}

$\{[0,0.04),\ [0.04,0.54),\ [0.54,1]\}$

naught101

1

pour tout point

(c'est-à-dire que la mesure de Lebesgue de l'intervalle semi-ouvert est la même que celle de l'intervalle ouvert), donc je ne pense pas que cela soit important.

P (U = u) = 0

$P(U=u)=0$

u

$u$

Macro

1

Sur une machine numérique de précision finie, cependant, peut-être un jour avant la fin de l'univers, cela importera ...

jbowman

1

Assez juste, @whuber, voir mon montage.

Macro

1

OK, c'est un algorithme. BTW, pourquoi ne retournez-vous pas quelque chose comme ça min(which(u < cp))? Il serait bon d'éviter également de recalculer la somme cumulée à chaque appel. Avec ce calcul préalable, l'algorithme entier est réduit à min(which(runif(1) < cp)). Ou mieux, parce que l'OP demande de générer des nombres ( pluriel ), vectorisez-le comme n<-10; apply(matrix(runif(n),1), 2, function(u) min(which(u < cp))).

whuber

2

Un algorithme simple consiste à commencer par votre nombre aléatoire uniforme et, dans une boucle, soustrayez d'abord la première probabilité, si le résultat est négatif, vous retournez la première valeur, s'il est toujours positif, vous passez à l'itération suivante et soustrayez la probabilité suivante , vérifiez s'il est négatif, etc.

C'est bien car le nombre de valeurs / probabilités peut être infini mais vous n'avez besoin de calculer les probabilités que lorsque vous vous approchez de ces nombres (pour quelque chose comme générer à partir d'une distribution de Poisson ou d'une distribution binomiale négative).

Si vous avez un ensemble fini de probabilités, mais que vous en générerez de nombreux nombres, il pourrait être plus efficace de trier les probabilités de sorte que vous soustrayiez d'abord la plus grande, puis la deuxième plus grande ensuite et ainsi de suite.

Greg Snow
la source

2

Tout d'abord, permettez-moi d'attirer votre attention sur une bibliothèque python avec des classes prêtes à l'emploi pour la génération de nombres aléatoires entiers ou à virgule flottante qui suivent une distribution arbitraire.

D'une manière générale, il existe plusieurs approches à ce problème. Certains sont linéaires dans le temps, mais nécessitent une grande mémoire, certains s'exécutent en O (n log (n)). Certains sont optimisés pour les nombres entiers et certains sont définis pour les histogrammes circulaires (par exemple: générer des points temporels aléatoires pendant une journée). Dans la bibliothèque mentionnée ci-dessus, j'ai utilisé cet article pour les cas de nombres entiers et cette recette pour les nombres à virgule flottante. Il manque (encore) de support d'histogramme circulaire et est généralement désordonné, mais cela fonctionne bien.

Boris Gorelik
la source

2

J'ai eu le même problème. Étant donné un ensemble où chaque élément a une probabilité et dont les probabilités des éléments se résument à un, je voulais tirer un échantillon efficacement, c'est-à-dire sans trier quoi que ce soit et sans itérer de manière répétée sur l'ensemble .

La fonction suivante tire le plus petit de nombres aléatoires uniformément répartis dans l'intervalle . Soit un nombre aléatoire de . $N$ $[a,1)$ $r$ $[0,1)$

next (N, a) = 1 - (1 - a) \cdot \sqrt[N]{r}

$\begin{equation} \text{next}(N, a) = 1 - (1 - a) \cdot \sqrt[N]{r} \end{equation}$

$(a_i)$ $N$ $N = 10$

$a_0 = \text{next}(10, 0)$
$a_1 = \text{next}(9, a_0)$
$a_2 = \text{next}(8, a_1)$
$\dots$
$a_9 = \text{next}(1, a_8)$

$(a_i)$ $P$ $0 \leq k < |P|$ $p_k \in P$ $a_i$ $k$ $\sum p_0 \dots p_k > a_i$ $p_k$ $a_{i+1}$

$\{(1, 0.04), (2, 0.5), (3, 0.46)\}$ $N = 10$

i a_i k Sum Draw
0 0,031 0 0,04 1
1 0,200 1 0,54 2
2 0,236 1 0,54 2
3 0,402 1 0,54 2
4 0,488 1 0,54 2
5 0,589 2 1,0 3
6 0,625 2 1,0 3
7 0,638 2 1,0 3
8 0,738 2 1,0 3
9 0,942 2 1,0 3

$(1, 2, 2, 2, 2, 3, 3, 3, 3, 3)$

$\text{next}$ $N$ $[a, x)$ $x \leq 1$

casi
la source

Il semble que le problème que vous abordez a brusquement changé dans le deuxième paragraphe, passant d'un échantillon d'une distribution discrète arbitraire à un échantillonnage à partir d'une distribution uniforme . Sa solution ne semble pas pertinente pour la question qui a été posée ici.

whuber

J'ai clarifié la dernière partie.

casi

{1, 2, 3}

$\{1,2,3\}$

J'ai ajouté un exemple. Ma réponse a quelque chose en commun avec la réponse de David M Kaplan ( stats.stackexchange.com/a/26860/93386 ), mais ne nécessite qu'une seule au lieu de N (= taille de l'échantillon) itérations sur l'ensemble, au détriment du dessin N N- e racines. J'ai profilé les deux procédures, et la mienne était beaucoup plus rapide.

casi

a_{j} = \frac{\sum_{i = 1}^{j} \log (u_{i})}{\sum_{i = 1}^{N + 1} \log (u_{i})}

$a_j=\frac{\sum_{i=1}^j \log(u_i)}{\sum_{i=1}^{N+1}\log(u_i)}$

u_{1}, \dots, u_{N + 1}

$u_1,\ldots,u_{N+1}$

Comment générer des nombres basés sur une distribution discrète arbitraire?

Réponses: