Vous êtes un donjon hébergeant Dungeons & Dragons et un joueur lance 'Spell of Eldritch Chaotic Weather (SECW). Vous n'avez jamais entendu parler de ce sort avant, mais il s'avère qu'il est assez compliqué. Le joueur vous tend un livre dense et dit: «L'effet de ce sort est que l'un des événements de ce livre se produit. Le livre contient un énorme 1000 effets différents, et de plus, les événements ont différentes «probabilités relatives». Le livre vous dit que l'événement le plus probable est «boule de feu»; toutes les probabilités des autres événements sont décrites par rapport à la probabilité de «boule de feu»; par exemple: à la page 155, il est dit que «tempête de canard» est deux fois moins probable que «boule de feu».
Comment allez-vous, le maître du donjon, pour échantillonner un événement aléatoire de ce livre? Voici comment procéder:
L'algorithme d'acceptation-rejet:
1) Lancez un d1000 pour décider d'un événement «candidat».
2) Supposons que l'événement candidat soit 44% plus probable que l'événement le plus probable, «boule de feu». Puis acceptez le candidat avec une probabilité de 44%. (Lancez un d100, et acceptez si le résultat est de 44 ou moins. Sinon, revenez à l'étape 1 jusqu'à ce que vous acceptiez un événement.)
3) L'événement accepté est votre échantillon aléatoire.
L'algorithme d'acceptation-rejet est garanti pour échantillonner à partir de la distribution avec les probabilités relatives spécifiées.
Après de nombreux lancers de dés, vous finissez par accepter un candidat: 'summon frog'. Vous poussez un soupir de soulagement alors que vous pouvez maintenant revenir à la tâche (de routine en comparaison) de gérer la bataille entre les troll-orcs et les elfes-dragons.
Cependant, pour ne pas être en reste, un autre joueur décide de lancer 'Niveau. 2 tempête de cyber-effet arcanique. Pour ce sort, deux effets aléatoires différents se produisent: une attaque générée aléatoirement et un buff de personnage généré aléatoirement. Le manuel de ce sort est si énorme qu'il ne peut tenir que sur un CD. Le joueur vous lance et vous montre une page. Votre mâchoire tombe: l ' entrée pour chaque attaque est à peu près aussi grande que le manuel du sort précédent, car elle répertorie une probabilité relative pour chaque buff d'accompagnement possible
' Cupric Blade '
Le buff le plus probable accompagnant cette attaque est' Hotelling aura '
' Jackal Vision 'est 33% plus susceptible d'accompagner cette attaque que' Hotelling aura '
'Toaster Ears' est 20% plus susceptible d'accompagner cette attaque que 'Hotelling aura'
...
De même, la probabilité d'un le sort d'attaque dépend de la probabilité que le buff se produise.
Il serait justifié de se demander si une distribution de probabilité appropriée peut même être définie compte tenu de cette information. Eh bien, il s'avère que s'il y en a un, il est uniquement spécifié par les probabilités conditionnelles données dans le manuel. Mais comment en tirer un échantillon?
Heureusement pour vous, le CD est livré avec un échantillonneur automatique de Gibbs, car vous auriez à passer une éternité à faire ce qui suit à la main.
Algorithme d'échantillonnage de Gibbs
1) Choisissez un sort d'attaque au hasard
2) Utilisez l'algorithme d'acceptation-rejet pour choisir le buff conditionnel à l'attaque
3) Oubliez le sort d'attaque que vous avez choisi à l'étape 1, choisissez un nouveau sort d'attaque en utilisant l'algorithme d'acceptation-rejet conditionnel au buff de l'étape 2
4) Passez à l'étape 2, répétez indéfiniment (bien que généralement 10000 itérations suffiront)
5) Quel que soit votre algorithme à la dernière itération, c'est votre échantillon.
Vous voyez, en général, les échantillonneurs MCMC ne sont garantis que asymptotiquement pour générer des échantillons à partir d'une distribution avec les probabilités conditionnelles spécifiées. Mais dans de nombreux cas, les échantillonneurs MCMC sont la seule solution pratique disponible.