[R] Re : Generate a random bistochastic matrix

[Rolf Turner]

I don't think this idea has been suggested yet:

	(1) Form all n! n x n permutation matrices,
	say M_1, ..., M_K, K = n!.

	(2) Generate K independent uniform variates
	x_1, ..., x_k.

	(3) Renormalize these to sum to 1,
		x <- x/sum(x)

	(4) Form the convex combination

		M = x_1*M_1 + ... + x_K*M_K

M is a ``random'' doubly stochastic matrix.

The point is that the set of all doubly stochastic matrices
is a convex set in n^2-dimensional space, and the extreme
points are the permutation matrices.  I.e. the set of all
doubly stochastic matrices is the convex hull of the the
permuation matrices.

The resulting M will *not* be uniformly distributed on this
convex hull.  If you want a uniform distribution something
more is required.  It might be possible to effect uniformity
of the distribution, but my guess is that it would be a
hard problem.

				cheers,

					Rolf Turner
					rolf at math.unb.ca