You are a dungeonmaster hosting Dungeons & Dragons and a player casts 'Spell of 
Eldritch Chaotic Weather (SECW).  You've never heard of this spell before, but it turns out it is quite involved.  The player hands you a dense book and says, 'the effect of this spell is that one of the events in this book occurs.'  The book contains a whopping 1000 different effects, and what's more, the events have different 'relative probabilities.'  The book tells you that the most likely event is 'fireball'; all the probabilities of the other events are described relative to the probability of 'fireball'; for example: on page 155, it says that 'duck storm' is half as likely as 'fireball.'

How are you, the Dungeon Master, to sample a random event from this book?  Here's how you can do it: 

_The accept-reject algorithm:_

1) Roll a d1000 to decide a 'candidate' event.

2) Suppose the candidate event is 44% as likely as the most likely event, 'fireball'.  Then _accept_ the candidate with probability 44%.  (Roll a d100, and accept if the roll is 44 or lower.  Otherwise, go back to step 1 until you accept an event.)

3) The accepted event is your random sample.

The accept-reject algorithm is guaranteed to sample from the distribution with the specified relative probabilities.

After much dice rolling you finally end up accepting a candidate: 'summon frog'.  You breathe a sigh of relief as you now you can get back to the (routine in comparison) business of handling the battle between the troll-orcs and dragon-elves.

However, not to be outdone, another player decides to cast 'Level. 2 arcane cyber-effect storm.' For this spell, two different random effects occur: a randomly generated attack, and a randomly generated character buff.  The manual for this spell is so huge that it can only fit on a CD.  The player boots you up and shows you a page.  Your jaw drops: the _entry_ for each attack is about as large a the manual for the previous spell, because it lists a relative probability for each possible accompanying buff

> 'Cupric Blade'

> The most likely buff accompanying this attack is 'Hotelling aura'

> 'Jackal Vision' is 33% as likely to accompany this attack as 'Hotelling aura'

> 'Toaster Ears' is 20% as likely to accompany this attack as 'Hotelling aura'

...

Similarly, the probability of a particular attack spell occurring depends on the probability of the buff occurring.

It would be justified to wonder if a proper probability distribution can even be _defined_ given this information.  Well, it turns out that if there is one, it is uniquely specified by the conditional probabilities given in the manual.  But how to sample from it?

Luckily for you, the CD comes with an automated Gibbs' sampler, because you would have to spend an eternity doing the following by hand.

_Gibbs' sampler algorithm_

1) Choose an attack spell randomly

2) Use the accept-reject algorithm to choose the buff conditional on the attack

3) Forget the attack spell you chose in step 1.
Choose a new attack spell using the accept-reject algorithm conditional on the buff in step 2

4) Go to step 2, repeat forever (though usually 10000 iterations will be enough)

5) Whatever your algorithm has at the last iteration, is your sample.

You see, in general, MCMC samplers are only _asymptotically_ guaranteed to generate samples from a distribution with the specified conditional probabilities.  But in many cases, MCMC samplers are the only practical solution available.