Convergence of random walks on double transitive group generated by its permutational character

Keywords: probability, finite group, convergency, convolution

Abstract

Let $P$ be a probability on a finite group $G$, $U(g)=\frac{1}{|G|}$ the uniform (trivial) probability on the group $G$, $P^{(n)}=P *\ldots*P$ an $n$-fold convolution of $P$. A lot of estimates of the rate of the convergence $P^{(n)}\rightarrow U$ are found in different norms. It is well known conditions under which $P^{(n)}\rightarrow U$ if $n\rightarrow\infty$. Many papers are devoted to estimating the rate of this convergence for different norms. We consider finite groups that have a double transitive representation by substitutions and the probability that naturally arises in this image. This probability on each element of the group is proportional to the number of fixed (or stationary) points of this element, which is considered as a substitution. In other words, this probability is a character of the substitution representation of the group. A probability is called class if it takes the same values on each class of conjugate elements of a group, that is, it is a function of the class. The considered probability is class because any character of a group takes on the same values on conjugate elements. Any probability (and, in general, functions with values in an arbitrary ring) on a group can be associated with an element of the group algebra of this group over this ring. The class probability corresponds to an element of the center of this group algebra; that is why the class probability is also called central. On an abelian group, any probability is class (central).
In the paper convergence with respect to the norm $\|F\|=\sum\limits_{g\in G} |F(g)|$, where $F(g)$ is a function on group $G$, is considered. For the norm an exact formula not estimate only, as usual for rate of convergence of convolution $P^{(n)}\rightarrow U$ is given. It turns out that the norm of the difference $\|P^{(n)}-U\|$ is determined by the order of the group, degree the group as a substitution group, and the number of regular substitutions in the group. A substitution is called regular if it has no fixed points. Special cases are considered the symmetric group, the alternating group, the Zassenhaus group, and the Frobenius group of order $p(p-1)$ with the Frobenius core of order $p$ ($p$ is a prime number). A Zassenhaus group is a double transitive substitution group of a finite set in which only a trivial substitution leaves more than two elements of this set fixed.

Downloads

Download data is not yet available.

References

P. Diaconis, Group Representations in Probability and Statistics. Institute of Mathematical Statistics, 1988. - 198p.

L. Saloff-Coste, Random walks on finite groups. In Probability on Discrete Structures. H. Kesten (editor), Springer. - 2004. - P.263-340.

D.S. Passman, Permutation groups, Benjamin, 1968. - 310p.

M. Isaacs, Character theory of finite groups, AMS Chelsea. - 1976. - 303p.

Ya.G. Berkovich, E. M. Zhmud, Characters of Finite Groups, part 2, Fields Institute Communications (v. 181), 1999. - 332 p.

A.L. Vyshnevetskiy. Random walks on finite groups with conjugate class probability: algebraic approach, Visnyk of V.N.Karazin Kharkiv National University, Ser. ``Mathematics, Applied Mathematics and Mechanics, Vol.86, 2017. - P. 4-9. (in Russian)

H. Ryser, Combinatorial mathematics, N. Y. - 1963. - 154p.

Published
2019-05-30
Cited
How to Cite
Vyshnevetskiy, A. L. (2019). Convergence of random walks on double transitive group generated by its permutational character. Visnyk of V. N. Karazin Kharkiv National University. Ser. Mathematics, Applied Mathematics and Mechanics, 89, 4-9. https://doi.org/10.26565/2221-5646-2019-89-01
Section
Статті