在圆周上任意取3点，求这3个点可以被分配在一个半圆周上的概率

mathe

wayne 发表于 2014-1-16 20:06
设 $X_i, 0\leq i \leq n$ 服从 $[0,2\pi]$的均匀分布.
那计算
得到 ${n+1}/2^n$

两个问题稍有不同，这个不带回绕的，应该要小一些

Lwins_G

@wayne

这个现象可以解释。

我们试图定义一个从线性的`n`点合法方案一一对应于环状的`n+1`点合法方案的映射`f`。

定义`f`如下：

1) 把这个线性的`n`点方案首尾相接，并且新添加第`n+1`个点在连接处，得到一个环状的`n+1`点方案。
2) 如果得到的不是合法方案，那么把除了新加的点以外的所有点放置到它们原先所在的位置的正对侧，易知现在它必然是合法的。

证明`f`是一一对应的步骤就不写了，有兴趣的读者可以自己举几个例子理解一下它为什么确实是一一对应的。

wayne

mathe的思路我详细陈述一下。
如果$n$个点分布在角度为$2t\pi$内的概率是$F_n(t)$，那么，$F_{n+1}(t)$的计算 可以针对前面$n$个点的分布情况来积分:
假设前面$n$个点分布在角度为$2s\pi, s\in(0,t)$的范围内，那么第$n+1$个点不仅可以落在角度$2s\pi$范围内，还可以分别落在角度$2s\pi$两侧的$2(t-s)\pi$的范围内，即这种情况合理安放第$n+1$点的位置的概率就是 $2(t-s)+s =2t-s$，于是对$s$进行积分：
$F_{n+1}(t)=\int_{s=0}^t (2t-s)dF_n(s)$
======
另外，mathe的这个积分式子可以根据 分部积分转化成：
$F_{n+1}(t) = t*F_n(t) + \int_0^tF_n(s)ds$

hujunhua

依照2#和5#的方法，于圆周上任取n点偏于一个半圆的概率，可以如下计算：

首先，不用考虑其中任意两点处于一种固定的相对位置的情况，比如两点重合或者处于对径位置情况。对于连续的圆周来说，这样的特例概率是零。所以只需要考虑n个不同点，并且没有两点处于对径位置的情况，这样的一个n点组，我们称为一个样本。
任一特定样本s，将其中的1个点或者更多的点换成其对径点所得的新样本 s’ 称为它的一个相关样本。显然，s 连同它自身共有$2^n$个相关样本，对于对径变换，它们组成一个封闭的簇。
于是整个样本空间可以划分为一个个簇, 所有的簇组成样本空间的一个商集。显然，每个簇恰好有2n个半偏样本，所以取到半偏样本的概率是${2n}/2^n=n/2^{n-1}$.

关于每个簇恰好有2n个半偏样本，说明一下。一个簇有2n点，分为n对对径点，将圆周分成了n对相对弧段。在任意一段半圆周上，都恰好包含其中的n个点（直径端无点）或者n+1个点（直径端有点，我们不用考虑这种零概率情况），这就是一个半偏样本。当半圆的直径端在一对相对弧段上滑动时，所包含的半偏样本是不变的，所以一对相对弧段对应于1对半偏样本。故共有n对半偏样本。

hujunhua

wayne都说不觉明，那是我表述还不够清晰呀，我还自以为描述得跟杜甫的诗一样，妇孺皆知呢。有点受打击！
我估计应该是对“每到个簇恰好包含2n个半偏样本”的说明不够充分。加个图吧。至于什么商集，如果不熟悉，可以无视它，不影响。

如图，红色虚线半圆（为了清晰，将它缩到了圆内，实际上应该与圆重合的）包含了一个半偏样本｛1,2,3,4,..., n｝,当半圆的直径端P,P'在相对弧段1n', 1'n上滑动时，半圆弧所包含的点仍然是{1,2,3,4, n}. 所以相对弧段1n'&1’n 就对应于一对相对的半偏样本｛1,2,3,4,...,n｝&｛1',2,',3,',4',...,n'｝.

wayne

额，老大这是在核查我是否真的吸收了你的元气么，好，请鉴别：

n个点之间存在重叠或者对径重叠现象的因为维度低且种类有限可数，所以概率为0 不予考虑。

现在只考虑既不重叠也不对径重叠(即中心对称)的情况：
这种情况下，对于$n$个点，总能新产生出位置不同的$n$个对径点。这$2n$个点分布在圆周上，将圆周分成$2n$小段.
我们在圆上任取一条直径，试验一下直径将这n个点分成2堆的情况，将会发现，连同这n个点的对径点一块算的话，直径总能将这$2n$个点对半分。
这种分法总共有$2n$种,又因为总样本空间,即$n$个点分成2堆,有\(2^n\)种,所以$n$个点分布在半圆弧内的概率就是\(\tfrac{2n}{2^n}\)
过关了没，

sheng_jianguo

