1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Challenge 7b: A Snail's Pace

  1. Nov 17, 2013 #1

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This question is courtesy of mfb:

    An immortal snail is at one end of a perfect rubber band with a length of 1km. Every day, it travels 10cm in a random direction, forwards or backwards on the rubber band. Every night, the rubber band gets stretched uniformly by 1km. As an example, during the first day the snail might advance to x=10cm, then the rubber band gets stretched by a factor of 2, so the snail is now at x=20cm on a rubber band of 2km.

    The challenge: Approximate the probability that it will reach the other side at some point (better approximations are obviously preferred, but any bounds are acceptable as long as they are found by doing something interesting)
     
  2. jcsd
  3. Nov 22, 2013 #2
    Well, if no one else is going to say something...

    Using [STRIKE]probability axioms[/STRIKE] super-cool, interesting dark magic and sorcery, we obtain the bounds for the probability ##0\leq p\leq 1##.

    ...Anyone else? :tongue:
     
  4. Nov 23, 2013 #3

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That is not sufficient to qualify for "something interesting" :p.
    7a gives an easy lower bound, but that is really low.
     
  5. Nov 23, 2013 #4

    (1) When you say "rubber band" do you mean a loop as in an ordinary rubber band? And if so, then what do you mean by "the other side"?


    (2) If it's just a rubber strip 1km in initial length and he starts at 0, what happens if he moves backwards the first time?
     
  6. Nov 23, 2013 #5

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    Let's say that the other end of the rubber band is to the right, just to establish a direction. What happens on day one, with a 50-50 chance, the snail decides to move left? Does it fall into a frying pan to become escargot?

    I don't think you want the direction to be random if the snail is at the end.

    An alternative specification of the problem is to place the snail in the middle of a 2 km long rubber band that stretches 2 km longer every night. Now the question is to find the probability that the snail reaches either end at some point in time.
     
  7. Nov 23, 2013 #6

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    No loop. A rubber strip, if you like.

    It will not move backwards if that is not possible. Alternatively, use D H's extension of the rubber band. If the solution is sensitive to that detail, it is really good.
    The snail does not fall down :D.
     
  8. Nov 23, 2013 #7

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    You can assume that he either just doesn't step, or that he steps to the right if he's up against the leftmost side, whichever makes calculations for you easier (I know I'm being nice here :p)
     
  9. Nov 23, 2013 #8
    I think I'm onto something.

    Define [itex]a_n[/itex] to be the position of the snail relative to the start, in cm.
    Then the following recurrence relation is true: [itex]a_{n+1} = (a_n+10χ_n)\frac{n+2}{n+1}[/itex], where [itex]χ_n[/itex] is a random variable taking values in [itex] \{ 1, -1 \} [/itex] with equal probability 1/2.

    Rearranging a bit, we get [itex]\frac{a_{n+1}}{n+2} = \frac{a_n}{n+1} + 10\frac{χ_n}{n+1}[/itex].

    From this, it follows that [itex]\frac{a_n}{n+1} = 10\sum_{k=1}^{n}\frac{χ_{k-1}}{k}[/itex]
    The condition that the snail reaches the end at time n is equivalent to [itex]a_n = 100000(n+1)[/itex], so by replacing in the previous equation:

    [itex]\sum_{k=1}^{n}\frac{χ_{k-1}}{k} = 10000[/itex]

    So the question can be rephrased as: What is the probability that [itex]χ[/itex] becomes 1 as many times as necessary in order for the sum of the first n terms to be larger than or equal to 10000?

    We can get a lower bound from that, since the worst case happens when all the k first terms are -1 and the n - k remaining terms are 1. (The denominators get smaller, so if we manage to guarantee that this sum is larger than 10000, any other rearrangements containing at least n-k ones will also be larger than 10000). So, find the largest k such that [itex]H_n - H_k ≥ 10000[/itex]. Then any rearragement containing at least n-k times the occurence [itex]χ = 1[/itex] will be larger than 10000.

    This is a sequence of Bernoulli trials, basically. So this gives us a lower bound for the probability of reaching 10000 in n trials. A similar strategy can be used to get an upper bound.

    Then, the answer to the question is whether the limit as n approaches infinity of this probability tends to 0, 0 < l < 1 or to 1.
     
    Last edited: Nov 23, 2013
  10. Nov 23, 2013 #9
    As an estimate, [itex]H_n - H_k = ln(\frac{n}{k})[/itex] so getting [itex]n(1-e^{-10000})[/itex] times a 1 during the n days is sufficient to guarantee having reached the end.

    Similarly, we need at least [itex]e^{10000-γ}[/itex] ones (obtained from 7a) to have any chance of reaching the end.

    So the probability for n is bounded below by the probability of getting at least [itex]n(1-e^{-10000})[/itex] times a one during the n trials. It is bounded above by the probability of getting at least [itex]e^{10000-γ}[/itex] times a one during n trials.

    (Actually this is slightly wrong because I am not sure whether the estimate for [itex]H_n = ln(n)+γ[/itex] is an upper or lower bound or neither).

    EDIT: Oh, I realise the upper bound is useless, since we want to show that it tends to 1. The upper bound obviously tends to 1.
     
    Last edited: Nov 23, 2013
  11. Nov 24, 2013 #10

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That will certainly depend on n. For small n, it is wrong.
     
  12. Jan 26, 2014 #11
    Looking at Boorglar's work, the situation is equivalent to a drunkard's walk where the drunkard is getting tired, so the size of step n is 1/n. Will this walk hit 10,000 or not ? A casual survey of the literature of 'Harmonic random walks' indicates that a random walk with step size f(n) converges iff 1/(f(n))^2 has a finite sum, which is true in this case. Hence the probability of hitting 10,000 is less than 1, and it looks like it is very very small...
     
  13. Jan 26, 2014 #12

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That is true.
     
  14. Jan 26, 2014 #13
    The total variance after an infinite number of steps of this drunkard walk with decreasing step size 1/n is equal to the sum of 1/n^2 from 1 to infinity, or pi^2/6. Hence the probability of exceeding 10,000 must be like the probability of a standard normal variable exceeding 10,000/(pi^2/6). That is a very small number.
     
  15. Jan 27, 2014 #14

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    That's not a valid approximation - the drunkard/snail could reach 10000, and go backwards afterwards, converging to a value below 10000. And it is not a lower limit either, as I think the distribution is not a normal distribution.
     
  16. Jun 9, 2014 #15
    I do not believe the snail will reach the end in finite time, but it may reach the end in the limit, Assuming the extreme case, the snail always moves forward, at time 0, the snail moves 10cm to the right, and is at 10cm on a 1km band. The band then stretches, so the snail is now at 20cm on a 2km band. The snail moves 10cm again and is now at 30cm on a 2km band, but then the band stretches and the snail is at 45 cm on a 3km band.

    Let i be a given 'time'. What we have here is that the snail moves 10/i*100,000 of the bands length at time n, after which the band gets stretched by i+1/i, so Pos(n), the snails position at time n (more precisely, before time n+1: after movement and expansion) should be:
    (sorry i am putting the equation just a minute)
    Basically, we have a harmonic series here, which does diverge, but only at infinity, which means that the snail will reach the end with probability 1, but will never reach it at any finite observation.

    Once moving backwards is included, it takes on the properties of a 1-dimensional random walk, which, given infinite time, I believe reaches the end, but given finite time won't since even moving forward always doesn't.

    Pos(n) is the fraction of the band at which the snail sits, so once H_n is greater than 10,000, the snail will hit the end of the band, which is about e^10000 or a very big number. I am still not sure if it ever hits in finite time when there is positive probability for moving backwards.
     
  17. Jun 9, 2014 #16
    equations are as follows:
    n
    Pos(n)= ∑ [(i+1)/i][10/i*100,000]
    i=1
    n
    Pos(n)= [1/10,000] ∑ [(i+1)/i^2]
    i=1

    i am new here still don't know how to use symbols and make equations.
     
    Last edited: Jun 9, 2014
  18. Jun 9, 2014 #17
    if iam correct please reply.
    Thank you for giving such a good sum logical as well as which explores thinking.
     
  19. Jun 9, 2014 #18

    D H

    User Avatar
    Staff Emeritus
    Science Advisor

    With this deterministic behavior, the snail will reach the end of the rubber band in a finite time. This is the classical snail (or ant or worm) on a rubber band (or tape or rope) problem. With the numbers supplied in the original post, it will take about 8.8*104342 days for the snail to cross the rubber band. That is a ridiculously long but nonetheless finite time.
     
  20. Jun 11, 2014 #19

    Matterwave

    User Avatar
    Science Advisor
    Gold Member

    As the snail is immortal, and all possibilities should be eventually explored, at some point the snail should make a step to the right with enough consistency to reach the end. Should not the probability be 1 that he reaches the other side given that this task is possible to do with a deterministic snail? After all, for any length ##l<\infty## there is always some such integer ##n<\infty## (but very large) for which a snail moving exclusively to the right will reach the end. One just has to wait for the snail to only move exclusively to the right for a long enough period by chance. How long this might take would be unimaginably long of course, but it seems to me the probability should be 1...
     
  21. Jun 11, 2014 #20

    mfb

    User Avatar
    2016 Award

    Staff: Mentor

    @Murtuza Tip: This is the easier challenge 7a.

    @Matterwave: The number of steps needed increases every day. Without stretching, your argument would work.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Challenge 7b: A Snail's Pace
  1. A little challenge (Replies: 8)

  2. Challenging problems (Replies: 6)

  3. Master's Challenge (Replies: 15)

  4. A Euclidean Challenge (Replies: 10)

Loading...