MARKOV-CHAINS ON HYPERCUBES - SPECTRAL REPRESENTATIONS AND SEVERAL MAJORIZATION RELATIONS

Various Markov chains on hypercubes L2n are considered and their spectral representations are presented in terms of Kronecker products. Special attention is given to random walks on the graphs J1(1 = 1, . . , n) where the vertex set is L2n and two vertices are connected if and only if their Hamming distance is at most l. It is shown that lambda(J1) > lambda(J1) > lambda(J(n-1)) > lambda(J(n)), l = 2, . . . , n - 2, where lambda (J1) is the spectrum of the random walk on J1 and > denotes the majorization ordering. A similar majorization relation is established for graphs V(l) where two vertices are connected if and only if their Hamming distance is exactly l. Some applications to mean hitting times of these random walks are given.