[k-man]

This is a new twist to the original puzzle posted by magician.

An ant is in the center of a circle (diameter 3m). He walks in a straight line in a random direction for 1m. He's getting tired, so his next move is again in the random direction, but only for 0.5m. Every subsequent move is 1/2 of the previous move in length and in a random direction. If the ant moved in the same direction twice he would escape the circle in just 2 moves (let's consider reaching the edge of the circle as escape). But, if any of his moves are in the opposite direction of the previous move he will never reach the edge. So, here is the question...

What's the probability of the ant escaping the circle?

[bonanova]

The ant travels a total distance of 2m.

Un upper limit for the probability can be found by constructing a circle of 1m radius centered 1m from the origin of the 1.5m circle.

The fraction of the circumference of the 2nd circle that lies outside the 1st circle gives the best case probability of escape

(all his steps, after the first, are aligned.)

[Guest]

This is a new twist to the original puzzle posted by magician.

An ant is in the center of a circle (diameter 3m). He walks in a straight line in a random direction for 1m. He's getting tired, so his next move is again in the random direction, but only for 0.5m. Every subsequent move is 1/2 of the previous move in length and in a random direction. If the ant moved in the same direction twice he would escape the circle in just 2 moves (let's consider reaching the edge of the circle as escape). But, if any of his moves are in the opposite direction of the previous move he will never reach the edge. So, here is the question...

What's the probability of the ant escaping the circle?

Zero--if he gets stepped on! LOL

[Guest]

Assuming that the ant turns after the first leg of its trip, after the second leg of the trip, its total distance from the origin must be greater than or equal to 1.25m. Otherwise, the ant will never make it out of the circle.

Using the law of cosines, we can determine that the angle formed between the first and second leg of its trip cannot be less than 108 degrees. If it were, then the distance from the origin to the ant's position would be less than 1.25m.

Thus, if the ant turns more than 72 degrees either left or right from its original heading, it will never get out. The probability that it will never get out is 144/360. The probability that it will get out would then be 1-144/360 or 216/360.

Edited April 29, 2011 by jpf

[Guest]

Assuming that the ant turns after the first leg of its trip, after the second leg of the trip, its total distance from the origin must be greater than or equal to 1.25m. Otherwise, the ant will never make it out of the circle.

Using the law of cosines, we can determine that the angle formed between the first and second leg of its trip cannot be less than 108 degrees. If it were, then the distance from the origin to the ant's position would be less than 1.25m.

Thus, if the ant turns more than 72 degrees either left or right from its original heading, it will never get out. The probability that it will never get out is 144/360. The probability that it will get out would then be 1-144/360 or 216/360.

Remember that it is still possible for the ant to never escape if the ant just headed towards the center after the 1.25 m is crossed. I'd say to use the law if cosines and an infinite series' pruduct to find the possiblility that the ant will get out. I might be completely off.

[Guest]

In order not to resurrect the old problem, I will give here my opinion about questions in both threads:

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

3. What is the average/expected amount of walks required for the ant to escape the circle?

First, let's consider the center of the circle of radius 1.5 as the origin of an algaebric geometry plane, where each point has a complex number real+j*imag associated.

At step 1, the ant:

- chooses a random angle a_1 (uniformly distributed in [-pi..pi])

- walks to position pos_1 = cos(a_1) + j*sin(a_1)

At step 2, the ant:

- chooses a random angle a_2 (uniformly distributed in [-pi..pi])

- walks to position pos_2 = pos_1 + cos(a_2) + j*sin(a_2)

...

At step k, the ant:

- chooses a random angle a_k (uniformly distributed in [-pi..pi])

- walks to position pos_k = pos_(k-1) + cos(a_k) + j*sin(a_k)

For now, we do not care whether the ant is inside the circle or not.

The position of the ant after k steps is:

pos_k = SUM(cos(a_i)) + j*SUM(sin(a_i))

Second, given a probability density function (pdfx) of a random variable x, the pdfy for a variable y = g(x) is:

pdfy = pdfx(g^-1) * | dx / dg^-1 |

For uniform variable x in the interval [-pi...pi] and y = g(x) = cos(x), the pdfy is something along the lines:

pdfy = 1/pi * 1/sqrt(1-y^2), for y in the interval [-1..1]

This is the pdf of the cosine of a random angle.

For the sine, a rather similar formula should be found.

