wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> easy >> Cross the infinite wall
        
(Message started by: pscoe2 on May 11^th, 2010, 4:41am)

Title: Cross the infinite wall
Post by pscoe2 on May 11^th, 2010, 4:41am

Hi,

I tried to look for a similar already posted riddle but could not find one. I am sorry if this is a repost.

The question is that there is an infinite wall with only 1 gate to get through it.
You are dropped off at a random location and are asked to go to the other side.

What is the best approach for this problem.

thanks,
Puneet

Title: Re: Cross the infinite wall
Post by towr on May 11^th, 2010, 4:50am

[hide]If you go along the wall in one direction there's a 50% chance you will miss the gate, so you'll need to go backwards and forwards in some way.
I don't know what would be optimal, but you could double or triple the distance every time you switch direction.[/hide]

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 11^th, 2010, 4:54am

I haven't given it much thought, but [hide]perhaps it involves the properties of a 1-D random walk (http://en.wikipedia.org/wiki/Random_walk#One-dimensional_random_walk), where we can place the gate at the origin WLOG. :)
However, we would need to prove that no method exists that is more efficient than tossing a fair coin[/hide].

Title: Re: Cross the infinite wall
Post by icecoldcelt on May 12^th, 2010, 8:40am

Is it infinitely tall? :P

Title: Re: Cross the infinite wall
Post by SMQ on May 12^th, 2010, 9:18am

on 05/11/10 at 04:54:11, ThudanBlunder wrote:

[hide]However, we would need to prove that no method exists that is more efficient than tossing a fair coin[/hide].

I think that's unlikely to be true. [hide]At any given time you have searched some continuous region of the line. Recrossing this region yields no new information--you already know the door isn't there. Therefore, at a minimum, any time spent by a random walk within the region already searched could be better spent either extending the searched region or crossing the region directly.[/hide]

--SMQ

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 12^th, 2010, 9:42am

on 05/12/10 at 09:18:40, SMQ wrote:

I think that's unlikely to be true.
--SMQ

I agree with your reason. (Well, I did say I hadn't given it much thought.) :)
But I'm not sure if the OP has any reason for putting this in Easy.

on 05/12/10 at 09:18:40, SMQ wrote:

--SMQ

And what does the Q stand for? ;)

Title: Re: Cross the infinite wall
Post by SMQ on May 12^th, 2010, 10:07am

on 05/12/10 at 09:42:12, ThudanBlunder wrote:

And what does the Q stand for? ;)

Believe it or not: nothing at all. It's just a letter I chose because my actual initials are too generic.

--SMQ

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 12^th, 2010, 11:11am

on 05/12/10 at 10:07:16, SMQ wrote:

Believe it or not: nothing at all. It's just a letter I chose because my actual initials are too generic.

--SMQ

Exactly what I said to rmsgrey the other day.

Title: Re: Cross the infinite wall
Post by rmsgrey on May 12^th, 2010, 3:00pm

Choosing randomly from infinity gets messy.

It's fairly easy to come up with an approach that's guaranteed to find the gate after travelling a finite distance provided you start within a finite distance of it - just keep changing direction, walking at least one step further after each turn.

Deciding how to compare different approaches is tricky - you can't talk sensibly about expected time to the gate without knowing more about the random distribution involved...

Title: Re: Cross the infinite wall
Post by towr on May 12^th, 2010, 3:16pm

How would it work out with the gate's location was given by a (known) normal distribution with the mean at the location where you were dropped? So for example going one standard deviation in one direction, and two standard deviations in return would give you over 68.2% chance of having found the gate. (Expected time is a bit more complicated)
What would be the best path to follow?

Title: Re: Cross the infinite wall
Post by pscoe2 on May 12^th, 2010, 11:47pm

The way i was thinking this can be done best is to go logrithmically.

Like go n miles in 1 direction and then 2n in other... 4n back in first then 8n in other and so on till you find the gate..

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 13^th, 2010, 4:26am

on 05/12/10 at 15:16:14, towr wrote:

How would it work out with the gate's location was given by a (known) normal distribution with the mean at the location where you were dropped?

That's one model, but isn't a uniform distribution more natural and less anthropocentric. LOL

on 05/12/10 at 23:47:55, pscoe2 wrote:

Like go n miles in 1 direction and then 2n in other... 4n back in first then 8n in other and so on till you find the gate..

With a uniform distribution perhaps a Fibonacci switch is more efficient (as when searching and sorting). :-/

Title: Re: Cross the infinite wall
Post by towr on May 13^th, 2010, 4:29am

on 05/13/10 at 04:26:18, ThudanBlunder wrote:

That's one model, but isn't a uniform distribution more natural and less anthropocentric.

Err, how do you imagine getting a uniform distribution on an infinite domain?
And besides, most things in nature seem to follow/approximate a normal distribution. I don't see what's anthropocentric about it.

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 13^th, 2010, 4:35am

on 05/13/10 at 04:29:09, towr wrote:

Err, how do you imagine getting a uniform distribution on an infinite domain?

Oh dear, I just edited my post to mention that very matter. Then I unedited it.

As for the rest, I suggest you lighten up.

Title: Re: Cross the infinite wall
Post by towr on May 13^th, 2010, 4:43am

*throws molotov cocktail at ThudanBlunder*
Will that do for lighting things up ? ::)

Title: Re: Cross the infinite wall
Post by ThudanBlunder on May 13^th, 2010, 5:19am

on 05/13/10 at 04:43:56, towr wrote:

*throws molotov cocktail at ThudanBlunder*
Will that do for lighting things up ? ::)

The problem being 1-D does not require us to be. :P

Anyway, is there any reason to assume that we will be dropped off at the most favourable point on the distribution?

