Answers · The mathematics underneath
How do you build a random walk whose long-run distribution is a distribution you choose?
In shortPropose a symmetric random move; accept moves to heavier target weight outright and moves to lighter weight with probability equal to the weight ratio, then run the chain.
Use a symmetric proposal and an accept/reject step: if the proposed point has at least as much target weight as the current point, move there; if it has less, move there with probability equal to the ratio of the two weights. The chain then has the chosen distribution as its stationary distribution, because the rule satisfies detailed balance with that distribution. You need only the weights up to an unknown multiplicative constant, so the total that cannot be computed never appears.
The proposal \(q_{ij}\) is any rule with \(q_{ij}=q_{ji}\); picking a neighbour uniformly, or adding a symmetric random nudge, both qualify. The proposal decides which moves are attempted and how large a step can be. The acceptance factor decides how often an attempted move is kept. If a move is refused, the chain records another visit to the current point; that refusal is part of the transition matrix and is essential, because without it the chain would not spend enough time in the heavy places.
Take four positions in a line with weights 1, 2, 4, 8. Their total is 1+2+4+8=15, so the chosen shares are 1/15=0.0667, 2/15=0.1333, 4/15=0.2667 and 8/15=0.5333. Propose one of the two neighbours with equal probability. From the first to the second the ratio is 2/1=2, so the move is accepted with certainty. From the second to the first the ratio is 1/2=0.5, so it is accepted with chance 0.5 and refused with chance 0.5. A refusal is not a retry: the chain stays where it is for that hop, which is how it spends extra time at the heavier positions. From the third to the second the chance is 2/4=0.5; from the fourth to the third it is 4/8=0.5. Uphill moves are never refused.
| position | weight w_i | share w_i/15 |
|---|---|---|
| first | 1 | 1/15 = 0.0667 |
| second | 2 | 2/15 = 0.1333 |
| third | 4 | 4/15 = 0.2667 |
| fourth | 8 | 8/15 = 0.5333 |
Why detailed balance is enough
Let \(i\) have weight \(w_i\) and \(j\) have weight \(w_j\), and suppose \(w_j \le w_i\). The proposal chance \(q\) is the same in both directions. The chance of going from \(i\) to \(j\) is \(q\) times \(w_j/w_i\), so the probability flux is \((w_i/Z)q(w_j/w_i)=qw_j/Z\). The chance of going from \(j\) to \(i\) is \(q\) times 1, so the reverse flux is \((w_j/Z)q=qw_j/Z\). The two fluxes are equal. If \(w_i \le w_j\) the same calculation with \(i\) and \(j\) exchanged gives the same equality, and equal weights are immediate. That equality is detailed balance, and summing it over \(i\) gives that the target is stationary.
The guess that fails
The natural guess is that any transition rule with the target as a stationary distribution will do. Stationary is not enough. A deterministic cycle on a finite set with equal weights leaves the uniform distribution stationary, but the walk never settles: it is periodic, and the long-run distribution as a limit does not exist. Likewise a rule that can never propose a move into a separated region leaves the target stationary on the part it can reach and gives zero long-run chance to the rest. You need the proposal to make every point of positive target weight reachable, which is irreducibility, and you need no fixed cycle, which is aperiodicity. The accept/reject step supplies detailed balance, but it does not by itself supply reachability or remove periodicity.
If the proposal is not symmetric, replace the ratio \(w_j/w_i\) by \((w_j q_{ji})/(w_i q_{ij})\). The cancellation of the unknown total remains, because any constant \(c\) multiplying every weight cancels: \((c u_j)/(c u_i)=u_j/u_i\). A proposal that puts zero chance on a move makes that move impossible, so irreducibility must be checked on the graph of proposals, not assumed from the target having positive weight everywhere. If the target gives zero weight to some point, the chain should not visit it; the acceptance ratio is zero for a move into it.
The construction promises correctness, not speed. It says the chain rests at the chosen distribution, and under irreducibility and aperiodicity it approaches it from any start, but it gives no bound on how long that takes. Early hops are biased by the starting point, successive recorded positions are dependent, and a target with separated regions can trap the walk in one of them for an exponentially long time as the valley between them deepens. In that case the output can look settled and still be missing much of the distribution. The acceptance rule is already right; all practical work is about the proposal and the running time.
Worth keeping
- Accepting a move with probability the ratio of target weights, capped at one, makes the target distribution stationary by detailed balance.
- Only ratios of target weights appear, so an unknown normalising constant cancels.
- Detailed balance does not by itself guarantee convergence; the chain must also be irreducible and aperiodic.
Where this goes next
This question is one step of Markov Chains, a course that works through its subject from the beginning. The page that teaches this part of it is Building a Chain to Reach a Chosen Distribution, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- What's the difference between a state the chain keeps returning to and one it eventually leaves forever?A state the chain keeps returning to is in a closed group it cannot leave; any other state is left forever after finitely many visits.
- Why does a Markov chain eventually forget which state it started in?A finite Markov chain forgets its starting point when it has one closed class and no cycle, because two runs from different starts share chance that the rule cannot separate again.
- What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
- How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.
- How do you find the parabola that best fits a function near a point?Match the function's height, slope and bending at the chosen point; those three conditions single out exactly one parabola.
- Why does a test for a rare disease give so many false positives if the test is accurate?A positive result means the test fired, not that you are likely to be ill; when the disease is rare, healthy people vastly outnumber ill ones, so a small false-alarm rate on them swamps the few true cases.