在一個半徑為1的圓內，任取四個點A,B,C,D，則線段AB與CD相交的概率為多少？

12-03

在一個半徑為1的圓內，任取四個點A,B,C,D，則線段AB與CD相交的概率為多少？

這個網頁供參考：Sylvester"s Four-Point Problem -- from Wolfram MathWorld
這是個有名的問題，問題原始描述為：一個區域內，隨機4點的凸包是三角形的概率有多大？——這和本問題其實是聯繫非常緊密的。在本問題中要求的其實是：在單位圓內，隨機4點的凸包是四邊形的概率有多大？而這等價於求：單位圓內，隨機4點的凸包不是三角形的概率有多大？
本問題中要求的兩線段相交的概率，實際上就是這個凸包是四邊形的概率的1/3。這個推導過程參見高票 @Lightwing 的答案。
根據參考網頁的結論，在單位圓內，隨機選4個點，組成凸四邊形的概率是 $1-frac{35}{12pi^2}$ ，所以本題的答案就是 $frac{1}{3}left(1-frac{35}{12pi^2} ight)approx0.23483$

應該是1/3吧

任意四個點，有六個edge。

設一對獨立edge，有以下三種方法。

每次只有一種方法是相交的。另外兩種不相交。
這三種方法都是一樣的概率。所以相交的概率為1/3。

或者說，如果給這四個點進行標字：A、B、C、D。總共有24種方法，4*3*2*1。
24種都有一樣的概率出現。
其中8種方法才導致AB、CD對應的是紅色對。
另外16種的AB、CD對應了綠色對或藍色對。

---

嚴格一點的說法：

假設圓周為1。
按順序在這個圓周上選個A、B、C、D。

A在哪裡不重要。
選B的時候，A和B把圓周分成了兩段。小段長度平均為1/4。大段長度平均為3/4。
圓周小段的分布也是uniform的;0到0.5都一樣概率出現。

如果小段為X，大段1-X。
那麼，選C和D的時候，如何才能讓CD與AB相交？
需要C和D，一個在小段一個在大段。

C在小段、D在大段：概率為X*(1-X)
C在大段、D在小段：概率為(1-X)*X
兩者總概率就是2X - 2X^2。

X本來是uniform的，0到0.5。
所以要integrate。把2X-2X^2 integrate從0到0.5。

那就是X^2 - (2/3)X^3 從 0 到 0.5。
-&> [ 0.5^2 - (2/3)0.5^3 ] - [ 0^2 - (2/3)0^3 ]
-&> [1/4 - 1/12] - [ 0 - 0 ]
-&> 1/3

---

之前好像看錯題目了，補充一些想法：

如果要求圓內而不是圓邊，第一部分邏輯還是成立的：

對應任何四個這樣的點，概率是1/3。

但是，圓內任意選四個點，不一定形成上圖那樣。還有很大概率形成以下這樣的：

如果選四個點，類似這種情況，相交的概率直接是0。

所以呢，假設四個點選成這樣的概率為P。
那AB、CD相交的概率是：（1-P）*（1/3） + P * 0。

所以絕對少於1/3！

求具體答案，應該先求P。

P：一個圓內，任意四個點，一個點在另外三個點所形成的三角形之內的概率。

我們可以分為四種獨立情況：
D在ABC三角內，C在ABD三角內、B在ACD三角內、A在BCD三角內。

四個概率一樣，也不能同時發生，所以假設其中一個概率為P*。P=4P*。

如何求P*，這個很難。

P*：一個圓內，先任意選三個點作為三角形，再選一個點。點在三角形內的概率。
也就是這個點在三角形面積之外的概率。

再假設我們知道圓內所有三角形的面積分布：
F(t) -&> 在所有這樣的三角中，三角面積於圓圈面積比例少於t的概率。

F(t)很重要，因為：

P* = integral of t * F"(t) between 0 and 1.

