SOME APPLICATIONS OF THE METHOD OF THE CHARACTERISTIC EVENT by Robert Frazee Main, j r . B . S c , Oregon State U n i v e r s i t y , 1967 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE i n the Department of Mathematics We accept t h i s thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA June, 1973 In presenting t h i s thesis i n p a r t i a l fulfilment of the requirements for an advanced degree at the University of B r i t i s h Columbia, I agree that the Library s h a l l make i t freely available for reference and study. I further agree that permission for extensive copying of t h i s thesis for scholarly purposes may be granted by the Head of my Department or by his representatives. I t i s understood that copying or publication of t h i s thesis for f i n a n c i a l gain s h a l l not be allowed without my written permission. Department of Mathematics The University of B r i t i s h Columbia Vancouver 8, Canada Date September 15. 1973 i i ABSTRACT A method of in t e g r a t i n g over d i f f i c u l t sets i n E n by replacing the c h a r a c t e r i s t i c function of the set with a discontinuous i n t e g r a l has been used by Markov, Chandrasekhar, Melzak, and others. This thesis employs t h i s method i n some problems a r i s i n g from random walks. A discussion of the d i f f i c u l t i e s encountered and suggestions f o r further study are included. i i i TABLE OF CONTENTS Page I. Chapter I 1 Introduction 1 II. Chapter II 6 Random Walks 6 1. Markov's Method Applied to the General Problem of Random F l i g h t s 6 2. Solutions to Some Problems A r i s i n g from Random Walks i n the Plane 8 I I I . Chapter I II 14 Geometrical P r o b a b i l i t y 14 1. Quadrilaterals 14 2. Knots and Linking 19 I. Linking of a Triangle and a Straight Line 19 I I . Knotting of a Five Step R e c t i l i n e a r Path 21 I I I . Knotting of a Closed Six Step R e c t i l i n e a r Path 23 IV. Chapter IV 26 1. Crossing of a Fixed Plane by an n-Step Random Walk 26 2. Behavior of f(n,d) as n Gets Large 32 3. Weight of a Problem 34 V. Chapter V 36 Some Useful Discontinuous Factors and Further Suggestions 36 VI. Bibliography 39 i v ACKNOWLEDGEMENTS I have received considerable help and encouragement from Dr. Z.A. Melzak i n the preparation of th i s t h e s i s , and f o r t h i s I am deeply g r a t e f u l . CHAPTER I INTRODUCTION In t h i s thesis we s h a l l be concerned with s e t t i n g up, handling, and evaluation of c e r t a i n i n t e g r a l s of the form (1) I = Y J f(x-,....,x )dx.....dx 1' ' ny 1 n where each x^ i s a vector v a r i a b l e ranging over a subset S of some m-dimensional Euclidean space, and Y i s a subset of the n- f o l d Cartesian product S n = SxSx... . This may be interpreted as follows : l e t a configuration C consist of n points taken i n S, l e t f = f(C) be an integrable configuration f u n c t i o n , and c a l l a configuration successful i f i t meets a condition Y ; now I i s the i n t e g r a l of the configuration function taken over the set of a l l successful configurations. Depending on whether the condition Y on C i s geometrical, i . e . invariant under r i g i d motions of C as a whole and therefore independent of S and of the p o s i t i o n of C i n S n , we may divide our problems into those concerning i n t e r n a l and external configurations. Further c l a s s i f i c a t i o n of problems of t h i s type w i l l depend on the number and type of elementary conditions describing Y. Writing (1) f o r s i m p l i c i t y as 2 I = j f(x)dx Y we s t a r t the processing of I by rewritingg (1) as (2) I = l y ( x ) f ( x ) d x Sn where l y ( x ) i s the c h a r a c t e r i s t i c function of Y i n S n (that i s , l y ( x ) i s defined over S n and i s 1 i f x e Y and 0 otherwise). This may appear to be a mere formal device f o r t r a n s f e r r i n g the d i f f i c u l t y of the problem from the case of an easy integrand and d i f f i c u l t range of i n t e g r a t i o n to the reverse case of hard integrand and simple range. Suppose, however, that the c h a r a c t e r i s t i c function 1 , or the discontinuous factor as i t i s often c a l l e d i n t h i s context, has an i n t e g r a l representation l Y ( x ) = F(x,u)du so that I = F(x,u)f(x)dudx Sn G The i n t e g r a l F(x,u)du, being a discontinuous f a c t o r , w i l l be d i s c o n t i n -ue uous as a function of x on the boundary of the successful set Y. Since most discontinuous f a c t o r s have i n t e g r a l representations i n v o l v i n g i n f i n i t e l i m i t s of i n t e g r a t i o n , i t w i l l s u f f i c e to s a t i s f y the conditions i n [8] to 3 interchange the order of i n t e g r a t i o n . I t w i l l usually be the case that the boundary of Y i s of n-dimensional content zero, hence i f f p(x,u)du i s boundedly convergent on S n and uniformly convergent on S n ~ {boundary of Y} then the interchange w i l l be j u s t i f i e d , that i s ; F(x,u)f(x)dudx = F(x-,u)f (x)dxdu SnG G S„ If the order of integrations may be interchanged then (3) F(x,u)f(x)dx du ; G S. n i t happens sometimes that the inner i n t e g r a l can be evaluated, giving us I = H(u)du which w i l l often be a simpler representation of I than the o r i g i n a l equation (1) and may even lead to a complete evaluation of I . In the s p e c i a l case when f(x) = 1 and the volume of S i s normalized to be 1, the i n t e g r a l (2) i s the p r o b a b i l i t y that the configuration condition Y i s met when the n points making up the configuration are taken independently and uniformly at random i n S. This shows that our i n t e g r a l I of (1) i s e s s e n t i a l l y the con d i t i o n a l expectation of f with respect to the condition Y. 4 I t i s therefore not s u r p r i s i n g that the method we have sketched has been heavily applied to various p r o b a b i l i s t i c problems of the geometrical-comb inatorialv.variety ,-and' 7especially 1" to •-• various'-: questions in v o l v i n g random walks. In p a r t i c u l a r , Markov [1], used i t to f i n d the basic p r o b a b i l i t i e s i n the general case of the problem of random f l i g h t s , Rayleigh and Kluyver employed i t to solve a generalization of Pearson's o r i g i n a l random walk, and more recently Melzak [2] applied i t to handle i n t e r s e c t i o n problems i n plane random walks. These developments are summarized i n Chapter I I . Several geometrical configurations i n two and three dimensions are considered i n Chapter 3. We f i r s t generalize Sylvester's four-point problem : given four points independently and uniformly at random i n a plane convex region R, what i s the p r o b a b i l i t y that the r e s u l t i n g configura-t i o n i s a convex q u a d r i l a t e r a l ? By using four l a b e l l e d points we have here three configurations : convex, concave, s e l f - c r o s s i n g . We also consider the analogue of f i v e points i n a three-dimensional convex region. F i n a l l y , we take up closed r e c t i l i n e a r paths a r i s i n g from s i x l a b e l l e d points i n a three-dimensional region, which lead to knotted and unknotted configurations. In Chapter 4 we return to random walks and we consider the following question which generalizes one i n [2] : what i s the expected number of crossings of an n-step continuous plane random walk by a f i x e d l i n e ? If the random walk takes place i n m-dimensions and the l i n e i s replaced by a hyperplane, then i t turns out that there are e s s e n t i a l l y two 5 cases of the general hyperplane crossing problem, depending on whether m i s even or odd. Due to te c h n i c a l d e t a i l s of the i n t e g r a t i o n process one obtains i n the f i r s t case multiple i n t e g r a l s , i n v o l v i n g powers of Bessel functions, whereas only elementary functions turn up i n the second case. Here we give a complete s o l u t i o n f o r m = 3, and discuss the asymptotics of the expected number of in t e r s e c t i o n s when n i s l a r g e . We also derive some plane- and l i n e - crossing r e s u l t s f o r lower-dimensional random walks by projecting the three-dimensional case onto a plane and onto a l i n e . In those lower-dimensional random walks the step-length i s no longer f i x e d but i s i t s e l f a random v a r i a b l e . Its d i s t r i b u t i o n depends, of course, on the dimension of the o r i g i n a l random walk which was projected. Thus, l e t us take unit steps i n the plane P, i n random d i r e c t i o n ; when these are projected onto any l i n e i n P we obtain steps f o r which the p r o b a b i l i t y -1 2 -1/2 density function i s IT (1 - x ) . However, when we take unit steps i n random d i r e c t i o n i n three dimensions, and project them on a l i n e , we ob t a i n , by an o l d r e s u l t of Archimedes, steps uniformly d i s t r i b u t e d on [-1,1] . Hence, by projecting uniform random walks of d i f f e r e n t dimensionality onto, say, a l i n e , we have cases of point-crossing problems for a one-dimensional walk but with d i f f e r e n t step-length d i s t r i b u t i o n s . In the concluding Chapter V we c o l l e c t various forms of discontinuous f a c t o r s , suggest further problems which might be amenable to treatment by the same method, and discuss connections with other problems i n c o n f i g u r a t i o n a l geometry. 6 CHAPTER II In t h i s chapter we demonstrate the use of the method i n the sol u t i o n of some problems i n random f l i g h t s . 1. Markov's Method Applied to the General Problem of Random F l i g h t s . Consider a p a r t i c l e whose p o s i t i o n i n En at time t Q i s R* . If i t then undergoes the displacements r ^ , r ^ , ... r ^ at the times n t l 5 t t then i t s p o s i t i o n at time t i s R = R + r, . I f the 1 2 n r n n , L. k k=l steps r ^ , k = l , . . . , n , are independent random va r i a b l e s then the equation n R = R + 2 rv defines a random f l i g h t . n k=l K The general problem of random f l i g h t s i s to f i n d the p r o b a b i l i t y that R^ i s i n [R, R + dR] . The general s o l u t i o n i s due to Markov, and i s an excellent example of the method employed i n t h i s t h e s i s . N Now R^ = . I r . , and r . i s an n- dimensional vector whose i = l components are each a function of s variables ; k k, 1 s N k,-> . r . = r.(q.,...,q.) = r.(q.) l i i l i i The d i s t r i b u t i o n of q_^ i s given by r^(q\)dq\ Let P^(R Q)dR 0 represent the p r o b a b i l i t y that ( 1 ) v l ^ o i U ^ o + id\ - Then 7 t t N (2) P N(R o)dR o = j ... j n "{ ir.Cq^dq. } where the i n t e g r a t i o n i s taken only over that subset of the configuration space i n which (1) i s s a t i s i f i e d . Let th i s subset be S. If l g i s the c h a r a c t e r i s t i c function of S, then •> f f N (3) P N(R 0)dR o = ... l s ( q ,...,q ) II { r.Oq^dq.. > J J i = l where the i n t e g r a t i o n i s taken over the enti r e configuration space, A. We now introduce an a n a l y t i c representation for l g . Let 1 ,Jc , s i n ( u v y dR ) N ( 4 ) 6k " 7 ^uf e xP<i uk I ( ri ~ V >d uk k=l,...,n "k Ki = l This i s the w e l l known discontinuous i n t e g r a l of D i r i c h l e t , which i s 1 N k l k r k k l k when R - -r- dR < ) r . < R + -r dR and i s 0 otherwise. Since only o 2 o I o 2 o J 1=1 sets of p o s i t i v e measure i n the configuration space may a f f e c t the outcome, we don't need to consider the cases of actual e q u a l i t y . Now (5) i s - TT \ b k=l k and s u b s t i t u t i n g (5) i n t o (3), we have 8 (6) P.T(R.')dR = N o o k=l ]=1 J J J The Interchange i n the order of i n t e g r a t i o n i s j u s t i f i e d as i n the introduction giving us N (7) F\T(R )dt = ~ v J N v o' o n 77 J - o o { TT ~ ^ ° \ e - c o 1 k=l k n f IN . 5-1^ * : - l 1 ».k> (8) 1_ ' n IT J ' N A • J i = l TT j •'?i(q 1)dq- i| du1...dur. r (-Tj s i n ( K d R o k ) , e x k=l k n N ', I I u.r;* k-1 i = l k 1 -i(u'R ) o N TT j rr(q 1)dq- ±|.du 1..-.du n (9) 1 dt< (2TTJ ' - o o 00 .00 - i u . J TT i = l l(UT .) r i ( q i ) d q i e du.. .. . du 1 n which i s Markov's s o l u t i o n of the general problem of random f l i g h t s . Solutions to Some Problems A r i s i n g from Random Walks i n the Plane The o r i g i n a l problem of random f l i g h t s as proposed by Pearson was as follows " A man s t a r t s from point 0 and walks a distance a i n a straight l i n e ; he then turns through any angle whatever and walks a distance a i n a 9 second s t r a i g h t l i n e . He repeats t h i s process n times. I require the p r o b a b i l i t y that a f t e r n stretches he i s at a distance between r and r + dr from h i s s t a r t i n g point 0. " Kluyver solved a ge n e r a l i s a t i o n of t h i s problem i n which the steps are of unequal length, say a^, a^, a^, by using the discontinuous fact oo j ^ r t ) j Q ( s t ) d t = 1 i f s < r 0 i f s > r Let S be the resultant of the steps a n , ..., a , and 0 the angle m v 1' m m b between S and a ,,. Then i n the two dimensional problem a l l values of m m+1 r 0 m between -TT and TT are equally probable. Let P n(r> a^> •••» a R) be the p r o b a b i l i t y that |Sn| < r . Then (1) ( r , a^, ..., (2TT) n-1 d0 .de o...d0, n-1 n-2 1 n-1 where the i n t e g r a t i o n i s taken over only those part of X [-7r> 7r].> 1=1 1 which |Sn| < r . Let these parts constitute the set S. Then xn 0 J ^ r t ) J o ( | S n | t ) d t i s the c h a r a c t e r i s t i c function of S, and s u b s t i t u t i n g t h i s discontinuous f a c t o r i n t o (1) we get P n ( r , a v a n) = (2Tr)n ^ 1 -TT (•TT |"TT r°° r J , ( r t ) J (Is It)dtd9 -de , _ 1 ' o 1 n1 n-1 n-^ —TT 3 -TT •'0 10 n-1 where the i n t e g r a t i o n i s now taken over the whole n - 1 cube X [-7T> 17] . i = l 3 We interchange the order of i n t e g r a t i o n and apply the law of cosines repeatedly to get r°° n 3 n ( r ' V ••••an> = r L J l ( r t ) TT J 0 ( a m t ) d t J 0 m=l which i s Kluyver's r e s u l t . 2 In [2] the discontinuous factor sgn(x) = — sin(ux) -du was 0 U used to solve problems a r i s i n g from Pearson's random walk i n the plane i n which the steps are each of length 1. The f i r s t problem we recount here i s "what i s the expected number of s e l f i n t e r s e c t i o n s of a random walk of length n ?" t i l The f i r s t step involves characterizing the crossing of the i and th j steps and then using t h i s c h a r a c t e r i z a t i o n to b u i l d a c h a r a c t e r i s t i c fucntion for the set of configurations which y i e l d crossings. th Let the 1 step be from (x^, y^) to (x-£+i » ^1+1^ a n <^ ai ^e th the angle the i step makes with the x-axis. The equation of the l i n e th L^(x,y) which c a r r i e s the i step i s (y - y.)cos(a.) - (x - x.)sin(a.) = 0. Let L ^ = L^(Xj,y^.). Then, neglecting events of p r o b a b i l i t y 0, the i ^ th i i+1 i i+1 step and j step cross i f and only i f L^ L^ < 0 and L^ L.. < 0 ; th that i s L_^ separates the endpoints of the j step and L^ separates the endpoints of the i * " *1 step . 11 Hence D - v [ l - sgn(L± J)sgn(L 3 - s g n ( L . X ) s g n ( L . ] i s 1 i f the i1" *1 and j*''1 steps cross, and 0 otherwise. Then the t o t a l number of crossings f or a given configuration i s n j-2 F (ex.. , . . . , a ) = T T D . . 3=3 i = l J and the expected number of crossings i s f(n) = (2rr) -n 2TT ,2TT ... F(a.. , a )da... .da o Jo 1 n 1 By using the given representation of sgn(x), we have 0 fOT sinfuL 3 ]du ^<V> - f f0 ^ - , and by s u b s t i t u t i n g t h i s into F(a^, a n), interchanging the order of i n t e g r a t i o n , then i n t e g r a t i n g over the configu-r a t i o n space, one obtains n—1 . f°° f«> f(n) = j I (1-p/n) l - \ ( u v ) _ 1 [ J P _ 1 ( u - v ) - J P _ 1(u+v)]dudv + p=2 i Jo J0 ° ° • y- *CO *00 .OO *0O -CO Q (uvwz)"1 I e. cos(c.sin6)J P _ 1 ( ( a . 2 + 2n.a.b.cos0 + b . 2 ) 2 ) J 0-* 0J 0J 0J 0 i = l 1 1 ° 1 i i i i dGdudvdwdz th where J Q ( x ) i s the 0 order Bessel f u n c t i o n , and the quantities indexed by i are 12 e . n . a. b. c. 1 x 1 1 1 1 1 -1 w-z u-v v-w 2 1 1 w-z u-v v+w 3 -1 -1 w-z u+v v+w 4 -1 1 w-z u+v v-w 5 -1 -1 w+z u-v v-w 6 -1 1 w+z u-v v+w 7 1 -1 w+z u+v v+w 8 1 1 w+z u+v v-w was shown that f(n) ~ — n log(n) .TT2 • Another r e s u l t i n [2] concerned the r e l a t i o n of a random walk to an external c o n f i g u r a t i o n , namely, "what i s the expected number of crossings of a f i x e d l i n e of distance b from the o r i g i n by a random walk of length n?". Although the methods are employed as i n the s e l f - i n t e r s e c t i o n problem, the in t e g r a t i o n and f i n a l r e s u l t appear more simply. This i s due to the fact that the c h a r a c t e r i z a t i o n of a crossing i s much simpler. By symmetry we can take the equation of the f i x e d l i n e to be y = b. th Then the i step crosses i f f sgn(y^ - b) s g n ( y i + ^ - b) < 0, and 1 th = - ^ ( l - sgn(y^ - b) sgn(y^ +^ - b)) = 1 i f the i step crosses, and i s 0 n otherwise. Then the t o t a l number of crossings i s J| D, and the expected i = l 1 number of crossings i s , _ n (2T\ f(n,b) =J-J (2TT) N I \ ... i = l J0 •> [ s g n ^ - b ) s g n ( y ± + 1 -b) ]do^. .. do^. 13 i-1 ._, . f s i n [ u ( £ sin(a t ) - b ] d u i J- 2 k—1' ' By using y. = £ s i n a, and sgn(y. - b) = — 1 k=i fc 1 17 Jo U i t was found that „ n-1 f°° f m f f(n,b) = % - TT y ( u v ) _ ± J (u) { cos[b(u-v)] J ^"(u-v) -2 i=0 io Jo ° 1 cos[b(u+v)] J o^(u+v) j- dudv. In considering the problem "what i s the expected number, f(n,m), of crossings of an !n- walk by an M- walk , each s t a r t i n g from the o r i g i n ? " i t was observed by the author, and v e r i f i e d by c a l c u l a t i o n that one need only f i n d the expected number of s e l f - i n t e r s e c t i o n s of an n + m walk, then subtract the number of self—crossings of the f i r s t n steps and of the l a s t m steps. Thus f(n,m) = f(n+m) - f(n) - f(m). 2 Using f(n) = — n log(n) i t was shown i n [2] that f or fi x e d t TT2 and large n f(n,tn) ~ — n[log(l+t) + t l o g ( l + l / t ) ] TT2 and i n p a r t i c u l a r f(n,n) - n ^ £ i 6 TT2 14 CHAPTER III In t h i s chapter we apply the method of the c h a r a c t e r i s t i c event to some problems i n geometrical p r o b a b i l i t y . We f i r s t consider the nature of qu a d r i a l t e r a l s whose v e r t i c e s are chosen at random. We then discuss the 3 p r o b a b i l i t y of knots being formed by 5 and 6 step random walks i n E . 1. Quadrilaterals Consider four points P^, T.^, P^» P^ chosen at random i n the unit square i n the plane. We ask three questions : 1) What i s the p r o b a b i l i t y that the q u a d r i l a t e r a l P-jF^P^P^ i s convex? 2) What i s the p r o b a b i l i t y that PjF^PgP^ i s s e l f - i n t e r s e c t i n g ? 3) What i s the p r o b a b i l i t y that P.,P„P.,P. i s concave? We now develop the configuration conditions which describe each arrangement, and use these conditions to get the c h a r a c t e r i s t i c function of each arrangement. The following table summarizes the separation by diagonals according to the type of arrangement which occurs. 15 P^, P^, and P^ are chosen a r b i t r a r i l y . Once these three points are chosen there are seven regions i n which P^ can be located; regions A, B, C, D, E, F, and G. We note that the p r o b a b i l i t y of landing on one of the three l i n e s determined by P^, Y^, and P^ i s zero. The following table records three conditions; whether P^ and P^ are separated by the l i n e P2P4 ' whether P2 a n c* P4 a r e s ePa r a t ed by the l i n e V^?^, and whether P-jF^P^P^ i s convex, concave, or s e l f i n t e r s e c t i n g . Region i n which P^ l i e s separation by P^P^ separation by P2^4 c o n^ i g u r a t i o n A yes no concave B no no s e l f i n t e r s e c t i n g C no yes concave D no no s e l f i n t e r s e c t i n g E yes no concave F yes yes convex G no yes concave 16 As can be seen from the t a b l e , ¥^P^P^P^ i s convex i f both diagonals separate, concave i f only one diagonal separates, and s e l f i n t e r s e c t i n g i f no diagonal separates. Thus the nature of the q u a d r i l a t e r a l i s completely determined by the separations by the diagonals. We now b u i l d c h a r a c t e r i s t i c functions f o r convexity, concavity, and s e l f i n t e r s e c t i n g . Let L = 0 be the equation of the l i n e carrying the points and P.. Then L.. separates P and P i f f J 13 m n sgn(L..(P ))sgn(L..(P )) = -1 . 13 n • 13 m So the c h a r a c t e r i s t i c function of the set of convex configuration i s (1) D 1 = - s g n ( L 1 3 ( P 2 ) ) s g n ( L 1 3 ( P 4 ) ) ) ( l - s g n a ^ P ^ s g n a ^ ^ ) ) ) that of the s e l f i n t e r s e c t i n g configurations i s : (2) D2 = i ( l + s g n ( L 1 3 ( P 2 ) ) s g n ( L 1 3 ( P 4 ) ) ) ( l + s g n C L ^ P . ^ ) sgn ( L 2 4 ( P 3 ) ) ) and that of the concave configuration i s (3) D3 = |(1 - s g n ( L 1 3 ( P 2 ) ) s g n ( L 1 3 ( P 4 ) ) s g n ( L 2 4 ( P 1 ) ) s g n ( L 2 4 ( P 3 ) ) ) If T^, T 2» and T 3 are the p r o b a b i l i t i e s of the above three cases, then Tl " 28 1 f1 ^ D 1(x 1,...,x 4,y 1,...,y 4)dx 1...dy 4 17 9***9 9 * * * 9 y 4)dx r ..dy4 9***9 ; 4 ' y l ' * •' >y 4)dx 1...dy 4 We can then replace sgn L..(P ) by the a n a l y t i c representation 2 r •» sin[uL. . (P ) ] sgn L..(P ) = -n m TT du u and perform the integrations. Rather than carry out the integ r a t i o n s , we w i l l employ Sylvester's theorem. This theorem gives the p r o b a b i l i t y T^ that four points chosen at random i n a convex region A w i l l form a convex q u a d r i l a t e r a l , for some ordering. The configurations which are s e l f - i n t e r s e c t i n g have an ordering i n which they would be convex, and no ordering of the concave configurations can y i e l d a convex fi g u r e . Hence the convex configurations plus the s e l f -i n t e r s e c t i n g configurations comprise a l l configurations which would be convex under some ordering. Thus T^ + = T^ and T^ = 1 - T^ . Since the four points have 4! = 24 equally possible orderings, and eight of these give r i s e to a convex configuration, we must have 2T.. = T„ . Thus A l t e r n a t i v e l y , combining the i n t e g r a l s f o r T^ and T^ and int e g r a t i n g would provide another proof of Sylvester's theorem for the square. 2 T = — T 2 3 A = 1 -18 25 By Sylvester's theorem T..= — . when A i s a parallelogram, A Jo hence T = ^ - T = ^ - T = — nence i± 1 Q g , i £ I o g , i 3 3 6 . We note that since Sylvester's theorem applies to any convex i 2 region A i n the plane, the r e s u l t = -j T^, T 2 = 3" T A> a n d T3 F 1 ~ T A holds for any convex region, not j u s t the square. We can generalize Sylvester's theorem by asking what i s the p r o b a b i l i t y that, given f i v e points chosen at random i n a convex region R 3 i n E , no point i s in s i d e the tetrahedron formed by the other four points. We can characterize a successful configuration i n terms of separation conditions, set up the c h a r a c t e r i s t i c function, and then integrate, using /• \ 2 /" sin(ux) , the discontinuous f a c t o r sgn(x) = — du . 17 J 0 u 3 There are 10 planes formed by 5 points i n E . (We neglect as being of p r o b a b i l i t y zero the case when four of the points l i e on a plane). If one point i s insi d e the tetrahedron formed by the other four, then 6 planes are separating. If the configuration i s convex then the plane of any face cannot be separating. We need only show that there are s i x faces to conclude that there are less than s i x separating planes. Now each face must be a t r i a n g l e , since no four points l i e i n a plane. By Euler's formula, where E i s the number of edges, V the v e r t i c e s , and F the faces. 3F we have 2 + E = V + F , so E = 3 + F . Now E = — , since each face has 3F 3 edges, and each edge i s shared by 2 faces, so = 3 + F or F = 6 . Thus there can be at most four separating planes i n the convex configuration. Then the c h a r a c t e r i s t i c function i s 19 D(P 1 JP 2,P 3,P 4,P 5) 1 2 6 - 2 i,j,k,m e [1, ,5] a l l unequal /-i T (M) T (N)\ (1 - sgnL. \ sgnL.... ) • l j k l j k fo r 1 i f the region determined by P^,P2,P3,P4,P,-B ( P r P 2 , P 3 , P 4 , P 5 ) = { xs convex 0 i f not Then the p r o b a b i l i t y that the region i s convex i s [Vol(R)] JR-'R f R RJ R D(P 1,P 2,P 3,P 4,P 5)dP 1...dP 5 2. Knots and Linking We consider here the p r o b a b i l i t y of some knotting configurations 3 a r i s i n g i n E . These w i l l include the l i n k i n g of a random t r i a n g l e with a fix e d s t r a i g h t l i n e , the knotting of a f i v e step r e c t i l i n e a r path, and the knotting of a closed s i x step r e c t i l i n e a r path. I. Linking of a Trian g l e and a Straight Line If H i s a f i x e d l i n e and P^, P 2 > P 3 are three randomly chosen 3 points i n E , what i s the p r o b a b i l i t y that I penetrates the t r i a n g u l a r 20 region ^^2^3 ' Such a configuration w i l l be c a l l e d a l i n k . We can characterize a l i n k by three separation conditions. Let P 1(x,y,z) = 0 be the plane containing I and the point P^. A l i n k occurs i f the plane P 1 separates the other two points, for i = 1, 2, and 3. One of these separations i s redundant, since i f any two of the planes are separating, then the t h i r d must also separate. Thus only two separation conditions must be s a t i s f i e d for a successful configuration. -|(1 - s g n ( P 1 ( P 2 ) ) s g n ( P 1 ( P 3 ) ) ) = 1 i f P 1 separates P £ and P 3 1 2 2 2 and - ^ ( l - sgn(P (P 1))sgn(P (P 3>)) = 1 i f P separates P 1 and P 3 > and both are 0 i f separation does not occur. Thus, the c h a r a c t e r i s t i c function of the set of successful configurations i s D (P 1 5P 2,P 3) = -| (1 - s g n ( P 1 ( P 2 ) ) s g n ( P 1 ( P 3 ) ) ) ( l - s g n ( P 2 ( P 1 ) ) s g n ( P 2 ( P 3 ) ) ) By symmetry considerations, we may take the f i x e d l i n e l to be the z-axis. Then .P 1(x,y,z) = x y ± - y x ± and 21 D(P 1,P 2,P 3) = | 1 - s g n ( x 2 y 1 - y ^ ) s g n C x ^ - y ^ ) 1 - s g n ( x 1 y 2 - y 1 x 2 ) s g n ( x 3 y 2 - y ^ ) L e t t i n g sgn(P 1(P.)) = — u 1 sin[uP 1(P.)]du we have 3 TT D ( P r P r P 3 ) = j 1 -T T 2 ' JQ (uv) 1 s i n [ u ( x 2 y 1 - y ^ ) ] s i n [v ( x ^ - y.jX^dudv (wz) 1 s i n [ w ( x 1 y 2 - y 1 x 2 ) ] s i n [ z ( x 3 y 2 - y 3x 2)]dwdz which i s an a n a l y t i c representation of the c h a r a c t e r i s t i c functions of the successful set. I I . Knotting of a f i v e step r e c t i l i n e a r path 3 Given s i x points chosen at random i n E , say P^, P 2, P 3 > P^, P^, P 6 > what i s the p r o b a b i l i t y that the path P^P^^^P P forms a knot ? The only possible knot for such a path i s the t r e f o i l . Def: The path P ^ P P^P P g w i l l be c a l l e d an open knot i f the path, together with the rays P-P. and P CP,, forms a knot i n the usual 2. 1 J O sense, provided that P^ and P 2 are separated by the plane of P 3 > P^, and P,., and P,. and P g are separated by the plane of P 0, P Q, and P7i. Such 2' 3: a knot i s pictured below. 22 Let be the smaller of the two angular regions formed by the steps P. nP. and P.P.,.,. Then a f i v e step r e c t i l i n e a r path s a t i s f i e s the d e f i n i -l - l 1 l l + l r r t i o n of a knot i f P n P 0 passes through A, and A r and P rP r passes 1 2 ° 4 5 5 6 through A 2 and A^ . The condition that P a s s e s through A^ i s redundant, f o r the other three conditions imply i t . We can characterize the passage of P-j^+i through A^ . by saying that the plane P.P.P.,. separates P. , and P.,,. Denote t h i s event by 1 3 l + l ^ j - l 3+I P. P. P.. ../P. J . . , . Then for a knot to be formed i t i s necessary and 1 3 l + l 3-I 3+I J s u f f i c i e n t that P ^ P ^ / P ^ , P^Pg/P.^ , and P ^ P g / P ^ . Let P-^jk^P) = 0 be the equation of the plane containing the points P., P., and P. , and P.., (£) the r e s u l t of s u b s t i t u t i n g P into P.., (P). X J j£ XJ K. X» X J iC Then a knot i s formed i f f s g n ( P 1 2 4 ( 3 ) ) s g n ( P 1 2 4 ( 5 ) ) = -1, s g n ( P 5 2 6 ( l ) ) s g n ( P 5 2 6 ( 3 ) ) = -1, and s g n ( P 5 3 6 ( 2 ) ) s g n ( P 5 3 6 ( 4 ) ) = -1. Hence »4 1 - s g n ( P 1 2 4 ( 3 ) s g n ( P 1 2 4 ( 5 ) ) 1 - s g n ( P 5 2 6 ( l ) ) s g n ( P 5 2 6 ( 3 ) ) 1 - s g n ( P 5 3 6 ( 2 ) ) s g n ( P 5 3 6 ( 4 ) ) 23 i s 1 i f the path forms a knot, and zero otherwise. Therefore D i s the c h a r a c t e r i s t i c function of the second successful set. Using the a n a l y t i c representation sgn(P ( 1 ) ) = | [ u 1 sinfuP... ( l ) ] d u i j k TT J Q l j k one can set up the i n t e g r a l P = —7 7 7 7 7 I D dw vol(W) j w to evaluate the p r o b a b i l i t y that a knot i s formed, where W i s the space of a l l configurations. I I I . Knotting of a Closed Six-Step R e c t i l i n e a r Path A closed s i x step path P^I^P^P^P^Pg w i l l be c a l l e d a knot i f there e x i s t s a plane which separates two of the points P^ and from the remaining four points and removal of the side P-j^+i r e s u l t s i n an open knot i n the sense of the previous example. We note that t h i s d e f i n i t i o n i s not equivalent to the d e f i n i t i o n i n the previous example since there e x i s t f i v e step open knots which cannot form closed s i x step knots. To see that t h i s d e f i n i t i o n i s reasonable, orient the closed s i x step knot so that one side i s nearest the observer. Take a plane which contains that side and i s p a r a l l e l to the next nearest side. Now translate 24 the plane away from the observer h a l f the distance between the two nearest sides. The plane w i l l separate the nearest side from the remainder of the knot. Removal of the nearest side must leave an open knot, for otherwise that could not have been a nearest side. Three of the steps pass through the angular regions formed by other pa i r s of sides, leaving three which don't. Those three which don't can each be separated from the rest of the points by a plane, and the removal of any one of them r e s u l t s i n a f i v e step open knot. Thus, i f there i s one separable edge whose removal leaves an open knot, then there must be three such edges. We now b u i l d a c h a r a c t e r i s t i c function which w i l l test for a knot by t e s t i n g the configuration r e s u l t i n g from the removal of each of the s i x sides. I f the o r i g i n a l configuration i s a knot, then the removal of three of the sides i n d i v i d u a l l y , must r e s u l t i n an open knot. With any le s s than t h i s there i s no knot. Let be the c h a r a c t e r i s t i c function of the previous example with respect to the path P. , - P . , „.. .P,P., . . .P. . Since the three removable c l + l i+2 6 1 I edges must be non adjacent, we need only consider D^D^Dj. and "D^D^^ . If the configuration i s a knot, then one of these products i s 1 and the other i s 0. I f i t i s not a knot, then both are zero. Thus the c h a r a c t e r i s t i c function we seek i s X = D l D 3 D 5 + D 2D 4D 6 . We can si m p l i f y the above expression for x by noting that there i s at most one side which can be removed and s t i l l leave an open knot, and therefore we!need only consider the ' Di. two at a time. Henc X = + D2D4 . 26 CHAPTER IV In t h i s chapter we generalize a problem i n [2] by asking "what i s 3 the expected number of crossings of a f i x e d plane i n E by an n-step 3 continuous random walk i n E ?" We use the method of the c h a r a c t e r i s t i c event to give the s o l u t i o n and then discuss the asymptotic behavior as n gets large. In the l a s t section of the chapter we introduce and discuss the notion of the weight of a problem. i n E of unit length, the f i r s t segment s t a r t i n g at the o r i g i n , and each successive step s t a r t s at the end of the previous one. The d i r e c t i o n of any step i s random, with i t s endpoint uniformly d i s t r i b u t e d on the unit sphere centered at the end point of the previous step. This i s j u s t a g e n e r a l i z a t i o n of the random walk considered i n [2]. We wish to f i n d the expected number of crossings of a f i x e d plane at distance d from the o r i g i n by an n step random walk. The formula we w i l l prove i s : 1. Crossing of a Fixed Plane by an n-Step Random Walk By an n step random walk we mean a sequence of s t r a i g h t segments 3 (1) f (n,d) = ^ f sin(u+v) u+v ^k-1 cos[(u+v)d] dudv. 27 Since the d i r e c t i o n of the f i r s t step i s e n t i r e l y at random, we may assume that the equation of the plane i s z = d. Let ^ and z^ be th th the i n i t i a l and terminal z coordinates of the k step. Then the k step crosses the plane i f f sgn(z^ - d)sgn(z^ - d) = -1. Let 1 th = - ^ ( l - sgn(z^_^ - d)sgn(z^ - d ) ) . Then = 1 i f the k step crosses the plane, and i s 0 otherwise. Hence the t o t a l number of crossings by a given random walk of n steps i s : n (2) F(z 1 }z 2,...',z ,d) = I Dfc . k=l By Archidmedes' proof of the surface area of. a sphere each z^ v a r i e s uniformly over the i n t e r v a l t2^ . ! ~ x> zk _ i + x3» hence the expected number of crossings i s r l r n-1 (3) f(n,d) = (2) n ... F(z ,z.,...,z ,d)dz ...dz . J - l Jz -1 1 2 n n 1 n-1 th Let <j>k be the colatitude of the k step. Then 0 <_ <j)^ <_ ir and Prob[(J) - •|d<J>_;_Sl"f)k £ <j> + "|d<j>] = sin<() d<j> . Hence (4) f(n,d) 2 J . . . j sin((},k) F l c o s d j ^ ) , cos ((j^) ,.. . , cos(<j>n) . d j d ^ . . . d ^ k I and since z^ = . £ cos(<^), we have 28 (5) f(n,d) = 2 TT n 0 k=l r n . 1 • /• r k-1 £ ••r 1 - sgn I cos(<j> ) - d k=l j = l 3 sgn J cos(<j>.).- d j = l d<j>.. . .. dd> 1 n = 2 -(n+1) n f i frr n I k=l J 0 0 p=l "ff sin((j> ) 1 - sgn £ cos(cj>.) - d k-1 j = l sgn 1 cos(cj>.) - d 3=1 2 d<b, ... dd> 1 Tn 2 f -1 We now introduce the discontinuous factor sgn(x) = — u sin(ux)du into (5) and get _/ n r r n r- . o o . o o k-1 (6) f(n,d) = 2 ^n + J J £ ... T Ts i n( * ) 1 - \ (uv) sin[u( £ cos(<|,.)-k=l JO JO p=l P L Tt^JoJo j = l 3 s i n [ v ( J cos(<j).)-d)dudv i = l J d <j)^ . . . d § 1 n rn I-TT n /" T00 1"°° -1 k-l ( 7 ) = | - n-T 7 I ••' TT s i n ( i ) (uv) 1s i n [ u ( £ cos(* )-d)] 2 TT k=l JO Jo p=l P Un JO j = l 3 s i n [v( £ cos((j)j)-d)]dudv|- d(j>^ . . .d<J)n <8> '-2-^-2.1 2 TT k=l J0 JO (uv) -1 0 JO TT n k-1 TT sin(cj) ) s i n [ u ( £ cos(<j>. )-d) ] P=l P j = l 3 s m [v( £ cos(<j>. )-d) ]dcf>.. . . .d<j> dudv . i = l 3 J - n The interchange i n the order of in t e g r a t i o n may be j u s t i f i e d as follows 29 F i r s t , fir fTT n r r00 r00 _ 1 k-1 (9) • ••• TT - s i n ( * ) i ( u v ) s in [ u ( £ cos(ct. )-d) ] J0 J0 p=l p J0 J0 j = l J V } s i n [ v ( 2, cos (<(>.. )-d] dudv | d<j>-^. ..dcji^ >0O . 0 0 rr n _ ^ k-1 JJ" sin(<j) )(uv) sin[u( £ cos (<j>. )-d) ] 0 <0 <0 ^0 p=l p j=»l J k s' i n [ v ( £ cos(cfi. )-d) ]dcf)1.. .dcj) dudv j = 1 J i n holds i f the i n f i n i t e l i m i t s of in t e g r a t i o n are replaced by any f i n i t e ones. The i n t e g r a l i n s i d e | • | i s boundedly convergent as a function of <f>^ , ^ 2 since i t i s for a l l tt> ,^ <|> . The boundary of the successful set i s t exactly the set of those ((j>. , <j> ) for which £ cos(<J>.) = d for j = l 3 t = k-1, k. If we remove these sets from the hyper cube H = [0, T r ] n , then the i n t e g r a l i s uniformly convergent on any compact subset of the remainder. Since the removed set i s of n-dimensional content zero, the interchange i s j u s t i f i e d . n j-oo ,oo (10) Now f (n,d) = ^ f-r- I (uv) G dudv, where Z 2n~V k=l ' 0 J 0 k IT fTT n k-1 Gk = k '0 fTT II K - 1 TT sin((j) ) s i n [ u ( £ cos (cf> )-d) ] J0 p=l p j = l 2 k s i n [ v ( J cos(ci).)-d) ]dcb1 .. .dcf) j = l 3 i n 30 Integrating w. r . t . '*"' ^n' a n d u s i nS the trigonometric i d e n t i t y sin(A)sin(B) = -|<cos(A - B) - cos(A + B)) we have Gk = 2 n-k-1 (•TT /-Tf k k-1 ... J]" sin( (J) ) [cos (u-v) ( £ cos(cj).)-d) - vcos ( 4 ) ] Jo Jo p=l p j = l 2 k k-1 - cos[( u+v) ( 1 c o s ( ^ ) - d ) + v c o s C c f ^ J d ^ . . . d ^ . Integrating w. r. t. <j>^ and using t = cos(<j>^), we have G, = 2 n-k-i r r i r r l k k-1 0 "[J sin(<j> )[cos[(u-v)t + (u-v)( Y cos(<J))-d) JoJ-1 p=2 P j=2 J - VCOS(((^.)] k-1 cos[(u+v)t + (u+v) ( £ cos(<j)j)-d) + vcosdj^)]] dtd<f)2.. . d ^ J ~2 k-1 = 2 n-k-1 f T T k JY s i n ( f ) " 0 p=2 sin[(u-v) + (u-v) ( Y cos (tj>. )-d)- vcos(<j>,)] .1=2 3 u + v sin[-(u-v) + (u-v) ( J cos(tj).)-d) - vcos(cf>,)] i=2 J k u - v k-1 sin [ (u+v)+(u+v) ( I cos((j).)-d) + vcos(<j)k) .1=2 U "+ V = 2 n-k-1 k-1 + sin[-(u+v)+(u+v) ( £ cos((j).)-d) + vcos ( & ) ] .1=2 3 u + v , d ^ . . -dcf^ TT k • ( • _ - » k-1 J7 sin(t}> ) 2 cos[(u-v)( Y cos (ct. )-d)-vcos (tt,) ] 0 p=2 P U V j=2 2 k - 2S 1^ "+ V ) cos[(u+v)( I cos((j> )-d)+vcos(<f» k)]} d*2...d<()k j=2 2 J 31 Continuing i n t h i s fashion, we get Gk = 2 n-2 sin(<j)k) sin(u-^v) u-v k-1 cos I-(u-v) d - vcos(<j>k)] sin(u+v) u+v k-1 cos[-(u+v)d + vcos(^ k)V d(j>k n-2 /fsin(u-v) u-v k-1 sin[-(u-v)d-v] - sin[-(u-v)d+v] -v sin(u+v) u+v k-1 sin[-(u+v)d+v] - sin[-(u+v)d-v] v = 2 n-2 sin(u-v) u-v k-1 2n -2 s i n v /[sin(u-v) sxn v v k-1 u-v ( . cos[(u-v)d] -cos[(u-v)d] -sin(u+v) u+v sin(u+v) k-1 . sxn v v cos[(u+v)d] u+v k-1 cos[(u+v)d] Substituting G, into (10), we get f ( n , d ) = Tr - — — y n-1 2 L , , 2 TT k=l •'0J0 , x - l „n-2 s i n v (uv) 2 — - — sin(u-v) u-v k-1 cos[(u-v)d] -sin(u+v) u+v k-1 cos [ (u+v) d] j-dudv n 1 Xl fco -co 2TT k=l J0J0 I (uv) 1 sin v /fsin(u-v) u-v k-1 cos[(u-v)d] sin(u+v) u+v k-1 cos[(u+v)d]\ dudv which proves (1). 32 By pr o j e c t i n g the walk i n E onto a l i n e and onto a plane, we can obtain the expected number of crossings of a hyperplane at distance d from the o r i g i n by a random walk of variable step length. The d i s t r i b u t i o n of the step length w i l l depend upon the image space of the pr o j e c t i o n . If one cuts the unit sphere by two p a r a l l e l planes of distance s apart, then the surface area of the sphere between the two planes i s the same no matter where the two planes are. Thus i f a point i s chosen at random on the unit sphere with uniform d i s t r i b u t i o n then the z coordinate of the point w i l l be uniformly d i s t r i b u t e d on [-1,1]. Hence by pr o j e c t i n g our walk onto the z axis, we see that f(n,d) i s the expected number of crossings of the coordinate d by a random walk on the l i n e with v a r i a b l e steps uniformly d i s t r i b u t e d i n [-1,1]. 3 If we proj ect the walk i n E onto the zy plane we get a random / 2 walk of v a r i a b l e step length with d i s t r i b u t i o n function (1 - / l - I ) on the i n t e r v a l [0,1]. The angle between steps i s random with uniform d i s t r i b u t i o n on [0,2TT]. Thus f(n,d) i s the expected number of crossings of a l i n e at distance d from the o r i g i n by such a random walk. 2. Behavior of f(n,d) as n Gets Large To determine the behavior of f(n,d) as n gets large, i t w i l l s u f f i c e to determine i t s behavior f or d = 0, since as n gets large the th p r o b a b i l i t y that some step, say the k , gets close to the plane approaches 1, 33 and from that step on i t may be expected to behave the same as an n-k walk with d = 0. For d = 0 we have where f(n,0) =J-~12 I I k 1 2TT k=l k I, = .CO f00 s i n v T sin(u-v) 0 • 2 0 uv [ u-v k-1 sin(u+v) u+v k-1 dudv th The p r o b a b i l i t y that the k step crosses i s 2 0 2 ^k 2ir Work i s i n progress tojletermine the asymptotic behavior of f ( n , 0 ) . F e l l e r [5] proves that the number of returns to zero of a random walk on the l i n e of unit step length tends to c^n . Since f(n,0) can be considered to be the expected number of crossings of zero by a random walk on the l i n e of v a r i a b l e step length with uniform d i s t r i b u t i o n , i t appears p l a u s i b l e that f(n,0) tends to c'Vii for some constant c' . To show t h i s i t w i l l be s u f f i c i e n t -to^sRow^tinat _ 1 2 2 I k — > rr - bk - ek where e, i s an error term such that k e. /k —> 0 k as 34 3. Weight of a Problem Here we w i l l t r y to d i s t i n g u i s h between types of problems according to t h e i r separation conditions. A successful configuration i s one of the type sought i n the problem, and the successful set i s the set of a l l such configurations. We w i l l c a l l a problem one of weight k i f i t i s necessary that k separations occur simultaneously f o r a successful configuration to occur, or that j separations and k-j non separation must occur simultaneously. In a problem of weight k i t appears that the c h a r a c t e r i s t i c function of the successful set w i l l involve products of sgn(A^)sgn(B^) of length k. Usually, the less the weight of a problem, the simpler the i n t e g r a t i o n w i l l be. In the examples discussed so f a r which use separation conditions, problems of weight 1,2,3, and 10 have occurred. The problem of the crossing of a f i x e d l i n e by a random walk i n the plane was a problem of weight 1. th Here a crossing occurred at the i step i f one separation occurred. The problem of the s e l f i n t e r s e c t i o n s of a random walk i n the plane was a problem of weight 2. Here the i * " *1 and steps crossed i f two separations occurred. The nature of the q u a d r i l a t e r a l formed by four ordered points i n the plane was also of weight 2 since the nature of two separations had to be known simultaneously. The knot problem was of weight three since three separation conditions had to be met. The ge n e r a l i z a t i o n of Sylvester's 3 theorem to f i v e points i n E was of weight ten since the separation or 35 non-separation by ten planes was required simultaneously. Problems of weight 1 and 2 can be distinguished by whether the problem i s concerned with the r e l a t i o n s h i p between a random configuration and a f i x e d , or external s t r u c t u r e , or between two random configurations. The crossing of a f i x e d hyperplane by a random walk i s of weight 1 while s e l f i n t e r s e c t i o n s and convexity are of weight 2. 36 CHAPTER V SOME USEFUL DISCONTINUOUS FACTORS AND FURTHER SUGGESTIONS Since the nature of a problem determines which discontinuous factor i s best used, we l i s t here some a n a l y t i c representations of discontinuous f a c t o r s according to the condition on the va r i a b l e s which i s sought. 1. For separation of points by hyperplanes, sgn(x) i s u s e f u l , where sgn(x) =7- u ^ sin(ux)du ( 1 i f x > 0 -1 i f x < 0 Other i n t e g r a l s which may be useful i n separation problems are (J i s a Bessel function) J Q ( a t ) s i n ( b t ) d t = • i f b > a 0 i f b < a i f b > a J Q ( a t ) cos(bt)dt = • i f b < a 37 r , y-1 , y . r , b /a i f b < a 0 i f b > a where R(y) > 0 . within some bound one can use i f s < r i f s > r 3. To determine when y i s i n some i n t e r v a l we use 1 i f - a < y < a 0 otherwise In suggesting further problems whose s o l u t i o n may be amenable to the method of the c h a r a c t e r i s t i c event we must remain aware of the fac t that although the method may allow the s e t t i n g up of the s o l u t i o n i n terms of i n t e g r a l s , any s i g n i f i c a n t evaluation may be hopeless. Thus while problems which appear to be of weight one, two, or three are possibly amenable to so l u t i o n by t h i s method, problems of higher weight are probably not. An obvious problem of weight one would be to determine the expected number of crossings of a hyperplane i n E n by a continuous random walk of length k. This would also provide the expected number of crossings of hyperplanes by continuous random walks of v a r i a b l e step length by J ^ ( a t ) J ^ _ 1 ( b t ) d t = • 2. To determine when s i s J 1 ( r t ) J Q ( s t ) d t = -1 l s i n (cm) i(uy) , — e du TT U 38 pro j e c t i n g walks i n E onto spaces of lower dimension. The d i s t r i b u t i o n of the step length would be determined by the dimensions of the domain and range of the p r o j e c t i o n . 2 Another problem i s the extension of Sylvester's theorem, i n E 3 and E , to determine the p r o b a b i l i t y that n points taken at random i n a convex region themselves form a convex region. Since both Crofton's theorem and the method of the c h a r a c t e r i s t i c event lead to Sylvester's theorem, a study of the r e l a t i o n between the two may be of i n t e r e s t . Crofton's theorem and the method both apply to properties of configurations which are in v a r i a n t under tr a n s l a t i o n s and r o t a t i o n s , hence Crofton's theorem may be us e f u l i n the reduction of the weight of a problem, thereby making the problem more amenable to s o l u t i o n by the method. 3 The analysis of the l i n k i n g of a s t r a i g h t l i n e i n E by the path P j ^ P g * • •^ k» K > 3, may be expressable by the method, as might the 3 p r o b a b i l i t y of knotting by an n step path i n E , n >_ 6. 39 BIBLIOGRAPHY [1] A. A. Markov, Warscheinlichkeitsrechnung, L e i p z i g , 1912. [2] Z. A. Melzak, On Some P r o b a b i l i t i e s i n Continuous Random Walks, Quarterly of Applied Mathematics, to appear. [3] S. Chandrasekhar, Noise and Stochastic Processes, e d i t o r Nelson Wax, New York : Dover 1954, Chapter 1, pp. 4-18. [4] G. N. Watson, Theory of Bessel Functions, 2nd edn. Cambridge, 1958. [5] W. F e l l e r , An Introduction to P r o b a b i l i t y Theory and i t s Applications, Vol. 1, 3rd edn., John Wiley and Sons, 1968, pp. 84-86. [6] M. G. Kendall and P. A. P. Moran, Geometrical P r o b a b i l i t y , Charles G r i f f i n and Co., London, 1963. [7] M. N. Barber and B. W. Ninham, Random and Res t r i c t e d Walks, Gordon & Breach, Science Publishers, Inc. New York, 1970. [8] E. C. Titchmarsh, The Theory of Functions, 2nd edn., Oxford, 1939.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Some applications of the method of the characteristic...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Some applications of the method of the characteristic event Main, Robert Frazee 1973
pdf
Page Metadata
Item Metadata
Title | Some applications of the method of the characteristic event |
Creator |
Main, Robert Frazee |
Publisher | University of British Columbia |
Date Issued | 1973 |
Description | A method of integrating over difficult sets in Eⁿ by replacing the characteristic function of the set with a discontinuous integral has been used by Markov, Chandrasekhar, Melzak, and others. This thesis employs this method in some problems arising from random walks. A discussion of the difficulties encountered and suggestions for further study are included. |
Subject |
Random walks (Mathematics) Functions, Characterstic |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-03-23 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
IsShownAt | 10.14288/1.0080449 |
URI | http://hdl.handle.net/2429/32772 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
AggregatedSourceRepository | DSpace |
Download
- Media
- 831-UBC_1973_A6_7 M33_5.pdf [ 2.03MB ]
- Metadata
- JSON: 831-1.0080449.json
- JSON-LD: 831-1.0080449-ld.json
- RDF/XML (Pretty): 831-1.0080449-rdf.xml
- RDF/JSON: 831-1.0080449-rdf.json
- Turtle: 831-1.0080449-turtle.txt
- N-Triples: 831-1.0080449-rdf-ntriples.txt
- Original Record: 831-1.0080449-source.json
- Full Text
- 831-1.0080449-fulltext.txt
- Citation
- 831-1.0080449.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0080449/manifest