[Guest]

An ant stands in the middle of a circle (3 meters in diameter) and walks in a straight line at a random angle from 0 to 360 degrees. Problem is, it can only walk one meter before it needs a break. To make things even more exasperating, the ant has the memory of a fish and forgets what direction it has just walked in. After the break, it gets all dizzy and thus chooses another random direction from 0 to 360 in an attempt to escape the circle again.

As you can well imagine, it could escape the circle after just 2 walks (just one break needed). Or... it could take 20,000 walks (19,999 breaks needed)!! There might even be the very slim possibility it might take 20,000^20,000 walks. You can probably guess what I'm going to ask...

What is the average amount of walks required for the ant to escape the circle?

[superprismatic]

1. Without loss of generality, we can rotate the ant's

first move so that it points straight up. From then

on, we form a triangle using one side from the

origin to the ant's position and, given the new

angle, we can compute the side from the origin to

the ant's new position. Then we can rotate this so

that it points straight up. We do this over and over

until the length of the new side is larger than 1.5,

the radius of the circle. Also, by doing it this way

we can see that the angle can be chosen randomly

between 0° and 180°, without any loss of generality.

2. I simulated this for a billion iterations and I

got 3.52944622 as the average number of walks.

3. I have no idea how to compute this analytically.

[superprismatic]

5993/1698?

[Guest]

The ant walks 1m for its first journey. Then it can walk in an infinite number of directions for it's second. However as we only need to consider one side, both sides being a mirror image, we can see on average its trek will be at a right angle to its first journey, this creates a right angle triangle base 1.414m in length. When this is repeated a second time for the ant's third journey it reaches 1.7m on average from the centre out of the circle. At least that's what I think!

[Guest]

Love the beauty and brutality of the puzzle, though! Pretty clearly the median would be 3: graphically, it appears that almost 50% would escape on 2, and a more than 50% of the remainder on 3. But I can't even imagine how to set up the math to solve for a mean. Great puzzle!

[Guest]

I used the same method superprismatic used and got stuck at about the same point. Then it occurred to me that the probability of the ant escaping on the next turn can easily be calculated by finding the angles that would allow it to escape immediately. However, I haven't yet figured out exactly how to apply that...

[Guest]

Well, since the ant can go an infinite number of walks the average should be counted

as EXPECTATION on the number of walks.

Mathematically speaking it is a SUM over all possible steps from 2 to infinity,

summing the #num of walks needed, multiplied by the probability that the ant breaks free in this #num of walks

Formula: E(X) = SUM(n) {n * p(n)},

where p(n) is the probability that the ant will break free in n walks.

We can measure the probability of exiting the great circle if current ant's position is at point (a, b)

(center of the great circle is at the origin (0,0))

Consider the great circle, and the circle of all possible locations

after the ant has completed the walk from point (a, b).

If these circles intersect they give us in the general case a curve on the

circle of all possible locations that is outside of the great circle.

If we measure its length in degrees and divide in 360 we get the probability

of exiting the great circle in the next step.

Equation of the great circle: X² + Y² = 1.5²

Equation of all possible locations at next walk (also a circle): (X-a)² + (Y- b)² = a² + b²

If we know a, b we can calculate the intersection points between the two circles.

We calculate the length of the line between the intersection points.

Knowing that the length of the radius of the circle of all possible locations is 1,

we have all the lengths of the triangle formed between (a, b) and the intersection

points. The lengths will give us the angle through the cosine law. and that's it!

But I only solved a smaller problem.

The ant in n walks can be practically anywhere inside the great circle..

So we need to find all possible locations of the ant after n walks...

[Guest]

We all agree that the first walk will take the ant 1m away from the center. That's where the probability starts.

distance = 2^n + 1, probability=1 / {2^(n+1) + 1}Thus, the expected value = sum((2^n+1)/(2^(n+1) + 1)) for n=0, 1, 2, ...The successive terms in this summation series quickly converges to 0.5. Which means there is always a probability of additional 0.5 meters. The average walks for 2 digits after decimal (for probability) is 20 walks.

Though I still feel it would be better if we start measuring angles.

[bonanova]

Here's an extension to the puzzle, where the answer needs no calculation, just reasoning:

What happens to the probability of eventual escape from the circle as the step size goes to zero?

That is, the distance traveled by the ant before his direction is randomized?

Why?

[Guest]

@bonanova

Are you assuming that the ant will reverse directions in successive steps?

[Guest]

Here's an extension to the puzzle, where the answer needs no calculation, just reasoning:

