Re: Sean Pitman: definitions wanted


Seanpit wrote:
> RobinGoodfellow wrote:

[snip]

I don't have much time today, so I'll have to I'll have to postpone
replying to the first part of your post.

> > Yes, they are *related*. They are not the same thing. The number of
> > steps is referred not as "distance" but as "time". Accept it and move
> > on.
>
> Each step requires a unit of time. Each step represents a certain
> distance of measure, whether that be meters or residue differences. You
> are arguing that the "Eucledian distance" does "not refer to the number
> of steps" taken during a random walk, but to the "time" taken.

No, no, no, no, no! And in case that wasn't sufficiently clear, I will
quote Darth Vader from the end of episode III - NOOOOO!!!!!! This is
not what I'm saying at all - I'm not sure how you could have
misunderstood me so badly. "Eucleadean distance" - i.e. the simple
straight-line distance between points A and B - in no way refers to
"time taken". The number of steps taken to reach A from B refers, *is*
the time taken. Since each discrete step takes a fixed amount of time
(in most scenarios), the number of steps is used as a measure of
passage of time. That is, a step is used as a unit of time measure,
much like a generation is used as unit of time measure in population
genetics. This is the standard, accepted terminology in algorithm and
stochastic analysis. I am simply trying to get you to start using it
correctly, nothing more, nothing less.

My second point is that the relationship between "distance" (e.g.
straight-line distance, or Hamming distance, or mutational distance, or
whatever metric have you) and "time" (e.g. number of steps) need not be
exponential for random walks, and dependins entirely on the nature of
the random walk and properties of the configuration space were the walk
is taking place.

> The problem here is that the "time" taken is divided up into the number of
> steps were each step takes a certain amount of time. Therefore, the
> amount of time and the number of steps are equivalent as long as you
> know how long each step takes.

Yes!!! That is exactly what I've been trying to tell you. My main
gripe is that you are referring to the number of steps as "distance",
which is both confusing and inaccurate. The number of steps *is* time,
and that's that.

> > > > However, this
> > > > time is not necessarily *exponential* in the distance covered.
> > >
> > > Yes, it is. As far as the total number of steps are concerned, time and
> > > total distance walked increase in equivalent degrees. If a drunk
> > > walker has a distance meter and takes one step per second, with a 1
> > > meter stride, how far would he have walked and how much time would it
> > > take, on average, for him to find a target that averages 10, 20, 30 and
> > > 50 meters away on a 2D surface?
> >
> > To reach any points a distance N meters away?
>
> No, to reach a specific point, a specific target, N meters away.
>
> > If you read the
> > wikipedia link, you'll see the answer is N^2.
>
> That's the answer to reach *any* point N meters away - not a specific
> point.

Correct. Glad you're with me so far.

> > To reach a specific
> > point N meters away? Depends on the mesh size of the lattice on which
> > the walk is talking place, and whether the walk is allowed restarts.
> > Assuming a mesh size of one meter, there are approximately N^2 possible
> > targets a distance N meters away.
>
> Yep . . .
>
> > A random walk with restarts from the
> > origin - which models the multiple random walkers in evolutionary
> > process all originating from the common ancestral point - will
> > therefore take N^4 steps to reach a specific target. Which, of course,
> > is not exponential in N.
>
> You're wrong.

No, I'm not - although, in your defense, I wasn't exactly very clear.
The model I proposed was not of a random walk that will wonder
indefinitely, but will restart from the origin after apporimately N^2 -
the standard notation is O(N^2) - steps have been taken. This is a
model of the processes whereby an allele can sustain only a certain
number of mutations before being selected out of the gene pool, unless
it happens to mutate into something functional.

So, after O(N^2) steps, we would expect the random walk to land at some
point N meters away from the origin, assuming step sizes of 1 meter on
a square lattice. There are about N^2 such points, and the random walk
could land on each one with equal probability. Thus, if the walk takes
O(N^2) steps from the origin and reaches some N meters away, the
probability that it will be the *right* point is 1/O(N^2). Therefore,
we would expect we'd need to restart our walk O(N^2) times before our
goal. So, O(N^2) restarts times O(N^2) steps per run gives us O(N^4)
steps.

The above analysis is somewhat oversimplified, and I believe if we were
to get into the finer details, I might need to add another factor of N
to the calculation. Still, however, the expected time for such a walk
to reach a point N meters away is decidedly sub-exponential in N.

> Given a square grid and a walker that can step one squa re at a time
> (forward, backward, left and right), it will take 4^N steps to reach a
> specific square on the grid. If the walker can step in any of the 8
> squares immediately around his current square, then the average number
> of steps to reach the target square are 8^N. Either way, the
> exponential is N.

This calculation you make is for a completely unconstrained random
walk, which is different from the walk I described. But, indeed, this
particular type of random walk will require exponential time to reach
the "target". Notice how, by changing one simple property of the walk
- specifically, adding a constraint analogous to negative selection,
with no additional positive selection - the expected time to target
changes from exponential to polynomial in the distance.

Now, here's a followup problem for you. Assuming an unconstrained
random walk that you describe, but with multiple walkers all making
their steps in the same time, how many will we need before we could
expect that one of them will find our target point in O(N^2) time? Is
that number exponential in N?

[snip]

Cheers,
Leonid.

.

Relevant Pages

  • Re: Optimal rate of fire.
    ... In real life conditions, a soldier rarely gets to shoot at a target ... 150 meters distant. ... That's a huge distance, except in desert ...
    (soc.history.war.world-war-ii)
  • Re: I will rebuild physics from the ground up, as promised.
    ... 10 meters, and science predicts that it will require 1 second to traverse ... measurements show that the 10 meters are traversed in just 0,9 seconds. ... distance of 10 meters is measured at a distance using standard surveying ... Let the probability that length exists at any ...
    (sci.physics)
  • Re: Training journal while learning to unicycle
    ... drove over there instead of to my work parking lot and set off. ... meters (hard to tell, since the odometer has a resolution of 100 ... I managed to cycle that distance 3 times! ... Also, before I started distance riding I was riding around, finally ...
    (rec.sport.unicycling)
  • Re: Sean Pitman: definitions wanted
    ... >> distance of measure, whether that be meters or residue differences. ... Random walk steps can indeed cover a distance, ... non-exponential only helps you if your targets are really close. ... > a square lattice. ...
    (talk.origins)
  • Re: Munafs one-short run
    ... only the distance was an issue. ... the stumps within the demarcated area as set out above but that the point ... impact is greater than 250 cm from the stumps, the third umpire shall ... Note that the popping crease is 1.22 meters away from the stumps. ...
    (rec.sport.cricket)