Expected number of points on circle to form an acute angled triangle

2.3k Views Asked by At

This problem was asked to me in an interview.

We keep on adding points on a circle uniformly until there exist three points on the circle which form an acute angled triangle. What is the expected number of points on the circle when the process stops?

2

There are 2 best solutions below

0
On

You fail to have an acute triangle if all the points are within a semicircle. When adding a new point (assuming there is not yet an acute triangle), the chance that you will form an acute triangle is the fraction of the circle covered by the shortest arc containing the existing points. For three points, the chance is $\frac 14$, as the distance between the first two points is uniform from $0$ to $\pi$, so the chance the third point forms an acute triangle is uniform from $0$ to $\frac 12$. Depending on the job, this would seem like enough progress for an interview, but I would like to see a complete answer.

0
On

Well, let's consider the probability of any 3 points forming an acute triangle. First, due to the symmetry of a circle, the position of the first point is irrelevant. Then, the next point is somewhere in $[0,\pi]$ radians from the first point. Finally, a triangle in the circle is acute iff it contains the center of the circle, so the angle $\theta$ between the first two points, reflected over the origin, is the region the third point must occupy to form an acute triangle. Denoting $P(n)$ as the probability of forming an acute triangle after $n$ points, and $p(n)$ being the probability that the $n^{\mathrm{th}}$ point forms the first such triangle, $$p(3)=P(3)=\frac{\int_0^\pi \frac{\theta}{2\pi} \mathrm d\theta}{\pi}=\frac{\frac{1}{2}\theta^2|_0^\pi}{2\pi^2}=\frac{1}{4}$$

Now, the next point, if it doesn't form an equilateral triangle, can occupy $2\pi-\theta$ rad, $\pi$ of which would extend the maximum angle between points.

For generality, let's call $\theta_n$ the largest angular separation between any two points after $n$ points have been placed, given that no three points form an acute triangle. We can obtain a recurrence relation for $\overline{\theta_n}$, as placing a new point increases $\theta$ linearly when it is between $\theta$ and $\pi$ from one of the most extreme points. When it is between these points, $\theta$ increases by $0$. Thus, $\overline{\theta_n}=\theta_{n-1}+\frac{2\int_0^{\pi-\theta_{n-1}}x\mathrm dx+\int_0^{\theta_{n-1}}0\mathrm dx}{2\pi-\theta_{n-1}}=\theta_{n-1}+\frac{(\pi-\theta_{n-1})^2}{2\pi-\theta_{n-1}}$. The original average $\theta_2$ was $\pi/2$, so $\overline{\theta_3}=2\pi/3$, and so chances of forming an acute angle with the fourth point is $1/3$. By the fourth point, the chance of having formed an acute angled triangle is now $$ \frac{1}{4}+\frac{3}{4}\cdot\frac{1}{3}=\frac{1}{2} $$ So you can expect a $50/50$ chance of an acute triangle after 4 points.

Now let's compute expected value:

In fact, by substituting $\overline{\theta_n}$ for $\pi\left(1-\frac{1}{a_n}\right)$, we obtain $$\begin{align} \overline{\theta_n}&=\pi\left(1-\frac{1}{a_{n-1}}\right)+\frac{\left(\pi-\pi\left(1-\frac{1}{a_{n-1}}\right)\right)^2}{2\pi-\pi\left(1-\frac{1}{a_{n-1}}\right)} \\ &=\pi\left(1-\frac{1}{a_{n-1}}+\frac{1}{a_{n-1}(1+a_{n-1})}\right) \\ &=\pi\left(1-\frac{1}{a_{n-1}+1}\right) \end{align}$$

And therefore $a_n=a_{n-1}+1$. Since $a_2=2$, $\overline{\theta_n}=\frac{(n-1)\pi}{n}$:

$$\begin{align} P(n+2)&=\sum_{k=1}^n \left(\prod_{i=1}^k (1-p(i+1))\cdot\frac{p(k+1)}{1-p(k+1)}\right) \\ &=\sum_{k=1}^n \left(\left(\prod_{i=1}^k \left(1-\frac{i}{2(i+1)}\right)\right)\frac{k}{k+2} \right) \\ &=\sum_{k=1}^n 2^{-k} \left(\prod_{i=1}^k \frac{i+2}{i+1}\right) \frac{k}{k+2} \\ &=\sum_{k=1}^n \frac{k}{2^{k+1}} \\ &=1-\frac{n+2}{2^{n+1}} \end{align}$$

The product is $1-\frac{\overline{\theta_{i+1}}}{2\pi}$, or the probability of not getting an acute triangle for $k+2$ points, multiplied by $k/(k+2)$ so that the last term is the probability of getting an acute triangle rather than not. Telescoping series allows the simplification of the product. The sum can be proven by induction on $n$.

We then have that $P(n)=1-2^{1-n}\cdot n$. We can also determine the expected value of the number of points, $E(X)$:

$$E(X)=\sum_{n=3}^\infty n\cdot p(n)=\sum_{n=3}^\infty \frac{n(n-2)}{2^{n-1}}=\sum_{n=1}^\infty \frac{n(n-1)+3n}{2^{n+1}}$$ Since $\sum_{n=0}^\infty {n\choose r}2^{-n}=2$, $\sum_{n=0}^\infty n\cdot 2^{-n}=\sum_{n=0}^\infty \frac{1}{2}n(n-1)2^{-n}=2$. $$ \Rightarrow E(X)=\sum_{n=0}^\infty \left({n\choose 2}2^{-n}+\frac{3}{2}{n\choose 1}2^{-n} \right)=2+3=5$$