From: George Marsaglia <geo@stat.fsu.edu>
Newsgroups: sci.math
Subject: Re: Random walk on  N-sphere
Date: Tue, 04 Aug 1998 11:25:08 -0700

Dave Rusin wrote:

> I'm standing at the North pole of the  N-sphere. I will take steps a
> uniform distance  epsilon  in random directions on the  N-sphere.
>         1. What is the expected number of steps until I first reach the
>                 Southern hemisphere?
>         2. What is the expected number of steps until I first reach the
>                 Antarctic circle?
> Interpret "distance" and "Antarctic circle" as you see fit; I want to
> go "really far away" from the North pole so that I can likely loop around
> obstacles whose positions I don't know anyway.
>
> dave
>

&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&
I made a big mistake in my first reply to the above query.
A more thorough examination suggests the following way
to reduce the problem to a random walk on a line.  It provides
an easy way to simulate the problem.

Let s be the (Euclidean) distance taken at each step, in a random direction.
Let t=1-s*s/2.

Start at (0,0,1) on the unit sphere (Earth).  The latitude is z, -1<=z<=1.
(Here "latitude" is not the usual angle, but the z-coordinate of
a point on the sphere.)

Then successive values of the "latitude" z may be generated by the formula:

        z <--  z*t+q or  z*t-q (probabilities 1/2)

        with  q=sqrt[(1-z*z)*(1-t*t)*(1-V*V)]

and V uniform in (-1,1).

This reduces the problem to a random walk on a line, but not
with equally distributed increments.   For given step size s,
one need only start with z=1 and continue to change z randomly
by the above formula until a specified level is passed.

To prove this, we may assume the current position is

   (x,0,z), x=sqrt(1-z^2).

Our new position is  the random point (a,b,c)  on the sphere,
subject to

                 |(x,0,z)-(a,b,c)|=s.

This reduces to  two equations:

                 ax + cz = t

                 a^2+c^2 = 1-b^2,

with b uniform on the range necessary to provide solutions for a and c.
(Each coordinate of a random point on the sphere is uniform (-1,1).)

Each choice of b, uniform in (-sqrt(1-t^2),sqrt(1-t^2)) provides
exactly two choices for c, the new z-coordinate:

                z*t+q or z*t-q.

George Marsaglia