Expected number of regions with $n$ random lines in a circle

Question

There are $n$ random lines drawn in a circle, defined by endpoints being uniform on circle. I am trying to figure out the expected number of regions separated by $n$ lines. I know $f(0)=1$, $f(1)=2$ and $f(2)=\frac{10}{3}$. Though naive, I can work it out through enumeration. But when $n$ is large, is there a formula to do this?

Answer 1

Euler's formula states that, for any planar graph, $f - e + v = 2$, where $f$ is the number of faces (what you call regions, with an important caveat to be discussed at the end of this post), $e$ is the number of edges, and $v$ is the number of vertices.

Each line necessarily intersects the circle at exactly $2$ distinct points (the case of a tangent line happens with probability $0$, and the case of no intersections is not relevant). If, in addition, there are $P$ points of intersection, then $v = 2L + P$, where $L$ is the number of lines.

It happens with probability $0$ that any point $P$ lies at the intersection of more than $2$ lines or that any vertex on the edge of the circle is at the intersection of more than $1$ line with the circumference. Thus, there are exactly $4$ edges meeting at each of the $P$ intersection points and exactly $3$ edges ($2$ circular arcs and $1$ edge corresponding to a line) meeting at each of the $2L$ circumference points. Thus, we might guess $e = 3(2L) + 4(P)$. But this actually double counts, since each edge is connected to exactly $2$ different vertices. Thus, we must divide by $2$ to get the true number of edges $e = 3L + 2P$.

Putting this all together, we find $$ f - (3L + 2P) + (2L + P) = 2 $$ That is $$ f - L - P = 2 $$ Or $$ f = 2 + P + L $$ You might wonder why we have $2$ instead of $1$ in this last expression. That is because the exterior of the graph counts as a face for Euler's formula. That is, we have overcounted by $1$. Therefore, the number of regions is given by $$ R = 1 + P + L $$ as you suspected.

The only remaining question is how to assign a probability to $P$. As I mentioned in my first comment, my guess is that this will be impossible without more precisely defining how you will be randomizing your lines.

Answer 2

Following the hint from antkam, With $L$ lines intersecting $P$ points, we have number of regions at $R=1+L+P$. $E(P(L))$ can be calculated by linearity of expectation, which means for any two lines, there is $\frac{1}{3}$ probability that they intersect and we have $C^2_L$ combinations. So, $E(R(L))=1+L+\frac{C^2_L}{3}$.