或者說，本提問的答案是 1/3 - 4/3 * integral of t * F"(t) between 0 and 1.

但是F(t)很複雜，至少有O(t^7)。也有可能包括pi。答案是有的，只是比較麻煩。

Random triangles 這篇論文裡面有探索這個隨機三角在圓內的面積問題。
這論文收費，沒法打開。

但是這種三角的平均面積比例是35/48pi。
不過這是integral of F"(t) between 0 and 1。而非integral of t * F"(t) between 0 and 1。
只能說追求的P*少於 35/48pi。少很多。

不好意思沒有絕對答案，只能說少於1/3很多。

---

（真要得出F(t)有這麼一種思路）

三個點A、B、C。圓中心為N。
NA、NB、NC三個線的長度分別為a、b、c。
BNC、CNA、ANB三個角度分別為A",B",C"。

然後該三角面積則是0.5*(b*c*sin[A"] + c*a*sin[B"] + a*b*sin[C"])。

我們只知道A"+B"+C"這些角度其中兩個是uniform，0 - 2pi 之間隨機。
第三者受限A"+B"+C" = 2pi（全形）。

然而a、b、c這些長度互相獨立、也在0和1之間，但是非uniform，是t^2這樣一個分布。
（因為選一個點，離中心更遠，概率越大）

應該是可以把這些條件或分布用在上面面積方程上。。。
integrate三四次來獲得最後面積分布的結果F(t)。。。
但是保證結果很難看很複雜。F(t)複雜了，那這個提問的答案也會很複雜的。

---

P* = (35/48) * (1/pi^2) ??
所以答案可能是 1/3 - (35/36)*(1/pi^2) = ~0.23483

先上答案 $frac{1}{3} (1-frac{35}{12pi^2} )$
說實話第一次看到這個問題我就想會不會和這個問題在邊長為1的正方形中隨機取三個點，構成三角形的面積期望是多少？ - Lancewu 的回答 - 知乎有關係。
我在上述回答里後面附加了圓內隨機三角形的面積期望，計算方法和軟體模擬，答案是 $frac{35}{48pi}$ 。怎麼樣，機智的你可能已經從答案的相似性---- $frac{35}{12pi^2}=frac{4}{pi} imes frac{35}{48pi}$ 中看出來聯繫了。

我先說一些怎麼把此題轉換成計算圓內隨機三角形的期望。

首先讓 $A$ , $B$ , $C$ , $D$ 四個點的坐標（也是隨機變數）記為 $a,b,c,d$ 。
大寫表示變數，小寫表示固定的坐標而不是變數。

下面用標準的數學表示方法，可能有些不友善。

不過我先盡量科普一下。
$mathbb{P}($ 某事件 $)$ 代表某事件發生的概率(probability)， $mathbb{P}($ 某事件 $X|$ 某條件 $Y)$ 代表在給定某條件 $Y$ 的情況下某事件 $X$ 的發生的概率。
並且有 $mathbb{P}(X|Y)=frac{mathbb{P}(X)}{mathbb{P}(Y)}$ 和 $mathbb{P}(X)=sum_{i} mathbb{P}(X|Y_i)mathbb{P}(Y_i)$ 或者 $mathbb{P}(X)sim int_{y} mathbb{P}(X|Y=y)mathbb{P}(Y=y)=int_{y} mathbb{P}(X|Y=y)f_Y(y)dy$ 。

接下來開始正答。
讓 $X$ 代表事件： $AB$ 與 $CD$ 相交。

$mathbb{P}(X)$
$=int_{a,b,c,d} mathbb{P}(X|A=a,B=b,C=c,D=d)f_A(a)f_B(b)f_C(c)f_D(d)da~db~dc~dd$
這裡有四個pdf,其實都是同一個函數，可以都寫成 $f(x)$ 的形式。
$=int_{a,b,c,d} mathbb{P}(X|A=a,B=b,C=c,D=d)f(a)f(b)f(c)f(d)da~db~dc~dd$
到這一步先把這個被積概率寫成兩個函數

$p(a,b,c,d):=mathbb{P}(X|A=a,B=b,C=c,D=d)$
$F(a,b,c,d):=f(a)f(b)f(c)f(d)$

理解下 $p$ ,即放入四點坐標，如果AB相交CD, $p=1$ ;如果沒有相交， $p=0$ .

讓 $Phi ={(a,b,c,d):a,b,c,din D^1}$ 是這個四維的樣本空間。 $D^1$ 指圓心在原點，半徑為1的圓盤。
那麼我們的積分可以正規寫成：
$=int_{(a,b,c,d)inPhi}p imes Fda~db~dc~dd$

那麼這兩個函數有什麼可以利用的地方呢？
我們知道如果一個有關圓的問題，你不利用一下對稱性的話，那宛如一個智障。
這時候就考慮一下如果交換變數會怎麼樣，記得 $a,b,c,d$ 一共有 $4!=24$ 種排列方式。
因為 $F(a,b,c,d)=f(a)f(b)f(c)f(d)$ 的構造特殊，對於它來講不管什麼排列方式結果都是一樣的，那麼下列的情況我們只需要考慮 $p(a,b,c,d)$ 就行了。

1.
如果 $D$ 在三角形 $ABC$ 內,如下圖，並沒有相交， $p(a,b,c,d)=0$ .

如果瘋狂重命名呢？
舉個例子，因為AB這條線等於BA,CD也等於DC.
所以 $p(a,b,c,d)=p(b,a,c,d)=p(a,b,d,c)=p(b,a,d,c)=0$ ,這裡就搞定了4種情況，另外AB和CD互換也是一樣的兩條線，即 $p(c,d,a,b)=p(d,c,a,b)=p(c,d,b,a)=p(d,c,b,a)=0$ 又是4種。這8種情況都是對應的同樣一組線。
在上面這幅圖裡，我們可以看到有三組線段，分別為綠色，藍色和紅色。
每組線段的端點互換可以代表8種情況，三組包含了所有 $a,b,c,d$ 的24種排列方式。
我們可以看到不管是哪種排列， $p$ 的值始終為0。

2.
如果 $A$ 在三角形 $BCD$ 內，類似， $pequiv 0$
3.
如果 $B$ 在三角形 $ACD$ 內，類似， $pequiv 0$
4.
如果 $C$ 在三角形 $ABD$ 內，類似， $pequiv 0$
5.
如果上述情況都不發生，我們有下圖

那麼同樣的道理，這三組分別代表8種情況，只有藍色的8種情況下， $p$ 的值為1，其他都是0.

那麼如何利用上面這些結果呢？記住AB與CD相交的概率等於AC與BD相交的概率，等於BC與AD相交的概率等等，可以理解為只是把變數的順序換一下而已。那麼我們有下列這24個積分相等。

$int_{(a,b,c,d)inPhi}p(a,b,c,d)Fda~db~dc~dd=int_{(a,b,c,d)inPhi}p(a,b,d,c)Fda~db~dc~dd$

$=...=int_{(a,b,c,d)inPhi}p(d,c,b,a)Fda~db~dc~dd$
所以原積分為上面24個積分之和的24分之一。
為了方便寫，
讓 $g(a,b,c,d)=p(a,b,c,d)+p(a,b,d,c)+...+p(d,c,b,a)$ 為這24個函數的相加。

則原積分 $=frac{1}{24} int_{(a,b,c,d)inPhi}g(a,b,c,d)Fda~db~dc~dd$

現在設 $Psi={(a,b,c,d)in Phi|a~in~Delta abc~or~b~in~Delta~acd~...}$ 即上面1~4種情況的集合。

根據上面的分析，我們有
如果 $(a,b,c,d)in Psi$ (即一點在另外三點的三角形內)，24個 $p$ 全是0，所以 $g(a,b,c,d)=0$ .
如果 $(a,b,c,d) otin Psi$ (即任意一點不在另外三點的三角形內)，24個 $p$ 里有8個1，所以 $g(a,b,c,d)=8$ .

所以
$=frac{1}{24} int_{(a,b,c,d)inPsi}g(a,b,c,d)Fda~db~dc~dd+frac{1}{24} int_{(a,b,c,d) otinPsi}g(a,b,c,d)Fda~db~dc~dd$
$=frac{1}{24} int_{(a,b,c,d) otinPsi}8Fda~db~dc~dd$
$=frac{1}{3} int_{(a,b,c,d) otinPsi}f(a)f(b)f(c)f(d)~da~db~dc~dd$
$=frac{1}{3} mathbb{P}((A,B,C,D) otinPsi)$
$=frac{1}{3} (1-mathbb{P}((A,B,C,D)inPsi))$

呼...算到這裡只需要證明

$mathbb{P}((A,B,C,D)inPsi)=frac{4}{pi}mathbb{E}(A_{Delta ABC}|A,B,Cin D^1)$
右邊那個值是 $frac{4}{pi}$ 倍的圓內隨機三點形成的三角形的面積期望值。

然後那個期望值我們已經在這個回答里算出了在邊長為1的正方形中隨機取三個點，構成三角形的面積期望是多少？ - Lancewu 的回答 - 知乎
所以只要證明這兩個相等就行了。

$mathbb{P}((A,B,C,D)inPsi)$
$=mathbb{P}(D~in~Delta ABC)+mathbb{P}(A~in~Delta BCD)+mathbb{P}(B~in~Delta ACD)+mathbb{P}(C~in~Delta ABD)$
因為對稱
$=4 imesmathbb{P}(D~in~Delta ABC)$
$=4int_{a,b,c,d}mathbb{P}(D~in~Delta ABC|A=a,B=b,C=c,D=d) imes f(a)f(b)f(c)f(d)~da~db~dc~dd$
我們先對 $d$ 進行積分。
$=4int_{a,b,c}mathbb{P}(D~in~Delta abc)~~f(af(b)f(c)da~db~dc$
中間那個指給定一個三角形 $Delta abc$ ,點 $D$ 在三角形內的概率是多少，很明顯就是三角形的面積除以圓的面積
$=4int_{a,b,c} frac{S_{Delta abc}}{pi} imes f(a)f(b)f(c)~da~db~dc$
$=frac{4}{pi}int_{a,b,c} S_{Delta abc} imes f(a)f(b)f(c)~da~db~dc$
$=frac{4}{pi}mathbb{E}(A_{Delta ABC}|A,B,Cin D^1)$
$=frac{4}{pi} imes frac{35}{48pi}$
$=frac{35}{12pi^2}$

那麼最終答案是
$mathbb{P}(AB$ 相交 $CD)=frac{1}{3} (1-frac{35}{12pi^2} )approx 0.23483$

基本思路和現在的高票答案是一模一樣的，不過我的寫法比較新手向，基本沒有跳步，每一步的邏輯都比較清晰，也相對比較嚴謹把。

在邊長為1的正方形中隨機取三個點，構成三角形的面積期望是多少？ - Lancewu 的回答 - 知乎
$square$

蒙一發大約是~0.23
這個辦法稍快一點
In[40]:= &<&< ComputationalGeometry`
n = 10^4.;
Count[Length /@ ConvexHull /@ RandomPoint[Disk[], {n, 4}], 4]/(3 n)

Out[42]= 0.236367
=============================================
In[132]:= Clear["Global`*"]
lines = Map[Line, RandomPoint[Disk[], {10^4, 2, 2}], {2}];
sol = NSolve[{x, y} [Element]
BooleanRegion[BooleanCountingFunction[{2}, 2], #], {x, y}] /@
lines;
Length@Select[Norm /@ ({x, y} /. Flatten[sol, {1, 2}]), # &< 1 ]/10^4.

Out[135]= 0.2341

Interesting question!
老師說過，對於probability裡面的問題，如果會抖機靈，世界會變得簡單很多

如果四個點是在圓上
我們可以這樣考慮這個問題：我們首先選擇三個點A,B,C,因為我們隨機選擇的點是隨機的，根據total probability theorem和對稱性（選擇三個點後我們可以任意指定哪個是A,哪個是B，哪個是C），我們僅僅需要考慮以下的這種「均勻情況」就好了

那麼當且僅當第四個點在(A,B)段上的時候是相交的，所以概率就是1/3啦。如果四個點在圓內
那麼我覺得要先問一句：這四個點到底是怎麼隨機均勻選擇的？比如我可以有兩種方法去選擇每個點

極坐標方式：我產生一個均勻分布在0到1的隨機數代表其半徑，再產生一個均勻分布在0到2Pi的隨機數代表其角度。
我獨立產生兩個隨機數，都是均勻分布在-1到1，作為其橫坐標和縱坐標，如果在圓外就捨棄，產生下一個，如果在圓內就接受。

以上兩種方法貌似都是「均勻隨機」，但是結果是不一樣的，比如如我們看分布在下圖中內圓中的概率，第一種方法是1/2，第二種方法應該就是1/4

回到原來的問題，我們就用第一種方法產生四個點好了。那麼再抖一次機靈，前三個點的平均情況應該如下圖所示。

那麼為了讓CD與AB相交，D的極坐標的半徑必須大於1/4（概率是3/4）並且角度要在AB之間（概率是1/3）所以貌似相交的概率是1/4.

To summary：

四個點在圓上的概率是1/3,
四個點在圓內（按照上述第一種方法產生四個點）的概率是1/4.

第一個與 @Lightwing相同，心裡比較踏實，第二個答案貌似有較大的出入，不知道是不是抖機靈失效，還是兩個答案的前提不一樣，比如如何產生圓內隨機點。 @Lightwing 大神，我的答案有沒有bug ？

Probability of Intersecting Two Random Segments in a Circle

線段 $p_1 p_2$ 與線段 $q_1 q_2$ 相交等價等價於， $p_1,p_2$ 位於 $q_1 q_2$ 兩側且 $q_1,q_2$ 位於 $p_1 p_2$ 兩側。

apartQ 用來判斷是否位於兩側，intersectQ 用來判斷是否兩個條件都滿足（也就是相交）。

apartQ[p1_,p2_,q1_,q2_]:=Simplify@UnitStep[-Last@Product[Cross[Append[p1-p2,0],Append[p1-q,0]],{q,{q1,q2}}]]; intersectQ=Evaluate[apartQ[{#1,#2},{#3,#4},{#5,#6},{#7,#8}]apartQ[{#5,#6},{#7,#8},{#1,#2},{#3,#4}]];

intersectQ 是一個 listable function，在實現的時候要利用這一點，

intersectQ@@Flatten[RandomPoint[Disk[],{1*^7,4}],{{2,3},{1}}]//Mean//N

(* 0.234956 *)

題主你倒是先定義一下樣本空間啊。。。玩幾何概型不定義樣本空間，會出貝特朗悖論的

直接甩個參考文獻吧http://www.jstor.org/stable/2689482?seq=1#page_scan_tab_contents

給的結論是35/12pi^2

@章佳傑， @Lightwing 的回答很有趣，很有啟發。仔細看了一遍後發現確實是自己想錯了，修改答案如下，組成四邊形時有1/3的情況相交，三角形凸包的時候相交的概率幾乎為0。所以答案應該還是0.23左右。

1/3

文科生弱弱問一句，a.b.c.d四個點都有無限種可能，這種情況，真的還可以算概率嗎