这个问题的规则是相当具体的,因为我实际上正在查看 GLn 的一个子集 ,其中行向量和列向量必须具有某种形式(称这些向量为有效- 下面的示例),所以请多多包涵。以下是规则:
您可以随机均匀地选择一个长度为 n 的有效非零向量。
给定有效向量
v1, v2, ..., vk
,您可以使用函数确定它们形成的部分列是否是有效向量的前缀(例如,是否[v1_1 v2_1 ... vk_1]
作为有效向量的前 k 个条目出现)isPrefix
。给定有效向量 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:一个向量是有效的,如果它有不同的条目。这个特别烦人,因为该条件适用于行和列。
再次感谢所有看过这篇文章的人!