

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 2D plane? And what about a 2D 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:
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. 

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:


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:
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:
In 2D he is probably referring to z where (roughly speaking) z^{2} = SIGMA x_{i}^{2} + SIGMA y_{i}^{2} 

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:
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(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) 

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:
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 (http://mathworld.wolfram.com/CatalanNumber.html). Then, the partial sum for the expected value: :D 

Title: Re: NEW: HARD: Lazy hunter catch the rabbit. Post by THUDandBLUNDER on Jun 28^{th}, 2004, 6:10am Quote:
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:
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:
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(NM) (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:
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 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. ;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(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 (http://www.ocf.berkeley.edu/~wwu/cgibin/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:
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. 

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:
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 (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.. 

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:
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 (http://www.ocf.berkeley.edu/~wwu/cgibin/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:
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... :/ 

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:
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:
Which part do you have a problem with? That the sequences that terminate when HT=2 for the first time are exactly those that are made up of two independent sequences, each of which terminated when HT=1 for the first time? That the second HT=1 sequence is independent of the first? That E(k) is being defined as the expected length of a sequence which terminates when HT=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:
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_{i}P(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_{i}P(I&J) + y_{j}P(I&J)) = SUM_{i,j}(x_{i}P(I&J)) + SUM_{i,j}(y_{j}P(I&J)) SUM_{i,j}(x_{i}P(I&J)) = SUM_{i}(SUM_{j}(x_{i}P(I)P(JI))) For any given i, since x_{i} and P(I) are independent of j: SUM_{j}(x_{i}P(I)P(JI)) = x_{i}P(I)*SUM_{j}(P(JI)) since, for any given i: SUM_{j}(P(JI)) = 1 we have: SUM_{i,j}(x_{i}P(I&J)) = SUM_{i}(x_{i}P(I)) = E(X) and similarly (provided the sums are asolutely convergent): SUM_{i,j}(y_{j}P(I&J)) = E(Y) so: E(X+Y) = E(X) + E(Y) QED 

Powered by YaBB 1 Gold  SP 1.4! Forum software copyright © 20002004 Yet another Bulletin Board 