Involutive random walks on total orders and the anti-diagonal eigenvalue property

DOI10.1016/J.LAA.2022.01.018MaRDI QIDQ2669181zbMATH OpenOpenAlexFDO

Authors John R. Britnell, Mark Wildon

Publication date 9 March 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

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

zbMATH Keywords

anti-diagonal eigenvalue propertybinomial transformeigenvalueeigenvectorinvolutionrandom walkspectrum

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Random matrices (algebraic aspects) (15B52) Dynamical systems and their relations with probability theory and stochastic processes (37A50) Generation, random and stochastic difference and differential equations (37H10) Stationary stochastic processes (60G10) Sums of independent random variables; random walks (60G50) Discrete-time Markov processes on general state spaces (60J05)

Abstract: This paper studies a family of random walks defined on the finite ordinals using their order reversing involutions. Starting at $xin0,1,ldots,n-1$, an element $ylex$ is chosen according to a prescribed probability distribution, and the walk then steps to $n-1-y$. We show that under very mild assumptions these walks are irreducible, recurrent and ergodic. We then find the invariant distributions, eigenvalues and eigenvectors of a distinguished subfamily of walks whose transition matrices have the global anti-diagonal eigenvalue property studied in earlier work by Ochiai, Sasada, Shirai and Tsuboi. We prove that this subfamily of walks is characterised by their reversibility. As a corollary, we obtain the invariant distributions and rate of convergence of the random walk on the set of subsets of $1,ldots,m$ in which steps are taken alternately to subsets and supersets, each chosen equiprobably. We then consider analogously defined random walks on the real interval $[0,1]$ and use techniques from the theory of self adjoint compact operators on Hilbert spaces to prove analogues of the main results in the discrete case.

Recommendations

• A random walk on the symmetric group generated by random involutions
• Time reversal of random walks in \({\mathbb{R}}^ d\)
• scientific article; zbMATH DE number 4058559
• EIGENVALUES OF A RANDOM WALK ON ORIENTED MATROIDS
• Random Walks of Ordered Elements with Applications

Cites work

• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• scientific article; zbMATH DE number 193258 (Why is no real title available?)
• Reversibility and stochastic networks. With a new preface
• Symmetry Analysis of Reversible Markov Chains

Cited in

(1)

• A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffle

This page was built for publication: Involutive random walks on total orders and the anti-diagonal eigenvalue property

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