wu :: forums « wu :: forums - Lazy hunter catch the rabbit. » Welcome, Guest. Please Login or Register. Jan 24th, 2022, 9:29am RIDDLES SITE WRITE MATH! Home Help Search Members Login Register
 wu :: forums    riddles    hard (Moderators: Icarus, Eigenray, Grimbal, SMQ, william wu, ThudnBlunder, towr)    Lazy hunter catch the rabbit. « Previous topic | Next topic »
 Pages: 1 2 Reply Notify of replies Send Topic Print
 Author Topic: Lazy hunter catch the rabbit.  (Read 15447 times)
ERIC H. ZENGULUS
Newbie

Posts: 11
 Lazy hunter catch the rabbit.   « on: Jun 27th, 2004, 10:16am » Quote Modify

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?

 « Last Edit: Jul 19th, 2004, 7:58pm by Icarus » IP Logged
pedronunezmd
Junior Member

Gender:
Posts: 115
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #1 on: Jun 27th, 2004, 1:32pm » Quote Modify

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.
 « Last Edit: Jun 27th, 2004, 1:41pm by pedronunezmd » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #2 on: Jun 27th, 2004, 2:14pm » Quote Modify

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
104 seconds until +100
and
106 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.

 « Last Edit: Jun 27th, 2004, 3:18pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #3 on: Jun 27th, 2004, 2:57pm » Quote Modify

on Jun 27th, 2004, 10:16am, 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..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ERIC H. ZENGULUS
Newbie

Posts: 11
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #4 on: Jun 27th, 2004, 3:12pm » Quote Modify

on Jun 27th, 2004, 2:57pm, 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.
 IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #5 on: Jun 27th, 2004, 3:37pm » Quote Modify

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|2 = |SIGMA xi|2 + |SIGMA yi|2

 « Last Edit: Jun 27th, 2004, 4:00pm by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #6 on: Jun 28th, 2004, 12:57am » Quote Modify

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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #7 on: Jun 28th, 2004, 2:18am » Quote Modify

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??

 « Last Edit: Jun 28th, 2004, 3:18am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #8 on: Jun 28th, 2004, 2:57am » Quote Modify

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)
 « Last Edit: Jun 28th, 2004, 3:10am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #9 on: Jun 28th, 2004, 5:59am » Quote Modify

on Jun 28th, 2004, 2:57am, 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 Cn/22n+1, where Cn is n-th Catalan number. Now, assymptotically, Cn ~ 4n / ([sqrt][pi] n3/2) – look, for instance, at formula (9) here. Then, the partial sum for the expected value:

[sum]1 [le] n [le] N (2n+1)Cn/22n+1 ~ 1/[sqrt][pi][sum]n-1/2 ~ 2[sqrt](N/[pi]).

 « Last Edit: Jun 28th, 2004, 6:01am by Barukh » IP Logged
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #10 on: Jun 28th, 2004, 6:10am » Quote Modify

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.

 « Last Edit: Jun 28th, 2004, 6:53am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #11 on: Jun 28th, 2004, 6:16am » Quote Modify

Nice analysis, Barukh.

I saw a connection with the Ballot Problem, too.
But, unlike you, I didn't come up with a formula.

 « Last Edit: Jun 30th, 2004, 5:37am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #12 on: Jun 28th, 2004, 7:09am » Quote Modify

on Jun 28th, 2004, 6:10am, 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.
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
ThudnBlunder
wu::riddles Moderator
Uberpuzzler

The dewdrop slides into the shining Sea

Gender:
Posts: 4489
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #13 on: Jun 28th, 2004, 7:30am » Quote Modify

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!)

 « Last Edit: Jun 28th, 2004, 7:33am by ThudnBlunder » IP Logged

THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #14 on: Jun 28th, 2004, 7:46am » Quote Modify

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

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]
 « Last Edit: Mar 25th, 2012, 10:16pm by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
Barukh
Uberpuzzler

Gender:
Posts: 2276
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #15 on: Jun 30th, 2004, 5:26am » Quote Modify

on Jun 28th, 2004, 7:46am, 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 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.
 « Last Edit: Jun 30th, 2004, 5:29am by Barukh » IP Logged
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #16 on: Jun 30th, 2004, 6:27am » Quote Modify

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)?
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #17 on: Aug 19th, 2004, 5:33am » Quote Modify

on Jun 28th, 2004, 2:57am, towr wrote:
 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]

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, which I might delete depending on how this goes. Frankly, I like my problem statement better ... less cluttered
 « Last Edit: Aug 19th, 2004, 5:36am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #18 on: Aug 19th, 2004, 6:10am » Quote Modify

on Aug 19th, 2004, 5:33am, 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.
 « Last Edit: Aug 19th, 2004, 6:22am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: NEW: HARD: Lazy hunter catch the rabbit.   « Reply #19 on: Aug 19th, 2004, 6:20am » Quote Modify

on Aug 19th, 2004, 6:10am, 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?
 « Last Edit: Aug 19th, 2004, 6:23am by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Lazy hunter catch the rabbit.   « Reply #20 on: Aug 19th, 2004, 6:25am » Quote Modify

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..
 IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: Lazy hunter catch the rabbit.   « Reply #21 on: Aug 19th, 2004, 6:29am » Quote Modify

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
 IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
towr
wu::riddles Moderator
Uberpuzzler

Some people are average, some are just mean.

Gender:
Posts: 13730
 Re: Lazy hunter catch the rabbit.   « Reply #22 on: Aug 19th, 2004, 6:53am » Quote Modify

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..
 « Last Edit: Aug 19th, 2004, 6:53am by towr » IP Logged

Wikipedia, Google, Mathworld, Integer sequence DB
william wu

Gender:
Posts: 1291
 Re: Lazy hunter catch the rabbit.   « Reply #23 on: Aug 19th, 2004, 1:45pm » Quote Modify

on Aug 19th, 2004, 6:53am, 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, 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.
 « Last Edit: Aug 19th, 2004, 1:46pm by william wu » IP Logged

[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
c
Newbie

Posts: 6
 Re: Lazy hunter catch the rabbit.   « Reply #24 on: Mar 25th, 2012, 12:22pm » Quote Modify

on Aug 19th, 2004, 1:45pm, 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...
 IP Logged
 Pages: 1 2 Reply Notify of replies Send Topic Print

 Forum Jump: ----------------------------- riddles -----------------------------  - easy   - medium => hard   - what am i   - what happened   - microsoft   - cs   - putnam exam (pure math)   - suggestions, help, and FAQ   - general problem-solving / chatting / whatever ----------------------------- general -----------------------------  - guestbook   - truth   - complex analysis   - wanted   - psychology   - chinese « Previous topic | Next topic »