AN !?£‘-!ERS{ON ALGORHHM FOR
ONEeDIMENSiGNALi F EXPANSE ONS

 

Mains“: tie Degr 05951.0.
w MUSELUR “RES”
800?? {ES WERE?!
1939

IHE$l$

This is to certify that the
thesis entitled

AN INVERSION ALGORITHM FOR
ONE-DIMENSIONAL F-EXPANSIONS

presented by

Scott Bates Guthery

has been accepted towards fulfillment
of the requirements for

Probability

 

. ) f '

,1
: [“4 [121141ng
./ Major professor /

/
DateJ/szf" & f /f{/

0-169

7;! 74- M J-‘iL. (fixm '1‘
*5 n. -..- , 5

Michigan State
University

       
   

 

   
   
      

   

" amame By
HMS G SUNS' 1
300K BINDERY INC.

| IBMRY HINDI-g
I

ABSTRACT

AN INVERSION AlGORITHM FOR
ONE-DIMENSIONAL F-EXPANSIONS

By

Scott Bates Guthery

This paper presents an algorithm for the construction of a
function, whose fractional part preserves a given Lebesgue equi-
valent measure on (0,1), from a summation representation of the
Radon-Nikodym derivative of the given measure. Examples are
given and the technique is used to construct a function whose
associated f-expansion stochastic process has the same finite

dimensional distributions as a given stationary process.

AN INVERSION ALGORITHM FOR
ONE-DIMENSIONAI.F-EXPANSIONS

BY

Scott Bates Guthery

A THESIS
Submitted to
‘Michigan State University

in partial fulfillment of the requirements
for the degree of

DOCTOR 0F PHIIDSOPHY
Department of Statistics and Probability

1969

gems

4/ 2.3-1-“3

To Peter

ii

ACKNOWIEDGMENTS

I would like to thank Professor John R. Kinney for his
patient guidance before and during the preparation of this
dissertation. His insights in information theory, once decoded,
have served to greatly expand my appreciation of the field.

I would also like to thank Mrs. Noralee Barnes for her
help in preparing the manuscript, the Department of Statistics
and Probability for financial support during my graduate career,
and Messrs. Allan Oaten and Michae1.Waterman for many helpful

conversations.

iii

Chapter

.I.

II.

III.

IV.

TABLE OF CONTENTS

INTRODUCTION
1.1 Background
1.2 Terminology

THE INVERSION AIGORITHM

2.1 Definitions and Basic Relations

2.2 Conditions for Valid and Ergodic
Expansion Pairs

2.3 Rokhlin's Formula

EXAMPLES

3.1 Lebesgue Measure

3.2 Generalizations of the Continued
Fraction

3.3 Miscellaneous Functions

ASSOCIATED PROCESSES WITH FINITE MEMORY

4.1 Inversion Using a.Markov Process

4.2 The Uniqueness of the Construction
for Lebesgue Measure

ASSOCIATED PROCESSES WITH INFINITE MEMORY

5.1 Approximating an Arbitrary Stationary
Process

5.2 A Representation Theorem

BIBLIOGRAPHY

iv

Page

12
15

16
16

17
21

23
24

27

29

29
33

37

I. INTRODUCTION

This paper examines a variety of one-dimensional f—expansions
along with their invariant measures and associated stochastic pro-
cesses. To introduce the material, we present the following brief

summary of relevant work in the field.

1. Background

 

The classical f—expansion is the continued fraction. Beginn-
ing with x e (0,1) and f(x) = llx and letting [ ] denote the
greatest integer function and < > the fractional part, we use the

expansion algorithm:
_ '1 _ -1
a1(x) - [f (x)], r1(x) -<f (x)>
and for i 2 1, if ri(x) # 0, then

ai+1<x)=[f'1(ri<x>>] and r (x) =<f'1<ri<x)>>.

i+l

Setting pn(x) f(a1(x) + f(a2(x) +;..+ f(an(x))

1

 

1
a1(") + a2(x) +

 

.+ 1
an (X)

 

we have x = pan) if rn(x) = O and otherwise x = 1im pn(x).
n—m

Properties of this expansion have been studied extensively
and an excellent survey is provided by Khinchin (6 ).

Let us set
(0,1)f = {x‘rn(x) 3‘ o for all n}

and note that since we have excluded only a countable number of

elements of (0,1), we have
1((0.1)f) = 1

where A is Lebesgue measure. Any non-atomic probability measure
on (0,1) induces, in the obvious way, a probability measure on
(0’1)f' The underlying c-field is, in all cases, assumed to be
the Borel field B and almost everywhere (a.e.) statements are
made relative to A-

In 1951, RyllANardzewski (10) considered the transformation
T(x) =<1/x> on (0,1) and found that the measure w on (0,1)

defined by

l 1

dw/dx = log 2 (x+1)

was preserved by T and that T was ergodic with respect to w.

By noting that for a.e. x 6 (0,1)
n
T (x) = rn(x>,
where we let ro(x) = x, and hence

an+1(x) = [l/T“(x)] ,

he was able to deduce many of the measure theoretic prOperties of
the continued fraction expansion through applications of the
individual ergodic theorem.

For example, to calculate the frequence of the digit p in

the continued fraction expansion of a number x in (0,1)f, one

defines
1 q = p
I (q) =
p 0 q 1‘ p
and sets
11
F(p.X) = lim- 2 I ( (X))
n—m k=1 P ak
1 “‘1 k
= lim- 2 1 ([l/T (x)]).
new k=0 p

Using the individual ergodic theorem, one then has

 

1 1 “'1 (11/ k 1 t /
im'-' 2 T ( ) ) = I ( 1 t )dw(t) a.e.
nam n k=O p x J g p 1
1 1
= 1 I (E ltl) dc
log 2 O (t+1)
. 1 $22.2.

 

log 2 log p(p+2)

That is, for a.e. x in (0,1) the frequence of p in its con-

2
1 log fl .
log 2 p(p+2)

Then, in 1957, Renyi (8) extended this result to the work

 

tinned fraction expansion is

of Everett (3) and Bissinger (1) who had investigated the use
of an arbitrary monotone function in the expansion algorithm and
conditions under which x = 1im pn(x). Such functions were said

11—100
to be valid for f-expansions.

Citing the following conditions on f:
Al) f(1) = 1;
A2) f(t) is non-negative, continuous, and strictly
decreasing for 1 s t s N and f(t) = O for
t 2 N where N > 2 is an integer or +m;

A3) “(1:2) - £(c1)| s \t2 - t1| for 1 s t1 < t2 and

|f(t2) -f(t1)|<‘t2-t1‘ if 'r-e<t1<t2

where T is the solution of the equation
1 +-f(T) = T and O < e < r is arbitrary;
B1) f(0) = 0;
B2) f(t) is non-negative, continuous, and strictly
increasing for O S t s N and f(t) = 1 for
t 2 N where N > 1 is an integer or +n;

