Pitman lost his keys
Zachriel
find the keys, he will have to search by walking blindly in the dark.
Let's represent the playing field as a rectangle divided into squares.
Pitman can step randomly into any of the four adjoining squares. He keeps
walking randomly until he stumbles across the keys. Each step takes the same
time and travels the same distance. (And to make it a bit easier, Pitman
can't accidentally leave the field. If he attempt to move beyond the edge,
he steps in the other direction. Otherwise, poor Pitman might never find his
keys!)
In our example, the playing field is 50 x 100, and the keys are at a
distance of 10 from Pitman's starting position.
http://www.zachriel.com/images/pitmanskeys.jpg
Remembering that Pitman can't leave the playing field, and as there are
about 5000 squares making up the playing field; we hope that after no more
than a few thousand steps he'll stumble across the keys. Whew.
But what if Pitman's friend decides to help. They start at the same location
and go in their own random directions, one blind step at a time. How long
should it take? What if the entire playing team helps, everyone gathering at
the same location, then going their separate, random ways?
How long will it take to find Pitman's keys? In particular, is it
proportional to the number of walkers?
And will Pitman ever stop wandering aimlessly?
;o)
--
Zachriel's
Word Mutation and Evolution Experiment
And it takes less than "zillions of years"!
http://www.zachriel.com/mutagenation/
John Wilkins
number of keys that were good enough?
--
John S. Wilkins, Postdoctoral Research Fellow, Biohumanities Project
University of Queensland - Blog: evolvethought.blogspot.com
Nihil tam absurdum quod non quidam Philosophi dixerit - adapted from Cicero
David D.
Zachriel wrote:
> Oh no! Pitman lost his keys on the playing field. But it's dark. In order to
> find the keys, he will have to search by walking blindly in the dark.
Obviously he'll search under the street light. Its easier to see.
Navillus
Zach,
Can you make that simulation calculate the average steps it takes N
searchers to find the keys, as a function of the distance from the
starting point you put the keys?
Zachriel
"Navillus" <cwsul...@ucdavis.edu> wrote in message
news:1134353630.0...@g49g2000cwa.googlegroups.com...
That is something I have considered. But I want Sean to make a few precise
predictions about his understanding of random walks first.
The playing field really shouldn't have an edge. But it seems that if the
walker moves too far from the keys, he may end up having "taken a wrong turn
at Albuquerque", and never return. The problem then becomes a halting
problem. I could make it "dragons beyond", and assume the walkers drop off
the edge of the Earth, but then calculating an average might be a problem.
I think making the field big compared to the distance to the keys should be
sufficient for our purposes.
--
Zachriel, angel that rules over memory, presides over the planet Jupiter.
http://zachriel.blogspot.com/
bro...@noguchi.mimcom.net
It's OK to have an infinite field because the contribution to the
probability of finding the keys made by paths that first go very very
far away and then come back to the keys is tiny. You're going to use
approximations that drop off those terms anyway. This is a two
dimensional random walk problem which can be treated as a discrete time
Markov chain. It is way, way beyond Sean. You can find a good start in
a book, "An Introduction to Stochastic Processes with Applications to
Biology" by Linda J.S. Allen.
RobinGoodfellow
Please, please don't do anything yet! I may stand to win $1000 on
this, if Sean doesn't come to his senses. :)
Navillus
You already can! Sean accepted the challenge! Read all about it:
http://groups.google.com/group/talk.origins/browse_thread/thread/0933cb64f41aecf8/3088e90e343b4b47
RobinGoodfellow
Navillus wrote:
> RobinGoodfellow wrote:
[snip]
> You already can! Sean accepted the challenge! Read all about it:
> http://groups.google.com/group/talk.origins/browse_thread/thread/0933cb64f41aecf8/3088e90e343b4b47
I already replied to Sean, trying to explain to him why he is utterly
wrong, and giving him a chance to back out. I wouldn't feel right
taking this much money from someone without making sure he understands
what he is getting himself into. But, if he is as stubborn in this
instance as usual, he will likely ignore my warning anyway. Which
would be fine by me.
Cheers,
Leonid.
David Ewan Kahana
[snip]
>
> That is something I have considered. But I want Sean to make a few precise
> predictions about his understanding of random walks first.
>
> The playing field really shouldn't have an edge. But it seems that if the
> walker moves too far from the keys, he may end up having "taken a wrong turn
> at Albuquerque", and never return. The problem then becomes a halting
> problem. I could make it "dragons beyond", and assume the walkers drop off
> the edge of the Earth, but then calculating an average might be a problem.
>
> I think making the field big compared to the distance to the keys should be
> sufficient for our purposes.
>
You could avoid edges by using a periodic boundary condition.
Identify the left hand boundary with the right hand boundary ...
if Pitman steps off to the right at square (100, 23), he lands back on
the field at (1,23); similarly for the top and bottom boundaries.
David
Zachriel
<bro...@noguchi.mimcom.net> wrote in message
news:1134355840....@g43g2000cwa.googlegroups.com...
That's true if we were using analysis. However, it is a halting problem for
a simulation, a simulation having the advantage of something people can
actually see and play with. In RobinGoodfellow's analysis in the "Sean
Pitman: definitions wanted" thread, he just lets them tire out, that is,
move so long and then quit. Possible solutions:
* Finite steps, then quit. (Sean gets tired and walks home.)
* Drop off edge of field. (Sean takes wrong turn at Albuquerque. Never
heard from again.)
* Bounce off edge of field. (Sean keeps wandering in field until he finds
his keys. Mutters everytime he reaches edge.)
* Wrap around field. (David Ewan Kahana would like to help look, but only
if the playing field is some futuristic sphere like Thunderdome.)
Zachriel
Walter Bushell
"Zachriel" <angelma...@zachriel.com> wrote:
Make the field a Klein bottle and put him on the inside.
--
"The power of the Executive to cast a man into prison without formulating any
charge known to the law, and particularly to deny him the judgement of his
peers, is in the highest degree odious and is the foundation of all totali-
tarian government whether Nazi or Communist." -- W. Churchill, Nov 21, 1943
Andrew McClure
Seanpit
You're too kind ; ) Just so you know though, even if you did end up
being wrong I wouldn't have taken your money either. However, I'm
certainly willing to ante up here (my response to your reply is pasted
below).
Sean Pitman
www.DetectingDesign.com
______________
RobinGoodfellow wrote:
> Seanpit wrote:
> > RobinGoodfellow wrote:
>
> [snip]
>
> > > That's quite an interesting view! If a sequence walks off the
> > > "beneficial island", selection immediately kills it off and
> > > automagically poofs a brand new sequence at random somewhere in the
> > > beneficial island so as to replace it?! Tell me, oh wise one, what
> > > other wondrous powers does selection have?
> >
> > That's exactly what happens. A population that occupies an island
> > reproduces itself largely on the island. If an individual in this
> > population happens to take a jump into the surrounding ocean, that
> > individual can most certainly die off right away - without reproducing
> > or swimming very far at all. However, this loss will most likely not
> > be all that significant since the reproductive rate of those still on
> > the island may easily cover the loss.
>
> That is correct, but it has nothing to do with your concept of
> "sampling". Those sequences that are in the "island" aren't being
> generated de-novo at random. They themselves are descended from an
> ancestral population. A new sequence is not a "dart" thrown into the
> island: it can only arise if its a sufficiently close ancestor was in
> the island in the first place. This process is far more analogous to
> random walk with multiple walkers than "random sampling".
I'm not talking about sampling the island. Sampling different regions
of the island is a random walk. I'm talking about sampling the
surrounding ocean of non-beneficial sequences. The population throws
individuals as "darts" into the surrounding ocean at random to see if
any other beneficial islands might be just off the current island. The
random sampling is an attempt to get off the current island and find
some other island steppingstones.
> I suggest you try to get your mathematical
> education from sources other
> than Dembski. Contrary to what the ID
> community seems to believe, he is very
> far from being the greatest mathematician
> to ever walk the earth.
No one says that Dembski is the greatest mathematician to cross the
Earth. All I'm saying is that he is a mathematician.
> > It's true. You think 50% homology is just incredible - right? It
> > isn't. Look at what happens with 50% homology as you move up the
> > ladder. At lower levels, say, a 10 residue sequence with 50% homology
> > to another sequence, the linear distance is only 5 residue differences.
> > The odds that these 5 residues will exist somewhere else in the genome
> > or that they can be found by random walk alone, are pretty good.
> > However, for functions that require at least 100 residues a 50%
> > homology with another sequence means that there is a gap of 50
> > residues. The odds that these 50 exist somewhere else in the genome is
> > a lot less than it was at the lower levels. And, this problem only
> > becomes worse as you keep moving up the ladder.
>
> That is of course if you assume that the 50% that are not homologous
> are "fully specified". This is a very silly assumption to make. Very
> few amino acids in real proteins are "fully" specified. Even less so
> if you take into account all possible evolutionary and co-evolutionary
> pathways.
I only assume a "fair" degree of specificity (i.e., around 1 in 1e30
per 100aa).
> > At the level of flagellar motility 50% or 60% homology with a subsystem
> > function is nothing - and that's about the best you have. Sure, you say
> > that you can put these subsystems together to get up to 90% or so
> > homology. There are several problems with this. First off, putting
> > these subsystems together just right involves the crossing of huge gaps
> > right off the bat. Then, what about those parts that have no
> > homologies in the genome? How do you get those parts in the genome and
> > then into the right place in relation to the other parts? That's a
> > huge problem for your theory.
>
> I posed that problem as a question for you. I did a quick and dirty
> solution, and the answer isn't nearly as improbable as you think it is.
> You seem to be making assertions that it's completely improbable, but
> no calculations to show for it. Do try to answer my question about the
> probablity of a fortuitous gene transfer merging a pair of functional
> complexes. It's somewhere upthread.
I've already answered this. If the merge requires more than a few
dozen changes in *fairly specified* residue positions, it is quite
improbable and becomes exponentially more improbable with each increase
in the number of residues that need to be changed to a fairly specified
degree.
> > I don't think my calculations are off to any significant degree. If
> > every space has equal odds of being hit by random walk, which is most
> > certainly true (even the start space in a 2-D lattice), then the chance
> > that a specific square will be hit are most certainly right around X^N.
> >
> > It may be slightly off, but I think it is fairly close. Dembski, who is
> > a mathematician, uses these same odds in his own calculations of random
> > walks to a specific target:
> >
> > "Given these provisos, the stopping time for the random walk to
> > reach the target T will have expected value whose order of magnitude is
> > 1U(T ) (for the relevant mathematics, see Spitzer 2001). The stopping
> > time here is simply the number of steps required for the random walk to
> > reach the target. Thus, for instance, the average number of steps for a
> > random walk to locate a particular protein 100 amino acids in length
> > will have order of magnitude 1 U(T ) = 1 1/20^100 = 20^100 ˜ 10^130.
> > Thus, we find that random walks, as with uniform random sampling, are
> > no better than exhaustive search in decreasing the number of points
> > that, on average, need to be examined before the search succeeds."
> >
> > http://www.designinference.com/documents/2005.03.Searching_Large_Spaces.pdf
>
> Figures you wouldn't understand that the scenario that Dembski is
> describing is completely different from the one you and I are
> discussing. He is talking about an unaided random walk finding a
> specific point in a bounded L-dimensional hypercube of volume 20^L.
> There are exactly 20^L points inside such a hypercube, and, since the
> unaided random walk will eventually approach a stationary uniform
> distribution, his approximation of about 20^L steps is indeed an
> adequate one, since every point has 1/20^N probability of being hit at
> every step (after the walk has gone on for enough steps to "mix" - i.e.
> approach a uniform distribution).
That's right . . .
> You and I, however, are discussing
> the walk on an unbounded 2-Dimensional lattice. Since the number of
> points on such a lattice is infinite, the uniform probability of a
> hitting a specific point via random sampling is exactly 0. (i.e. If
> you throw darts purely at random at an infinite 2-D lattice, you will
> never hit a specific point on that lattice.) On the other hand,
> Polya's theorem establishes that a random walk on such a lattice will
> eventually hit any given point on the lattice with probability 1. That
> is, pick any specific point on the lattice, and you are certain to
> visit that point via random walk after a certain amount of steps, even
> though that number of steps can be arbitrarily large. Therefore, in
> this example, random sampling approximation to a random walk just
> doesn't work.
Perhaps . . .
> > So you see, random walks and random sampling have the same odds of
> > success. There just is no advantage to a random walker over a random
> > sampler in finding a specific target.
>
> Again, I strongly urge you to learn your mathematics from a source
> other than Dembski. (Or are all other authors of statistics textbooks
> blinded by their evolutionist beliefs?) Or at least try to understand
> what Dembski is doing in that case, and how his scenario differs from
> the one you and I are discussing.
Right . . .
> > > Of course not. There are 8N+4 squares along the perimeter of the grid
> > > in this model (e.g. 20 for N=2, 28 in a 7x7 grid where N=3, etc.)
> >
> > Not true. Count the squares along the edge of a 7 x 7 grid and you
> > will see that there are only 24 squares.
>
> Ack. Right you are. 8N instead of 8N+4. There are only 16 squares
> along the edges of a 5x5 grid instead of 20.
; )
< snip >
> > Your formula of N^2 is wrong. Each increase in the number of walkers
> > does not decrease the search time exponentially as you say. It divides
> > the search time fairly equally (though a little less than equal) like I
> > originally said.
>
> Even your own math, wrong as it is, does not bear this out. Your
> latest calculation shows that they expected times are independent of N
> entirely - which, of course, is also wrong.
It was late when I was working on my responded to your last post and I
was very tired from a very long week. And so, for some reason, I didn't
catch that your 1 - (7/8)^k is actually the same as my 1 -
(((X-1/X)^k)*(X^N)) / (X^N) formula for N = 1.
_________
X = the number of potential directions that can be taken from any one
Location
N = the minimum number of steps to a particular target
W (or k) = the number of walkers
_________
> > > Come on, Sean, think about this for a minute. The N simulataneous
> > > walkers is analagous to the scenario of a single walker with mutliple
> > > restarts.
> >
> > Nope. It is analogous to multiple walkers *without* restarts. If the
> > *average* for one walker without a restart is X^N, and it is, then it
> > is quite clear that the average for multiple walkers without restarts
> > is X^N/W.
>
> Think about it just a little longer, Sean. If I restart a walk after
> N^2 steps each time, and do so 2*PI*N times, it is as if I've taken N^2
> steps along 2*PI*N mutually independent random walk paths. This is
> exaclty equivalent to the scenario of 2*PI*N independent walkers
> walking for N^2 steps. There is absolutely no difference.
I agree, except for a minor question about Pi (see below)
What you are talking about is the average number of steps for the
population as a whole - not the total average for the individual steps
taken by each of the walkers to reach the target. In other words, I
was talking about the average of the total number of steps of each
walker while it seems you were talking about the average number of
steps for the population as a whole - which is more relevant to the
problem actually. In that case, your formula seems pretty much correct
and mine is not. The search time for the population is not reduced by
dividing X^N by the number of walkers (W), but by your formula of about
N^2 given 2*Pi*N walkers.
So, given the population as a whole, you're right. The average "time"
to success for at least one individual in a population as a whole
decreases dramatically with increasing numbers of random walkers.
Where would you like your $1000 sent? ; )
Sean Pitman
www.DetectingDesign.com
P.S. The Pi thing:
I've thought a bit more about this and come to the conclusion that even
if you walk along a lattice in 1 of 4 directions, the number of points
that can be hit along the edge of the grid is not 2*Pi*N.
For example, say that the straight-line distance to the edge of the 2-D
grid equals 3 steps - all steps being exactly the same length. How
many points along the edge of the grid would be exactly 3 steps away?
According to you there should be 2 x 3 x 3 = 18. However, if you
actually draw it out, there are only 12 points on the grid that are
just 3 equally distant steps away from the center (i.e., in keeping
with my original formula of X*N). Your formula of 2*Pi*R =
circumference of a circle, but doesn't say how many points along the
edge of the circle a walker can actually touch the edge.
But, this is an aside having nothing to do with the main point.
RobinGoodfellow
Seanpit wrote:
> RobinGoodfellow wrote:
> > Navillus wrote:
> > > RobinGoodfellow wrote:
> >
> > [snip]
> >
> > > You already can! Sean accepted the challenge! Read all about it:
> > > http://groups.google.com/group/talk.origins/browse_thread/thread/0933cb64f41aecf8/3088e90e343b4b47
> >
> > I already replied to Sean, trying to explain to him why he is utterly
> > wrong, and giving him a chance to back out. I wouldn't feel right
> > taking this much money from someone without making sure he understands
> > what he is getting himself into. But, if he is as stubborn in this
> > instance as usual, he will likely ignore my warning anyway. Which
> > would be fine by me.
> >
> > Cheers,
> > Leonid.
>
> You're too kind ; )
Why, thank you! :)
> Just so you know though, even if you did end up
> being wrong I wouldn't have taken your money either.
Thank you again, but, to be perfectly honest, I'm not *that* kind. As
far and as I am concerned, you never really took the bet, and I
intended to give you every chance to back out of doing so, but had we
gone through with it, I would have expected you to pay up afterwards.
> However, I'm certainly willing to ante up here (my response to your reply is pasted
> below).
That's very generous of you, but I wouldn't dream of claiming the ante,
since we never seriously agreed on the bet. I'll reply to the rest of
your post in the "Definitions Wanted" thread a little later.
Cheers,
Leonid.
[snip]
B Richardson
I recently parked near the tallest building in downtown Chicago
and neglected to scribble down where. I came to fetch it some days
later, and thought it should be easy to find being just a few
blocks from the Sears Tower. A random 90 minute walk carrying
35 pounds of luggage in six inches of snow failed to turn up my
car. I then resorted to the random cab ride and eleven dollars
later I found my car.
Seanpit
RobinGoodfellow wrote:
> > You're too kind ; )
>
> Why, thank you! :)
Sorry, but I've been doing even more thinking about this since
yesterday and I'm not sure your right anymore. I know I wasn't right,
but now I think that you might not be right either. I've copied my
reply to your most recent post in the "Definitions Wanted" thread
below:
______________
I'd like to go over your comments about this Dembski reference again:
> > http://www.designinference.com/documents/2005.03.Searching_Large_Spaces.pdf
>
> Figures you wouldn't understand that the scenario that Dembski is
> describing is completely different from the one you and I are
> discussing. He is talking about an unaided random walk finding a
> specific point in a bounded L-dimensional hypercube of volume 20^L.
That's right.
> There are exactly 20^L points inside such a hypercube, and, since the
> unaided random walk will eventually approach a stationary uniform
> distribution, his approximation of about 20^L steps is indeed an
> adequate one, since every point has 1/20^N probability of being hit at
> every step (after the walk has gone on for enough steps to "mix" - i.e.
> approach a uniform distribution).
That depends. It depends on the location of the target within the
hypercube relative to the starting location of the random walker(s).
If the distance to the target was N^0.5/2, then it seem that this would
be true. However, if the distance to the target were only one step
away from the starting point in this multidimensional cube (i.e., one
character difference), then the random walk distance/time would be much
shorter.
> You and I, however, are discussing
> the walk on an unbounded 2-Dimensional lattice.
Yes, but I am actually more interested in a bounded lattice.
> Since the number of
> points on such a lattice is infinite, the uniform probability of a
> hitting a specific point via random sampling is exactly 0. (i.e. If
> you throw darts purely at random at an infinite 2-D lattice, you will
> never hit a specific point on that lattice.)
I'm not quite sure about this notion for a 2D lattice. What is
infinity divided by infinity?
> On the other hand,
> Polya's theorem establishes that a random walk on such a lattice will
> eventually hit any given point on the lattice with probability 1.
Yes, that makes sense - given an infinitely long random walk.
> That
> is, pick any specific point on the lattice, and you are certain to
> visit that point via random walk after a certain amount of steps, even
> though that number of steps can be arbitrarily large.
Like infinitely large . . .
> Therefore, in
> this example, random sampling approximation to a random walk just
> doesn't work.
I'm still not sure about this for an unbounded 2D lattice and I'm
really leaning the other way for a bounded 2D lattice.
> > So you see, random walks and random sampling have the same odds of
> > success. There just is no advantage to a random walker over a random
> > sampler in finding a specific target.
>
> Again, I strongly urge you to learn your mathematics from a source
> other than Dembski. (Or are all other authors of statistics textbooks
> blinded by their evolutionist beliefs?) Or at least try to understand
> what Dembski is doing in that case, and how his scenario differs from
> the one you and I are discussing.
I do understand that the scenario Dembski is describing for
multidimensional sequence space is different from a random walk on a 2D
lattice in a few particulars. However, I'm not so sure the differences
are significant as far as the main points we are discussing. Is it
really true that random walk finds things in a significantly different
amount of time vs. random sampling in a 20D vs. a 2 D bounded or
unbounded lattice?
I've been thinking a bit more about this and I am not so sure you're
right any more. Now, I don't think I was right in my initial
calculations, but I'm not sure you were right either now.
Consider the notion of a patterned walk instead of a random walk -
inside a limited lattice (like a football field). If a walker started
out in the middle and walked in an ever-expanding spiral circle mowing
the field with a lawn mower, how many steps would it take to mow over
the wallet if the wallet was N Euclidian steps away? About 2N^2 -1
steps - right (the total number of squares on the grid - 1)? Now, what
if you had two of these non-random walkers? How many steps would it
take for this "population" of two? 2N^2/2 - Right? I mean, you'd just
be mowing the lawn twice as fast and so you'd mow over the wallet twice
as fast. The same holds for 3 of these non-random walkers = 2N^2/3 . .
. etc.
It seems then that the *random* walk increases the average number of
steps beyond the total number of squares on the grid because of the
problem of retesting previously occupied squares. Therefore, all that
additional *random* walkers do is reduce the amount of resampling quite
dramatically.
If this is true, I'm not quite sure how random walk on a bounded 2D
lattice would be any more or less successful than random *sampling* on
a bounded 2D lattice - or even an unbounded 2D lattice for that matter.
The greater the number of random walkers, the less the resampling
before success and the more in line with the formula 2N^2/Walkers you
get. The same thing seems true of random sampling. The greater the
number of random samplers, the less resampling is done before success
and the more in line with the formula 2N^2/Samplers you get.
So, perhaps we were both wrong? I mean, your formulas did not work with
small distances and mine didn't work with large distances to the
target. This new formula seems to work for all target distances. Try
it in your simulation and check it out - if you don't mind.
Sean Pitman
www.DetectingDesign.com
Zachriel
Pitman: "It depends on the location of the target"
Quite right! Assuming each walker moves in lockstep:
Time = number of locksteps
Steps = walker-steps, total number of steps for all walkers
Distance = Direct distance from walker to another point.
On average:
If each walker starts in a different random location on an infinite plane,
then it is the same as a random sample. However...
On an infinite plane, finding a target at a finite distance, a random walker
will be faster (take less time) than a random sample. More walkers will be
faster than fewer walkers. More walkers will even take fewer overall steps —
up to a point of optimization. It's fastest at the beginning. If the walkers
don't find the target near the beginning of the search while they are
"close", they will tend to disperse (though in a finite time will always be
at a finite distance).
On a finite plane, finding a target, a random walker will be faster if it
starts "close" compared to the size of the space, but will be slower if not
"close".
Biological evolution works quite differently, as adaptation is largely due
to selection, except to point out that the targets are closer rather than
farther away, a point Pitman has always failed to grasp.
In any case, random walking is not the same as a random sample. A large
number of walkers starting from the same location does not act random by any
means, but acts something like a gas expanding into the surrounding space.
http://www.zachriel.com/randomwalker/HundredWalkers.gif
Zachriel
http://zachriel.blogspot.com/
Random Walkers Coming Soon!
(crossposted to the "Sean Pitman: definitions wanted" thread)
Zachriel
Zachriel wrote:
> Pitman: "It depends on the location of the target"
>
> Quite right! Assuming each walker moves in lockstep:
>
> Time = number of locksteps
> Steps = walker-steps, total number of steps for all walkers
> Distance = Direct distance from walker to another point.
>
> On average:
>
> If each walker starts in a different random location on an infinite plane,
> then it is the same as a random sample. However...
>
> On an infinite plane, finding a target at a finite distance, a random walker
...starting from the same location (island in Pitmanian parlance)...
> ...will be
> faster than fewer walkers. More walkers will even take fewer overall steps -
Seanpit
Zachriel wrote:
> Pitman: "It depends on the location of the target"
>
> Quite right! Assuming each walker moves in lockstep:
>
> Time = number of locksteps
> Steps = walker-steps, total number of steps for all walkers
> Distance = Direct distance from walker to another point.
>
> On average:
>
> If each walker starts in a different random location on an infinite plane,
> then it is the same as a random sample. However...
>
> On an infinite plane, finding a target at a finite distance, a random walker
> will be faster (take less time) than a random sample. More walkers will be
> up to a point of optimization. It's fastest at the beginning. If the walkers
> don't find the target near the beginning of the search while they are
> "close", they will tend to disperse (though in a finite time will always be
> at a finite distance).
Right . . .
> On a finite plane, finding a target, a random walker will be faster if it
> starts "close" compared to the size of the space, but will be slower if not
> "close".
I'm not quite sure what you're saying here . . . Obviously a closer
target will be found more quickly than a target that is farther away.
But, I'm not sure that is what you are trying to say here.
> Biological evolution works quite differently, as adaptation is largely due
> to selection, except to point out that the targets are closer rather than
> farther away, a point Pitman has always failed to grasp.
Selection doesn't work if the various sequence options are equally
non-beneficial. Also selection often prevents random walk by keeping
walkers from straying too far from their original island starting
points. And, the clincher: At higher levels the target islands are
indeed very far away across vast neutral/detrimental gaps. There is no
guidance via biased selection across these gaps.
> In any case, random walking is not the same as a random sample.
Yes, it is in a limited lattice framework, which is what I'm talking
about. Each "level" of sequence space is a limited lattice framework.
The ratios of each level create small lattices within the overall
lattice of that level. The odds of success via random walk or random
sampling within such a lattice the same.
> A large
> number of walkers starting from the same location does not act random by any
> means, but acts something like a gas expanding into the surrounding space.
> http://www.zachriel.com/randomwalker/HundredWalkers.gif
The gas expands via random walk. The number of gas particles, like
random walkers, is limited. Only a limited number of positions can be
occupied/tested over a given span of time. Beyond this, a particular
beneficial starting point is not allowed to send out random walkers too
far into sequence space because of the limits placed on it's population
of potential walkers by natural selection.
> Zachriel
> http://zachriel.blogspot.com/
> Random Walkers Coming Soon!
Sean Pitman
www.DetectingDesign.com
Zachriel
Seanpit wrote:
> Zachriel wrote:
> > Pitman: "It depends on the location of the target"
> >
> > Quite right! Assuming each walker moves in lockstep:
> >
> > Time = number of locksteps
> > Steps = walker-steps, total number of steps for all walkers
> > Distance = Direct distance from walker to another point.
> >
> > On average:
> >
> > If each walker starts in a different random location on an infinite plane,
> > then it is the same as a random sample. However...
> >
> > On an infinite plane, finding a target at a finite distance, a random walker
> > will be faster (take less time) than a random sample. More walkers will be
> > faster than fewer walkers. More walkers will even take fewer overall steps -
> > up to a point of optimization. It's fastest at the beginning. If the walkers
> > don't find the target near the beginning of the search while they are
> > "close", they will tend to disperse (though in a finite time will always be
> > at a finite distance).
>
> Right . . .
>
> > On a finite plane, finding a target, a random walker will be faster if it
> > starts "close" compared to the size of the space, but will be slower if not
> > "close".
>
> I'm not quite sure what you're saying here . . . Obviously a closer
> target will be found more quickly than a target that is farther away.
> But, I'm not sure that is what you are trying to say here.
A group of random walkers will find the target quicker than a random
sample if the target is "close". More walkers will find the "close"
target faster (less time) than fewer walkers. More walkers will even
find the target in fewer overall steps than fewer walkers, up to a
limit of optimization. This is the fundamental difference between a
random walk and a random sample.
You will now assert that, in biology, targets and origins are random
with respect to one another (or at least that the target is necessarily
far way from the origin). This claim is unsupported.
>
> > Biological evolution works quite differently, as adaptation is largely due
> > to selection, except to point out that the targets are closer rather than
> > farther away, a point Pitman has always failed to grasp.
>
> Selection doesn't work if the various sequence options are equally
> non-beneficial. Also selection often prevents random walk by keeping
> walkers from straying too far from their original island starting
> points. And, the clincher: At higher levels the target islands are
> indeed very far away across vast neutral/detrimental gaps.
That is your (false) assertion. If the target is randomly situated with
respect to the origin, then a random walk is equivalent to a random
sample. Of course, the target is not random with respect to the origin
in biology (or language), which is what your assertions imply. And the
Theory of Evolution does not posit a long random walk, nor in any case;
is there evidence that such would be required.
> There is no
> guidance via biased selection across these gaps.
>
> > In any case, random walking is not the same as a random sample.
>
> Yes, it is in a limited lattice framework, which is what I'm talking
> about. Each "level" of sequence space is a limited lattice framework.
> The ratios of each level create small lattices within the overall
> lattice of that level. The odds of success via random walk or random
> sampling within such a lattice the same.
Attempting a translation: In a given finite space, the targets are
always scattered randomly (or are far away in any case) with respect to
the origin of the search.
This claim is false with regards to biological evolution. There is deep
order within the structure of genetic homologies (and language, too).
>
> > A large
> > number of walkers starting from the same location does not act random by any
> > means, but acts something like a gas expanding into the surrounding space.
> > http://www.zachriel.com/randomwalker/HundredWalkers.gif
>
> The gas expands via random walk. The number of gas particles, like
> random walkers, is limited. Only a limited number of positions can be
> occupied/tested over a given span of time.
True.
> Beyond this, a particular
> beneficial starting point is not allowed to send out random walkers too
> far into sequence space because of the limits placed on it's population
> of potential walkers by natural selection.
Natural selection is not currently at issue in the discussion of random
walkers. The issue is that random walkers generally do not have the
same characteristics as random sampling. Only if the origin of each
walker is randomly and independently sampled, does the random walk and
the random sample resemble one another.
>
> > Zachriel
> > http://zachriel.blogspot.com/
> > Random Walkers Coming Soon!
>
> Sean Pitman
> www.DetectingDesign.com
Zachriel
http://zachriel.blogspot.com/
Seanpit
> The issue is that random walkers generally do not have the
> same characteristics as random sampling. Only if the origin of each
> walker is randomly and independently sampled, does the random walk and
> the random sample resemble one another.
Random walkers and random samplers do have exactly the same odds of
successfully finding a target as long as the target is on the edge of
the lattice and the random walkers start in the middle. The origin of
each random walker does not have to be "random" for this statement to
be true. Ask Leonid if you don't believe me.
> Zachriel
> http://zachriel.blogspot.com/
Sean Pitman
www.DetectingDesign.com
Zachriel
"Seanpit" <seanpi...@naturalselection.0catch.com> wrote in message
news:1134672404.5...@g47g2000cwa.googlegroups.com...
> Zachriel wrote:
>
>> The issue is that random walkers generally do not have the
>> same characteristics as random sampling. Only if the origin of each
>> walker is randomly and independently sampled, does the random walk and
>> the random sample resemble one another.
>
> Random walkers and random samplers do have exactly the same odds of
> successfully finding a target as long as the target is on the edge of
> the lattice and the random walkers start in the middle. The origin of
> each random walker does not have to be "random" for this statement to
> be true. Ask Leonid if you don't believe me.
I assume that's a finite plane. What happens to a walker when it reaches the
edge?
* Finite steps, then quit.
* Drop off edge of field.
* Bounce off edge of field.
* Wrap around field.
And why in the world would a bunch of random walkers just happen to be
exactly in the middle of a finite plane with the target on the edge? Why not
a target somewhere within the plane? Why not the walkers some place other
than the middle?
hersheyhv
Only if the walkers *all* started out equidistant from the wallet. If,
by chance, one was close to the wallet, the time would, on average, be
dramatically reduced. We are not interested in the average time it
would take measured by averaging out the time it would take each
individual walker to find the wallet. We are interested in the
shortest time it would take given the starting distribution of walkers.
Obviously, those walkers that start out, by chance or placement,
closest to the wallet would be the ones most likely to find it. Once
the wallet is found, why continue the search?
> It seems then that the *random* walk increases the average number of
> steps beyond the total number of squares on the grid because of the
> problem of retesting previously occupied squares. Therefore, all that
> additional *random* walkers do is reduce the amount of resampling quite
> dramatically.
If, as you point out, selection actually prevents a *long* random walk,
then whether or not the wallet will be found will depend upon whether
or not it is 'within reach' of a constrained random walker. In this
case, it is quite clear that only walkers that are, by chance, close to
the wallet will be likely to find it. Now what you have to do is
demonstrate that it is physically impossible for a walker to *ever* be
positioned, by chance or by utility, close to the wallet.
> If this is true, I'm not quite sure how random walk on a bounded 2D
> lattice would be any more or less successful than random *sampling* on
> a bounded 2D lattice - or even an unbounded 2D lattice for that matter.
> The greater the number of random walkers, the less the resampling
> before success and the more in line with the formula 2N^2/Walkers you
> get.
The greater the number of walkers, the more likely that one will be
close to the wallet if the walkers are randomly distributed. But, of
course, in biological systems neither the walkers nor the wallet (the
teleologic goal you have set) are randomly distributed over total
sequence space.
hersheyhv
Seanpit wrote:
> Zachriel wrote:
>
> > The issue is that random walkers generally do not have the
> > same characteristics as random sampling. Only if the origin of each
> > walker is randomly and independently sampled, does the random walk and
> > the random sample resemble one another.
>
> Random walkers and random samplers do have exactly the same odds of
> successfully finding a target as long as the target is on the edge of
> the lattice and the random walkers start in the middle. The origin of
> each random walker does not have to be "random" for this statement to
> be true. Ask Leonid if you don't believe me.
How does this even remotely model a search for a teleologically
determined sequence 'island' from a starting point of the many sequence
'islands' that already exist in a cell (the random walkers leaving
random starting points distributed throughout sequence space)? Are you
claiming that the walkers all leave the *same* sequence space, one
equidistant from the target?
Zachriel
"Seanpit" <seanpi...@naturalselection.0catch.com> wrote in message
news:1134672404.5...@g47g2000cwa.googlegroups.com...
>
>> The issue is that random walkers generally do not have the
>> same characteristics as random sampling. Only if the origin of each
>> walker is randomly and independently sampled, does the random walk and
>> the random sample resemble one another.
>
> Random walkers and random samplers do have exactly the same odds of
> successfully finding a target as long as the target is on the edge of
> the lattice and the random walkers start in the middle. The origin of
> each random walker does not have to be "random" for this statement to
> be true. Ask Leonid if you don't believe me.
That is incorrect. Any point on the edge may be just as likely to be hit,
but a random sample is more efficient because the walkers concentrate their
initial efforts close to the origin, and only disperse *somewhat* in finite
time. The edge is the farthest point possible and is the most difficult case
for walkers originating at the center. The asserted equivalence of walkers
and samplers is misleading. The search time of walkers is heavily dependent
on the exact characteristics of the landscape.
A more appropriate arrangement, in light of your assertions, might be to
have targets scattered randomly within the lattice, not on its edge.
(For "Pitman lost his keys", we'll use bounce off edge method.)
--
Zachriel
http://zachriel.blogspot.com/
RANDOM WALKERS: It might just take "zillions" of years!
Zachriel
"Zachriel" <angelma...@zachriel.com> wrote in message
news:11ppgo1...@corp.supernews.com...
> Oh no! Pitman lost his keys on the playing field. But it's dark. In order
> to find the keys, he will have to search by walking blindly in the dark.
>
> Let's represent the playing field as a rectangle divided into squares.
> Pitman can step randomly into any of the four adjoining squares. He keeps
> walking randomly until he stumbles across the keys. Each step takes the
> same time and travels the same distance. (And to make it a bit easier,
> Pitman can't accidentally leave the field. If he attempt to move beyond
> the edge, he steps in the other direction. Otherwise, poor Pitman might
> never find his keys!)
>
> In our example, the playing field is 50 x 100, and the keys are at a
> distance of 10 from Pitman's starting position.
> http://www.zachriel.com/images/pitmanskeys.jpg
>
> Remembering that Pitman can't leave the playing field, and as there are
> about 5000 squares making up the playing field; we hope that after no more
> than a few thousand steps he'll stumble across the keys. Whew.
>
> But what if Pitman's friend decides to help. They start at the same
> location and go in their own random directions, one blind step at a time.
> How long should it take? What if the entire playing team helps, everyone
> gathering at the same location, then going their separate, random ways?
>
> How long will it take to find Pitman's keys? In particular, is it
> proportional to the number of walkers?
No, it is not directly proportional as previously claimed. Nor does placing
a target on the edge of the searchable area make the search time equivalent
to a random sample. In fact, random walkers act nothing like random
sampling. The number of walkers and the proximity of the target is crucial
to how long and how efficient a search will be, quite unlike random sampling
which depends solely on the size of the searchable area.
Another silly bit of Jovian computer code...
http://www.zachriel.com/randomwalker/
(requires Excel)
>
> And will Pitman ever stop wandering aimlessly?
That is still an unanswered question.
;o)
--
Zachriel
http://zachriel.blogspot.com/2005/12/random-walkers.html
RANDOM WALKERS: And it might just take "zillions" of years!
Zachriel
>
<snip>
>
> Another silly bit of Jovian computer code...
> http://www.zachriel.com/randomwalker/
> (requires Excel)
>
>
Just a few notes for the Google archives:
DEFINITIONS
Walkers = Can move randomly in any of four directions.
Box = Area (lattice, field) where walkers can move about.
Origin = Where the walkers start.
Target = What the walkers are looking for, Dr. Pitman's keys.
Time = number of locksteps,
faster = shorter time.
Steps = walker-steps, total steps for all walkers,
efficiency = fewer steps.
Distance = Direct walking distance.
Budget of Ministry of Silly Walks = £348,000,000
CONTROLS
ctrl-g Go Trials
ctrl-t Single Trial
ctrl-r Runs once
ctrl-e Draws Box
STANDARD MODE
Set the size of box, the number of walkers and the distance to the target.
The origin and the target will be on opposite sides of the center.
Only one parameter can be stepped at a time.
OPTIONS
Setting Walkers (B2) to -1 will generate random sampling
Setting Distance (B4) to 0 will put origin in the center and target on the
edge
Setting Distance (B4) to -1 will generate a random target
TO STOP, Press Esc
WISH LIST:
Redesign random target to allow multiple random targets with given
density.
RESEARCH PROGRAM:
Determine how walkers work within a vast box, and finite distance.
Determine relevance to biological evolution, little or none?
RESEARCH GRANTS:
Pending with the Ministry of Silly Walks.
Zachriel
>
<snip>
>
> Another silly bit of Jovian computer code...
> http://www.zachriel.com/randomwalker/
> (requires Excel)
More notes for the Google archives:
The vast majority of the 'silly bit of Jovian computer code' is user input
and data validation. This is the actual kernal of the program. Not all that
amazing, really. Rather silly, if you ask me.
For w = 1 To indexWalkers
wx = Walkers(w, 1)
wy = Walkers(w, 2)
If flgPath Then Worksheets("Box").Cells(wy,
wx).Interior.ColorIndex = 15
' Take a random step!
r = Rnd
If r < 0.25 Then
wx = wx + 1
If wx > maxX Then wx = maxX - 1
If wx < 1 Then wx = 1
ElseIf r < 0.5 Then
wx = wx - 1
If wx < 1 Then wx = 2
If wx > maxX Then wx = maxX
ElseIf r < 0.75 Then
wy = wy + 1
If wy > maxY Then wy = maxY - 1
If wy < 1 Then wy = 1
Else
wy = wy - 1
If wy < 1 Then wy = 2
If wy > maxY Then wy = maxY
End If
' Update box as required
Worksheets("Box").Cells(wy, wx).Interior.ColorIndex = w Mod 54
Walkers(w, 1) = wx
Walkers(w, 2) = wy
If wx = targetX And wy = targetY Then Winner = True
Next w
Only the "Parameters", "Box", and "Results" worksheets are integral to the
program. The other worksheets are only data, created by copying the
"Results" worksheets after various runs.
--
Zachriel
http://www.zachriel.com/randomwalker/
Seanpit
Zachriel wrote:
> "Seanpit" <seanpi...@naturalselection.0catch.com> wrote in message
> news:1134672404.5...@g47g2000cwa.googlegroups.com...
> > Zachriel wrote:
> >
> >> The issue is that random walkers generally do not have the
> >> same characteristics as random sampling. Only if the origin of each
> >> walker is randomly and independently sampled, does the random walk and
> >> the random sample resemble one another.
> >
> > Random walkers and random samplers do have exactly the same odds of
> > successfully finding a target as long as the target is on the edge of
> > the lattice and the random walkers start in the middle. The origin of
> > each random walker does not have to be "random" for this statement to
> > be true. Ask Leonid if you don't believe me.
>
> That is incorrect. Any point on the edge may be just as likely to be hit,
> but a random sample is more efficient because the walkers concentrate their
> initial efforts close to the origin, and only disperse *somewhat* in finite
> time. The edge is the farthest point possible and is the most difficult case
> for walkers originating at the center. The asserted equivalence of walkers
> and samplers is misleading. The search time of walkers is heavily dependent
> on the exact characteristics of the landscape.
The advantage of random sampling over random walk is negligible. The
are indeed pretty much equivalent as long as the target is on the edge
of the lattice.
> A more appropriate arrangement, in light of your assertions, might be to
> have targets scattered randomly within the lattice, not on its edge.
That wouldn't work as it would give random walk a significant advantage
over random sampling. The only way random walk and random sampling are
pretty much equivalent is if the target is located on the edge of a
limited lattice.
>
> (For "Pitman lost his keys", we'll use bounce off edge method.)
Right . . . as long as the "bounce" is a random bounce.
> Zachriel
> http://zachriel.blogspot.com/
> RANDOM WALKERS: It might just take "zillions" of years!
Sean Pitman
www.DetectingDesign.com
Zachriel
That is simply false. I have provided the means for you (or anyone ekse) to
test this assertion with open source software. It isn't just false, but
wildly incorrect. Consider this series, which consists of the averaging of
two hundred trials.
20 400 1,638
30 900 2,548
40 1,600 3,285
50 2,500 3,575
60 3,600 4,227
70 4,900 5,288
80 6,400 4,767
90 8,100 5,479
100 10,000 5,357
110 12,100 5,265
120 14,400 7,041
130 16,900 6,764
140 19,600 7,185
150 22,500 6,427
160 25,600 6,707
170 28,900 5,935
180 32,400 7,996
190 36,100 7,379
200 40,000 8,395
Zachriel
"Zachriel" <angelma...@zachriel.com> wrote in message
news:11qei2o...@corp.supernews.com...
Please ignore this post. It was sent incomplete.
Zachriel
That is simply false. I have provided the means for you (or anyone ekse) to
test this assertion with open source software. It isn't just false, but
wildly incorrect. Consider this series, which consists of the averaging of
two hundred trials for each row.
Walkers = 10
Distance = 10
Trials = 200
Size Area Steps
20 400 1,638
30 900 2,548
40 1,600 3,285
50 2,500 3,575
60 3,600 4,227
70 4,900 5,288
80 6,400 4,767
90 8,100 5,479
100 10,000 5,357
110 12,100 5,265
120 14,400 7,041
130 16,900 6,764
140 19,600 7,185
150 22,500 6,427
160 25,600 6,707
170 28,900 5,935
180 32,400 7,996
190 36,100 7,379
200 40,000 8,395
Now we know that the number of total 'steps' required on average for a
random sampling is equal to the area of the lattice, Area^1. However (if the
area is large), the steps required for the walkers increases much more
slowly, on the order of Area^0.3
Here's the graph.
http://www.zachriel.com/randomwalker/index.asp#Sizer20to200
(The published results include extensive additional trials not included
above. Same general result, though.)
Why does this answer your question?
According to you, if
Sizer = 20
Walkers = 10
Distance = 10
Then Sampling = Walking.
However, we can see that sampling is much more efficient for this small
area. The efficiency of walkers does not surpass that of samplers until the
Size = 80 and the Area = 6400. Before then, sampling is better — even though
the target is much closer to the origin than the edge.
I'll run some additional trials, but your beliefs in this regard are clearly
incorrect and indicate a misunderstanding of the statistical nature of how a
random walk works.
--
Zachriel
http://www.zachriel.com/randomwalker/
RANDOM WALKERS: And it might just take "zillions" of years!
Zachriel
>
> "Seanpit" <seanpi...@naturalselection.0catch.com> wrote in message
> news:1135025707.1...@g14g2000cwa.googlegroups.com...
>> The advantage of random sampling over random walk is negligible. The
>> are indeed pretty much equivalent as long as the target is on the edge
>> of the lattice.
>
>
<snip>
> I'll run some additional trials, but your beliefs in this regard are
> clearly incorrect and indicate a misunderstanding of the statistical
> nature of how a random walk works.
Your prediction is random sampling takes the same number of steps as random
walkers.
Sizer = 50
Area = 2500
Distance = Edge (24)
Walkers = 1 to 20 step 1
Trials = 100
1 13,475
2 16,107
3 16,061
4 13,834
5 13,947
6 16,437
7 16,663
8 17,084
9 16,953
10 17,000
11 15,032
12 15,381
13 17,473
14 19,637
15 15,514
16 15,214
17 16,928
18 16,916
19 19,190
20 20,457
The power trendline is y = 13743 x^0.0826.
The linear trendline is y = 195.36x + 14414.
The Pitmanian prediction is y = 2500.
(x = walkers, y = steps).
Of course, random sampling should take 2500 'steps'. You are off by only a
factor of about five to eight, depending on the number of walkers. And it
appears the more walkers there are, the more wrong you are.
What can we see from these results when searching for a teleological
(predetermined) target on the edge? Well, the curve is near flat. That's
because by the time the walkers reach the edge they have become largely
dispersed. However, they always take longer (on average) than samplers
because they spend such an inordinate amount of time in the center. The more
walkers, the more steps wasted uselessly in the center. Of course, this is a
highly contrived situation.
The previous graph is much more interesting.
http://www.zachriel.com/randomwalker/index.asp#Sizer20to200
For a target at a near distance, walkers are far more efficient searching
vast regions. In fact, the efficiency for a random sampling approaches zero
as the region to be searched increases, quite unlike walkers.
--
Zachriel
http://www.zachriel.com/randomwalker/
RANDOM WALKERS: And it might just take "zillions" of years!
>
>
> --
> Zachriel
> http://www.zachriel.com/randomwalker/
> RANDOM WALKERS: And it might just take "zillions" of years!
>
>
<snip>
Zachriel
Still another trial:
Walkers = 10
Trials = 100
Sizer = 2 to 50
Area = 4 to 2500
Distance = Edge (1 to 25)
Area Steps
4 10
9 27
16 40
25 79
36 107
49 204
64 219
81 368
100 420
121 603
144 678
169 822
196 916
225 1,193
256 1,080
289 1,446
324 1,791
361 2,016
400 1,989
441 2,350
484 3,078
529 3,078
576 3,071
625 3,786
676 3,820
729 5,058
784 4,669
841 5,217
900 4,869
961 5,625
1,024 5,336
1,089 7,596
1,156 5,526
1,225 8,401
1,296 7,892
1,369 8,782
1,444 8,579
1,521 9,301
1,600 10,947
1,681 9,583
1,764 11,805
1,849 9,783
1,936 14,042
2,025 14,821
2,116 15,763
2,209 14,016
2,304 19,685
2,401 14,306
2,500 16,950
Graphing x = Area, y = Steps
Samplers y = x
Walkers y = 1.9855 x^1.1614
http://www.zachriel.com/randomwalker/Sizer2to50.gif
2,500 <> 16,950
--
Zachriel
http://www.zachriel.com/randomwalker/
RANDOM WALKERS: And it might just take "zillions" of years!
Seanpit
< snip >
> Your prediction is random sampling takes the same number of steps as random
> walkers.
>
> Sizer = 50
> Area = 2500
> Distance = Edge (24)
> Walkers = 1 to 20 step 1
> Trials = 100
< snip >
> The power trendline is y = 13743 x^0.0826.
> The linear trendline is y = 195.36x + 14414.
> The Pitmanian prediction is y = 2500.
> (x = walkers, y = steps).
>
> Of course, random sampling should take 2500 'steps'. You are off by only a
> factor of about five to eight, depending on the number of walkers. And it
> appears the more walkers there are, the more wrong you are.
The average random sampling trial number before success is not equal to
the area. The non-random sampling average is equal to the area.
Increasing the number of random walkers simply decreases the repeat
steps taken before success is achieved. The same thing is true of
increasing the number of random samplers.
There is a difference, of course, between random sampling and random
walk, but with larger lattices, this difference isn't significant as
far as my purposes are concerned.
> What can we see from these results when searching for a teleological
> (predetermined) target on the edge? Well, the curve is near flat. That's
> because by the time the walkers reach the edge they have become largely
> dispersed. However, they always take longer (on average) than samplers
> because they spend such an inordinate amount of time in the center. The more
> walkers, the more steps wasted uselessly in the center. Of course, this is a
> highly contrived situation.
With larger and larger lattices, and a set number of walkers, this
difference becomes negligible. Fairly quickly the walkers become
"mixed", and, at this point, have essentially the same odds of finding
the target as do random samplers.
> Zachriel
> http://www.zachriel.com/randomwalker/
> RANDOM WALKERS: And it might just take "zillions" of years!
Sean Pitman
www.DetectingDesign.com
Zachriel
Seanpit wrote:
> > "Zachriel" <angelma...@zachriel.com> wrote in message
>
> < snip >
>
> > Your prediction is random sampling takes the same number of steps as random
> > walkers.
> >
> > Sizer = 50
> > Area = 2500
> > Distance = Edge (24)
> > Walkers = 1 to 20 step 1
> > Trials = 100
>
> < snip >
>
> > The power trendline is y = 13743 x^0.0826.
> > The linear trendline is y = 195.36x + 14414.
> > The Pitmanian prediction is y = 2500.
> > (x = walkers, y = steps).
> >
> > Of course, random sampling should take 2500 'steps'. You are off by only a
> > factor of about five to eight, depending on the number of walkers. And it
> > appears the more walkers there are, the more wrong you are.
>
> The average random sampling trial number before success is not equal to
> the area. The non-random sampling average is equal to the area.
"non-random sampling" ?!
If you take random samples of a set composed of equiprobable elements,
then the average number of samples to find a singular target is the
number of elements.
> Increasing the number of random walkers simply decreases the repeat
> steps taken before success is achieved. The same thing is true of
> increasing the number of random samplers.
The number of samplers decreases the time arithmetically. If there are
2500 elements and ten samplers, then they will find a singular target
after 250 (on average), a total of 250 * 10 = 2500 samples.
>
> There is a difference, of course, between random sampling and random
> walk, but with larger lattices, this difference isn't significant as
> far as my purposes are concerned.
"As far as my purposes are concerned" ?!
In fact, the larger the lattice, the greater the error in your
assertion. I don't know why you would argue this. Anyone can use RANDOM
WALKERS and see what the facts are.
>
> > What can we see from these results when searching for a teleological
> > (predetermined) target on the edge? Well, the curve is near flat. That's
> > because by the time the walkers reach the edge they have become largely
> > dispersed. However, they always take longer (on average) than samplers
> > because they spend such an inordinate amount of time in the center. The more
> > walkers, the more steps wasted uselessly in the center. Of course, this is a
> > highly contrived situation.
>
> With larger and larger lattices, and a set number of walkers, this
> difference becomes negligible. Fairly quickly the walkers become
> "mixed", and, at this point, have essentially the same odds of finding
> the target as do random samplers.
But walkers don't start mixed. In the evolutionary model you keep
pushing, they start on an island and begin their search from there. And
for targets that are close compared to the size of the space to be
searched, walkers are far more efficient than sampling.
>
> > Zachriel
> > http://www.zachriel.com/randomwalker/
> > RANDOM WALKERS: And it might just take "zillions" of years!
>
> Sean Pitman
> www.DetectingDesign.com
Zachriel
http://zachriel.blogspot.com/
Seanpit
< snip >
> But walkers don't start mixed. In the evolutionary model you keep
> pushing, they start on an island and begin their search from there. And
> for targets that are close compared to the size of the space to be
> searched, walkers are far more efficient than sampling.
It depends. The odds of sampling are not evenly distributed, but are
much greater near the island since single point mutations are much more
common than indels and shorter indels (especially insertions) are
significantly more common than larger indels. As you point out, this
makes close targets much more likely to be hit than more distant
targets - either by random walk or by random sampling. But, this is
also a two-edged sword in that more distant targets are much less
likely to be hit by random sampling and by limited random walkers that
all start on the same island.
Now, as far as random sampling is concerned, consider that the odds of
success are lower given the possibility of repeat sampling. Repeat
sampling increases the average time to success over non-repeat
sampling.
For example, say we have just 2 squares and one of them is the target.
What is the average time to success between a random and a non-random
sampler? The odds of hitting the right square on the first shot are 1
in 2. For the random sampler, what are the odds of hitting the target
on the second shot if the first shot misses? Again, the odds are 1 in
2. Compare this with the non-random sampler where the odds of the
second shot are 1 in 1. So, the non-random sampler will find the
target in at most 2 tries while the random sampler will find the target
in at most an infinite number of tries. We can assume that half the
tries will be successful in one shot with both types of samplers.
However, the other half of the tries will not always be successful in
just 2 tries with random samplers. So, the average number of tries to
achieve success for a non-random sampler is 1.5 tries while the average
for random samplers is 2 tries.
For non-random walk finding a target at the edge of a lattice (not
knowing it is actually at the edge), the average number of steps is
also somewhat less than the size of the lattice. For a random walker in
a larger lattice, the average number of steps is just over the size of
the lattice, but not by too much in a large lattice.
Now, you argue that greater numbers of random walkers starting from the
same starting point increases the number of repeat steps significantly
more than the same number of random samplers. This is true, but for a
large lattice, the relative increase isn't significant enough to much
matter as far as the main point of this discussion is concerned.
Zachriel
Seanpit wrote:
> Zachriel wrote:
>
> < snip >
>
> > But walkers don't start mixed. In the evolutionary model you keep
> > pushing, they start on an island and begin their search from there. And
> > for targets that are close compared to the size of the space to be
> > searched, walkers are far more efficient than sampling.
>
> It depends.
Sounds like the grind of the Patented Pitmanian Goal Post Mover warming
up.
> The odds of sampling are not evenly distributed,
You made a specific claim (12/15/2005) concerning random walkers and
random samplers.
Pitman: "Random walkers and random samplers do have exactly the same
odds of successfully finding a target as long as the target is on the
edge of the lattice and the random walkers start in the middle."
http://groups.google.com/group/talk.origins/msg/505c304b4eb16aaf
This was part of a long discussion concerning abstract walkers in
abstract space including phrases such as "uniform random sampling".
Your claim is false. Random walkers are more efficient than random
samplers if the target is close compared to the size of area to be
searched, but less efficient if the target is on the edge.
<snip>
Zachriel
http://zachriel.blogspot.com/
Seanpit
Zachriel wrote:
< snip >
> This was part of a long discussion concerning abstract walkers in
> abstract space including phrases such as "uniform random sampling".
> Your claim is false. Random walkers are more efficient than random
> samplers if the target is close compared to the size of area to be
> searched, but less efficient if the target is on the edge.
Sure, there is a difference, but it really isn't all that significant
when you start talking large multidimensional lattices. Beyond this,
when you apply it to the main problem we are discussing, the odds of
random sampling are not evenly distributed.
Zachriel
odds of successfully finding a target as long as the target is on the
edge of the lattice and the random walkers start in the middle."
http://groups.google.com/group/talk.origins/msg/505c304b4eb16aaf
Seanpit wrote:
> Zachriel wrote:
>
> < snip >
>
> > This was part of a long discussion concerning abstract walkers in
> > abstract space including phrases such as "uniform random sampling".
> > Your claim is false. Random walkers are more efficient than random
> > samplers if the target is close compared to the size of area to be
> > searched, but less efficient if the target is on the edge.
>
> Sure, there is a difference, but it really isn't all that significant...
Your original claim was "exactly". Your claim was false. Not even
close, and revealed a misunderstanding of the nature of how a random
walk works.
> ... when you start talking large multidimensional lattices. Beyond this,
> when you apply it to the main problem we are discussing, the odds of
> random sampling are not evenly distributed.
Please provide the distribution of probabilities in whatever dimension
you choose, distance to the teleological target, and of course, your
predictions.
Zachriel
Seanpit
Zachriel wrote:
> > Sure, there is a difference, but it really isn't all that significant...
>
> Your original claim was "exactly". Your claim was false. Not even
> close, and revealed a misunderstanding of the nature of how a random
> walk works.
For large lattice structures in multidimensional space, it gets pretty
darn close to "exact". That is why Dembski noted that neither random
walk or random sampling had a significant advantage over the other as
far as finding targets in limited sequence space. Of course, his
thought problem assumed original "mixing" of the random walkers while
mine doesn't. However, the extra time needed to obtain a "mixed"
pattern starting from a common starting point in a large lattice isn't
that significant to the point I'm trying to make here.
< snip >
> Zachriel
Sean Pitman
www.DetectingDesign.com
Zachriel
Seanpit wrote:
> Zachriel wrote:
>
> > > Sure, there is a difference, but it really isn't all that significant...
> >
> > Your original claim was "exactly". Your claim was false. Not even
> > close, and revealed a misunderstanding of the nature of how a random
> > walk works.
>
Before proceeding, let's make sure we are using the same definitions as
Dembski. Random samplers give equal weight to each point of the
lattice. Random walkers give equal weight to each neighbor. And each
sample or step is independent of previous selections.
These are the assumption that Dembski used. Those are the assumptions I
used, except that for multiple walkers, they all start in the same
location, in line with a monoclonal population exploring the local
sequence space.
> For large lattice structures in multidimensional space, it gets pretty
> darn close to "exact". That is why Dembski noted that neither random
> walk or random sampling had a significant advantage over the other as
> far as finding targets in limited sequence space.
He noted that because he built random sampling into his definition of
random walkers.
> Of course, his
> thought problem assumed original "mixing" of the random walkers while
> mine doesn't.
That is a fundamental and inescapable difference.
> However, the extra time needed to obtain a "mixed"
> pattern starting from a common starting point in a large lattice isn't
> that significant to the point I'm trying to make here.
I note you didn't provide the specifics requested. Let me guess. The
size and dimension of the lattice where this is true will be just
outside the reach of a computer simulation. In any case, please provide
specifics.
>
> < snip >
>
> > Zachriel
>
> Sean Pitman
> www.DetectingDesign.com
Zachriel
http://zachriel.blogspot.com/
Zachriel
If a particular strain of walkers is surrounded by vast oceans of
neutrality, then there are no limits as to how far they can travel.
There is no selection across neutral gaps. Our Silly Walkers test only
the process of neutrality. I would like to cite John Cleese's seminal
research in this area. (Cleese, John. "Budgetary Constraints and the
scientific investigation of Silly Walks." Ministry of Silly Walks,
Monty Python's Flying Circus, Episode 14, 1970.)
I invite anyone to try RANDOM WALKERS. Please note that for any target
reasonably close to the origin when compared to the edge, the more
walkers, the more likely they will find the target quickly - before
they disperse. The fewer walkers, and the more distant the target, the
more likely they will disperse before arriving at the target. Here is
the hundred-walker example again.
http://www.zachriel.com/randomwalker/HundredWalkers.gif
That makes the efficiency of walkers primarily a function of numbers
and distance, while the efficiency of samplers is strictly a function
of the area to be searched.
--
Zachriel
http://www.zachriel.com/randomwalker/
RANDOM WALKERS: And it might just take "zillions" of years!
>