markov

Markov Chain Monte Carlo Project

• Free software: MIT license
• Documentation: https://markov.readthedocs.io.

How to use

• run the code /markov/markov.py
• the input parameters are steps (istep), weights related parameters T and r (T, r), total nodes number (m), the nodes location in the 2-D grid (init.coor([_,_,…], [_,_,…]))
• the code generates a m*m 2D grid, origin is 0, dx=dy=1. For example, if m=3, meaning we have 3 nodes and a 3*3 grid. We can initialize the nodes by init.coor([2,1,1],[1,0,1]). The first, second, and third nodes are located at (2,1), (1,0), (1,1), respectively.

Features

• This is a Markov Chain Monte Carlo code to estimate the graphs that arise in a distribution network. The Markov Chain is a sequence of graphs. We do not know the transition probability matrix, but we can compute the relative probability of two graphs. See more description in problem_description.
• The code employs Metropolis-Hastings Algorithm
• The proposal probability is based on randomly cutting/adding an edge. There are three cases, ‘no cut’ case, ‘no add’ case and normal case.

1. ‘no cut’ case. If the graph is disconnected by further cutting any edges, it is the so called ‘no cut’ case. Thus, the probability of adding an edge is 1.

1. P(j|i)=1/(total possible edges - edges already exist).
2. We need to cut an edge to go back to previous graph. After adding an edge, if it becomes ‘no add’ case, P(i|j)=1/(existing edges - edges cannot be cut). After adding an edge, if it is a normal case, P(i|j)=0.5/(existing edges - edges cannot be cut)

2. ‘no add’ case. If the graph cannot add any more edges, it is ‘no add’ case. The probability of removing an edge is 1.

1. P(j|i)=1/(existing edges - edges cannot be removed)
2. We need to add an edge to go back to previous graph. After cutting, if it becomes cannot cut case, P(i|j)=1/(total possible edges - edges already exist). If it’s normal case, P(i|j)=1/(total possible edges - existing edges).

3. Normal case. The probability of adding or removing is 0.5.

If add an edge, P(j|i)=1/(total possible edges - existing edges). If cut an edge, P(j|i)=1/(existing edges - edges cannot be removed) The calculation of P(i|j) is similar to previous cases.

Sample results

• parameters

1. 5 nodes; m=5
2. r=2, T=10
3. total steps; istep=30000
4. initial nodes position (0,0) (1,2) (1,3) (3,2) (4,4); init.coord([0,1,1,3,4],[0,2,3,2,4])

• results

1. 2 most possible graphs: graph1 and graph2
2. expected number of edges connected to vertex 0 is 1.97
3. expected number of edges is 4.96
4. expected maximum distance is 6.64
5. this shows time series of averaged quantities

Credits

This package was created with Cookiecutter and the audreyr/cookiecutter-pypackage project template.