6

这个问题的规则是相当具体的，因为我实际上正在查看 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)显式函数失败次数，则返回到步骤 k-1（或者更进一步，以某种显式方式）。f

任何建议、意见、参考等将不胜感激！谢谢！

例子：

我实际上正在寻找有关如何进行采样的一般参考或指南。我有几个我想这样做的有效向量示例，最终能够自己完成比列出每个示例并让 SO 社区散列解决方案对我更有帮助。然而，为了具体说明所涉及的困难，这里有一个例子：

交替符号矩阵：一个向量是有效的，如果它的条目都是 0、-1、1，非零条目在 1s 和 -1s 之间交替，并且条目的总和为 1。例如，每个置换矩阵都由有效向量组成，以及以下内容：

 0  1  0
 1 -1  1
 0  1  0

Distinct Entries：一个向量是有效的，如果它有不同的条目。这个特别烦人，因为该条件适用于行和列。

再次感谢所有看过这篇文章的人！

4

1 回答 1

3

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

随机抽样的一种定义是生成与从原始列分布随机生成矩阵然后只保留有效矩阵一样的分布。

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

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

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

于 2011-05-17T18:23:41.670 回答