来自某教师群昨晚的单位正方形内两点距离大于1的概率

kuing

云浮罗伟荣(5922*****) 22:18:51
请教大家：在边长为1的正方形内（含边界）任取两个点A，B，则|AB|≥1的概率是多少？
这个问题应该怎么破？

话说曾经在《撸题集》第907页题目6.8.7里写过类似的题，然而细想后发现上面这题比那题要复杂得多，因为那题全是圆，而这里既有圆又有方，重叠面积公式非常复杂，还要用重积分，下面大致写写。

首先将正方形放在坐标系中，使之为 $[0,1]\times[0,1]$。下面设定一些区域，记
\begin{align*}
D&=\left\{ (x,y)\biggm|0<y<x<\frac12 \right\}, \\
D_1&=\{(x,y)\mid(x,y)\in D,x^2+(y-1)^2<1,(x-1)^2+(y-1)^2>1\}, \\
D_2&=\{(x,y)\mid(x,y)\in D,x^2+(y-1)^2<1,(x-1)^2+(y-1)^2<1\}, \\
D_3&=\{(x,y)\mid(x,y)\in D,x^2+(y-1)^2>1\},
\end{align*}
它们表示的区域如下图。

下载 (4.09 KB)

2016-3-21 17:45

　　　　

下载 (9.67 KB)

2016-3-21 17:45

现在，在 $D$ 内取一点 $(x,y)$，以其为圆心，作半径为 $1$ 的圆，记在圆外且在正方形内的区域面积为 $S(x,y)$。

下载 (12.97 KB)

2016-3-21 20:36

　　　　

下载 (14.96 KB)

2016-3-21 20:36

经过计算，可以求出
\[S(x,y)=\led
& f(x,y), && (x,y)\in D_1, \\
& 0, && (x,y)\in D_2, \\
& f(x,y)+f(1-x,y), && (x,y)\in D_3,
\endled\]
其中
\[f(x,y)=\frac12\left( 2(1-x)(1-y)-(1-x)\sqrt{x(2-x)}-(1-y)\sqrt{y(2-y)} +\arccos (1-x)+\arccos (1-y)-\frac\pi2 \right), \]
那么，根据对称性，所求的概率为
\[P=8\iint_{D}S(x,y)\rmd x\rmd y=8\iint_{D_1}f(x,y)\rmd x\rmd y+8\iint_{D_3}f(x,y)+f(1-x,y)\rmd x\rmd y.\]

到这里，已经不是人工可以做了，即使开挂，挂也挂，想算出精确值，不大可能，只好改用数值计算命令，计算其近似值，如下图：

下载 (12.77 KB)

2016-3-21 20:30

即 $P\approx 0.025074$。

嘛，我知道这样的过程不会让人信服，连我自己都没什么信心，于是决定还是用挂来摸拟实验。

在Mathematica7中运行如下程序：

1. i = 0;
   
2. n = 10^8;
   
3. Do[x1 = RandomReal[];
   
4.   y1 = RandomReal[];
   
5.   x2 = RandomReal[];
   
6.   y2 = RandomReal[];
   
7.   If[(x1 - x2)^2 + (y1 - y2)^2 >= 1, i++],
   
8.   {n}];
   
9. N[i/n]

复制代码

这里的 RandomReal[] 是产生 [0,1] 内的随机数，共做 10^8 次独立重复试验来统计结果。

运行十来二十分钟之后，看结果是多少，就大概知道那个近似值是否准确了，各位有软件的话不妨自己运行一下。

kuing

当然了，或许有其他方法绕过那些复杂的计算，等概率大神来玩了……

至于那个 S(x,y) 的公式，晚点我再用软件验证一下……

煮饭先……

kuing

面积公式验证成功：

下载 (34.12 KB)

2016-3-21 20:45

战巡

回复 1# kuing

