Building a Chain to Reach a Chosen Distribution
Last timeChains That Look the Same Run Backwards
A distribution you can write down but cannot draw from. The construction here builds a chain that rests exactly there using only ratios, and promises correctness without promising any speed.
Every lesson so far has handed you a rule and asked where it ends up. This one
hands you the destination and asks for a rule.
That sounds like a curiosity. It is the reason this subject is in constant use.
Why anyone needs this
Suppose you can write down how much weight a distribution gives to any single
point, but you cannot divide by the total, because the total is a sum over more
points than exist atoms to count them with. This is the ordinary situation. A
model with fifty yes or no variables has more configurations than that.
So the weights are known and the distribution is not, and drawing a sample from
it directly is out of reach. But a chain that rests at that distribution can be
run. Start it anywhere, step it forward, and note down where it is from time to
time. Those notes are samples from the target.
The whole difficulty has been moved into one question: how do you build a hop
rule whose resting distribution is the one you were given? Detailed balance is
the answer, because it is the only version of the resting condition simple
enough to engineer.
- the chance of accepting a proposed move from where you are, i, to the proposed point j. If it is not accepted you stay at i, and that counts as a hop
- take the smaller of the two. If the proposed point has at least as much weight, the ratio is at least one, the smaller is one, and the move is accepted with certainty. Only downhill moves are ever refused
- the ratio of the target weight at the proposed point to the weight where you are. This is the only place the target appears anywhere in the construction, and it is a ratio, so any constant multiplying every weight cancels and the unknown total never has to be computed
| step | where the walk is | what gets proposed | the ratio of weights | what happens |
|---|---|---|---|---|
| 1 | position two, weight four | position three, weight eight | two, so at least one | accepted outright, move to three |
| 2 | position three, weight eight | off the right hand end | no such point | refused, stay at three, count the hop |
| 3 | position three, weight eight | position two, weight four | one half | a coin comes up against it, stay at three |
| 4 | position three, weight eight | position two, weight four | one half | this time it is accepted, move to two |
| 5 | position two, weight four | position one, weight two | one half | accepted, move to one |
| 6 | position one, weight two | position two, weight four | two, so at least one | accepted outright, move to two |
It rests where it was asked to
The check is short enough to do here, and worth doing, because it is the only
thing that makes any of this legitimate.
Take two points and let the second have the smaller weight. The flow from the
first to the second is the first weight, times the chance of proposing that
move, times one, since the move is downhill and accepted outright. The flow back
is the second weight, times the same proposal chance since proposals are
symmetric, times the ratio of the first weight to the second. But the second
weight times that ratio is the first weight.
Both flows come to the same thing. Detailed balance holds, so the target rests.
The other case is this one with the names exchanged, and equal weights need no
argument at all.
The lesson stops here
3 more paragraphs to go
You have read the opening. The rest of the argument, the problems that check whether it landed, and the lines worth keeping at the end all come with a plan.
The first lesson of every course in the library reads the whole way through, free, so you can see exactly what the rest of them are.
See the planThe contentsThis is the reading half
Starting the course gives you your own copy of it. Every idea on every page has problems standing under it, marked with a reason rather than a tick, and any sentence you do not believe can be opened and argued with. None of that can happen on a page nobody owns.
The contents