为什么这种随机生成图表的方式不公平?

我的目标是生成一个有向图,包含n个顶点,每个顶点都有一个边缘出来,并有一个边缘进来。我认为这样做的一种方法是将所有的顶点放在一个底池中,顶点轮流洗牌和拉出条目 – 例如,如果顶点1拉出顶点3,那么意味着将有一个从1到3的边缘。如果一个顶点从jar子中拉出来,它就把它放回去重新洗牌。 如果最后一个顶点发现底池只包含它自己,那么我们需要重新开始。 这是我的Kotlin代码:

fun generateGraph(n: Int): Map { val vertices : List = (1..n).toList() while (true) { val pot = vertices.toMutableList() val result = mutableMapOf() for (vertex in 1 until n) { do { java.util.Collections.shuffle(pot) } while (pot[0] == vertex) result.put(vertex, pot.removeAt(0)) } if (pot[0] != n) { result.put(n, pot.removeAt(0)) return result } else { // The last vertex left in the pot is also the last one unassigned. Try again... } } } 

这似乎工作。 然而,当我测试时,我发现它比其他图表出来更多。 当n是3时,唯一有效的图是循环

 {1=3, 2=1, 3=2} {1=2, 2=3, 3=1} 

但我发现第一次出现的次数是第二次的两倍:

 fun main(args: Array) { val n = 3 val patternCounts = mutableMapOf<Map, Int>() val trials = 10000 (1..trials).forEach({ val graph = generateGraph(n) patternCounts[graph] = patternCounts.getOrDefault(graph, 0) + 1 }) println(patternCounts) } 

刚刚打印的这个运行

 {{1=3, 2=1, 3=2}=6669, {1=2, 2=3, 3=1}=3331} 

我错过了什么? 而且,有没有办法让这个公平?

不难看出为什么会出现这种结果。 顶点1与顶点3的一半时间匹配。 如果发生这种情况,图形不能被拒绝,因为拒绝只发生在最后剩下的顶点是n (在这种情况下是3)并且该顶点已被使用。 所以有一半的时间你会得到{(1,3),(2,1),(3,2)}。

另外一半的时间,顶点1将与顶点2匹配,但是在顶点2与顶点1匹配之后,这些情况中的一半(即,总数的1/4)将被拒绝。因此{(1,2),( 2,3),(3,1)}将被选择四分之一的时间。

在剩余的季度,整个过程将重复,这意味着{(1,3),(2,1),(3,2)}将继续经常被选择两次。

一种解决方案是一旦匹配顶点与自身就立即拒绝整个图形。 在这种情况下,选择前无需重新洗牌; 如果图表被拒绝,你只能重新洗牌。

一般的问题是,匹配顶点与自身的情况并不独立于所有其他选择。 所以只是在一些比赛之后重新洗牌,而其他的则会导致偏见。

任何匹配后拒绝并重新启动可能不是最有效的解决方案,但它将起作用。 使算法更高效的一种方法是渐进式的洗牌,而不是整个洗牌,然后validation它。 另外一个可能性是在一个从数学堆栈交换这个问题引用的论文中描述的

我错过了什么? 而且,有没有办法让这个公平?

你错过的是你的algrothim是不公平的。

首先,你需要知道软件随机数发生器不是真正的随机数。 它总是使它看起来是公平的,不像真正的随机。

然后,考虑以下内容

 java.util.Collections.shuffle(pot) 

给你3个结果。

 1, 2, 3 1, 3, 2 2, 1, 3 2, 3, 1 3, 1, 2 3, 2, 1 

如果您删除您的待办事项条件,并且条件,所有结果都有相似的计数。

但是,你做,而条件防止位置=价值。 可能的结果是

 2, 1, 3 2, 3, 1 3, 1, 2 

请注意,结果的分布是不均匀的。 考虑以下:

 When vertex == 1: case pot[0] == 1: reroll case pot[0] == 2: continue // 50% case pot[0] == 3: continue // 50% If the result[0] == 2: When vertex == 2: case pot[0] == 1: continue // 25% case pot[0] == 3: continue // 25% If the result[0] == 3: When vertex == 2: case pot[0] == 1: continue // 50% case pot[0] == 2: reroll Result: 2, 1, 3 (25%) 2, 3, 1 (25%) 3, 1, 2 (50%) 

然后,if-condition DISCARD 2,1,3(不是与while循环不同的循环,它从头开始,剩下的结果是

  2, 3, 1 (25%) 3, 1, 2 (50%) 

(3, 1, 2):(2, 3, 1)约为2:1,与您的结果相符。

 fun generateGraph(n: Int): Map { val vertices : List = (1..n).toList() loop@ while (true) { val pot = vertices.toMutableList() val result = mutableMapOf() // No need to shuffle evey position java.util.Collections.shuffle(pot) for (vertex in 1..n) { val value = pot[vertex-1] // if position == value, always start from scratch if (value == vertex) continue@loop result.put(vertex, value) } return result } } 

此外,你应该提高你的数学概率和统计之前,你怀疑一个随机数发生器的数量分布。

    Interesting Posts