Weak lumping of left-invariant random walks on left cosets of finite groups
Preprint
Abstract
Let $G$ be a finite group and let $H$ be a subgroup of $G$. The left-invariant random walk driven by a probability measure $w$ on $G$ is the Markov chain in which from any state $x \in G$, the probability of stepping to $xg \in G$ is $w(g)$. The initial state is chosen randomly according to a given distribution. The walk is said to lump weakly on left cosets if the induced process on $G/H$ is a time-homogeneous Markov chain. We characterise all the initial distributions and weights $w$ such that the walk is irreducible and lumps weakly on left cosets, and determine all the possible transition matrices of the induced Markov chain. In the case where $H$ is abelian we refine our main results to give a necessary and sufficient condition for weak lumping by an explicit system of linear equations on $w$, organized by the double cosets $HxH$. As an application we consider shuffles of a deck of $n$ cards such that repeated observations of the top card form a Markov chain. Such shuffles include the random-to-top shuffle, and also, when the deck is started in a uniform random order, the top-to-random shuffle. We give a further family of examples in which our full theory of weak lumping is needed to verify that the top card sequence is Markov.
Keywords
All Related Versions
This publication has 13 references indexed in Scilit:
- A necessary and sufficient condition for double coset lumping of Markov chains on groups with an application to the random to top shuffleProceedings of the American Mathematical Society, 2024
- The Mathematics of Shuffling Cards2023
- Double coset Markov chainsForum of Mathematics, Sigma, 2023
- Bell numbers, partition moves and the eigenvalues of the random-to-top shuffle in Dynkin Types A, B and DJournal of Combinatorial Theory, Series A, 2017
- On the relations between Markov chain lumpability and reversibilityActa Informatica, 2016
- A rule of thumb for riffle shufflingThe Annals of Applied Probability, 2011
- Markov property for a function of a Markov chain: A linear algebra approachLinear Algebra and its Applications, 2005
- Character degrees and random walks in finite groups of Lie typeProceedings of the London Mathematical Society, 2004
- Analysis of Top To Random ShufflesCombinatorics, Probability and Computing, 1992
- Trailing the Dovetail Shuffle to its LairThe Annals of Applied Probability, 1992