Third, the pdf of a sum of independent random variables is the convolution of pdfs.

In other words, the pdf of SUM(cos(a_i)) is (pdfy'*'pdfy'*'...'*'pdfy)(y), where '*' here represents convolution.

A similar relation should be obtained for SUM(sin(a_i)). Lets call these pdf_sumcos and pdf_sumsin

Fourth, the pdf of the squared SUM(cos(a_i)) and the squared SUM(sin(a_i)), is computed as changes of variables (see step 2). Let's call the resulting pdfs: pdf_sumcos2 and pdf_sumsin2

Fifth, the pdf for the squared absolute value of the complex number pos_k is:

pdf_k = (pdf_sumcos2'*'pdf_sumsin2)(y).

I should mention that I do not see any particular reason why the computation described should be important, other than an exam.

For the purpose of a brain teaser, this pdf_k can be approximated by a sufficiently large number of experiments.

Finally, the answers to the questions above:

p_k = the probability that the ant is outside the circle after k steps (we do not care how many times the ant stepped outside and back inside)

p_k = INT(1.5,inf,pdf_k,dy) = integral from (1.5^2) to infinity of pdf_k(y) dy

pek = the probability of the ant escaping in exactly k steps

pmk = the probability of the ant escaping in k or less steps (maximum k steps, k included)

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

pe1 = 0; pek = p_k*PROD(1-p_i); , where i goes from 1 to k-1

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

pmk = SUM(pei), where i goes from 1 to k

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

E = SUM(i*pei), where i goes from 1 to infinity

Edited May 4, 2011 by Kornrade

[bonanova]

In order not to resurrect the old problem, I will give here my opinion about questions in both threads:

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

3. What is the average/expected amount of walks required for the ant to escape the circle?

First, let's consider the center of the circle of radius 1.5 as the origin of an algaebric geometry plane, where each point has a complex number real+j*imag associated.

At step 1, the ant:

- chooses a random angle a_1 (uniformly distributed in [-pi..pi])

- walks to position pos_1 = cos(a_1) + j*sin(a_1)

At step 2, the ant:

- chooses a random angle a_2 (uniformly distributed in [-pi..pi])

- walks to position pos_2 = pos_1 + cos(a_2) + j*sin(a_2)

...

At step k, the ant:

- chooses a random angle a_k (uniformly distributed in [-pi..pi])

- walks to position pos_k = pos_(k-1) + cos(a_k) + j*sin(a_k)

For now, we do not care whether the ant is inside the circle or not.

The position of the ant after k steps is:

pos_k = SUM(cos(a_i)) + j*SUM(sin(a_i))

Second, given a probability density function (pdfx) of a random variable x, the pdfy for a variable y = g(x) is:

pdfy = pdfx(g^-1) * | dx / dg^-1 |

For uniform variable x in the interval [-pi...pi] and y = g(x) = cos(x), the pdfy is something along the lines:

pdfy = 1/pi * 1/sqrt(1-y^2), for y in the interval [-1..1]

This is the pdf of the cosine of a random angle.

For the sine, a rather similar formula should be found.

Third, the pdf of a sum of independent random variables is the convolution of pdfs.

In other words, the pdf of SUM(cos(a_i)) is (pdfy'*'pdfy'*'...'*'pdfy)(y), where '*' here represents convolution.

A similar relation should be obtained for SUM(sin(a_i)). Lets call these pdf_sumcos and pdf_sumsin

Fourth, the pdf of the squared SUM(cos(a_i)) and the squared SUM(sin(a_i)), is computed as changes of variables (see step 2). Let's call the resulting pdfs: pdf_sumcos2 and pdf_sumsin2

Fifth, the pdf for the squared absolute value of the complex number pos_k is:

pdf_k = (pdf_sumcos2'*'pdf_sumsin2)(y).

I should mention that I do not see any particular reason why the computation described should be important, other than an exam.

For the purpose of a brain teaser, this pdf_k can be approximated by a sufficiently large number of experiments.

Finally, the answers to the questions above:

p_k = the probability that the ant is outside the circle after k steps (we do not care how many times the ant stepped outside and back inside)

p_k = INT(1.5,inf,pdf_k,dy) = integral from (1.5^2) to infinity of pdf_k(y) dy

pek = the probability of the ant escaping in exactly k steps

pmk = the probability of the ant escaping in k or less steps (maximum k steps, k included)

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

