.PH ""
.ds HP 11 11 11 11 11 11 11
.nr Pt 1
.fp 4 GS
.EQ
delim $$
ndefine ciplus % "\o'O+'" %
define xun % bold x %
define vun % bold v %
tdefine ciplus % "\o'\(pl\(ci'" %
define jun % bold j %
tdefine scrG % font 4 size +2 G %
ndefine scrG % G under %
tdefine scrA % font 4 size +2 A %
ndefine scrA % A under %
tdefine scrC % font 4 size +2 C %
ndefine scrC % C under %
define bmember % "\o'\(sp\h'.2m'\v'+.35m'\(mi\v'-.35m''" %
tdefine CC % bold C %
ndefine CC % C under %
define =D % "\v'.3m'\z=\v'-.6m'\h'.3m'\s-1D\s+1\v'.3m'" %
.EN
.am DE
.ls 2
.sp
..
.nr Eq 1
.ce 99
.S 12
.B
RANDOM SHUFFLES AND GROUP REPRESENTATIONS
.S 10
.sp
.I
L. Flatto
A. M. Odlyzko
.R
.sp
AT&T Bell Laboratories
Murray Hill, NJ  07974
.sp
.I
D. B. Wales
.sp
.R
California Institute of Technology
Pasadena, CA  91125
.sp 1.5
.I
ABSTRACT
.R
.sp
.ce 0
.P
This paper considers random walks on a finite
group $G$, in which the probability of going from
$x$ to $yx$, $x,y~member~G$, depends
only on $y$.
The main results concern the distribution of the number
of steps it takes to reach a particular element of
$G$ if one starts with the uniform distribution on
$G$.
These results answer some random sorting questions.
They are attained by applications of group
representation theory.
.bp
.ce
.B
RANDOM SHUFFLES AND GROUP REPRESENTATIONS
.sp 2
.R
.H 1 "Introduction"
.ls 2
This paper was motivated by the following
question raised by some of our colleagues
about random sortings.
.PH "''- \\\\nP -''"
.nr P 1
Suppose we are given a randomly permuted
deck of cards, and we keep shuffling it
by choosing two cards at random and interchanging
them.
What is the expected number of shuffles until
the deck is fully sorted?
Does this number change appreciably if
instead of interchanging two random cards, we
always interchange the top card with a card
drawn at random from the following ones?
Our results answer both of these questions.
It turns out that if $n$ denotes the number
of cards, then for both variants of the problem,
the expected number of shuffles is close to
$n!$, but that it is larger for the
second variant where we always interchange
the top card with a random card.
More precisely, in the first problem the expected
number of shuffles is
.DS 2
.EQ (1.1)
n! ~+~ 2(n-2)! ~+~ o((n-2)!) ~~~roman {as} ~~n ~->~ inf~,
.EN
.DE
while in the second problem it is
.DS 2
.EQ (1.2)
n! ~+~ (n-1)! ~+~ o ((n-1)!) ~~~roman {as} ~~n ~->~ inf~.
.EN
.DE
.P
We consider the shuffling problem as a special
instance of random walks on finite groups.
Let $G$ be a finite group with a measure $mu$
which induces the random walk moving from $x$
to $yx$ with probability $mu (y)$ for all
$x,y ~member~ G$.
Assume that the support $OMEGA$ of $mu$,\ $OMEGA ~=~
"{" x member G:~ mu (x) ~>~ 0 "}"$,
generates $G$.
This entails no loss of generality, for
if $OMEGA$ generates a proper subgroup
$H$ of $G$, then the random walk is confined to
a single right coset of $H$ in $G$ and we
can instead consider the random walk on $H$.
We study $T$, which is the number of steps
the random walk takes to reach the identity
element $e$ of $G$, if the starting point of
the walk is uniformly distributed on $G$.
(We choose $e$ for convenience; obviously
the distribution of $T$ remains the same if $e$ is
replaced by any other element of G).
We obtain a formula, involving the irreducible
representations of $G$, for the generating
function of $T$ (Theorem\ 4.1).
.P
While the formulas of Theorem\ 4.1 are very general,
they are not sufficiently simple to yield results about
the expectation and distribution of $T$ in case of
arbitrary walks.
However, these formulas simplify significantly
(Theorem\ 4.2) when $mu$ is constant on conjugacy
classes, i.e. $mu (xyx sup -1 ) ~=~ mu (y)$ for all
$x,~y ~member~ G$.
The first variant of our shuffling problem corresponds
to this case.
Here $G$ is the symmetric group $S sub n$ and
$mu ((ij))~=~1/ ( pile {n above 2} )$,
$1~<=~i~<~j~<=~n$,
$mu (x) ~=~ 0$ for all other $x member G$.
Thus $mu$ is constant on the conjugacy class of
transpositions, and Theorem\ 4.2 applies directly.
.P
In the second variant of the random shuffling
problem, $G$ is also $S sub n$ but now
$mu ((jn)) ~=~ 1 over n-1 , ~ 1 ~<=~ j ~<=~ n-1$,
and $mu (x) ~=~ 0$ for all other $x member G$, so
that $mu$ is not constant on conjugacy classes.
Still, the formulas of Theorem\ 4.1 can be simplified,
using results from the representation theory of the
symmetric group.
What makes this possible is the fact that the set
of transpositions $(jn), ~ 1 ~<=~ j ~<=~ n-1$, is
invariant under conjugation by elements of the
symmetric group $S sub {n-1}$ on the $n-1$ letters
$1,...,n-1$.
In general, one can hope that methods similar to
ours will work whenever
$mu$
is invariant under conjugation by elements of
a large subgroup of $S sub n$.
.P
We shall use the formulas of Theorem\ 4.2 to obtain limit
laws for $T$ as $n-> inf$, when $G~=~S sub n$ and $mu$ is
uniformly concentrated on a fixed conjugacy class $C$, i.e. the
$p$-cycles ($p ~>=~ 2$) of $C$ are independent of $n$.
We show in Theorem\ 5.3 that
in this case
.DS 2
.EQ (1.3)
E(T) ~=~ n! ~+~ n! over |C| ~+~ o left ( n! over |C| right ) ~
~~~~roman {as} ~~n ~->~ inf~,
.EN
.sp 2
.EQ (1.4)
lim from {n -> inf} ~
P(T ~>=~ tn!) ~=~ e sup -t ,~~~ t ~>=~ 0~.
.EN
.DE
.P
These results extend readily to the case
where $mu$ is concentrated on several
conjugacy classes, uniformly over each
class.
They also extend to random walks on the
alternating group $A sub n$ (Theorem\ 5.4).
Finally, they can sometimes be extended
to cases where $mu$ is not constant on
conjugacy classes.
For example, we show that they hold for the
second variant of the shuffling problem
(Theorem\ 5.6).
The laws
(1.3), (1.4) do not hold universally.
In Section\ 6 we give examples of random
walks on abelian groups where the limit
laws for $T$ are quite different from those
of (1.3), (1.4).
.P
The theory of group representations
enters into our problem as follows.
Let $T sub x$, $x member G$, be the number
of steps taken by the walk starting
at $x$ to reach $e$.
Let $f(x,z)$ and $f(z) ~=~ 1 over |G| ~ sum from {x member G} ~
f(x,z)$ be respectively the generating
functions of $T sub x$ and $T$.
The definition of the random walk leads
to a convolution equation for $f(x,z)$
with respect to the variable $x$.
The theory of group representations allows
us to take a "Fourier transform" of this equation,
converting as usual convolution into multiplication.
Using the "inverse Fourier transform", we obtain
formulas for $f(x,z)$ and $f(z)$.
Detailed knowledge of the irreducible
representations of $S sub n$ enables us to
deduce the limit law for $T sub x$ and $T$ from the
formulas for $f(x,z)$ and $f(z)$.
.P
The idea of applying group representations
to shuffling problems is mentioned in [8,12],
where various other applications to
probability and statistics are given.
Closely related to our paper are
those of Good [11], and Diaconis
and Shahshahani [9].
Good
[11] deals with
random walks on finite Abelian groups, in
which case the irreducible representations
are 1-dimensional and trivial to
compute.
In [9] the representation theory of $S sub n$ is used
to study the rate at which the distribution
of the product of $k$ random transpositions on $n$ letters tends
to the uniform distribution as $k -> inf$.
.P
Our results can be applied to some of
the problems studied by Diaconis and Shashahani [9].
In particular, as is shown in [8],
they lead to a simplification of the proof of the
main result of [9].
They also enable one to study the rate of convergence
to the uniform distribution of the random walk generated
by interchanging a random card with the top card [8].
.P
In this paper we show that the machinery
of group representations is capable of
producing very precise answers to certain
questions concerning random shufflings.
Less precise answers to such questions
can also be obtained by more standard
probabilistic methods [1,2].
In fact, the probabilistic methods occasionally
apply when our techniques do not.
As an example, we have not found a way
to use the formulas of Theorem\ 4.1 to obtain
a limit law for $T$ when $G~=~S sub n$ and $mu$ is
concentrated uniformly on the transpositions
($kappa , ~ kappa + 1)$, $1 ~<=~ kappa ~<=~ n-1$,
whereas it follows from [1,2] that $T$ becomes
exponentially distributed as $n -> inf$.
.P
Random walks on groups are examples of Markov
chains, the transition probabilities given by
$p(x,y) ~=~ mu (yx sup -1 )$, $x, ~y member G$.
In general, one can consider any finite irreducible
chain (we use the term irreducible to
mean that any state may be reached from
any other one in a finite number of steps with positive probability) and
study the expected number $N$ of steps required
to move from one state to another averaged
over all pairs of states.
This problem has been investigated extensively
by Aleliunas et al. [3] and Mazo [15].
Mazo shows that $N ~>=~ n over 2$, $n$ being
the number of states, equality holding if and only if the
chain consists of consecutive points on a circle and
one moves deterministically from one point to
the next.
Simple examples show that no upper bound for $N$
exists (see\ Section\ 7).
Upper bounds are known [3,15] in the
case of a random walk on an undirected graph $scrG$ with
$n$ nodes, the walk moving from any node to all
those connected to it with equal probability.
In this case
.DS 2
.EQ (1.5)
n-1 ~<=~ N ~=~ O(n sup {3} )~,
.EN
.DE
the lower bound being attained
if and only if $  scrG$ is the complete graph
on $n$ nodes.
An example is
given in [15] which shows that the best possible exponent
is $3$.
.P
These results apply directly to random
walks on finite groups.
In this case $E(T) ~=~ n-1 over n ~ N$,
where $n ~=~ |G|$.
(The presence of the term $n-1 over n$ is
explained in section\ 7.)
Thus $E(T) ~>=~ n-1 over 2$, equality holding
if and only if $G$ is cyclic and $mu (g) ~=~ 1$
for some generator $g$ of $G$.
Furthermore, we conclude from (1.5) that
if $mu (x) ~=~ mu (x sup -1 )$, $x member G$,
and $mu$ constant on its support, then
$E (T) ~>=~ {(n-1) sup 2} over n$.
In Section\ 7, we modify Mazo's argument
to yield $E(T) ~=~ O (n sup 2 )$
in this case.
The exponent 2 is best possible, since for
simple random walk on a cyclic group of
order n, $E(T) ~wig~ n sup 2 over 6$ (Theorem\ 6.1).
.P
The plan of this paper is as follows.
In Section\ 2 we give a brief review of general
results in the theory of group representations
required in this paper.
This is followed in Section\ 3 with a description of
the irreducible representations and characters of $S sub n$.
In Section\ 4 we derive formulas for the generating
functions of $T sub x$ and $T$.
These are used in Section\ 5 to derive limit laws
for $T sub x$ and $T$.
In Section\ 6, we obtain limit laws for $T$ on
certain Abelian groups in order to illustrate
how different the behavior can be then as compared to the
random  walks considered on $S sub n$ and $A sub n$.
Finally, in Section\ 7, we view random walks
on groups as Markov chains to obtain bounds
for $E(T)$ in terms of $|G|$.
.sp
Acknowledgment:\0\0We would like to thank
Larry Shepp, Jim Mazo, and Kenneth Baclawski
for some helpful discussions.
In particular, K. Baclawski
brought to our attention the asymptotic
character formula for $S sub n$ derived by Wasserman in
his thesis [19].
.H 1 "Representations of Finite Groups"
We review those aspects of the representation
theory of finite groups needed in this paper.
In this section we present the general theory,
and in the next one the more detailed
theory of the symmetric group.
Our discussion is brief and we quote standard
results without proof.
For a comprehensive treatment the reader is
referred to [4,7,17] for the general theory
and to [4,14] for the theory of the symmetric
group.
For a somewhat slower paced presentation of
the theory, see [8].
.P
Let $G$ be a finite group.
$A$ representation
$rho$ of $G$ is a homeomorphism from $G$ into
the group of invertible linear maps of a finite dimensional complex
vector space $V$, which will be referred to as
a $G$-module.
The dimension $d sub rho$ of $V$ is called
the degree of $rho$.
Without loss of generality, we can consider
$rho ( x ) , ~ x member G$, to be $d sub rho ~times~ d sub rho$
unitary matrices.
A representation
$rho$ is said to irreducible
if and only if $ V$ has no proper subspace invariant
under all $rho ( x )$.
The 1-dimensional irreducible representation
$rho (x) ~=~ 1, ~ x member G$, is called the
identity representation and is denoted by 1.
Two representations $rho ,~ rho sup prime$ of
$G$ are said to be equivalent if and only if they are of
equal degree and there exists an invertible
$d sub rho ~times~ d sub rho$ matrix $M$ such that
$M rho (x) M sup -1 ~=~ rho prime (x) , ~
x member G$.
If $rho ,~ rho sup prime$ are equivalent representations
on the $G$-modules $V,~W$, then we express this
fact by $V ~=wig~ W$.
.P
The function
$ chi sub rho (x) ~=~ Tr~ rho (x)$
$=$ trace of $rho (x)$
is the character of
the representation $rho$.
A character
$chi sub rho$ is called
irreducible whenever $rho$ is.
If $rho sup prime (x) ~=~ M rho (x) M sup -1$,
then $chi sub rho sup prime (x) ~=~ chi sub rho (x)$;
i.e., equivalent representations have the same character.
If $x$ and $y$ are conjugate elements in $G$
(i.e. $y ~=~ a x a sup -1$ for some $a member G$),
then $chi sub rho (y) ~=~ Tr [ rho (a) rho (x) rho sup -1 (a)]
~=~ chi sub rho (x)$.
Thus $chi sub rho$ is constant on conjugacy classes.
We define $chi sub rho (C) ~=~ chi sub rho (x)$, $x member C$,
for any conjugacy class $C$.
.P
Let $scrC$ be the set of conjugacy classes of
$G$ and
$G hat$ a complete set of inequivalent irreducible
representations of $G$.
.sp
.I
Theorem 2.1.
If $delta sub st$ denotes the Kronecker symbol,
which equals 1 for $s~=~t$ and is 0 otherwise,
then
.DS 3
.EQ
~mark roman i)~~ | scrC | ~=~ | G hat |~,
.EN
.sp
.EQ (2.1)
~lineup roman ii)~~ 1 over {| G |} ~
sum from { C  member scrC} ~ | C | ~
chi sub rho (C) chi bar sub {rho prime} ~(C) ~=~
delta sub {rho rho prime} ,~~~ rho ,~ rho sup prime ~member~ G hat~,
.EN
.sp
.EQ (2.2)
lineup roman iii)~~ 1 over { | G |} ~ sum from
{rho member {G hat}} ~ chi sub rho (C) ~ chi bar sub {rho} (C prime )
~=~ {delta sub { C  C prime}} over { | C | } ,~~~C,C sup prime ~member~ scrC~.
.EN
.DE
.R
.P
Equations
ii), iii) are the
orthogonality relations for characters.
Equation
ii) implies
that inequivalent irreducible representations
have distinct characters.
As a special case of iii), let $C ~=~ C sup prime ~=~ "{" e "}"$.
Then
$ chi sub rho (e) ~=~ d sub rho$,
and iii) becomes
.DS 2
.EQ (2.3)
sum from {rho member G hat} ~ d sub rho sup 2 ~=~
| G |~.
.EN
.DE
.P
Let $scrA ~=~ scrA~ (G)$ be the set of formal
sums $f ~=~ sum from {x member G} ~ f (x) x$,
$f(x)$ any complex valued function on $G$.
For $lambda$ complex and $f, ~ g member scrA (G)$
define:
.DS 2
.EQ
lambda f ~=~ sum from {x member G} ~ lambda f (x) x ,~~~
f+g ~=~ sum from {x member G} ~ [ f(x) + g(x)] x ,~~~
fg ~=~ sum from {x member G}~ [ f star g ] (x) x~,
.EN
.DE
where $[f star g] (x) ~=~ sum from {y member G} ~
f(xy sup -1 ) g (y) $.
$f star g$ is called the
convolution of $f$ and $g$ and $scrA~ (G)$
the group algebra of $G$.
Any representation of $G$ extends uniquely to
$scrA (G)$ by letting $rho (f) ~=~ sum from {x member G} ~
f(x) rho (x)$.
We have
.DS 2
.EQ
rho ( lambda f ) ~=~ lambda rho (f),~~~
rho (f + g) ~=~ rho (f) + rho (g),~~~
rho (fg) ~=~ rho (f) rho (g)~.
.EN
.DE
Let $f hat ( rho ) ~=~ rho (f), ~ rho ~member~ G hat $.
Then
$f hat$
is a function on $G hat$ and is called the
Fourier transform of $f$.
We have
.DS 2
.EQ (2.4)
{f * g} ~ ( rho ) ~=~ f hat ( rho ) 
g hat ( rho ) ,~~ ~ rho ~member~ G hat~,
.EN
.DE
so that the Fourier transform converts convolution
into multiplication.
We recover $f$ from $f hat$ by
the following result.
.sp
.I
Theorem 2.2.
(Inversion Formula)
.R
.DS 2
.EQ (2.5)
f(x) ~=~ 1 over { | G |} ~ sum from {rho member G hat} ~
d sub rho ~ Tr ~ [ f hat ( rho ) rho ( x sup -1 ) ] ,
~~~ x ~member~ G~.
.EN
.DE
.P
Let $f(x)$ be a class function on $G$, so that $f$ is
constant on conjugacy classes.
Let $f(C) ~=~ f(x),~ x ~member~ C$.
In this case $f hat $ simplifies to
the following.
.sp
.I
Theorem 2.3.
If $I sub rho$ is the identity $d sub rho ~times~d sub rho$
matrix and $f$ is constant on conjugacy classes, then
.DS 2
.EQ (2.6)
f hat ( rho ) ~=~ 1 over {d sub rho} ~
[ sum from {C member scrC} ~
| C | ~ f (C) chi sub rho (C) ] ~cdot~ I sub rho~.
.EN
.DE
Proof:
.R
.R
$f hat ( rho ) ~=~ sum from {C member scrC} ~
f(C) ~ rho (C)$, where $rho (C) ~=~ sum from {x member C}
~ rho (x)$.
We have
.DS 2
.EQ (2.7)
rho sup -1 (y) rho (C) rho (y) ~=~ sum from {x member C}
~ rho (y sup -1 xy ) ~=~ rho (C) ,~~ ~ y ~member~ G~,
.EN
.DE
so that $rho (C)$ commutes with $rho (y),~ y ~member~ G$.
As $rho$ is irreducible, we conclude from
Schur's lemma that $rho (C) ~=~ lambda sub C I sub rho$,
$lambda sub C$ a complex number.
Taking traces we obtain
.DS 2
.EQ (2.8)
Tr ~ rho ( C ) ~=~ | C | chi sub rho ( C ) ~=~ lambda sub rho
d sub rho~,
.EN
.DE
which proves (2.6).
.H 1 "Representations of the Symmetric Group"
Let $G ~=~ S sub n$, the symmetric group on $n$
letters, $1 ~<=~ n ~<~ inf$.
We describe $scrC$ and $G hat$ by setting up one-to-one
correspondences between each of these sets and the
set $P sub n$ of partitions of $n$.
.P
The partitions of $n$ are designated by
$lambda ~=~ ( lambda sub 1 , "..." , lambda sub m )$,
where $lambda sub 1 ~>=~ lambda sub 2 ~>=~ ".." ~>=~ lambda sub m$
is a sequence of positive integers with
$n ~=~ lambda sub 1 ~+~ ".." ~+~ lambda sub m$.
The $lambda sub i$'s are named the parts of
$lambda$, and $n ~=~ | lambda |$ the weight of $lambda$.
We also use the notation
$lambda ~=~ (1 sup {a sub 1} 2 sup {a sub 2} ".." n sup {a sub n} )$
to mean that there are $a sub j$ parts equalling $j$.
.P
The partition $lambda$ of $n$ gives rise to the
conjugacy class $C sub lambda$ consisting of those
elements in $S sub n$ with cyclic decomposition
$( kappa sub 1 kappa sub 2 ".." kappa sub {lambda sub 1} )$
$( kappa sub {lambda sub 1 + 1} ".." kappa sub
{lambda sub 1 + lambda sub 2} ) "..."
( kappa sub {lambda sub 1 + "..." +  lambda sub m-1 +1} "..." kappa sub n )$,
where $kappa sub 1 , kappa sub 2 , ".." , kappa sub n$
is a permutation of $1, 2, ".." ,n$.
(In practice, one
only writes down the cycles of length $>= ~2$.)
The correspondence $lambda~ -> ~C sub lambda$ is one-to-one
from $P sub n$ onto $scrC$.
If $lambda ~=~ (1 sup {a sub 1} 2 sup {a sub 2} .. n sup {a sub n} )$, then
.DS 2
.EQ (3.1)
| C sub lambda | ~=~ n! over {1 sup {a sub 1} a sub 1 !
2 sup {a sub 2} a sub 2 ! ".." n sup {a sub n} a sub n !}
~.
.EN
.DE
For example, if $a sub 1 ~=~ n -2 ,~ a sub 2 ~=~ 1$, and all other
$a sub i ~=~ 0$, then $C sub lambda$ is the class of
transpositions and $| C sub lambda | ~=~ {n(n-1)} over 2$.
.P
To obtain the correspondence $P sub n ~->~ G hat$, we define
the Specht modules $S sup lambda$.
We require several concepts.
The Young diagram of $lambda$
is the diagram, the first row of which contains $lambda sub 1$
squares, the second row $lambda sub 2$ squares, etc.
To illustrate, the diagram of (5,3,1,1) is given in
figure 1i).
We denote the diagram of $lambda$ by $[ lambda ]$.
.DS 
.TS
center;
l2 | l| l| l| l| l| c c c c c c | l2 | l| l| l| l
l2 | l | l | l | l | l | c c c c c c | l2 | l | l | l | l
l2 | l | l | l | l l c c c c c c | l2 | l | l l l
l2 | l | l l l c c c c c c l2 | l | l | l l l
l2 | l | l l l c c c c c c l2 | l | l l l l
l2 l l l l c c c c c c l2 | l | l l l l.
	_	_	_	_	_							_	_	_	_
