Rolling a random walk on a sphere - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T19:57:34Z http://mathoverflow.net/feeds/question/63574 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/63574/rolling-a-random-walk-on-a-sphere Rolling a random walk on a sphere Joseph O'Rourke 2011-05-01T02:15:20Z 2011-12-10T02:21:09Z <p>A ball rolls down an inclined plane, encountering horizontal obstacles, at which it rolls left/right with equal probability. There are regularly spaced staggered gaps that let the ball roll down to the next, lower obstacle. The pattern resembles a binary tree: <br /><img src="http://people.csail.mit.edu/~orourke/MathOverflow/RollingObstacles.jpg" alt="Rolling Obstacles"><br /> Suppose the vertical and horizontal rolls have equal length $\delta$. Tracing out the roll contact point on the ball surface we see a random walk, with each step a geodesic arc of length $\delta$, and $90^\circ$ turns. I expected that for rational (multiples of $\pi$) $\delta$, the trace would not fill the surface, but the experiment below for $\delta=\pi/16$ (for 10, $10^2$, $10^3$, $10^4$ downhill steps) indicates otherwise.</p> <blockquote> <p>For which $\delta$ will this trace fill the sphere surface?</p> </blockquote> <p><br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<img src="http://people.csail.mit.edu/~orourke/MathOverflow/RollingSphereFill.jpg" alt="Sphere Paths"> <br /> Thanks for any insights!</p> <p><b>Answer</b>: The surface will be filled for every $\delta$ except $\pi/2$ and $\pi$. See Scott Carnahan's answer below, and Dylan Thurston's simplification. I find this answer remarkable!</p> http://mathoverflow.net/questions/63574/rolling-a-random-walk-on-a-sphere/63581#63581 Answer by S. Carnahan for Rolling a random walk on a sphere S. Carnahan 2011-05-01T06:22:14Z 2011-05-01T08:06:46Z <p>Let <code>$A = \begin{pmatrix} \cos \delta &amp; -\sin \delta &amp; 0 \\ \sin \delta &amp; \cos \delta &amp; 0 \\ 0 &amp; 0 &amp; 1 \end{pmatrix}$</code>, and let <code>$B = \begin{pmatrix} 1 &amp; 0 &amp; 0 \\ 0 &amp; \cos \delta &amp; -\sin \delta \\ 0 &amp; \sin \delta &amp; \cos \delta \end{pmatrix}$</code> be rotation by $\delta$ along the $z$ and $x$ axes, respectively. In suitable coordinates, a progression down one step in the tree is either $AB$ or $AB^{-1}$.</p> <p>The trace will fill (a.s.) a dense subset of the surface if and only if the closure of the group generated by $AB$ and $AB^{-1}$ is not a subgroup of $SO(3)$ of dimension zero or one.</p> <p>The dimension zero closed subgroups of $SO(3)$ are either cyclic, dihedral, or symmetries of Platonic solids, and the dimension one closed subgroups are conjugates of $SO(2)$ and $O(2)$. Therefore, it suffices to determine which values of $\delta$ yield a pair of elements in either a conjugate of $O(2)$, or a conjugate of one of the three Platonic groups (isomorphic to $A_4$, $S_4$, and $A_5$).</p> <p>In order for $AB$ and $AB^{-1}$ to both lie in a conjugate of $O(2)$ it is necessary and sufficient that they have a common eigenvector with eigenvalue $\pm 1$ - this eigenvector is the axis of rotation. Writing this requirement explicitly yields a polynomial identity in $\sin \delta$ and $\cos \delta$ <strike>(whose solutions I haven't enumerated yet)</strike>. <strong>Edit:</strong> Some straightforward case elimination with the $z$ coordinate of a common eigenvector shows that $\delta$ must be an integer multiple of $\pi/2$.</p> <p>For the Platonic solutions, we can narrow down the solution set using the criterion that the rotation $(AB^{-1})^{-1}(AB) = B^2$ lies in the group, and Platonic solids have rotational symmetries of order at most 5. This means $\delta$ is a multiple of $\pi/3$, $\pi/4$ or $\pi/5$.</p> <p>Since the traces of $AB$ and $AB^{-1}$ are both $(\cos \delta)(2 + \cos \delta)$, we can compare with character table entries to see if that number is the trace of an element in a Platonic group. It was pretty easy to eliminate candidates by eyeball in SAGE.</p> <p><strong>Conclusion:</strong> The only values of $\delta$ where the image is not dense are $0$, $\pm \pi/2$, and $\pi$. </p>