pe1 = 0; pek = p_k*PROD(1-p_i); , where i goes from 1 to k-1

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

pmk = SUM(pei), where i goes from 1 to k

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

E = SUM(i*pei), where i goes from 1 to infinity

reduced each step b y 1/2?

[Guest]

reduced each step b y 1/2?

Sorry, I do not understand the question...

[k-man]

In order not to resurrect the old problem, I will give here my opinion about questions in both threads:

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

3. What is the average/expected amount of walks required for the ant to escape the circle?

First, let's consider the center of the circle of radius 1.5 as the origin of an algaebric geometry plane, where each point has a complex number real+j*imag associated.

At step 1, the ant:

- chooses a random angle a_1 (uniformly distributed in [-pi..pi])

- walks to position pos_1 = cos(a_1) + j*sin(a_1)

At step 2, the ant:

- chooses a random angle a_2 (uniformly distributed in [-pi..pi])

- walks to position pos_2 = pos_1 + cos(a_2) + j*sin(a_2)

...

At step k, the ant:

- chooses a random angle a_k (uniformly distributed in [-pi..pi])

- walks to position pos_k = pos_(k-1) + cos(a_k) + j*sin(a_k)

For now, we do not care whether the ant is inside the circle or not.

The position of the ant after k steps is:

pos_k = SUM(cos(a_i)) + j*SUM(sin(a_i))

Second, given a probability density function (pdfx) of a random variable x, the pdfy for a variable y = g(x) is:

pdfy = pdfx(g^-1) * | dx / dg^-1 |

For uniform variable x in the interval [-pi...pi] and y = g(x) = cos(x), the pdfy is something along the lines:

pdfy = 1/pi * 1/sqrt(1-y^2), for y in the interval [-1..1]

This is the pdf of the cosine of a random angle.

For the sine, a rather similar formula should be found.

Third, the pdf of a sum of independent random variables is the convolution of pdfs.

In other words, the pdf of SUM(cos(a_i)) is (pdfy'*'pdfy'*'...'*'pdfy)(y), where '*' here represents convolution.

A similar relation should be obtained for SUM(sin(a_i)). Lets call these pdf_sumcos and pdf_sumsin

Fourth, the pdf of the squared SUM(cos(a_i)) and the squared SUM(sin(a_i)), is computed as changes of variables (see step 2). Let's call the resulting pdfs: pdf_sumcos2 and pdf_sumsin2

Fifth, the pdf for the squared absolute value of the complex number pos_k is:

pdf_k = (pdf_sumcos2'*'pdf_sumsin2)(y).

I should mention that I do not see any particular reason why the computation described should be important, other than an exam.

For the purpose of a brain teaser, this pdf_k can be approximated by a sufficiently large number of experiments.

Finally, the answers to the questions above:

p_k = the probability that the ant is outside the circle after k steps (we do not care how many times the ant stepped outside and back inside)

p_k = INT(1.5,inf,pdf_k,dy) = integral from (1.5^2) to infinity of pdf_k(y) dy

pek = the probability of the ant escaping in exactly k steps

pmk = the probability of the ant escaping in k or less steps (maximum k steps, k included)

1. What's the probability of the ant escaping the circle [ in exactly k steps ]?

pe1 = 0; pek = p_k*PROD(1-p_i); , where i goes from 1 to k-1

2. What's the probability of the ant escaping the circle [ in k or less steps ]?

pmk = SUM(pei), where i goes from 1 to k

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

E = SUM(i*pei), where i goes from 1 to infinity

That's an interesting approach with the complex numbers, but it's more applicable to the original problem as it doesn't take into account that every step is 1/2 the distance of the previous step.

BTW, I still haven't solved this problem myself, so any new thoughts and ideas are welcome. I did create a simulation of the problem and after 100 million tries the result is that the probability of the ant escaping is

about 20.45%

I also plotted the probability distribution for the final location of the ant and interestingly the mean is at around 1.25m from the center of the circle with a local minimum at 1m and another small peak at .85m. Here is the chart that shows the probability of an ant being at a particular distance from the center after 8 steps.

[Guest]

Yes. when taking into account that every step is halved, the probability seems to be a little over 20%...

There are some mistakes in my method...

The formula for the probability of the ant escaping the circle [ in exactly k steps ] is wrong.

The random variables sumcos2 and sumsin2 are not exactly independent.