Markov chains on hypercubes: Spectral representations and several majorization relations

DOI10.1002/RSA.3240040102MaRDI QIDQ4034706zbMATH OpenOpenAlexFDO

Authors Samuel Karlin, Bo Henry Lindqvist, Yi-Ching Yao

Publication date 16 May 1993

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1002/rsa.3240040102

zbMATH Keywords

Hamming distanceKronecker productsmajorization relationMarkov chains on hypercubesspectral representations

Mathematics Subject Classification ID

Combinatorial probability (60C05) Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20)

Recommendations

• Stratified random walks on then-cube
• Spectral properties of hypercubes with applications
• Exact solution for a class of random walk on the hypercube
• The rapid mixing of random walks defined by an \(n\)-cube
• Inequalities for the spectra of symmetric doubly stochastic matrices

Cites work

• A Multi-dimensional Linear Growth Birth and Death Process
• A Remark on Stirling's Formula
• Asymptotic analysis of a random walk on a hypercube with many dimensions
• Bounds on the cover time
• Ehrenfest urn models
• scientific article; zbMATH DE number 3145626 (Why is no real title available?)
• Inequalities: theory of majorization and its applications
• Lower bounds for covering times for reversible Markov chains and random walks on graphs
• Majorization, doubly stochastic matrices, and comparison of eigenvalues

Cited in

(5)

• Hypergraph Markov Operators, Eigenvalues and Approximation Algorithms
• Graph homomorphisms through random walks
• A divide and conquer approach to computing the mean first passage matrix for Markov chains via Perron complement reductions
• Distributions of values of indefinite forms and higher-order spectral estimates for finite Markov chains.
• On the inverse mean first passage matrix problem and the inverse \(M\)-matrix problem

This page was built for publication: Markov chains on hypercubes: Spectral representations and several majorization relations

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