楼主题目可以推广到高维空间的超球面，我在2#给出的是3维空间中2维球面请况，对于一般情况下我推出的结果如下（原理见2#的说明）：
若在$r+1$维空间中，$n$个$r-1$维超球面最多可以把$r$维超球面切割成$F(n,r)$部分，则
当$r$为奇数时\[F(n,r)= 2\binom{n}{1}+2\binom{n}{3}+…+2\binom{n}{r}\]
当$r$为偶数时\[F(n,r)= 2\binom{n}{0}+2\binom{n}{2}+…+2\binom{n}{r}\]
（其中，\(\binom{n}{i}=\frac{n!}{i!\cdot{(n-i)!}}\)表示$n$个数中取$i$个数组合的个数$(i=0,1,2,…,r)$，当$n＜r$时，\(\binom{n}{i}=0\)).
所以，若在$r+1$维空间中，在$r$维超球面上任意取$n$个点，则这$n$个点可以被全部分配在半个超球面上的概率为\(p=\frac{F(n,r)}{2^n}\)。
请各位高手看看上面组合公式是否还能简化。
举例：
当$r=1$时，即2维空间中，$n$个双点（0维球面）最多可以把圆（1维球面）分为\(F(n,1)=2\binom{n}{1}=2n\)，故$r=1$时, \(p=\frac{2n}{2^n}\)。
当$r=2$时，即3维空间中，$n$个圆（1维球面）最多可以把球面（2维球面）分为\(F(n,2)=2\binom{n}{0}+2\binom{n}{2}=n^2-n+2\)部分，故$r=2$时，\(p=\frac{n^2-n+2}{2^n}\)。
当$r=3$时，即4维空间中，$n$个2维球面最多可以把3维球面分为\(F(n,3)=2\binom{n}{1}+2\binom{n}{3}=(n^3-3n^2+8n)/3(n>2时)\)部分，故$r=3$时，\(p=\frac{n^3-3n^2+8n}{3\cdot{2^n}}\)，当$n>2$时，$p=1$，当$n<3$时。

hujunhua

sheng_jianguo 发表于 2014-1-7 08:39
我知道比较好的解答如下，不知有更好的解答：
　　因为是均匀分布，所以取到每个点的概率密度与取到其对径 ...

……可以证明，F(k)等于球面上k个大圆（任意两个大圆不重合，任意三个大圆不共点）把球面分割成小片的片数。

这个如何证明的？

sheng_jianguo

hujunhua 发表于 2014-1-22 15:30
……可以证明，F(k)等于球面上k个大圆（任意两个大圆不重合，任意三个大圆不共点）把球面分割成小片的片 ...

当初我是在网上看到3维空间上的结果（见2#），没严谨推敲其证明，但用编程法计算过模拟概率，结果与公式非常接近，也找不出反例。27#高维空间结果是我自己推出的。
今天在网上又查了一下，此问题在1962年已有很好的一般性结论，我推出的结论和他相同，只是人家公式更简洁（我推出的结果再用杨辉三角恒等式就和他完全一样）。下面摘录网上查到文章，不知老大有更好更有说服力的想法：

球面上随机N个点在同一个半球上的概率
作者：张志强， 发表于 2012年8月23日
这个题目是当年北大概率课上陈大岳老师出的练习题目，当时是一个简单情形，球上4个点组成的四面体包含球心的概率。最近在MITBBS上看到又有人提及。我在这里写一下解答。
这个题目事实上是1962年J.G. Wendel发表于Math. Scand的论文A problem in geometrical probability。论文给出了一个更一般性的结论：d-维空间的单位球面上随机分布的N个点，全在同一个半球上的概率是：\[\begin{equation}P_d(N)=\frac{1}{2^{N-1}}\sum_{i=0}^{d&#8722;1}\binom{N&#8722;1}{i}\end{equation}\]
不过我很不喜欢这篇文章的证明过程。在这篇论文证明的基础上，可以抽象出来另外一种方法，我觉得更接近于问题的本质：
首先随机抽取 N 个点$ x_1,x_2…,x_N $，考虑它们在球面上的对称点。在这 N 对对称点各取其一，一共有$ 2^N$ 种取法。我们下面将这些取法当成样本，计算这里面有多少个样本满足 N 个点都在同一个半球上。不考虑发生概率为0的边界情况，对于任何一个半球，恰好有一个样本满足所有点都在这半个球面上。接下来我们只需要计算有多少个不同的半球，对应不同的样本。
半球与球面上的点有一一对应关系，这一点是这个半球的「极点」。画以xi 为「极点」的半球所座的大圆(d-1维)，一共形成 N 个大圆。这些大圆将球面划分为若干个区域。很容易发现，对于同一个区域的点所对应的半球，都包含同一个样本；不同区域的点对应的半球，则包含不同的样本。
这就是说位于同一个半球的样本数量等于 N 个大圆将球面划分的区域的数量，即\(2\sum_{i=0}^{d&#8722;1}\binom{N&#8722;1}{i} \)。从而可得最终的结论(1)。

hujunhua

“很容易发现，对于同一个区域的点所对应的半球，都包含同一个样本；不同区域的点对应的半球，则包含不同的样本。” 这一点需要有所说明。

这应该是由极点与赤道大圆的对应关系的关联性质所决定的。且记点以$p$为极点的赤道大圆为\(\bigodot{p}\). 那么\({p_1\in\bigodot{p_2}}\iff{p_2\in\bigodot{p_1}}\). 所以，点$p$在一个区域内移动时，\(\bigodot{p}\)随之转动，只要点$p$不触碰区域的边界，边界（大圆弧）所对的极点就不会触碰\(\bigodot{p}\), 所以也就不会越过\(\bigodot{p}\)（因为连续性，要越过，必经触碰）.所以............