Top to random eigenvalues.py
From Werner KRAUTH
| Revision as of 22:36, 8 June 2024 Werner (Talk | contribs) (→References) ← Previous diff |
Revision as of 22:36, 8 June 2024 Werner (Talk | contribs) (→References) Next diff → |
||
| Line 76: | Line 76: | ||
| ==References== | ==References== | ||
| - | Aldous D. and Persi Diaconis P., Shuffling Cards and Stopping Times, The American Mathematical Monthly 5, 333 (1986) | + | Aldous D. and Persi Diaconis P., Shuffling Cards and Stopping Times, The American Mathematical Monthly 5, 333 (1986) |
| Diaconis, P., Fill, J., and Pitman, J., Analysis of top to random shuffles. Combinatorics, Probability, and Computing (1992) 1, 135-155. | Diaconis, P., Fill, J., and Pitman, J., Analysis of top to random shuffles. Combinatorics, Probability, and Computing (1992) 1, 135-155. | ||
Revision as of 22:36, 8 June 2024
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).
In this example, I consider the transition matrix for the top-to-random shuffle discussed in Lecture 2. This N! x N! matrix has N distinct eigenvalues, and therefore huge degeneracies.
Python program
import numpy as np
import itertools
import scipy.linalg as la
def factorial(n):
return 1 if n == 0 else (0 if n == 0 else factorial(n - 1) * n)
for N in [2, 3, 4, 5, 6, 7]:
FacN = factorial(N)
ConfCopy = [0] * N
print(N, 'N', FacN)
#
# Setup of transition matrix
#
P = np.zeros((FacN, FacN))
Conf = [k for k in range(N)]
ConfList = list(itertools.permutations(Conf))
for Conf in ConfList:
i = ConfList.index(tuple(Conf))
ConfCopy[:] = Conf
a = ConfCopy.pop(0)
for k in range(N):
TargetConf = ConfCopy[0:k] + [a] + ConfCopy[k:N - 1]
j = ConfList.index(tuple(TargetConf))
P[i][j] = 1.0 / float(N)
eigvals, eigvecsl, eigvecsr = la.eig(P, left=True)
eigvals.sort()
stats = [0] * (N+1)
for a in eigvals:
index = int(N * a.real + 0.5)
stats[index] += 1
print(stats)
Output
2 N 2 [1, 0, 1]
3 N 6 [2, 3, 0, 1]
4 N 24 [9, 8, 6, 0, 1]
5 N 120 [44, 45, 20, 10, 0, 1]
6 N 720 [265, 264, 135, 40, 15, 0, 1]
For N=6, the output means that
the eigenvalue 1 is 1 times degenerate
the eigenvalue 1 - 1/N is 0 times degenerate
the eigenvalue 1 - 2/N is 15 times degenerate
the eigenvalue 1 - 3/N is 40 times degenerate, etc
The degeneracy of the second eigenvalue is thus n(n-1)/2.
NB: The number of cards in the deck is N, and the diameter of the transition matrix is N-1 (this is also computed by the program). The number of configurations is N!, in other words, it is huge.
Further information
The program Top_to_random_simul.py contains a Monte Carlo simulation of the top-to-random shuffle. It will output a deck with will be perfectly shuffled in the limit of infinite shuffling times.
Top_to_random_simul_stop.py performs a simulation with a stopping criterion: It will output a perfectly shuffled deck.
Top_to_random_TVD.py computes the total variation distance, starting from a single-permutation starting configuration at time t=0.
Finally, Top_to_random_TVD_Mix_Rel.py again computes the total variation distance, starting from a single-permutation starting configuration at time t=0, but it performs an analysis in terms of mixing and relaxation timesfor the small system sizes that are available to us.
References
Aldous D. and Persi Diaconis P., Shuffling Cards and Stopping Times, The American Mathematical Monthly 5, 333 (1986)
Diaconis, P., Fill, J., and Pitman, J., Analysis of top to random shuffles. Combinatorics, Probability, and Computing (1992) 1, 135-155.