B3) |f(t2) --f(t1)‘ < |t2 - tI‘ for 0 s t < t

1 2;

and a) if Hn(x,t) = g; f(a1(x) + f(a2(x) +...+ f(an(x) + t)))

then

sup H (x,t)
0<t<1 n

inf H (x,t)
0<t<1

SC<4¢D

where the constant C 2 1 depends neither on x
nor on n;

Renyi proved

Theorem 1.1. If f satisfies conditions A or B then f is valid
for f-expansions. If f further satisfies condition C, then there
exists a unique probability measure w on (0,1) such that:

i) m is equivalent to 1;

-1
ii) w is preserved by T(x) =«<f (x)>;

iii) T is ergodic with respect to w;

and iv) C"1 s gfi-S C.
This theorem defines an entire class of functions whose measure
theoretic f-expansion prOperties can be investigated using the
technique introduced by Ryll-Nardzewski, viz., the individual
ergodic theorem. However, since it utilizes a non-constructive
proof, it leaves open the problem of finding the measure w for
each function in the class. This problem has been solved in only
a very few cases and is the primary impetus behind the present
work.

Next, in 1960, Rokhlin (9) obtained an approximate rate of
convergence for the f-expansion of numbers using the functions and

measure described by Renyi. Defining m = f"1 and

Bub!) = {ylai(y) = a100, i = 1(1>n}
he proved

Theorem 1.2. If f satisfies A and C or B and C and log ‘m"
is Lebesgue integrable on (0,1), then

log w(Bn(x)) log 103nm) 1
h(T) = -lim n = -lim =J” log‘cp'(t)‘dw(t) a.e.
0

11-40: M

 

 

The number h(T) is called the entropy of the endomorphism T

and the theorem says that

103nm) 2: e‘m‘m.

Finally, in 1966,Kinney and Pitcher ('7) considered the

discrete stochastic process [ai,v,(0,1)f] associated with an

f-expansion formed by the coefficients (ai) of an f-expansion
and a measure v on (0,1). Using this construct, theywere able
to calculate the dimension of some sets defined in terms of f-
expansions and connect certain properties of the processes with

properties of the f-expansions.

2. Terminology

Suppose we consider the following conditions on a function

A') f(1) = 1; f(t) is non-negative, continuous and de-
creasing for 1 s t s N; and f(t) = 0 for t 2 N
where N > 2 is an integer or +w;

B') f(0) = 0; f(t) is non-negative, continuous, and in-
creasing for 0 s t s N; and f(t) = l for t 2 N
where N >11 is an integer or '+n.

If f satisfies A' let us define
-1
f (x) = g1b{t‘f(t) s x}
and if f satisfies B' let us define
-1 _
f (x) - glb{t|f(t) 2 x}

for all x 6 (0,1). With these definitions, we see that an f
which satisfies A' or B' may be used in the expansion algorithm
and that the set (0,1)f is well-defined. Such a function will
be said to be available for f-expansions. Obviously, any function
which satisfies A or B satisfies A' or B' reapectively. Note also

that f"1 is continuous at all but at most a countable set of

points and that except for these points f-1(x) is that unique
y such that f(y) = x.

Suppose now that f is available for f—expansions and that
w is a x-equivalent measure on (0,1). If the transformation
T =1<fm1> is an endomorphism on ((0,1)J3,w); i.e., T is measurable
and w(T-]‘B) = w(B) for all B 6 B; then we shall call the pair
(f,dw/dx) an expansion pair. The measure w will be said to be
invariant with respect to or preserved by f. If an expansion
pair (f,h) is such that f is valid for f-expansions, the pair
is called a valid expansion pair. Similarly, if T is an ergodic
endomorphism the pair is called an ergodic expansion pair. In
this terminology Renyi's theorem states that if f satisfies A
and C or B and C then there exists a unique x-equivalent probability

1 s dw/d), s c and (Law/cu) is a valid,

measure m such that C-
ergodic expansion pair.
It has been found that many functions may be invariant with
reapect to the same measure. In the following we will study this
relationship by providing an inversion algorithm which produces a
variety of functions which preserve a given x-equivalent measure.
Conditions will also be presented which insure that the resultant
expansion pairs are ergodic and valid. As a result we will have
a number of examples of the results of Renyi's theorem and, there-
fore, functions whose f-expansion properties can be investigated
with the individual ergodic theorem. Finally, we note that just
as many functions preserve the same measure, many expansion pairs
may be associated with the same stochastic process. We shall close

by showing that the inversion algorithm may also be of use in

studying this relationship.

II. THE INVERSION ALGORITHM

The inversion algorithm given below can produce expansion
pairs from a summation representation of the Radon-Nikodym derivative
of a x-equivalent measure. Conditions are also given on the
representation which insure that the resultant expansion pairs are

valid or ergodic.

1. Definitions and Basic Relations
Let g be an a.e. non-negative Lebesgue integrable function
on [0,N) where N is an integer 2 2 or +m. Set
C(x) =‘I g(t)dt for x E [0,N) and assume 1im C(x) = 1. Then
G is an a.e. differentiable nondecreasing fuhZIion from [0,N)

onto [0,1) which is absolutely continuous On every finite sub-

