Author |
Topic: Lazy hunter catch the rabbit. (Read 16163 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? and what about 3D ...
|
« 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
wu::riddles Administrator
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
wu::riddles Administrator
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
wu::riddles Administrator
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
wu::riddles Administrator
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 |
|
|
|
|