What happens to the probability of eventual escape from the circle as the step size goes to zero?

That is, the distance traveled by the ant before his direction is randomized?

Why?

The probability of eventual escape naturally is 1 regardless of step size because there is no limit on the number of steps.

[bonanova]

@bonanova

Are you assuming that the ant will reverse directions in successive steps?

No, that he will randomize his direction in successive steps.

[bonanova]

The probability of eventual escape naturally is 1 regardless of step size because there is no limit on the number of steps.

That reducing the step size to infinitessimal values for a constant size circle

is the same as keeping the step size equal to unity and increasing the size of the circle without bound.

Is the probability still 1, looking at it that way?

[HoustonHokie]

That reducing the step size to infinitessimal values for a constant size circle

is the same as keeping the step size equal to unity and increasing the size of the circle without bound.

Is the probability still 1, looking at it that way?

For bonanova's question (either form), the probability is 0. As either the distance walked by the ant approaches 0 or the circle size approaches infinity, the probability of escape approaches 0. It's just not gonna happen...

[Guest]

What is the answer to the primary question and the extensions that bonanova made?

[superprismatic]

The answer to Bonanova's question is 1. Here's why:

Take position of the ant in the circle after walk #1.

Suppose that it is distance D from the center.

Now there is a probability of ε/180 that the next

walk will be within ±ε° away from the direction

defined by a vector going from the center of the

circle to the position of the ant. Now, this means

that the the ant will move at least D-δ further away

from the center of the circle, for some small δ which

depends on ε. Note that ε can always be chosen so

that it makes δ very small compared to D. So, chose

N and ε so that D-N×δ exceeds the radius of the

circle. This will happen with probability (ε/180)^N.

This may be small, but it is non-zero, so eventually

it will come to pass and the ant will leave the

circle. No matter how small D is, such a finite N

can always be computed.

[Guest]

I think you are all missing a simple bit of information here.

Since the goal is the edge of a circle you can calculate the probability of reaching the edge by calculating the probability of reaching 3m from the centerpoint. x and y position do not matter in a circle just linear distance from the centerpoint.

After 10 moves the ant has over a 50% chance of already escaping.

After 9 the ant has less than 50% chance.

The exact mean is impossible to determine because you have a theoretical possibility of infinity.

How I found it

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

#define _USE_MATH_DEFINES

int main() {

    double Distance = 0;

    int Walks = 0;

    int Trials = 0;

    double Average = 0;

    float Angle;

    while (Trials <= 1000000) {

    srand ( Trials - Walks + Distance - time(NULL));

    Angle = (((rand() % 1000)) );

    Distance += cos (2 * Angle /1000 * M_PI);

    Walks = Walks + 1;

    if ((Distance > 3)||(Distance < -3)) {

    Average = (Trials * Average + Walks) / (Trials + 1);

    Trials = Trials + 1;

    std::cout << Average;

    std::cout <<"\n";

    Distance = 1;

    Walks = 1;

    };

    };

}

I know this is not the most efficient c++ code but it works for a rough estimate.

with sig figs it estimates 9.393 walks

[Guest]

While the principal behind my code is correct, the code itself has a fatal flaw and therefore answer is incorrect. Will fix code tomorrow (today after I get some sleep its 3:40 here)

[Guest]

After 4 moves the ant has over a 50% chance of already escaping.

After 3 the ant has less than 50% chance.

The exact mean is impossible to determine because you have a theoretical possibility of infinity.

How I found it

#include <iostream>

#include <stdio.h>

#include <stdlib.h>

#include <time.h>

#include <math.h>

#define _USE_MATH_DEFINES

int main() {

    double DistanceX = 0;

    double DistanceY = 0;

    int Walks = 0;

    int Trials = 0;

    double Average = 0;

    float Angle;

    while (Trials <= 1000000) {

    srand ( Trials - Walks + DistanceX - time(NULL));

    Angle = (((rand() % 1000)) );

    DistanceX += cos (2 * Angle /1000 * M_PI);

    DistanceY += sin (2 * Angle /1000 * M_PI);

    Walks = Walks + 1;

    if ((sqrt ((DistanceX * DistanceX) + (DistanceY * DistanceY))) >= 3) {

    Average = (Trials * Average + Walks) / (Trials + 1);

    Trials = Trials + 1;

    std::cout << Average;

    std::cout <<"\n";

    DistanceX = 0;

    DistanceY = 0;

    Walks = 0;

    };

    };

}

I know this is not the most efficient c++ code but it works for a rough estimate.