interval of [0,N).
N-l
Next we set h(x) = Z g(x +'k) for x 6 (0,1) and assume
k=0
that h is positive over its domain of definition. Since
1 N
g h(t)dt =4; g(t)dt = 1, h is a probability density which deter-
mines a probability measure w on the Borel subsets of (0,1)
which is equivalent to Lebesgue measure. If we now set
x
H(x) =‘£ h(t)dt for x 6 [0,1], then H and H-1 are 1-1

strictly increasing a.e. differentiable transformations on [0,1].

Finally, we define

fU(x) = H-1(G(x)) for x 6 [mm

and
fD(x) = H'la - G(x-1)) for x e [1,N+1).

We note immediately that fU is an a.e. differentiable
nondecreasing function on [0,N) such that fU(0) = 0 and
1im fU(x) = 1. On the other hand, fD is an a.e. differentiable
:Eflincreasing function on [1,N+l) such that fD(1) = l and

lim f (x) = 0. Let us complete f and f by setting
x~N+1 D U D

0 x < 0
fU<x> -
1 x 2 N
and
x < 1
fD(x> =
O x 2 N+1.

It is easily seen that fD and fU satisfy A' and B' respectively

so that both are available for f-expansions.

In the following, we shall let

ch(x> = £51m. ch<x> = £61m,
TD(X) = <ch(X)>. TU(X) = <ch(X)>
and R(x) = H-1(l - R(x)).

Note that 9D, mu, TD, and T are a.e. differentiable functions

U
on [0,1] and that R is a strictly decreasing a.e. differentiable
function on [0,1]. Before proceeding to discuss the expansion

properties of fU and fD, we present the following lemma concern-

ing elementary relations between them.

10

Lemma 2.1. The following relations hold:

2.1.1 fU(x) R(fD(x+l)) fD(x) = R(fU(x-l))

2.1.2 ¢N(X) mb(R(x)) - l mb(x) = mU(R(x)) + 1

2.1.3 TU(x) TD(R(x)) TD(x) = TU(R(x))

2.1.4 fé(x) g(x)/h(f (x)) a.e. f6(x) -g(x-1)/h(fD(x)) a.e.

2.1.5 mé(x) m6(R(x))R'(x) a.e. mfi(x) m5(R(x))R'(x) a.e.

2.1.6 R(x) = R'1(x)
2.1.7 R'(x) = -h(x)/h(R(x)) a.e.
Proof.

2.1.1 and 2.1.6 follow directly from the definitions of fU, fD’

and R. For 2.1.2 we have ¢U(x) g1b{t‘fU(t) 2 x}

glb{t|R(fD (t+1)) 2 x}

g1b{t| fD(t+1> 2 R(x)}

glb{t-1|fD(t) 2 R(x)}

g1b{t|fD(c) 2 R(x)} - 1

ch(R(X)) - 1

and similarly for mD(x). 2.1.3 follows directly from 2.1.2 since

TU(X) = <ch(X)> = <ch(R(x)) - 1>

= <ch<R<x>>> = gas»

and similarly for TD(x). For 2.1.4 we use the differential form

df-1(u) = du/(§§(f-1(u))) to obtain

11

rag.) = d H-1(G(x)) g(x)/<§—:(H'1<c(x>))

g(x)/h(fU(x)) a.e.
and

-g<x-1>/<j—fi-(H‘1(1 - soc-1m)

f6(x) = d H-1(1 - G(x-1))

= -g(x-1)/h(fD(X)) 8-6.

2.1.5 is simply an application of the chain rule to 2.1.2 with
the proviso that the equality holds only where both derivatives
exist. Finally, 2.1.7 follows again from the above mentioned

differential form since
R'(x) = d H'la - R(x)) = -h(x)/h(R(x)) a.e.

That (fU,h) and (fD,h) are, in fact, expansion pairs

is shown by

Theorem 2.2. The transformations TU and TD are endomorphisms
on ((0,1) ,B,w) .

aegi-

Since the inverse image of any interval is at most a countable
union of intervals under either transformation, each is measurable

and it is sufficient to prove that w(T-1(0,a)) = w((0,a)) for

a 6 (0,1). If we let f = fU, then we have

12

_1 N-l raw) N-l
(Dav (0,00) = 2 J“ h(t)dt = 2 H(f(k+oz)) - H(f(k))
k=0 f(k) k=0
11-1 1+0; 1: N-l ids
= 2 J; g(t)dt -fg<t>dt) = 2 £ g(t)dt
k=0 0 k=0
N-loz aN-l
= 2 £g(t+k)dt =£ 2 g(t+k)dt
k=0 k=0
CY

=£homc=wumm>

so that TU preserves m.

If, on the other hand, we let f = fD, we have

N f(k)

N
h(t)dt = 2 H(f(k)) - H(f(k-|o))

w(TI-)1(0.oz)) = 21] 1
k: (W) k:

N (khx-l k-l )

:51 2E g(t)dt ~£ g(t)dt

‘ N-l kw N-l '

2 i g(t)dt = 2 Ego-Atom:
k=0 RFC

a N‘]. 0!
= 2 g(t+k)dt =j‘ h(t)dt = w<<0»01>>
k=0 0

so that TD preserves w and the proof is complete.

2.2 Conditions for Valid and Ergodic Expansion Pairs

If we now consider the following condition on the function

g:
D1) g(x) > O a.e.
and
N-l
D2) g(t) < inf 2 g(x+k) for all t E (0,N);
0stl k=0

we have

13

Theorem 2.3. If g satisfies conditions D then (fU,h) and

 

(fD,h) are valid expansion pairs.
Proof.

Clearly fD satisfies Al, fU satisfies Bl,and D1 implies

A2 and B2 respectively. Since lfé(x)‘ = h?%1%%)) a.e. and
U
y = gSX'lz . '
‘fD(x)| h(fD(x)) a.e. condition D2 guarantees that ‘fU(x)‘ < 1

a.e. for x E (0,N) and ‘f6(x)| < 1 a.e. for x E (1,N+1).
Therefore by the mean value theorem fD satisfies A3 and EU

satisfies B3. Since fD meets conditions A and fU meets con-
ditions B, by Theorem 1.1 both are valid for f—expansions.

To show that the pair (fU,h) and (fD,h) are ergodic
expansion pairs, we can either show that ft and fD satisfy
Renyi's condition C or demonstrate directly that TU and TD are
ergodic endomorphisms. The first method is, in general, very

difficult but the following lemma can be of help in some Special

cases .

'Lgmma‘ggg. If a function f on [0,N) satisfies
E1) o<els|i'(x)|sez<1 for xE[0,N)

and E2) f' Lipschitz of order 1

