# Challenge 7b: A Snail's Pace

1. Nov 17, 2013

### Office_Shredder

Staff Emeritus
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. Nov 22, 2013

### Mandelbroth

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:

3. Nov 23, 2013

### Staff: Mentor

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

4. Nov 23, 2013

### jackmell

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

5. Nov 23, 2013

### D H

Staff Emeritus
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.

6. Nov 23, 2013

### 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.

7. Nov 23, 2013

### Office_Shredder

Staff Emeritus
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)

8. Nov 23, 2013

### Boorglar

I think I'm onto something.

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

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

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

$\sum_{k=1}^{n}\frac{χ_{k-1}}{k} = 10000$

So the question can be rephrased as: What is the probability that $χ$ 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 $H_n - H_k ≥ 10000$. Then any rearragement containing at least n-k times the occurence $χ = 1$ 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
9. Nov 23, 2013

### Boorglar

As an estimate, $H_n - H_k = ln(\frac{n}{k})$ so getting $n(1-e^{-10000})$ times a 1 during the n days is sufficient to guarantee having reached the end.

Similarly, we need at least $e^{10000-γ}$ 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 $n(1-e^{-10000})$ times a one during the n trials. It is bounded above by the probability of getting at least $e^{10000-γ}$ times a one during n trials.

(Actually this is slightly wrong because I am not sure whether the estimate for $H_n = ln(n)+γ$ 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
10. Nov 24, 2013

### Staff: Mentor

That will certainly depend on n. For small n, it is wrong.

11. Jan 26, 2014

### davidmoore63@y

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

12. Jan 26, 2014

### Staff: Mentor

That is true.

13. Jan 26, 2014

### davidmoore63@y

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.

14. Jan 27, 2014

### 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.

15. Jun 9, 2014

### Murtuza Tipu

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.

16. Jun 9, 2014

### Murtuza Tipu

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
17. Jun 9, 2014

### Murtuza Tipu

Thank you for giving such a good sum logical as well as which explores thinking.

18. Jun 9, 2014

### D H

Staff Emeritus
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.

19. Jun 11, 2014

### Matterwave

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

20. Jun 11, 2014

### 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.