with sig figs it estimates 3.841 walks

[Guest]

Superprismatic, can you explain what δ is? I'm a little confused by your explanation.

The probability of leaving the circle approaches, but does not equal 1. Any curve you can possibly draw is a set of infinite steps of infinitely small size. So the ant could end up in any point in space, inside or out of the circle. So the probability that the ant exits the circle is (area outside of the circle)/(total area of space).

[superprismatic]

Superprismatic, can you explain what δ is? I'm a little confused by your explanation.

The probability of leaving the circle approaches, but does not equal 1. Any curve you can possibly draw is a set of infinite steps of infinitely small size. So the ant could end up in any point in space, inside or out of the circle. So the probability that the ant exits the circle is (area outside of the circle)/(total area of space).

Look at the situation when the walk is 1 unit and the

radius of the circle is 1.5 units.

Take the position of the ant in the circle after some

number of walks. Suppose it is distance D from the

center. Now there is a probability of ε/180 that

the next walk will be within ±ε° away from the direction

defined by a vector going from the center of the

circle to the position of the ant. Now, this means

that the the ant will move at least √(D²+1-2×D×Cos(180°-ε))

further away from the center of the circle (using the

law of cosines). Note that as ε gets closer to 0, this

number gets close to D+1. If we pick ε to be 90°, then

this number will always be greater than or equal to

√(D²+1). So, let's see what happens if

ε is picked to be 90° for four successive times (this

happens with probability (90/180)⁴=(1/2)⁴=1/16):

We start at distance D from the center, the first step

gets us to at least √(D²+1), the next step

gets us to at least √(D²+2), the third step

gets us to at least √(D²+3), and the fourth

gets us to at least √(D²+4) away from the

center, which is out of the circle regardless of what

D we started with. All we need is 4 steps in that range

([-90°,+90°]) for ε, and the ant is out of the circle

regardless of where the ant was before the 4 steps.

Similarly, if the circle were to have radius N, then

N² steps (like those above) would be required, and that

occurs whith probability (1/2)^N2.

In an infinite random walk, this would eventually happen.

[Guest]

I don't think that works

(1/2)^N2 goes to 0 as N goes to infinity.

A couple questions, because I get confused when dealing with infinity. I know that for the ant to travel between two points it will have taken infinite steps, since the path can be broken down into more steps without limit. However since the ant needs to keeps walking forever it could also be thought that its path shouldn't have an ending point, but should be infinitely long. How does amount of steps in a finite path compare to the amount of steps in an infinite path? Which type of infinity are we dealing with here?

[superprismatic]

I don't think that works

(1/2)^N2 goes to 0 as N goes to infinity.

A couple questions, because I get confused when dealing with infinity. I know that for the ant to travel between two points it will have taken infinite steps, since the path can be broken down into more steps without limit. However since the ant needs to keeps walking forever it could also be thought that its path shouldn't have an ending point, but should be infinitely long. How does amount of steps in a finite path compare to the amount of steps in an infinite path? Which type of infinity are we dealing with here?

No matter how big the circle is, the ant will eventually escape

because every path of every length will "eventually" be tried

including all those which escape it. So, the size of the circle

is basically irrelevant.

[EventHorizon]

I will simplify it to where the ant is moving on the number line.

I will change the movement per iteration to choosing uniformly from [-1,1] and adding that distance to the ant's current number.

Let d be the distance equivalent to the circle's edge, and since I am not choosing d it can go towards infinity (though it is always a finite number) and not change the result.

**********************

First, I'll introduce the operation called convolution. If you already know what it is, skip down to the other **********************.

Mathematically, convolution of function f(x) and g(x) (denoted (f*g)(x)) is the integral from negative infinity to positive infinity of f(z)g(x-z)dx.

This is useful because you can define a 'filter' (a function to be convolved with) to smooth, average, sharpen, etc.

For instance, if you wanted a function to average the values of a function one to the left of x up to one to the right of x, you'd convolve with a function that is 0 everywhere except has the value of 1/2 from -1 to 1.

Here's a couple resources, wikipedia and an applet that you can use to see how convolution works. For the applet (which I didn't write), you draw the functions (red and blue lines), then click on the line in the next area down and drag from left to right across the line (or right to left). It'll show you the function it is integrating, and then draw the value of the integral in the lowest section.

http://en.wikipedia.org/wiki/Convolution

http://www.jhu.edu/signals/convolve/