then f satisfies condition C.

12:22:.

If 0 s t1 < t2 s N, then from (i) we have that
|f(t2) - f(t1)\ s ezlt2 - t1|
and from (ii) we have that

sup f'(t) - inf f'(t) S‘M(t2 - t

)
tr<b<t2 tI<t<t2 1

where M

sup f'(a
0<t<1

inf f'(a
0<t<1

1

1

is a constant independent of t

+f (a2+. . .+f (an+t))) -

14

l

+f(a2+. . .+f(an+t)))

1:

sup f'(a1+f(a2+...+f(an+t))) - inf f'(a

_ 0<t<1

14| f(a2+f(a3+. . .+f(an+1)))

S

inf f'(a

0<t<1 1

and t Now,

2.

+f(a +. . .+f(a +t)))
0<t<1 1 2 "

+f(a2+;..+f(an+t)))

- f(az+f(a3+...+f(an)))\

 

e1

1462‘ f(a3+f(a4+. . .+f (an+l))) - f(a3+f (a4+. . .+f (an)))\

S

 

therefore,

sup H (x,t)
0<t<1

0<t<1

 

e1
-1

 

sup 'df f(a1(x) +-f(a2(x)

= 0<t<1
inf Hn(x,t)

inf g—t f(a1(x) + f(a2(x)
0<t<1

+°.’ .+ f(an(X)+t)))

+...+'f(an(x)+t)))

 

 

 

su f' a (x) +-f a x +u..+ f a x 4t
H 0631 (j (j+1() (n() )))
= inf f(a (x) + f(a (x) +...+ f(a (x)+t)))
j l 0<t<1 j j+1 n
n Meg-1
II (1+ )
j=l 1
m Meg-1
s n (l + ) = Cl< m
j=l 61
since, by theorem 8.6.1 of Hille (4.), the infinite product con-
j-l
wMez
verges if 2 e converges which it obviously does.
j=l l

. I
By noting that fU(x) = g(x) a.e. and f6(x) = -g(x-1) a.e.

when w

is Lebesgue measure, we see that the conditions of this

15

lemma are reduced to conditions on the input function g.

3. Rokhlin's Formula

We conclude this chapter with

 

Theorem 2.5. If fD and fU satisfy A and C and B and C

respectively, then h(TU) = h(TD).

Proof.

1 1
h(TU) =£ loglcpl'l(x)‘h(x)dx =J; loglcp5(R(x))R'(x)‘h(x)dx

0
=1; loglcplgocm'<R<x>)|h<R<x))R'<x>dx

l 1
g log|m5(x)|h(x)dx +~£ log‘R'RCx)|h(x)dx

1
h(TD) +£ log |M§fgl|ux>dx

1 1
h(TD) +£ loglh<R(x)>lh(x)dx -j log‘h(x)‘h(x)dx
0 ,

o 1
h(TD) +j1‘ log‘h(x)|h(R(x))R'(x)dx -f log‘h(x)‘h(x)dx
o

= h(TD).

III. EXAMPLES

In this section we present examples of the use of the inversion

algorithm which include generalizations of some known expansion pairs

along with some new ones.

1. Lebesgue Measure
Perhaps the easiest and most interesting measure to invert is

Lebesgue measure which has density function h(x) = 1. If we, for

N-l
example, have non-negative constants pk such that 2 pk = l
k=0
then we set g(x) = pk for k s x < k+l and k = O,l,...,N-l.
Then, since H(x) = H-1(x) = x, we have
} [x]-l
f (x) = C(x) = g(t)dt = 2 p + <x>p
U o k=0 k [x]
and
[x]-2
f (x) = 1 - G(x-l) = 1 - z p - <x>p .
D k=0 k [x] 1

A well-known special case of this expansion is obtained by setting

pk = fi' for k = O,l,...,M-l, from which we get

= Ix] +<x> =
fum M M

2|x

and

_ x -1. <x> = _ Ell
fD(x) - l - M. ‘+'qq- l M .

These are called the M-adic expansions since they yield the expansion

of numbers base M.

16

17

Suppose now we insist that 01< 61 s pk s 62 < 1. Then by

noting that h(x) = 1 implies fé(x) = g(x) a.e. and
f6(x) = -g(x-l) a.e., it is easily seen that g satisfies condition

D and f satisfies condition C by Lemma 2.1. Therefore, fD and fU

n
satisfy the conditions of Renyi's theorem. Letting S = 2 p
n k=0 k
and S_1 = 0, we can compute their entrapy by Rokhlin's formula as

follows:
h(TD) = mu) =f logl q; (x>|dx = 2 i log rdx
O U n=0 n
n-l
N-l
= 2 (-1ng)(8 -S_)
“=0 n n n 1
N-l
= - l .
r120 pn 03 pm

2. Generalizations 2f the Continued Fraction

 

Another interesting family of f-expansions is provided by a
special case of a summation theorem involving the psi function.

Suppose bi’ i = l(1)n, are distinct constants not less than 1 and

where m 2 2 and p(x) is a polynomial of degree m-2 or less.
By the partial fraction theorem, we may write Un(x) as

ai

x-l-n-l-bi

vitae

U (x) =
n 1 l

where 2 a1 = 0. Then by a theorem cited by Davis (2 ) we have
m

E U (x) = -2 a‘i’(x+b.)
n=0 n i=1 i 1

18

9.

dx 1n T(x) for

where Y is the psi function defined by T(x) =

x > 0. We now set

g(X) = U[x] (<X>) = _.P_B)_

m
n (xiii)
i=1

and assume the Un(x) have been normalized so that

co co 1 m 1
J” g(t)dt = 2 j‘ Un(t)dt = -.2_ ai J‘ 1(t+bi)dt
0 n=00 1-1 0
m
= - 2 a1(ln F(l+b.) - 1n T(b.))
_ 1 1
i-l
m
= - 2 a1 1n b = 1
i=1 1
Since
on w m
h(x) = )3 g(x+n) = 2 U (K) = " Z ai T(X‘Fbi)
n=0 n=0 “ i=1
we have
x m x
H(x) =£ h(t)dt = - 2 a A ‘1’(t+b.)dt
._ i 1
1-1
m
= -iilai ln(F(x+bi)/F(bi)).
Now assume m is even, bi = bi-l + l for i = 2(2)m, and
that p(x+n) has been chosen so that ai = '81-1 for i = 2(2)m.
Then setting k = m/2 and c1 = a21_1 and d1 = b21_1 for

