Random walks on finite groups converging after finite number of steps

Let P be a probability on a finite group G, P(n)=P∗…∗P (n times) be an n-fold convolution of P. If n→∞, then under mild conditions P(n) converges to the uniform probability U(g)=1|G| (g∈G). We study the case when the sequence P(n) reaches its limit U after finite number of steps: P(k)=P(k+1)=⋯=U for...

Full description

Saved in:

Bibliographic Details
Published in:	Algebra and Discrete Mathematics
Date:	2008
Main Authors:	Vyshnevetskiy, A.L., Zhmud, E.M.
Format:	Article
Language:	English
Published:	Інститут прикладної математики і механіки НАН України 2008
Online Access:	https://nasplib.isofts.kiev.ua/handle/123456789/153370
Tags:	Add Tag No Tags, Be the first to tag this record!
Journal Title:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Cite this:	Random walks on finite groups converging after finite number of steps / A.L. Vyshnevetskiy, E.M. Zhmud // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 2. — С. 123–129. — Бібліогр.: 3 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-153370
record_format	dspace
spelling	Vyshnevetskiy, A.L. Zhmud, E.M. 2019-06-14T03:38:17Z 2019-06-14T03:38:17Z 2008 Random walks on finite groups converging after finite number of steps / A.L. Vyshnevetskiy, E.M. Zhmud // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 2. — С. 123–129. — Бібліогр.: 3 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20P05, 60B15. https://nasplib.isofts.kiev.ua/handle/123456789/153370 Let P be a probability on a finite group G, P(n)=P∗…∗P (n times) be an n-fold convolution of P. If n→∞, then under mild conditions P(n) converges to the uniform probability U(g)=1\|G\| (g∈G). We study the case when the sequence P(n) reaches its limit U after finite number of steps: P(k)=P(k+1)=⋯=U for some k. Let Ω(G) be a set of the probabilities satisfying to that condition. Obviously, U∈Ω(G). We prove that Ω(G)≠U for ``almost all'' non-Abelian groups and describe the groups for which Ω(G)=U. If P∈Ω(G), then P(b)=U, where b is the maximal degree of irreducible complex representations of the group G. en Інститут прикладної математики і механіки НАН України Algebra and Discrete Mathematics Random walks on finite groups converging after finite number of steps Article published earlier
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
title	Random walks on finite groups converging after finite number of steps
spellingShingle	Random walks on finite groups converging after finite number of steps Vyshnevetskiy, A.L. Zhmud, E.M.
title_short	Random walks on finite groups converging after finite number of steps
title_full	Random walks on finite groups converging after finite number of steps
title_fullStr	Random walks on finite groups converging after finite number of steps
title_full_unstemmed	Random walks on finite groups converging after finite number of steps
title_sort	random walks on finite groups converging after finite number of steps
author	Vyshnevetskiy, A.L. Zhmud, E.M.
author_facet	Vyshnevetskiy, A.L. Zhmud, E.M.
publishDate	2008
language	English
container_title	Algebra and Discrete Mathematics
publisher	Інститут прикладної математики і механіки НАН України
format	Article
description	Let P be a probability on a finite group G, P(n)=P∗…∗P (n times) be an n-fold convolution of P. If n→∞, then under mild conditions P(n) converges to the uniform probability U(g)=1\|G\| (g∈G). We study the case when the sequence P(n) reaches its limit U after finite number of steps: P(k)=P(k+1)=⋯=U for some k. Let Ω(G) be a set of the probabilities satisfying to that condition. Obviously, U∈Ω(G). We prove that Ω(G)≠U for ``almost all'' non-Abelian groups and describe the groups for which Ω(G)=U. If P∈Ω(G), then P(b)=U, where b is the maximal degree of irreducible complex representations of the group G.
issn	1726-3255
url	https://nasplib.isofts.kiev.ua/handle/123456789/153370
citation_txt	Random walks on finite groups converging after finite number of steps / A.L. Vyshnevetskiy, E.M. Zhmud // Algebra and Discrete Mathematics. — 2008. — Vol. 7, № 2. — С. 123–129. — Бібліогр.: 3 назв. — англ.
work_keys_str_mv	AT vyshnevetskiyal randomwalksonfinitegroupsconvergingafterfinitenumberofsteps AT zhmudem randomwalksonfinitegroupsconvergingafterfinitenumberofsteps
first_indexed	2025-11-25T20:37:07Z
last_indexed	2025-11-25T20:37:07Z
_version_	1850526705378131968
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2008). pp. 123 – 129 c© Journal “Algebra and Discrete Mathematics” Random walks on finite groups converging after finite number of steps A.L. Vyshnevetskiy, E. M. Zhmud’ Communicated by B. V. Novikov Abstract. Let P be a probability on a finite group G, P (n) = P ∗ . . .∗P (n times) be an n-fold convolution of P . If n → ∞, then under mild conditions P (n) converges to the uniform probability U(g) = 1 \|G\| (g ∈ G). We study the case when the sequence P (n) reaches its limit U after finite number of steps: P (k) = P (k+1) = · · · = U for some k. Let Ω(G) be a set of the probabilities satisfying to that condition. Obviously, U ∈ Ω(G). We prove that Ω(G) 6= U for “almost all” non-Abelian groups and describe the groups for which Ω(G) = U . If P ∈ Ω(G), then P (b) = U , where b is the maximal degree of irreducible complex representations of the group G. Let G be a finite group, P be a probability on G, P (n) = P ∗ . . .∗P (n times) be an n-fold convolution of probability P . If n → ∞, then under well known conditions (see for example [1]), the sequence P (n) converges to the uniform probability U , where U(g) = 1 \|G\| (g ∈ G). In this paper we study the case when the sequence P (n) reaches its limit U after some finite number of steps: P (k) = P (k+1) = · · · = U (1) (k ∈ N where N is the set of natural numbers). The set Ω(G) of the probabilities satisfying (1) is not empty as U ∈ Ω(G). It turns out that probabilities from Ω(G) are tightly connected with nilpotent elements of the group algebra RG of the group G over the field R of real numbers and that such probabilities exist for “almost all" non-Abelian groups. 2000 Mathematics Subject Classification: 20P05, 60B15. Key words and phrases: random walks on groups, finite groups, group algebra. Jo u rn al A lg eb ra D is cr et e M at h .124 Random walks on finite groups The main result of the paper is the following. Theorem. For a finite group G the following conditions are equivalent: (a) Ω(G) = U ; (b) G is either an Abelian group or Hamiltonian 2-group, i.e. G = A×Q where A is an elementary Abelian 2-group, Q is the quaternion group of order 8; (c) The zero is the only nilpotent element of the algebra RG. 1. The set Ω(G) In what follows we write ∑ g instead of ∑ g∈G. The set F (G) of all functions G → R is an algebra over R with respect to operations of addition and convolution F1 ∗ F2(h) = ∑ g F1(hg−1)F2(g), F1, F2 ∈ F (G) A map ϕ : F → f = ∑ g F (g)g is an isomorphism of this algebra on the group algebra RG. We denote functions from F (G) by capital letters and their ϕ-images by corresponding small letters: if F ∈ F (G), then ϕ(F ) = f . For example, ϕ(U) = u = 1 \|G\| ∑ g g. A probability on G is a non-negative function P : G → R such that∑ g P (g) = 1. Let Π(G) be the set of all probabilities on a group G. For an arbitrary element x = ∑ g X(g)g ∈ RG we denote \|x\| = ∑ g X(g). If P ∈ Π(G), then \|p\| = 1. For any x, y ∈ RG we have \|x + y\| = \|x\| + \|y\|, \|x − y\| = \|x\| − \|y\| (2) As xu = ux = \|x\|u (3) and xyu = xyu2 = xu · yu, we have \|xy\| = \|x\| · \|y\| (4) Let Nil(A) be the set of all nilpotent elements of an arbitrary algeb- ra A. Lemma 1.1. \|x\| = 0 for each x ∈ Nil(A). Jo u rn al A lg eb ra D is cr et e M at h .A.L. Vyshnevetskiy, E. M. Zhmud’ 125 Proof. As xk = 0 for some k ∈ N, then 0 = \|xk\| = \|x\|k by (4), so \|x\| = 0. Lemma 1.2. If P ∈ Π(G) and x = p − u, then pn = xn + u for any n ∈ N. Proof. As \|x\| = \|p\| − \|u\| = 0, then by (3) xu = ux = 0. Under the binomial formula, pn = (x + u)n = xn + un = xn + u. Corollary 1.3. P ∈ Ω(G) if and only if x ∈ Nil(RG). Proof. P ∈ Ω(G) if and only if pn = u for the some n ∈ N. Theorem 1.4. If P ∈ Ω(G), then P (b) = U , where b is the maximal degree of irreducible representations of G over the field C of complex numbers. Proof. By Lemma 1.2 it is enough to prove that xb = 0, where x = p−u. For this purpose, in turn, it is enough to prove that Γ(xb) = 0 for any irreducible C-representation Γ of group G, extended by linearity to the group algebra CG. Let n be the degree of a representation Γ, F (t) be the characteristic polynomial of a matrix Γ(x). As degF (t) = n and matrix Γ(x) is nilpotent by Corollary 1.3, then F (t) = tn. By Hamilton-Cayley theorem (Γ(x))n = 0, and as n ≤ b, then Γ(xb) = (Γ(x))b = 0. The theorem is proved. If P ∈ Π(G), then P ∗ U = U . Therefore condition (1) is equivalent to P (n) = U for some n ∈ N. By Theorem 1.4 condition (1) for k = b holds for any probability P ∈ Ω(G). A function X on a group G is called a class function if X is constant on each class of conjugate elements of G. For a class function X its ϕ-image x is in the center Z(RG) of the algebra RG. Lemma 1.5. If P ∈ Ω(G) is a class function, then P = U . Proof. Let x = p − u. As p, u ∈ Z(RG), then x ∈ Z(RG). By Corollary 1.3 x ∈ Nil(RG), so xy ∈ Nil(RG) for any y ∈ RG. Therefore the principal ideal of algebra RG, generated by element x, is nilpotent. As RG is semisimple, then x = 0, i.e. P = U . For f ∈ RG and a ∈ R we write f ≥ a if F (g) ≥ a for any g ∈ G (we recall that F = ϕ−1(f), see the first paragraph of this section). Let N(G) = {x ∈ Nil(RG) \| x ≥ − 1 \|G\|}. Since Nil(RG) = {Rx \| x ∈ N(G)}, then Nil(RG) = {0} ⇔ N(G) = {0}. (5) Theorem 1.6. There is a bijection θ : N(G) → Ω(G). Jo u rn al A lg eb ra D is cr et e M at h .126 Random walks on finite groups Proof. For x ∈ N(G) we let θ1 : x → x + u. Then θ1(x) ≥ 0 by definition of N(G); by (2) and Lemma 1.1 \|θ1(x)\| = \|x\| + \|u\| = 1. Let θ = ϕ−1 · θ1 (composition of mappings); then θ(x) ∈ Π(G). Since x = θ1(x) − u ∈ Nil(RG), then by Corollary 1.3 θ(x) ∈ Ω(G). So θ(N(G)) ⊂ Ω(G). Since ϕ is a bijection and θ1 is an injection, then θ is an injection. Let P ∈ Ω(G) and x = p − u. By Corollary 1.3 x ∈ Nil(RG). Since p ≥ 0, then x ≥ − 1 \|G\| . So x ∈ N(G). Since p = θ1(x), then P = ϕ−1(p) = θ(x). So θ is a surjection. Thus θ is a bijection. The proof of Theorem 1.6 gives a way to obtain every probability of Ω(G): for x ∈ N(G) a function P = ϕ−1(x + u) is in Ω(G) and any P ∈ Ω(G) can be obtained this way. Now we name the groups we study. Definition. A group is called S-group if Ω(G) = {U}. 2. Description of S-groups Let Mn(K) be the algebra of all n × n matrices over a skew field K. Lemma 2.1. Nil(Mn(K)) = {0} if and only if n = 1, i.e. Mn(K) = K. Proof. If n = 1, then Mn(K) = K is a skew field, so Nil(Mn(K)) = {0}. If n > 1, matrix units Eij are nilpotent if i 6= j (Eij is a matrix which (i, j)-th element is 1 and others are 0). The following theorem is a key one. Theorem 2.2. The following conditions are equivalent: (a) G is a S-group; (b) Nil(RG) = {0}; (c) The algebra RG is an orthogonal direct sum of skew fields. Proof. (a) ⇔ (b). By definition, the statement (a) means that \|Ω(G)\| = 1. By Theorem 1.6 it is equivalent to \|N(G)\| = 1, i.e. N(G) = {0}. By (5) it means that Nil(RG) = {0}. (b) ⇔ (c). By Wedderburn’s theorem algebra RG decomposes into orthogonal direct sum of matrix algebras over skew fields. The equality Nil(RG) = {0} is equivalent to Nil(Mn(K)) = {0} for each of such algebras Mn(K), and by Lemma 2.1, to Mn(K) = K. Jo u rn al A lg eb ra D is cr et e M at h .A.L. Vyshnevetskiy, E. M. Zhmud’ 127 Note 2.3. For a S-group G let a skew field K be one of direct summands of RG (see point (c) of Theorem 2.2). As K is a finite-dimensional algebra over R, then by well known theorem of Frobenius ([2], p. 465), K is isomorphic either to field R, or to field C of complex numbers, or to quaternion skew field Q. Lemma 2.4. Subgroups of an S-group are S-groups. Proof. Let H be a subgroup of S-group G. By Theorem 2.2 we have Nil(RG) = {0}. As Nil(RH) ⊂ Nil(RG), then by Theorem 2.2 H is S-group. Let Z(G) be the center of G. Lemma 2.5. If x ∈ Nil(RG), then X(g) = 0 for any g ∈ Z(G). Proof. Let T be the regular representation of a group G, ρ be its character, extended by linearity on algebra RG. As ρ(g) = 0 (g 6= 1) and ρ(1) = \|G\|, then ρ(x) = ∑ g X(g)ρ(g) = X(1)\|G\| On the other hand, the matrix T (x) is nilpotent, so ρ(x) = tr (T (x)) = 0. Therefore X(1) = 0, and lemma is proved for special case g = 1. For proof in general case we let y = g−1x. Then y ∈ Nil(RG). By the above paragraph Y (1) = 0. As Y (1) = X(g), the proof is complete. Corollary 2.6. Abelian groups are S-groups. Proof. For an Abelian group G we have G = Z(G), so Nil(RG) = {0}. By Theorem 2.2, G is S-group. Another proof we obtain from Lemma 1.5, since any function on Abelian group is a class function. A non-Abelian group is called Hamiltonian if all its subgroups are normal. Lemma 2.7. ([3], p. 308). A group G is Hamiltonian if and only if G = N × A × Q, (6) where N is an Abelian group of odd order, A is an elementary Abelian 2-group, Q is the quaternion group of order 8. Let G be a Hamiltonian S-group. As its subgroup N is Abelian, then algebra RN decomposes into an orthogonal direct sum of fields: RN = Λ1 ⊕ . . . ⊕ Λr (7) Jo u rn al A lg eb ra D is cr et e M at h .128 Random walks on finite groups Lemma 2.8. We have (a) Λi ∼= R (i = 1, . . . , r); (b) G is a 2-group. Proof. (a) If statement (a) does not hold, then by note 2.3, Λi ∼= C for some i. The algebra RQ is an orthogonal direct sum of skew fields, and as the group Q is non-Abelian, then one of these skew fields (say, K) is isomorphic to the quaternion skew field Q. By (6) the algebra RQ contains an ideal I = Λi · K ∼= C ⊗ Q. As the ring C ⊗ Q is isomorphic to the full matrix ring M2(C) and Nil(M2(C)) 6= 0 (Lemma 2.1), then Nil(I) 6= 0 whence Nil(RG) 6= 0. As it contradicts to Theorem 2.2, the statement (a) is proved. (b) By (6) it is enough to prove that N = {1}. By (7), an arbitrary element g ∈ N has decomposition g = x1 + · · · + xr, where xi ∈ Λi (i = 1, . . . , r). Let n = \|N \|. Elements xi are mutually orthogonal, so 1 = gn = x1 n + · · · + xr n. As 1 = e1 + · · · + er, where ei is the unit of Λi, then xi n = ei (i = 1, . . . , r). Therefore xi is an element of finite order in the multiplicative group of the field Λi. As Λi ∼= R, then xi = ±ei (i = 1, . . . , r) and g2 = x1 2 + · · ·+ xr 2 = 1. But N is a group of odd order, so g = 1, therefore N = {1}. Theorem 2.9. The following conditions are equivalent: (a) G is a Hamiltonian 2-group; (b) G is a non-Abelian S-group. Proof. (a)⇒(b) Let G be a Hamiltonian 2-group. By Lemma 2.7 G = A × Q, therefore Z(G) = A × Z(Q). For any s ∈ G \ Z(G) we have s = at, where a ∈ A, t ∈ Q \Z(Q). So s2 = a2t2 = t2 = z, where z is the unique element of order 2 in group Q. Let y ∈ Nil(RG). If y 6= 0, then yn = 0, yn−1 6= 0 for the some n ∈ N. Let x = yn−1; then x2 = 0, x 6= 0. Therefore ∑ s X(s)X(s−1g) = 0 (8) for any g ∈ G. By Lemma 2.5 we can assume that in (8) s ∈ G \ Z(G) instead of s ∈ G. Then by above s2 = z. Substituting in (8) g = z we obtain ∑ s(X(s))2 = 0, whence X(s) = 0 for any s ∈ G\Z(G). Again by Lemma 2.5 X(s) = 0 for s ∈ Z(G), so X = 0 i.e. x = 0 — a contradiction. Therefore Nil(RG) = {0} and G is a S-group. Jo u rn al A lg eb ra D is cr et e M at h .A.L. Vyshnevetskiy, E. M. Zhmud’ 129 (b)⇒(a) Let G be a non-Abelian 2-group. For arbitrary elements g, s ∈ G we let ν = (g − 1)s(gn−1 + gn−2 + · · · + g + 1) ∈ RG where n is order of the element g ∈ G. Since (g − 1)(gn−1 + gn−2 + · · ·+ g+1) = gn−1 = 0, we have ν2 = 0. By Theorem 2.2 Nil(RG) = {0}, so ν = 0. As ν = gsgn−1 + · · ·+gs−sgn−1−· · ·−s, then gs = sgk for some k ∈ {0, 1, . . . , n − 1}. Therefore s−1gs = gk. So the subgroup generated by g is normal in G. It yields that each subgroup of G is normal, i.e. G is Hamiltonian. By the statement (b) of Lemma 2.8, G is a 2-group. Theorem is proved. As a consequence of Theorems 2.2 and 2.9 we obtain Theorem 2.10. For a finite group G the following conditions are equiv- alent: (a) Ω(G) = U ; (b) G is an Abelian group or a Hamiltonian 2-group; (c) The zero is the only nilpotent element of the algebra RG. References [1] Saloff-Coste L. Random walks on finite groups. In: Probability on Discrete struc- tures, H Kesten (editor), Springer, 2004. [2] Huppert B. Endliche Gruppen I. Springer-Verlag, Berlin, 1967. [3] Vinberg E.B. A course in algebra. AMS, Providence, 2003. Contact information A. L. Vyshnevetskiy Karazina st. 7/9, apt. 34, 61078, Kharkov, Ukraine E-Mail: alexwish@mail.ru

Random walks on finite groups converging after finite number of steps

Institution

Similar Items