Convolution is commutative, associate, distributive, and has an identity function called the delta function (a value of infinity at one point (which integrates to 1) and zero elsewhere in the case of continuous functions, or a value of 1 at the point in the case of discrete functions).

So if I use * to multiply two functions... it's convolution, otherwise it is standard multiplication. Sorry for the confusion, but I didn't choose the symbols.

**********************

So... how does convolution even apply? glad you asked...

If you let f_t be the distribution of where the ant is at time t (delta function in the case of t=0), and then you use the transition I described before, the distribution of the possible new positions f_t+1 is f_t(x)*g(x) where g(x) is 0 everywhere except 1/2 from -1 to 1. Notice how g(x) encodes the transition function.

Why does this work? If you let f(x) for a given x be the probability that the ant is at x, the convolution will multiply the probability the ant is at a location with the probability that the ant will move to a given spot (for all spots!)... and the integral part of convolution will add up all possible ways to get to that same spot from other locations based on the probability the ant is in those locations as well.

If you repeatedly convolve a function with another function (or equivalently itself), the result approaches a Gaussian (a.k.a. a normal curve, though this assumes the original function is continuous (as opposed to one with embedded delta functions)). Convolving a Gaussian with a Gaussian results in a Gaussian with a standard deviation of the sqrt of the sum of the squares of the standard deviations of the original Gaussians (sorta like the Pythagorean theorem). Since the ant position starts as a delta function, we merely need to look at convolutions of the transition function g with itself ad infinitum.

Let n be the number of times to convolve g with itself until it is very close to a Gaussian, and let this function be G. Let its standard deviation at that time be s.

If you convolve G with itself, you get a function that is even closer to a Gaussian, but with a standard deviation of sqrt(s²+s²) = s*sqrt(2).

