49112

Why is this way of randomly generating a graph unfair?

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?

Answer1:

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

Answer2:

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

What you are missing is that <strong>your algrothim</strong> is unfair.

First, you need to know that software random number generator is not real random. It always make it seems to be fair, unlike real random.

Then, consider the following

java.util.Collections.shuffle(pot)

give you 3 outcomes.

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

If you remove your do-while condition and if condition, all of the outcome has similar count.

However, you do-while condition prevents position = value. The possible outcomes are

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

Note that the distribution of the outcomes are <strong>NOT</strong> even. Consider the following:

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%)

Then, the if-condition <strong>DISCARD</strong> 2, 1, 3 (Not rerolling which is different from while loop. It started from scratch again. The remaining outcomes are

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

(3, 1, 2):(2, 3, 1) is about 2:1 which matches your result.

<strong>Solution</strong>

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

Also, you should improve you math on probability and statistics before you doubt the number distribution of a random number generator.

Recommend

  • C# arrays use of unassigned local variable
  • Use of unassigned local variable (Object)
  • How to access multiple website using different bindings on IIS 7.5
  • converting date time to string
  • Need explanation on a angular direcive load
  • What happens when application pool re-cycles in ASP.NET MVC?
  • Add chart on phpoffice/phpword
  • How full does the old generation have to be to trigger a major GC cycle?
  • matplotlib issues when nan first in list
  • A Question about the .NET garbage collector when cyclic references exist
  • How to find specific subgraph in Neo4j using where clause
  • Collapsible Sankey Diagram - D3
  • UWP/C# - Issue with AQS and USB Devices
  • How to make JSON.NET deserialize to Microsoft Date Time?
  • Why use database factory in asp.net mvc?
  • Unable to decode certificate at client new X509Certificate2()
  • preg_replace Double Spaces to tab (\\t) at the beginning of a line
  • one Local Olampyad Questions on Informatic in 2011
  • Atlas images wrong size on iPad iOS 9
  • ImageMagick, replace semi-transparent white with opaque white
  • NetLogo BehaviorSpace - Measure runs using reporters
  • Apache 2.4 and php-fpm does not trigger apache http basic auth for php pages
  • Finding past revisions of files in StarTeam w/ .NET SDK / C#
  • output of program is not same as passed argument
  • Cross-Platform Protobuf Serialization
  • sending/ receiving email in Java
  • ActionScript 2 vs ActionScript 3 performance
  • Release, debug version and Authorization Google?
  • Akka Routing: Reply's send to router ends up as dead letters
  • R: gsub and capture
  • jqPlot EnhancedLegendRenderer plugin does not toggle series for Pie charts
  • Is there a mandatory requirement to switch app.yaml?
  • How to format a variable of double type
  • Comma separated Values
  • coudnt use logback because of log4j
  • unknown Exception android
  • JaxB to read class hierarchy
  • Checking variable from a different class in C#
  • java string with new operator and a literal
  • How to load view controller without button in storyboard?