Stopping circle.py

From Werner KRAUTH

Revision as of 22:12, 12 June 2024 Werner (Talk | contribs) ← Previous diff		Revision as of 22:51, 12 June 2024 Werner (Talk | contribs) Next diff →
Line 9:		Line 9:
	data = [0] * N		data = [0] * N
	for iter in range(N_trials):		for iter in range(N_trials):
-	NotVisited = set([k for k in range(N)])
	x = 0		x = 0
	if random.uniform(0.0, 1.0) < 1.0 / N:		if random.uniform(0.0, 1.0) < 1.0 / N:
Line 24:		Line 23:
	for k in range(N):		for k in range(N):
	print('site = ', k,' probability = ', data[k])		print('site = ', k,' probability = ', data[k])
		+
		+
		+	==Output==
		+
		+	Here is output of the above Python program
	site = 0 probability = 0.1673		site = 0 probability = 0.1673
Line 31:		Line 35:
	site = 4 probability = 0.1656		site = 4 probability = 0.1656
	site = 5 probability = 0.1696		site = 5 probability = 0.1696
		+
		+	==Further Information==
		+
		+	* What works like a charm for the random walk on the cycle fails for all other graphs except the complete graph (see Lovász and Winkler (1993).
		+	* The coupling from the path approach is much more robust.
		+
		+	==References==
		+
		+	* Lovász, L., Winkler, P., On the last new vertex visited by a random walk, J. Graph Theory 17, 593 (1993)

---

Revision as of 22:51, 12 June 2024

Contents 1 Context 2 Python program 3 Output 4 Further Information 5 References

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

Python program

import random
N_trials = 100000
N = 6
data = [0] * N
for iter in range(N_trials):
    x = 0
    if random.uniform(0.0, 1.0) < 1.0 / N:
        data[x] += 1.0 / N_trials
    else:
        NotVisited = set([k for k in range(N)])
        NotVisited.discard(x)
        while len(NotVisited) > 0:
            sigma = random.choice([-1, 1])
            x = (x + sigma) % N
            NotVisited.discard(x)
        data[x] += 1.0 / N_trials
print('stopping samples')
for k in range(N):
    print('site = ', k,' probability = ', data[k])

Output

Here is output of the above Python program

site =  0  probability =  0.1673
site =  1  probability =  0.1671
site =  2  probability =  0.1645
site =  3  probability =  0.1657
site =  4  probability =  0.1656
site =  5  probability =  0.1696

Further Information

• What works like a charm for the random walk on the cycle fails for all other graphs except the complete graph (see Lovász and Winkler (1993).
• The coupling from the path approach is much more robust.

References

• Lovász, L., Winkler, P., On the last new vertex visited by a random walk, J. Graph Theory 17, 593 (1993)