Spectral analysis of random-to-random Markov chains

DOI10.1016/J.AIM.2017.10.034zbMATH Open1405.60113arXiv1509.08580OpenAlexW2962995814MaRDI QIDQ1682003FDOQ1682003

A. B. Dieker, Franco Saliola

Publication date: 28 November 2017

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Permutations, matrices, and generalized Young tableaux
• Generating a random permutation with random transpositions
• The representation theory of the symmetric groups
• Title not available (Why is that?)
• La correspondance de Robinson
• Random walks and hyperplane arrangements
• On Lexicographically Shellable Posets
• Title not available (Why is that?)
• Refined estimates for some basic random walks on the symmetric and alternating groups
• Semigroups, rings, and Markov chains
• Proof of Aldous’ spectral gap conjecture
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Spectra of symmetrized shuffling operators
• A lower bound for the mixing time of the random-to-random insertions shuffle
• Title not available (Why is that?)
• A Hodge decomposition for the complex of injective words.
• Descent classes of permutations with a given number of fixed points
• Combinatorial topology and the global dimension of algebras arising in combinatorics
• Improved bounds for the mixing time of the random-to-random shuffle
• Descents of derangements and circular words
• The combinatorics of the bar resolution in group cohomology
• Title not available (Why is that?)
• Representation Stability for Cohomology of Configuration Spaces in ${\mathbb{R}}^d$
• Title not available (Why is that?)
• Mixing time of the card-cyclic-to-random shuffle
• Probabilistic and combinatorial aspects of the card‐cyclic to random insertion shuffle
• Spectral Gap for Random-to-Random Shuffling on Linear Extensions
• Interlacings for Random Walks on Weighted Graphs and the Interchange Process

Cited In (19)

• Cutoff for a one-sided transposition shuffle
• Cutoff for random to random card shuffle
• On the spectral analysis of second-order Markov chains
• 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
• Invariant theory for the free left-regular band and a \(q\)-analogue
• Eigenvalues of symmetrized shuffling operators
• Spectral Analysis, without Eigenvectors, for Markov Chains
• Spectral analysis of finite Markov chains with spherical symmetries
• Total variation cutoff for the flip-transpose top with random shuffle
• The full spectrum of random walks on complete finite \(d\)-ary trees
• 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
• Patterns in random permutations

Uses Software

• SageMath
• Sage-Combinat

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)