"Science, Faculty of"@en .
"Mathematics, Department of"@en .
"DSpace"@en .
"UBCV"@en .
"Main, Robert Frazee"@en .
"2011-03-23T18:06:54Z"@en .
"1973"@en .
"Master of Science - MSc"@en .
"University of British Columbia"@en .
"A method of integrating over difficult sets in E\u00E2\u0081\u00BF 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."@en .
"https://circle.library.ubc.ca/rest/handle/2429/32772?expand=metadata"@en .
"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\u00E2\u0080\u009E 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 \u00E2\u0080\u00A2-\u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2> 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*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 ~ ^ \u00C2\u00B0 \ e - c o 1 k=l k n f IN . 5-1^ * : - l 1 \u00C2\u00BB.k> (8) 1_ ' n IT J ' N A \u00E2\u0080\u00A2 J i = l TT j \u00E2\u0080\u00A2'?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- \u00C2\u00B1|.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^> \u00E2\u0080\u00A2\u00E2\u0080\u00A2\u00E2\u0080\u00A2\u00C2\u00BB 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 (\u00E2\u0080\u00A2TT |\"TT r\u00C2\u00B0\u00C2\u00B0 r J , ( r t ) J (Is It)dtd9 -de , _ 1 ' o 1 n1 n-1 n-^ \u00E2\u0080\u0094TT 3 -TT \u00E2\u0080\u00A2'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\u00C2\u00B0\u00C2\u00B0 n 3 n ( r ' V \u00E2\u0080\u00A2\u00E2\u0080\u00A2\u00E2\u0080\u00A2\u00E2\u0080\u00A2an> = 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) = \u00E2\u0080\u0094 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-\u00C2\u00A3+i \u00C2\u00BB ^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\u00C2\u00B1 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 ^ - 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\u00E2\u0080\u00941 . f\u00C2\u00B0\u00C2\u00B0 f\u00C2\u00AB> 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 \u00C2\u00B0 \u00C2\u00B0 \u00E2\u0080\u00A2 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 \u00C2\u00B0 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) ~ \u00E2\u0080\u0094 n log(n) .TT2 \u00E2\u0080\u00A2 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 \u00E2\u0080\u00A2> [ s g n ^ - b ) s g n ( y \u00C2\u00B1 + 1 -b) ]do^. .. do^. 13 i-1 ._, . f s i n [ u ( \u00C2\u00A3 sin(a t ) - b ] d u i J- 2 k\u00E2\u0080\u00941' ' By using y. = \u00C2\u00A3 s i n a, and sgn(y. - b) = \u00E2\u0080\u0094 1 k=i fc 1 17 Jo U i t was found that \u00E2\u0080\u009E n-1 f\u00C2\u00B0\u00C2\u00B0 f m f f(n,b) = % - TT y ( u v ) _ \u00C2\u00B1 J (u) { cos[b(u-v)] J ^\"(u-v) -2 i=0 io Jo \u00C2\u00B0 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\u00E2\u0080\u0094crossings 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) = \u00E2\u0080\u0094 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) ~ \u00E2\u0080\u0094 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 ^ \u00C2\u00A3 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^\u00C2\u00BB 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\u00E2\u0080\u009EP.,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 , \u00C2\u00A5^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 \u00E2\u0080\u00A2 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\u00C2\u00BB 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 ' * \u00E2\u0080\u00A2' >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 \u00E2\u0080\u00A2\u00C2\u00BB 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\u00E2\u0080\u009E . 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 = \u00E2\u0080\u0094 T 2 3 A = 1 -18 25 By Sylvester's theorem T..= \u00E2\u0080\u0094 . when A i s a parallelogram, A Jo hence T = ^ - T = ^ - T = \u00E2\u0080\u0094 nence i\u00C2\u00B1 1 Q g , i \u00C2\u00A3 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 /\u00E2\u0080\u00A2 \ 2 /\" sin(ux) , the discontinuous f a c t o r sgn(x) = \u00E2\u0080\u0094 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 = \u00E2\u0080\u0094 , 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.... ) \u00E2\u0080\u00A2 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 \u00C2\u00A3 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 \u00C2\u00B1 - y x \u00C2\u00B1 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.)) = \u00E2\u0080\u0094 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 \u00C2\u00B0 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.., (\u00C2\u00A3) 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\u00C2\u00A3 XJ K. X\u00C2\u00BB 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 \u00C2\u00BB4 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 = \u00E2\u0080\u00947 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 . , \u00E2\u0080\u009E.. .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\u00C2\u00BB 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 k be the colatitude of the k step. Then 0 <_ _;_Sl\"f)k \u00C2\u00A3 + \"|d] = sin<() d . Hence (4) f(n,d) 2 J . . . j sin((},k) F l c o s d j ^ ) , cos ((j^) ,.. . , cos(n) . d j d ^ . . . d ^ k I and since z^ = . \u00C2\u00A3 cos(<^), we have 28 (5) f(n,d) = 2 TT n 0 k=l r n . 1 \u00E2\u0080\u00A2 /\u00E2\u0080\u00A2 r k-1 \u00C2\u00A3 \u00E2\u0080\u00A2\u00E2\u0080\u00A2r 1 - sgn I cos( ) - d k=l j = l 3 sgn J cos(.).- d j = l d.. . .. dd> 1 n = 2 -(n+1) n f i frr n I k=l J 0 0 p=l \"ff sin((j> ) 1 - sgn \u00C2\u00A3 cos(cj>.) - d k-1 j = l sgn 1 cos(cj>.) - d 3=1 2 d*** 1 Tn 2 f -1 We now introduce the discontinuous factor sgn(x) = \u00E2\u0080\u0094 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 \u00C2\u00A3 ... T Ts i n( * ) 1 - \ (uv) sin[u( \u00C2\u00A3 cos(<|,.)-k=l JO JO p=l P L Tt^JoJo j = l 3 s i n [ v ( J cos(^ . . .d '-2-^-2.1 2 TT k=l J0 JO (uv) -1 0 JO TT n k-1 TT sin(cj) ) s i n [ u ( \u00C2\u00A3 cos(. )-d) ] P=l P j = l 3 s m [v( \u00C2\u00A3 cos(. )-d) ]dcf>.. . . .d 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) \u00E2\u0080\u00A2 \u00E2\u0080\u00A2\u00E2\u0080\u00A2\u00E2\u0080\u00A2 TT - s i n ( * ) i ( u v ) s in [ u ( \u00C2\u00A3 cos(ct. )-d) ] J0 J0 p=l p J0 J0 j = l J V } s i n [ v ( 2, cos (<(>.. )-d] dudv | d-^. ..dcji^ >0O . 0 0 rr n _ ^ k-1 JJ\" sin(. )-d) ] 0 <0 <0 ^0 p=l p j=\u00C2\u00BBl J k s' i n [ v ( \u00C2\u00A3 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 | \u00E2\u0080\u00A2 | i s boundedly convergent as a function of ^ , ^ 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>. , ) for which \u00C2\u00A3 cos(.) = 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 ( \u00C2\u00A3 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) = -|^ and using t = cos(^), we have G, = 2 n-k-i r r i r r l k k-1 0 \"[J sin( )[cos[(u-v)t + (u-v)( Y cos(. )-d)- vcos(,)] .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( ) 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(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 - \u00E2\u0080\u0094 \u00E2\u0080\u0094 y n-1 2 L , , 2 TT k=l \u00E2\u0080\u00A2'0J0 , x - l \u00E2\u0080\u009En-2 s i n v (uv) 2 \u00E2\u0080\u0094 - \u00E2\u0080\u0094 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 \u00E2\u0080\u00A2 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 \u00E2\u0080\u0094 > rr - bk - ek where e, i s an error term such that k e. /k \u00E2\u0080\u0094> 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 = \u00E2\u0080\u00A2 i f b > a 0 i f b < a i f b > a J Q ( a t ) cos(bt)dt = \u00E2\u0080\u00A2 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 = \u00E2\u0080\u00A2 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) , \u00E2\u0080\u0094 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 * \u00E2\u0080\u00A2 \u00E2\u0080\u00A2^ k\u00C2\u00BB 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. "@en .
"Thesis/Dissertation"@en .
"10.14288/1.0080449"@en .
"eng"@en .
"Mathematics"@en .
"Vancouver : University of British Columbia Library"@en .
"University of British Columbia"@en .
"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."@en .
"Graduate"@en .
"Random walks (Mathematics)"@en .
"Functions, Characterstic"@en .
"Some applications of the method of the characteristic event"@en .
"Text"@en .
"http://hdl.handle.net/2429/32772"@en .
**