# Ant in a circle

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.

-
en.wikipedia.org/wiki/Brownian_motion take a look at Smoluchowski model – Norbert Apr 19 '12 at 11:08
Have you considered Monte Carlo simulation? I think that this problem would be ideally suited to such analysis. – Tpofofn Apr 19 '12 at 12:28
@Norbert, interesting link. Thank you for sharing. – Neil Apr 19 '12 at 13:31
@Tpofofn, I'm not familiar with it. What does a Monte Carlo simulation do? – Neil Apr 19 '12 at 13:31
@Neil, a Monte Carlo Simulation is a brute force approach in which you simulate the ant some large 'N' number of time and count up the number of legs it takes him to leave the circle each time. See this link: en.wikipedia.org/wiki/Monte_Carlo_method – Tpofofn Apr 19 '12 at 15:27

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:

-
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. – bgins Apr 19 '12 at 12:40

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<r\,|\,r-1< R_{n-1}< r+1] \\&= F_{n-1}(r-1)+ \int_{r-1}^{r+1} f_{n-1}(s)\cdot \mathbb{P}[R_n<r|R_{n-1}=s] \,ds } The latter integral can certainly be split into the two cases $s<r$ 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<r|R_{n-1}=s]&= \left\{ \begin{align} 1-\frac{\beta -r^2 \alpha}{2\pi} && s \le r\\ \frac{A_\gamma+r^2A_\alpha}{2\pi} && s \gt r\\ \end{align} \right. } 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.

-
I'm having a hard time wrapping my head around that. What is E[T]? Time it takes for the ant to leave a circle of radius T? – Neil Apr 19 '12 at 10:47
$\mathbb{E}[T]$ is the expected value of the time of first passage outside the circle of radius $R$. – bgins Apr 19 '12 at 12:36

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

-

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<N ; i++)
{
int c = 0 ; // Count number of legs
double d=0 ; // distance from center ;
double xt=0.0, yt=0.0 ; // Total x,y distance from 0

while (d <= R)
{
double ang = 2*PI*rGen.nextDouble() ;
xt += cos(ang) ;
yt += sin(ang) ;
d = sqrt(xt*xt + yt*yt) ;
c++ ;
}
countArr[c]++ ;
}
for (int i=0 ; i<L ; i++)
System.out.println(i + ", " + countArr[i]/(double)N) ;
}
}


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

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

-

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.

-
Hmm, I think that's an accurate representation of the problem, but how can you determine when the absolute value of the sum of a random number between -1 and 1 will exceed 3? – Neil Apr 19 '12 at 10:23
The sum of a set of identical random variables is just the convolution. So you could calculate the chances for each $n$ and then sum over that. – nbubis Apr 19 '12 at 10:28
so what would that be? $\sum_n{sin(\pi) - sin(0)}$? That's 0, so the $\sum_n{0}$ is never going to be 3 or greater. Maybe I don't yet see it. – Neil Apr 19 '12 at 10:35
No. you would first need to write the the distribution given by $\cos(\theta)$, say $f(x), x \in [-1,1]$. Once you have that you can calculate the convolution of this distribution $n$ times to obtain a series of distributions $f_n$. Finally, your answer is: $$\sum{nP(f_n>3)}$$ – nbubis Apr 19 '12 at 10:53
Or rather, a semi-infinite plane bounded by the line $x=3$. – TonyK Apr 19 '12 at 11:40