16
$\begingroup$

An ant is sitting in the middle of a circle of radius 3 meters. Every minute, the ant picks a random direction and moves straight 1 meter.

On average, how long does it take the ant to leave the circle? If it helps calculations, you can disregard the fact that the ant may technically leave prior to the end of the minute, in other words, if the ant is 0.5 meters from the edge of the circle and walks outwards, consider it a minute, not 30 seconds.

I'm normally quite good at these types of problems, but this one seems more statistical in nature and I'm not sure how to approach it. Obviously the ant could stay in the circle forever wandering around, but it's statistically impossible, meaning the average amount of time the ant spends in the circle is a limit which converges (answer is not "infinite time").

I'd love to hear any techniques on solving this problem.

  • 0
    Not an answer, but I made a GeoGebra simulation that could help students visualize what's going on, or collect a limited amount of data. [http://www.geogebratube.org/material/show/id/8479](http://www.geogebratube.org/material/show/id/8479)2012-04-25

5 Answers 5

11

Calling $\mathbb{E}(d)$ the expected time for leaving the circle if you are at distance $d$, $\mathbb{E}(d)$ should have the following property: $\mathbb{E}(d)=1+\frac{1}{2\pi}\int_0^{2\pi}\mathbb{E}(\sqrt{d^2+1-2d\cos\alpha})d\alpha$ with the constraint $\mathbb{E}(d)=0$ if $d>3$.

This formula say that the expected leaving time is 1 (the cost of doing another step) + the mean of the expected time over each point at distance 1 from the current point ($\sqrt{d^2+1-2d\cos\alpha}$ is the cosine law applied at the triangle between the origin, the current point and next point).

I don't know how to explicit solve this equation (nor if is feasible to be done), but it can be used for iteratively approximate the solution.

edit: I've tried to solve with R, seem that the solution is $\mathbb{E}(0)\simeq11.42$, and this is the plot of the approximation of the function: enter image description here

  • 0
    Very nice work! Your $\alpha$ is my $\gamma$, and I give geometric formulas to solve the integral if you care to look at my post and cannibalize it for yours.2012-04-19
2

The ant's position at each time $n\in\mathbb{N}$ is a random variable which we could model in the complex plane as $Z_0=0$, $Z_n=Z_{n-1}+\Delta Z_n=\sum_{k-1}^n\Delta Z_k$ for moves $\Delta Z_n=e^{i\Theta_n}$ which are i.i.d. and which depend on uniform i.i.d. random variates $\Theta_n=2\pi\,U_n\sim\operatorname{Unif}\left(0,2\pi\right)$ . If we also let $ R_n=|Z_n|\,, \qquad S_n=\sup\limits_{1\le k\le n}R_n \qquad \text{and} \qquad T=\inf\left\{n\mid R_n>R\right\} $ be the first time $n$ for which $R_n>R=3$, then we are asking for $\mathbb{E}[T]$, which can be calculated as \mathbb{E}[T]=\sum_{n=R}^{\infty}n\cdot\mathbb{P}[R_{n-1} < R < R_n]\,. Now if we let F_n(r)=\mathbb{P}[R_n < r] and let $f_n(r)=\mathbb{P}[R_n = r]$ be the PDF and CDF of $R_n$, we can see that $F_n(n)=1$, and we may be able to determine these functions inductively, with a recursion: \eqalign{ F_n(r)&= \mathbb{P}[R_n < r]\\&= \mathbb{P}[R_{n-1} < r-1]+ \mathbb{P}[R_n The latter integral can certainly be split into the two cases s and $s>r$, for which the indeterminate probability inside the integrand can be evaluated using geometry by subtracting the area of sectors of circles (and triangles for $s>r$):

\eqalign{ \mathbb{P}[R_n where the angles $\alpha,\beta,\gamma$ can be expressed using the law of cosines: $ \eqalign{ \cos\alpha &=\frac{r^2+s^2-1}{2rs}\\ \cos\beta &=\frac{r^2-s^2-1}{2 s} \qquad\text{or}\qquad\sin\beta=r\,\sin\alpha\\ \cos\gamma &=\frac{-r^2+s^2+1}{2 s}=-\cos\beta\\ } $ (or solved from the equations $re^{i\alpha}=s+e^{i\beta}$ & $\beta+\gamma=\pi$, from which one can infer the diagrams for each case) and $A_\alpha=2\alpha-\sin2\alpha$ is twice the area of \{z\in\mathbb{C}:\,|z|>r,\,|z-s|<1\}.

Well, that's a start. There is surely a more elegant recursion; perhaps @carlop has found it.

  • 0
    $\mathbb{E}[T]$ is the [expected value](http://en.wikipedia.org/wiki/Expected_value) of the time of first passage outside the circle of radius $R$.2012-04-19
2

Just for fun and simplicity, here's the results if the ant were constrained to 1 dimension (can only move left or right). Also note that I considered the ant out when he reaches 3 from the center:

1E:  1 from edge   Move Out: Exit and stop considering ant   Move In: Goto 2E 2E:  2 from edge   Move Out: Goto 1E   Move In: Goto C C:  Center   Move Right or Left: Goto 2E  After Move 1: 1:1 at 2E After Move 2: 1:2 at 1E, 1:2 at C After Move 3: 1:4 out, 3:4 at 2E After Move 4: 1:4 out, 3:8 at 1E, 3:8 at C After Move 5: 7:16 out, 9:16 at 2E 

Chance of being at 2E after (1 + 2*n) moves: $(3/4)^n$ Chance of being out at (1 + 2*n) moves: $1 - (3/4)^n$ Chance of an ant getting out on the (1 + 2*n)th move: $(1 - (3/4)^n) - (1 - (3/4)^{n-1}) = (3/4)^{n-1}-(3/4)^n$

Thus, the average time it takes an ant to get out is: $\sum_{n=1}^{\infty}{(1 + 2n)*((3/4)^{n-1}-(3/4)^n)}$

Whose final value turns out to be 9, which will clearly be lower than the average time for the 2-dimensional problem.

It would also be interesting to consider a fly in a sphere with similar constraints :)

2

I developed code using Monte Carlo Method as show below. I used Java because that is what I had available, but it could be translated to Matlab or other code:

import java.util.Random; import static java.lang.Math.* ;  public class RandomWalk { static int N = 100000 ; // Number of iterations static double R = 3.0 ; // Radius of circle static int L = 200 ;  public static void main(String[] args) {     int countArr[] = new int[L] ;     for (int ci : countArr) countArr[ci]=0 ;     Random rGen = new Random();        rGen.setSeed(856) ;      for (int i=0 ; i

The PDF of the ant leaving the circle on leg $i$ looks like this:

PDF of ant leaving the circle on leg i

Note that the plot has modes at $i=4$ and $i=6$. The expected value is 11.4.

1

I think one way to solve this would be to consider the direction in which the ant ends up leaving. We can now look at this as a one-dimensional problem, namely, when is: $\sum_n{cos(\theta_n)}>3$ Where $\theta$ is distributed uniformly.

  • 0
    I think this approach is a dead end.2012-04-19