SSEP coupling.py
From Werner KRAUTH
| Revision as of 19:59, 12 June 2024 Werner (Talk | contribs) ← Previous diff |
Current revision Werner (Talk | contribs) (→Further information) |
||
| Line 1: | Line 1: | ||
| + | ==Context== | ||
| + | This page is part of my [[BegRohu_Lectures_2024|2024 Beg Rohu Lectures]] on "The second Markov chain revolution" at the [https://www.ipht.fr/Meetings/BegRohu2024/index.html Summer School] "Concepts and Methods of Statistical Physics" (3 - 15 June 2024). | ||
| + | |||
| + | The present program illustrates the coupling and, in particular, the phenomenon of monotone coupling in Markov chains in the example of the Symmetric Simple exclusion Process (SSEP) of NPart particles on the path graph of NSites sites without periodic boundary conditions. We start, at time t=0 with two configurations, one called ConfLow and another one, called ConfHigh, and runs the same Markov chain on both of them until they resulting configurations coincide (in both configurations, at each time step, we attempt to move the same particle in the same direction). In the output of our program, we check that this coupling time scales as N^3 log N. NB: There are no periodic boundary conditions, but to simplify the program, we use "phantom" vertex "-1" (containing "phantom particle "-1") and phantum vertex "NSites", with phantom particle "NPart". Only particles 0 to NPart-1, which can live on vertices 0,..., NSites-1, are "real". | ||
| + | |||
| + | ==Python program== | ||
| import math | import math | ||
| import random | import random | ||
| Ntrials = 100 | Ntrials = 100 | ||
| - | + | ||
| - | for NPart in [8, 16, 32, 64, 128]: | + | for NPart in [8, 16, 32, 64]: |
| NSites = 2 * NPart | NSites = 2 * NPart | ||
| Coupling = [] | Coupling = [] | ||
| for Iter in range(Ntrials): | for Iter in range(Ntrials): | ||
| - | ConfLow = {-1:-1, NPart: NSites}; ConfHigh = {-1:-1, NPart: NSites} | + | ConfLow = {-1: -1, NPart: NSites}; ConfHigh = {-1: -1, NPart: NSites} |
| for k in range(NPart): | for k in range(NPart): | ||
| ConfLow[k] = k | ConfLow[k] = k | ||
| Line 28: | Line 34: | ||
| print(NPart, sum(Coupling) / len(Coupling)) | print(NPart, sum(Coupling) / len(Coupling)) | ||
| - | + | Output of the above program (mean coupling time / (N^3 logN) | |
| - | 8 1.2698 | + | |
| - | 16 1.1993 | + | N t_coup / N^3 / log N |
| - | 32 1.1190 | + | 8 1.2698 |
| - | 64 1.1028 | + | 16 1.1993 |
| + | 32 1.1190 | ||
| + | 64 1.1028 | ||
| + | |||
| + | ==Further information== | ||
| + | |||
| + | This program can easily be adapted to the coupling-from-the-past approach to Markov-chain sampling introduced by Propp and Wilson in 1996, and then it allows one to obtain perfect samples of the Boltzmann distribution. It uses the concept of monotone coupling. When ConfLow and ConfHigh have coupled, ALL configurations have coupled also. | ||
| + | |||
| + | ==References== | ||
| + | * Propp J., Wilson D., Random Struct. Algorithms 9, 223 (1996) | ||
Current revision
Contents |
Context
This page is part of my 2024 Beg Rohu Lectures on "The second Markov chain revolution" at the Summer School "Concepts and Methods of Statistical Physics" (3 - 15 June 2024).
The present program illustrates the coupling and, in particular, the phenomenon of monotone coupling in Markov chains in the example of the Symmetric Simple exclusion Process (SSEP) of NPart particles on the path graph of NSites sites without periodic boundary conditions. We start, at time t=0 with two configurations, one called ConfLow and another one, called ConfHigh, and runs the same Markov chain on both of them until they resulting configurations coincide (in both configurations, at each time step, we attempt to move the same particle in the same direction). In the output of our program, we check that this coupling time scales as N^3 log N. NB: There are no periodic boundary conditions, but to simplify the program, we use "phantom" vertex "-1" (containing "phantom particle "-1") and phantum vertex "NSites", with phantom particle "NPart". Only particles 0 to NPart-1, which can live on vertices 0,..., NSites-1, are "real".
Python program
import math
import random
Ntrials = 100
for NPart in [8, 16, 32, 64]:
NSites = 2 * NPart
Coupling = []
for Iter in range(Ntrials):
ConfLow = {-1: -1, NPart: NSites}; ConfHigh = {-1: -1, NPart: NSites}
for k in range(NPart):
ConfLow[k] = k
ConfHigh[NPart - 1 - k] = NSites - 1 - k
iter = 0
while True:
iter += 1
Active = random.randint (0, NPart - 1)
sigma = random.choice([-1, 1])
if ConfLow[Active + sigma] != ConfLow[Active] + sigma: ConfLow[Active] += sigma
if ConfHigh[Active + sigma] != ConfHigh[Active] + sigma: ConfHigh[Active] += sigma
CLow = [ConfLow[k] for k in range(NPart)]
CHigh = [ConfHigh[k] for k in range(NPart)]
for k in range(NPart):
if CLow[k]> CHigh[k]: print(Error)
if ConfLow == ConfHigh:
Coupling.append(iter / NPart ** 3 / math.log(NPart))
break
print(NPart, sum(Coupling) / len(Coupling))
Output of the above program (mean coupling time / (N^3 logN)
N t_coup / N^3 / log N 8 1.2698 16 1.1993 32 1.1190 64 1.1028
Further information
This program can easily be adapted to the coupling-from-the-past approach to Markov-chain sampling introduced by Propp and Wilson in 1996, and then it allows one to obtain perfect samples of the Boltzmann distribution. It uses the concept of monotone coupling. When ConfLow and ConfHigh have coupled, ALL configurations have coupled also.
References
- Propp J., Wilson D., Random Struct. Algorithms 9, 223 (1996)
