圆周折线穿越计数
Segment Traversal
题目详情
在圆周上随机取点:先取 ,再取 并连线 ;继续取 ,每次连接 ;最后连 。
问:圆内部线段交点数的期望作为 的函数是什么?并计算 时的值。
You select a uniformly random starting point on the circumference of a circle, say . Then, you select another uniformly random point on the circumference, , and draw a line segment between and . You then continue to select uniformly random points on the circumference of the circle, say , and draw a line segment between and for each . Lastly, you draw a line segment from back to . Find the expected number of intersections between line segments on the interior of the circle as a function of . Evaluate this for .
解析
把这看作:在凸位置的 个点上,随机选择一个哈密顿环(按抽样顺序给出)。
一次内部交点由 4 个顶点决定:对任意 4 点,只有其两条对角线会相交。设该 4 点对应对角线为两条固定不相交边 (在图上端点不重合)。
随机哈密顿环包含两条给定不相交边的概率为
(计数:总哈密顿环数 ;同时包含两边的环数 。)
故交点期望为
当 :
答案:函数为 ,在 时为 。