Échantillon avec une probabilité donnée

Question

Je suis tombé sur une question de base en mathématiques/probabilités et je voulais trouver des idées pour améliorer ma solution.

Supposons que l'on vous donne une collection (un alphabet, les chiffres naturels, etc.). Comment vous assurez-vous que vous dessinez une certaine valeur X de cette collection avec une probabilité donnée P?

Je vais vous expliquer ma solution naïve avec un exemple:

Collection = {A, B} 
X = A, P = 1/4 

Nous construisons un tableau v = [A, B, B, B] et nous utilisons une fonction rand pour échantillonner uniformément les indices du tableau, à savoir {0, 1, 2, 3}

Cette approche fonctionne, mais n'est pas efficace: le plus petit P, le plus grand le stockage de la mémoire de v. Par conséquent, je me demandais quelles idées la communauté de stackoverflow pourrait avoir en améliorant ceci.

Merci!

Answer 1

Partitionner l'intervalle [0,1] en intervalles disjoints dont l'union est [0,1]. Créez la taille de chaque partition pour correspondre à la probabilité de sélectionner chaque événement. Ensuite, échantillonnez aléatoirement à partir de [0,1], évaluez le résultat de vos partitions, puis recherchez la sélection correspondant à cet intervalle. Dans votre exemple, ceci produirait les 2 intervalles suivants [0,1/4] et [1/4,1] - générer une valeur uniforme aléatoire à partir de [0,1]. Si votre échantillon se trouve dans le premier intervalle, puis votre sélection X = A, si dans l'autre intervalle, puis X = B.

Answer 2

Votre solution proposée n'est en effet pas géniale, et la manière la plus générale et la plus efficace de la résoudre est celle des états de mathematician1975 (méthode dite CDF inverse). Pour votre problème spécifique, qui est l'échantillonnage multinomial, vous pouvez également utiliser une série de tirages de distributions binomiales pour échantillonner à partir de votre collection. Ceci est souvent plus intuitif si vous n'êtes pas familier avec les méthodes d'échantillonnage.

Si le premier élément de la collection a une probabilité p_1, échantillonner uniformément dans l'intervalle [0-1]. Si l'échantillon est inférieur à p_1, renvoyer l'élément 1. Sinon, renormaliser les résultats restants par 1-p_1 et répéter le processus avec le résultat possible suivant. Après chaque échantillonnage infructueux, renormaliser les résultats restants par la probabilité totale des résultats rejetés, de sorte que la somme des résultats restants soit 1. Si vous arrivez au dernier résultat, renvoyez-le avec la probabilité 1. Le résultat du processus sera aléatoire. selon votre vecteur original.

Cette méthode utilise le fait que les composants individuels d'un multinomial sont distribués binomialement, et tout sous-vecteur du multinomial est également multinomial avec les paramètres donnés par la renormalisation que je décris ci-dessus.