Ergodic Theorems for a Certain Class of Markoff Processes Citation Kennedy, Maurice (1954) Ergodic Theorems for a Certain Class of Markoff Processes. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/Z1NN-R156. https://resolver.caltech.edu/CaltechETD:etd-01072004-100602 Abstract NOTE: Text or symbols not renderable in plain ASCII are indicated by [...]. Abstract is included in .pdf document. A system, whose state may be described by a point t in a bounded set in Euclidean space, is considered. At every unit interval of time, attractions [...] towards certain points [...] are applied with probabilities [...], where t is the state of the system. Given the initial probability distribution [...] for the state of the system, the problem is to obtain limiting theorems for the distribution at the nth unit of time as [...]. Subject to certain conditions on [...] and [...] such convergence theorems are obtained. Some particular properties for the case, where the attractions are toward the vertices of a simplex, are discussed. Finally the one-dimensional learning model is considered. Item Type: Thesis (Dissertation (Ph.D.)) Subject Keywords: (Mathematics and Physics) Degree Grantor: California Institute of Technology Division: Physics, Mathematics and Astronomy Major Option: Mathematics Minor Option: Physics Thesis Availability: Public (worldwide access) Research Advisor(s): Karlin, Samuel Thesis Committee: Unknown, Unknown Defense Date: 1 January 1954 Record Number: CaltechETD:etd-01072004-100602 Persistent URL: https://resolver.caltech.edu/CaltechETD:etd-01072004-100602 DOI: 10.7907/Z1NN-R156 Default Usage Policy: No commercial reproduction, distribution, display or performance rights in this work are provided. ID Code: 46 Collection: CaltechTHESIS Deposited By: Imported from ETD-db Deposited On: 08 Jan 2004 Last Modified: 09 Jun 2023 00:00 Thesis Files Preview PDF (Kennedy_m_1954.pdf) - Final Version See Usage Policy. 2MB Repository Staff Only: item control page

