
Encyclopaedia of DesignTheory: Topic Essay 
A printable PDF version of this document is available.
Now we can choose a random structure of a certain type in some situations. If we can count the structures, then we may suppose there are N altogether; choose a random number x from [0,N1], skip over the first x structures in the count, and take the next one. If each structure is determined by a sequence of choices, and making these choices uniformly gives the uniform distribution, then we can make the choices at random as long as we know how many choices there are at each stage.
For example, how can we choose a random permutation µ of the set {1,...,n}? The image 1µ of 1 can be any of 1,...,n; choose this image at random. Then 2µ can be any of 1,...,n except 1µ; choose a random number x from 1,...,n1 and add one if x>=1µ, then set 2µ=x. Continuing in this way gives the required random permutation.
Choosing a random graph on n vertices is even easier: simply decide with a single coin toss whether each pair of vertices is joined by an edge or not. (Indeed, the number of graphs is 2^{n(n1)/2}, and counting them is equivalent to choosing one at random.)
In other cases, e.g. Latin squares, we don't even know how many structures there are, so choosing one at random cannot be done by these methods; we need a new idea.
sum_{j=1}^{m} p_{ij}=1.The interpretation is that we have a marker on one of the states; at a certain moment it moves to a new state, where the probability of moving from state s_{i} to state s_{j} is p_{ij}. The displayed equation just reflects the fact that the marker is bound to move to some state!
We can now iterate this procedure. The marker starts out on some state, possibly chosen at random from an arbitrary probability distribution. At each positive integer time it makes a transition according to the specification above. We are interested in how it behaves in the long term. There are two extremes of behaviour:
For most interesting chains, we don't have either of these extremes, but instead, under certain hypotheses the marker's position approaches a limiting distribution as the number of transitions increases.
The displayed equation above can be rewritten as Pj^{T}=j^{T}, where j is the allone vector, j=(1,1,...,1). So 1 is a right eigenvalue of P. Since the left and right eigenvalues of a matrix are the same, there is a vector q=(q_{1},...,q_{m}) such that qP=q.
It can be proved that we can choose q to have all its entries nonnegative, so we can normalise the entries so that
sum_{i=1}^{m} q_{i}=1.Then we can interpret q as a probability distribution on the states. Suppose that the marker starts in this distribution. Then after one transition, its probability of being in state s_{j} is
sum_{i=1}^{m} q_{i} p_{ij} = q_{j},that is, the same as before the transition! So if the marker starts in the distribution q, then it remains in this distribution. So q is certainly a candidate for a limiting distribution.
We need a couple of conditions on the chain to guarantee good limiting behaviour and rule out cases like the first example above. Let p_{ij}^{n} be the probability of moving from state s_{i} to state s_{j} after n transitions. (Exercise: this is just the (i,j) entry of the matrix P^{n}.) The chain is said to be irreducible if, for any two states s_{i} and s_{j}, there exists n such that p_{ij}^{n}>0, that is, it is possible to move from s_{i} to s_{j}. The chain is said to be aperiodic if, for any state s_{i}, the greatest common divisor of the set
{n : p_{ii}^{n}>0}is equal to 1.
Theorem Let P be an irreducible and aperiodic Markov chain, and q the normalised left eigenvector of P with eigenvalue 1. Then, starting from an arbitrary initial distribution, the distribution after n steps approaches q as n tends to infinity.
The particular type of Markov chain we consider is the random walk on an undirected graph. The states are the vertices of the graph, and a transition consists of choosing an edge through the vertex on which the marker sits (all edges being equally likely) and moving to the other end of this edge. In other words, p_{ij} is the reciprocal of the valency of the ith vertex v_{i} if v_{i} and v_{j} are adjacent, and is zero if they are nonadjacent. It is not hard to see that the random walk is irreducible if and only if the graph is connected, and is aperiodic if and only if the graph is not bipartite. (Since the graph is undirected, we can always return to the start vertex after 2 steps with nonzero probability.)
With our fair coin we can do a random walk on a graph, since we have to choose among a number of edges at each step, giving each edge the same probability.
It is also simple to compute the limiting state. We claim that the vector whose ith component is the valency of v_{i} is a left eigenvector with eigenvalue 1. This is an easy exercise; here is a heuristic argument. If the probability of starting at v_{i} is ck_{i}, where k_{i} is the valency of v_{i} and c is a constant, then the probability of passing along any given edge is c, and so the probability of arriving at v_{j} is ck_{j}.
In other words, if a graph is connected and nonbipartite, then the random walk on that graph has the property that, in the limit, the probability of being at any vertex is proportional to its valency. In particular, if the graph is regular, then the limiting distribution is uniform.
In order to use this method to choose a random Latin square, we need to find a set of "moves" connecting up the set of all Latin squares of given order. This was done by Jacobson and Matthews [1]; we outline their method.
First we reformulate the definition of a Latin square. We regard it as a function from N^{3} to {0,1}, where N={1,...,n}, having the property that, for any given x,y in N, we have
sum_{z in N} f(x,y,z)=1,with similar equations for the sum over y (for given x,z) and the sum over x (for given y,z). The interpretation is that f(x,y,z)=1 if and only if the entry in row x and column y of the array is z.
We also have to enlarge the space in which we walk, by admitting also "improper" Latin squares. Such a square is a function from N^{3} to {1,0,1} having the properties that it takes the value 1 exactly once, and that the above equation and the two similar equations hold. Effectively, we allow one "negative" entry which must be compensated by additional "positive" entries.
To take one step in the Markov chain starting at a function f, do the following:
f(x',y,z)=f(x,y',z)=f(x,y,z')=1.If f is proper, these points are unique; if f is improper, there are two choices for each of them.
Jacobson and Matthews showed that the graph which has the set of all proper and improper Latin squares as vertices and the moves of the above type as edges is connected and nonbipartite, and so the random walk on this graph has a unique limiting distribution. Moreover, in this distribution, all (proper) Latin squares have the same probability.
For example, suppose we want to choose a random graph on n vertices, with each isomorphism class equally likely. Here Omega is the set of all 2^{n(n1)/2} graphs on the given vertex set V, and G is the symmetric group S_{n} consisting of all permutations of V. Starting with a graph Gamma, we calculate the automorphism group G of Gamma (for example, using a program such as nauty [3]), choose a random element g of G, and then choose a random graph Gamma' preserved by g.