wu :: forums - Print Page


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

        riddles >> hard >> Lazy hunter catch the rabbit.
        
(Message started by: ERIC H. ZENGULUS on Jun 27^th, 2004, 10:16am)

Title: Lazy hunter catch the rabbit.
Post by ERIC H. ZENGULUS on Jun 27^th, 2004, 10:16am

Discrete one dimensional line. Rabbit starts from zero jumps one step left or right randomly every second. Lazy hunter sleeps at +100 point and wait for the rabbit to come. Averagely how many seconds the hunter have to wait b4 the rabbit hits on him ?

And what about a circle of 1000 points?
And what about a 2-D plane?
And what about a 2-D sphere?
and what about 3D ...

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by pedronunezmd on Jun 27^th, 2004, 1:32pm

Well, for a one dimensional line, the answer is somewhere around "infinite number of seconds" for the average wait time.

Try running this scenario with the hunter just waiting at the +1 point instead of the +100 point. Depending on how long you're willing to allow the rabbit to jump into the negative ranges, even the average wait time for this is quite high. (For example, counting the rabbit reaching the -1,000,000 time mark as a maximum limit of time, you get an average wait time of about 1500 seconds for 20,000 trials, with about 20 of those trials ending because the rabbit reached the -1,000,000 time mark and otherwise would have skewed the average even more.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 27^th, 2004, 2:14pm

Quote:

Well, for a one dimensional line, the answer is somewhere around "infinite number of seconds" for the average wait time.

But even for the 2D 'circle', after n steps the expected rms distance is sqrt(n).
And the rabbit will (almost certainly for large n) need less than n steps to reach sqrt(n) for the first time.

So I make it less than
10⁴ seconds until +100
and
10⁶ seconds until +1000

In other words, not as long as you appear to think.

For the 2D plane (where the hunter waits at a positive distance from the origin) I think we need to multiply the above numbers by 4.

I'm not sure if the same metric can be applied to the 3D case.

Of course, for the the 1D case the expected waiting time will be shorter.
I expect it wil involve a summation of the formula used in the previous rabbit puzzle.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 27^th, 2004, 2:57pm

on 06/27/04 at 10:16:05, ERIC H. ZENGULUS wrote:

And what about a 2-D sphere?

I'm not sure what you mean by this.. If you mean the surface of a sphere, I'd like to know how you'd define a discrete grid on it in any intuitive sense..

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by ERIC H. ZENGULUS on Jun 27^th, 2004, 3:12pm

on 06/27/04 at 14:57:41, towr wrote:

I'm not sure what you mean by this.. If you mean the surface of a sphere, I'd like to know how you'd define a discrete grid on it in any intuitive sense..

right, i'm thinking of the surface of a sphere but i've no idea how to define it in a discrete way. i dont know the answer to the problems i posed.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 27^th, 2004, 3:37pm

Quote:

I'm not sure what you mean by this.. If you mean the surface of a sphere, I'd like to know how you'd define a discrete grid on it in any intuitive sense..

In 2D he is probably referring to |z| where (roughly speaking)

|z|² = |SIGMA x_i|² + |SIGMA y_i|²

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 28^th, 2004, 12:57am

well, that doesn't help me any..

Anyway, looking at the 1D line
Using a markov model, I so far get an expected time
greater than 70186.2 seconds
That's with 0.920344 rabbits got caught so far, the rest is almost all still between -10000 and 100. I also think this will go to infinity, as it's only about 16000 when 75% is caught, so it rises rapidly with the last few percentages.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 28^th, 2004, 2:18am

Quote:

I also think this will go to infinity,

towr, for the 1D case are you saying that you think the expected waiting time for the rabbit to hit +/-100 is infinite? If so, between which two integers does the expected waiting time jump from finite to infinite??

???

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 28^th, 2004, 2:57am

Even the expected time for getting to 1 will be infinitely long.

Consider this
the recursive formula for the expected time to get from 0 to X (i.e. move X steps forward) is
E(0) = 0
E(X) = 1 + E(X+1)/2 + E(X-1)/2

So E(1) = 1 + E(2)/2
But E(2) should be equal to 2 * E(1) (take one step, and then another)
So E(1) = 1 + E(1), which means E(1) = [infty]
And this despite the fact that the rabbit does get to 1 with probability 1..

The expected time in the 2D/3D plane is of course at least as bad (it'd be worse if it were possible, in the 3D case the rabbit won't even get to the hunter with probability 1 anymore, though it does in the 2D case)

This leaves the ring, and maybe the sphere if anyone can make sense of it.
The surface of a torus might also be interesting (f.i. a 1000x1000 square where the top wraps around to the bottom, and the left wraps around to the right)

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by Barukh on Jun 28^th, 2004, 5:59am