ERGODIC THEOREMS FOR A CERTAIN CLASS OF MARKOFF PROCESSES Thesis by Maurice Kennedy In Partial Fulfillment of the Requirements for the Degree of : Doctor of Philosophy California Institute of Technology Pasadena, California 1954 Acknowledgements It is with great pleasure that I acknowledge my debt to Professor Samuel. Karlin, He suggested this problem to me, and has been most generous with help and advice throughout the past two yearse I have also great pleasure in expressing my thanks to the United States Government, for having awarded me a grant for graduate study during the year 1951-52, My thanks are also due to the California Institute of Technology for having provided me with the opportunity of continuing my work here, by awarding me a graduate research assistantship and a tuition scholarship; and in particular I wish to express my thanks to Professor Bohnenblust and the Mathematics Department, on whose recommendation such awards are made, Abstract A system, whose state may be described by a point t in a bounded set in Euclidean space, is considered. At every unit interval of time, attractions A, towards certain points y, are applied with probabilities B,(t)> (f 6, (t) = 1), where t is the state of the system. Given the initial probability distribution v(t) for the state of the system, the problem is to obtain limiting theorems for the distribution at the n® unit of time as n+, Subject to certain conditions on h A; and [ B,(t)} such convergence theorems are obtained. Some particular properties for the case, where the attractions are toward the vertices of a simplex, are discussed, Finally the one-dimensional learning model is considered, TABLE OF CONTENTS Section Title Page Acknowledgements SHPO CHR EHD EOE Oe ee HEH Oe EHO EES Abstract PESOH SOTHO HHEHEHE TES CHR HOSE HCE D EEO DER OD RE 1, PAtroduction cecccsccccccccccccccececsscesvcsece 1 2. Theorems on Banach Spaces .escesesccescsesccceses 7 3. Description of a Certain Class of Transformations on a Compact Metric Space wresccsserecccccccce A Ae Description of the Markoff Process cecscscccecees 18 5, Uniform C = 1 Convergence for U" on C(m).. 27 6. Strong C -1 Convergence for U" on C()sicee 29 7. Weak-Star C- 1 Convergence for Ty eer ccccecce 31 8, Convergence Theorems for uv", tT for a Class of Absorption PrODLOMS 5 coocceccccscscvcevscesces 34 9. Properties of U and T for the Case When There Exists an Index k such that g(t) > 0 for all +t e€ © with the Possible Exception of Jy eee vee eeeosee ee svaceeveeceaseeseeeeeseoanseeeeseate 48 10. Convergence Theorems for vo and T™ for a Class of Problems Similar to those Considered in Section 9 CROSS HORH OHHH E ROEHL EHRHOEEEEHEEO OHS 52 11, A Special Problem Involving Attractions Towards the Vertices of a Simplex rer errrrrerrererre ey Y | 62 12. Properties of the One-dimensional Learning Model.. 70 References @e¢eetpeeeeoeeeepeeerantseeeoeveanesvser een eeeeed 77 1. Introduction. Certain learning models have been introduced by Bush and Mosteller [1]. These models give rise to a class of transition operators which were studied by Karlin [2] for the case of one dimension. The mathematical description of the simplest process of this ‘kind can be formulated as follows: A particle on the unit interval executes a random walk subject to two impulses, one of which is applied at the end of every unit of time. If it is located at the point t, then t+ At = At with t= At+e1-A 1 1 1 g(t), where g(t) + g(t) =1. If p(t) is the initial probability probability Q(t), and ta with probability measure for the position of the particle, the probability measure Ty at the end of the first time interval, is clearly given by . T p(B) ard AE E Le) J Gait) ay (t) + J g(t) ap (t). 2 C 1 If g(t) (i'= 0,1) are continuous, then T represents a continuous transformation of the Banach space of Borel measures on the unit interval, into itself. Instead of working with the transformation T on this space, Karlin considers the transformation U, on the space of continuous functions, defined by Ux(+) = = g,(t) x(A,t) ° i He shows that T is the conjugate transformation to U. Thus by -~2- proving strong convergence for the iterates U", subject to certain conditions on g,(+), weak-star convergence is obtained for Ty . For probability measures, weak-star convergence is of course convergence in distribution, It is the object of this thesis to generalize these results, A countable set of transformations $ As} of a compact metric svace © into itself is introduced in section 3. These have the property that e (Ast, Ass) 2 NE (t,s) (O< A <1). Hach A; represents an attraction towards a fixed point y, (1 = 1,2, «.. ). In section 4 we consider a system whose state may be described by a point t in © . Our Markoff process consists in applying at every unit interval of time, one of the transformations f As} » Ay being chosen with probability $.(t), where { d.(t)} is a family of continuous functions each satisfying a uniform Lipschitz condition, and the sum of whose Lipschitz constants is finite. If v -is a prob- ability measure defined on the Borel sets of m , giving the probability distribution of the initial state of the system, then the probability distribution Ty; for the state of the system at the end ot the first unit time interval, is te(e)= Lf gst) dy (t). rea This is a continuous transformation of the space YY¥t (n) of finite Borel measures into itself. The object is to obtain weakestar con- vergence theorems for ™y » Proceeding as in Karlin's paper we define the transformation U of C(m) (the space of continuous functions on 2, ) into itself by -3- Ux(t) = of B,(t) x(A,t). U is a continuous transformation and T is its conjugate, i.e., (Ux, ) = (x,Ty ) xeC(o), pe m(o) where (xp) = [ x(t) ap (t). It follows, since (U"x, v) = (x, Ty ) that (UPx, +) represents the expectation of x(t) at the end of the n*} time interval. There is a direct probability interpretation of the trans- formation U. It is clear from the definition of U that ug, (+) represents the probability that if the state of the systems is initially at t, then at the first unit of time the attraction As is applied; and in general, ug, (t) represents the probability that. at the nth unit of time, the attraction A; is applied, given that initially the state of the systemis t, At this stage reference should be made to the work of other authors — Ocinescu, Mihoc, Doeblin, Fortet, Ionescu Tulcea and Marinescu [3-9]. We shall refer in the main to the papers [8,9] of the latter two, for they generalize that part of the work of the others which is relevant here. Our transformation U isa particular case of a transformation considered by them,yand it follows from their work that if we consider U asa transformation of the space C(O) into itself, where Cc, (2) is the Banach space of continuous functions x(t), each satisfying a uniform Lipschitz condition on , with the norm -~k = t) - [bel Ip, = masclx(t)| + sup | MGS . Cy then U is a quasi-completely continuous transformation. This important result enables us in section 5, to establish uniform C -1 convergence on C, (a) for the iterates u", and in particular to prove C -1 convergence for Ung, In order to obtain results for C(M) and WYL() we must now Specialize 1 to be a compact set in finite-dimensional Euclidean space. We do this in order to have the property that c,(2) be dense in C(©). In section 6 we obtain by the Banach-Steinhaus theorem C ~ 1 strong convergence for u" on C(). ‘In section 7 these results are translated into the conjugate space and C -1 weak-star convergence is obtained for ™y ° In section 8, we consider the case where for each i, (i = 1,2, ... ) the fixed point of A, is an absorbing point, i.e., ha y, is an absorbing point (i = 1,2, ... ). This condition is expressed by 8:(y;) = | (i = 1,2, ... ). In addition we introduce the additional and natural assumption that for each i, as y;, is approached, the probability of choosing the next attraction to be Aas does not decrease, This is expressed mathematically by assuming ;(A,t) > @,(t) for all t (i = 1,2, ... ). Under these assumptions, we obtain the uniform con~ vergence of u" on C,(a), their strong convergence on C(.m), and the weak-star convergence of T2y in Wre(m),. Moreover the limiting transformations are explicitly determined. -5- In section 9, we consider certain properties of U and T for a certain class of probabilities {di (t) \ « in section 10 a slightly different class (though strongly overlapping) is considered. Here the assumption that 2 G,(t) G,(s) #0 for all t,s in is made, and again convergence theorems are obtained. The method used is exactly that of Karlin [2] and indeed the result is indicated in his paper. Here however it is difficult to obtain information about the limiting transformation. Section 11 introduces the N-dimensional analogue of the model considered by Karlin. It consists of attractions towards the vertices of a simplex, each attraction being directly proportional to the distance from the corresponding vertex. This model is a particular example of the problem treated in earlier sections. Certain properties concerning the convergence of derivatives of U"x(t) are obtained under further ‘restrictions of 9,(t). The thesis concludes with section 12 which is devoted to establishing certain additional properties for the one-dimensional learning model, At the start in section 2, those properties of Banach spaces which will be required, are set out, The main theorem of Ionescu Tulcea and Marinescu (theorem 2.2) which provides the quasi-complete continuity of U on Cc, (a) (theorem 4.2) is stated. However it is not always necessary to appeal to this theorem to establish this result, apart from the verification that the iterates U" are uniformly bounded in CCn)s which is easily proved, and is stated as a separate lemma (lemma 4.8, which is itself derived from lemma 2.1). For example in ~6-/ section 9 once the convergence in C(..) is obtained, it is easily deduced from theorem 2.1 (a simpler theorem than that of Ionescu Tulcea and Varinescu) that U is quasi-completely continuous on C; (a). For the case of a finite number of attractions this is also true under the hypothesis of section 8, It is clear that similar theorems may be worked out where instead of { Ax(t)} satisfying a Lipschitz condition of order 1, they satisfy a Lipschitz condition of order d, where O< d <1 { 9, page 146]. Finally, we note that only the case, where the number of attractions is countable, has been treated. However, it is clear from the work of Ionescu ‘lulcea and Marinescu [8,9 ]that subject to certain assumptions corresponding to those imposed on hd, (+) } here, the transformation U obtained for the non-countable case is quasi~- ‘completely continuous on C,(o.). There seems no reason to. doubt that convergence theorems similar to those of sections 8 and 10 can be obtained, -J7- 2. Theorems on Banach spaces. -We first consider those properties of Banach spaces which shall be required in subsequent sections, let E, B be Banach spaces with norms xl ln [Ixl 1,» respectively and with the property that as vector spaces Bc E. Let U be a linear transformation of E into itself, which is continuous with respect to both norms, i.e., (2.1) |[tll,= sup | |uxl|, <@ x eB HIxll, <1 and (2.2) ull, = sup = |fuxl|,<«. E xeB E HIxll_ <1 In addition we assume (2.3) there exist two constants Ryr (0 <r<1) such that [luxl ly < rllelly + Rl bel lps xeB, The following lemma is due to Ioneseu Tulcea and Marinescu [9]. The proof is simple and is given for completeness. LEMMA 261. If [|U" |, < Hy (n = 1,2, ...) then (2.4) He" ll, £¢ N = 14525 cee where C is some positive constant, PROOF: For x €B we have from (2.3) -3- 2 [lu“x!], < rllux|], + BR] luxl |, <r*|lell, + Bel lxllp + RHI lal ly since [ltxll. < Hlxll, by hypothesis. Again Ww-xl 1, <r7llell, + (e?R + oR + RH) [Ix |, <r? | fell, + a(r® +r +4) [hell where A = Max(R, R-H). (2.5) [Ix [5 <2" lxll, + Bl bellp A where LL = Ter Hence for each x eB, [fo"x1 1, <o, Therefore by the principle of uniform boundedness, n lull, <¢ where C is some positive constant, and the lemma is established, We shall denote by Ss the sphere of radius r in B, ieee, (2.6) s.= | xesl Iixll,sr}. THEOREM 2.1. If (2.7) S, is compact in E (i.e. with respect to [lx] 1.) (2.8) [U's [I'l < kn = 1,2, (2.9) For each xe B, there exists an element Vx ¢ E such thet [|u™ - vx |, >0 as n> -~9-=- then V is a linear transformation of B inte itself continuous with respect to both norms; in fact and the sequence of transformations vw converge uniformly in the Benorm to Vy, i.e., (2.11) ||u" - vij, > 0 as n+, PROOF : The first step is to establish that for each xe B, Vx cB. V is clearly a linear transformation of B into EF. For xe Sys [lu"xtl, < KI IxIl, by (2.8) < Xk (since x € S,). Therefore for x € Ss Sux € S, which by (2.7) is clearly a compact set in FE and thus is closed in F. From (2.9) it follows that Vee Ske and hence is in B,. Since V is linear it is clear that for any x eB, Vx € Be Moreover, Tvl], = sup |[vxll, x € Sy < sup {{x{|, xe Sy = K we lIvli, < K and we have established that V is a con tinuous linear transformation of B into itself, From (2.8), [oI Ip < HI bel xe Be -~ 10 - co [Ivellp < HI lxI 1, (by 2.9). Hence V is continuous in E-norm and ||v| L <H. It is also clear from (2.9),that Vx is a fixed point of U,. It remains to prove (2.11). From (2.8) we see that (u'x | form an equicontinuous family of functions defined on B, with respect to either norms. By (2.9), Ux converges in E=norm and therefore the convergence is uniform on every compact set in E; in particular | ju" - vx] |p >0 uniformly with respect to xe 8, a compact set (by 2.7). The hypothesis of lemma 2.1 being satisfied,we may use equation (2.5) as follows [|u"x - vel], = [lu (u% = vx) II yo7k " [fu = ve} 1, + | |u% - well, . Choose k 3 Ho - vx| 15 < = for all xe S,. Now choose mek) < & , For xe S, Nan>N,lr ik lute - vel], < [ody + IIvell, k < 2K. Hence for xE Ss n>WN <i+ Es lu" - vel, <$+8=c, Lees | ju" - vx | > 0 uniformly with respect to x eS, or B 1 |v" - vil, > 0 which completes the proof of the theorem, -~ll- THEOREM 2.2. Theorem of Ionescu Tulcea and Marinescu, If (2.12) x, € Bs [Ix 1, < Ky lim Ix, - x| le =Q implies that xeB and IIxIl, < Ke (2.13) |lu'll, <4, n= 1425 vee (2.14) U transforms every bounded set in B into a compact set in E, then the norms Ho" ls are uniformly bounded and U is quasi-completely continuous as a transformation of B into itself, i.ew, J n 9 [|u" - vil, <1 where V is 4 completely continuous transformation of B into itself. Corollary: The theorem is valid if in (2.3), (2.14), U is replaced by U" for some positive integer m, The theorem and corollary are proved in reference [9]. The authors also observe that if the unit sphere 5, in B is compact in E, that (2.12) and (2.14) are satisfied. We prove this in the following lemma, LEMMA 2.2. If the unit sphere S, in B is compact with respect to IIxI 1, then the hypotheses (2.12) and (2.14) of the above theorem are automatically satisfied. PROOF: Let x, © By [Ix ll, < lim I]x, - xl], = 0 nao -12- x, © Sy = {x & Bi [xt], <K} which is clearly a com- pact set in E from the hypothesis. Hence there exists a subsequence x converging in Fenorm to an element in S This element mst be x, n, K* Hence xe Sys f.eey x EB and IIx! 1, < K. Thus hypothesis (2.12) is established. Now let P be a bounded set in B, i.e., xe P implies that | |x] le < K (a constant), Let ix, | e P 1A [fox He < HUlly [xl Ip 1A k||U]|, = R (say). Now S, = {x e BI Hx}, <R \ is compact in E. Hence there exists a subsequence [Uy | which converges in E~norm to an element y ¢ Sp» i.e., to an element in B. Hence UP is a condition- ally compact set with respect to the E-norm, but the closure of a con= ditionally compact set in a complete metric space is compact. Hence UP is contained in a compact set in E. Hence the hypothesis (2.14) is established and the lemma is proved. We conclude this section by stating the general ergodic theorem for Banach spaces as proved by Yosida and Kakutani [I0] and the THEOREM 2.3. Let B be a Banach space and U a completely continuous or quasi-completely continuous transformation of B into itself such that Jiu" }| <C. Then there exists at most a finite number of eigen- values of U of modulus 1. Denote these values by ) 13 h ny sees r_E Then there exists a system of completely continuous transformations -13- U U (each. of them # 0) and a completely continuous or 4 geecs Ak quasi-completely continuous transformation S (which may vanish) such that . k n n i=1 i with Wy, SU, US a0, uv =u, UU =0(i#}) i "s i eG GG (2.16) U, s=gu_ =o, flu, [[<c, ai=1,...,k \ Ma 4 ™4 | and (2.17) |[[s"|] <—. , M, € being positive constents (1 + ©) (2.18) For any complex ), | ,| = 1, there exists a completely con- tinuous transformation Ul: which maps B into itself, such that 2 n 1 vu .U U M _ | z (S+o3? +S) 74, Sn n 142, eee where M is a constant independent of n, and UL #0 if and only if )\ is an eigen value of U (2.19) Iu" || > 0 if and only if U has no eigen-value of modulus 1. If | ju" } | +» 0 then convergence is geometric, i.e., [fu" |] < —_t— > Mh being positive (1 + h) constants. (2.20) | {u - U, || +0, U, #0 if and only if 1 is an eigen- value of U and there are no other eigen-values of modulus 1, Again if this condition is satisfied, the convergence is geometric, i.e., (2.21) | |v" - U, I[< H,h being constants. H (9 +n)” -l4- 3. Description of a Certain Class of Transformations on a Compact Metric Space. Let © be a compact metric space. Let fa.} be a countable set of 1-1 transformations of o. into itself with the property that (3.1) ee (Ayts Ass) SD @ (tos) 1 = 1525 ooo for ail pairs of points t,s ¢ where e is the metric on f. and \ is a constant such that 0< A <1. LEMMA 3,1. ha, \ form a set of 1-1 bicontinuous transformations of . into itself. Each A, represents an attraction towards a fixed i point Ys which is the unique fixed point of Ass and moreover the rate of attraction to the fixed points is uniform with respect to ji, i.e. nL (3.2) lim A,t = Y; n> 6 for any te , the convergence being uniform with respect to i and tef_. For each i, v3 is the unique solution of (3.3) AiY4 = ¥ye PROOF: It is clear that if ts » t, we have by (3.1) A i > A,t each i. i Hence A, is a continuous transformation. From (3.1) © (ayts Ags) SX” e (tes) <M)" where M is a constant, since e (t,s) is bounded for a compact set. -15- Choose gs = AM. Hence, by above inequality e(agts ay Pt) < my” for every positive integer p. Hence, since a compact metric space is complete, Ayt > qe Clearly ALY; =y.. Moreover 3 is the unique point satisfying this i equation,for let AuY} = vie then Ayyt = YS so that since n e(Aivas Ay) SoM n let n»>o, then e(yssv}) = 0. oo oY; = Vye Finally the convergence in (3.2) is uniform with respect to +t en. and all i, for e(Astsy,) = e (At, Aiy,) < \ M. Hence the convergence is uniform, The bicontinuity of A, follows from the fact that a con- i tinuous 1-1 transformation of a compact space into a Hausdorff space is bicontinuous. Hence the lemma is proved. For convenience in notation we now introduce a definition. Definitio: alJg= A,» eee yA, S for any set S 1, recesd, 1 n ala] a represents the range of all products of n transformations, - 16 - Since A,D ca, it is clear that [2] lo all alt] sok ee Om OFA This is a monotone decreasing sequence of sets,swhich therefore converges to F, where (3.4) F= n ally . F represents the points of which are reached by an infinite number of transformations. We define G to be the complementary set, i.ce, (3.5) G=F, LEMMA 3.2. If the number of transformations 4,4 is N (finite) then F is a closed set, PROOF: As being a continuous transformation maps any compact set [n] onto a compact set. Hence A“ “MN, being a finite union of compact sets and therefore closed sets,is closed. Thus F is a countable intersection of closed sets and therefore is closed, An alternative way of writing F is provided by the following lemma, The proof is that of Hausdorff.[11, page 131]. LEMMA 3.3. o (3.6) Fe UM Ayo eee > A, O, o n=1 1 n where the union is taken over all infinite sequences 6 , where the i's range from 1 to N. . PROOF: Denote the right-hand side of F by Ft. Any element of Ft is given as the limit of a sequence of sets eo i, ty i, ig 13 It is obvious that the element determined by this sequence isin F (see (3.4) On the other hand let xe F (3.4). Then (3.8) xEAIO, ADAWOS NX, ee e L, es 45 A 3 a) Consider the first suffix in each of these terms. They form an infinite sequence ‘ve ; { - Since the range of suffixes is 1 to N, there mist be one integer which occurs infinitely often in the sequence, Let it be denoted by ij. Remove those terms in (3.8) which do not have i, as the first suffix. Consider the second suffixes of the remainder. Apply the same argument to obtain suffixes i,» Ti sec » such that 3 X*EA, OX, A, Ag XY, A, A. A, LD , aces 1, i, i, i, i, i; Hence by (3.7) xe F!, Hence F = F' and the lemma is proved, - 193 - 4. Description of the Markoff Process. _ First we state a well-known theorem, THEOREM 4.1. Let © be a compact Hausdorff space, and let C, (2) be the real Banach space of real continuous functions x(t) defined on with [}x[] = max |x(t)| teQ Let c*(n) be the conjugate Banach space of C,(2). Define partial orderings of both spaces as follows: x>y, if and only if x(t) >y(t) all ten; xy e C(n.). Y2v, if and only if p(x) 2 V(x) all x20, fPyVv e cx), Denote by Wl (1) the space of all real-valued completely=additive regular set~functions (E), defined for all Borel sets E of 1, Fe 4 If we put |] yi{| = sup P(E) - inf (E), and >V if and 4 BECO 4 ECS 4 ‘ only if \(E) > v(E) for any Borel set ECON, then Y(N) is isometric and lattice isomorphic to the conjugate space C*{M) of Cp(). The correspondence is given by (401) (yp) =f x(t) a(t). an PROOF: See Kakutani [12]. We shall denote by C(m) the Banach space of complex-valued con- tinuous funetions x(t} defined on 1, -~19- We now return to consideration of the compact metric space O. and the transformations VA, | introduced in section 3. ‘Consider a system whose state may be described by a point inf. Let B,(t) be a countable family of continous functions defined co on 1. with the property that 0 < £, (+) <1, and & B,(t) = 1. Our 1 Markoff process consists in applying at every unit interval of time one of the transformations tA} » A, being applied with probability B,(t), where te 0 represents the state of the system, Let YE) be a probability measure defined on the Borel sets of QO , giving the probability distribution of the initial state of the system. Let (4.2) Tp (e) = Z J dy(t) ay(t). -1 A 4E Since £4; } is a set of continuous transformations, it is clear that iy defines a measure defined on all Borel sets of ©, and represents the probability measure for the state of the system after Since {. is a compact metric space, it is separable and therefore the concepts of Baire measures and Borel measures coincide. Since Baire measures on 1 are recular, this means that Borel measures are regular. Hence Yu(O), defined in theorem 4.1, consists of the set of all finite Borel measures on 1. Equation (4.2) defines Ty for any eWi(o.). Clearly T is linear and Ty is a Borel measure ysince FA; | are continuous. Moreover, T is a positive linear transformation. If yp > O then lity || = Ty (2) =p(Q) =| Ip | by (4.2). An arbitrary measure i" may be written as a = y - y > - 20 = with norm given by || ¢|| = hyn + |] pTl|. Hence [ty lh = lee" = tel) s Hey H+ lee Uy" + (yl = [pd «lity ls (pil. | Thus we obtain LEMMA 4.1. T is a positive linear transformation of Yt (2) into itself of norm 1. Now consider the space C(n) of continuous complex-valued functions on $1 . We define a linear transformation U of this space into itself by x ~> Ux, where (4.3) Ux(t) = 2, B,(t) x(A,t) for every continuous function x(t) «¢ C(M). It is clear that U is linear and positive. [!ux]] = sup = [Ux(t)| ten < sup |x(t)| since 2 B;(t) = 1, ten = ||x||. 2 [[uxl] < [Ixl], i.e., U is continuous with j|ul| <1. If x(t) is a constant,then Ux = x. ev [fu{] = 1. [|u| | <1, but again since U preserves constants, Nica = 1, and in general {|u"| | = 1. Summing up we have that -21- LEMMA 4.2. U is a positive linear transformation of C() into itself of norm 1,which preserves constants. By theorem 4.1, yr(2) is the conjugate space of C, (2) with identification given by equation (4.1), ise, (x,y) = f x(t) ap(t). a As in Karlin's paper [2],we now connect transformations T and U by means of the following lemma, (404) (Ux, v) = (x, Ty ) for each xe Ca(2), ye m(o), PROOF: Let aa Oo, x20. n bet Ate)= z f B,(t) ay (t). A (B) is a positive measure, and A) 7 Ty (Ek). Since Ay is continuous on its domain,and since by the continuity of Ass As is a Borel-measurable transformation we may write n Ace) = 2 f cays) ay (ay't) - 22- Gy a) = | x(t) aa, (t) » n Z| x(t) By(ay't) ay (ays) i=i a n Xf x(a,t) d,(t) ay (t) i=1 a / 1 Ms Now (x»A) > (x, Ty ) as n+o for (xp Ty) = (x, 2,) = fxtt) a(ty -2,). By the above Ty - )\ is a positive measure, and there exists ngan > n y v n Pp on" = "o (Ty - 2) (2) < e/||x]|. Hence for n> ny (x, Ty) - (x, AL) < es oe (x, a) A (x, Ty). Hence, (x Ty) = ame, 0) =f Zag Ce) xCayt) ay Ce), Q the limit heing taken under the integral sign since all the terms are positive, o% = (Xy Ty ) = Ux, Y)- Since an arbitrary x €C,() can be written as x =x" where x, x” are positive and in Ca(%), and similarly for 4 & YU X ) the result (4.4) immediately follows,and the lemma is proved. We now consider a subspace Ci(n) of C (nm). We define Cc, (a) to be the vector subspace of C(1) consisting of those complex - 23- valued functions in C(), which satisfy a Lipschitz condition, i.e., [x(t) - x(s)| <o (445) M(x) = sup OTE) where the sup, is taken over all t,s e¢C(M), t#s. This set of functions €,(0) forms a Banach space under the norm IIx! |,» where (466) Tx, = TP Ixf] + M(x). We now verify a very important property of C,(2). LEMMA 4.4. The unit svhere in 6, (%) is compact in C(M.), i.e., B= {xe0,(0)! Ilxll, <1} is compact with respect to norm | |x|]. “PROOF: Let (x,\ be a sequence in 2 ,. Hence Ix, (t) = x, (s)| i 4 (4.7) Ihe, I * sup 0 (b8) <1, which implies that and Ix,(t) - x)(s)| <p (ts). Thus (x(t) } form a bounded sequence of equicontinuous functions defined on a compact metric space. Hence by Arzela's theorem,there exists a subsequence \x, | converging uniformly to a continuous i funetion x(t), i.e, Hay - x} | > 0. - 2h - It remains to show that x eZ ;° From (4.7) Ixy (t) - xy, (s)| “Thal <1- Ixy, t#s. Let i». to obtain sup J#(t) = x(s)1L <1- [xl] tds e(t,s) which proves that xeC,(Q) and Hxt I, <1, 4... xe2,. This establishes the lemma, It is now necessary to impose two further restrictions on. DB, (%) . We assume and also (409) Ms E M(B,) < This latter condition is automatically satisfied if the number of transformations is finite. 579] LEMMA 4.5.2 2 bs = 1, where | p,\ are considered as elements of 1 ao z 1 B, (+t) = 1, the convergence being uniform. PROOF: By definition _ B;(t) = 1, so it only remains to prove the uniform convergence of the series, However the partial sums are positive, continuous and converge to a continuous function on a compact set and so by Dini's theorem converge uniformly. As is pointed out by Ionescu Tulcea and Marinescu [8,9], the following is true. -25- LEMMA 4.6. The transformations U defined by (4.3) applied to the elements of c,(2) is a continuous transformation of Cc, (2) into itself, and (4.20) fuxll, < Wllxll, + Ri lel], where }, R are constants and O< A <1, /\ being the constant introduced in (3.1). PROOF: Doeblin and Fortet [4] proved the continuity for a finite number of transformations, but proof goes forward in exactly the same way under our assumptions, Ux(t) - Ux(s) =F A, (t) x(a,t) - FA, (s) x(Ays) ~ Ux(t) = Ux(s) 5p. (+) x(A,t) ~ *(A,8) e (Ayt» Ajs) e (t,s) i e (A;tsA,8) ; e (t,s) (B,(¢) = 6, (s)) +) merce) x(A;S)- Hence by means of (3.1), (4.5) and (4.9) we obtain M(Ux) < AM(x) + M|[x|]. Hence if xe c(m), M(Ux) < ©, i.e., Ux ce C, (9). [lel], = [fox] | + ace) [x] + Amc) + ot fal AMG) + Alixl] + 1 # =D) Le fo [foxll, < NT belly, + REI where R=1+M-RA, 1A - 26 - It follow that [loxl I, s C*R) [lel lps Hence U is a continuous linear transformation of C, (2) into itself satisfying (410), and thus the lemma is proved. It is clear from the foregoing that we have LEMMA 4.7. C(n), C,(a) satisfy the conditions for the Banach spaces E and B respectively, introduced in section 2. Moreover the transformation U introduced in this section satisfies the conditions for the transformation U introduced in section 2 by means of equations (2.1), (2.2) and (2.3). | The following lemma is a direct consequence of lemma. 4.7 and lemma 2.1,using the fact that ||u"|| = 1. We conclude the section with the following theorem. THEOREM 4.26 U is a quasi-completely continuous transformation of c.(a) into itself. This is proved by Ionescu Tulcea and Marinescu. It is a direct consequence of applying lemmas 4.7, 4.4, 2.2 and the fact that |{u"|| = 1 to their theorem, i.e., theorem 2.2. -27- 5, Uniform C-1 Convergence for U" on Cc, (1) . THEOREM 5.1. There exists a non-zero positive continuous transformation U, of c,(2) into itself such that 1 2 Jk C - Gi) th 2 U-Glh sy N= 1425 woe where € is some constant independent of n. Moreover, U, preserves constant functions, PROOF: Since Ux =x if x(t) = constant, it follows that ‘= 1 is an eigen-value of U, which by theorem 4.2 is a quasi-completely continuous transformation of c,(n) into itself. Using lemma 4.8, Leeey [v" tl, < C, we obtain (5.1) from theorem 2.3. That U, preserves constant functions is obvious from the fact that (5.1) implies (5.2) {2 5 uN = v,xl| > 0 xeC.(o), ° n 4 1 L L , which implies that (5.3) A > Ux - U xl] +0 xe C,() ° n 4 1 | L . The positivity of U, follows also from (5.3). “hus the theorem is 1 established, It is easy to see from the definition of U, that uf, (t) represents the probability, that given that the initial state of our system is t, that at the end of the nth time interval, the trans- formation A, is applied, Since B, {t) Pa c, (2) we obtain from (5.1) a mean convergence theorem for the limiting probabilities of applying the transformation Ay» as nso given that the initial state is +t. This has been obtained by Doeblin and Fortet [4], and Ionescu Tulcea and Marineseu {é]. LEMMA 5.1. The following inequalities hold for n= 1, 25 eee 5 (4) IE xr uF g,-0, 4 ll,<% ° n 4 i 1°i'L—- on and consequently , 12 Uk c! (5.5) IKE 2 ws, -U, Bll<e> where C! is a constant independent of n and i. PROOF: This follows from (5.1) and the fact that A [Idyll < lll + m0d,) <1+M by (4.9). Hence the lemma is established. -29- 6. Strong C - 1 Convergence for ji on C(). From now on we restrict consideration to ©. a compact subset of Euclidean space. Since is compact it follows that, since polynomials are dense in C(f), C, (m2) is dense in C(M). It is for this property that the restriction on © has been made. THEOREM 6,1. 1 2 ok (6.1) Ile = Ux- U,x1 | -0 as n+ 1 for each xe C(O), where U, is a continuous transformation of c(n.) into itself, and Iv, 1] = 1, Moreover U, as a transformation on C,()s is the same as that of the last section. 1 2 PROOF: Let V. =- ZU ERQUE non | IIvf <1 lA but since Vn clearly preserves constants [Iv 1 = 1. From (5.1) we easily obtain that for x ¢ c, (a) Cc lIv,x = u,xl| < [vx - Uxll, <£ ledles Lele, Lim | }v_ x - U,xI | = 0 for xe C, (2). n->o Since Lv, =1, we have by the Banach-Steinhaus theorem (since C, (4) is dense in C(m)) that lim [|v x - u,xl| = 0 noo - 30- where U, is a continuous linear transformation of C(m) into itself, and is in fact the unique extension of U, defined on c,(Q) to the whole space C(M). Also | lu, [| <1, but since U, preserves constants, 1 [|u, || = 1. Hence the theorem is established. Corollary: The following relation holds (6.2) WU, = U,U =U, =U This follows by standard arguments. See Yosida and Kakutani [10]. Definition: ¥,(t) = U,6;(t)» 1 = 1,2, cee e oo LEMMA 6.1. Ue C()s i= 1,2, ... , and & u, = 1, convergence i=] being in the sense of C(M), ies, ao (6.3) 2 v(t) = 1 1 where the convergence is uniform on (1 . PROOF: Since U, transforms C,(a.) into itself, ¥, € c, (0). Co By lemma 4.5, 2% D; = 1, convergence being in the sense of C(1), 1 Since U, is continuous on C(f.) by theorem 6.1, we have that wo . in the sense of C(0), which proves the lemma, -31- 7. Weak-Star C - 1 Convergence for ry e THEOREM 7.1, For any measure ff € WL (Q), we have the following: n 1 k (7.1) n 2 ry Ty ’ where the half-arrow denotesweak-star convergence, i.e., (x, Ty ) = lim (x, + ry )s n> 0 =—Mp and where T, is a positive continuous linear transformation of norm 1 of Wi(.) into itself, PROOF: From (4.4), we have for x € C,() (Ux, wv) = (x, Ty) and in general (x Ty) = (u,v). Thus af ak y.1 $ k,.1 3 Lk 7 oak (742) (xs = Ty) a (x Ty) = 5 2 Wx p) = & 2 Ux f). From (6.1) we have 12 ok lin 5 + ux = Ux (convergence in sense of C(M.)), n> 1 ; Let T, be the conjugate transformation of Uys Lee, (U.x,v) = ( lim i > vex ) = lin (t ; ws ) roy noo ™ 4 ae ns>o 7 4 ace Hence by (7.2) and (7.3) (x, Ty) = lim (x,t 5 why) x, Typ in Xs v - 32 = for all xe Cy(). T, being the adjoint of U,, 1, is a continuous 1 linear transformation of YY. (£1) into itself of norm 1. Let a >O0, then Ty >0O. If x > 0, it follows from (7.1) that (x, TY) > 0d, Hence T, yp 2 QO. Thus qT, is positive. The theorem is therefore established. Corollary: The following relation holds (7.4) TT " 3 a i} J i} ees This is an immediate consequence of (4.4) and (6.2). LEMMA _7.1. For any open set H C G (defined by (3.5)), T, p () = 0. If there are only a finite number of transformations Ass then Ty yr (a) = O64 PROOF: Let x(t) ¢ C(a) where x(t) > 0 teu (7.5) x(t) = 0 teH. HCG, H° > F. F,G were defined in section 3. It is clear by the method of definition that there exists N such that for n>N, alt] g cH°. Thus for n >N U'x(t) =F By (eB, (ay +) weeee By (A, eee b) x(A, eee A, t) n n~1 1 n 1 Hence lim U'"x(t) = 0. Let a be any positive measure n> - 33- - - ik oy (x, Tp) = Ox p) = Qing 2 Ux, /) (lim U"x, re) 0. * f x(t) a(t, y (4)) = 0 ” J x(t) d(T, (t)) =0 by (7.5). Now T, is a positive transformation. Thus T, y (H) > 0, but since x(t) > 0 on H, it follows that tT, (H) = 0. Since T, is positive and every measure v may be written as the difference of two positive measures, it follows that Ty (H) = 0 for all f+ If the number of transformations is finite then by lemma 3.1, G is an open set. Let be a positive measure. There exists a sequence of open sets H v i H, ¢ Hy eee CH, C coe ~>G Ty (HL) Tp (G). Hence T, v(G) = 0, Hence in the case of a finite number of transformations the whole measure is concentrated on F, Hence the lemma is established. - 3%,- 8. Convergence Theorems for uy tT for a Class of Absorption Problems. -Throughout this section the following assumptions are made (8.1) Byly,) = 1 1 = 152, ose i.e., there is absorption at each of the points Yas and (8.2) By (A,t) 2 8, (%) each tyi, i.e., the probability of applying A; does not decrease as V5 is approached, Under these assumptions convergence theorems will be obtained for U" and T", No use will be made of theorem 4.2 (due to Ionescu Tulcea and Marinescu), which gives the quasi-complete continuity of U relative to C, (4) until lemma 8.4 is reached. Here for the case where the number of transformations fAs4 is finite, the quasi- complete continuity of U will be a consequence of our convergence theorems. However in the general case, it has been found necessary to appeal to theorem 4.2 to establish the quasi-complete continuity of U relative to Cin), although one suspects that this is unnecessary.. Furthermore, until lemma 8.4 is reached no use will be made of sections 5, 6, and 7 which depend on theorem 4.2, LEMMA 8.1. U preserves thevalues at the points Ys (j = 1,2, ... ), LCs, (8.3) Ux(y,) = x(y,) L = 1,2, woe o -35- PROOF: Ux(t) = ZF B,(%) x(A,t) a 4=1 ao Ux(y) = 2 Bs(y,) x(ajy;)- Since 7 6; (t) =1 and 6, (t) >0O it follows from (8.1) that B(y.) = 8. (Kronecker delta) Hence Ux(y;) = x(A59 5) = x(¥5) since A,y; = Y5- THEOREM 8.1, If x(t) is a fixed point of U in C(M) having the value zero at each of the vertices ¥59 3 = 1,2, «6. » then x(t) = 0. Two continuous fixed points of U which are equal at y5 j =] 925 ase 5 are identical. PROOF: This is an extension of a theorem due to Bellman. Let x(t) be & real~valued continuous fixed point of U such that x(¥5) =O, (§ = 1,2, .0. )e let t, be a point where max x(t) is reached. x(t.) = Ux(t.) = I O,(t,) x(a,t,) eo This is a series of positive or zero terms. Therefore B, (t,) (x(t) - x(A,t,)] = 0, L= 1,25 woe o Since 2 B,(t,) =1, B;(t,) > 0, there exists at least one i, say i =k, such that B,(%,) > 0. Hence - 36 = x(t.) = x(A,t.) . Repeating the above argument with & replaced by A ty we obtain k Co 2 B, (Art) [x(A,t,) - x(A,A,t,)] = 0. By (8.2), B (At) > Bt)» which is greater than zero. Hence x(A,t.) = x(Art) ko k 0’* Repeating this process we obtain = = = n = n, = = x(t.) = x(A,t) x(A,t) x(lim Ay t) x(y,,) 0. Hence max x(t) = 0. Applying the same argument to y(t) = -x(t} we obtain min x(t) = 0. Hence x(t) = 0. The proof for a complex-valued fixed point follows byseparating it into its real and imaginary parts. The second part of the theorem follows from the first part. THEOREM 8.2. vu" converges strongly on C(1.), i.e., there exists a continuous transformation U, of C(O) into itself such that 1 (8.4) lim ||u"« - u,xl| =0 nn» for eachx e C(O). PROOF: The proof is in several stages. (I) For each xe C(O), | u'x(t) i form a uniformly bounded - 37 ~ family of uniformly equicontinuous functions on 1 . PROOF: Since |ju"||. <c (by lemma 4.8) [fomxl 1, < clixll, and hence in particular (Ux) <c{lx\ |, or (8.5) lu'x(t) - U"x(s)| < Clixll, e@ (ts). Hence { u"x(t) } form an equicontinuous family of functions on for each x €& C, (a). Since ium =1 the family is uniformly bounded, Thus the first part of the proof is established. (II) There exists a number & > O, such that at each point + eMi.there exists an index i (depending on +t) for which B;(t) >§& . (§& is independent of t+.) PROOF: Ve set Q(t) = sup B,(t). @e(t) is a lower semi-continuous function on fL and therefore, on the compact set , reaches its minimum, Since £ B;(t) = 1, and each B, (t) > O, it follows that at each point i there exists at least one index i such that B,(t) 70. Hence e(t) > O for each te OX , but since it reaches its minimum %' (say), §' > 0 and @(t) > &'. Let & be any positive number < &', It is clear that the assertion is fulfilled for this choice of & , and the second part of the theorem is established. (TIT) Let x(t) © C,(%), x(y,) = 0 (J = 142, oes)» then given any positive number ec, there exist spheres S.(e) with centers V5 (i = 1,2, ... ) and each of the radius nh , such that if t is in any one of the spheres, ju'x(t) | < ¢/2, all n. Moreover, there exists a - 38 - n fixed integer n independent of t and i such that Ast & S, (e) for all ten ,(i = 1,2, 2... )- PROOF: We observe that from (1) by equicontinuity we may choose nA such that (t,s)< implies that |U'x(t) -U'x(s)| <¢/2 for all n. Choose S, (e) to be the sphere of radius n about y, (i = 1525 coe )o Then for te S, (e) Ju"x(t) - U"x(y,)| < £/2, but x(y,) = 0 and therefore by lemma 8.1, u'x(y,) = 0. Hence for te S,(e) and all n, lu"x(t) | < 6/2. It is an immediate consequence of lemma 3,1, that there exists an integer n nj» such that. At e S$, foreach i and all te. Hence (III) i is established. (Iv) Let x(t) « C. (a), x(y5) = 0. Then given any positive number €, there exists an integer m _ such that [lu"xl| < ©. PROOF: Suppose this not true, ices, ||U"x|| > all nm. Let fx] =H. We assert that under this assumption kn fu °xl| < ot k = 1,2, soe 5 where n, is the integer introduced in (III) and n a=1-35%«1 where & is the positive number introduced in (II). We prove this assertion by induction. It is clearly true for k= 0. Let it be true for ky - 39- (k+1)n n kn (8.6) U o x(t) = uu 2 x(t) kn, “28s (tA, (ay t) eee Pe a Ay tu (Ag ves Ay te fe) Consider t fixed. In accordance with (II), we can choose a positive integer L so that B, (t) > ., But then by assumption (8.2) 2 6 (a) >&, B, (a+) >& ete., so that n -1 n (8.7) A(t) Bla,t) »-. BA? t)> bo. From (8.6) n x(t)| < H(t) 6 (at). B (ay? t)] U ° x(a,%t)| lu + ae ()B, (a 2) eee A (Ay mn, eee Ast) lu x(As fe) fo) , seedy t) n 7 fo) -1 where [{' denotes that one term has been omitted in the summation, kn n ae 4 sees nt ce 0.,, 0 ives, 1, = 4,5 =i, = Ak. Replace [U x(A, +) | by In, 5 ° kn ({u x(Ay t)| = aH) + a‘H and use [ju xf] < aH to obtain (k+1)n 6 , , nv kn, ne iy, |v x(t)] < H(t) Bla,t) .-. Ba” t)(U °x(ay"t) |-a'R) +2 Ps (OA, (Ay 8) eee 6; (A. eee Ay) aH by the induction assumption, Thus (k+1)n (8.8) Ju °x(t)| < -B,(+)6,(a,t) «2 n -1 kn n Ae t) (aH-|U “x(a, t) |) + oH (since ¥ B, (t) =1), n By (III) at e S$ (e) and hence kn (8.9) aXH = fu x(a, | > aH = &/2. - 40 + kn By the induction hypothesis, ||u °x]| < oH and then it follows that a“ > ©, for otherwise the assumption that ||u"x|{ > ©, all n, would be violated. Hence in particular, c/2 < ae and from (8.9) we have kn n aH - |v “x(a, °t) | > aH - ot = at . Therefore by (8.7), (8.8) (k+1)n n Mo lu x(t)| < = po H sate = aly (1 -2, )=as"'n. The right—hand side of this relation is independent of +t, so that (k+1)n [Iu OI] < ak tH, kn Hence our assertion that | |v x] | < aH, k = 152, oe. » has been established. However this contradicts our assumption that ||U"x|| >, all n. Hence there exists an integer m such that | |u"x]| < e Hence we have established (IV). (V) If x€6,(@), x(y,) = 0, then [Ju x] ] > 0. PROOF: this is an immediate consequence of (IV) and the fact that [lol] = 1. (VI) For each xe C.(2), there exists an element yec(n) such that lim [ju -yf] =o. n2>o©o -41- PROOF: By Arzela's theorem we have, since by (1) f u"x(t) } form a uniformly bounded set of uniformly equicontinuous functions defined on a compact metric space, that there exists a subsequence ns iu x(t) } such that My U “x(t) » y(t) the convergence being uniform. Hence y(t) is in C(1). and we have n. (8.10) lim [|u *x-y{] =o. ae.) Since U is continuous n,+1 (8.11) lim |ju* x-vy]] =0. i > 06 Hence ay (8.12) lim U “(x - Ux) =y - Uy, : ima the convergence being in the sense of C(O). Now since by lemma 8.1 Ux preserves values at the points Y59 and also since Ux € C, (2), we have that x= Uxe C, (a), with value zero at each of points Y5 Hence by (Iv) n ||U"(x - Ux)|] > 0. Therefore (8,12) gives y = Uy. Thus y is a fixed point of U and by (8.10) and lemma 8.1, it is clear that it has values x(¥5) at the points Ys However by theorem 8.1, such a fixed point is unique. Thus y is independent of the sub- n, i sequence {u x \ e Hence -42- lim |ju"x -yl| =o. n > 0 Thus (VI) is established. (VII) Theorem 8.2 now follows, for if xe C(.), we have by the Banach-Steinhaus theorem, since C,() is dense in C(f) and | Ju" | | = 1, that lim ||u"x - u,x|| = 0 neo where U, is a continuous transformation of C(Q) into itself and Hu, TI <1. However since U preserves constants, so does Uy and therefore Hu, || = 1. Hence we have established Theorem 8.2. THEOREM 8.3. U, is a continuous linear transformation of C, (2) into itself and (8.13) lim ||" - U, ||, = 0» a) PROOF: Since [|ury | = 1, and Hu" l, <C (by lemma 4.8) we have by applying lemmas 4.4, 4.7 and theorem 8.2 to theorem 2.1, the fact that U, is a continuous transformation of C, (2) into itself, with (8.14) ull, < ¢ together with (8.13). Hence the theorem is established. LEMMA 8.2. U, preserves values at the points 5? i.e. for x ec C(1) PROOF: This is a trivial deduction from theorem 8.2 and the fact that U preserves the values of a function at the points ae (j = 1,2, ... ). - 43 - LEMMA 8.3. ¥, (¢) = 0,6, (+) is the unique continuous fixed point of U having the values 1 at y, and zeros at all v5 (j #4). Moreover i] o_- ao (8.15) 2 LA the convergence being that of C(tL). 1 \t PROOF: UU, (t) = UU,H,(t) = UH. (t) = ¥,(t), since UU, =U dy (8.4). Thus Vs points y 5 (lemma 8.2) we have from the assumption (8.1) that is a fixed point of U. Since U, preserves values at the (8.16) ¥ (5) = 0,8, 5) = By) = % (Kronecker delte), ij Thus v,(t) is a fixed point of U having the value 1 at y, and value zero at all ys (j # i), and thus by theorem 8.1 it is unique. From theorem 8.3, Y= UB, is in c.(2). By lemma 4.5 2 b, =1, convergence being in the sense of C(), but since Uy is continuous on C(£.),it follows that the convergence being in the sense of C(f_). Hence the lemma is established, THEOREM 8.4. The following is an explicit form for U,x where xeC(n), (8.17) U,x = 2, x(y,) ¥; = the convergence being in the sense of C(1). PROOF: Let oO a(t) = 2 x(y,) ¥, (+) i=i oo <max |x(t)]| Z(t). i=1 . ~ Since 35 ¥, (t) = 1, the convergence being uniform (by 3.15) i=i it follows that the series for q(t) is uniformly convergent. Hence eo q(t} « C(M). We thus have g= 5 x(y,) Vas the convergence being i=] in the sense of C(1.). Hence using lemma 8.3 ce ao Uqg= 2 x(y,) UY, = z x(y,) ¥,= qe i=1 i=] Thus by lemma 8,3 and theorem 8,1 we have that q is the unique fixed point having the values x(y,) at the points Ys Since UU, = U, _ (by 8.4) we have by lemma 8.2, that U,x is also a fixed point of U, having the values x(¥ 5) at the points Y5 Hence by the uniqueness theorem 8,1, Uyx = q, and thus the theorem is proved, | LEMMA 8.4. U is a quasi-completely continuous transformation of C, (A) into itself with )= 1 as the only eigen-value of modulus 1. Also (8.18) UA, (t) > ¥, (+t) the convergence being uniform geometric with respect to t and i, PROOF: If the number of transformations Ay is finite, we se. from (8.17) that U, maps CG. (2.) into a finite-dimensional space and so is com- pletely continuous. Hence from (8.13) we see that U is a quasi-completely continuous transformation of Cc (n.) into itself, Observe that we have -45- not appealed to theorem 4.2 (theorem of Ionescu Tulcea and Marinescu). However for the general case, we appeal to theorem 4.2 to obtain the quasi-complete continuity of U with respect to C,(o.). Using lemmas 4.7, 4.8 and equation (8.13) we may apoly theorem 2,3 to U relative to c,(2), to obtain from (2.18) that U; is completely continuous relative to C,(m), and from (2.20) that ~=1 ds the only eigen-value of modulus 1. Equation (2.21) gives . H [|unx = uj,x||,<—>— |I[xl],. 1 L (+ h)® L In particular, n H < —it Ht, h bei < n ’ eing constants (1 +h) (by 4.9). Since U,B, = Vs (8.18) is established and the lemma is proved. THEOREM 8.5. For any y 2 Wun) (8.19) Ty —-Ty (weak-star ) where qT, is the adjoint of Uy. The explicit form of qT, is given by , Co = if (8.20) Typ 2 ,( Jy dy (t)) where I, is a probability measure with all its measure concentrated at the point 5° - 46 - PROOF: (8.19) is merely a translation of theorem 8.2 from Cp (A) into its conjugate space. The proof is exactly the same as that of theorem 7.1. We now obtain the explicit form of Thy « From (8.17) a 4 u x(y;) Wye oo oo Hence (U,x, v) = z x(y,;) (Ys ). Let Ty = 2 T5(Wyo¥ )- This is clearly an element in Yi(Q). It is also clear that (U,x, v) = (x, Ty ) all xe C.(). Hence T! = U, = T,. Thus Ty = 2 1, (594) and the theorem is established, Probability Interpretation of ¥;(t). In section 5, it was pointed out that vA, (t) represents the probability that given the initial state of our systems was +t, that at th the end of the n~ time interval, the transformation A, is applied. i ¥, (t) = Jim wp, (t) thus representsthe limiting probability of No -* applying As given that initially the state of the system was t,. Another point of view is obtained from (8.20), If p(t) = J t ° i.e, the probability measure concentrated on point ¥y then HP TB M5) Ty -47 - so that ¥; (44) gives the probability that if the initial state is toe the limiting state is Y5° To sum up, we have two probability interpretations for ¥;(t): (1) Limiting probability as n->o that at the nv step A; is applied, where the initial state is t. (2) Probability that the limiting state is vss given that the initial state is t. - 48 ~ 9. Properties of U and 2 for the case when there exists an index k such that 6, (+t) > 0 for all te with the possible exception of x In this section we assume the existence of an index Kk such that (9.1) A(t) >o for t#y, (0< B(y,) <1). We generalize a method of Bellman to obtain a fixed point theorem similar to that of theorem 8.1 THEOREM 9.1. Under the above condition, the only fixed points of U in C(m) are constants. PROOF: Let x(t) be a fixed point. Let te be a point where the maximum is achieved. Assume that max x(t) # x(y,)« x(t.) = Ux(t,) = % H(t.) x(a,t,) [o#) ZH, (t)[x(t,) ~ x(ayt,)] = 0. this is a series of positive terms. Hence B,(t,)[x(t,) - x(A,t.)] = 0. tf B,(t,) = 0 then by (9.1} t, = ¥, and max x(t) = x(¥;) contrary to the assumption, Hence x(t) = x(Ay to)» -49 - Thus AY with ty replaced by Ay t, to obtain t, isa maximum point for x(t). Apply the above argument ; 2 _ B (at) fx(a,t,) - x(ayt.)] = 0. Again, By (A,t,) # 0, otherwise the assumption is contradicted. Hence x(A,t_) = x(Ant ) ko ko and proceeding in this way we obtain x(t.) = x(At) = = x(A;t.) = lim x(at,) = x(y,) nro since x(t) is continuous, but this violates the assumption that x(t.) # x(y,) e Hence x(t.) = x(y,) ¢. max x(t) = x(y,,) Consider the function y(t) = - x(t). It is a continuous fixed point of U. Hence max y(t) = y(y,) or min x{t) = x(y,) oe max x(t) = min y(t) = x(y,) or x(t) = constant, The proof for a complex-valued fixed point is immediate by splitting into real and imaginary parts. Corollary: U,x(t) =k (a constant dependent on x). - 50- PROOF: From (6.2) we have that U,x is a fixed point of U, for each x e C(q). Hence the corollary follows from the theorem. THEOREM 9,2. If is any probability measure, i.e., y(E) >0 for every Borel set and f (A) = 1, then Tv ©) = V(E) where V(E) is a probability measure independent of v (EZ), so that n we may say + 2 ry converges in distribution to V , where V is 1 a probability measure independent of the initial distribution a e Moreover V is the unique probability distribution which is a fixed point of T. PROOF: Let fy /' be two probability measures, Let 1, /f =V, n so that by (7.1), “ Z ty — V¥ (weak-star convergence). 1 n a 1 k let Ty! = V', so that 2 % Ty '—av. For any xc ,(M) n n (x, Ve-vi) = lim (x, + x ry -+ z ry) no 1 1 n Lim (x, + z T(r- yp ')) n> n Lim Ce 2 v*x, vr") n-o = (U,x» v- +") by (6.1) (k» f= y") by corollary to last theorem J k a(y- py!) 0. -51- Hence V¥ = vt. From (7.4), T,/ * V is a fixed point of T. Let Yo be another fixed point of T which is a probability measure, = = Vz then TYG Vo but from above, T, Vo V. Hence V oe Thus the theorem is proved, - 2 10. Convergence theorems for y and go for a class of problems —— —— a —_— se similar to those considered in section 9. In this section we make the assumption that (10.1) Z 6,(t) B,(s) # 0 tse N. This is almost equivalent to the class of problems considered in section 9, for if (9.1) were strengthened to B, (%) >O all t, for some k, then(10.1) would be consequence. Under thisassumption a convergence theorem for U" will be obtained by straightforward application of the method of Karlin {2]. As is pointed out by Ionescu Tulcea and Marinescu, this could be obtained by a method of Ocinescu and Mihoe [3], but according to their theorem as stated, this would apply to the case where B, (%) >0O all t, for some k, We shall not make use in this section of the theorem 2.2 or its consequence, theorem 4.2, to derive the quasi-complete continuity of U with respect to C,(). This will be a consequence of our convergence theorem. We first prove the following lemma, LEMMA 10,1. Let two particles start from t, s respectively. We say that a success occurs at a given unit of time if the same transformation Ay is applied to both particles at the same time, otherwise we say that failure occurs. Then a success run of length r (r any positive integer) is certain to occur in finite time. ~ 53 - co PROOF: The probability of success at initial step is 2 B,(t)A,(s). This being the sum of a uniformly convergent series of continuous functions (c.f. lemma 4.5) on the product spaces Q x © is contimuous. Hence it achieves its minimum § which by (10.1) is > 0. Thus the probability of success at the initial step is >) . The con= ditional probability of success at the second step is > & ,and in general the conditional probability of success at the KP step is > & . Consequently, by the theory of recurrent events, a success run of length r is certain to happen in finite time. Thus the lemma is established. THEOREM 10,1. U" converges strongly on C(Q), Lees (10.2) lim |ju"x- kK |] = n> co for each xe C(9.), where Ik is a constant function dependent on x. PROOF: Let x(t) eC io). U'x(t) = U"x(s) = hoe gp. 1, (85, (s)(u" x(a, ° -vu" "x(a, s)] = 2B, (+8, (8), (ag 8085, (ay a) LUP McCay ay t) - OP ECay ay 8] =2 6, OF; es Reet t)B, (A, 8)... By (A, one Ay t)B, (A; seed, 8) 4, "4g to dn a re ee n=? n-r r 1 r 1 We now divide the right-hand side into two parts 5S, ,5. We take all 1°°2° the terms for which i. * Jy (k = 1, ... 5 r), and place these in S,° - 54 = The sum of the coefficients of these terms clearly represents the probability of a success run of length r occurring in the first r trials of model discussed in lemma 10.1. The remaining terms are placed in So» and clearly the sum of the coefficient of these terms represents the probability of not obtaining a success run of length r ending on th the r trial, We now make a further reduction of terms in So as above. We transfer to S, terms of the type By (18; (S)A, (Ag tBy (Aj 8) ee ne ee a a eh n-r-1 p say (Atta gy SUT, eek OU Ag Ay Ajs)] Observe that i, # Jy. otherwise this term would have been included in So- The sum of the coefficients of this set of terms is clearly the probability of a success run of length r ending at the (r+1)5* trial in the model discussed in lemma 10.1, where the first trial consisted of failure. Thus the sum of the coefficients in S, represents the probability of a first success run of length r ending at the yh or the (r+1) 8? trial. Hence the sum of the coefficient of the terms ‘in So represents the probability of no success run of length r in r+1 trials, Proceeding in this manner (10.3) U"x(t) = U'x(s) = S, +S where Is, | < 2 (Probability of no success run of length r in n trials) max |x(t)|. Let n+», by lemma 10.1 (10.4) S, > 0 uniformly with respect to tse. - 55- Consider 8, « It is of the forn Eplwix(ay ++. At )- UiK(ay oe. Ayo] where 2p< 1. k k k Iu x(Ry oes Ayr) x(Ay e+ aio) < M(U"x) O(Ag oes A T oA, cooks Tr r o). i, 1 Apply lemma 4.8, ices, | |U"| I. < C and (3.1) to obtain k k JU"x(Ay eeeAp 7) — Ux(A, weed, OL OW Tell, @ (79) r 1 r 1 <D |Ixl|, since @(7,0) is bounded on a compact set. % Isl <DW IIxl], XP <0¥ [lel Hence for nor |u"x(t) - U'x(s) | = Is, + s, | < Is,] + Is,| <0W IIxll, + Iso Choose r 9 D a ll, < ¢/2. Having chosen r, by (10.4) we can choose N so that for n>N, Is. | <c€. Hence n>N Ju"x(t) - U"x(s)| < ec. Hence (10.5) Lim |u"x(t) - u"x(s)| = 0, neo the convergence being uniform on Q x O_. Consider the set f u'x(s) { - 56 - where s is some fixed point in 1. . This is a bounded set of numbers (bounded by max |x(t} |). Hence there is a convergent subsequence such that n. For any te TX, n . ns n U *x(t) - k= (U “x(t) = U n *x(s)) + (U *x(s) =k). It follows by (10.5) that my lim |uU “x(t) - k,,| = 0, io k. being a constant dependent on x, and the convergence being uniform with respect to +t. Choose i such that n, Ju *x(t) - kl<e all te tf n,+ eo n, x(t) = f= | 2 Bit) “x(ast) ~ i) < j S ©» uM—B n. B,(t)|U “x(a,t) - k| and in general, n, 2 ly ~ x(t) - k | <& Hence ju"x(+) - | converges uniformly to zero, i.é., lim | |v" - kK] = 0 for xeC,(M). n2>o Let x(t) ¢ C(m.). Since [jon {| =1 and C, (a) is dense in C(.), it follows by the Banach-Steinhaus theorem that - 57 - lim. ||U"x - U,x|] = 0 nwo where U, is a continuous transformation of C() into itself such that ||U,||[ <1. Since U, obviously preserves constants, [jul] =. Since U,x =k for xe C.(M)> (10.6) U,x = k, a constant dependent on x, for all x eC(M). Hence for xe C(M) lim |{u" - xk || =0, no x and the theorem is established, THEOREM 10.2. U, defined in the last section by 1 U,x = k. is a continuous linear transformation of C(m) into C() and C,() into 6,(4). Moreover (10.7) lin ||u" -v, Hh, 20 n > co and U is a quasi-completely continuous transformation of c,(2) into itself. PROOF: We have ||u"|| = 1. Also Hort, <C by lemma 4.8. Hence by means of lemmas 4.4, 4.7, and theorem 10,1 we see that the hypothesis of theorem 2.1 is satisfied and hence U, isa continuous linear trans formation of c, (2) into itself and lim | ju" - 1,11, = 0. n2o Since U, maps 6, (9) into the one-dimensional space of constants, it = 58 - is completely continuous, Hence U is quasi-completely continuous as a transformation of C, (2) into C,(n). This proves the theorem, - Observe again as remarked at the beginning of the section, that no appeal was made to theorem 2.2 of Ioneseu Tulcea and Marinescu [8,9 in order to obtain this result except through the easily proved fact that Homi, < Gs which we gave as a separate lemma (lemma 4.8). Now that we have obtained the quasi-complete continuity of U, all the results of sections 5, 6, and 7 are available. It is clear that the transformation Uj» that we have obtained in this section, is the same as that introduced in those sections. By means of (10.7) some strong results can be obtained by appealing to theorem 2.3. LEMMA 10.1, = 1 is the only eigen-value of modulus 1 of U with respect to C,(). Also (10.8) vA, (eu, B, (t) = ¥, (constant) the convergence being uniform geometric with respect to t and ie PROOF: The first part follows from theorem 2.3, Equation (2.21) gives H |Ju™ - U xl I, < De [x1 1, H,h constants. In particular —H_ < Ht 1 so H' ,h constants(by &.9)). (1 + h) By theorem 10.1, U58; = Ws is a constant. Hence (10.8) is established and the lemma is proved, ~ 59 - As has been pointed out, wy which is a constant represents the limiting probability of applying the transformation A, at neh step as n +o, given that the initial state is t. Then since Ly is a constant, this limiting probability is independent of the initial state. The above lemma was established by Ocinescu and Mihoe for a finite number of transformations where there exists one k such that 6, (t) > 0 for all t. THEOREM 10.3. For any V e Wn) (10.9) Ty — Ty (weak-star ) where T, is the adjoint of Ue. Moreover if vr is a probability 1 measure ythen (10.19) Ty = VY where V is a probability measure independent of v « It is the unique probability measure which is a fixed point of fT. PROOF (10.9) is merely a translation into the conjugate space of the result of theorem 10.1. The proof is exactly the same as that of theorem 7.1. The proof of the second part of the theorem is the same as that of theorem 9.2, ‘It would be desirable to have some information concerning the limiting measure. The following result holds for constant non- zero probabilities B;(t). THEOREM 10.4- Let 6, (+t) = B; be a non-zero constant for each i, Then the limiting probability measure v (10.10) is continuous, i.e., - 60- the measure of each point in 1 is zero. In fact T, a is continuous ‘for any measure ye MO). PROOF: Let V(t.) > 0 where t, is a point in © . Choose vy 7 toe There exists an n_ such that Ayo. does not include t 0° Now sime V= TV we have V(t.) =26, we B var oe att). ° 44 Jn Jn J, ° Each coefficient on the right-hand side is greater than zero and the sum of the coefficients is 1. Moreover v (Apt) = 0 since —n, | Ay te i} » Hence -1 1 j ese A t,). V(t) < max V{(A j 1 Jyoeeesd, n ~1 =-1 Hence V(t.) < VAS eos Aj to! for some Sys cee» June Apply the same argument to t, = a5 ore AF toi we obtain a sequence n 1 of points ty? ths tos eos such that V(t.) < V(t.) < v(t.) < V(t3) < see ‘Since there is strict inequality no two of the points coincide. Hence there is a countable set each of which has measure > v(t.) > 0. Hence the measure is infinite, This being a contradiction we have V(t.) = 0. Thus since the same proof may be applied to Ty for any pe Wu(n.), the theorem is established. We conclude this section with the following theorem, - 6] - THEOREM 10.5. If va,O = AL , and if B,(t) >O all i, all te 1 then there exists an n_ such that U" isa strictly positive trans=- formation, i.€e, (10.11) af x(t) >0O and #0 then U'x(t)>O teN, PROOF: By hypothesis F (defined (3.4)) is the full space 1. Let te be such that x(t.) > 0. By lemma 3.2 there exists a sequence of integers i> to» eee 9 i ee» such that A, > A; 1 1 + A. OL ees eee A A, eee A; cen ees > t e i, i, 15 n fe) Since x(t.) > 0 there exists a neighborhood U of te for. which Choose n so that A, «4, NM cU. 1, n n = U'x(t) 2; (8s (a; t) eee ae ae aj} x(Ay see 5,0). Since A, eee As t ¢ U, and the coefficients are > 0, it follows i 1 n : ‘from the last equation that U'x(t) > 0, and the theorem is proved. =~ 62 = 11. A Special problem involving attractions towards the vertices of a simplex. We now introduce a special model which is a generalization from 1 to N dimensions of the learning model considered by Karlin. Let . be a simplex in Ey (Euclidean space of N dimensions). Let V,,5 V. ne sees Vire4 be the vertices of the simplex. Any point 1? of OL. is given by its barycentrice coordinates t= (tystyy ove ty) where N+ > = Let Bs denote the (N+i) x (N+1) projection matrix 0 QO 0 0 0 0 0 71 #1 =«1 1 yeh row. 0 0 ¢) i matrix, We define our transformations on the simplex as follows Observe that B,t=y,. Let I denote the identity (N+1) x (N+1) (11.1) A; = AI + (1 - »,) By O< <1 i = 1,...,N+1 Clearly A, represents a transformation which carries a i point R into a point R' on the line RNY where (11.2) (RIV,) = A, (BV,). - 63 - i.e, A, represents an attraction towards the vertices Vie We have by (11.1) that if +t = (ty toseee s tray) is any point of . , the coordinates of the transformed point are given by At...) (1163) ASE = C Mites Aytos ees Rte tT — Ms Atayperers Atay It is obvious that i = - (11.4) Ao Jelt, 21 »h ay has as domain A, and is defined by AD = Wp 1+ (1 - YDB It is clear that this set of transformations satisfy the conditions imposed in section 3. In particular e(A,ts Ass) < NE (tes) all i,t, where \ = max )\ i N+1 N+1 LEMMA 11.1. U a,o OQ. if and only if FY 42 Ne 1 1 PROOF: A, = felt, 21-2,} '- >t te f\ (A,o.)° if and only if o<t i A (a, yo = tlt, i<d- dp i=l, cece 9 Ntl, In order to obtain a point t satisfying these conditions, we must select t; (i = 1,...,N+1) to satisfy the above inequalities and in addition 7 ts = 1. This can be done if and only if - 64 = N+1 XY (1-2) >1 1 or N 2 a; < Ne N+1 N+1 Thus f) (a,n)° is non-void if and only if > As <N. By taking 1 1 complements the result follows. tet |S| denote the Lebesgue measure of any set. N+1 | LEMMA 11.2, If F A,<1 then |=| = 0 where F is defined by 1 (3.4) PROOF: = fas | = D5/O] = 2, taking [.o[ = 1 Ny « |U A, Al s XA; i 1 N+ N i lay VANS AG LT DG * N+1 y Ny2 | Y; aasal< Cr ah) and proceeding in this manner we obtain N+ ala | < ( z 4)" using the notation introduced in section 3. Hence In glnly | = 0, i.e., |F| = 0, and the lemma is proved. Since the model under consideration is a special case of those considered in previous sections, all the limiting theorems proved hold for this model. However we may obtain some properties con- cerning the convergence of derivatives of U'x for this model, - 65 - We begin by proving a theorem which for this model gives more information than lemma 4.8 (i.e., | ju" les < C}, when we have differentiable probabilities B,(t)- Consider t,; tos coe sy ty as independent variables, tye = Tm tym tam sees om tye We write x(t) = x(t,» bos eos 9 ty) let ¢ ™’ a) be the set of m-times continuously differentiable functions. THEOREM 11,1. Let f(t) € c™(), If x(t) © C™(M), then there exist constants Ky depending on x(t) ( £=1,...,m) such that Lon 8 u x(t) < kK nh = 1,2, eo at. atv | 4 | 4 seo N for all 4» 15» eee » iy such that i, +i tere +i Fisn, 1 2 i.e., all first m derivatives are uniformly bounded, for each x(t) & ce"). PROOF: te [|x|] <K, then ||u'x|| < K, so that the theorem is true for £ = 0, Suppose the theorem is true for £- 1, Ux(t) = 5 By (t) XC Dityseees Arty + 1D seees Dyty) i=] + +1 6b) x( N+1 Li aeees Dye by? - 66 - £ N+1 L 2 atte. atl = © lat. tat.*%... at 1 cee Oty iyoeerdg [Or Og ee Oy J L dt, eee Ob js 4-1 1 N where C is a constant bounding sums of absolute values of derivatives of B, (t) with binomial coefficients, Observe that N+1 g L x B,(%) DY. < max NV. = p(say) . i i i=i i where p< 1. Lon 2 nt j .m-1_ nex (2 rate) <p max [2 YD) 6 max [AU tt teas net, ted; Mat js t-1 nat,” at oem (t) <p max i +c! (by induction hypothesis) td nat,§ tne < p* max ao w(t) + pc! +! bei mat. j at tod, not, < constant. Hence the theorem is established by induction, - 67 = Corollary: Under the conditions of the theorem, the sequence of functions a n W(t) =& a 7 [u'x(t)] nat form an equicontinuous system of functions on 1 for each set of N . indices ij9 eee 5 iy such that 2 i, =r<m-t1, We use the notation D x(t) to stand for any one of the rr) gerivatives of x(t). THEOREM 11.2, Let x(t) © C™(n). If U"x(t) converges uniformly to U, x(t) then (1.5) oF (u'x(t)) > 0° (u,x(t)] O<r<m-1 the convergence being uniform on 1. . PROOF: We prove the theorem by induction. By hypothesis the theorem is true for r= 0. Suppose the theorem is true for r-# 1, By the corollary to theorem 11.1 W(t) = Diu"x(t)} form an equicontinuous family of functions on 11 . Moreover, by theorem 11.1 they are uniformly bounded, Hence by Arzela's theorem there exists a subsequence W,. (t) such that i (11.6) lim Wy (t) = w(t), irza i the convergence being uniform on ©. Suppose At least one of the indices i, #0. Let i, #0. Let r-1 _ ar! rs ce Pe (mT at.2 ) at, jee? By the induction hypothesis tim DP! (u(t)) = oP (u,x(t)) kao the convergence being uniform, In particular k, lim pro! (u *x(t)) = pro! (u,x(t) | i > but by (11.6) this sequence differentiated with respect to- %, converges uniformly and hence r w(t) =D (U4x(t)) . Hence W(t) is independent of the subsequence, and the theorem is proved. +his theorem means that if B, (+t) E c"(n), and satisfy either the conditions of section 9 or those of section 10, and if x(t) is any function in C™(1) then the first (m-1) derivatives converge uniformly over , LEMMA 11.3. Everypoint t inthe set F may be represented in the forn -69- (11.7) t= (1 95) BL + uO -%4)) BL + 200 + », veo hy (1 - As ) B, + eee 1 n-1 n n where i,, los ooo y in» ees is a sequence of integers ranging from 1 to N+i, This representation is not necessarily unique. PROOF: By lemma 3.2 there exists a sequence i,, in, ... such that (11.8) A NIA, AA DA, A, A, XL > sees >t i, 1 12 1 72 73 ~ limt =t, n where t = (A, T+(1 -d, )B, CA, T+) - A, )B.) OA, IH(1 -A, JB, os n My 17 Pa SM i) oe ee - and os is an arbitrary point in . Now BB. = Bye Thus we have t =A A oo. A, I4(1 =r, JB, tA (1 = DB, + eee n i, 15 in i, i, i, i, i, (1 -% )Bs . n n Letting n>, the result (11.7) follows. - 70 = 12. Properties of the One-dimensional Learning Model. In this section we specialize the model of the last section to the case where N= 1. This is the model treated by Karlin [2]. Some additional properties are obtained in this section. Here 1 is the unit interval. Write +t for ty so that by =1- +t. We change the notation of the last section in that we replace the index 2 by the index 0. Thus our attractions consist of Ay towards the origin and A, towards the point 1 where 1 (12.1) At = ASts At = yt +1- Aye By lemma 3.2, the set F is closed. It is shown by Karlin [2, page 753] that if r, + ro <1, then F consists of a Cantor-like set. If A, + , #1, then it is clear that F=0,. Any sequence a = (a49 Boe ses ) where a, ranges over the k pair of numbers 0,1 gives rise to a point +(a)in Nl, according to lemma 11,3, by the equation n=1 n=1 2 a. n=I- FY a _ < 1 3 1 2 (12.2) (a) = (1 -2,) 2 a4 A, . If: » + B, <1, then each point in F is described by a unique sequence a, This follows from the fact that no point can be in the range of both Ay and Ay: If Xo + a, * 1, there is exactly one point in the range of both A, and A,» namely, the point » o(= T=) »° At most two Sequences 15 Go give rise to the same point, and such sequences considered as the coefficients of the dyadic expansion of a number -~71 = between gero and one correspond to the same number. Again, this statement is easily verified. Let a= (a4 Any eee ) at = (aly aby eee ) Define a<a' if a, <a} for the first inequality of corresponding elements (ices, a, = at, wee 5 a 4 = at 4). With this convention we have the following lemma: LEMMA 12.1, If d, + a, <1, then a <a! implies that t(a) < t(a') PROOFs = Let a, = ats 2) = aby woe o A) = Alyy a, = Op af = Te k-1 k-1 n=1 n= z a, kel- * as wo x a, nck & a, t(a!) = t(a) 2 (1-0,) A [i- 2 ae re] 1 a?) ke ket ket Za, kl-Da oo! Gem) A AF te se wT AG fle 2 ° c+ since ay = 0 k=1 k=1 Soa. kei-Z a, 7 7 1 7 La > (=m) [1-7] 1 20 if and only if ot hy S16 We now define transformations Ags Ay on the sequences a =(a45 aos eee) by - 72 = (12.3) Ao = (0, 19 By vee ); Aya = (1, a5 By eee) Tt is clear that (12.4) t(Aoa) = Ajt(a)s $(A,a) = A,t(a) THEOREM 12,1. Let X + » <1. If Bit)» p, (t) are constants De» B, respectively, and if F(t) is t ie cumilative distribution corresponding to the limiting measure V(E), defined in section 10, then +t, F(t) can be expressed in the following parametric form n=1 n=) x a; n-1— > ay t(a) = (1 =,) ee a, »,| » ° n=1 n=1 ~ > a, n=1- 2 ay (12.5) G(a) = (1 - g,) 2 a p,' B, i. L G(t) = G(a(t)) ter. PROOF: It is only necessary to define G on F for v(F°) =O by lemma 7.1. It is clear from lemma 12,1 that the first two formulas in (12.5) are monotonic functions of a, and thus G(t) is well-defined and is monotonic on F. (If No + D4 = 1, then two a's give rise to the same t(a) but these two a'; give the same G(a), so that there is no ambiguity.) G(0) = 0, G{1) = 1. Hence G(t) represents a distribution on F. Clearly it is continuous on F. By extending it in an obvious way we have a distribution on £1. - 73 < Our object is to obtain the unique fixed point of T, i.e., Vssuch that (12.6) V(E) = Bo vac) + £.V(A5'E). if BE is in F°, so is ann, Ay's. Thus, since v(F°) = 0, it is sufficient to obtain a continuous probability dis- tribution H(t) (see theorem 10.4) on F such that (12.6) is satisfied, If te A O , but not in A.M, then (12.6) gives | a -1 (12.7) H(t) = DEAS t). If teA,, but not in Aja, then (12.6) gives (12.8) a(t) = BH(aT't) + 6. Now tea MAN AO if and only if A) + A, =1 and t= Vo. For this point, HC) ,) = B, which is cc:.sistent with both the above equations. ‘+hus the continuous distribution H(t) which satisfies (12.9) H(A,t) = B H(t) (from (12.7) ) (12.10) H(A,*) = B,H(+) +1 b, (from (12.8)) is the required distribution. Now we may obtain for G(a) equations similar to (12.4), so that we find G(t) satisfies (12.9) and (12.10) for all terF and therefore all te fF, and thus is the required distribution, Hence the theorem is proved, - Th a An obvious question to be asked in this type of problem is whether or not the limiting distribution is absolutely continuous or singular. The following theorem provides an answer under very special conditions. THEOREM 12.2. Let Dy = D, = 1/2. Under the conditions of section 10, the fixed points of T are singular except for the case B(t) = 6,(t) = 1/2, In this case the fixed point is absolutely con= tinuous,and the unique fixed point which isa probability distribution is given by F(t) = t. PROOF: V(E) = TV¥(E) = J 6, (t) av(t) + f Bt) dv(t). at's ACE Let F(t) be the cumlative distribution corresponding to V. Consider first », + 2, >1. “he above equation yields the following pelations for F(t): v Ao J Bp(t) ar(t) fs) tt eh, TEAS | R(T) = | B,(t) aF(t) + J B(t)aF(t) ° [+] { ay 1 T> 45 rr)= J Blt) arte) + Jp (edarct. S - 75 = r Suppose F(T) = f(t) dt. os es. «6F'(4") = f(T.) aeGe Then the above relations give O<T< 1-3 £(T) = x 6, ( TAS) £(TA 9) Dee IA, ST SAS ECT) = a,| . Je | . (12,11) + x BM T/y,) (7A) ae <1: _ 21 r-(1 -);) T-(1=h ) No <a <1; f(r) = wall + f x, Abe Now assume the given hypothesis n = r, = 1/2. Consider the Fourier coefficients of f 1 f(n) = J £(t) eorint dt. fo Using the above relations we obtain 1 i 1 . . A(n) = f B(x) P(x) eT ay + if A, (x) £(x) etinx .rin 4. ° ) 1 : f. f(x) eorinx ax ) oe (2n) K ln). -~ 7h = Thus B(n) = B(2n) = ...ee00085 = O by the Riemann-Lebesgue lemma, Hence f(n) = 0, all n. Therefore, f(x) = const. Since F is a probability distribution, it follows that f(x) = 1. From (12.11) we have o< T< 1/2 £(7) = 26,(2T ) £(2T ) “*. 1 = 26 (2T ). Hence B(t) = 1/2 all t. % 6, (t) = 1/2. The transformation T preserves absolute continuity, and singularity. Since any measure V = Vi + V5 where Vy is absolutely continuous and V5 is singular, the decomposition being unique, we have from the uniqueness of the fixed point V of T (under the conditions of section 10) that the fixed point is either absolutely continuous or singular. Hence the theorem is proved. . Finally we note that if g, (t) = Ay (t) = ro then the unique fixed point of T 4s given by F(t) = +t. This may be verified directly or it is easily seen from 12.5. [7] [2] [3] [4] [5] [6] (7] [8] [9] [10] [11] [12] -77 - REFERENCES R.R. Bush and C.F. Mosteller, A mathematical model for simple learning, Psych. Rev. 58 (1951), 313-323. S. Karlin, Some random walks arising in learning models 1, Pacific Journal of Mathematics 3 (1953), 725=756. O. Onicescu et G. Mihoc, Sur les chatnes des variables statistiques, Bull. Sci. Math. 59 (1935), 174-192. We. Doeblin et “, Fortet, Sur des chatnes 4 liaisons complétes, Bull. Soc. Math. France 65 (1937), 132-148. “N R. Fortet, Sur des operations linéaires non-completement con= tinues, Comptes Rendus, Acad. Sei. Paris 204 (1937), 1543-5. R. Fortet, Sur l'iteration des substitutions algebriques lineaires a une infinite de Nariables et ses applications ala theorie des probabilités en chaine, Revista de Ciencias 40 (1938), 185=—262, 337-448, 481~536. R, Fortet, Sur une suite également repartie, Stud. Math. 9 (1940), 54-70. C.T. Ionescu Tulcea et G. Marinescu, Sur certaines chaines a liaisons complétes, Comptes Rendus, Acad. Sci. Paris 227 (1948), 667-669. C.T. Ionescu Tulcea et G. Marinescu, Theorie ergodique pour des classes d'operations non-completement continues, Annals Of Mathematics 52 (1950), 140-147. Ke Yosida and S, Kakutani, Operator=theoretical treatment of Markoff's Process and mean ergodic theorem, annais of Mathematics 42, (1941), 188-228, F, Hausdorff, Mengenlehre, third revised edition, Dover , New York, S. Kakutani, Concrete Representation of Abstract (M)-Spaces, Annals of Mathematics 42 (1941), 994-1023,