i = 1(l)k, we have

 

k (1"(x-l-di) f‘(diH)
H(x) = - 2 c 1n
i=1 i 11:11) T(x-l-di+l)

w

d

i
- Z c, 1n )
i=1 1 gt-I-di

 

19

If k=1,b=b1, and B=ln(1+%) then

H-1(x) = b exp(Bx - l)
and since
g(x) = [B(x+b) (x-l-b+l)]-1

we have

 

G(x) = 1 + 13'1 1:183:31).

Therefore, the two functions

x
x+b+l

 

_ -1 =
iU(x> -H (cm)

and

b
x+b-l

 

fD(x) = H-1(l - G(x-l)) =

form expansion pairs with the density function

l

W) "' W

Note that when b = l f yields the continued fraction expansion.
D
b (b1+1)

3
If k = 2, c1 = -c2, and B = ln(BI?g;:ES) then

Bx
b1b3(1 - e )

 

-1
H (X) = Bx
ble - b3

and since

(b3-b1) (2x-l-b3-l-b1-i-1)
g(x) = B (x-I-b 1) (x-l-b 1+1) (x4433) (x-l-bB-I-l)

 

1‘” l 1 1

- - ______.+.________
1 x+b1+1 (x+b3) (x+b3+1))

u
I
A

we have

20

_1 (x+b1)(x+b3+l)
G(x)= £g(x)dt= 1 +3 1:1(<x+b3 )(fib 1+1)).

 

Therefore the two functions

b1b3(b3- b1) + 12161123) (x+b1+1) - b3(x+b1)(x+b3+l)

{h(x) = (b1 :33) +b1(x+b1) (x4133+1) - b3(x+b3)(x+b1+1)

 

and

b1"1"i(b b3)

£11“) = b(x+b3- 1) (x4431) - b3(x+b1-1)(x+b3)

form expansion pairs with the density function

h - b

 

 

_ 3 l
h(x) ' B(x+b1)(x+b3) °
(b +1) (b +1)
Finally, consider the case k = 2, c1 = c2, and B = 1n( b b
l 3

Here we have

 

 

 

 

2 Bx
H—1(x) = /(b1"b3) +41’1":ie " (bf'ba)
2
and since
1 l 1 l l
g(x) = - —— - + - )
B(x+b1 x+b1+1 x+b3 x+b3+l
we have
_ (fib)®fi)
C(x) = 1 + B 1 1 3

“E (x+b 1+1) (x+b3+1)]'

Therefore the two functions

fU(x) = % J<b1-b3)2 + 4(b1+1) (133+1) (xi-b1) (xi-b3)(x-l-bl+1)-1(x+b3+1)-1--%-(b1+b3)

and

 

fD(x) = %J(b1-b3)2 + 4b1b3(x+b1)(xi-b3)(x-l-b1+l)-1(x+b3+l)-1-%(b1+b3)

21

form expansion pairs with the density' function

h +-2x +-b

( l 3).
(X'Po 1) (x+b3)

l
B

 

h(X) =

3. Miscellaneous Examples

 

Using the inversion algorithm, available expansion pairs are
at least as numerous as the entries in various series summation
tables such as Jolly (5) or Davis (2).

For example, consider the use of the familiar exponential

 

 

series
a k
a ax a sax)
( a )e - ( a ) z k!
e -1 e -1 k=0

Here we let

and, therefore,

x [t]
x _g__ (a<t>)
G( ) (ea-1]; [t]! dt

1 [x] 2E (a<x>)[x+1]

( )3
ea_1 k=1 k! [x+l]!

 

 

where we ignore the summation term if 0 s x < 1. Next, since we

are setting

 

h(x) = (2 )ea"
e -l

we have

22

 

X 3X
a at -
H(x)= a je dt=(e—a—l).
e -1 0 e -l
Inverting H, we find
- l
H 1(x) = ;'10g((ea-l)x+l).

Therefore, we have

