Complexity of random knot with vertices on sphere Connect $n$ random points on a sphere in a cycle of
segments between succesive points:

     

I would like to know the growth rate, with respect to $n$, of the crossing number
(the minimal number of crossings of any diagram of the knot)
$c(n)$ of such a knot.
I only know that $c(n)$ is $O(n^2)$,
because it is known
that the crossing number is upper-bounded by
the stick number $s(n)$:
$$\frac{1}{2}(7+\sqrt{ 8 c(K) + 1}) \le s(K)$$
for any knot $K$.
And $s(n) \le n$ is immediate.
I feel certain this has been explored but I am not finding it
in the literature.  Thanks for pointers!
 A: I think you should look at this paper "The average crossing number of equilateral random polygons" by Y Diao, A Dobay, R B Kusner, K Millett and A Stasiak. http://iopscience.iop.org/0305-4470/36/46/002 
It can't seem to get the full text right now, so I'm not sure exactly what their random knot model is. It certainly isn't quite what you wanted, as they require their polygons to be equilateral. In their model the crossing number grows as $n \; \ln n$.
If this doesn't answer your question, consider looking through the rest of Ken Millett's work. He is one of the main people working on random knots.
A: You can find estimates nd other relevant information in the following two papers:
Arsuaga, J., Blackstone, T.*, Diao,Y., Karadayi, E. , Saito, Y. Sampling Large Random knots in Confined Spaces. J. Phys. A: Math Gen. (2007) 40; 11697-11711 
Arsuaga, J., Blackstone, T.*, Diao,Y., Karadayi, E. , Saito, Y. Linking of Uniform Random Polygons in Confined Spaces. J. Phys. A: Math. Gen. (2007) 40; 1925-1936
and 
The linking number and the writhe of uniform random walks and polygons in confined spaces
E Panagiotou et al 2010 J. Phys. A: Math. Theor.
A: I did some experiments on the degrees of Alexander polynomials, as suggested by Bill Thurston, and here is a table of values:
{{10, 1}, {20, 3}, {30, 7}, {40, 7}, {50, 19}, {60, 35}, {70, 
  43}, {80, 73}, {90, 73}, {100, 115}, {120, 123}, {140, 175}, {160, 
  233}, {180, 259}}

(the first number is the number of vertices, the second is the degree of the Alexander polynomial).
Or, for those of us more visually-minded, here is a plot:

I would describe the growth rate as at most $N^{3/2},$ consistent with Bill's theory.
A: Edited 2/9 after discussion with Dylan Thurston
It seems unlikely that the obvious knot projections can be simplified by more than a constant
factor, so a quadratic lower bound for the expected minimum crossing number seems likely.
Crossing number by itself though is a strange measure of complexity, and it is
hard to compute.   However, it's bounded below by hyperbolic volume of the knot complement.
It would be possible to get some experimental evidence by feeding output of your random
process through snappea, and looking at the distribution of hyperbolic volume. However, I think hyperbolic volume probably grows at a less than quadratic rate.  You can imagine thickening the knot into a growing solid torus, pushing outward until every part of the 
boundary has bumped into other boundary --- similarly to a Voronoi subdivision.  With
tubes of diameter some constant times $n^{-.5})$, the total volume of tubes is on the
order of the volume of the ball, so typical tube spacing should be $O(n^{-.5})$.
This suggests the number of faces in this subdivision should be $O(n^{3/2})$, which
would give a triangulation having $O(n^{3/2})$ tetrahedron where the knot is in the
1-skeleton, implying that the typical Gromov norm or hyperbolic volume probably
grows as $O(n^{3/2})$.  This would only imply $n^{3/2}$ crossings.
Marc Lackenby, in SPECTRAL GEOMETRY, LINK COMPLEMENTS AND SURGERY DIAGRAMS, developed
a beautiful method to give lower bounds for crossing numbers for knots.  His method
possibly could be applicable to improve this situation, provided  the Cheeger constants
for these manifolds can be shown to be not too small.
It's also possible that one could estimate the degree of the Alexander polynomial, to
get an estimate of the crossing number. 
A: This is not really an answer but an over-long comment following up suggestions of Ian Agol and Bill Thurston.
Experiment suggests (with 97% confidence) that the crossing probability (in a specified or random projection, for two line segments with the four endpoints chosen independently uniformly at random with respect to Haar measure) is greater than $.2499$ and less than $.2501$.  I have a motto never to compute by integrating what can be computed by symmetry, so the hope would be, for some integer $S$, to write a total of $4S$ symmetry-related expressions for the probability whose sum is identically $S$. So far any such trick eludes me; does anyone else see a way?
It would surprise me, for very large $n$, if even a constant factor improvement over a randomly chosen obvious projection is possible.  I would wager, then (although I would hate to have to prove it) that
$$\lim\limits_{n\rightarrow\infty} \frac{\bar{c}(n)}{n^2} = \frac18,$$
where $\bar{c}(n)$ is the expected value of crossing number for $n$ random points on the sphere.
The suggestion of a Voronoi-like spine whose dual would triangulate the knot complement is an interesting one.  The individual faces are sections of hyperbolic paraboloid.  It seems reasonable that their number would be strictly between linear and quadratic, although I don't yet see a good heuristic for guessing the correct order.
EDIT:  I was able to satisfy myself that the crossing probability is exactly $\frac14$, through a fairly (and probably unnecessarily) involved process.  At most stages one can reduce to simpler calculations using symmetries or nice facts such as the probability-preserving projection map from a $(d-1)$-sphere in $\mathbb{R}^d$ onto the ball of its first $d-2$ components.  For the final step I did have to compute an integral, though—the same one that tells you the angular momentum of a spinning coin (whose axis of rotation is in the plane of the coin).
I have started to suspect that in a certain precise sense an integral is unavoidable—that the boundary of crossing configurations is curved in ways that prevent abutment, just as the region north of $30^\circ$ latitude carries exactly $\frac14$ of the surface area of a perfect globe, but no finite collection of $4S$ rotated copies of it can be an exact $S$-fold cover.  (The transcendental answer to the usual Sylvester's four-point problem in the disc also discourages the finite cover approach.)