这就相当于四个随机变量$x_1,x_2,y_1,y_2\sim UNIF(0,1)$且全部独立
\[f(x_1,x_2,y_1,y_2)=1·I_{[0,1]}(x_1,x_2,y_1,y_2)\]
令$u=x_1-x_2,v=y_1-y_2$
易证$u,v$服从三角形分布，有
\[f(u,v)=(1-|u|)(1-|v|)I_{[-1,1]}(u,v)\]
令$p=u^2,q=v^2$
\[f(p,q)=\frac{1-\sqrt{p}}{\sqrt{p}}·\frac{1-\sqrt{q}}{\sqrt{q}}I_{[0,1]}(p,q)\]
令$k=p+q=(x_1-x_2)^2+(y_1-y_2)^2$，有
\[f(k,q)=(\frac{1}{\sqrt{k-q}}-1)(\frac{1}{\sqrt{q}}-1)I_{[q,q+1]}(k)I_{[0,1]}(q)\]
\[f(k)=\int_{\max(0,k-1)}^{\min(k,1)}(\frac{1}{\sqrt{k-q}}-1)(\frac{1}{\sqrt{q}}-1)dq\]
\[=(k+\pi-4\sqrt{k})I_{[0,1)}(k)+(4\sqrt{k-1}-k-2+2\arctan(\frac{1}{\sqrt{k-1}})-2\arctan(\sqrt{k-1}))I_{[1,2]}(k)\]
\[P(k\ge 1)=1-\int_0^1f(k)dk=1-\int_0^1(k+\pi-4\sqrt{k})dk=\frac{19}{6}-\pi\]

kuing

回复 4# 战巡

虽然完全不懂，但看起来是正确的样子 $19/6-\pi$ 确实约为 $0.025074$ 应验了二楼说的，只是没想到结果会这么简单

isee

三角形分布 第一听说，或者，是完全忘记了。。。。

战巡

回复 5# kuing


最后求出来的那个就是|AB|^2的概率密度函数，所以理论上不管它问|AB|在什么范围都可以通过这个来求，不过还好它这里只是|AB|>1，如果是什么|AB|>1.1之类就麻烦了，后面那一块的积分看起来不是善茬

血狼王

回复 7# 战巡

看得出来。
所以说这道题里面水很深，进一步推广难度实在有点大

战巡

回复 6# isee

三角形分布一般在概率论中都不怎么讲，所以很多人没听过也很正常
不过其实并不复杂，两个均匀分布相加或相减就是三角形分布

鉴于你们上不了维基，我截了个图出来

下载 (73.45 KB)

2016-3-22 23:42

血狼王

三角形分布……
这名字真精妙

血狼王

对了，如果改成在三角形内两点距离不超过xxx的概率，应该更刺激的……

战巡

回复 11# 血狼王


刺激啥？方法都是一样的，改成三角无非是把问题搞的更繁琐，有意思么？纯粹是以折腾人为目的么？
如果是工程上需要这个值，大可直接蒙特卡罗法解决，没必要去算精确值

三尺水

算算正方形里三点构成钝角三角形的概率吧

战巡

回复 13# 三尺水

没空去给你算这种坑爹问题的精确值，只跑个蒙特卡罗给你，结果自己看吧

下载 (25.79 KB)

2016-5-26 00:44

三尺水

回复 14# 战巡 我算出来了才考你们的。还有圆内随机三点，过三点的圆被大圆包含。求取到这三点的期望

三尺水

回复 14# 战巡
你这个仿真都是正方形里，圆里或三角形里怎么规定取点的边界，比如上面正方形改成圆，写个代码我看看

isee

搬个板凳做前排……

战巡

回复 16# 三尺水

你在之前的问题里写的就是“正方形”里，所以模拟用正方形

换成圆又何难之有？一看就知道你是没学过MCMC的，连这种问题都要问，还以为可以难倒别人

下载 (84.07 KB)

2016-5-26 23:54

那个圆饼就是抽样结果，给你看看是否均匀的
另外为了提高效率我这里用了minibatch，算法和之前的不一样

另：其他形状也都能做出来，只要知道分布的都能搞定，软件里没有直接对某分布抽样的大不了Metropolis–Hastings，没什么难的

三尺水

回复 18# 战巡


    结果没错，我的积分结果是去0.719675

三尺水

回复 18# 战巡 还有计算圆内取三点过三点的圆被大圆包含的概率