.sp 1.5
	_	_	_	_	_							_	_	_	_
.sp
i)	_	_	_								ii)	_	_
.sp 1
	_											_	_
.sp 1.5
	_											_
.sp 1.5
												_
.TE
.sp
.ce
Figure 1.
.DE
.P
The squares are coordinatized by $(i,j)$,
$i$ indicating the row counted from top to
bottom, and $j$ the column counted from
left to right.
$A$ $lambda$-tableau $t$ is any
of the $n!$ arrays of integers obtained by
inserting $1, ".." ,n$ into the $n$ squares of
[$lambda$].
Two tableaux
$t sub 1$ and $t sub 2$ are called
equivalent if $t sub 2$ is obtained from
$t sub 1$ by permuting elements in each row of
$t sub 1$.
The set of tableaux equivalent to a given tableau $t$
is called a $lambda$-tabloid and is designated by
{$t$}.
For any $pi ~member~ S sub n$, let $rho sub lambda ( pi ) t$
be the tableau obtained from $t$ by replacing each entry
$i$ by $pi (i)$, $1 ~<=~ i ~<=~ n$, and let
$rho sub lambda ( pi ) "{" t "}" ~=~ "{" rho sub lambda ( pi ) t "}"$.
(The last definition can be checked to be
independent of the representative $t$.)
.P
Let $M sup lambda$ be the vector space
over $"\o'C\s5\(br'"$ spanned by the $lambda -$ tabloids,
and extend the action of $S sub n$ to $M sup lambda$
by linearity.
$M sup lambda$ is an $S sub n$-module and
contains the irreducible submodule $S sup lambda$
defined as follows.
For any tableau $t$, let $C sub t$ be the subgroup
of $S sub n$ consisting of the column permutations
of $t$.
Let $roman sgn ~pi$ be 1 if $pi$ is even and $-1$ if $pi$
is odd.
Then
$e sub t ~=~ sum from {pi member C sub t} ~
( roman sgn ~ pi ) ~cdot~ rho sub lambda ( pi ) "{" t "}"$
is called a $lambda$-polytabloid.
The linear span of all polytabloids is an irreducible
$S sub n$-module.
It is the Specht module corresponding to $lambda$
and is designated by $S sup lambda$.
From now on, when speaking of $rho sub lambda$, we
mean its restriction to $S sup lambda$.
Then
$lambda ~-> ~rho sub lambda$ is the desired 1-1 correspondence
from $P sub n$ onto $G hat$ [13].
In the sequel, we shall write
$d sub lambda ,~ chi sub lambda$, etc. for $d sub rho sub lambda$,
$ chi sub rho sub lambda$, etc.
.P
As simple illustrations, let $lambda ~=~ (n),~ (1 sup n )$.
It follows from the
definition that
$S sup (n)$,
$S sup {(1 sup n )}$
are 1-dimensional spaces spanned respectively by
$e sub {1 "..." n}$,
$e sub {(1 "..." n ) sup tr}$, and
.DS 2
.EQ
rho sub (n) ~( pi ) ~=~ 1 ,~~ ~ rho sub {(1 sup n )} ( pi ) ~=~
roman sgn ~pi ,~~~ pi ~member~ S sub n~.
.EN
.DE
$rho sub (n)$ and $rho sub {(1 sup n )}$ are respectively
the identity and alternating representations of $S sub n$.
.P
Let $A sub n$ be the alternating subgroup of $S sub n$.
We show how the sets $scrC , G hat$ for $A sub n$ can
be obtained from the corresponding sets for $S sub n$.
For any partition $lambda$, the conjugate partition $lambda sup prime$
is defined to be the one whose diagram $[ lambda sup prime ]$ is
the transpose of $[ lambda ]$.
For example, if $lambda ~=~ (5,3,1,1)$, then
$lambda sup prime ~=~ (4,2,2,1,1)$.
(See figure 1ii.)
We call a conjugacy class of $S sub n$ even (odd) if
all its members are even (odd) permutations.
.sp
.I
Theorem 3.1.
i) The even conjugacy classes of $S sub n$ remain
conjugacy classes of $A sub n$, except for those whose
cyclic decomposition consists of cycles of distinct
odd lengths, in which case the class decomposes
into two classes of equal size.
Call the former classes undivided and the latter
divided.
.P
ii) if $lambda ~!=~ lambda sup prime$, then the restrictions
of $rho sub lambda$, $rho sub {lambda sup prime}$ to $A sub n$
are equivalent irreducible representations.
If $lambda ~=~ lambda sup prime$, then $rho sub lambda$
decomposes, when restricted to $A sub n$, into two inequivalent
irreducible representations $rho sub {lambda 1} ,~ rho sub {lambda 2}$
of $A sub n$.
The above gives a complete set of inequivalent irreducible
representations of $A sub n$.
.nr Eq 1
.DS 2
.EQ iii)
chi sub {lambda prime} (x) ~=~ left {
matrix {
rcol {- chi sub lambda (x) , above chi sub lambda (x) ,}
rcol { x~ roman {odd ~,} above x~ roman {even~.}}
}
.EN
.DE
iv)\0\0Let $lambda ~=~ lambda sup prime$ and $C$
an even undivided class.
Let $chi sub {lambda 1}$, $chi sub {lambda 2}$ be
the characters of $rho sub {lambda 1}$,
$rho sub {lambda 2}$.
Then
.DS 2
.EQ
chi sub {lambda 1} (C) ~=~ chi sub {lambda 2} (C) ~=~
{chi sub lambda (C)} over 2~.
.EN
.DE
.R
.P
We remark that $chi sub {lambda j} (C) ,~ j ~=~ 1,2$,
can also be computed when $C$ is a divided
class [4, p. 208], but we do not require these
values in this paper.
The dimensions of the Specht modules may be computed
in the following way.
.sp
.ul
Definition 1:
A tableau
$t$ is standard if and only if its entries increase
along rows and columns.
.sp
.I
Theorem 3.2.
The $e sub t$'s, $t$ varying over standard
$lambda$-tableaux, form a basis for $S sup lambda$.
Thus $d sub lambda$ equals the number of standard
$lambda$-tableaux.
.sp
Corollary 1:
Let $| lambda | ~=~ n$, $1 ~<=~~ j ~<=~ n$.
Then
.DS 2
.EQ (3.2)
sum from {| lambda | =n , lambda sub 1 = j}~
d sub lambda sup 2~<=~
( pile {n above j} ) sup 2 (n-j)!
~,
.EN
.DE
which implies
.DS 2
.EQ (3.3)
d sub lambda sup 2~<=~
( pile {n above lambda sub 1} ) sup 2
(n- lambda sub 1 ) !
~.
.EN
.DE
Proof:
.R
Let $lambda ~=~ (j,~ lambda sub 2 , "..." , lambda sub m ) $.
Then
$lambda * ~=~ ( lambda sub 2 , ".." , lambda sub m )$
is a partition of $n-j$ with $lambda sub 2 ~<=~ j$.
The first row of a standard $lambda$-tableau for which
$| lambda | ~=~ n$ and $lambda sub 1 ~=~ j$ can be chosen in
at most
$( pile {n above j} )$ ways.
Having chosen the first row, the remaining part of the
$lambda$-tableau can be chosen in at most
$d sub {lambda *}$ ways.
Hence
.DS 2
.EQ (3.4)
d sub lambda~<=~
( pile {n above j} ) d sub {lambda *}
~.
.EN
.DE
By (2.3)
.DS 2
.EQ (3.5)
sum from {| lambda | = n ,~ lambda sub 1 = j} ~
d sub lambda sup 2~<=~
( pile {n above j} ) sup 2~
sum from {lambda *}~
d sub {lambda *} sup 2~<=~
( pile {n above j} ) sup 2
(n-j)!
~.
.EN
.DE
.I
Corollary 2:
Let $0 ~<~ a ~<~ 1$ be such that $an$ is an integer.
Then
.DS 2
.EQ (3.6)
sum from {| lambda | = n ,~ lambda sub 1 >  an}
~ d sub lambda sup 2 ~<=~ n! left ( 4 over {(1-a) sup a n sup a}
right ) sup n
~.
.EN
.DE
Proof:
.R
We have
.DS 2
.EQ
sum from j=0 to n~
( pile {n above j} ) sup 2~<=~
[
sum from j=0 to n~
( pile {n above j} ) ] sup 2~=~4 sup n~.
.EN
.DE
Hence, by Corollary 1,
.DS 2
.EQ (3.7)
sum from {| lambda | =n, lambda sub 1 > an} ~
d sub lambda sup 2 ~<=~ sum from {an<j <= n} ~
( pile {n above j} ) sup 2 (n-j)!~<=~(n-an)!
4 sup n ~=~ n! 4 sup n {(n-an)!} over n! ~<=~
{n!4 sup n} over {(n-an) sup an}
.EN
.DE
.P
We state two methods for computing the irreducible
characters of $S sub n$.
.sp
.ul
Definition 2:
Let $[ lambda ]$ contain $s$ squares along its
diagonal.
Let $a sub i~=~lambda sub i -i$,
$b sub i~=~lambda sub i sup prime -i$,
$1~<=~i~<=~s$.
The $a sub i$'s and $b sub i$'s are called
the Frobenius coordinates of $lambda$ and we write
$lambda ~=~ left ( 
pile { a sub 1 "..." a sub s above b sub 1 "..." b sub s }
right )$
.P
For instance, if $lambda ~=~ (5,3,1,1)$ then
$lambda ~=~ left (
pile { 4 ~~~ 1 above 3 ~~~ 0 }
right )$.
.sp
.ul
Definition 3:
A $p$-staircase in $[ lambda ]$ is a collection
of $p$ squares $S sub 1 ,  "..." , S sub p$ in $[ lambda ]$
such that: i) $S sub j$ and $S sub j+1$, $1 ~<=~ j ~<=~ p-1$,
are contiguous with $S sub j+1$ either to the right or to
the top of $S sub j$, ii) $S sub 1$ is at the bottom
end of its column and $S sub p$ is at the right
end of its row.
The sign of the staircase is $+1$ if it spans an
odd number of rows and $-1$ otherwise.
.sp
.ul
Definition\ 4:\0
For any [$lambda$] and any element
$gamma ~member~ G$, let
.DS 3
.EQ
r sub lambda ( gamma ) ~=~
{chi sub lambda ( gamma )} over {d sub lambda} ~.
.EN
.DE
.sp
.I
Theorem 3.3.
(Frobenius [10]) Let $gamma$ be a $p$-cycle,
$p ~>=~ 2$, and $lambda ~=~ left (
pile { a sub 1 "..." a sub s above b sub 1 "..." b sub s }
right )$.
Let $x sub i ~=~ a sub i ~+~ 1 over 2$, $y sub i ~=~
b sub i ~+~ 1 over 2$, $F (x) ~=~ prod from 1=1 to s ~
x+y sub i over x-x sub i $.
Then $r sub lambda ( gamma )$
is the coefficient of $1 over x$ in the expansion of
.DS 2
.EQ (3.8)
- {(x+ 1 over 2 ) . . . (x+p- 1 over 2 )} over
{p.| lambda | . . . . ( | lambda | - p + 1 )} ~cdot~
{F(x+p)} over F(x)
.EN
.DE
in descending powers of $x$.
.sp
Theorem\ 3.4.
(Murnaghan \(em Nakayama rule [14]).
Let $gamma ~=~ ( gamma * ) ~cdot~
(p)$ be the disjoint product of
$gamma *$ and a $p$-cycle.
Then
.DS 2
.EQ (3.9)
chi sub lambda ( gamma ) ~=~ sum from {lambda *} ~+-~ chi sub {lambda *}
( gamma * )
~,
.EN
.DE
the summation extending over all $[ lambda * ]$
obtained by stripping a $p$-staircase from
$[ lambda ]$ and $+-$ being the sign of the
removed staircase.
.R
.P
Theorems\ 3.3, 3.4 yield exact formulas for the
irreducible characters of $S sub n$.
(See [13] for
some examples.)
Unfortunately, these formulas become progressively more
cumbersome as the number of cycles and their lengths
increase.
We shall make use in Section\ 5 of the following
asymptotic character formula derived by Wasserman
in his thesis [19].
.sp
.I
Theorem 3.5.
Let $gamma$ be a permutation of $1, ".." ,m$ with
$gamma sub 2$ 2-cycles, $gamma sub 3$ 3-cycles, etc;
thus $gamma$ may be considered an element of $S sub n$
for $n ~>=~ m$.
Let $ lambda ~=~ left (
pile {a sub 1 "..." a sub s above b sub 1 "..." b sub s }
right )$, $alpha sub i ~=~ {a sub i + 1 over 2} over
{| lambda |}$, $beta sub i ~=~ {b sub i + 1 over 2} over {| lambda | }$,
$1 ~<=~ i ~<=~ s$.
Then
.DS 2
.EQ (3.10)
r sub lambda ( gamma ) ~=~ prod from {p ~>=~ 2} ~
( sum from i=1 to s ~ [ alpha sub i sup p ~-~
(- beta sub i ) sup p ] ) sup {gamma sub p} ~+~
O left ( 1 over {| lambda |} right )
.EN
.DE
where the constant in $O left ( 1 over {| lambda |} right )$
depends only on $gamma$.
.br
Proof:
.R
We reproduce the proof of [17].
Consider first the case where $gamma$
is a $p$-cycle.
Let $F(x)$ be defined as in Theorem\ 3.3.
We have
for $| x |$ sufficiently large
.DS 2
.EQ (3.11)
roman {log}~ F(x) ~=~ sum from 1=1 to s ~
left [ roman {log} ~ left ( 1 ~+~ y sub i over x right ) ~-~
roman {log} left ( 1-^ x sub i over x right ) right ] ~=~
sum from n=1 to inf ~ s sub n over nx sup n ~,
.EN
.DE
where
.DS 2
.EQ
s sub n ~=~ sum from 1=1 to s ~
[ x sub i sup n - (-y sub i ) sup n ]~.
.EN
.DE
Hence
for $| x |$ sufficiently large
.DS 2
.EQ (3.12)
F(x+p) over F(x) ~=~ roman {exp} ~
left { sum from n=1 to inf ~ s sub n over nx sup n ~
left [ left ( 1 ~+~ p over x right ) sup -n -1 right ] right } ~=
.EN
.sp
.EQ
sum from k=0 to inf ~ 1 over k! left {
sum from n=1 to inf ~ {-ps sub n} over x sup n+1 ~
left [ 1-^ p(n+1) over 2x ~+~ ".." right ] right } sup k ~.
.EN
.DE
.P
We use (3.12) to obtain the Laurent expansion
of $g(x) ~=~ x left ( x ~+~ 1 over 2 right ) ".." left ( x+p -^1 over 2 right ) ~
F(x+p) over F(x)$ for large $| x |$.
Define the weight of any monomial in the
$s sub n$'s to be its degree when considered as a
polynomial in the $x sub i$'s and $y sub i$'s.
The coefficient of $x sup -1$ in the expansion
of $g(x)$ is a polynomial in the $s sub n$'s, and
the unique monomial of highest weight
appearing in it is $-ps sub p$.
Since
.DS 2
.EQ
| s sub n | ~<=~ sum from 1=1 to s ~(x sub i sup n + y sub i sup n ) ~<=~ 
[ sum from i=1 to s ~ (x sub i + y sub i ) ] sup n ~<=~
| lambda | sup n
~,
.EN
.DE
we conclude from Theorem\ 3.3 that
.DS 2
.EQ (3.13)
r sub lambda ( gamma ) ~=~
{s sub p + O ( | lambda | sup p-1 )} over
{| lambda | .... ( | lambda | -p+1)} ~=~
s sub p over {| lambda | sup p} ~+~ O left ( 1 over {| lambda |} right )
~=~ sum from i=1 to n ~ [ alpha sub i sup p - (- beta sub i ) sup p ]
~+~ O left ( {1 over {| lambda |}} right )
~,
.EN
.DE
the constant in $O left ( 1 over {| lambda |} right )$ depending only
on $p$.
.P
Next, let $gamma ~=~gamma *$.
$(p)$ be the
disjoint product of $gamma *$ and a $p$-cycle $(p)$.
Suppose (3.10) holds for $gamma *$.
Then one readily checks
.DS 2
.EQ (3.14)
r sub {lambda *} ( gamma * ) ~=~ r sub lambda ( gamma * )
~+~ O left ( 1 over { | lambda |} right )
~,
.EN
.DE
the constant in $O left ( {1 over { | lambda | }} right )$
depending only on $gamma *$ and hence only on $gamma$.
By (3.9) we have
.DS 2
.EQ (3.15)
r sub lambda ( gamma ) ~=~ sum from {lambda *} ~ +-~ r sub
{lambda *} ( gamma * ) {d sub {lambda *}} over d sub lambda
~,
.EN
.DE
which, for $gamma * ~=~ e$, becomes
.DS 2
.EQ (3.16)
r sub lambda ( gamma ) ~=~ sum from {lambda *} ~+-~
{d sub lambda *} over {d sub lambda}
~.
.EN
.DE
.P
Any standard $lambda *$-tableau can be extended to a
standard $lambda$-tableau by a suitable insertion
of $| lambda | -p+1, ".." , | lambda |$ in the removed
$p$-staircase.
Hence
.DS 2
.EQ (3.17)
sum from {lambda *} ~ d sub {lambda *} ~<=~ d sub lambda
~.
.EN
.DE
We conclude from (3.14)-(3.17)
that
.DS 2
.EQ (3.18)
r sub lambda ( gamma ) ~=~ r sub lambda ( gamma * ) ~
sum from {lambda *} ~+-~ d sub {lambda *} over d sub lambda ~+~
O left ( 1 over { {| lambda |} } right ) ~=~ r sub lambda ( gamma * ) ~
r sub lambda ((p)) ~+~ O left ( 1 over {| lambda |} right )
~,
.EN
.DE
and Theorem\ 3.5 follows by induction.
.P
Since
$rho sub lambda ( sum from {x member C} x )~=~
| C | r sub lambda I sub lambda$
(Theorem 2.3),
theorems\ 3.3 and 3.4 may be used to obtain the
eigenvalues of $rho sub lambda ~ ( sum from {x member C} x)$.
We obtain next the eigenvalues of $rho sub lambda ( sum from k=1 to n-1 ~
(kn))$.
.P
Let $[ lambda sup j ]$, $1 ~<=~ j ~<=~ s$, be the
set of diagrams derived from $[ lambda ]$ by removing one square,
with
$(i sub 1 , lambda sub {i sub 1} ) , ".." ,
( i sub s , lambda sub {i sub s} )$,
${i sub 1} ~<~ ".." ~<~ i sub s$, as the coordinates of the
removed squares.
Let $d sub j ~=~ roman dim ~ S sup {lambda sup j}$.
.sp
.I
Theorem\ 3.6.
(Branching Theorem [14]).
Let $S sub n-1$ be the subgroup of $S sub n$ which
fixes $n$.
Let $V sub 0 ~=~ 0$ and $V sub j$, $1 ~<=~ j ~<=~ s$,
be the span of the polytabloids $e sub t$, $t$ varying
over the standard $lambda$-tableaux with $n$
in any of the $i sub 1 -th , i sub 2 -th , "...",
i sub j - th$
rows.
Then $V sub j / V sub j-1 ~=wig~ S sup {lambda sup j}$,
$1 ~<=~ j ~<=~ s$.
.R
.P
We remark that, by Maschke's Theorem, we may choose
for each $j$ an $ S sub n-1$-module $W sub j$ such that
$V sub j ~=~ V sub j-1 ciplus W sub j$.
Hence we conclude from Theorem\ 3.6 that $S sup lambda ~=~
W sub 1 ciplus ".." ciplus W sub s$, where
$W sub j ~=wig~ S sup {lambda sup j}$.
Thus, $S sup lambda$ splits into a direct sum of
$S sub n-1 "-"$invariant subspaces.
.sp
.I
Theorem\ 3.7.
The eigenvalues of $rho sub lambda ( sum from k=1 to n-1
(kn))$ are $lambda sub {i sub j} - i sub j$ counted
with multiplicity $d sub j , ~ 1 ~<=~ j ~<=~ s$.
.sp
Proof:
.R
Let $sigma ~=~ sum from k=1 to n-1 ~ (kn)$.
Then $sigma x ~=~ x sigma$,
$x ~member~ S sub n-1$, and so
$rho sub lambda ( sigma ) rho sub lambda (x) ~=~
rho sub lambda ( x ) rho sub lambda ( sigma ) , ~ x ~member~ S sub n-1$.
For $w~member~ S sup lambda$, there exists a
unique decomposition $w ~=~ sum from {i =1} to s
~ w sub i ~roman with~ w sub i~member ~ W sub i $.
Let $pi sub i ( w) ~=~ w sub i$.
Then $pi sub i rho sub lambda  (x) ~=~
rho sub lambda (x) pi sub i$,
for all
$x ~member~ S sub n-1$ and $1 ~<=~ i ~<=~ s$,
which implies
.DS 2
.EQ (3.19)
pi sub i rho sub lambda ( sigma ) ~cdot~
rho sub lambda (x) ~=~ rho sub lambda (x) ~cdot~
pi sub i ~ rho sub lambda ( sigma ) ~,~~~
x ~member~ S sub n-1 ~ and~ { 1 ~<=~ i ~<=~ s}~.
.EN
.DE
Now
$rho sub lambda | sub {W sub i}$,
$rho sub lambda | sub {W sub j}$,
are inequivalent irreducible representations
of $S sub n-1$ for $i ~!=~ j$.
Applying both sides of (3.19) to vectors in
$W sub j$, we conclude from Schur's lemma
that $pi sub i rho sub lambda ( sigma )| sub {W sub j} ~=~ 0$
for $i ~!=~ j$;\0
i.e.
$rho sub lambda ( sigma )$ maps each $W sub j$ into
itself, and furthermore
.DS 2
.EQ (3.20)
rho sub lambda ( sigma ) | sub W sub j ~=~ mu sub j ~cdot~
roman { identity} ,~~~~~ mu sub j~ 
member~"\o'C\v'-.2'\s5\(br\v'.2''"~,
.EN
.DE
so that
$mu sub j$ is an eigenvalue of
$rho sub lambda ( sigma )$ with multiplicity
$d sub j$.
Let $t$ be a standard tableau with $n$ in the
$i sub j  -th$ row.
Then
.DS 2
.EQ (3.21)
rho sub lambda ( sigma ) e sub t ~=~ mu sub j e sub t ~+~
sum ~ alpha sub u e sub u
~,
.EN
.DE
the $alpha sub u$'s are complex numbers and the summation
extends over all standard $gamma$-tableaux having
$n$ in either of the $i sub 1 -th , ".." , i sub j-1 -th$
rows.
We prove that $mu sub j ~=~ lambda sub {i sub j} - i sub j$
by evaluating the coefficients of $"{" t "}"$ on both sides
of (3.21).
The one on the right is $mu sub j$.
This is so because $e sub t$ contains {$t$} with 
coefficient 1 and each tabloid contained in one
of the $e sub u$'s has $n$
appearing in the $i sub j-1 -th$ row or higher.
The left side of (3.21) equals
.DS 2
.EQ (3.22)
sum from k=1 to n-1 ~ rho sub lambda ((kn)) "{" t "}" ~+~
sum from k=1 to n-1 ~ sum from {pi member C sub t - "{" e "}"} ~
roman sgn ~pi~ ~cdot~ rho sub lambda ((kn) pi ) "{" t "}" ~=~
sum sub 1 + sum sub 2
~.
.EN
.DE
The {$t$}-coefficient of $SIGMA sub 1$ is
$lambda sub {i sub j} -1$ as
$rho sub lambda ((kn)) "{" t "}" ~=~ "{" t "}"$
if and only if $k$ is in $i sub j -th$ row,
and this occurs for $lambda sub {i sub j} - 1$
values of $k$.
Suppose that $pi ~member~ [ C sub t - "{" e "}" ]$
and $rho sub lambda ((kn) pi ) "{" t "}" ~=~ "{" t "}"$.
If there is an $i$ such that
$pi (i)~!=~i,k,n$,
then $(kn) pi (i) ~=~ pi (i)$.
Thus $rho sub lambda [ (kn) pi ]$ moves
$pi (i)$ out of the row in which it
occurs in $t$, and
$rho sub lambda ((kn) pi ) "{" t "}" ~!=~ "{" t "}"$.
Hence $pi ~=~ (kn)$.
As $pi ~member~ C sub t$, $k$ must be in the same
column as $n$.
We conclude that the {$t$}-coefficient of
$SIGMA sub 2 ~roman equals~ -(i sub j - 1 )$, hence the
{$t$}-coefficient of the left side of
(3.21)\ $roman is~ lambda sub i sub j - i sub j$.
.H 1 "Generating Functions of $fat {T sub x}$ \f3and T\f1"
We derive formulas for the generating functions of
$T sub x$ and $T$.
Recall that $T sub x$ is the random variable which
gives the number of steps for the random walk
starting at $x$ to hit the identity $e$, with
$T sub e ~=~ 0$.
Hence
.DS 3
.EQ
T ~=D~ 1 over {|^G^|} ~ sum from {x member G}~
T sub x
.EN
.DE
where $=D$ means that the two random variables have
identical distribution function.
.sp
.I
Lemma:
Let $G$ be a finite group and $mu$ a measure
on $G$ whose support $OMEGA$ generates $G$.
Then
$[ I sub rho - z mu hat ( rho ) ]$ is invertible if:
i) $|z| ~<~ 1$ and $rho$ is any representation,
or
ii) $z ~=~ 1$ and $rho ~!=~ 1$ is any irreducible representation.
.sp
Proof:
.R
If the matrix
$[I sub rho - z mu hat ( rho ) ]$ is not invertible then
$[I sub rho - z mu hat ( rho ) ] vun ~=~ 0$ for some vector $vun ~!=~ 0$.
Suppose the latter holds.
Let $|| vun || sup 2 ~=~ sum from i=1 to {d sub rho} ~ v sub i sup 2$,
where $vun ~=~ ( v sub 1, "..." , v sub d sub rho )$.
As $rho (x)$ is unitary for all $x ~member~ G$,
.DS 2
.EQ (4.1)
|| vun || ~<=~ | z | sum from {x member OMEGA} ~
mu (x) || rho (x) vun || ~=~ | z | ~cdot~ || vun ||
~<=~ || vun ||~.
.EN
.DE
Thus equality holds in (4.1).
For $|z|~<~1$ this is impossible, and
$[I sub rho - t mu hat ( rho ) ]$ is invertible
in this case.
If $z~=~1$, then $|| vun || ~=~ sum from {x member OMEGA} ~
mu (x) || rho ( x ) vun ||$ is equivalent to
.DS 2
.EQ (4.2)
rho (x) vun ~=~ vun ,~~ ~ x ~member~ OMEGA~.
.EN
.DE
As $OMEGA$ generates $G$, we conclude by repeated
use of (4.2) that $rho (x) vun ~=~ vun , ~x ~member~ G$.
The irreducibility of $rho$ then implies that
$rho ~=~ 1$.
Hence $[ I sub rho - mu hat ( rho )]$ is invertible for
$rho ~!=~ 1$.
.sp
.I
Theorem\ 4.1.
Let
.DS 3
.EQ
F(x,z)~mark =~
E(z sup {T sub x} )~=~
sum from n=0 to inf~
P(T sub x = n ) z sup n ~,
.EN
.sp
.EQ
f(z)~lineup =~
E(z sup T )~=~sum from n=0 to inf~
P(T=n) z sup n~,
.EN
.DE
for $x~member~G$
and $| z |~<~1$ or $z~=~1$.
Let $nu (x) ~=~ mu (x sup -1 ) ,~ x ~member~ G$.
Then
.DS 2
.EQ (4.3)
F(x,z) ~mark =~ {1+(1-z) sum from {rho != 1} d sub rho
~Tr [ rho (x) ~cdot~ (I sub rho - z nu hat ( rho )) ] sup -1}
over
{1+(1-z) sum from {rho != 1} d sub rho ~ Tr [ {I sub rho - z nu hat
( rho ) ] sup -1}}
~,
.EN
.sp
.EQ (4.4)
f(z) ~lineup =~ 1 over {1+ (1-z) sum from {rho != 1} d sub rho ~
Tr [I sub rho - z nu hat ( rho ) ] sup -1}
~,
.EN
.sp
.EQ (4.5)
E(T sub x ) ~lineup =~ sum from { rho != 1} ~ d sub rho ~
Tr [ I sub rho - nu hat ( rho ) ] sup -1 ~-~
sum from {rho != 1} ~ d sub rho ~ Tr [ rho (x) ~cdot~
(I sub rho - nu hat ( rho )) ] sup -1
~,
.EN
.sp
.EQ (4.6)
E(T) ~lineup =~ sum from {rho != 1} ~ d sub rho ~
Tr [ I sub rho - nu hat ( rho ) ] sup -1
~.
.EN
.DE
Proof:
.R
The random walk moves from $x$ to $yx$ with
probability $mu (y)$.
Hence
.DS 2
.EQ (4.7)
F(x) ~=~ sum from {y member G} ~
mu (y) E (z sup {1+T sub yx } ) ~=~ z ( nu * F) (x), ~~
~x != e~,
.EN
.DE
where we have written $F(x)$ for $F(x,z)$.
.P
Multiply both sides of (4.7) by
$rho (x)$, $rho ~member~ G hat$, and sum over
all $x != e$.
Since $F(e) ~=~ 1$, we get
.DS 2
.EQ (4.8)
F hat ( rho ) - I sub rho ~=~ z {nu * F} ~
( rho ) - z ( nu * F) (e) I sub rho ~=~ z nu hat ( rho )
F hat ( rho ) - z ~ [ sum from {y ~member~ G} ~
mu (y) F(y)] I sub rho ,~~~ rho ~member~ G hat
.EN
.DE
where we have written $F hat ( rho )$ for
$F hat ( rho , z )$.
.P
Suppose that $|z| ~<~ 1$.
Replacing $mu$ by $nu$ in the lemma and using (4.8),
we obtain
.DS 2
.EQ (4.9)
F hat ( rho ) ~=~ [ 1-z sum from y ~ mu (y) F (y) ] ~cdot~
[ I sub rho - z nu hat ( rho ) ] sup -1
~.
.EN
.DE
Inverting
this relation leads to
.DS 2
.EQ (4.10)
F(x) ~=~ {[1-z sum from y mu (y) F(y)]} over
{| G |} ~cdot~ sum from rho ~
d sub rho ~ Tr ~[ rho (x) ~cdot~ (I sub rho - z nu hat ( rho ))] sup -1
,~ ~~ x ~member~ G~.
.EN
.DE
In particular,
.DS 2
.EQ (4.11)
1 ~=~ F(e) ~=~ {[1-z sum from y mu (y) F(y)]}
over {| G |} ~cdot~ sum from rho ~ d sub rho ~
Tr [ I sub rho - z nu hat ( rho ) ] sup -1
~.
.EN
.DE
Equations
(4.10) and (4.11) give (4.3) for $| z |~<~1$.
By continuity (4.3) also holds at
$z~=~1$.
Since
.DS 2
.EQ
P(T=n) ~=~ 1 over {| G |} ~ sum from {x member G}
~ P(T sub x =n) ,~~~ 0 ~<=~ n ~<~ inf
~,
.EN
.DE
we have
.DS 2
.EQ (4.12)
f(z) ~=~ 1 over {| G |} ~ sum from x ~
F(x,z) ~=~ {F hat (1,z)} over {| G |}~,
.EN
.DE
and (4.4) follows from (4.9) and (4.12).
.P
Since $E (T sub x ) ~=~ dF over dz (x,1),~E (T) ~=~
df over dz (1)$, (4.5) and (4.6) follow
by differentiating respectively (4.3) and (4.4).
.P
The above formulas simplify when $mu (x)$ is
a class function.
Assume that $mu$ is concentrated on the
$k$ conjugacy classes $C sub 1 , ".." , C sub k$,
uniformly over each class.
By Theorem\ 2.3, $nu hat ( rho ) ~=~ s sub rho I sub rho$
where $s sub rho ~=~ sum from i=1 to k ~ mu (C sub i )
r bar sub rho (C sub i )$,
$r bar sub rho (C sub i ) ~=~ {chi bar sub rho (C sub i )} over {d sub rho}$.
Hence
we obtain the following result.
.sp
.I
Theorem\ 4.2.
Let $x ~member~ G , ~ | z | ~<~ 1$ or $z~=~1$.
Then
.DS 3
.EQ (4.13)
F(x,z) ~mark =~ {1+(1-z) sum from {rho != 1} ~
{d sub rho chi bar sub rho (x)} over {1-s sub rho z}} over
{1+ (1-z) sum from {rho != 1} ~ d sub rho sup 2 over
{1- s sub rho z}}
~,
.EN
.sp
.EQ (4.14)
f(z) ~lineup =~ 1 over {1+ (1-z) ~ sum from {rho != 1} ~
d sub rho sup 2 over {1-s sub rho z}}
~,
.EN
.sp
.EQ (4.15)
E(T sub x ) ~lineup =~ sum from {rho != 1} ~
{d sub rho sup 2} over {1-s sub rho} ~-~ sum from { rho != 1} ~
{d sub rho chi bar sub rho (x)} over {1-s sub rho}
~,
.EN
.sp
.EQ (4.16)
E(T) ~lineup =~ sum from {rho != 1} ~
{d sub rho sup 2} over {1-s sub rho}
~.
.EN
.DE
.H 1 "Limit Laws for $fat {T sub x}$ \f3and T\f1"
Let $mu$ be a measure on $S sub n$ concentrated uniformly
on a conjugacy class $C ~!=~ "{" e "}"$.
We assume in the sequel that $C$ is fixed.
By this we mean that the number of $p$-cycles in
$C$, $p ~>=~ 2$, is independent of $n$.
Thus elements in $C$ move $m$ letters and
fix all others, $m$ being the sum of the lengths
of the $p$-cycles, $p ~>=~ 2$, in $C$.
In this case (3.1) becomes
.DS 2
.EQ (5.1)
| C | ~=~ {n(n-1) ".." (n-m+1)} over
{2 sup {a sub 2} {a sub 2}! ".." k sup {a sub k} {a sub k}!}~,
.EN
.DE
with $k$ the length of the longest cycle in $C$.
.P
We obtain limit laws for $T sub x$ and $T$ as
$n ~->~ inf$.
The subgroup $H$ generated by $C$ is normal.
Hence for $n ~>=~ 5$, $H~=~S sub n$ or $A sub n$
depending on whether $C$ is odd or even.
We consider these two cases separately.
To derive limit laws we need the estimates
for $| r sub lambda (C) | ~=~ | chi sub lambda (C) | size 14 /  d sub lambda$
given in Theorem\ 5.2.
First, we obtain the following trivial estimate.
.sp
.I
Theorem\ 5.1.
If $lambda ~!=~ (n), ~ (1 sup n )$,
$C~!=~"{" e "}"$, and $n~>=~5$,
then
.DS 2
.EQ (5.2)
| r sub lambda (C) | ~<=~ {d sub lambda - 1} over
d sub lambda
~.
.EN
.DE
Proof:
.R
$chi sub lambda (C)$ is an integer and
the sum of $d sub lambda$ roots of unity.
Hence $| chi sub lambda (C) | ~<=~ d sub {lambda } -1$
unless the eigenvalues of
$rho sub lambda (x), ~ x ~member~ C$, are either
are all $+1$ or all $-1$, i.e. $rho sub lambda (x) ~=~ I sub lambda$,
$~x ~member~ C$, or $rho sub lambda (x) ~=~ - I sub lambda $,
$x ~member~ C$.
For $n ~>=~ 5$ and $lambda ~!=~ (n)$, $(1 sup n )$,
$rho sub lambda$ is faithful, and so these possibilities
are ruled out as we are assuming $C ~!=~ "{" e "}"$.
.sp
.I
Theorem\ 5.2.
i) There exists a constant $theta sub 1~=~
theta sub 1 (C)~>~0$ such that
.DS 2
.EQ (5.3)
| r sub lambda (C) | ~<=~ {max [ lambda sub 1 , lambda sub 1 sup prime ]
+ theta sub 1} over {| lambda |}
~.
.EN
.DE
ii) There exists a constant $theta sub 2~=~theta sub 2 (C)~>~0$
such that
.DS 2
.EQ (5.4)
| r sub lambda (C) ~<=~ 1 - {theta sub 2} over {| lambda | sup {theta sub 2}}
~ if ~~ lambda ~!=~ (n),~~~ ( 1 sup n ) ~ roman {and} ~
C ~!=~ "{" e "}"
~.
.EN
.DE
Remark:
.R
Calderbank, Hanlow, and Wales [6] recently obtained another
bound for $|^ r sub lambda (C) ^|$,
namely that for $lambda ~!=~ (n)$, $(1 sup n )$, and
$C ~!=~ "{" e "}"$,
.DS 3
.EQ
| ^ r sub lambda ( C ) ^| ~<=~ n-3 over n-1 ~.
.EN
.DE
.ul
Proof:
i)\0 Let $C$ have $gamma sub p$ cycles of length
$p, ~ p ~>=~ 2$.
Let $lambda ~=~ left (
pile {a sub 1 "..." a sub s above b sub 1 "..." b sub s}
right )$,
$alpha sub i ~=~ {a sub i ^+^ 1 over 2} over {| lambda |}$,
$beta sub i ~=~ {b sub i ^+^ 1 over 2}$, $1 ~<=~ i~<=~ s$.
By Theorem 3.5,
there is a $theta sub 1~=~theta sub 1 (C)~>~0$ such
that
.DS 2
.EQ (5.5)
| r sub lambda (C) ~-~ prod from {p >= 2} ~ { sum from {i = 1}
to s ~ [ alpha sub i sup p - (- beta sub i ) sup p ] }
sup {gamma sub p} |
~<=~ theta sub 1 over {| lambda |}
~.
.EN
.DE
Since $ alpha sub i ,~ beta sub i ~>~ 0$ and
$sum from {i = 1} to s ( alpha sub i + beta sub i ) ~<=~ 1$,
.DS 2
.EQ (5.6)
| sum from {i = 1} to s ~ [ alpha sub i sup p - (- beta sub i ) sup p ]
| ~<=~ alpha sub 1 ~ sum from {i = 1} to s ~ alpha sub i + beta sub 1 ~
sum from {i = 1} to s ~ beta sub i ~<=~ max [ alpha sub 1 , beta sub 1 ]
~.
.EN
.DE
The bound
(5.3) follows from (5.5) and (5.6).
.sp
ii)\0 If $lambda sub 1 ,~ lambda sub 1 sup prime ~<=~
| lambda | - 2 theta sub 1$, then (5.3)\0 gives
.DS 2
.EQ (5.7)
| r sub lambda (C) | ~<=~ 1 ^-^ {theta sub 1} over
{| lambda |}
~.
.EN
.DE
If $lambda sub 1 ~>~ | lambda | - 2 theta sub 1$, then by (3.3)
.DS 2
.EQ (5.8)
d sub lambda ~<=~ {| lambda |!} over {lambda sub 1 !} ~<=~
{| lambda |} sup {(| lambda | - lambda sub 1 )} ~<=~
| lambda | sup {2 theta sub 1}
~.
.EN
.DE
Hence by (5.2),
.DS 2
.EQ (5.9)
| r sub lambda (C)| ~<=~ {d sub lambda - 1} over {d sub lambda} ~<=~
1 ~-~ 1 over {| lambda | sup {2 theta sub 1}} ~ roman {if} ~~
lambda ~!=~ (n) , ~ (1 sup n ) ~ roman {and} ~ C ~!=~ "{" e "}"
~.
.EN
.DE
Similarly (5.9) holds
if $lambda sub 1 sup prime ~>~ | lambda | - 2 theta sub 1$.
Thus
(5.4) follows from (5.7) and (5.9).
.sp
.I
Theorem\ 5.3.
We have
.DS 2
.EQ (5.10)
sum from {| lambda | = n} from size 8 {lambda != (n) , ( 1 sup n )}
~ chi sub lambda sup 2 (C) ~ {| r sub lambda (C) |} over {1- | r sub lambda
(C) |} ~=~ o left ( n! over {| C |} right ) ~ ~~roman {as} ~~n ~->~ inf
~.
.EN
.DE
Proof:
.R
Let $0~<~a~<~1$.
For given $n$ and $a$, with $na~member~Z$, let
.DS 2
.EQ (5.11)
I sub 1 ~=~ "{"  lambda : ~ lambda != (n), (1 sup n ) ~
and~ | r sub lambda (C) | ~<=~ a "}" ,~~~~
I sub 2 ~=~ "{" lambda :~ lambda != (n) ,~ ( 1 sup n ) ~
and~ | r sub lambda (C) | ~>~ a "}"~.
.EN
.DE
By (2.2),
.DS 2
.EQ (5.12)
^^sum from {| lambda | = n} from size 8 { lambda != (n), (1 sup n )}
^ chi sub lambda sup 2 (C) ~ {| r sub lambda (C) |} over
{1 -  |  r sub lambda (C) | } ^<=^ [ sum from {lambda member I sub 1}
^+^ sum from {lambda member I sub 2} ] ^
chi sub lambda sup 2 (C) ^
{ |  r sub lambda (C) | } over {1- | r sub lambda (C) | } ^<=^
a over 1-a ^ n! over {| C |} ^+^ sum from {lambda member I sub 2} ^
{d sub lambda sup 2} over {1- |  r sub lambda (C) | }
~.
.EN
.DE
.P
If $lambda ~member~ I sub 2$, then by (5.3), $max~[ lambda sub 1 ,~ 
lambda sub 1 sup prime ] ~>~ an over 2$ for $n$ sufficiently large,
say $n~>~N$.
Hence
.DS 3
.EQ (5.13)
sum from {lambda member I sub 2} ~
{d sub lambda sup 2} over {1- | r sub lambda (C) | } ~mark <=~
sum from {| lambda | = n , lambda sub 1 > an over 2} ~
d sub lambda sup 2 over {1- | r sub lambda (C) |} ~+~
sum from {| lambda | = n , lambda sub 1 sup prime > an over 2}
~ d sub lambda sup 2 over {1- |  r sub lambda (C) | } 
.EN
.sp
.EQ
lineup =~2~sum from {| lambda | =n, lambda sub 1 > an over 2 }~
d sub lambda sup 2 over {1- |  r sub lambda (C) | } ~
,~~~ n ~>~ N~.
.EN
.DE
.P
We conclude from Corollary\ 2 to Theorem\ 3.2
and Theorem\ 5.2 ii)
that for $n~>~N$,
.DS 2
.EQ (5.14)
sum from {| lambda | = n} from size 8 {lambda != (n) , (1 sup n )} ~
{chi sub lambda sup 2 (C)} ~ {{| r sub lambda (C) |} over
{1-  |  r sub lambda (C) | }} over
{n! over {| C |}} ~ ~<=~ a over 1-a ~+~ 2 over {theta sub 2} ~
n sup {theta sub 2 + m} ~cdot~ left ( 4 over {(1- alpha ) sup alpha
n sup alpha} right ) sup n ~,
.EN
.DE
where $alpha ~=~ {[ an over 2 ]} over n$.
.P
Letting first $n ~->~ inf$ and then $a ~->~ 0$ in (5.14),
we obtain (5.10).
.sp
.I
Theorem\ 5.4.
Let $C$ be odd and $phi (x) ~=~ 1$ if $x ~member~ C$,
$phi (x) ~=~ 0$ if $x ~member~ C$.
Let $x ~!=~ e$.
Then
.DS 2
.EQ (5.15)
E(T sub x ) ~=~ n! ~+~ phi (x) n! over {| C |} ~+~ epsilon (n,x)
~,
.EN
.DE
where
$lim from  {n -> inf}~epsilon (n,x) | C | / n!~=~0$
uniformly in $x$.
For $t~>=~0$,
.DS 3
.EQ (5.16)
lim ~ P[ T sub x ~>=~ tn!] mark ~=~ e sup -t , ~ ~
{uniformly~ in}~ x~.
.EN
.sp
.EQ (5.17)
E(T) ~lineup =~ n! ~+~ n! over {| C |} ~+~ o left ( n! over {| C |} right )
~.
.EN
.sp
.EQ (5.18)
lim from {n-> inf} ~
P[T ~>=~ tn!] ~=~ e sup -t ,~~ ~ t ~>=~ 0
~.
.EN
.DE
Proof:
.R
The results are derived from the formulas of
Theorem\ 4.2 and the estimate of Theorem\ 5.3.
In all ensuing sums, $lambda$ varies over all
partitions of $n$ distinct from ($n$).
We have
.DS 2
.EQ (5.19)
SIGMA ~ d sub lambda sup 2 over {1-r sub lambda} ~=~
SIGMA ~ d sub lambda sup 2 left [ 1+ r sub lambda + r sub lambda sup 2
+ {r sub lambda sup 3} over {1-r sub lambda} right ] ~=~
SIGMA ~ d sub lambda sup 2 + SIGMA ~ d sub lambda chi sub lambda (C)
~+~ SIGMA chi sub lambda sup 2 (C) ~+~SIGMA ~ chi sub lambda sup 2 (C) ~
r sub lambda over 1-r sub lambda~.
.EN
.DE
Hence by theorems\ 2.1 and 5.2,
.DS 2
.EQ (5.20)
SIGMA ~ d sub lambda sup 2 over 1-r sub lambda ~=~
n! ~+~ n! over {| C |} ~+~ o left ( n! over {| C |} right )~.
.EN
.DE
Similarly,
.DS 3
.EQ (5.21)
SIGMA ~ {d sub lambda chi sub lambda (x)} over {1-r sub lambda} 
~mark =~
SIGMA left [ 1 + r sub lambda + r sub lambda sup 2 +
{r sub lambda sup 3} over {1-r sub lambda} right ] ~
d sub lambda chi sub lambda (x) 
.EN
.sp
.EQ
lineup =~SIGMA ~ d sub lambda chi sub lambda (x) ~+~
SIGMA ~ chi sub lambda (x) chi sub lambda (C) ~+~
SIGMA ~ chi sub lambda sup 2 (C) r sub lambda (x) ~+~
SIGMA ~ {chi sup 2 (C) r sub lambda (x) r sub lambda (C)} over
{1-r sub lambda (C)}
~.
.EN
.DE
Hence, by Theorem\ 2.1,
.DS 2
.EQ (5.22)
SIGMA ~ {d sub lambda chi sub lambda (x)} over
{1-r sub lambda} ~=~
-2 + phi (x) ~ n! over {| C |} ~+~
SIGMA ~ chi sub lambda sup 2 (C) r sub lambda (x) ~+~
SIGMA ~ {chi sup 2 (C) r sub lambda (x) r sub lambda (C)} over
{1-r sub lambda (C)}
~.
.EN
.DE
.P
To prove (5.15), we consider separately $x$
odd and $x$ even.
If $x$ is odd, then by Theorem\ 3.1\ iii),
$chi sub lambda sup 2 (C) r sub lambda (x) ~=~
- chi sub {lambda sup prime} sup 2 (C) r sub {lambda sup prime} (x)$.
Hence $SIGMA ~ chi sub lambda sup 2 (C) r sub lambda (x) ~=~-1$
and we conclude from (5.22) and Theorem 5.3 that
.DS 2
.EQ (5.23)
SIGMA ~ {d sub lambda chi sub lambda (x)} over {1-r sub lambda}
~=~ phi (x)~ n! over {| C |} ~+~ o left ( n! over {| C |} right ) 
.EN
.DE
uniformly in $x$ odd.
Equations
(4.15), (5.20) and (5.23) give (5.15) for $x$ odd.
For $x$ even we have
.DS 2
.EQ (5.24)
E (T sub x ) ~=~ 1 ~+~ 1 over { | C |} ~ sum from {c member C} ~
E (T sub cx )
~.
.EN
.DE
.P
We conclude from (5.15) and (5.24) that
.DS 2
.EQ (5.25)
E(T sub x ) ~=~ n! ~+~ n! over {| C |} ~-~
{|C sub x |} over {| C |} sup 2 ~n! ~+~ o left ( n! over {| C |} right ) 
.EN
.DE
uniformly in $x$ even, where
$C sub x ~=~ "{" c member C :~ ~ cx member C "}"$.
Let $c sub 1 ~member~ C sub x$.
Then $x ~=~ c sub 1 sup -1 c sub 2$ for some $c sub 2 ~member~ C$.
Since each of the elements of $C$ moves $m$ letters, $x$ moves at most
$2m$ letters.
Since $c sub 1$ and $c sub 1 x$ have the same cyclic decomposition,
the sets of elements moved by $c sub 1$ and $x$ must overlap.
Hence one of the elements moved by $c sub 1$ can be chosen in
at most $2m$ ways, which implies
.DS 2
.EQ (5.26)
| C sub x | ~<=~ 2 m sup 2 n sup m-1
~.
.EN
.DE
Now (5.25) and (5.26) give (5.15) for $x$ even.
.sp
Next we prove (5.16).
Rewrite (4.13) as
.DS 2
.EQ
E (z sup {T sub x} ) mark ~=~ {1 + SIGMA ~ {d sub lambda chi sub lambda (x)}
over {1-r sub lambda} ~ (1-z) + g(x,z) (1-z) sup 2} over
{1+ SIGMA ~ {d sub lambda sup 2} over {1-r sub lambda} ~
(1-z) + g (e,z) (1-z) sup 2}
~,
.EN
.sp
.EQ (5.27)
~~~
.EN
.sp
.EQ
g (x, z) ~lineup =~ -~ SIGMA ~ {r sub lambda d sub lambda
chi sub lambda (x)} over {(1-r sub lambda z ) (1-r sub lambda )}
~,
.EN
.DE
where $x ~member~ S sub n~ and~ | z | ~<~ 1$.
By Theorems\ 2.1 and 5.2,
.DS 2
.EQ (5.28)
| g (x,z) | ~<=~ SIGMA ~ d sub lambda sup 2 over {(1-r sub lambda ) sup 2}
~<=~ {n sup {2 theta sub 2}} over {theta sub 2 sup 2} ~
n! ,~~~x ~member~ S sub n ~and~ | z | ~<~ 1~.
.EN
.DE
.P
We conclude from (5.27) and (5.28)
that
.DS 2
.EQ (5.29)
lim from {n-> inf} ~
E (e sup {- lambda {T sub x} / n!}) ~=~ 1 over {1+ lambda} ~=~
int sub o sup inf ~ e sup {- lambda t} ~ e sup {-t} dt ,~~~
lambda ~>=~ 0~.
.EN
.DE
Equation
(5.16)\0follows from the Continuity Theorem for
Laplace transforms [4].
Equations (5.17) and (5.18) may be derived in the
same way as (5.15) and (5.16).
They also follow from the latter by averaging over $x$.
.sp
.I
Theorem\ 5.5.
Let $C$ be even and $!=~ "{" e "}"$.
Let $x~member~A sub n$ and $x ~!=~ e$.
Then
.DS 3
.EQ (5.30)
E (T sub x ) ~mark =~ n! over 2 ~+~ O left ( n! over {| C |} right ) ~
~~~{uniformly~in} ~ x~.
.EN
.sp
.EQ (5.31)
lim from {n -> inf}~
P left [ T sub x~>=~t^ n! over 2 right ] lineup ~=~
e sup t ,~~~"uniformly in" ~ x ~ for~t~>=~0~.
.EN
.sp
.EQ (5.32)
E(T) ~lineup =~ n! over 2 ~+~ n! over {2 | C |} ~+~ o left (
n! over {| C |} right )~.
.EN
.sp
.EQ (5.33)
lim from {n -> inf}~
P left [
T~>=~t ^ n! over 2 right ] , ~~~t~>=~0~.
.EN
.DE
.R
.P
Theorem\ 5.4 is derived from the formulas of Theorem\ 4.2
and Theorem\ 3.1 which gives the irreducible characters of
$A sub n$ for undivided classes.
This is the case here as the number of 1-cycles\ $-> ~ inf$ when
$n ~->~ inf$.
We omit the proof of Theorem\ 5.5 which is almost identical
with that of Theorem\ 5.4.
Observe that the result (5.30) is somewhat weaker than its
counterpart (5.15) as the sum $SIGMA~ chi sub lambda sup 2 (C) r sub lambda (x)$
can not be handled by the above method.
.P
We also remark that Theorems\ 5.4 and 5.5 and their proofs
go through with some minor modifications in case the
measure $mu$ is concentrated on a finite number of
fixed conjugacy classes, uniformly over each class.
Again, we omit the proof.
.P
Finally, we obtain a limit theorem for $T$ in case $mu$
is uniformly distributed on the class of transpositions
$(12),..,(1n)$.
.sp
.I
Theorem\ 5.6.
As $n~->~inf$,
.DS 3
.EQ (5.34)
E (T) ~mark =~ n! ~+~ (n-1)! ~+~ o [ (n-1)! ]~,
.EN
.sp
.EQ (5.35)
lim from {n -> inf} ~ P [T ~>=~ tn!] ~lineup =~ e sup -t ,~~~
0 ~<=~ t ~<~ inf~.
.EN
.DE
Proof:
.R
By (4.6),
.DS 2
.EQ (5.36)
E(T) ~=~ SIGMA ~ d sub lambda sup 2 ~+~
SIGMA ~ d sub lambda ~ Tr rho sub lambda ( nu ) ~+~
SIGMA ~ d sub lambda ~Tr ~ rho sub lambda sup 2 ( nu ) ~+~
SIGMA ~ d sub lambda ~ Tr "{" rho sub lambda sup 3 ( nu )
[ I sub lambda - rho sub lambda ( nu ) ] sup -1 "}"
~.
.EN
.DE
We have
.DS 2
.EQ (5.37)
nu ~=~ 1 over n-1 ~ sum from j=1 to n-1 ~ (jn), ~~~
nu sup 2 ~=~ 1 over (n-1) sup 2 ~ [
(n-1) e ~+~ sum from {j != k != n} ~ (jkn) ]
~.
.EN
.DE
Hence
.DS 2
.EQ (5.38)
Tr~ rho sub lambda ( nu ) ~=~ chi sub lambda (12) ,~~~
Tr ~ rho sub lambda sup 2 ( nu ) ~=~ d sub lambda over n-1 ~+~
chi sub lambda (123)
~.
.EN
.DE
From (5.36), (5.38) and Theorems\ 2.1, 3.7 we obtain
.DS 2
.EQ (5.39)
E(T) ~=~ n! + (n-1)! ~+~ o [(n-1)!] ~+~
sum ~ d sub lambda ~ sum from {j=1} to s ~
{d sub j ( {lambda sub i sub j - i sub j} over n-1 ) sup 3}
over {1- {( {lambda sub i sub j - i sub j} over n-1 ) }}
~,
.EN
.DE
where we have used the same notation as in Theorem\ 3.7.
.P
We estimate the double sum of (5.39) which we refer to
as $SIGMA$.
Let $0 ~<~ a ~<~ 1$ and divide the partitions $lambda$ of $n, ~ lambda ~!=~ (n)$,
into $A$ and $B$,
with
$A$ consisting of those $lambda$ for which
$| {lambda sub i sub j - i sub j} over n-1 | ~<=~ a $ for all $j$,
and
$B$ of all other $lambda$.
We have
.DS 2
.EQ (5.40)
| sum from {lambda member A} | ~<=~ a over 1-a ~
sum ~ d sub lambda ~ sum from {j=1} to s ~
d sub j ( lambda sub i sub j - i sub j ) sup 2 ~=~
a over 1-a ~ sum ~ d sub lambda ~ Tr ~ rho sub lambda sup 2
( nu ) ~<=~ a over 1-a ~ n! over n-1~.
.EN
.DE
Since $-( lambda sub 1 sup prime - 1 ) ~<=~
lambda sub i sub j - i sub j ~<=~ lambda sub 1 - 1 $
for all $j$
and $sum from j=1 to s ~ d sub j ~=~ d sub lambda$, we also
have
.DS 2
.EQ (5.41)
| sum from {lambda member B} | ~<=~ n ~ sum from {lambda member B}
~ d sub lambda sup 2 ~<=~ n [ sum from {lambda sub 1 > a (n-1)} ~
d sub lambda sup 2 ~+~ sum from {lambda sub 1 sup prime ~>~ a (n-1)} ~
d sub lambda sup 2 ] ~=~ 2n ~ sum from {lambda sub 1 >a(n-1)} ~
d sub lambda sup 2
~.
.EN
.DE
Hence by Corollary\ 2 of Theorem\ 3.2,
.DS 2
.EQ (5.42)
lim bar from {n-> inf} ~ {| SIGMA |} over (n-1)! ~<=~ a over 1-a
~.
.EN
.DE
Letting $a -> 0$, we conclude
.DS 2
.EQ (5.43)
SIGMA ~=~ o (n-1)!
~.
.EN
.DE
Expansion
(5.34) follows from (5.39) and (5.42).
To prove (5.35) we rewrite (4.4) as
.DS 3
.EQ
f(z) ~mark =~ 1 over {1+ET (1-z) + g(z) (1-z) sup 2}
~,
.EN
.EQ (5.44)
~~~
.EN
.EQ
g(z) ~lineup =~ -~ sum ~ d sub lambda ~ sum from {j = 1} to s ~
{d sub j ~cdot~ ( {lambda sub i sub j - i sub j}
over {n-1} )}
over {( 1^-^ {lambda sub i sub j - i sub j}
over n-1 ) ~(
1^-^ {lambda sub i sub j - i sub j} over n-1 z )}
~,
.EN
.DE
and observe that
.DS 2
.EQ
| g(z) | ~<=~ sum ~ d sub lambda ~ sum from j=1 to s ~
{d sub j} over {[ 1^-^ {lambda sub i sub j - i sub j}
over n-1 ] sup 2} ~=~ O (n sup 2 ~cdot~ n! )
~.
.EN
.DE
The remainder of the proof is identical with that
of (5.16).
.H 1 "Other Groups"
In Section\ 5 we showed that for certain
random walks on $G ~=~ S sub n$\ or\ $A sub n$,
$E(T) ~wig~ | G |$ and
$lim from {n -> inf} ~ P [T ~>~ | G | t ] ~=~ e sup -t , ~ t ~>=~ 0$.
One may inquire to what extent these limit laws carry over
to other infinite classes of groups.
We consider the simple random walk on $Z sub n sup d$.
We show that the above limit laws break down completely
for $d ~=~ 1$ and partially for $d ~>=~ 2$.
.P
The group $Z sub n sup d$ is the direct product
of $d$ copies of the cyclic group of order $n$.
Its elements
are the d-tuples
$x~=~[x sub 1 , "..", x sub d ]$, each $x sub i$ an integer
from $0$ to $d-1$,
and addition of coordinates is performed modulo $n$.
Thus $| Z sub n sup d | ~=~ n sup d$.
The simple random walk on $Z sub n sup d$ is given by the measure
$mu (x) ~=~ 1 over 2d$ when $x$ is any of the
$2d$ points $[0,"..",0, +- 1, 0, "..", 0]$.
As $Z sub n sup d$ is abelian, all irreducible
representations are 1-dimensional.
They are given by
$rho ( xun )~=~n sup -1 exp ( 2 pi i jun cdot xun )$,
where $jun ~=~ [ j sub 1 , "..", j sub d ]$, $jun~cdot~ xun ~=~ 
j sub 1 x sub 1 + ".." + j sub d x sub d$, each $j sub i$ an integer
between $0$ and $n-1$.
The number
$s sub rho$ defined in section\ 4 is given by
.DS 2
.EQ (6.1)
s sub rho ~=~ 1 over d ~ sum from {k=1} to d ~ cos ~
{2 pi j sub k} over n
~,
.EN
.DE
and formulas (4.16) and (4.14) become
.DS 2
.EQ (6.2)
E(T) ~=~ sum from {jun != fat 0} ~
d over {[1- cos^  {2 pi j sub 1} over n ] +".."+ [ 1- cos ^
{2 pi j sub d} over n ]}~,
.EN
.sp
.EQ (6.3)
E(z sup T ) ~=~
left [ 1 + (1-z) ~ sum from {jun != fat 0} ~ 1 over {
[ 1-z ~cos^ {2 pi j sub 1} over n ] +".."+ [ 1-z~
cos^ {2 pi j sub d} over n ]} right ] sup -1~.
.EN
.DE
.I
Lemma:
We have
.DS 2
.EQ (6.4)
sum from {1 <= j sub 1 , .. , j sub d <= n} ~
1 over {j sub 1 sup 2 +.. + j sub d sup 2} ~wig~
left {
matrix {
ccol { pi sup 2 over 6 above pi over 2 ~ log ~ n ~ above
left [ int sub {I sup d} ~ dt over {{t sub 1 sup 2}+..+{t sub d sup 2}}
right ] n sup {d-2} }
ccol { ,~d ~=~ 1 above ,~d ~=~ 2 above ,~d ~>~ 2 }
}
.EN
.DE
where $dt ~=~ dt sub 1 ~..~ dt sub d$, and 
.DS 2
.EQ
I sup d ~=~ "{"  (t sub 1 ,"...",t sub d ):~~0 ~<=~ t sub 1 , "...",
t sub d ~<=~ 1 "}" 
.EN
.DE
.br
Proof:
.R
For $d ~=~ 1$, (6.4) is a well known identity.
Let $d~=~2$.
Define
.DS 2
.EQ
A sub jun ~=~ "{" (t sub 1 , t sub 2 ) : ~~ j sub i ~<=~
t sub i ~<=~ j sub i  +1 , ~~ i = 1,2 "}"
~~~~roman {for}~~  0 ~<=~ j sub 1 ,
j sub 2 ~ and ~ jun~!=~ 0~.
.EN
.DE
We have
.DS 2
.EQ (6.5)
1 over {(j sub 1 + 1) sup 2 + ( j sub 2 + 1 ) sup 2} ~<=~
int sub {A sub jun} ~ dt over {t sub 1 sup 2 + t sub 2 sup 2} ~<=~  1 over
{j sub 1 sup 2 + j sub 2 sup 2}~,
.EN
.sp
.EQ (6.6)
^^"{" ( t sub 1 , t sub 2 ) : ^
t sub 1 , t sub 2 ^>=^ 0 , ^
2 ^<=^ t sub 1 sup 2 + t sub 2 sup 2 ^<=^ n sup 2 "}"
^\(ib ^ union from {j sub 1 , j sub 2 <= n} ^
A sub jun \(ib ^ "{" (t sub 1 , t sub 2 ) :^
t sub 1 , t sub 2 >= 0 , ^
2 ^<=^ t sub 1 sup 2 + t sub 2 sup 2 ^<=^ 2 (n+1) sup 2 "}"
~.
.EN
.DE
A simple integration exercise then gives
.DS 2
.EQ (6.7)
sum from {1 <= j sub 1 , j sub 2 <= n} ~
1 over {j sub 1 sup 2 + j sub 2 sup 2 } ~=~
pi over 2 ~ {log~n} ~+~ O (1)~.
.EN
.DE
The case $d~>~2$ is treated likewise and the
proof is omitted.
.sp
.I
Theorem\ 6.1.
For the simple random walk on $Z sub n sup d$,
.R
.DS 3
.EQ (6.8)
E(T) ~wig~ 1 over 6 ~ n sup 2 , ~~~~ d ~mark =~ 1~,
.EN
.sp
.EQ (6.9)
E(T) ~wig~ 2 over pi ~ n sup 2 ~log ~ n,~~~~ d ~lineup =~ 2
~,
.EN
.sp 2
.EQ (6.10)
E(T) ~wig~ c (d) n sup d , ~~~~ d ~lineup >~ 2
~,
.EN
.DE
.ul
where
.DS 2
.EQ (6.11)
c(d) ~=~ int sub { I sup d} ~ dt over {1^-^
{cos~ 2 pi t sub 1 + ".."+ cos ~ 2 pi t sub d} over
d}
~>~1~.
.EN
.DE
.ul
Remark:
The constant $c sub d$ for $d ~>=~ 3$ also equals the
expected number of returns to the origin
of the simple random walk on the infinite d-dimensional
lattice $Z sup d$, starting at the origin [18].
Is there a simple explanation for this fact?
.sp
.ul
Proof:
$d~=~1$:
We have
.DS 2
.EQ (6.12)
1 over {1- cos~t} ~=~
2 over t sup 2 ~+~ 2 over {( 2 pi -t ) sup 2} ~+~ g(t) ,~ ~~
g (t) ~ roman {continuous~on} ~ [0, 2 pi ]
~.
.EN
.DE
Hence
.DS 2
.EQ (6.13)
E(T) ~=~ sum from {j=1} to {n-1} ~
1 over {1- cos ~ {2 pi j} over n} ~=~
n sup 2 over pi sup 2 ~ sum from j=1 to n-1 ~
1 over j sup 2 ~+~ left [ sum from j=1 to n-1 ~
g left ( {2 pi j} over n right ) ~cdot~ 1 over n right ] n
~.
.EN
.DE
As $g$ is continuous,
.DS 2
.EQ (6.14)
lim from {n -> inf} ~ sum from j=1 to n-1 ~
g left (  {2 pi j} over n right ) ~cdot~ 1 over n ~=~
int sub 0 sup {2 pi} ~ g(t) dt
~.
.EN
.DE
Hence
(6.8) follows from the lemma and (6.14).
.sp
$d ~=~ 2$:\0Let $0 ~<~ delta ~<~ 1 over 2$.
Using (6.8), we have
.DS 2
.EQ (6.15)
E(T) ~=~ 8 ~ sum from {1 <= j sub 1 , j sub 2 <= delta n} ~
1 over {2- cos~ {2 pi j sub 1} over n ~-~
cos~ {2 pi j sub 2} over n} ~+~ O (n sup 2 )
~,
.EN
.DE
the constant in $O$ depending only on $delta$.
.P
For $epsilon ~>~ 0$, choose $0~<~ delta sub epsilon ~<~ pi$
such that
.DS 2
.EQ (6.16)
left | {1 over 2 (t sub 1 sup 2 + t sub 2 sup 2 )} over
{2- cos~t sub 1 - cos~ t sub 2 } ~ - ~ 1 right | ~<~
epsilon ~~ {if} ~~
|t sub 1 | , | t sub 2 | ~<~ delta sub epsilon ~ and ~
(t sub 1 , t sub 2 ) ~!=~ (0,0)~.
.EN
.DE
.P
Let $delta$ in (6.15) be $delta sub epsilon over {2 pi}$.
We conclude from the lemma and (6.15)
that
.DS 2
.EQ (6.17)
1- epsilon ~<=~ lim from {n -> inf} bar ~
E(T) over {2 over pi ~ n sup 2 ~log ~ n} ~<=~
{lim from {n-> inf}} bar ~ E(T) over {2 over pi ~
n sup 2 ~ log ~n} ~ <=~ 1 + epsilon ~.
.EN
.DE
Letting $epsilon ~->~ 0$, we get (6.9).
.sp
$d ~>~ 2$:
Let $B sub jun ~=~ left { t~=~ (t sub 1 , ".." , t sub d ) :~
{j sub i} over n ~<=~ t sub i ~<=~ {j sub i + 1} over n ,~
1 ~<=~ i ~<=~ d right } ~~ roman {and}$
.DS 2
.EQ (6.18)
f sub n (t) ~=~ left {
matrix {
ccol { 1 over {1^-^{( cos~ {2 pi j sub 1 } over n +..+
cos~ {2 pi j sub d} over n )} over d} above "" above 0}
ccol { roman {on} ~ B sub jun ,~ ~ jun ~!=~ 0~, above "" above roman {on} ~
B sub 0~. }
}
.EN
.DE
We have
.DS 2
.EQ (6.19)
{E sub n (T)} over n sup d ~=~ int sub {I sup d} ~ f sub n (t) dt
~,
.EN
.DE
.sp 2
.DS 2
.EQ (6.20)
lim from {n -> inf} ~ f sub n (t) ~=~
1 over {1^-^ {cos~ 2 pi t sub 1 + ...+ cos~ 2 pi t sub d} over
d } ~~~~~ roman {a.e.~ on}~ I sup d .
.EN
.DE
.P
By the dominated convergence theorem,
$lim from {n -> inf} ~ {E sub n (T)} over n sup d ~=~ c (d)$.
.P
Let $f(t)~=~1~-~{cos^ 2 pi ^ t sub 1 + "..." + cos ^ 2 pi ^ t sub d} over d$.
Then $int sub {I sup d} f(t) dt~=~1$.
We conclude from the Schwarz inequality
.DS 2
.EQ
1~=~int sub {I sup d} f sup -1/2 (t) cdot
f sup 1/2 (t) dt~<~int sub {I sup d} f sup -1
(t) dt cdot int sub {I sup d} f(t) dt~=~c(d)
.EN
.DE
.sp
.I
Theorem\ 6.3.
For the simple random walk on $Z sub n sup d$,
we have
.R
.DS 3
.EQ i)
mark (6.21)~~ lim from {n -> inf} ~ P (T ~>=~ E(T) ~cdot~ x ) ~=~
e sup -x ,~ x ~>=~ 0 ~,~ d ~>=~ 2~.
.EN
.sp
.EQ ii)
lineup (6.22)~~ lim from {n -> inf} ~ P(T ~>=~ n sup 2 x ) ~=~
{2 over pi sup 2} ~
sum from {n=0} to inf ~ {e sup {-2 pi sup 2
(n^+^ 1 over 2 ) sup 2 x}} over {(n^+^ 1 over 2 ) sup 2 } ~,~
x ~>=~ 0 , ~ d ~=~ 1~.
.EN
.DE
.ul
Remark.
For $d ~=~ 1$, the density is a theta function.
Formulas similar to (6.22) occur also
in the analysis of other random walks [18].
.sp
.ul
Proof:
i) By (4.14) and (4.16),
.DS 2
.EQ (6.23)
E (e sup {-{lambda T} over ET} ) ~=~
1 over {1 + ET [1-e sup {- lambda over ET} ] ~+~
g (e sup {- lambda over ET} ) [ 1-e sup {- lambda over ET} ] sup 2} ,~~~
lambda ~>=~ 0
~,
.EN
.DE
where
.DS 2
.EQ (6.24)
g(z) ~=~ sum from {rho =1} ~ {s sub rho} over
{(1-s sub rho )(1-s sub rho z )} ,~~ | z | ~<=~ 1
~.
.EN
.DE
.P
We have
.DS 2
.EQ (6.25)
|g(z)| ~<=~ left [ max from {rho != 1} ~
1 over {1 -s sub rho} right ] ~cdot~
sum from {rho != 1} ~ 1 over {1-s sub rho } ~<=~
d over {1- cos~ {2 pi} over n} ~cdot~ ET~.
.EN
.DE
.P
We conclude from (6.23) and (6.25)
that
.DS 2
.EQ (6.26)
lim from {n -> inf} ~  ( e sup {- {lambda T} over {ET}}  )
~=~ 1 over {1+ lambda} ~=~int sub 0 sup inf ~ e sup {- lambda x} ~cdot~
e sup -x dx ,~~~ lambda ~>=~ 0
~,
.EN
.DE
and (6.21) follows from the Continuity Theorem.
.sp
ii) By (6.3),
.DS 2
.EQ (6.27)
E ( e sup  {{- lambda T} over n sup 2} ) ~=~
left [ 1 +2 ( 1-e sup {- lambda over n} ) ~cdot~
sum from j=1 to {  [ n-1 over 2 ]} ~
1 over {1-e sup {- lambda over n sup 2} ~ cos~
{2 pi j} over n} ~+~ O(1) right ] sup -1
~.
.EN
.DE
Expanding in powers of $1 over n$,
.DS 2
.EQ (6.28)
1 over {1 -e sup {- lambda over n sup 2} ~
cos~ {2 pi j} over n} ~=~ n sup 2 over {2 pi sup 2 j sup 2 + lambda}
~+~ O (1) ,~~~ 1 ~<=~ j ~<=~ left [ n-1 over 2 right ]
~,
.EN
.DE
the $O(1)$ term being uniform in $j$.
Hence
.DS 2
.EQ (6.29)
sum from j=1 to {[ n-1 over 2 ]} ~
1 over {1-e sup {- lambda over n sup 2} ~
cos ~ {2 pi j} over n} ~=~ n sup 2 ~
sum from j=1 to {[ n-1 over 2 ]} ~
1 over {2 pi sup 2 j sup 2 + lambda} ~+~
O(n)
~.
.EN
.DE
We conclude from (6.27) and (6.29)
that
.DS 2
.EQ (6.30)
lim from {n -> inf} ~ f ( e sup {- lambda over n sup 2} ) ~=~
left [ 1 + lambda over pi sup 2 ~ sum from j=1 to inf ~
1 over {lambda over {2 pi sup 2} + j sup 2} right ] sup -1 ~=~
{tanh sqrt size 6 {lambda over 2}} over {sqrt size 6 {lambda over 2}} ,~~~
lambda ~>=~ 0
~.
.EN
.DE
Now
$tanh~ {sqrt size 6 {lambda over 2}} over {sqrt size 6 {lambda over 2}}$
is the Laplace transform of
$4 ~ sum from n=0 to inf~ e sup {-2 pi sup 2 (n + 1 over 2 ) sup 2 x}$
[16, p. 294, formula 8.51] and (6.22)
follows from (6.30) by the Continuity Theorem.
.H 1 "Bounds for E(T)"
In the previous sections we obtained very precise
asymptotic results for some special classes of groups.
In this section we consider bounds for $E(T)$ valid for
all finite groups $G$.
.P
The bounds are given as
functions of $| G |$.
We use results of Mazo on random walks on graphs [15].
Let $scrG$ be a finite connected graph with nodes
$1,2,.., n$.
The nodes are considered as states of a Markov chain
with transition probabilities $p sub {i j}$.
It is assumed that the chain is irreducible,
i.e. any node
can be reached from any other one in a
finite number of steps with positive probability,
and all $p sub {i i} ~=~ 0$.
Let $n sub {i j}$ be the expected number of steps
required to go from $i$ to $j$, and define
.DS 2
.EQ (7.1)
N ~=~ 1 over {n(n-1)} ~ sum from {i = 1} to n ~
sum from {pile {j=1 above j != i}} to n~
{n sub ij}~.
.EN
.DE
As a special case, let $p sub ij~=~0$ if $i$ and
$j$ are not connected and $p sub {i j} ~=~ 1 over scrL sub i$
if $i$ and $j$ are connected, $scrL sub i$ being the number
of edges leaving node $i$.
We refer to this chain as random routing.
The following lower bound holds for $N$.
.sp
.I
Theorem\ 7.1.
i)\0 $N ~>=~ n over 2$, equality holding 
if and only if
$scrG$ consists of
$n$ nodes placed consecutively along a circle
and one moves
deterministically from one node to the next.
ii)\0 For random routing $N ~>=~ n-1$, equality holding
if and only if $ scrG$ is the complete graph on $n$ nodes.
.R
.P
The above results have direct applications to random
walks on a finite group $G$.
The assumptions on $scrG$ translate to:
$mu (e) ~=~ 0$
and $OMEGA$ generates $G$.
We have $1 over n-1 ~ sum from {{i = 1} from {size 8 {i != j}}} to n
~ size 10 {n sub {i j} ~=~ E(T)} $ for all $j$, where $n ~=~ | G |$, so that
$E(T) ~=~ {| G | -1} over {| G |} ~ N$.
Under these assumptions on $mu$, Theorem\ 7.1
yields the following result.
.sp
.I
Theorem\ 7.2.
i)\0$E(T) ~>=~ | G |~-~1$, equality holding if and only if $G$ is cyclic
and $mu (g)~=~ 1$ for some generator $g$ of $G$.
ii)\0If, in addition to the above assumption on $mu ,~~ OMEGA sup -1 ~=~ OMEGA$
and $mu$ is constant on $OMEGA$, then
$E(T)~>=~( | G | -1 ) / | G |$,
equality holding if and only if $OMEGA ~=~ G- "{" e "}"$.
.R
.P
We remark that all the random walks considered in sections\ 5 and 6
satisfy the conditions of Theorem\ 7.2 ii).
The example $p sub 12 ~=~ p sub 21 ~=~ 1- epsilon$, $epsilon ~->~ 0$,
shows that $N$ can be made arbitrarily large for
$n ~>~ 2$, thus ruling out an upper bound for
$N$.
However, in case of random routing,
Mazo [14] obtained the following upper bound.
.sp
.I
Theorem\ 7.3.
Let $d~=~$\ diameter of $scrG$, $scrL sub M ~=~max~ scrL sub i$,
$scrL sub m ~=~ min~ scrL sub i $.
Then
.DS 2
.EQ (7.2)
N ~<=~ {2 scrL sub M sup 3/2} over {scrL sub m sup 1/2} ~
(1+d) n
~.
.EN
.DE
.R
.P
In [15] an example is given for which $N ~>=~ cn sup 3$
as $n -> inf$, $c$ a positive
constant independent of $n$.
Using (7.2), we prove
the following result.
.sp
.I
Corollary:
.DS 2
.EQ (7.3)
N ~<=~ 6 left ( {scrL sub M} over {scrL sub m} right ) sup 3/2
~ n sup 2
~.
.EN
.DE
In particular, if all $scrL sub i$'s are equal,
then
.DS 2
.EQ (7.4)
N ~<=~ 6 n sup 2
~.
.EN
.DE
.R
.P
Observe that, for random walks on finite groups
satisfying the conditions of Theorem\ 7.2 ii), all $scrL sub i$'s
are equal.
Hence
.DS 2
.EQ (7.5)
E(T) ~<=~ 6 | G | sup 2
~.
.EN
.DE
.P
As shown in section\ 6, for the simple walk on a cyclic group
$E(T) ~wig~ 1 over 6 | G | sup 2$.
Thus the exponent 2 in (7.5) is best possible.
.sp
.ul
Proof of Corollary:
Let $p,q$ be two nodes of $scrG$ which can be linked
by $d$ edges but no fewer.
We then have $d+1$ nodes $p~=~p sub 0 , p sub 1 , "..", p sub d ~=~ q$
with $p sub i$ connected to $p sub {i + 1}$, $0 ~<=~ i ~<=~ d-1$.
Let $r$ be any node of $scrG$ which is connected to some
$p sub i$ and let $j$ be the smallest value of
$i$ for which this occurs.
$r$ is not connected to $p sub k$ for
$k ~>~ i  + 2$, otherwise we can replace
$p sub j , p sub {j+1}, .., p sub k$ by $p sub j p sub r p sub k$
in the above chain to produce one with fewer than $d$ edges linking
$p$ to $q$.
It follows that any node of $scrG$ is connected to a
most $3~ p sub i$'s.
Hence in counting the nodes connected to $p sub i ,~ 0~<=~ i ~<=~
d$, any node of $scrG$ is counted at most 3\ times, so that
.DS 2
.EQ (7.6)
(d +1) scrL sub m ~<=~ 3n
~.
.EN
.DE
Inequalities
(7.6) and (7.2) give (7.3).
.ls 2
.PH ""
.bp
.ce
.B
REFERENCES
.R
.sp
.AL 1
.LI
D. Aldous, Markov chains with almost exponential
hitting times, Stochastic processes and their
applications, \f213\f1(1982), 305-310.
.PH "''R-\\\\nP''"
.nr P 1
.LI
D. Aldous, Random walks on finite groups and rapidly
mixing Markov chains,
in
.ul
Se\*'minaire de Probabilite\*'s XVII,
Lecture Notes in Mathematics #986, Springer 1983.
.LI
R. Aleliunas, R. M. Karp, R. J. Lipton,
L. Lova\*'sz,
C. Rackoff, Random walks, universal
traversal sequences, and the complexity
of maze problems,
pp. 218-223 in Proc. 20th IEEE
Found. Comp. Sci. Symp.,
IEEE, New York 1979.
.LI
H. Boerner, \f2Representations of Groups\f1, North Holland Publishing
Co., 1963.
.LI
L. Breimann, \f2Probability\f1, Addison-Wesley Publishing Co.,
1968.
.LI
A.\ R. Calderbank, P.\ Hanlow, and D. B. Wales, A ratio of character
values arising in the analysis of random shuffles,
unpublished manuscript.
.LI
C. W. Curtis and I. Reiner, \f2Representation Theory of Finite
Groups and Associative Algebras\f1, Wiley-Interscience, 1962.
.LI
P. Diaconis, \f2Group Theory in Statistics\f1, in preparation.
.LI
P. Diaconis and M. Shashahani, Generating a random permutation
with random transpositions, Z. Wahrscheinlichkeitstheorie u. verw. Geb. \f257\f1 (1981),
159-179.
.LI
F. G. Frobenius, U\*:ber die Charakteren der symmetrischen Gruppen,
Berliner Berichte (1900), 516-534.
.LI
I. J. Good, Random motion on a finite Abelian group, Proc. Cambridge
Phil. Soc. \f247\f1 (1951), 756-762.
.LI
E. J. Hannan, Group representations and applied probability,
J. Appl. Prob. \f22\f1 (1965), 1-68.
.LI
R. E. Ingram, Some characters of the symmetric group,
Proc. A.M.S. \f21\f1 (1950), 358-369.
.LI
G. D. James, \f2The Representation Theory of the Symmetric
Groups\f1, Lecture Notes in Mathematics 682, Springer-Verlag 1978.
.LI
J. E. Mazo, Some extremal Markov chains, Bell System
Tech. J. 61 (1982), 2065-2080.
.LI
F. Oberhettinger and L. Badii, \f2Tables of Laplace Transforms,\f1
Springer Verlag, 1973.
.LI
J. P. Serre, \f2Linear Representations of Finite Groups\f1, Springer,
1977.
.LI
F.\ Spitzer,
.ul
Principles of Random Walk,
Van Nostrand 1964.
.LI
A. J. Wasserman, Automorphic actions of compact groups on
operator algebras, Ph.D. thesis, Univ. of Pennsylvania, 1981.
.LE
.PH ""
.bp
Proposed running head:
.sp 1i
.ce
.B
.S 12
Random Shuffles
.R
.S 10