有没有一种从GLn子集中采样的快速方法？

Question

这个问题的规则是相当具体的,因为我实际上在查看 GLn 的子集,其中行和列向量必须具有某种形式(称这些向量有效 - 下面的例子),所以请耐心等待.以下是规则:

1. 您可以随机均匀地选择长度为n的有效非零向量.

2. 给定有效向量v1, v2, ..., vk,您可以[v1_1 v2_1 ... vk_1]使用该函数确定它们形成的部分列是否是有效向量的前缀(例如,是否作为有效向量的前k个条目出现)isPrefix.

3. 给定有效矢量v1,v2,...,vk,您可以使用该函数确定它们是否线性相关areIndependent.

目标是随机均匀地从这个GLn子集中进行采样.这是一个天真的解决方案失败:

    Step 1: Select a valid v1 uniformly at random. 
            If isPrefix(v1) then Go to Step 2.
            Otherwise repeat Step 1.

    Step 2: Select a valid v2 uniformly at random. 
            If areIndependent(v1,v2) & isPrefix(v1,v2), then go to Step 3. 
            Otherwise, repeat Step 2.

    ...

    Step n: Select a valid vn uniformly at random. 
            If areIndependent(v1,v2,...,vn) & isPrefix(v1,v2,...,vn), then END. 
            Otherwise, repeat Step n.

这个可能的解决方案的问题在于,它可能会陷入无限循环中,在不太可能的事件中areIndependent(v1,v2,...,vk) & isPrefix(v1,v2,...,vk)正确返回,TRUE但无法将此k元组完成为线性独立的有效n元组.这种情况的一个常见例子是,当k=n-1存在唯一的有效矢量时vn,其isPrefix(v1,v2,...,vn)为TRUE,但该矢量不依赖于先前的n-1个矢量.

因此,当我进入这个循环时,我需要以某种方式添加一些步骤来备份一两步,但我不一定知道我什么时候进入它.我正在寻找这些方面的解决方案:如果步骤k f(k)因某些显式函数的时间失败f而可能取决于有效向量的分布,则返回步骤k-1(或者甚至进一步,以某种明确的方式).

任何建议,评论,参考等将不胜感激!谢谢!

例子:

我实际上正在寻找有关如何进行抽样的一般参考或指南.我有几个有效矢量的例子,我希望这样做,而且我最终能够自己完成它比列出每个例子并让SO社区散列出解决方案更有帮助.但是,具体而且要理解所涉及的困难,这里有一个例子:

交替符号矩阵:如果向量的条目全为0,-1,1,则向量有效,非零条目在1和-1之间交替,并且条目的总和为1.例如,每个置换矩阵将由有效向量组成,还有以下内容:

 0  1  0
 1 -1  1
 0  1  0

不同的条目:如果向量具有不同的条目,则该向量有效.这个特别烦人,因为条件适用于行和列.

再次感谢所有看过这个的人们!

Answer 1

我怀疑您可能必须转向马尔可夫链蒙特卡罗算法 - http://en.wikipedia.org/wiki/Metropolis%E2%80%93Hastings_algorithm - 不一定是为了速度，但确保您的随机样本合理分布。

随机抽样的一种定义是产生相同的分布，就像从原始列分布中随机生成矩阵一样，然后仅保留有效的矩阵。

如果从树中生成项目，并且节点的度数不同，则不会以相同的概率访问叶子。考虑一棵具有两个非叶节点的简单树，其中一个具有单个叶子节点，另一个具有一百万个叶子节点。如果通过从根向下移动来采样，在每个节点处进行随机选择，则单个叶子子节点的访问次数将比具有一百万个兄弟节点的集合中任何特定叶子的访问频率更高。

由于您陷入了上面的无限循环，因此您发现了一个没有子节点的情况。假设根本没有叶子，那么您有一棵树，其中节点的度数并不相同。

您最终可能不得不为不同的有效性规则编写不同的方法，并且必须担心您的马尔可夫链需要多长时间才能“老化”并变得相当随机。后一点有一个（某种）例外。如果您试图计算出尾部概率来排除随机选择给定配置的可能性，您可以从该点开始马尔可夫链，因为 - 在原假设下 - 该点已经是随机选择的，所以如果您生成的所有值的统计数据都比该起点更大，有些可疑的事情正在发生。