A starship lost 100 light-millennia from Sol knows only its distance from Sol, not the direction; jumping...
probability/lost.in.plane New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
A starship lost 100 light-millennia from Sol knows only its distance
from Sol, not the direction; jumping in random directions, can it get
within 1/4 light-hour of Sol?
[ Editor: problem statement reconstructed from Mike Paterson's summary
of the discussion; his original posting ("Lost in the Plane", 1993) is
not among the collected material. From the summary, the crew can choose
the length of each jump, the direction of each jump is random, and the
problem is posed in the plane. ]
Show solution
I think it is time to summarise progress on my starship problem. There have been interesting and helpful postings and e-mail messages from many people, particularly Tromp, Ring, Tung, Miller, Karr, Flajolet, Rubin, Karr, Elkies [Editor: "Ekies" in the original]. (Sorry for missed names here.) The situation for the starship's crew is not too bad. They can keep jumping a distance equal to their current distance from Sol. Although their expected distance from Sol will increase geometrically, the expected logarithm of their distance stays constant. This is because the integral of log(2 sin(theta/2)) for theta from 0 to 2*pi is zero. If they want to avoid getting too close to Sol a jump of a few light-minutes less than their distance each time also yields a corresponding integral which is zero. The aim of the crew is to approach from, say, 100 light-millenia away from Sol to within, say, 1/4 light-hour away, i.e., to reduce the (natural) log of their distance by at least log(100*1000*365*24*4), which is about 22. The standard deviation of each log-step (in the exact distance case) is pi/sqrt(12), which is about 0.9. Some fairly technical results on random walks assure us that the behaviour of the log of the distance is similar to the behaviour of a random walk on the real line where each step is either pi/sqrt(12) to the left or to the right. The starting point is log(100*1000*365*24*4) and the aim is to reach a negative number. Roughly we are asking how long it takes for a gambler with $24 to get ruined betting $1 each time. The expected time is infinite, but with high probability the gambler will be ruined (and the crew saved) after only a few thousand steps. In the limit, the probability exceeds any desired constant, e.g., 0.99, after a number of steps proportional to the square of the starting value. Unfortunately, I can't give the constant of proportionality nor estimate the closeness of convergence of our original problem to the gambler's ruin for the numbers involved. I don't know how much the numbers coming from peoples' simulations can be relied on. I expect they give better numerical information than can be obtained easily from the theory, but these random walks are somewhat slippery. I would welcome corrections or further information from those with more knowledge than I about the theory of random walks. As I said in my original posting, I have only a partial solution but it seems clear that the starship's crew should remain fairly hopeful! -- Mike Paterson <msp@dcs.warwick.ac.uk>, August 1993