# How can I randomly draw an ensemble of unit vectors that sum to zero?

Inspired by this question, I would like to determine the probability that a random knot of 6 unit sticks is a trefoil. This naturally leads to the following question:

Is there a way to sample uniformly from the set of ensembles of $n$ unit vectors $\{ v_i \}_{i=1}^n$ in $\mathbb{R}^d$ that sum to zero? I would like some sort of analytic expression for the distribution (something I might be able to prove a theorem with), but also an algorithmic process to implement in code.

UPDATE: It looks like what I want is basically the Hausdorff measure of an algebraic variety. Can I use the construction of this measure produce an analytic expression for the distribution?

-
With unit vectors, I think this would be very hard. But if you're willing to go with Gaussians, I think you can calculate the conditional probability distributions without much trouble. – Yoav Kallus May 19 '13 at 17:27
Idea: pick $n$ randomly, subtract $1/n \sum v_i$ from each, then rescale each back to unit. I expect this would converge quickly, but don't have any reason to believe that it gets you exactly to the uniform distribution. – Allen Knutson May 19 '13 at 18:14
For your first question you have an ordered list of $6$ unit vectors in general position (seems right to assume that). In any of the $6!$ orders the sum is zero. We can start anywhere and traverse the knot in either order so there are essentially $60$ knots. I wonder how many of them could be a trefoil. Might be an easy question. The easiest non-trivial case is $5$ unit vectors in $\mathbb{R}^2.$ – Aaron Meyerowitz May 19 '13 at 21:06
@Carlo, since Allen says "I expect this would converge quickly," I take it to be implied that the process is iterated. – Yoav Kallus May 19 '13 at 22:03
If $n$ is large, then the distribution of the path should converge to that of a $d$-dimensional Brownian bridge (essentially a Brownian motion conditioned to end back at the origin). – Jon Peterson May 21 '13 at 14:45

Here is one approach. Start with a regular $n$-gon in the $xy$-plane with unit edge lengths; say its vertices are $v_i$, $i=0,\ldots,n-1$. Now iterate the following process.

Select a random diagonal, $v_i v_j$. Rotate the chain $v_i, v_{i+1}, \ldots, v_j$ (indices appropriately mod $n$) as a rigid unit about the line through $v_i v_j$, by a random angle $\theta \in [0,2\pi)$.

Continue until there is sufficient "mixing." I illustrate the process below for 30 iterations applies to a hexagon.

(Apologies for the scale—the chain wanders away from its initial locaion.)

-
Any rough guess on the order of magnitude of the mixing time of this Markov chain? – Alekk May 20 '13 at 2:18
@Alekk: Sorry, I cannot even guess. Perhaps others can... – Joseph O'Rourke May 20 '13 at 2:27
I believe polymer people call the correlation time for this kind of dynamics the "Rouse relaxation time," so that should give a clue to search for how it is calculated. – Yoav Kallus May 20 '13 at 3:12
Better yet (and more generally), I can randomly select half of the $v_i$'s and apply a random rotation that fixes their sum. Intuitively, this encourages more mixing, so it might be faster. – Dustin G. Mixon May 20 '13 at 12:53

Cantarella and Shonkwiler have now posted a paper on the equilateral random polygon case. Their paper seems to cover a lot of what you're interested in, including a new Markov chain algorithm as well as a new lower bound of 3/4 for the probability that a random equilateral hexagon is un-knotted.

That bound is really a huge underestimate, though -- they report that their Markov chain gives about a probability of $(1.3\pm0.2)\times10^{-4}$ for knottedness.

Older post

Cantarella, Deguchi and Shonkwiler have recently begun investigating various ensembles of random polygons which, while not of the particular form you specified, may still be of interest.

I can't summarize their approach better than the abstract of their paper:

We build a new probability measure on closed space and plane polygons. The key construction is a map, given by Knutson and Hausmann using the Hopf map on quaternions, from the complex Stiefel manifold of 2-frames in n-space to the space of closed n-gons in 3-space of total length 2. Our probability measure on polygon space is defined by pushing forward Haar measure on the Stiefel manifold by this map. A similar construction yields a probability measure on plane polygons which comes from a real Stiefel manifold. The edgelengths of polygons sampled according to our measures obey beta distributions. This makes our polygon measures different from those usually studied, which have Gaussian or fixed edgelengths. One advantage of our measures is that we can explicitly compute expectations and moments for chordlengths and radii of gyration. Another is that direct sampling according to our measures is fast (linear in the number of edges) and easy to code.

Some of our methods will be of independent interest in studying other probability measures on polygon spaces. We define an edge set ensemble (ESE) to be the set of polygons created by rearranging a given set of n edges. A key theorem gives a formula for the average over an ESE of the squared lengths of chords skipping k vertices in terms of k, n, and the edgelengths of the ensemble. This allows one to easily compute expected values of squared chordlengths and radii of gyration for any probability measure on polygon space invariant under rearrangements of edges.

In a follow-up paper Cantarella, Grosberg, Kusner and Shonkwiler compute the total expected curvature for these random $n$-gons and thus extract bounds on knotting probabilities of hexagons and heptagons.

It turns out there is a relatively large literature on "random equilateral polygons", which is the model you are interested in. I don't think there is any known analytic formula for the probability - you would be looking for the measure of some rather complicated semi-algebraic sets corresponding to the components of the configuration space which correspond to knotted polygons. Thus people have primarily been studying properties of such random knots with Monte Carlo sampling.

Ken Millett is one of the experts on random knots and would be a great person to chat with about these questions. Here's one of his papers titled "The Generation of Random Equilateral Polygons"; which contains a discussion of methods used in the literature following variations of the idea that Joseph O'Rourke described above.

Of course, the hexagonal case has been studied numerically but I couldn't find a precise estimate in my searches. An early paper by Ken Millett which shows it as a data point on a curve of knotting probability versus number of edges can be found here.

-