Friday, November 1, 2013

Sharing network conjecture

My experiment was to start with a graph with every vertex having a value of 1 and numbered as follows:

The iterative step was to randomly pick a vertex and take a random amount from that vertex and give it to another vertex that the first was connected to. So the first step might be to take .753 from the bottom vertex and give it to the vertex to the top left. Where .753 is just a random amount from the value of the bottom vertex.  Then this step repeats on the new values for the vertices.
So I did 3 trials of repeating this step 10,000,000 times on the computer and calculating the average amount that each vertex had throughout the experiment.
Trial one Verices #1 through #6
[1.1518971995357796,
1.1570109780324331,
0.924463843491593,
0.6901779251616574,
0.923239128197964,
1.1532115255805495]
Trial two:
[1.1521431216043976,
1.1542216510411125,
0.9243974762519348,
0.6943663654748421,
0.9220785246649209,
1.1527934609628454]
Trial three:
[1.1496366397190037,
1.1542629725537692,
0.9252708248471094,
0.694030320080955,
0.9233941167266151,
1.1534057260733457]

My conjecture is that the expected value for each vertex V(n) after many iterations is:
V(n) = (n*(1+E(n)))/ (S+n)
Where E(n) is the number of edges connected to V(n) and S is the total number of edges and n is the number of vertices.
So the expected value for the vertices under this formula would be:
[1.1538461538461538,
1.1538461538461538,
0.9230769230769230,
0.6923076923076923,
0.9230769230769230,
1.1538461538461538]
This compares well to the experimental values.

I thought it was interesting that the expected value for a vertex only seems to depend on the number of vertices, the total number of edges, and the number of edges connecting to that vertex, and not on the way that the vertices are connected in the graph.