on 06/28/04 at 02:57:12, towr wrote:

Even the expected time for getting to 1 will be infinitely long.

That’s correct, although not intuitive (at least for me…)! Here’s an analysis I did (it adds only the assymptotic growth to towr’s result).

The probability to get to 1 after 2n+1 steps equals C_n/2²ⁿ⁺¹, where C_n is n-th Catalan number. Now, assymptotically, C_n ~ 4ⁿ / ([sqrt][pi] n^3/2) – look, for instance, at formula (9) here (http://mathworld.wolfram.com/CatalanNumber.html). Then, the partial sum for the expected value:

[sum]_{1 [le] n [le] N} (2n+1)C_n/2²ⁿ⁺¹ ~ 1/[sqrt][pi][sum]n^-1/2 ~ 2[sqrt](N/[pi]).
:D

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 28^th, 2004, 6:10am

Quote:

Consider this
the recursive formula for the expected time to get from 0 to X (i.e. move X steps forward) is
E(0) = 0
E(X) = 1 + E(X+1)/2 + E(X-1)/2
So E(1) = 1 + E(2)/2
But E(2) should be equal to 2 * E(1) (take one step, and then another)
So E(1) = 1 + E(1), which means E(1) =
And this despite the fact that the rabbit does get to 1 with probability 1..

Yes, I see.

I remember reading 'The Theory of Stochastic Processes' by Cox & Miller years ago and really enjoying the stuff that I could understand. No doubt I knew the above fundamental result at one time but forgot it.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 28^th, 2004, 6:16am

Nice analysis, Barukh. 8)

