Author 
Topic: Lazy hunter catch the rabbit. (Read 15447 times) 

ERIC H. ZENGULUS
Newbie
Posts: 11


Lazy hunter catch the rabbit.
« on: Jun 27^{th}, 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 2D plane? And what about a 2D sphere? and what about 3D ...

« Last Edit: Jul 19^{th}, 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 27^{th}, 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 27^{th}, 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 27^{th}, 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 10^{4} seconds until +100 and 10^{6} 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 27^{th}, 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 27^{th}, 2004, 2:57pm » 
Quote Modify

on Jun 27^{th}, 2004, 10:16am, ERIC H. ZENGULUS wrote:And what about a 2D 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 27^{th}, 2004, 3:12pm » 
Quote Modify

on Jun 27^{th}, 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 27^{th}, 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 x_{i}^{2} + SIGMA y_{i}^{2}

« Last Edit: Jun 27^{th}, 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 28^{th}, 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 28^{th}, 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 28^{th}, 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 28^{th}, 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(X1)/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 28^{th}, 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 28^{th}, 2004, 5:59am » 
Quote Modify

on Jun 28^{th}, 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 C_{n}/2^{2n+1}, where C_{n} is nth Catalan number. Now, assymptotically, C_{n} ~ 4^{n} / ([sqrt][pi] n^{3/2}) – look, for instance, at formula (9) here. Then, the partial sum for the expected value: [sum]_{1 [le] n [le] N} (2n+1)C_{n}/2^{2n+1} ~ 1/[sqrt][pi][sum]n^{1/2} ~ 2[sqrt](N/[pi]).

« Last Edit: Jun 28^{th}, 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 28^{th}, 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(X1)/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 28^{th}, 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 28^{th}, 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 30^{th}, 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 28^{th}, 2004, 7:09am » 
Quote Modify

on Jun 28^{th}, 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 28^{th}, 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 28^{th}, 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 28^{th}, 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(NM) (so in this case 90000) [/e]

« Last Edit: Mar 25^{th}, 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 30^{th}, 2004, 5:26am » 
Quote Modify

on Jun 28^{th}, 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(NM) 
 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 NM. A very nice analysis of this problem is given in a classical W. Feller’s book “An Introduction to Probability Theory”, ch. XIV13. P.S. It would take me less time if I had looked at your edit, towr.

« Last Edit: Jun 30^{th}, 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 30^{th}, 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
wu::riddles Administrator
Gender:
Posts: 1291


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

on Jun 28^{th}, 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(X1)/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(X1)/2 which I don't think can be justified using your definition of E(X). If it takes E(X1) time to get to X1, 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(X1)]/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(k1)/2 because if you started at k, then there is a 5050 chance you will end up either a unit higher (k+1) or a unit lower (k1). 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 19^{th}, 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 19^{th}, 2004, 6:10am » 
Quote Modify

on Aug 19^{th}, 2004, 5:33am, william wu wrote:If it takes E(X1) time to get to X1, 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(X1)]/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 X1 and taking a step forward (E(X1)+1). And from X+1 and X1 either direction has a probability of 50%, so E(X) = (E(X+1)+1)*50% + (E(X1)+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 19^{th}, 2004, 6:22am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



william wu
wu::riddles Administrator
Gender:
Posts: 1291


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

on Aug 19^{th}, 2004, 6:10am, towr wrote: Beacuse there is two ways to get to X in one step, from X+1 and from X1, and from X+1 and X1 there's 50% chance to get to X, so f(X) = (f(X+1)+1)*50% + (f(X1)+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 19^{th}, 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 19^{th}, 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
wu::riddles Administrator
Gender:
Posts: 1291


Re: Lazy hunter catch the rabbit.
« Reply #21 on: Aug 19^{th}, 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 19^{th}, 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 (5050 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 Xk in your recursion formula..

« Last Edit: Aug 19^{th}, 2004, 6:53am by towr » 
IP Logged 
Wikipedia, Google, Mathworld, Integer sequence DB



william wu
wu::riddles Administrator
Gender:
Posts: 1291


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

on Aug 19^{th}, 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 Xk 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 superlinear. 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 19^{th}, 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 25^{th}, 2012, 12:22pm » 
Quote Modify

on Aug 19^{th}, 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*(k1) < 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 