[x] k [x+l]
a 1 .§_ (§<x>)
108((e '1) (ea-1(k§1 kl + [x+l]! )) + 1)

tum = H‘1(c(x>>

1 [x] ak +18<x>)[x+'l]
-'a og<k§l kl [x+l]!

It-I'

+1)

and, similiarly,

[x-l] k [x]
= '1 _ l a _a_ _ 8(a<X>L
fD(x) H (l - G(x-l)) - a log(e - z k! [x]!

k=l

 

Another family of expansion pairs, which extends the above
Lebesgue family, is provided by picking {a1}:=0 where

O = a 1< a

= d
0 1 < a 1 an setting

<000<d
n-l n

h(x) = Bi ai_1 s x < ai’ i = l,2,...,n

n
such that Z 81(ai - ai_1) = 1. Then, if p1 > O for i = O,l,...,N-l

N—l 1
and 2 p = 1, we set
._ i
1-0
for a1 1 s <x> < oi. This family inverts easily and yields monotone

"broken line" functions.

IV. ASSOCIATED PROCESSES WITH FINITE MEMORY

In this section we present a sufficient condition for the use
of the inversion to construct an expansion pair whose associated
stochastic process has the same finite dimensional distribution
as a given stationary Markov process of finite multiplicity. In
a Special case this construction is also shown to be unique.

That there is no loss of generality in assuming the given

process is stationary is shown by

Theorem 4.1. If (f,dw/dx) is an expansion pair, then its
associated stochastic process, [ai,w,(0,l)f], is stationary.
222.

The result follows directly from
my, let (0,913) be a probability Space and T be an
endomorphism on the Space.

Then the random variables X and XoT are identically
distributed.

If B is a Borel subset of the real line, then

P[X e B] P({wIX(w) E 3})

P(T'1{w\x(w) e 3})

P({m"Tm' E [w‘X(w) E B}])
P<{w|xmw)> e 3})

P1X 0 T E B].
23

24

Since (f,dw/dx) is an expansion pair the transformation
T(x) = <f-1(x)> is an endomorphism on ((0,1)f,B,u>). Therefore,
by the Lemma, a1(x) = [f-1(x)] and ak(x) = [£‘1(Tkx)] for

k = 2,3,... all have the same distribution.

1. Inversion Using §_Markov Process

Suppose [xi,P30] is a stationary Markov process of finite
multiplicity T and state Space {O,l,...,N-l} such that

P[xj = ij, j = l(l)T] > O for all (i1,...,iT) 6 ST. For any

M 2 1 and (11,...,iM) e SM let us define

M
I (i ,...,i ) = 2 i N
M 1 M j=1 j

M‘j

and

F(i1,...,i ) = 2 P[xn = jn, n = 1(1)M]

M
where the latter summation extends over all (j1,...,jM) for which
... S - ... . '
IM(j1, ,jM) IM(11, ,iM) Let us further define
F(11,ooo’iM-1) = F(il,ooo,iM-1’-1) and F(-1) = 0.
Now suppose w is a x-equivalent measure on (0,1) and

X
1et h = dw/d) and H(x) =‘j h(t)dt as usual. For each
0

(11,...,iT) 6 ST, let J(i ..,iT) be the indicator function of

1"
the interval [H-ICF(i1,...,iT-l)), H-1(F(il,...,iT))] and define

g(x) = 2 P[x1 = [x]|xj+1 = ij, j = 1(1)T]J(il,...,iT)(<x>)h(<x>).
3

Since, for all x 6 (0,1), we have

25

N-l N-l

kiog(x+k) = k2=0 SE P[x1 = k|Xj+1 = ij, j = l(l)T]J(i1,...,iT)(x)h(x)

N-l
= Z P’[x1 = k‘

* * *
i,, j = 1(1)T]h(x) for J(i ,...,i )(x) = 1
k=0 3 I

xj+l =

=h(x)a

g may be used in the inversion algorithm for h. Let us set
f(x) = H-1(G(x)) and denote the stochastic process associated with

(f,h) by [ai,w,(0,l)f]. Using this notation, we have

Theorem 4.3. If H(f(i1 + f(i2 +...+ f(iT))) = F(i1,...,iT—l) for
all (11,...,iT) 6 ST, then [xi,Pgfl] and [ai,w,(0,l)f] have
the same finite dimensional distributions.

Proof.

First, we have

f(i1+f(i2+. . .+f(iT+1+1)))

w[a. = ij, j = l(l)T+l] h(t)dt

J
f(i1+f(iz+...+f(iT+1)))

H(f(i1+f(i2+...+f(iT+I+l)))) -

H(f(il+f(12+. . .+f(iT+1))))

C(i1+f(i2+...+f(iT+1-l-l)))) -

g(il+f(iz+. . .+f (i'r+1)))

i1+f(i2+. . .+f(iT+1+l))

g(t)dt

il+f(iz+;..+f(iT+1))

26

f(12+. . .+f(iT+1+1))

= P[xl i1\xJ = ij, j = 2(1)rr+1] h(t)dt
f(i2+. . .+f (iT+1))
= P[xl = illxj = ij, j = 2(1)1-+1]
(H(f(i2+. . .+f(iT+1+l)))-

H (f(i2+. . .+f(iT+1))))
= P[x1 = i1|xj = ij, j = 2(1)T+1]P[xj=ij+1,j=l(1)'T]
= P[xj = ij, j = l(1)T+l].

Then, using induction, we assume n 2 1+2 and u)[aj = ij, j = l(1)n-l] =

P[xj = ij, j = l(1)n-1] for all (11,...,in_1) e s“"1 and show that
f(i1+f(12+. . .+f(in+1)))

m[aj = ij, j = l(1)n] = h(t)dt

f(il+f(12+...+f(in)))

H(f(i1+f(i2+. . .+f (in+l))))-H(f(i1+f(i2+. . .+f(in))))
= G(i1+f(iz+. . .+f (in+l)))-G(i1+f(i2+. . .+f(in)))
i1+f(i2+. . .+f(in+l))

g(t)dt

il+f(i2+. . .+f(in))

= p[x1=i1|xj=ij, j=2(l)'r+1]m[aj=ij+1, j=1(1)n]

= P[x =ij, j=2(l)T+l]P[xj=ij, j=2(l)n]

l=il|xj

P[xj = ij, j = 1(l)n].

27

4.2. The Uniqueness g: the Construction for Lebesgue Measure

 

In the above construction, one sees that the function g is
just a "wrinkled" version of the density function h over each
interval [L,L+1). Furthermore, if the resultant process is to
have a finite memory, the wrinkles must occur at exactly those
points in the condition of Theorem 4.3. It has been conjectured
that this fixed wrinkling is also necessary for the resultant
process to have a finite memory. That is, if an associated
stochastic process has finite memory, then the derivative of the
function with which the process is associated is a fixed Wrinkling
of the density function of the process. That this is indeed the

case when h(x) = 1 is shown by

Theorem 4.4. If [ai,x,(0,l)f] is a stochastic process of
multiplicity T associated with a.valid expansion pair (f,l),

T+1

then for each (i ) 6 S we have

l’°°°’ir+l

f'(x) = C(il,...,i )

T+l

for a.e. x in [11+f(12+f(13+...+f(1T+1))), i1+f(iz+f(i3+...+f(iT+1+l)))).
Proof.

For n 2 l and (i1,...,in) 6 Sn, let us set

M(i1,...,in) = P[xn=in\xj=ij, j=1(l)n-1]

f(i1+f(i2+;..+f(in+l)))-f(i1+f(i2+...+f(in)))
f(il+f(i2+;..+f(in_1+l)))-f(i1+f(i2+...+f(in_1)))

 

and

f(i1+f(i2+...+f(in+1)))-f(i1+f(iz+...+f(in)))

D(il.m.in) = f(iz+f(j_3+,,.+f(in+l)))-f(12+f(13+...+f(in))) '

 

28

Noting that

M(11,...,in)
M(i2""31n)

 

D(i1,...,in) = D(11,...,1

n-l)

we have by recursion that

n M(il’...,ij)
D(11,...,in) = D(il) 122 M(12,...,ij)

Further, since [ai,x,(0,l)f] is stationary of multiplicity T,

 

we know that

M(i1,. . .,in) = M(in_k,in_k+1,.. . ,in).

Now, since f is valid for f-expansion, we have a.e.
f'(x) = lim D([x],a1(<x>),...,an(<x>))
nam
so setting i1 = [x] and ij = aj_1(<x>) for j = 2,3,..., we
have

n. M(il,...,ij)
f'(x) = 1im D(i ) H
max 1 j=2 M(iz,...,ij)

 

But for j 2 T+2, we have

m(11,...,ij) =‘M(i2,...,ij) =‘M(ij_T,ij_T+1,...,ij)
so a.e.,
T+l M(i1,...,ij) _

 

f'(x) = D(i ) H . . -
l j=2 M(12,...,1j)

V. ASSOCIATED PROCESSES WITH INFINITE MEMORY

In this final section we use the specialization of the in-
version algorithm introduced in chapter IV to construct a sequence
of expansion pairs with Lebesgue measure which converges to a
pair (f,1) whose associated stochastic process has the same

finite dimensional distributions as a given stationary process.

5.1. Approximating_§n_Arbitrary Stationary Process

Let [x1,150] be an arbitrary stationary stochastic pro-
cess with finite state space S = {O,l,...,N-l] such that
P[xj = ij’ j = l(1)n] > 0 for all (11,...,in) E Sn and n 2 1.
We shall call such processes finite positive.

For T = 1,2,..., define the sequence of measures P on

T
O by setting

P [X = i-ja j = l(1)n] = P[xj =

T j , j = l(1)n] for n s T

11

and

n
PTEXj = ij. j = l(1)n] = P[xj = ij. j = 1(1)w]k=£1+lp[xk = ik‘xj=ij,j=k-T(1)k-1]

for n > T. From this definition, it is easily seen that for each
T [xi, PT, 0] is a stationary Markov process of multiplicity at
most T. Furthermore, this sequence of processes is consistent in

the sense that

PT[xj = ij, j = l(1)n] = P’T+1[xj = ij, j = l(1)n]

29

30

for all n s T. Let FT be defined for each of these processes
as in 4.1.
If we use this sequence of Markov processes in the con-

struction of section 4.1 and take h(x) = l we have

Theorem 5.1. The stochastic process associated with (fT,l),

[aT i,).,(0,1).f ], has the same finite dimensional distributions
9

T
as [xi,P},0].

Proof.
Using theorem 4.3 and letting f = fT’ we need only Show

that
. + . = . . _
H(f(11 f(i2 +;..+ f(lr)))) FT(11’°°°’1T 1)
for all (i1,...,iT) 6 ST. But since H(x) = x, this reduces to
f(i1 + f(i2 +x..+ f(iT))) = F¢(il’°"’ir-1)

and since f(x) = C(x), we have

i1+f (12+. . .+f(iT))
f(i1 + f(i2 +...+ f(iT))) =£ g(t)dt

i1"'f(iz+. . .+f (11))
= J; 2 P[xl = [x]lxj+1 = kj,j=l(1)T]J(k1,...,kT) (<x>)
'1'
S

il-l

= Z -P[x1 = L]
L=0
f(12+...+f(iT))

+41 zirptxlgi1‘xj+1=kj ’j=l(1)T]J(k1’ ' ' ° ’k'f) (x)
3

11-1

= 2 P[x1 = L]
L=O

31

+ 2 P[x1=il‘xj+1=kj,j=1(1)vr]
IT_1(k1. - - . skT_1)<IT_1(i2, . . . ,iT)

= FT (11, o o o ’lT-l) 9
Clearly if [xi,P,fl] satisfies

E: 0 < P[xn+1 = in+1\xj = 13, j = l(1)n] S e < 1 for

n+1

all ) E S and n 2 l

(11,...,1n+1

then [xi,P},fl] satisfies E and (fT,1) is a valid expansion

pair for all T. Suppose, on the other hand, that [xi,P50]

satisfies
F if
M.n = sup P[xn+1 = in+1|xj = lj, j = l(1)n]
n+1
S
and
m = 12:1 P[xn+1 = 1n+1|xj = lj, j = l(1)n]

S

then there exists a constant F such that

for all n 2 1.

Theorem 5.2. If [xi,P,0] satisfies condition F, then [xi,PT,fl]
satisfies F and (fT,1) is an ergodic expansion pair for all T.
Proof.

For fixed T and n, we have

32

Minn = 82:1 P'rb‘nfl = in+l‘xj = ij’ j = 1(1)“)
3
PTE’Ei = ij, j = l(1)n+1]

 

sup _ _
Sn+1 PTEXJ - ij, j - l(1)n]

= P = i = ‘ = +1-k 1
8:31 [xn+1 n+1‘xj 11, j n ()n]
S
where
(11 ns '1'
k =( .
LT 11 > ‘1'
Therefore, if n s 1', then M = M and if n > 'r, M = M .
'r,n n T,n 'r

A similiar argument shows the same to be true for m_" n so that,
3

in either case, we have

‘M
T,n s Fl/n.

m
Hence [Xi’PT’O] satisfies condition F.

Now, for a.e. x in (0,1) and n 2 l, we have

d
sup — f(a (x) -l- f(a (x) +...+ f(a (x)+t)))
0<t<1 dt 1 2 n
inf d— f(a1(x) + f(a2(x) +...+ f(an(x)+t)))

0<t<1 dt

n
sup II f'(a (X) + f(a (X) +---+ f(a (x)+t)))
= 0<t<1 i=1 1 1+1 “

n
inf 11 f'(ai(x) + f(a

(x) +...+ f(a (x)+t)))
0<t<1 i=1 n

i+l

ozliplf'(ai(x) + f(ai+1(x) +...+ f(an(x)+t)))
inf f'(a
0<t<1

S

(x) + f(ai+1(x) +...+ f(an(x)+t)))