I saw a connection with the Ballot Problem (http://mathworld.wolfram.com/BallotProblem.html), too.
But, unlike you, I didn't come up with a formula. :-[

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 28^th, 2004, 7:09am

on 06/28/04 at 06:10:09, THUDandBLUNDER wrote:

I suppose the 'common sense' way to look at it is:
The expected waiting time for an event with probability p = 1/p
The probability of the point arriving at +1 > 1/2
'Therefore' the expected waiting time < 2

That's the answer to another question, where the events are independent of previous steps.
f.i. the average time you have to wait till the rabbit makes a hop to the right is 2 as you'd expect.
However when you want to know the expected time until the rabbit get's to +1, it will depend on all previous jumps, so you can't use a result that relies on independence.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by THUDandBLUNDER on Jun 28^th, 2004, 7:30am

Quote:

That's the answer to another question, where the events are independent of previous steps.

Yes towr, I deleted that more than an hour ago!
(Like the turtle, I may be slow - but, like the rabbit, I'm hard to keep up with!) :P

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 28^th, 2004, 7:46am

Ah well, it's not like you never quoted something I deleted before you posted your reply to it :P

Anyway..
The ring variant seems to have a finite expected value, though still very high (about 90000 seconds, so the hunter would have to wait 25 hours).

Here's two plots of my simulations (the first one for the circle, the other for the line)
http://towr.home.fmf.nl/rabbit_ring.png
http://towr.home.fmf.nl/rabbit_1D.png

[e]
analytically, for a ring of N points, to get to a point at distance M from the start, I get an expected time of E = M(N-M)
(so in this case 90000)
[/e]

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by Barukh on Jun 30^th, 2004, 5:26am

on 06/28/04 at 07:46:26, towr wrote:

analytically, for a ring of N points, to get to a point at distance M from the start, I get an expected time of E = M(N-M)

Correct again! It took me some time to understand that this case is equivalent to the classical Ruin Problem (http://mathworld.wolfram.com/GamblersRuin.html) with gamblers’ initial capitals M and N-M. A very nice analysis of this problem is given in a classical W. Feller’s book “An Introduction to Probability Theory”, ch. XIV1-3.

P.S. It would take me less time if I had looked at your edit, towr. ;D

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Jun 30^th, 2004, 6:27am

So how about a torus? (an MxN field wrapped top to bottom and left to right, and the rabbit has to get from 0,0 to n,m)
And how about a hypertorus (3D or possibly higher dimensional surface)?

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by william wu on Aug 19^th, 2004, 5:33am

on 06/28/04 at 02:57:12, towr wrote:

Sorry, but I question the validity of this argument. Using the definition "E(X) = expected time to get from 0 to X.", I agree that E(2) = 2*E(1). However, then this is plugged into a recurrence

E(X) = 1 + E(X+1)/2 + E(X-1)/2

which I don't think can be justified using your definition of E(X). If it takes E(X-1) time to get to X-1, and E(X+1) time to get to X+1, why would the expected time to reach X simply be the average of these values ( [E(X+1) + E(X-1)]/2 ) plus 1? Rather if anything, the hitting time should get exponentially worse the farther your destination is away from the origin.

Perhaps your intentions were the following: let f(k) = Expected time to get to X, given that you started at k.Then one can clearly say

f(X) = 0
f(k) = 1 + f(k+1)/2 + f(k-1)/2

because if you started at k, then there is a 50-50 chance you will end up either a unit higher (k+1) or a unit lower (k-1). And then your situation is just like it was in the beginning, but with a new starting point for the random walk. Finally, we add 1 to the expectation since you just spent a step. You can use this framework to show that the expected time to hit 1 is infinite, but it takes some more work. I have a hint on how to show it in a different thread (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1092457471;start=1), which I might delete depending on how this goes. Frankly, I like my problem statement better ... less cluttered ::)

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by towr on Aug 19^th, 2004, 6:10am

on 08/19/04 at 05:33:41, william wu wrote:

If it takes E(X-1) time to get to X-1, and E(X+1) time to get to X+1, why would the expected time to reach X simply be the average of these values ( [E(X+1) + E(X-1)]/2 ) plus 1?

Because there are two ways to get to X, either by getting to X+1 and then taking a step back (E(X+1) +1), or by getting to X-1 and taking a step forward (E(X-1)+1).
And from X+1 and X-1 either direction has a probability of 50%, so E(X) = (E(X+1)+1)*50% + (E(X-1)+1)*50%. That it happens to be the average is just because from moving in any direction is equally likely..

Anyway, there is symmetry. The expected time to get from X to 0 is equal to that of 0 to X. And since we start at 0 and want to get to X I like starting there, and not working backwards from X.

Title: Re: NEW: HARD: Lazy hunter catch the rabbit.
Post by william wu on Aug 19^th, 2004, 6:20am

on 08/19/04 at 06:10:52, towr wrote:

Beacuse there is two ways to get to X in one step, from X+1 and from X-1, and from X+1 and X-1 there's 50% chance to get to X, so f(X) = (f(X+1)+1)*50% + (f(X-1)+1)*50%. That it happens to be the average is just because from any point any direction is equally likely..

WLOG let's say X is positive. Then since all the increments are unitary, if you are at X+1, then you must have already passed through X. At that point the random walk stops, since we are computing the expected time till the walk first hits X. Thus going to X+1 and coming back isn't a valid path; I don't think this is accounted for. Furthermore, wouldn't you intuitively agree that if you walk randomly start at 0, it should get "more than linearly difficult" to reach points that are farther away?

Title: Re: Lazy hunter catch the rabbit.
Post by towr on Aug 19^th, 2004, 6:25am

It's been almost two months.. I'm pretty sure I worked it out properly the first time, but If you really want me to look into it again it'll take some time, I don't expect the results to change though..

Title: Re: Lazy hunter catch the rabbit.
Post by william wu on Aug 19^th, 2004, 6:29am

Heh well, I'm sure others will pipe in soon regardless. I could be wrong ... I have a tendency to post nonsense at 6 am. In fact, I think I'll go to bed now. Good night towr ;)

Title: Re: Lazy hunter catch the rabbit.
Post by towr on Aug 19^th, 2004, 6:53am

hmm.. I remember now

We start at 0 and have to make one step to the right, E(1)
We have to make at least one step in some direction because we're not yet at 1.
So at the next moment we are at either 1 or -1 (50-50 chance, and one step made)
If we're at 1 we don't have to do any more steps to the right E(0)
and if we're at -1 we have to do two steps to the right E(2)
And that's of course equal to doing one step to the right and then another, 2*E(1)

so E(1) = 1 + (E(0)+E(2))/2
and E(0)=0 and E(2) = 2* E(1)
and thus E(1) is [infty]

my X in E(X) isn't a fixed point, it just says how many steps to the right you want to go, so it should be equivalent to X-k in your recursion formula..

Title: Re: Lazy hunter catch the rabbit.
Post by william wu on Aug 19^th, 2004, 1:45pm

on 08/19/04 at 06:53:07, towr wrote:

my X in E(X) isn't a fixed point, it just says how many steps to the right you want to go, so it should be equivalent to X-k in your recursion formula..

I agree now towr. That is neat! At first I was very disturbed by the line E(2) = 2*E(1), because that suggests that E(k) = k*E(1), and yet the growth should be super-linear. However, this suggests that the only solution is E(1) = [infty]. Then by plugging into the recurrence, you show that if E(1) is finite, nonsense results.

Here is another way to show this ...

Problem Recap: Starting at zero, you repeatedly flip a fair coin and move one step right if it comes up heads, and one step left if it comes up tails. Show that the expected time to reach +1 is infinite.

Alternative Solution: Define the random variable

[tau]' = time to hit 1.

From More Heads Than Tails (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi?board=riddles_medium;action=display;num=1068612055), we know that if

[tau] = time to hit either A or -B

then E([tau]) = AB. Let [tau]_B = time to hit either +1 or -B. Since the boundaries of [tau]_B are more constrained than those of [tau]', we must have

E([tau]') >= E([tau]_B) = B

for any finite B. Since B is arbitrary, E([tau]') = [infty].

Likewise, the expected time to reach -1 is also [infty]. And yet on the first step, the gambler must hit either +1 or -1.

Title: Re: Lazy hunter catch the rabbit.
Post by c on Mar 25^th, 2012, 12:22pm

on 08/19/04 at 13:45:26, william wu wrote:

At first I was very disturbed by the line E(2) = 2*E(1), because that suggests that E(k) = k*E(1)

Actually, it can be proven by induction that:

E(k) = k * E(1) - k*(k-1) < k * E(1), for all k > 1...

But this approach got me nowhere (and no, i can't easily swallow your "E(2) should be equal to 2 * E(1)"), so i guess i must resort to p(s, k) - computing the probability that after s steps the position is k... :-/

Title: Re: Lazy hunter catch the rabbit.
Post by rmsgrey on Mar 26^th, 2012, 5:47am

on 03/25/12 at 12:22:07, c wrote:

(and no, i can't easily swallow your "E(2) should be equal to 2 * E(1)")

In order to get two more heads than tails for the first time in a sequence of coin tosses, you have to, at some point have one more heads than tails for the first time. If you break the sequence into two at that point, you have a first "half" which runs until you have one more heads than tails for the first time, and a second "half" which runs until you have one more heads than tails in the second "half" for the first time.

The expected time for the whole thing is E(2), and the expected time for each half is E(1) (since the two "halves" are independent) so we get:

E(2) = E(1) + E(1) as required.

Title: Re: Lazy hunter catch the rabbit.
Post by c on Mar 26^th, 2012, 5:59am

That's the same storytelling towr did. But can you prove it? (sorry to dismiss your argument like this, but if i could accept yours, i'd've already accepted his...)

Title: Re: Lazy hunter catch the rabbit.
Post by rmsgrey on Mar 26^th, 2012, 6:11am

on 03/26/12 at 05:59:43, c wrote:

That's the same storytelling towr did. But can you prove it? (sorry to dismiss your argument like this, but if i could accept yours, i'd've already accepted his...)

Which part do you have a problem with?

That the sequences that terminate when H-T=2 for the first time are exactly those that are made up of two independent sequences, each of which terminated when H-T=1 for the first time?

That the second H-T=1 sequence is independent of the first?

That E(k) is being defined as the expected length of a sequence which terminates when H-T=k for the first time?

That the expected length of the sequence formed by concatenating two independent sequences is the sum of their individual expected lengths?

That the above collectively implies that E(2)=2E(1)?

Title: Re: Lazy hunter catch the rabbit.
Post by c on Mar 26^th, 2012, 6:13am

"That the expected length of the sequence formed by concatenating two independent sequences is the sum of their individual expected lengths". Thank you for considering my objection.

Title: Re: Lazy hunter catch the rabbit.
Post by rmsgrey on Mar 26^th, 2012, 7:02am

on 03/26/12 at 06:13:06, c wrote:

"That the expected length of the sequence formed by concatenating two independent sequences is the sum of their individual expected lengths". Thank you for considering my objection.

Actually, the independence isn't necessary here...

Letting I and J be the events X=x_i and Y=y_j respectively:

By definition:

E(X) = SUM_i(x_iP(I))

that is, the sum of (the individual outcomes times their probability of occuring).

E(X+Y) = SUM_i,j((x_i+y_j)P(I&J))

= SUM_i,j(x_iP(I&J) + y_jP(I&J))

= SUM_i,j(x_iP(I&J)) + SUM_i,j(y_jP(I&J))

SUM_i,j(x_iP(I&J)) = SUM_i(SUM_j(x_iP(I)P(J|I)))

For any given i, since x_i and P(I) are independent of j:

SUM_j(x_iP(I)P(J|I)) = x_iP(I)*SUM_j(P(J|I))

since, for any given i:

SUM_j(P(J|I)) = 1

we have:

SUM_i,j(x_iP(I&J)) = SUM_i(x_iP(I)) = E(X)

and similarly (provided the sums are asolutely convergent):

SUM_i,j(y_jP(I&J)) = E(Y)

so:

E(X+Y) = E(X) + E(Y)

QED