The Bias Engine

Every degree stays fixed. The sampling bias stays too.

A degree-preserving graph walk can look nicely random long before it is close to uniform. This example is small enough to enumerate, so its distribution can be compared with the actual target.

The graph-sampling experiment with finite-walk bias and a corrected draw — 01 The 70-graph example after 16 switch steps. The finite walk remains biased even though every degree is preserved. One corrected draw is shown beside the starting graph.

What to look for

The family has 70 labelled graphs: ten pairs of triangles and sixty six-cycles. The screen compares the finite walk with a corrected law and the exact uniform triangle-event probability of 1/7.

Under the hood

Enumerated graph states, finite transition laws and a residual correction.

Five small graph families and independently checked finite probabilities.

There are 70 labelled degree-two graphs in this example: ten pairs of triangles and sixty six-cycles. A uniform draw should land on the triangle event one time in seven.