i=1 i

33

Hence fT satisfies condition C which implies (fT,1) is an

ergodic expansion pair.

5.2. A Representation Theorem

Suppose, once again, that [xi,Pgn] is an arbitrary stationary

finite positive process with state Space S. Let

B(11,...,1n+1) = [11 + F(12,...,1n+1-1), 11 + F(12,...,1n+1)]

n+1

for all (i1,...,i ) E S and n 2 1. Set

n+1

_ . . . . ' n+1
an -{3(11,...,1n+1)|(11,...,in+1) e s }

and let an be the field generated by B“. Then ([0,N),Bn),
n = 1,2,..., is a sequence of measurable Spaces such that

c: 2 .
6n Bn+l for n 1

Now, for each n, 1et ([0,N)nan) denote the cartesian
n
product 11 ([0,N) ,Bn) and let ([0,N)Q,B) be the cartesian
i=1 ,
product of all of the ([0,N),EB). Define the probability measure

P on ([0,N)ny3n) by setting

n
= o o = 0 =' =..=' '=1 1
P[xj 1n+1,j’ j 2(1)n+1]/'N11’j 12,.) lj,j,J ()n+l
PnfB) =
0 otherwise
n

= ' . X... ... '

f” all B B(11,1’11,2) X B(in+1,1’ ’1n+l,n+l) 1“ i218“

