Spectral analysis of random-to-random Markov chains

DOI10.1016/J.AIM.2017.10.034MaRDI QIDQ1682003zbMATH OpenOpenAlexFDO

Authors A. B. Dieker, Franco Saliola

Publication date 28 November 2017

Published in Advances in Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.08580

zbMATH Keywords

spectrumrepresentation theorysymmetric groupdiscrete Markov chainrandom-to-random shuffling

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Probability measures on groups or semigroups, Fourier transforms, factorization (60B15)

Abstract: We compute the eigenvalues and eigenspaces of random-to-random Markov chains. We use a family of maps which reveal a remarkable recursive structure of the eigenspaces, yielding an explicit and effective construction of all eigenbases starting from bases of the kernels.

Recommendations

• On the spectral analysis of second-order Markov chains
• Spectral analysis of M/G/1 and G/M/1 type Markov chains
• Spectral Analysis, without Eigenvectors, for Markov Chains
• Spectral analysis of multi-dimensional self-similar Markov processes
• Spectral multipliers for Markov chains
• Spectral analysis of finite Markov chains with spherical symmetries
• The spectral method and ergodic theorems for general Markov chains

Cites work

• scientific article; zbMATH DE number 1601795 (Why is no real title available?)
• scientific article; zbMATH DE number 3647758 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 1210292 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 2042290 (Why is no real title available?)
• scientific article; zbMATH DE number 2070260 (Why is no real title available?)
• A Hodge decomposition for the complex of injective words.
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Combinatorial topology and the global dimension of algebras arising in combinatorics
• Descent classes of permutations with a given number of fixed points
• Descents of derangements and circular words
• Generating a random permutation with random transpositions
• Improved bounds for the mixing time of the random-to-random shuffle
• Interlacings for random walks on weighted graphs and the interchange process
• La correspondance de Robinson
• Mixing time of the card-cyclic-to-random shuffle
• On Lexicographically Shellable Posets
• Permutations, matrices, and generalized Young tableaux
• Probabilistic and combinatorial aspects of the card-cyclic to random insertion shuffle
• Proof of Aldous' spectral gap conjecture
• Random walks and hyperplane arrangements
• Refined estimates for some basic random walks on the symmetric and alternating groups
• Representation stability for cohomology of configuration spaces in \(\mathbb R^d\)
• Semigroups, rings, and Markov chains
• Spectra of symmetrized shuffling operators
• Spectral gap for random-to-random shuffling on linear extensions
• The combinatorics of the bar resolution in group cohomology
• The representation theory of the symmetric groups

Cited in

(21)

• Patterns in random permutations
• Cutoff for a one-sided transposition shuffle
• Cutoff for random to random card shuffle
• On the spectral analysis of second-order Markov chains
• Eigenvectors for a random walk on a hyperplane arrangement
• Spectral analysis of multi-dimensional self-similar Markov processes
• Spectrum of large random reversible Markov chains: two examples
• The eigenvalues of hyperoctahedral descent operators and applications to card-shuffling
• Eigenvalues of symmetrized shuffling operators
• Invariant theory for the free left-regular band and a \(q\)-analogue
• Note: random-to-front shuffles on trees
• Spectral analysis of finite Markov chains with spherical symmetries
• Spectral Analysis, without Eigenvectors, for Markov Chains
• The full spectrum of random walks on complete finite \(d\)-ary trees
• Total variation cutoff for the flip-transpose top with random shuffle
• Shuffling cards by spatial motion
• Rare event analysis of the state frequencies of a large number of Markov chains
• Cell complexes, poset topology and the representation theory of algebras arising in algebraic combinatorics and discrete geometry
• Spectral analysis of word statistics
• The one-sided cycle shuffles in the symmetric group algebra
• The symmetric group action on rank-selected posets of injective words

Describes a project that uses

Uses Software

• Sage-Combinat
• SageMath

This page was built for publication: Spectral analysis of random-to-random Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1682003)