The range order of a product of i transformations from a finite full transformation semigroup
- PDF / 181,895 Bytes
- 6 Pages / 468 x 684 pts Page_size
- 96 Downloads / 157 Views
RESEARCH ARTICLE
THE RANGE ORDER OF A PRODUCT FROM A FINITE
OF
i
TRANSFORMATIONS
F U L L TRANSFORMATION
SEMIGROUP
Peter M. Higgins Communicated
by N.R. Reilly
Let
T denote the full transformation semigroup on a finite set n {l,2,...,n}. Denote the range of u e T by Vs. Let X. be n 1 the random variable with value n-llv~l~2...ui I t where C~l,C~ 2 . . . .
,c~ i
member of
T
allowed). x2
are
are
n In
1 - e
randomly
chosen
is equally
likely
-i
members
of
T
(meaning
n
that
to be chosen and repetitions
each
are
[2 ] it was sho_w~ that the limiting means of X1 (e---l) and 1 - e respectively. The natural
extension
of this result is g i v e n
and take
M 0 = i.
below.
Denote
lim
EX i
by
and
Mi
-S. THEOREM
Mi+ 1 = 1 -
and in addition
We approach
1.
for
all
M. ~ 2/i
as
i ยง ~.
chosen
exs,
from
IVUl~2...Ui+ll
number of non-empty balls
i
= O,
the proof by first supposing
been randomly value of
e
Tn
we obtain
n
and
m
by
From
< 1/n
= r. as
The X,
in w h i c h
the r
[i, Ch. II, Sec.ll,
that for
=: Pm(r,n)
=
(_l)v(n-m) (n-m-9) n and
m-i
respectively
Pm l (r,n-l)
= m
() ~n
r Pm(r,n )
n
31
(i)
.
r
n-I
-
21.
el,~2,...,u i have
IV~l~2...~il
boxes.
V=0 n
, VarX.
in a ball tossing experiment
1 ( m K n, P ( X = n-m)
Replace
...
then has the same distribution
boxes
n-m (n) X
2,
that
and that
are tossed at random into 8 and 9]
1,
in
(i) to obtain (2).
HIGGINS
Sum equation
(2) o v e r
m
to g e t n Z m Pm(r,n), m= 1
i = In (n-~)r-
o r in o t h e r w o r d s E X = n - n(n-l) r n A l l the
factorial
manner.
moments
re(m-l) n(n-l)
1 n (n-l)
1
Since
Y-n-X
can b e
calculated
in t h i s
In p a r t i c u l a r
Pm-2(r'n-2)
=
of
(3)
E{Y(Y-I)}
VarX
)r
Pm(r,n) , whence
n
( n )r ~
% m (m-l) P m (r'n) m=l
= n(n-l)
= VarY
( n ~
(n-2)r n
we g e t
V a r X = n(n-l)
(n-2)r + n ( n - l ) r n n
_ n2(n-l)2r n
or VarX - n((l
- 2)r n
_
terms
Note the
first a n d
third
negative
while
second
the
V a r X < n,
independently
The
statement
first
result
follows
the s t a t e m e n t
from
+
is b o u n d e d
o f the r a n k
a n d the
hand side
of
(4)
(4) are
Thus w e h a v e
r .
VarX. < i/n. i
Therefore
can now be proved.
i = k - i,
Inequality
(i - 2) r n
-
a b o v e b y one.
(3) u p o n p u t t i n g for
(i - l ) r n
o f the r i g h t
of t h e t h e o r e m
holds
By Chebyshev's
(i - l) 2r) n
r = n. k ~ i.
fact t h a t
Assume Let ~
For
i = 0 the
inductively
e, 6 > 0 < i/~n
that
b e given.
it f o l l o w s
Xk t h a t for
n
sufficiently
large
The t h e o r e m
is n o w
obtained
E(Xk+llXk
~)
-
=
arbitrarily
=
small
1
(i
-
interval
P(I~_
by noting
l)nX (~
where
- ~_I9 < 6) > 1 - e.
that X
almost
- 6, M k + 6)
32
surely
lies
for s u f f i c i e n t l y
in the l a r g e n.
HIGGINS
F r o m w h a t has b e e n p r o v e d x > 0
w e see that the s e q u e n c e
decreasing of
a n d the fact t h a t
sequence -x = 1 - e
f(x)
which must
iM. (i
Data Loading...
