为什么这种随机生成图的方式不公平？ [英] Why is this way of randomly generating a graph unfair?

问题描述

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

  fun generateGraph（n：Int）：Map< Int，Int> {
 val顶点：列表< Int> =（1..n）.toList（）
 while（true）{
 val pot = vertices.toMutableList（）
 val result = mutableMapOf< Int，Int>（）
（顶点在1到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））
返回结果
} 
 else {
 //锅中剩下的最后一个顶点也是未分配的最后一个顶点。再试... 
} 
} 
} 
  

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

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

第一次出现的次数是第二次的两倍：

  fun main（args：Array< String>）{
 val n = 3 
 val patternCounts = mutableMapOf< Map< Int，Int>，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）}将继续被选择两次。

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

一般的问题是，将顶点与自身匹配的情况并不独立于所有其他选择。所以只是在某些比赛结束后重新洗牌，并在其他比赛结束后拒绝。

在任何比赛结束后拒绝并重新开始可能不是最有效的解决方案，但它会起作用。使算法更有效的一种方法是渐进式洗牌，而不是整个洗牌，然后验证它。另一种可能性在这个关于数学堆栈交换的问题中引用的论文中有描述

My aim is to generate a directed graph of n vertices such that each vertex has an edge going out and an edge coming in. I thought one way of doing this would be to put all the vertices in a pot and for the vertices to take turns shuffling it and pulling out entries -- so for example if vertex 1 pulls out vertex 3 then that means there will be an edge going from 1 to 3. If a vertex pulls itself out of the pot, it just puts it back and reshuffles. If at the end, the last vertex finds that the pot only contains itself, then we need to start over. Here's my Kotlin code:

fun generateGraph(n: Int): Map<Int, Int> {
    val vertices : List<Int> = (1..n).toList()
    while (true) {
        val pot = vertices.toMutableList()
        val result = mutableMapOf<Int, Int>()
        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...
        }
    }
}

It seems to work. However when testing I'm finding it comes out with some graphs more than others. When n is 3 the only valid graphs are the cycles

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

but I'm finding the first comes up twice as many times as the second:

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

A run of this just now printed

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

What am I missing? And, is there a way to make this fair?

解决方案

It's not difficult to see why that result occurs. Vertex 1 is matched with vertex 3 half the time. If that happens, the graph cannot be rejected because rejection only happens when the last remaining vertex is n (3 in this case) and that vertex has been used. So half the time you will get {(1,3), (2,1), (3,2)}.

The other half of the time, vertex 1 will be matched with vertex 2, but then half of those cases (i.e ¼ of the total) will be rejected after vertex 2 is matched with vertex 1. So {(1,2), (2,3), (3,1)} will be chosen a quarter of the time.

In the remaining quarter, the whole procedure will be repeated, which means that {(1,3), (2,1), (3,2)} will continue to be chosen twice as often.

One solution is to reject the entire graph as soon as you match a vertex with itself. In this case, there is no need to reshuffle before selecting; you only reshuffle if the graph is rejected.

The general problem is that the case of matching a vertex with itself is not independent of all the other choices. So just reshuffling after certain matches and rejecting after other ones leads to a bias.

Rejecting and restarting after any match might not be the most efficient solution, but it will work. One way to make the algorithm more efficient would be to shuffle incrementally, rather than doing the entire shuffle and then validating it. Another possibility is described in a paper referenced from this question on Mathematics Stack Exchange

这篇关于为什么这种随机生成图的方式不公平？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！