于超平面的凸集中随机取点

BeerRabbit

问题：如何在n+1维超空间内的超平面Sum[Xi,{i,1,n}]=S上被条件Xi~（0,1）限制的凸集T中随机取出一个点。





补充内容 (2015-1-27 11:17):
更正：是n维超空间

补充内容 (2015-1-27 11:18):
另外，将此问题推广一下，即如何在一个n维空间中的闭合的由线性规则约束形成的凸集内随机取点。

mathe

不妨设$k<=S<k+1$,其中k为整数，于是我们可以计算出超平面和超正方体$[0,1]^{n+1}$的边界的所有交点坐标都可以计算出来，必然是k个分量为1，还有一个$S-k$,余下都是0,共$h=(n+1)C_n^k$个点${A_1,A_2,...,A_h}$。然后我们找出单位向量$e_{n+1}=\frac{1}{\sqrt(n+1)}(1,1,...,1)$以及另外任意n个单位向量$e_1,e_2,...,e_n$和这个单位向量构成标准正交系，于是我们得到正交阵$[e_1,e_2,...,e_{n+1}]$,然后我们将h个交点用这个正交阵变换去掉最后一维坐标就得到一个n维超多面体所有顶点的n维坐标表示，产生里面随机点就可以了。

mathe

对于k维空间中平面$x_1+…+x_k=s$和单位超立方体交面的超面积可如下计算。先将交面投影到平面$x_k=0$得到区域可表示为$max(0,s-1)<=x_1+…+x_{k-1}<=s$
于是可以通过积分来推导出投影面积。
而积分$\int...\int_{0<=x_1+…+x_{k-1}<=s,0<=x_i<=1}dx_1…dx_{k-1}$可以根据s取值写成分段函数。
而这些分段函数可以通过递推式给出

mathe

算出上面这些积分的分段函数以后，解决本题就容易了。我们可以先计算x_1的边界分布密度函数，可以用这些积分表示，然后可以利用这个分布产生x_1,然后就变成低一维的问题了
现在我们记函数
$f(k,s)=\int...\int_{s<=x_1+x_2+...+x_k<=s+1,0<=x_i<=1}dx_1dx_2...dx_k$
显然$\int_0^k f(k,s)ds=1$
而且$f(k,s)$是分段多项式函数，其中$h<=s<=h+1$上是一个k次多项式，这个多项式我们可以记为$f_{k,h}(s)$
于是
$f_{1,0}(s)=s,f_{1,1}(s)=2-s$
而
$f_{k+1,h}(s)=\int_0^{s-h}f_{k,h}(s-x_{k+1})dx_{k+1}+\int_{s-h}^1f_{k,h-1}(s-x_{k+1})dx_{k+1}$

mathe

然后对于n+1维空间中随机点$x_1+x_2+...+x_{n+1}=S$,相当于n维空间中选择n个随机点使得$S-1<=x_1+x_2+...+x_n<=S$
我们先按照密度函数\(\frac{f(n-1,S-x)}{\int_0^1 f(n-1,S-x)dx}\)随机选择$x_n$，也就是随机选择[0,1]中均匀变量t,然后如果
\(\frac{\int_0^hf(n-1,S-x)dx}{\int_0^1 f(n-1,S-x)dx}=t\),那么选择$x_n=h$即可。
然后就变成在n-1维空间中选择n-1个随机点使得$S-1-h<=x_1+x_2+...+x_{n-1}<=S-h$,一直下去直到最后一个变量$x_1$.最后在计算$x_{n+1}=S-x_1-x_2-...-x_n$