Challenge 7b: A Snail's Pace

[Office_Shredder]

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)

 

[Mandelbroth]

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)

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:

 

[mfb]

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

 

[jackmell]

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)

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

 

[D H]

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.

 

[mfb]

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

No loop. A rubber strip, if you like.

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

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.

 

[Office_Shredder]

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)

 

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

 

[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 realize the upper bound is useless, since we want to show that it tends to 1. The upper bound obviously tends to 1.

 

[mfb]

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.

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

 

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

 

[mfb]

That is true.

 

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

 

[mfb]

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.

 

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

 

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

 

[Murtuza Tipu]

if iam correct please reply.
Thank you for giving such a good sum logical as well as which explores thinking.

 

[D H]

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.

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*10⁴³⁴² days for the snail to cross the rubber band. That is a ridiculously long but nonetheless finite time.

 

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

 

[mfb]

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

@Matterwave: The number of steps needed increases every day. Without stretching, your argument would work.

 

[.Scott]

Let me take a shot at this.
I will start by marking the rubber band every 10cm and will allow the band to run in both the positive and negative direction.
So at the start, the snail is at the zero mark, then moves to +/-1 (step 1), then to -1.5, -.5, +.5, +1.5 (step 2), then -11/6, -7/6, -5/6, -1/6, 1/6, 5/6, 7/6, 11/6 (step 3).

If I put the snail back to zero and start at step 3, I get:
-1/3, 1/3 (step 3), then -7/12, -1/12, +1/12, +7/12 (step 4)
which is better (in terms of spread) than simply repeating step 4 twice:
-1/4, 1/4 (step 4), then -1/2, 0, 0, 1/2 (step 4 again).

So, grouping things in 2^n sets (3-4, 5-8, 9-16, 17-32, etc)...

In general, I will get more spread from $1/(2^{(n-1)}+1), 1/..., 1/(2^n)$ than from $1/(2^n), ..., 1/(2^n)$, allowing me to set a lower bound on the spread.
So for each n>1, I will get a triangle-like spread of more than { -1/2, ..., 0(n times), ... 1/2 }.

Since we're allowed to apply an infinite number of the triangle-like commutations, there is no limit to how thin we can make the distribution, eventually spreading everything out beyond our bounds at the +/- 10,000 marks.

(probability = 1)

 

[mfb]

You don't get a triangle in those sets. Reaching extreme values gets less and less likely with more random steps per set.

 

[.Scott]

Not only are you right, but I believe that the "waist" of those triangles decreases logarithmically. So the sum will approach a limit and probability will be less than 1. I'll have to check that out when I have more time.

 

[Joffan]

I thought I'd look at a more tractable version to start with... so I put the snail in the middle of a 1m band, stretching 1m every day.

A monotonic snail reaches the end of the band in 83 days. A random-direction snail has only a $1.034 \times 10^{-25}$ chance of reaching a given end on the 83rd day. The probability improves for a little while as a few reverses are allowed and allowing an extra 1.5 days to overcome the reverse - derived as a lower bound of 1 day if the reverse is in the second half of the journey and two days if the reverse is in the first half. But then the necessary bias away from a 0.5 probability overcomes the reverses and the sum of the probability of ever reaching the either end is considerably less than $5 \times 10^{-11}$.

Using this idea that every reverse has to be overcome by at least 1.5 advances on average, we can bound the probability in the original problem generously by examining the probability distribution at the minimum number of days for a value of 0.4n when the mean is 0.5n and the variance is 0.25n. (Normal approximation to the binomial). For the 0.5m test problem above, this comes up with a ridiculous overestimate of 0.035, so that's fine.

Since the probability is going to be ridiculously tiny anyway, I'm going to allow some more wriggle room and make the calculation feasible by using Chebyshev instead of Normal limits for probabilities of being outside certain standard deviation limits.

So taking the monotonic journey time of $8.8 \times 10^{4342}$ days, we see that the required bias in forward/reverse journeys is approximately $4.2 \times 10^{2170}$ standard deviations away from the mean, and Chebyshev implies that the probability of such a deviation is no more than $5.7 \times 10^{-4342}$

 

[mfb]

No matter where the reverse day is, the snail will need more than one day to get to the same relative distance ("marker position on the band"). But then the band is longer and the snail does less progress. Reversing once can easily add billions of years to the total time.

Chebyshev is a good approach, however, if applied correctly.

 

[Joffan]

Hi mfb - yes, I'm well aware that the 1.5 days is a huge simplification, but I wanted any upper bound on probability I could reasonably support.

Technically, if a reverse day happens when the snail is close to the end, it may be that only one more day forward is required to reverse it enough that the finish line is still reached. Note that by the time we are that far in the future, the relative stretch local to the snail is miniscule.

 

[mfb]

Then I don't understand the calculation. The standard deviation after x=10^whatever days is certainly larger than the motion coming from the second day, which is x/20000. Therefore, we have to be at most 20000 standard deviations away from the mean to reach the target. And we have to be this far only once, not at a specific point in time, which increases the chance a bit.

 

[Joffan]

To get there in minimum time, we have to be a hell of a lot more standard deviations away from the mean. So that probability is correspondingly lower - vanishingly low even by the standards of later days.

But for the purposes of my simplified approximation, I am saying that forward:reverse ratio has to be at least than 1.5:1 and the date can be no earlier than the monotonic snail date. As you observe, some reverse dates have far higher requirements for balancing forward days, so the true "average ratio" is more than 1.5, but I'm ignoring that additional requirement for now. I am not trying to estimate the exact probability - just put an upper bound on it.

A 1.5:1 ratio implies that we are sitting at an apparent probability of 0.4 for reverse days (1.5:1 = 0.6:0.4) when the true given probability of choosing both forward and reverse is 0.5.

Now the hand-wavy bit... which is where I could probably use some thinking from someone else... my observation from the small-number case is that, taking this 0.4 probability on the monotonic snail date gives a probability that is more than the sum of the actual probabilities on all subsequent realistic dates. This is definitely the weakest link in my reasoning, so I'm kind-of relying on all the other conservative approximations to bail it out :-)

So looking at the chance of apparent 0.4 proportion of reverses on the monotonic date, I see how far that is away from the mean and use Chebyshev to get an (extremely high) upper bound on the probability of that. There's no chance, of course, that the snail actually gets to the finish line on that date with that proportion of reverses. It's a stand-in for the accumulation of later possibilities.

 

[mfb]

To get there in minimum time, we have to be a hell of a lot more standard deviations away from the mean. So that probability is correspondingly lower - vanishingly low even by the standards of later days.

Sure, but then we do not get an upper estimate, we get a lower one.

But for the purposes of my simplified approximation, I am saying that forward:reverse ratio has to be at least than 1.5:1 and the date can be no earlier than the monotonic snail date. As you observe, some reverse dates have far higher requirements for balancing forward days, so the true "average ratio" is more than 1.5

I don't think that argument works. Most days will be spent on a really really long band. The probability to reach the end will mainly come from paths with no step backwards for the first whatever days.

Concerning the difference between "is beyond the target at day X" and "will be beyond the target at some point":
* the first one is certainly a lower estimate for the second one.
* Now imagine we extend the line (but keep the stretching ratios) so we can keep moving afterwards: for every path that crossed the target and then moved back there is a symmetric path that crossed the target and is still beyond it. Therefore, twice the probability to be beyond the target at day X is an upper estimate for the probability to be beyond the target within the first X days.
As a factor of 2 is negligible compared to other numbers, it is sufficient to calculate the limit of "probability to be beyond the target at day X" for X->infinity to get an upper estimate.

Chebyshev gives a really weak limit of the order of 10000 standard deviations here (would have to check the numerical prefactor).

 

[Joffan]

Sure, but then we do not get an upper estimate, we get a lower one.

Right, which is why I'm not using that number. However as you say, that probability of a random snail being perfectly monotonic for that period does gives us a loose lower bound greater than zero:
$2^{-8.8 \times10^{4342}} = 10^{-2.65 \times 10^{4342}}$

What I was doing, wrongly I now think, was evaluating the probability of a "feasible" (but still highly unlikely) ratio of forward to reverse at that time, way before it was possible, in order to skip the summing to infinity.

I don't think I really understand your argument yet, but I haven't time to think about it right now.