4

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

Murtuza Vadharia
  • 1,616
  • 1
    When the snail is at the end of the rubber (at the beginning, for example), then he goes in the "forward" direction with 100%? – Peter Franek Jun 08 '14 at 13:35
  • @Tom think I'm onto something.

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

     – Murtuza Vadharia Jun 08 '14 at 14:09
  • i have not tried further becoz it was very hard to think when I was thinking about the solution at that time. – Murtuza Vadharia Jun 08 '14 at 14:10

2 Answers2

1

With the doubling interpretation, as you have written it, the snail can never reach the end:

Fix the end at $1$, start at $0$

$$X_0=0$$

$$\mbox{suppose} \ \forall n \ X_n=X_{n-1}+2^{1-n} 10^{-5} $$

This is a probability $0$ case, but moving forwards every time is clearly the best case for reaching the end anyway. In this case:

$$\lim_{n \rightarrow \infty}X_n=\frac{2}{10^5}\sum_{n=1}^{\infty} 2^{-n} = \frac{2}{10^5} \ll 1$$

John Fernley
  • 1,218
-1

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 $\frac{10}{i\cdot 100,000}$ of the bands length at time $n$, after which the band gets stretched by $\frac{i+1}{i}$, so $\textrm{Pos}(n)$, the snails position at time $n$ (more precisely, before time $n+1$: after movement and expansion) should be: $$ \begin{align} \textrm{Pos}(n) &= \sum_{i=1}^n \frac{i+1}{i}\frac{10}{i\cdot 100,000}\\ \textrm{Pos}(n) &= \frac{1}{10,000}\sum_{i=1}^n \frac{i+1}{i^2} \end{align} $$ 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.

Edit Ross is correct, $\textrm{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.

Avraham
  • 3,237
  • 2
    The snail will reach the end in finite time if it always goes forward. You are correct that you have a harmonic series. The sum is essentially $H_n$, the $n^{\text{th}}$ Harmonic number. You need $\ln n \gt 10000$, so $n \gt \exp(10,000)$, which is huge but finite. – Ross Millikan Jun 08 '14 at 14:38
  • Thank you for the correction. – Avraham Jun 08 '14 at 14:48
  • I don't understand this answer. "which, given infinite time, I believe reaches the end" -- I don't believe that the probability would be 1. The "intuitive" counter-argument is that, in a random walk, the average distance from the origin after $n$ steps is something like $\sqrt{n}$, which increases by $\simeq 1/\sqrt{n}$ at each step, and, given the stretching of the rubber, this rate is not enough to reach the end ($\sum \frac{1}{n^{3/2}}$ already converges). So, I would guess that the answer is a number between 0 and 1, but the problem is too hard for me. – Peter Franek Jun 08 '14 at 21:33
  • Sorry, was out of town. Given infinite time, anything with positive probability will be seen, including the end. – Avraham Jun 12 '14 at 03:07
  • @Avraham Not necessarily, if the probability of reaching the end tends to $0$ sufficiently fast – John Fernley Jun 22 '14 at 02:29