Random motion on finite rings. I: commutative rings

DOI10.1007/S10468-019-09864-WMaRDI QIDQ2188383zbMATH OpenOpenAlexWikidataFDO

Authors Yanyan Li

Publication date 11 June 2020

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

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

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)

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.

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

Cites work

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

Cited in

(6)

• Random walks on rings and modules
• Random motion on finite rings. I: commutative rings
• On generalized probability in finite commutative rings
• scientific article; zbMATH DE number 3936061 (Why is no real title available?)
• scientific article; zbMATH DE number 3466276 (Why is no real title available?)
• 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)