and extending Ph to 5p' in the natural way. It is easily seen

that P aP

1 2,... is a consistent sequence of measures so, by the

Kolmogorov consistency theorem, there exists a unique probability

34

* m * m
measure P on ([0,N) #6) such that PnCB) = P (B X H [0,N))
i=1
for all B 6 5%.

m
Now let :8 = V 5%, and define the probability measure P
n=l

on ([0,N),Eb by setting

11 n

_. *
e a . . . o = o , . . . 1
P(kr;1B(1nk,1,1nk,23 ’lnk’nk+1)) P (kEIB(ink91,lnk92 9 nk’nk+1)
Q
x 1'1 [0,N))
i=1
for any n 2 1; nk 2 l, k = l,2,...,n; and
B(ink’1,---,ink’nk+1) E Bnk and extending P to E in the natural

way. Note that

36(ila°--ain+1)) = P[x = i j = 2(1)n+1]/N

.l .1,
for all B(il,...,in+1) E Bn and n 2 1.
Next, suppose f;, T = 1,2,..., is the sequence of a.e.
derivatives of the fT defined relative to [xi,Pgn] as in 5.1.
We see immediately that f; is measurable with respect to
([0,N),Eg) and we have already remarked that

51:52 c...c:6Tc£-3T+1c...c6.

Theorem 5.3. The sequence (fFJB¢>’ T = 1,2,..., is a martingale.
Proof.

First, we have

E(f1'_) 2 P[x1=il|xj=ij,j=2 (1)T+1]P[x

T+l

S j=ij .i=2 (1)T+1]/N

2 P[xJ = “3’ j = 1(1)'r+1]/N = l/N

ST+1

35

so that the expectation of each f; is certainly finite. Secondly,

for x E B(il,...,iT+1)
1N- 1
E(f'+T1‘B )(x) = (P[x j=ij,j=2(1)T+1})1k2 P[x1=i1‘xj=ij,j =,2(1)T+1 x T+2=k]
x P[xj=ij,j=2 (1)T+1,XT+2=k]
_1N-1
= =' ’= = , -l l =k
(P[x-1 lj,J 2(1)T+1])1kEOP[xjij j= ( )T+1, x T+2 ]
= P[xj=ij,j= 1(l)T+1]/P[xj= 1,1,5 =2(1)T+l]

P[x 1=111x j=ij , j=2 (1)'r+1]

i; (x)

and since Bn is a partition of [0,N), the proof is complete.
Therefore, by the martingale convergence theorem, there is
a function g such that f; a g a.e. Further, since 0 s f; s l,
by the bounded convergence theorem we have fn difg a.e. Let us
define f =‘fg.
We see immediately that if we let T = <f-1> and
TT = <f;1> we have

N- 1 f(km) 11-1 f (“0)

1(T1([o,a))) = 2 dt = 2 lim
k=0 If(k) k=0T scoff: (Md

= lim ACT-1([0,a))) =
T—m T

since each (fT’l) is an expansion pair. Therefore, (f,l) is an

expansion pair.

36

Further, if [ai,x,(0,1)f] is the stochastic process

associated with (f,l), then

f(ii+f(i2+...+f(in+l)))

)[aj = ij, j = l(1)n] =]‘ dt
f(11+f (12+. . .+f (in)))
f'1-(5‘1-i-if'r(i2-I-° . .+fT(in+1)))
= lim dt
Tam fT(1i+fT(12+u..+fT(in)))
= P[xj = ij. j = l(1)n]
fT(il+fT(iz+;..+fT(in+1)))
since I dt = P[xj = ij, j = l(1)n] for
fT(il+fT(12+...+fT(in)))

all T 2 n. Therefore [ai,x,(0,l)f] has the same finite
dimensional distributions as [xn,P50]. As a result, we have

proven

Theorem 5.4. If (f,h) is an expansion pair whose associated
stochastic process is finite positive, then there exists an

*
expansion pair (f ,1) whose associated stochastic process has

the same finite dimensional distributions.

BIBLIOGRAPHY

10.

BIBLIOGRAPHY

Bissinger, B.H., A generalization of continued fractions.
Bull. Amer. Math. Soc. 50 (1944), 868-876.

Davis, H.T., The Summation 9£_Series. The Principia Press
of Trinity University: San Antonio (1962).

Everett, C.J., Representations for real numbers. Bull. Amer.
Math. Soc. 52 (1946), 861-869.

 

Hille, E., Analytic Function Theory. Blaisdell Publishing
Company: New York (1959).

Jolley, IuB.W., Summation g£_Series. Dover Publications:
New York (1961).

Khinchin, A.Ya, Continued Fractions. The University of
Chicago Press: Chicago (1964).

Kinney, J. and T. Pitcher, The dimension of some sets defined
in terms of f-expansions. g, Wahrscheinlichkeitstheorie
Verw. Geb. 4 (1966), 293-315.

Renyi, A., Representations for real numbers and their ergodic
properties. Acta Math. Acad. Sci. Hungar. 8 (1957), 477-493.

Rokhlin, V.A., Exact endomorphisms of a Lebesgue Space. Izv.
Akad. Nauk. SSSR, Ser. Mat. 25 (1961), 499-530; English
translation, Amer. Math. Soc. Transl. Series g 39 (1964),
1-360

Ryll-Nardzewski, C., On the ergodic theorems (II). Ergodic
theory of continued fractions. Studia Math. 12 (1951), 74-79.

37

M [17111111111 WT! IUFHVIIVIWIMIILH'IW 171' ES
3 129313062 0185