まず、カットの直線同士が完全に一致する確率、\(3\) 本以上のカットの直線が \(1\) 点で交わる確率は \(0\) であり、これらの事象は期待値に影響を与えない。よって、以下では \(M\) 本のカットの直線全てが円の内部を通り、円の内部の点を通るカットの直線は高々 \(2\) 本であるとして考える。

すると円の分割数は、\((円の内部の交点数)+M+1\) と表される。

\(i\) 回目のカットと \(j\) 回目のカットが円の内部で交点をもつ確率を \(p_{i, j}\) とすると、期待値の線形性より、 \(\displaystyle E(円の内部の交点数)=\sum_{i \lt j} p_{i,j}\) が成り立つ。

また、円の接線を \(\theta (0 \lt \theta \le \frac{\pi}{2})\) だけ回転させた直線がその円に対して張る弦の中心角は \(2 \theta\) であるため、点 \(P_{A_i}\) を通る全ての直線から一様ランダムに直線を選ぶという操作は、円周上(点 \(P_{A_i}\) を除く)から一様ランダムに \(1\) 点を選び、その点と点 \(P_{A_i}\) を通る直線を考えるのと等しい。

よって、\(A_i \neq A_j\) のとき、弦 \(P_{A_i} P_{A_j}\) の中心角を \(2\alpha\pi (0 \lt \alpha \lt 1)\) とおき、弦 \(P_{A_i} P_{A_j}\) によって分けられる円の内部のそれぞれの領域において \(i\) 回目のカットと \(j\) 回目のカットが交点を持つ条件を考えると、先述の言い換えを適用した際にランダムに選ばれる \(2\) 点の対称性より、\(p_{i, j} = \frac{\alpha^2+(1-\alpha)^2}{2} = \alpha^2 - \alpha + \frac{1}{2}\) が成り立つ。また、\(\alpha = \frac{| A_i - A_j |}{N}\) である。

以上より、

\(\displaystyle E(円の内部の交点数)=\sum_{i \lt j} p_{i,j}\)

\(\displaystyle = \sum_{i \lt j} \frac{(A_i - A_j)^2}{N^2} - \sum_{i \lt j} \frac{| A_i - A_j |}{N} + \frac{D}{2}\)

となる。ただし、\(D\) は \(A_i \neq A_j\) をみたす組 \((i,j)(i \lt j)\) の個数である。

各項は \(A\) を事前にソートしておくことで \(O(N)\) で求まるため、全体としてこの問題を \(O(N \log N)\) で解くことが可能である。