Random motion on finite rings. I: commutative rings

DOI10.1007/S10468-019-09864-WzbMATH Open1460.60075arXiv1605.05089OpenAlexW3100544352WikidataQ128490858 ScholiaQ128490858MaRDI QIDQ2188383FDOQ2188383

Authors: Yanyan Li 

Publication date: 11 June 2020

Published in: Algebras and Representation Theory (Search for Journal in Brave)

Abstract: We consider irreversible Markov chains on finite commutative rings randomly generated using both addition and multiplication. We restrict ourselves to the case where the addition is uniformly random and multiplication is arbitrary. We first prove formulas for eigenvalues and multiplicities of the transition matrices of these chains using the character theory of finite abelian groups. The examples of principal ideal rings (such as $mathbb{Z}_n$) and finite chain rings (such as $mathbb{Z}_{p^k}$) are particularly illuminating and are treated separately. We then prove a recursive formula for the stationary probabilities for any ring, and use it to prove explicit formulas for the probabilities for finite chain rings when multiplication is also uniformly random. Finally, we prove constant mixing time for our chains using coupling.

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

Recommendations

• Random walks on rings and modules
• Markov chains on finite fields with deterministic jumps
• Semigroups, rings, and Markov chains
• Speeding up Markov chains with deterministic jumps
• Unified theory for finite Markov chains

zbMATH Keywords

Markov chainsspectrummixing timesemigroup algebrasstationary distributionfinite chain ringsfinite commutative rings

Mathematics Subject Classification ID

Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Structure of finite commutative rings (13M05)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Title not available (Why is that?)
• Generating a random permutation with random transpositions
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Representation theory of finite monoids
• Finite chain rings
• Semigroups, rings, and Markov chains
• Eigenvalues of rank-one updated matrices with some applications
• Title not available (Why is that?)
• A combinatorial description of the spectrum for the Tsetlin library and its generalization to hyperplane arrangements
• Random walks arising in random number generation
• Generating random vectors in \((\mathbb Z/ p \mathbb Z)^d\) via an affine random process
• Concerning adjunctions to algebras
• The stationary distribution of an interesting Markov chain
• Möbius functions and semigroup representation theory. II: Character formulas and multiplicities.
• FINITE AUTOMATA AND MODELS OF SIMPLE FORMS OF BEHAVIOUR
• Random processes of the form \(X_{n+1}=a_ n X_ n+b_ n\pmod p\)
• Markov chains, \(\mathcal{R}\)-trivial monoids and representation theory
• Unified theory for finite Markov chains
• Generating uniform random vectors in \(\mathbb Z^k_p\): the general case
• Enumeration of finite commutative chain rings
• Asymptotic behavior of an affine random recursion in \(\mathbf Z_p^k\) defined by a matrix with an eigenvalue of size 1
• Title not available (Why is that?)
• Random walks on rings and modules
• Random motion on finite rings. I: commutative rings
• Mixing time and cutoff for a random walk on the ring of integers mod \(n\)

Cited In (6)

• Random walks on rings and modules
• Random motion on finite rings. I: commutative rings
• On generalized probability in finite commutative rings
• Title not available (Why is that?)
• Title not available (Why is that?)
• On relative commuting probability of finite rings

This page was built for publication: Random motion on finite rings. I: commutative rings

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