Title: Re: Cross the infinite wall
Post by Obob on May 13^th, 2010, 6:18am

If you aren't dropped at the most favorable point in the distribution, you have to further know the distribution of your starting point (the simplest possibility other than starting at the mean of the door's distribution is probably using the door's distribution as your starting point distribution as well). This further complicates the problem, which already seems fairly hard even in the case where you start at the mean.

Title: Re: Cross the infinite wall
Post by SMQ on May 13^th, 2010, 7:01am

on 05/13/10 at 04:26:18, ThudanBlunder wrote:

With a uniform distribution perhaps a Fibonacci switch is more efficient (as when searching and sorting). :-/

Unfortunately, a uniform distribution is sufficiently nonsensical (not only is there 0 probability of the door being at any chosen x, there is 0 probability of it being in any finite neighborhood of x) that it leads straightforwardly to a nonsensical solution:

Assume first a finite uniform distribution of width 2k--i.e. you are told you will be dropped off somewhere within k units of the door with uniform probability. It should be clear that no strategy can beat the obvious one: walk k units in one direction, then at most 2k units back the other way. This gives an expected distance of 3k/2. Any strategy with more reversals involves more average time spent traversing the region already searched and so loses to the simple strategy.

Now we see that in the limit as k approaches infinity, the best strategy approaches: "head out in one direction and walk to infinity," a strategy with only a 50% chance of success.

Seen another way, any strategy will be in steps of the form "cross the already-searched region, then continue onward some distance further." Given a uniform distribution, it would seem obvious that for any useful solution these steps should be scale-invariant--i.e. the further distance is always in the same proportion to the distance already searched--since the real number line is itself scale-invariant.

But now we find that a larger constant of proportionality is always more efficient than a smaller one, and again the limit of the strategy is to head out in one direction and hope it's the right one.

Either way, we find that any strategy on a "uniform" distribution which guarantees finding the door in finite time can be beaten by a strategy with larger steps, and so we conclude that there cannot be any such winning strategy.

--SMQ

Title: Re: Cross the infinite wall
Post by Grimbal on May 14^th, 2010, 2:52am

It is more natural to think that the door is at a fixed position, and that we have been dropped at a random posiiton with a known distribution (that distribution including our lack of knowledge of the actual distribution).
It is not unreasonable to think the distribution is centered on the door, using the symmetry of the situation. That argument is door-centric.

But then it happens that once you have been dropped, the distribution of the position of the door as compared to your starting position is the reverse distribution of your position as compared to the door's. So the idea that we probably start at the center of the distribution of where the door is is not anthropocentric (or ego-centric).

Title: Re: Cross the infinite wall
Post by monday on Jun 10^th, 2010, 10:43am

Well since the Earth is round, if you walk in one direction, you would eventually come to the gate, right?

Title: Re: Cross the infinite wall
Post by Hippo on Jun 11^th, 2010, 5:28am

Hi, I were not here for a while ... but surely this one was in some of the forums. I would expect towr searching abilities to find it ;).

Good measure here is comparison of optimal path len and the path len given by the algorithm.
Of course optimal algorithm choses geometric series with negative base and wents alternatively to points with corresponding cordinate (unless the hole is found). The question is to chose the optimal base.

I cannot remember it and I am lazy to count it now, but I suppose it was either -2 or -q (with q the golden ration (1+\sqrt{5})/2).

http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1206479450
http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_hard;action=display;num=1183214402

(Shortly ... q correspond to optimum for sum of turnpoint distances and 2 to optimum for walked path, but the generalisation to k-way search with k/(k-1) is also worth to mention (with \infty for only one way :D))

Title: Re: Cross the infinite wall
Post by Grimbal on Jun 11^th, 2010, 8:25am

I though about this the other day, and there might such a thing as an uniform distribution over the infinite space.

It looks like this:
Generate a random number r₀ uniformly between 0 and 1.

This fixes the door's position as r₀ (mod 1). Here mod is understood in reals.

Then start walking according to your favorite strategy.

When you reach a position r₀ (mod 1), you select a random integer i₁ in {0,1} and add it to r₀.
r₁ = r₀ + 1*i₁.

The door position is now fixed as r₁ (mod 2).

Etc. When you reach a position r_n (mod 2ⁿ), you select a random integer i_n+1 in {0, 1} and extend you range. r_n+1 = r_n + 2ⁿ*i_n+1.

The door position is now fixed as r_n+1 (mod 2ⁿ⁺¹).

This process is for all practical purposes equivalent to choosing the door uniformly over an infinite space, except that you never actually know where the door is. You just know where it is not. And it makes it plain obvious that you will never reach it. Or more precisely, you will reach it with probability 0 (which is the probability to flip a coin an infinite number of times and get tails every single time*).

* well, yes, Chuck Norris could do that.

Title: Re: Cross the infinite wall
Post by towr on Jun 11^th, 2010, 12:52pm

It isn't a uniform distribution over all reals for any n, though. And if you let n go to infinity, I don't see how it is any better than taking _{lim x -> inf} x*r₀; or avoids the same problems.

Title: Re: Cross the infinite wall
Post by Grimbal on Jun 13^th, 2010, 6:02am

Well, yes. It is not a distribution in the mathematical sense.

In fact, it illustrates that the limit to infinity of a uniform distribution results in the zero function, which is not a distribution any more.

But at least, you can send the poor guy searching. ;D This process gives a feel of what it would be like to search for a door located "anywhere on the real line". It shows that the door wouldn't be anywhere you can reach in finite time.

Of course, the fact that it fails to actually place the door anywhere shows that there is something wrong with the concept. But that problem is conveniently hidden at the end of times.