is cut into several regions by picking two random points on the border of the square at a time and connecting them to form
"random" lines. What is the expected number of regions? [/quote]
We will use
, where
, , and
are the expected number of vertices, edges, and faces, respectively.
We begin by computing the expected number of vertices. There are
vertices from the square and
vertices from the endpoints of each line (the probability of two lines sharing the same vertex is 0). Now, we find the expected number of vertices inside of the square. By linearity of expectation, this quantity is equal to the probability of two lines intersecting times the total number of pairs of lines. There are
pairs of lines.
The probability that a given pair of lines intersect is equal to the probability that no 3 endpoints are collinear. We have two cases. There is a
probability of having 3 points on one side of the square and 1 point is on the another. There is a probability of
of having all 4 points on the same side. So the probability of it being possible to make the lines intersect is
. The probability that the lines are the diagonals of the quadrilateral is
, because when we take a vertex of the quadrilateral and connect it to another vertex, there are 3 other vertices, but only 1 is good. Hence, the probability that a pair of given lines intersect is
. So the expected number of vertices is
.
Let us now compute the expected number of edges. We start out by finding the number of edges that are on the boundary of the square. For each point we add to the perimeter, we add one more edge. Initially, we had 4 sides. If we have
lines, then we have
points. So the number of edges that are on the boundary is
.
Now we compute the expected number of edges inside the square. For each pair of lines that intersect inside the square, they add
new edges. The expected number of edges we start out with inside of the square is
(because
lines). The expected number of intersection points inside of the square is
. Therefore, the expected number of edges inside the square is
.
Adding both cases up, we have an expected total of
edges.
Plugging
and
into
, we get that
. However, we need to subtract out 1 for the face outside the square. Thus, our desired answer is
.