Top to random eigenvalues.py
From Werner KRAUTH
| Revision as of 15:07, 6 June 2024 Werner (Talk | contribs) ← Previous diff |
Revision as of 19:24, 7 June 2024 Werner (Talk | contribs) Next diff → |
||
| Line 1: | Line 1: | ||
| ==Context== | ==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). | 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). | ||
| + | |||
| + | 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== | ==Python program== | ||
| Line 36: | Line 38: | ||
| stats[index] += 1 | stats[index] += 1 | ||
| print(stats) | 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. | ||
| + | |||
| + | ==Further information== | ||
| + | |||
| + | The | ||
| + | |||
| + | ==References== | ||
Revision as of 19:24, 7 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.
Further information
The