Convolving the result with G again results in a (at this point, i'm just going to call it a...) Gaussian with standard deviation of sqrt( (s*sqrt(2))²+s²) = s*sqrt(3).

So after repeating this m times (equivalent to convolving the original function (n*m) times), the standard deviation is s*sqrt(m).

Notice that we can get the standard deviation of the Gaussian to be greater than any value we want. For instance, if we want the standard deviation to be greater than 4000, it will take (4000/s)² * n iterations of the ant moving.

What this means is that we can get the probability the ant is within distance d to be smaller than any value we want by increasing the standard deviation of the Gaussian to be large enough.

So as n (defined as the number of times the ant moves) goes to infinity, the probability the ant is still within distance d of where he was initially decreases to 0.

Note that this allows the ant to go back in after leaving the circle, whereas in the problem it cannot (which complicates it greatly). This means the probability calculated this way is greater than the actual probability that the ant is still in the circle.

Note also that this simplification has a 50% chance of moving closer after 1 round, and the original problem has a greater than 50% chance since moving at a right angle from the direction towards the center still increases the distance a little. Though it does approach 50% as the distance from the initial position increases.

To prove bonanova's original question you can simply change the transition function to be a circle of distance 1 around the origin (discretizable to any fidelity and normalized to a valid probability distribution mass function). You will still get a Gaussian (2d this time), and the result is essentially the same.

I don't think I've explained this perfectly, but the idea is sound (but if you disagree, feel free to voice your concern and I'll try to clarify).

-=-=-=Answer=-=-=-

In other words, I agree with superprismatic that the probability the ant eventually leaves the circle is 1 regardless of the size of the circle (equivalently the step size). So letting it approach infinity (or 0 in the case of step size) doesn't change anything since it will never **equal** infinity (or 0 for step size).

-=-=-=-=-=-=-=-=-

I've thought a bit about the original problem (even found online the place where it was likely taken from) worked up some integrals that got ugly. I think I know how I'd approach it next, but I think it may take more time than I'm willing to spend on it at the moment. I'll put it in my queue though (it's an interesting problem after all).

[bonanova]

I will simplify it to where the ant is moving on the number line.

I will change the movement per iteration to choosing uniformly from [-1,1] and adding that distance to the ant's current number.

Let d be the distance equivalent to the circle's edge, and since I am not choosing d it can go towards infinity (though it is always a finite number) and not change the result.

**********************

First, I'll introduce the operation called convolution. If you already know what it is, skip down to the other **********************.

Mathematically, convolution of function f(x) and g(x) (denoted (f*g)(x)) is the integral from negative infinity to positive infinity of f(z)g(x-z)dx.

This is useful because you can define a 'filter' (a function to be convolved with) to smooth, average, sharpen, etc.

For instance, if you wanted a function to average the values of a function one to the left of x up to one to the right of x, you'd convolve with a function that is 0 everywhere except has the value of 1/2 from -1 to 1.

Here's a couple resources, wikipedia and an applet that you can use to see how convolution works. For the applet (which I didn't write), you draw the functions (red and blue lines), then click on the line in the next area down and drag from left to right across the line (or right to left). It'll show you the function it is integrating, and then draw the value of the integral in the lowest section.

http://en.wikipedia....iki/Convolution

http://www.jhu.edu/signals/convolve/

Convolution is commutative, associate, distributive, and has an identity function called the delta function (a value of infinity at one point (which integrates to 1) and zero elsewhere in the case of continuous functions, or a value of 1 at the point in the case of discrete functions).

So if I use * to multiply two functions... it's convolution, otherwise it is standard multiplication. Sorry for the confusion, but I didn't choose the symbols.

**********************

So... how does convolution even apply? glad you asked...

If you let f_t be the distribution of where the ant is at time t (delta function in the case of t=0), and then you use the transition I described before, the distribution of the possible new positions f_t+1 is f_t(x)*g(x) where g(x) is 0 everywhere except 1/2 from -1 to 1. Notice how g(x) encodes the transition function.

Why does this work? If you let f(x) for a given x be the probability that the ant is at x, the convolution will multiply the probability the ant is at a location with the probability that the ant will move to a given spot (for all spots!)... and the integral part of convolution will add up all possible ways to get to that same spot from other locations based on the probability the ant is in those locations as well.

If you repeatedly convolve a function with another function (or equivalently itself), the result approaches a Gaussian (a.k.a. a normal curve, though this assumes the original function is continuous (as opposed to one with embedded delta functions)). Convolving a Gaussian with a Gaussian results in a Gaussian with a standard deviation of the sqrt of the sum of the squares of the standard deviations of the original Gaussians (sorta like the Pythagorean theorem). Since the ant position starts as a delta function, we merely need to look at convolutions of the transition function g with itself ad infinitum.

Let n be the number of times to convolve g with itself until it is very close to a Gaussian, and let this function be G. Let its standard deviation at that time be s.

If you convolve G with itself, you get a function that is even closer to a Gaussian, but with a standard deviation of sqrt(s²+s²) = s*sqrt(2).

Convolving the result with G again results in a (at this point, i'm just going to call it a...) Gaussian with standard deviation of sqrt( (s*sqrt(2))²+s²) = s*sqrt(3).

So after repeating this m times (equivalent to convolving the original function (n*m) times), the standard deviation is s*sqrt(m).

Notice that we can get the standard deviation of the Gaussian to be greater than any value we want. For instance, if we want the standard deviation to be greater than 4000, it will take (4000/s)² * n iterations of the ant moving.

What this means is that we can get the probability the ant is within distance d to be smaller than any value we want by increasing the standard deviation of the Gaussian to be large enough.

So as n (defined as the number of times the ant moves) goes to infinity, the probability the ant is still within distance d of where he was initially decreases to 0.

Note that this allows the ant to go back in after leaving the circle, whereas in the problem it cannot (which complicates it greatly). This means the probability calculated this way is greater than the actual probability that the ant is still in the circle.

Note also that this simplification has a 50% chance of moving closer after 1 round, and the original problem has a greater than 50% chance since moving at a right angle from the direction towards the center still increases the distance a little. Though it does approach 50% as the distance from the initial position increases.

To prove bonanova's original question you can simply change the transition function to be a circle of distance 1 around the origin (discretizable to any fidelity and normalized to a valid probability distribution mass function). You will still get a Gaussian (2d this time), and the result is essentially the same.

I don't think I've explained this perfectly, but the idea is sound (but if you disagree, feel free to voice your concern and I'll try to clarify).

-=-=-=Answer=-=-=-

In other words, I agree with superprismatic that the probability the ant eventually leaves the circle is 1 regardless of the size of the circle (equivalently the step size). So letting it approach infinity (or 0 in the case of step size) doesn't change anything since it will never **equal** infinity (or 0 for step size).

-=-=-=-=-=-=-=-=-

There are two answers, actually.

The question is:

What happens to the probability of eventual escape

from the circle as the step size goes to zero?

Let p be the escape probability and x be the step length.

Small values of x are just the original problem with a proportionately larger circle.

Then p(x) = 1 for all nonzero x.

Thus the limit of p(x) as x ->0 is 1.

The ant escapes.

However, when the step size reaches zero, the ant doesn't move!

So the value of p(0) = 0.

The frozen ant stays at the origin forever.