The U n i v e r s i t y of B r i t i s h Columbia FACULTY OF GRADUATE STUDIES PROGRAMME OF THE FINAL ORAL EXAMINATION FOR THE DEGREE OF DOCTOR OF PHILOSOPHY of WARREN DAVID LITTLE B . A . S c , The U n i v e r s i t y of B r i t i s h Columbia, 1961 M.A.Sc, The U n i v e r s i t y of B r i t i s h Columbia, 196 3 FRIDAY, OCTOBER 22, 1965, a t 4:00 P„M, IN ROOM 402, MacLEOD BUILDING COMMITTEE IN CHARGE Chairman: L McT, Cowan E„ V. Bohn A, D„ Moore R. W. Donaldson C/A,~Swanson H. P. Z e i g e r Research S u p e r v i s o r : A. D. Soudack E x t e r n a l Examiner: L. D. Kovach Pepperdine C o l l e g e Los A n g e l e s , California HYBRID COMPUTER SOLUTIONS OF PARTIAL DIFFERENTIAL EQUATIONS BY MONTE CARLO METHODS ABSTRACT A continuous Markov process i s examined f o r t h e purpose of d e v e l o p i n g Monte C a r l o methods f o r s o l v i n g differential for equations. Backward Kolmogorov partial equations c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n s and more g e n e r a l equations s a t i s f i e d by a u x i l i a r y p r o b a b i l i t y dens i t y functions are derived. the i n i t i a l From these equations and and boundary c o n d i t i o n s t h a t t h e d e n s i t y functions s a t i s f y , differential i t i s shown t h a t s o l u t i o n s of p a r t i a l equations a t an i n t e r i o r p o i n t of- a r e g i o n can be w r i t t e n as t h e expected v a l u e of r a n d o m l y - s e l e c t e d initial and boundary v a l u e s . From these r e s u l t s , Monte C a r l o methods f o r s o l v i n g homogeneous and nonhomogeneous elliptic, and homogeneous p a r a b o l i c p a r t i a l differential equations a r e proposed. H y b r i d computer techniques f o r mechanizing C a r l o methods a r e g i v e n . ted computer i s t o c o n t r o l t h e analog computer and t o form t h e r e - q u i r e d averages. of The Markov process i s simula- on the analog computer and t h e d i g i t a l used the Monte Methods f o r d e t e c t i n g the boundaries r e g i o n s u s i n g analog f u n c t i o n g e n e r a t o r s and e l e c t r o n i c comparators a r e proposed. Monte C a r l o s o l u t i o n s a r e obtained on a h y b r i d system c o n s i s t i n g of a PACE 231 R-V analog computer and an ALWAC I I I - E d i g i t a l two computer. The i n t e r f a c e f o r t h e computers and a multichannel, d i s c r e t e - i n t e r v a l b i n a r y - n o i s e source a r e d e s c r i b e d . With t h i s equipment, solu- t i o n s having a s m a l l v a r i a n c e a r e obtained a t a r a t e of approximately f i v e minutes p e r s o l u t i o n , Example s o l u t i o n s a r e g i v e n f o r L a p l a c e ' s e q u a t i o n i n two and three dimensionsPoisson'.s and the heat e q u a t i o n in'two dimensions e q u a t i o n i n ' one, two and t h r e e dimensions. GRADUATE STUDIES Field of Study: Electrical Engineering A p p l i e d E l e c t r o m a g n e t i c Theory G. B. Walker Electronic F. K. Instrumentation Network. Theory A Servomechanisms Solid-State Electronic N o n l i n e a r Systems Electron Digital 0 Bowers D. Moore E. V. Bohn Devices Mo P. Beddoes A. C. Soudack Dynamics G. B. Walker Computers E. V. Bohn Related Studies: Numerical A n a l y s i s I Computer Programming Integral Equations T. H u l l C. Froese E. Macskasy PUBLICATIONS Beddoes, M.P. and L i t t l e . W.D., " U n i l a t e r a l Param e t r i c Frequency Converters w i t h N o n l i n e a r Conduct ance and C a p a c i t a n c e " , Proc, IEEE, V o l . 52, No. 3, p. 333, March, 1954. Soudack, A.C. and L i t t l e , W.D., "An Economical H y b r i d i z i n g Scheme f o r A p p l y i n g Monte C a r l o Methods to the S o l u t i o n of P a r t i a l D i f f e r e n t i a l E q u a t i o n s " , S i m u l a t i o n , V o l 5, No. 1, pp. 9-11, J u l y , 1965. L i t t l e , W.D., "An E l e c t r o n i c SPDT Switch", t i o n , Vol.- 5, No. 1, P. 12, July, 1965 Simula- L i t t l e , W.D., and Soudack, A . C , "On the Analog Computer S o l u t i o n of F i r s t - O r d e r P a r t i a l D i f f e r e n t i a l Equations", Annales AsICA, October, 1965. Kohne, H., L i t t l e , W.D., and Soudack, A . C , "An Economical M u l t i c h a n n e l Noise Source", S i m u l a t i o n , to be p u b l i s h e d , November, 1965. HYBRID COMPUTER DIFFERENTIAL SOLUTIONS EQUATIONS OP B Y MONTE WARREN D A V I D PARTIAL CARLO METHODS LITTLE B.A.Sc, University of B r i t i s h Columbia, 1961 M.A.Sc., University of B r i t i s h Columbia,, 1963 SUBMITTED IN PARTIAL FULFILMENT OF A THESIS THE We accept REQUIREMENTS THE DOCTOR OF in Department the DEGREE of Engineering this as thesis Members of of conforming to the standard the Electrical UNIVERSITY OF PHILOSOPHY Electrical required THE FOR Department Engineering OF B R I T I S H October, 1965 COLUMBIA In p r e s e n t i n g the r e q u i r e m e n t s f o r an British Columbia, available for mission representatives,, cation of w i t h o u t my Department this by the of Columbia of University of s h a l l make i t thesis Head o f my permission. fulfilment I f u r t h e r agree that this for financial The U n i v e r s i t y o f B r i t i s h V a n c o u v e r 8, C a n a d a Date study. the Library It i s understood thesis written the copying of granted in p a r t i a l advanced degree at r e f e r e n c e and be thesis I agree that for extensive p u r p o s e s may his this copying or shall not per- scholarly Department or that gain for freely be by publi- allowed ABSTRACT A of continuous developing ential equations. probability fied by From these that the of Monte differential be and boundary methods for solving Carlo methods the partial computer are analog computer and the the analog computer and to for detecting generators and Monte consisting d i g i t a l of this obtained Example three heat a PACE computer. multichannel With Carlo a rate solutions dimensions, equation 231 for the of of interface in of are solutions Poisson's one, two three ii of Monte Carlo e l l i p t i c a n d f equations are the proposed. Monte is used required averages. using are a in analog on a and two control Methods function hybrid an source per equation two in dimensions dimensions. and are variance minutes system ALWAC computers small five to on proposed. computer the a randomly-selected mechanizing Laplace's equation and point computer having for solutions simulated for approximately given derived. conditions results, obtained analog satis- is regions are conditional process comparators R-V value differ- that interior discrete-interval binary-noise equipment, at form are nonhomogeneous Markov solutions The and d i g i t a l boundaries electronic an purpose equations shown differential The the is the for boundary these techniques given.' the From general i t expected homogeneous equations and at for partial functions i n i t i a l values. parabolic Hybrid density satisfy, examined solving more equations w r i t t e n as i n i t i a l homogeneous the functions for and probability and is Kolmogorov functions equations can process methods Backward auxiliary partial region Carlo density density Markov III-E a described. are solution. two and and the TABLE OF CONTENTS Page List of Illustrations Acknowledgements 1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . o . . . . . . . . . . Thesis '.. Outline . . , . . . . * . . . « . . . . . . . « . FUNDAMENTAL RELATIONS FOR MARKOV P R O C E S S E S 2.2 Chapman-Kolmogorov Equations f o r Continuous Markov Processes w i t h i n Bounded Regions . . . . . . . 2.5 « 10 A Continuous Markov Process f o r which Backward Kolmogorov Equations are V a l i d . . . . . . . . . . . . . . . . 17 P a r t i a l Differential Equations Satisfied by Auxiliary Probability Density Functions ....... 23 In *t 1*0(3. H C " t 3.2 Solutions P a r t i a l 1011 of Boundary-Value Solutions Estimates Equations f o r . . . . . . . . . . . . . . . . Problems f o r o f t h e Number Carlo Solutions 3.5A Convergence 3»5B Number P a r t i a l Number P a r t i a l o f Random 39 o f Random Walks Carlo Walks Solutions f o r . . . . 45 45 Homogeneous Equations Walks Differential i i i f o r 42 f o r . . . . . . . . . . . . . . . . . . . . . . . . . Differential 31 Boundary-Value o f Random o f Monte 30 E l l i p t i c Equations o f Nonhomogeneous 30 Parabolic «»»»».»..<>..*..«e»o»»«.».o«.»«.««»«o»» Monte 3.5C Problems of Boundary-Value Differential Problems BOUNDARY- « 9 < * * « e » e a a * « » * » * « * * 9 * 9 « « * « « * e * » * « * Differential Solutions P a r t i a l 3.5 5 Backward Kolmogorov P a r t i a l Differential Equations . . . . . . . . . . . * . . . . . . . * . . . . . . « . . . . . . . * * . 3*1 3.4 1 5 MONTE CARLO METHODS F O R T H E S O L U T I O N S D F V A L U E P R O B L E M S ««o*#**e*«o-«« « • • •••••• 3o3 v i i i 5 Introduction 2.4 1 4 2.1 2.3 3. V INTRODUCTION 1.2 2. ............... .....,.*.. 46 Nonhomogeneous Equations « . . . . . * . * . 47 Page 4. COMPUTER MECHANIZATION OP MONTE CARLO METHODS FOR SOLVING- PARTIAL DIFFERENTIAL EQUATIONS ............. 50 4.1 I n t r o d u c t i o n ««»«*..«»««««.....«*»..««««..«««*. 50 4.2 S i m u l a t i o n o f the S t o c h a s t i c Process on an Analog Computer »»..•.•....«•.•......«...*..... 52 4.2A Analog Computer Setup ••••••*•••••••••.•« 52 4.2B Noise Source Requirements ............... 55 4.2C E f f e c t of F i n i t e Bandwidths on S o l u t i o n Times 4.5 . . . . . . . . . . . . . . a . * . . . . * . . . . * . . . . * * . . D e t e c t i o n o f Boundaries .......*«.............. 4.3A 4.5B 4.5C 57 D e t e c t i o n o f Boundaries f o r Problems w i t h One Space Detection Two Space Detection V a r i a b l e «»....o............... of Boundaries f o r Problems w i t h V a r i a b l e s »««.««««.««....»...«« o f Boundaries f o r Problems w i t h Three Space V a r i a b l e s »••«••••»..*•»'«••»• 5. 56 60 61 66 4.4 Generation o f I n i t i a l and Boundary Values ..... 67 4.5 Operations Performed by the D i g i t a l Computer 69 HYBRID COMPUTER SOLUTIONS OF ILLUSTRATIVE PROBLEMS . 75 5*1 I n t r o d u c t i o n «..«.«.*«.««..« 5.2 One-Dimensional Boundary-Value Problems ....... 73 5.3 L a p l a c e s Equation i n Two Dimensions •«....•,«» 79 5»4 Poisson's Equation i n Two Dimensions .......... 79 5.5 Heat Equation i n One Two and Three Dimensions. 84 5*6 Laplace's Equation i n Three Dimensions ........ 86 5.7 D i s c u s s i o n o f R e s u l t s .•»•»..•*».*«*•*•«•.«...* 86 « « « . » . . . . o • > * . . « . « « . T t iv 73 Page APPENDIX I I N T E R F A C E FOR T R A N S F E R OF DATA BETWEEN THE P A C E 2 3 1 R - V AND THE ALWAC I I I - E • • • » • • • » • • • • • • • • • • • • • • * • APPENDIX II MULTICHANNEL DISCRETE-INTERVAL APPENDIX III AN ELECTRONIC APPENDIX A 91 SPDT SWITCH BINARY-NOISE SOURCE . . . . . . . . . . . . . . . . . . 95 98 IV PROGRAM FOR APPENDIX V AVERAGE REFERENCES IMPLEMENTING DURATION «« v • o o o » » MONTE OF RANDOM WALES i o e 9 C A R L O METHODS ..... «•»•••••*•••••-•- e a o « g r 4 * o < T * « * « « f t « « 4 r « « « « < r « « « e * * « « o 100 101 103 LIST OP ILLUSTRATIONS Page 2-1, Space Region I l l u s t r a t i n g Defined Terms »...»..«.«. 7 3-1* Random Walks and I n i t i a l and Boundary C o n d i t i o n s of a T y p i c a l Problem with 1 Space V a r i a b l e ••••••••••• 32 4-1* Block Diagram f o r S i m u l a t i o n o f a S t o c h a s t i c D i f f e r e n t i a l Equation ••»•*««.*«»••*•«••«»*».*••«.« "X 5 3 4 - 2 * B l o c k Diagram f o r Generation of 4-3* T r i g g e r i n g o f Mode-Control F l i p - P l o p .............. 5 8 4 - 4 . D e t e c t i o n o f Termination Time t = 0 « • • « • • • • • » • • • * • • . . • • • • • • • • • • « * • 5 4 5 9 4-5* Boundary D e t e c t i o n f o r Problems with. One Space V a r i a b l e ••••••»•••••*«••.•*••••••*••••.••••••«*.*. 6 0 4-6* Two-Dimensional Region..**<,..«.••*...«.«»...«..».». 6 1 4 - 7 * Two-Dimensional Boundary D e t e c t i o n 4-8. Coordinate Transformation used f o r Boundary • « « « o » « * * * * » » « « * 6 2 D e t e c t i o n of Two-Dimensional Simple Regions ••«»... 6 3 4-9* Photograph I l l u s t r a t i n g a Detected Boundary 6 6 4 - 1 0 * Hybrid Computer System *»•••.*«•»«•••«•«.«•«•««•««» 7 0 4 - 1 1 . Flow Diagram f o r a T y p i c a l H y b r i d Computer Program. 7 2 5 - 1 . 5 - 2 . 5-3* S o l u t i o n s o f D. ^ — ^ + K dx 0 • • « « * • « . • • • • • * * • • * 7 4 o Values of 1 0 0 0^(07 obtained w i t h N = 1 0 0 0 . . . . . . . . 7 5 Average Time f o r a Random Walk used f o r the S o l u t i o n of a One-Dimensional Laplace Equation **»•»»«•*««»« 7 6 2 5 - 4 * = • Solutions of — % - ( 1 - x ) 0 = 0 • « • « » . . . . « • • • • « • « 7 8 o 5-5. 5-6* 5-7. S o l u t i o n s o f Laplace's Equation as a F u n c t i o n o f a Boundary P o s i t i o n * . » « • « • « • « . * . • « • * « * * * « . * « « « • * * • • 8 0 S o l u t i o n s o f Poisson's Equation and L a p l a c e s Equation i n the Region Shown ***•.»*.•**•*.***'**** 8 2 T S o l u t i o n s of the Heat Equation used i n the S o l u t i o n of P o i s s o n s Equation ••**»••*••*•*•»*•*•****«•«•• 8 3 r vi Page 5-8* 5-9» S o l u t i o n s o f the Heat Equation a t the Centre of a L i n e * a Square and a Cubic Region *.»••••*•«••»*•> 85 S o l u t i o n s o f Laplace's Equation i n Three Dimensions 87 AI-1* I n t e r f a c e f o r T r a n s f e r of Data Between PACE and ALWAC • « • * • « • "«• • * « * • • • *'» » * » • • • ••'• «•••*««*»*••••*«•• AI-2. I n s t r u c t i o n s f o r A c t i v a t i n g " Stepping Motor .»•*•«. 94 AII-1«. B l o c k Diagram o f 3-Channel Noise Source • •••».«••< 96 A I I I - 1 . C i r c u i t and P a t c h i n g f o r a SPDT Switch .*<•«•-»•<•'» 99 1 vii 92 ACKNOWLEDGEMENT Acknowledgement the my his course thanks of to this Dr. assistance E l e c t r i c a l support; A, and H. hybridization; . work. C. encouragement and and for Mr. R* thanks equipment E l e c t r i c a l particular, his E. are I supervisor Dr. E. assistance given for to helped would of like this Noakes, U.B.C., Butler have for with many his express of for the interest and computer helpful my w i f e , to project, Head the during discussions. Laurie, for her help. Research Council.for for a l l who Department, Acknowledgement and In to encouragement; Kohne Special due Soudack, Engineering Mr. is is gratefully given Studentships made Engineering available to awarded in through Block Department, U.B.C. v i i i the 1962, National and 1963, Grants to the 1964, 1. 1.1 INTRODUCTION Introduction High-speed computing devices together with s o p h i s t i c a t e d numerical methods are inadequate f o r s o l v i n g many p a r t i a l e n t i a l equations encountered i n the study of continuous differ- systems."*" Numerical methods c a l l e d Monte C a r l o methods are known f o r s o l v i n g many f u n c t i o n a l equations i n c l u d i n g a c l a s s of p a r t i a l d i f f e r 2 e n t i a l equations, but when implemented on a d i g i t a l computer 3 the methods have g e n e r a l l y proven to be v e r y / i n e f f i c i e n t . r 4 In I960 a Michigan r e p o r t an o u t l i n e d a Monte Carlo method u s i n g analog computer f o r s o l v i n g a c l a s s of homogeneous e l l i p t i c p a r t i a l d i f f e r e n t i a l equations. In the Michigan study, solutions were obtained w i t h a slow analog computer at approximately the same r a t e as that p o s s i b l e with a f a s t d i g i t a l computer. In t h i s p r o j e c t , a h y b r i d new computer i s used to implement Monte C a r l o methods that are developed f o r s o l v i n g a l a r g e c l a s s of both e l l i p t i c and p a r a b o l i c p a r t i a l d i f f e r e n t i a l equations. Computing techniques are developed so t h a t , u n l i k e the Michigan study, no s p e c i a l purpose the h y b r i d approach, many f e a t u r e s , program an e n t i r e problem equipment i s r e q u i r e d . With i n c l u d i n g the c a p a c i t y to s o l v i n g procedure and the c a p a c i t y to o b t a i n automatic p r i n t o u t of a l l s o l u t i o n s , are made p o s s i b l e . Most computer methods f o r s o l v i n g p a r t i a l equations depend upon approximating the equations 1 f i n i t e - d i f f e r e n c e equations. ' differential by a set of 5 The number of d i f f e r e n c e equations i n the s e t depends g e o m e t r i c a l l y upon the number of 2 independent variables approximated For digital is the partial differential and upon t h e . p r e c i s i o n r e q u i r e d many p r o b l e m s required in such the number that computation, of storage or difference and i n the times requirements that in for being solution. equations solution equipment equation the are case of COm- analog zr putation* as are solving elements, are entirely the set for Monte of solutions to the that Carlo stochastic solve inadequate random p r o c e s s e s as a means of mathematical which values sense to problems* a solution determined the solution* random p r o c e s s In the processes equations that by in of the are The for lumped analogies many involve others. the approximating random p r o c e s s is desired In the process converge be found, partial form of in; -some : passive such such and f o r differential random walks way related to the is a related manner in F o r many m a t h e m a t i c a l cannot case methods a n d membrane which repeated a but with methods problem f o r such equations simulations problems, analog are many are, known* to some Other methods of statistical blems difference electrolytic-tank suitable sampling of unrealistic* a pro- others, equations, c a n be used diffusion * A random p r o c e s s i s a p r o c e s s e x h i b i t i n g v a r i a t i o n s from o b s e r v a t i o n t o o b s e r v a t i o n w h i c h , no amount o f e f f o r t o r c o n t r o l i n t h e c o u r s e of" a r u n o r t r i a l " c a n r e m o v e * ? of The t e r m s t o c h a s t i c p r o c e s s a time-dependent nature.' is used to denote a random process 3 processes. the three (e.g. Such p a r t i a l d i f f e r e n t i a l equations linear Laplace's second-order equation) equation) equations. hyperbolic type solution by the In the A point for is value, walk, is sense A the As the started. By est can be to (e.g. equation) be is random at a walks be this is to are obtain are desired, value, of a shown, at to this the number point of where solution at this work,the random walks function generators well to determine d i g i t a l the random walks. random the the in is boundary or boundary of a each is deter- s t a t i s t i c a l walks points values dynamic is random-noise used to associated This walks generated on terminal positions computer average as walk values random a l l are and as a a were of i n t e r - obtained. comparators which such the at random converges tronic with to solutions. terminal position to the each i n i t i a l response of the considered, sequence an the to be normally average procedure,the to when as and of amenable or computer adjoining diffusion time the large in and analog used not of e l l i p t i c approximate started predetermined according solution In are the two discussed. used solution average w i l l to wave prescribed selected and mined. a either reached. parabolic namely, p a r t i a l d i f f e r e n t i a l equations of which terminated the procedure number and types; P a r t i a l d i f f e r e n t i a l equations methods a l l following large (e.g. canonic include approach can range be control with takes generated and memory the the the an Elec- analog computer walks. analog terminal advantage on the sources. the of on capabilities computer positions of analog The the speed computer of a d i g i t a l 4 computer. 1.2 Thesis Outline F o l l o w i n g t h i s i n t r o d u c t o r y chapter, partial differ- e n t i a l equations are d e r i v e d f o r c e r t a i n c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n s of a c l a s s of Markov processes. In Chapter 3>these p r o b a b i l i t y d e n s i t y f u n c t i o n s are used to d e r i v e Monte C a r l o methods that are proposed f o r solving a large.class of homogeneous and nonhomogeneous e l l i p t i c , a n d homogeneous p a r a b o l i c p a r t i a l d i f f e r e n t i a l equations. The convergence of the Monte C a r l o s o l u t i o n s to the exact s o l u t i o n i s a l s o The use considered. of a h y b r i d computer f o r s o l v i n g p a r t i a l d i f f e r e n t i a l equations by Monte C a r l o methods i s discussed i n Chapter 4. Computing techniques, by the equipment, are o u t l i n e d . as w e l l as l i m i t a t i o n s imposed Novel methods f o r d e t e c t i n g boundaries f o r problems with one, two and three s p a t i a l dimen- s i o n s are a l s o proposed. Experimental r e s u l t s are given i n Chapter 5 examples i n t h i s chapter and Poisson's equation i n c l u d e s o l u t i o n s of Laplace's i n two s o l u t i o n s of the heat equation and The equation three dimensions,as w e l l as i n one, two and three dimensions. F i v e appendices f o l l o w the c o n c l u s i o n s g i v e n i n Chapter 6. Included i n these appendices are the d e t a i l s of the 8 i n t e r f a c e that was scription..of a new b u i l t to l i n k the two type of multichannel developed f o r t h i s p r o j e c t . Q computers and noise source that the was de- 5 2. 2.1 FUNDAMENTAL RELATIONS FOR MARKOV PROCESSES Introduction In t h i s chapter c e r t a i n c o n d i t i o n a l p r o b a b i l i t y d e n s i t y f u n c t i o n s of s t o c h a s t i c processes known as continuous Markov processes are d e f i n e d and shown to be fundamental s o l u t i o n s of a c l a s s of p a r a b o l i c p a r t i a l d i f f e r e n t i a l equations. The of the p a r t i a l d i f f e r e n t i a l equations that are developed form is c l o s e l y r e l a t e d to the form of the equations f o r the boundaryvalue problems that can be solved by the proposed Monte C a r l o methods. In order that the methods apply to p a r t i a l differential equations of a v e r y g e n e r a l form, a v e r y g e n e r a l Markov process that can be r e a d i l y simulated on an analog computer i s considered. 2.2 Chapman-Kolmogorov Equations f o r Continuous Markov Processes w i t h i n Bounded Regions To s o l v e a boundary-value problem that i s d e f i n e d on an open bounded r e g i o n R and i t s boundary C, a continuous Markov process r ( t ) , d e f i n e d on R and C, i s considered. R i s assumed to be a one, two In t h i s work, or three-dimensional r e g i o n , and the v e c t o r r ( t ) i s assumed to have components x, y and z i n a c a r t e s i a n coordinate system. A continuous Markov process can be d e f i n e d as a s t o c h a s t i c process h a v i n g the-property that future^ v a l u e s of .r.,.; depend upon a time-Ordered set of known values of. r only 7 through the l a s t a v a i l a b l e value,* 6 T h a t i s , i f r i s known t o e q u a l r a t some f u t u r e t i m e t of r i 2 s i- n r n o a t time t ,then the value Q w a d e p e n d e n t upon known v a t some e a r l i e r t i m e t , <^t . - l ^ o of values From t h i s d e f i n i t i o n i t 7 can be shown f(1*2^2 that the c o n d i t i o n a l p r o b a b i l i t y density ^ '^ ) completely 0 describes 0 the s t a t i s t i c a l function properties Do fe f ir n where i t i o n f i s d e f i n e d as f o l l o w s . f(?2,t2 | ? *"fc )01^*2 i s t h e p r o b a b i l i t y t h a t t h e q Q random v e c t o r r i s i n d ^ t a t time t 2 i f a t time. , r = v . o' o The t e r m s g i v e n i n the d e f i n i t i o n are i l l u s t r a t e d The d i f f e r e n t i a l d r o f g e n e r a l i z e d volume a t t h e p o i n t d e f i n e d e i t h e r d x , dx,dy of R. 2 2-1. t h a t i s used i n the d e f i n i t i o n i s an element 2 is i n Figure o by ? . That i s , d r ^ 2 d x d y 2 d Z 2 d e p e n d i n g upon t h e d i m e n s i o n r 2 2 An e l e m e n t a r y p r o p e r t y of the c o n d i t i o n a l density f u n c t i o n f f o r a Markov process i s t h a t i t s a t i s f i e s the f o l l o w - 7 i n g Chapman-Kolmogorov i n t e g r a l ^ 2 > t 2 | r ,t ) = Q o Jf(? ,t 2 for a l l t This equation |r 2 <. t O equation n 1 1 , t 1 ) f ( r ^ ^ |r , t ) d r o o 1 (2.1) <_t . 0 2 expresses the f a c t that a t r a n s i t i o n of r from r 7 at t o to r~ a t 2 In function t i o n - g, f, is t 2 0 occurs addition the to via some the conditional following also point . conditional r, 1 at time t-, . 1 probability probability density density func- defined. Definition g(r^,t^ jr Q , t ^ d r ^ d t ^ random v e c t o r r between t^ r = r times w i l l is the reach probability boundary i f at that C within and t^ + dt^ time definition is a d i f f e r e n t i a l area a t Q the . dr^ , . o The term dr^ generalized in the surface about point r^ on C. element (see Figure 3 x Figure 2-1. ! Space Region Illustrating Defined of Terms 2-1) 8 From the Markov property walk from an i n t e r i o r point r t ^ must pass through some ? and the f a c t at t Q that a random t o a boundary point r ^ a t a t time t ^ <_ t ^ , i t f o l l o w s 1 g must a l s o s a t i s f y a Chapman-Kolmogorov equation; i . e . , S^b^b h h>\ V V = ? ,t )f(r ,t { for a l l t < o — 1 1 1 r ,t )d 1 o o r i that (2.2) t , < L t. 1 b • The Markov processes used f o r s o l v i n g p a r t i a l differential equations are i n i t i a t e d a t time t a t a point r Q w i t h i n R,and are terminated e i t h e r at a predetermined time ±2 ^ t Q or whenever the random v a r i a b l e r reaches a boundary point r ^ on C. Hence, i f a process i s terminated due to a boundary a b s o r p t i o n , i t occurs a t a time t ^ <_ t . these statements, f and g must s a t i s f y and boundary A. In view of 2 the f o l l o w i n g initial conditions. I n i t i a l condition f o r f . lim f(? ,t | r ,t ) = 2 2 o §(? Q 2 (2.3) - r ) Q where S(? " o^ ? 2 = 0 f o r ? 2 ^ *o a n d J^8^ 2 R " o^ ? d r 2 = 1 * 9 T h i s c o n d i t i o n expresses the f a c t that the point of t e r m i n a t i o n ? 2 i s the same as the s t a r t i n g point r Q i f the process i s terminated immediately a f t e r i t i s i n i t i a t e d . B. I n i t i a l c o n d i t i o n f o r g. lim g(? t v b | ? ,t ) 0 Q = 0 (2.4) That i s , the p r o b a b i l i t y of reaching a boundary point r ^ i s zero f o r a walk s t a r t i n g at an i n t e r i o r point r when the walk i s Q terminated immediately a f t e r i t i s i n i t i a t e d . C. Boundary c o n d i t i o n f o r f . lim ? f(? ,t 2 2 |r o > t ) = 0 (2.5) Q o"^ b ? T h i s c o n d i t i o n s t a t e s that i f the s t a r t i n g point r a boundary point ? Q approaches there i s zero p r o b a b i l i t y that r w i l l be b i n an i n t e r i o r r e g i o n d r a t a time t 2 2 > t . Q T h i s i s true s i n c e the process w i l l terminate immediately a t the boundary point r ^ . D. Boundary c o n d i t i o n f o r g. lim o g(r ,t b b r , t ) = §(?<, - 5? ) § (* o Q b b " V b where o(r w v o - r, ) b ( t , - t ) = 0 b b o unless r o = r, b and t, = t D O 10 t. 2 and As / the ? , interior the b / g(r n - ?) starting process is § (\ b point certain to - V r d r b d t = 1 b approaches Q a boundary point terminate immediately at the point i* . b In addition to these i n i t i a l the f o l l o w i n g i n t e g r a l r e l a t i o n must and t o 2 , t I 2 r Q , t o ) d r 2 f i r s t of term the bability that the v a l i d for a l l r Q + this r two has time t and reached a must 1 (2.7) is events = C Q equation at r ^ t j d r ^ o' o b b h 2 be , the probability that the boundary true, second term i s within time the sum of the r the tg. is pro- Since two terms unity. gral the equations partial following section (2.1) differential and previous are Partial Chapman-Kolmogorov section expanding (2.2) a are the Chapman-Kolmogorov converted to inte- second-order equations. Backward Kolmogorov The by of boundary In 2.3 • H / ' I S(r ,\ t within is be conditions, • R one also boundary : f ( ? The and converted term i n the to Differential Equations integral equations partial integrands of of differential the integral the equations equations 11 in a a Taylor limit. series series about F o ra general arerequired in which in a small series t h e random time Kolmogorov 1 f ( r = t 2 , t 2 | process r , andthen a l l terms variable by only r changes t h el i m i t t h ef i r s t processes a small t w ot e r m s i s taken. taking o f the^ T a y l o r b u t f o rMarkov amount of t h e The r e s u l t i n g p a r t i a l d i f f e r e n t i a l equations a r ecalled backward equations. At; + point i n t h eexpansions, when Consider t Markov interval At,only contribute second-order thei n i t i a l ? ,t o Q Chapman-Kolmogorov equation (2.1) f o r i . e . , ) Jf(? ,t | = 2 r 2 1 , t +At)f(? ,t 1 Q Q + At|r R For incremental gives If At At probability equation ,t )dr o (2.8) small, transition t h e t e r m f (r-, , t + A t I r , t ) i s t h e 1 o l o o probability density t h ed i s t r i b u t i o n o f displacements after Q t h edisplacement of reaching from r a boundary Q o f t h eprocess. after a small i s so small i s zero, It time At. that the i t follows from (2.7) that f(r ,t lim 1 At-^O o +A t r o' ,t o )d r n 1 1 (2.9) R To equation,the convert equation term f ( ? 2 , t 2 (2.8) into ^^.'^o + ^ a p a r t i a l d i f f e r e n t i a l ^ n ^ e equation i s expanded i n a T a y l o r s e r i e s about r - F o "the expansion, a l l r 0 v a r i a b l e s but are assumed t o be f i x e d . f(r ,t 2 The expansion y i e l d s r ,t + A t ) 2 o Q R ll(r ,t |r ,t -r At)(x -z ) + 2 2 o o 1 0 4K? ,t |r ,t At)(y -y ) + 2 2 o o + 1 o + (? + 2 * 21 o ' o 1 ? t +A t } ( x i- o x } (yi-y > Q A f(r ,t |r ,t +At)(x -x )(z -2 ) 2 2 6 + x 2 o o 1 1 o o 6 o z 0 ^ 2,1 1? , t + At) (y-L-y ) 2f(? 2 + Q i^f£(? ,t 2 bx 2 2 o r ,t o 0 o + At)( (Z-L-Z -x ) X l 2 o 2 |^ f(? ,t |r ,t At)(y -y )' 2 + + 2 ^2 2 2 o o + 1 0 1 ^ f(? ,t |r ,t At)(z -z ) 2 2 ^2 2 2 o o + 1 o ; O ) 13 + higher-order terms f(r l f t fAt V 0 t ^ (2.10) 1. If, terms not involving x^, y^ or z^ are taken outside the integral, 2. equation (2.9) i s used, 3. a l l terms are divided by A t , and the following limits are assumed; i i m r^ i- o r o i o' o i Tit At—o x x )f(? t +At ? t )dr a l ( r o' o t (2.11) ) J lim A t -*-o (2.12) 2 o^o a J (r ) R lim At-*0 1 (z -z )f(r ,t +At At 1 o 1 o R lim At 0 W J C ^ - V ^ l ' V ^ o ' V ^ l = ( 2 ' 1 4 ) R lim At-^0 J^yi-yo^^^i^o^^o^o^ *! = b ( r , t ) 2fe 1 R 2 o Q (2.15) 14 lim / 2ST , ( « 1 - . 0 ) 2 f ( p l t f 0 + A t | p o f t 0 ) d P b (r ,t ) 1 3 0 ( 2 . 1 6 ) Q At—0 R 1 lim At*-0 > At (x - )(y -y )f(r ,t At|r ,t )dr 1 X o 1 o 1 o + o o = ^(r^tj 1 R ( 2 . 1 7 ) 1 lim At^o (x -x )(z - )f(r ,t 4-At|r ,t )dr "St 1 o 1 Z o 0 1 o o = Cg^o'V 1 R ( 2 . 1 8 ) l At lim At—O (y -y )(z -z )f(r ,t At|r ,t )dr 1 0 1 o 1 o + 0 o = « (r t ) 1 3 0> 0 R ( 2 . 1 9 ) R ( 2 . 2 0 ) ZSt 1 X m At—o ^g^lvVAt) lim At—o - f(r 2 > t |f 2 Q > t ) I- t o t ) ( 2 . 2 1 ) then equation ( 2 . 1 0 ) becomes -£(ro,tJr / 2 ' " 2 r V ",t o ') ^ = a (r ,t )-p 1 i t o o o + a (r ,t )^ 2 Q o o + a (r ,t )^ 3 Q o + + c,(r ,t ) ^ + c ( r ,t ) § \ + c,(r ,t )ft , °' 6 <^o 6 W o 6*o6 o f 1 0 f v x 0 2 0 0 f 3 0 0 v z 0 ( 2 . 2 2 ) Z o . 15 This equation Section is a 2.4 Kolmogorov known a backward p a r t i c u l a r Markov equation Backward conveniently as in is valid terms of an process w i l l Kolmogorov Kolmogorov be for equation. which the In backward considered. (2.22) equation operator L can be written as r ,t • o' o (2.23) O o r ,t _ o o 7 where = r a ,t o' ( r , t n 1 ° 0 )-££> + , ( r a x 2 , t •)•$0 is are function with position in the r ? respect vector (2.23) and Q of p a r t i a l equation 0 0 0 ) e^o o subscripts a a , ( r . t 5 o The + 0 o to r . t O are and o t used and components The to that x vector 0 > y one dimension o o indicate that d i f f e r e n t i a l a n o r^ and d i f f e r e n t i a l equation. in y is d Z q time To of tg the are c l a r i f y the operator operations i n i t i a l parameters the notation, 16 _ _kf_U ,t |x ,t ) 2 O 6 2 o o = ( o , x ± 0 + b (x )^(x 0 ,t 2 |x o ,t o ) Q ) - ^ f Or o ,t 1 x Q 2 U 2 ' t 2 | o ' X t o (2.25) ) ) x By a procedure Chapman-Kolmogorov converted V r ,t b Using 1 Q equation backward +At) i s the previously operator ^ to a b ' similar Kolmogorov expanded defined i t follows S = L_ V V The for w i l l solving equations partial proceeding: t o Chapter limits (2.11) Kolmogorov to , t In series (2.11) to Q ) c a be n this case about (2.21) 3, w i l l the r Q . and the b 0 (2.26) o o equations 3 to derive problems similar (2.21) equations Q out above, that differential f o r m » t-^J r equation. limits b boundary-value a b i n a Taylor be used' i n Chapter of £ ^ carried g(5 ,t |r ,t ) o' derived (2.2) f o r notation, l to that to a Markov that (2.2fc). process and a method be that Monte have Carlo methods are governed by However, before that gives rise f o r generalizing considered. been the to 17 2.4 A Continuous Markov Process f o r which Backward Kolmogorov Equations are V a l i d In the Monte C a r l o methods to be o u t l i n e d , the coeff i c i e n t s i n the Kolmogorov equations c o i n c i d e w i t h the coef.f i c i e n t s i n the p a r t i a l d i f f e r e n t i a l equations f o r which the methods are a p p l i c a b l e . I t i s t h e r e f o r e necessary to consider, a Markov process f o r which the assumed l i m i t s (2.11) to (2.21) i are v a l i d . A mathematical model of such a process i s d e f i n e d by the f o l l o w i n g set of s t o c h a s t i c d i f f e r e n t i a l equations*. | | + A (x.,y.,z,t) = B ( x , y , z , t ) N ( t ) (2.27) |2 + A (x-,y,z,t) = B ( x , y , z , t ) N ( t ) (2.28) f | + A (x,y,z,t) = B (x,y,z,t)N (t) (2.29) 1 2 3 1 1 2 2 3 3 These equations can be w r i t t e n i n matrix form as | | + A(r,t) = B(?,t)N(t) (2.30) The dependent v a r i a b l e s x, y and z i n t h i s model are the components of the random v e c t o r r , f o r which d e n s i t y func-r t i o n s f and g have been d e f i n e d . The c o e f f i c i e n t s A. and'B. 1 i are, i n g e n e r a l , s l o w l y v a r y i n g continuous f u n c t i o n s of x, y, z and t . The d r i v i n g terms N^(t) are u n c o r r e l a t e d with each other, and each term i s s t a t i o n a r y Gaussian white n o i s e with 1 8 zero average. These p r o p e r t i e s of N^Ct) are expressed i n the f o l l o w i n g manner: = 0 N^*)/ (2.3D <^ (t )N (t ^> i 1 i 2 = 2D. § ( t t ) (2.32) =0 (2.33) r ^ (t)N (ty> i / j N (t )N.(t ) . . . K i 1 2 . (t )N (t ) 1 1 1 2 ^ 2 . . . N.(t N all ± i ( m 2 m + 1 2 =0 ) \ (2.34) (2.35) )^ t.)N.(t.)> ( ^ ( t ^ ^ t , ) ) , pairs In these equations the brackets <^ ^ s i g n i f y an ensemble average. S ( t ) i s tb.e u n i t impulse f u n c t i o n , and 2D^ i s the power s p e c t r a l d e n s i t y of N ^ t ) . Equations (2.34) and ( 2 . 3 5 ) , or s i m i l a r equations, are r e q u i r e d i n order to show that the l i m i t s of the h i g h e r - o r d e r moments (2.20) are a c t u a l l y zero. The properties that have been assumed f o r the model imply that each N^(t) has a Gaussian d i s t r i b u t e d a m p l i t u d e I n ( 2 . 3 5 ) , t h e sum i s to be taken over the equation ' p o s s i b l e ways 2 m! that 2m p o i n t s can be d i v i d e d i n t o m p a i r s . To show t h a t the process d e f i n e d by equation (2.30) 19 is actually given r ( t by the t ^ < Q ) a Markov = r , process, the Q i t statistics additional information: t From < Q t^. x ) = r + n sufficient o f r f t ^ ) that equation * l r ( t is are r(t_^) = to in show no r_-^ that, way affected where (2.30), r |B(r,t)N(t) j - dt A(r,t) (2.36) t Since upon ( t Q r ( t the Q ) r is Q s t a t i s t i c s , t ^ ) . giyen, = If the fixed, the of driving the additional s t a t i s t i c s of vector information r(t^) R(t) in r(t_^) = = T_ depend the r_-^ only interval is also then *o B(f,t)N(t) This in condition the N(t) interval in ( t intervals do on not Q r(t) ing by the , t Q since upon is The given 1 the indeed limits equations equations A(r,t) integral but does by equation Markov (2.11) (2.27) between not r to t give (2.32), (2.37) ± any about N(t) information N(.t) in of r(t-^) information the about two therefore r(t_^) = r_^. process. to (2.20) (2.29) = - Q information The • s t a t i s t i c s additional a dt provides ) , uncorrelated. depend Hence, ( t _ , t ^ ) , is the - t and of are t the Markov calculated = t + At by and process integratthen' 20 taking the required equation (2.27) Integration ensemble with averages l - x notation, gives o X Consider the coefficients written i n vector t +At ( and l i m i t s . o ) = A t V - A (r,t)dt + 1 J3 (.r,t)N (t)dt J 1 1 (2.38) Under rate thfe than condition N^(t), that this A^(r,t) equation and B-^(r,t) c a n be vary 1 Q o 1 Q slower A t ( -x ) = - A ( r , t ) A t + B ( r , t ) o a much written V Xl at N ^ t j d t + o(At) o (2.39) where l i m o(At) _ o (2.40) At—0 th The by ensemble average of the n t h e Binomial! Theorem power of ( X - ^ - X q i s ) expressed as n k n-k < ( * l - o ^ k.'(n-k)J - A l ( ? o ' t o ) A t k=0 V A t ^N (t )N (t ) 1 1 1 2 . . ^(t^)^- dt^tg . . . .dt k + o(At) (2.41) 21. where, Prom for k = 0, conditions N the multiple (2.32), 1 ( t 1 ) N (2.34) ( t 1 2 ) . integral and . is (2.35), R (t )J> . 1 k k , ^ ^2, (2D )^(At)' I k for!k A 1 ,dt •= d ^ d t g k for ki unity. k 0 odd (2.42) even (2.43) 2 (|)J 2 Hence, A ( r , t 1 = limits obtained Q taking a l l the are valid the for For b^(r ,t ) o o from limit. By in the in stochastic x A t Markov the a for + that process a l l by defined by equations, d i f f e r e n t i a l equations 1 for n for n _> (2.44) =2 i t in (2.45) 3 (2.46) limit dividing assumed relationships Kolmogorov = o(At) procedure, were n higher-order expressions a similar completeness, coefficients o(At) and Q these conditions the or + D , t ) , limiting ) A t o(At) directly and (2.29). a ^ ( r Q 2 = The o are by follows A t that Section equations 2.3 (2.27) to between the and coefficients (2.27) the to (2.29) limits, are 22 listed below: a i vV ( (2.47) (2.48) a 5 ( r o , t ) Q = ~ 3 A (2.49) V V ( -I 2 (2.50) (2.5D 2 V o'V = ? B 3 ( = The fact (2.52) V V C = that 3 o'V coefficients c.(r ° = ( ? ,t ) 1 0 consequence of correlated with theory, but in realize noise the assumption each other. practice sources i t that This would with the noise zero terms is extremely specified are - is 55) a 0 assumption be (2 NV(t) not are not necessary d i f f i c u l t crosscorrelation in to as well as autocorrelation. A density ential functions equations following satisfy Markov Kolmogorov f and (2.23) section, more process g giving that and auxiliary general equations partial w i l l be rise satisfy (2.26) has to Kolmogorov been probability d i f f e r e n t i a l studied. conditional probability partial discussed. density In functions equations than d i f f e r the that the 23 2.5 P a r t i a l D i f f e r e n t i a l Equations Probability The Density are partial d i f f e r e n t i a l equations. only functions partial contain and Monte terms g^which Carlo in means The the form variable of the i t s e l f of Kolmogorov can be equations methods Auxiliary this equations by can been equations, of problems form have solving Kolmogorov only obtained that for derivatives that d i f f e r e n t i a l equations extended ent f of Kolmogorov derived however, basis by Functions second-order the Satisfied the density yielding be treated. containing considering the An depend- auxiliary 12 density functions functions in the are u ( r f and v defined from the section by g. this With same weighting below. Markov the extension, These auxiliary process probability as considered density p a r t i a l d i f f e r e n t i a l equa- c o n t a i n i n g a t e r m : i n the - dependent v a r i a b l e i t s e l f c a n be s o l v e d . The a u x i l i a r y p r o b a b i l i t y d e n s i t y f u n c t i o n s u and v defined 2 and obtained previous functions tions are u , t 2 r as o , t follows: Q ) = /exp -m(t ,t 2 Q ) ^ 2 ^ 2 V V (2.54) ; (r, ,t, ' -b' b r o' ,t o (2.55) ) 24 The term m(t ,t ) Q is m(t ,t ) 2 where d[r(t),t] vector r(t) and Q = is a given / by the (2.56) d[r(t),t]dt continuous time functional positive of the random t. r(t )=r 2 The function 2 denote brackets a r(t )=r Q conditional expectation; that tion the subject within r(t ) = r 12 Siegert, satisfy ^2'*2 ' and brackets r ( t ) is 2 In a manner i t w i l l the be a p a r t i a l 0 T to that = L_ the to small similar shown following IV V in is, expected the conditions region that u ( r 2 dr given , t value r 2 Q d i f f e r e n t i a l by Q func- v^- Darling ) the that about 2 , t of and _ v(r^,t^ and _ -o'^r) r equations: u ( r , t | r , t ) - d(r ,t ) u ( r , t r ^ t j 2 2 Q o Q 2 g o' o l (2.57) V V =L._ . v ( r o' b , t b r , t o Q ) - d ( r o , t o ) v ( r b , t J r o (2.58) o , t o ) 25 Prom the identity exp -m(t ,t and the ^ m ( t i t ) 2 2 , t 1 ) -^r^exp - m ( t 2 , t 1 ) d t (2.59) 1 =-d[r(t ),t ] 1 2 the multiplying (2.60) 1 that -m(t ,t ) Taking 1 - relation follows exp = = o - 1 d[r(t ).,t ]exp 1 conditional by f ( ? 2 , t 2 1 expectation r Q ,t ) and of - m ( t both applying 1 ) d t sides of 2 , t (2.61) 1 this definition equation, (2.54), gives u ( r 2 , t r 2 o' ,t o ) - r ( t ^ y ^ < ^ [ r ( t 1 ) ,t ]exp 1 2 ) = r -m(t ,t ) 2 2 dt-jf ( r 1 r(t 2 , t 2 r o' ,t o )=r (2.62) ) ! . 26 The c o n d i t i o n a l expectation, i f r ( t ^ ) is,considered fixed at r-^, can be w r i t t e n r(t )=r 2 d[r(t ),t ]exp 1 2 -m(t ,t ) 1 2 1 r(t )=f. 0 r(t .)=r N 2 d(r ,t- )exp 1 L -m(t ,t ) 2 1 r(t )=r 1 ^ where p ( ? » ' 1 t r ,t ;r ,t )dr 1 Q Q 2 2 2N 0 ^ 0 \p(r ,t 1 1 r ,t ;r ,t )dr 1 o Q 2 2 (2.63) / i s the p r o b a b i l i t y that the 1 random v a r i a b l e r i s i n the r e g i o n dr-^ a t t-^ i f i t i s given that r i s at r tively. P(r » 1 Q and i n the r e g i o n d r a t times t 2 Q and t respec- 2 F o r a Markov process t 1 r„,tj 0 ' 1 O' f(? ,t 2 2 r ,t ) 1 1 (2.64) t Now, s i n c e r-^, w i t h i n the c o n d i t i o n a l e x p e c t a t i o n , i s fixed, d ( ? , t ) 1 i n the second member o f equation ' {2£ft) 1 taken outside the c o n d i t i o n a l e x p e c t a t i o n . Markov process, i s given and t c a 2 > Q "> t . The c o n d i t i o n r ( t ) = r t h e r e f o r e be d e l e t e d from the c o n d i t i o n a l t Also, f o r r ( t ) a r ( t ) i s independent o f ? ( t ) when r(t^) = 2 n Q Q expectation. can e 1 27 Therefore, R f ( r 1 > t |r 1 f Substituting equation using the definition u ( r 2 2 , t | r , t o Jyd(r ,t )u(r ,t 1 *o If 1 2 Q ) = f ( r ( , t 2 ' ? o of u ( ? 2 , t r 2 1 2 , t 1 2 ) = r r(t Q )=r r ( t 2 ) = r 2 r ( t 1 ) = r 1 ) f ( r 2 t back , t 0 2 o ' ? (2.65) r 2 Q r ( t , t t o 2 I r 2 , t 1 ) d r 1 (2.65) ) into equation (2.62), and gives 2 , t 1 Q ) f ( r ) - 1 , t 1 j r Q , t 0 ) d r 1 d t (2.66) 1 R the order equation where of integration are operated from (2.23) upon i s with reversed and both the operator sides L of the + -^-r , o' o 28 r ,t ) = 0 o' o the f o l l o w i n g equation i s obtained; + "TT yd(r l 1u ( r , t 2 t )u(r f 0 2 f t |r 2 r 0^ , tO ' j = 2 l f t )f(r ,t Q 1 Q j r ^ t ^ d ^ (2,67) R Prom equation (2.3), lim f(r ,t 1 however, S (? - r ) | r |,t ) = 1 o o 1 Therefore, u(? ,t 2' 2 st o L 0 u .r , t J -V V 0 =L o u(r ,t 2 2 r ,t ) -d(r ,t )u(r ,t o Q Q Q 2 2 (2.57) as was to be shown. By a s i m i l a r a n a l y s i s , w i t h p ( ? , t 1 r e p l a c e d by q ( ? , t 1 q(r ,t 1 1 I r ^ t ^ r ^ t ^ ) , where 1 |,r ,t ;r ,t )g(r ,t o o b ^o'"* o'^2'^2^ ; 1 b b f(r ,t 1 1 b r ,t ) o Q r ,t )g(r ,t o o b b r^t-J (2.68) 29 i t follows that It functions from is u conditions (2.3) definitions partial suggests as , v > t O' that the to satisfy to (2.6) (2.54) of and the density solutions This r t ) o satisfies note the as differential problems. chapter. v form fundamental value r important and The the > f that same g (2.58). auxiliary and density boundary respectively. This follows (2.55). i n i t i a l and equations functions or the i n i t i a l 1 and equation Green's property w i l l boundary developed f, g, u in and functions be condition's studied this v for in can for chapter be regarded boundarythe following 30 MONTE C A R L O METHODS 3. FOR THE SOLUTIONS OF BOUNDARY-VALUE PROBLEMS Introduction 3.1 In density value can functions problems be i t s e l f of is point is values point for or u a l l and analog sense to as of the the true The the time derivatives. and in and way problem defining a new B n o w "be for and be is not can the standard the form be described and v in which solution functions value walks in that is convenient since transformed to at f and the a walks increases. in preceeds the analysis, required of an form variable. for outlined. solving the various classes of on s t a t i s t i c a l equations the g, simulated sign for is determined equations minus the boundary is in random differential a a expected value converges of and at originating The random number methods be i n i t i a l expected of boundary- differential the density the to u walks desired. partial This of random to of boundaries. value number as g, considered, of is f, a l l approximation always time on probability the restricts Methods w i l l as large of A actual partial expected The Problems no by those probability- 0 governed to solution form solutions methods solution computer. the form a and between The approximation from v developed. i n i t i a l l y the An experimentally an be u problems terms v. and g, terminal points which in f, same given the relationships problems obtained at written to the In chapter w i l l applied equations 0 this problems by 31 3.2 Solutions of Boundary-Value Differential The section i s f o r Parabolic of the problem t o be c o n s i d e r e d Determine 0(r o ,t o 0 is (2) satisfied a piecewise is (3) C b ,t Q o f R; o 7 a bounded continuous region i n i t i a l R*, condition'0 (r ) o ) (3.2) o continuous i s boundary satisfied on t h e condition boundary i . e ., W ^ o W ' The The time that 0(r o ,t 7 o ,t 0 ), with determine random t defined walks (3 and i n i t i a l one space variable ) i s To (r boundaries problem that f o r t variable i s o and boundary shown < If a walk 0 (r ,t^) c with b as 0 of Problem at point soon as a boundary terminates i s position o n a- b o u n d a r y recorded, r^, whereas the i n i t i a l i n i n the figure (r of Figure i s i s at reached ( r ^ t ^ ) i f a walk value i s 0 (r^) q A at a ,t 0 terminated 3) such 0. the solution are started ' conditions a r e shown 0 is Q w i t h i n R;. i . e . , Q a piecewise c 3-1. this that : = 0 (r ) ; Q 0 (r ) such within satisfied (r ,0) 0 typical i n follows. Problem.A a Partial Equations statement as Problems ). point Each walk 0 or at t = 0 . the boundary terminated is recorded. value at t It = 0 Figure Random W a l k s 5-1. of a Typical and Problem I n i t i a l with 1 and Space Boundary Variable. Conditions 33 The can expected be w r i t t e n f(r ,0 i n terms 0(r ,t ) o 0 Q = ^ o b ( 5 2 ) f ( r 2 of the i n i t i a l of the probability r ,t ) and g(r ,t 2 Q value r b 0 , t 0 ) and boundary density values functions as | r , t ) d r . , 0 0 o R 0 (3.4) where tion. (3.4) i t has been I t must ential be proven i s actually To prove equation operator h assumed o and t o that a solution that + L_ . , the result i s the expected 0(r ,t ) o Q value as given i s the solu- by equation of Problem A. 0(r >t ) o o f Problem ^ o ? that o satisfies A, operate Since the partial on equation the operator differ- (3.4) w i t h t h e i s with respect to 34 , *o \ + L r . t o' 0(r 1 ,t 0 ) 0 o R 0 0J*V,tJ + / ^ r + L_ ^ ( r b , t b | r o , t o ) d r . b d t b (3.5) The right (2.23) side and of equation (2.26) _ 4 | ( r 0 and , t Q i n i t i a l ) also A, prove satisfies consider the Q o ' by Kolmogorov (2.4). equations Therefore, o and o ( 3 > 1 ) o 0(r ,t ) i n i t i a l zero 0(r ,t ) r that is condition = L 0*0 To (3.5) Q as defined boundary by equation conditons of (3.4) Problem . 35 lim 0(r ,t ) = o A ^ r ) lim f(? ,0 o 2 r ,t )dr 2 0 Q t * 0 R 0 + 0 c ( r v V l i m g ( r b' b t r t -*o , t )dr,dt, o' o b b (3.6) 0 By equations ( 2 . 3 ) and ( 2 . 4 ) , lim 0(r ,t ) = o Q y 0 o ( ? 2 ) S equation ( 3 . 6 ) becomes (r 2 - r )dr Q 2 = 0 (r ) . o Q (3.7) t ^ O R Therefore, 0 ( r ,0') = (3.2) 0 (^ ) Q O Also, lim r /0 (? ) 0(r ,t ) = Q O o lim 'f(r 0 V * o o b 2 2 > o^ b r R ) d r 2 0 r + o *o 0 b , t )dr, dt, o' o b b (3.8) 36 By equations lim (2.5) 0(r ,t ) = Q o and t h i s equation becomes (2.6), f /0 (r t ) 8 ( r ^ ) § c v b ( V V ^ l r —*r. Therefore, ^b'V • = Since a l l c o n d i t i o n s of Problem A are s a t i s f i e d , 0 ( r ,t ) o o as d e f i n e d by equation (3*4) i s a s o l u t i o n of the problem. The Monte C a r l o s o l u t i o n of Problem A i s obtained approximating the expected value 0 ( ? >t ) given by by equation (3.4) with the average 0 - ^ ( r » ) of the i n i t i a l and boundary Q 0 values 0^ that are recorded from a set of N random walks o r i g i n a t i n g at ( r , t ) . 0 Q T h i s average i s N i=l The convergence of 0^(? >"t ) "to 0 ( r , t ) i s considered i n Section q 3•5• Q Q Q Problem B Determine 0(r ,t ) o such Q that : _ 4f v v - ^vv - ^o-v^vv (1) \ = l V 6*0 + ^ 1 (3.11) is satisfied (2) .a p i e c e w i s e fied within continuous Q a piecewise (r, , t 0 i.e. Problem equation 2.5). as solution 0 ( V V that t v o Q ) = 0 c ( ? R 0 + satis- condition on t h e boundary 2 with ? ,t )dr o o v t o problem density by analogy 2 boundary satisfied 0 satisfies /0 (r )u(r ,O o i s (3.12) Q ) C of « i s t h e same functions R; (3.13) t h e same partial u and v the previous i s = condition = 0 (r ) ; of this the auxiliary Therefore, R*, , statement A except i n i t i a l continuous ) i s 0 ( r The region w i t h i n R; i . e . , 0(r ,O) (3) a bounded 2 as that f o r differential (Section problem, the 38 Prom (2.54) definitions (2.55), and equation (3-14) r(0)=r 0 0(r | ,t ) J0 (r ) = Q Q J ^exp - 2 d[r(t),t]dt r(t )=r R f ( ? Q 2'° I VV* "; 1 ? + / / 0 *o expected approximated N walks value ( c v V < ^ e x <V = ? b d[r(t), t]dt p r(t )=r Q C r The becomes o ,t value o' )dr,dt, b b 0(r ,t ) o Q by t h e average originating at at the terminal (3.15) given 0^(^ f^ ) o (? »"t ) 0 point by equation Q Q where (3.15) c a n be o f "the p r o d u c t 7 j_0j_ f 0^ i s of the i * * 1 walk the i n i t i a l a n d "Y^ i s / or ° r boundary the value of T y = exp - / t. o d[r(t),t]dt (3.16) 39 for T, the corresponding is 0 f o r walks minating walk. The upper terminating at a boundary. at t The Monte limit = 0, of integration... and t ^ f o r walks Carlo solution is ter- therefore N i=l Solutions 3.3 of Boundary-Value Differentjial The arise and boundary-value The Problem problems of steady-state equations the Poisson f o r these statement L_ 0(r problems Typical discussed partial are the Laplace ) = 0. i s 0(r C i s as equation ) such satisfied follows. that: within a bounded o (3.18) region (2) C, D and E t o be fields. of Problem Determine P P a r t i a l equation.' C (1) f o r E l l i p t i c Equations i n the study differential Problems RJ a piecewise is continuous satisfied on t h e boundary . 0(r ) b The boundary subscript t = 0 (r ) c is b . deleted condition C o f R„ c b i.e-., . from 0 (? ) (.3,19), operator L_ 0* 0 to indicate that L_ r_ i s ^.independent of time., 40 The solution of conditions expected random solution of this problem problem of type A. a are value walks of of values originating value is written g ( ? b r ,0) b , t Since independent boundary in at terms r of t , the at at Q is the L steady-state and solution the time the at terminal t = probability 0. r is Q the points The density boundary of expected function as Q oo 0(? ) = o J ^ 0 0 Prom equation follows solution that of c ( ? (2.26) 0(r } ) g ( r ) and as Problem o b , t b b | r ,0)dr dt o (3.20) b C Equation 0 ( r boundary given equation (2.6) (3.20) is for g, indeed i t a C. (3.20) = j f 0 by condition c < 5 b can ) G < also b l 5 ? o be ) d r written as (3.21) b C where oo g ( ? 0 b , t b r r t > 0)dt b 3.22) 41 i is the at time t C. As for tion of probability = Q w i l l or problems, (3.21) terminal that a eventually previous (3.20) the 0 density can boundary random terminate the be walk starting in b expected approximated values on value by That 0^. dr the given the at r Q boundary by equa- 0jj(? ) average Q is, IT i is the Monte Problem Carlo Determine L_ - 0(? ) Q 0(r ) such Q d(r )0(r ) = o Q that: 0 within a (3.24) o r bounded (2) 1 solution. D (1) = a region piecewise 0 (? ) c is b R\ continuous satisfied boundary on the condition boundary C of R; i . e . , 0(r ) = b Operator L_ ? time t , but a solution problem solution of type c . b (3-25) coefficient d(r ) are independent of o otherwise The of and 0 (r ) are of B. as defined by (2.24) this problem is the Hence, by analogy and (2.56). steady-state with Problem C, solution the is 00 0(r ) Q = J T/0 (? )v(r ,t 0 c b b b b |r ,0)dr dt Q b b . (3.26) 42 For t a = large 0,the number N expected of random value walks can 0(? ) Q starting be from r approximated at Q time by N ) 0„(?) = 1 o 7A (5.27) i=l where is y^ the value of y exp - - / d[r(t)]dt V for of 3.4 the the i * * i t 1 Solutions be and of the boundary Nonhomogeneous solutions constructed independent dependent is 0^ value at the terminal point walk. h The can walk of from boundary-value typical example for Problem E follows. Problem E is nonhomogeneous the boundary-value as solutions problem problem. problems Determine (1) L 0(r) r = Boundary-Value - and type 0(r ) ) a boundary-value a homogeneous homogeneous Poisson's of H(r 0 of is E. such Problems The problems time- time- equation statement is a of that: satisfied within a (3.28) 0 o bounded region continuous (2) a piecewise R, where H(r ) is a piecewise function*,. continuous boundary condition (r, ) 0 C D 43 i s s a t i s f i e d on.the boundary C o f R; i . e . , 0(r ) = 0 ( r ) b c (3.29) . b To determine the s o l u t i o n o f Problem E, consider the time-independent boundary-value problem o f type C: (1) L_ 0 ( r ) = 0 w i t h i n R, (3-30) 1 r o 0 (? ) (2) 0 ( r ) = x c b .(3.31) on the boundary C o f R •. b and the time-dependent boundary-value problem o f type A: (!) _ 4O^o = - L r w i t h i n R i ( 5 ' 3 2 ) o (2) 0 ( r , O ) = H ( r ) (3.33) (3) 0 ( r , t ) = 0 (3.34) 2 Q 2 b Q . Q The s o l u t i o n o f Problem E i s g i v e n by 0 0(r ) Q = 0 ^ ) J + 0 (r ,t )dt 2 Q o (3.35) . o -OO Proof Operate on 0(r ) with L_ r and use ( 3 . 3 0 ) and (3.32) . o 0 L_ 0 ( r ) = o J o ^ 0 ( 2 V V d t o ( " 6 ) - OO = 0 (r ,-oO) - 0 (r ,O) 2 Q 2 Q . (3.37) 44 Since the boundary-values Therefore, r (3.35), a r e 0, 0 (r ,-oO) = 0. 2 2 Q (3.33), by L_ Prom f o r 0 f o r r Q 0 ( r ) = - H(5 ). (3.28) . o = r v 0 0(? ) b = 0 (r ) 1 + b y 0 2 ( r b , t ) d t o . o (3.38) - oo Therefore, (3-31) by conditions 0(r ) = 0 (r ) b The solution Problem E, determining some ) given and i s The and 0(r Carlo numerical problems satisfies a l l conditions of solution. solution integrating of Problem t y " 02^o'^o^ t h e m e w i _ t : t l ' t t l E i s o d s o respect f obtained by Problems A to t Q by technique. 0(? ) L_ solved (3.35) a (3.29) . b 0-j_(r ) a n d 02^o'^o^ Nonhomogeneous are by therefore Monte C and then r c (3.34), and Q - equations d(r )0(r ) o Q = - o f the form H ( r o (3.39) ) o i n t h e same o f type manner B a n d D. as Problem E by considering 45 Estimates 3.5- o f t h e Number o f Random Walks f o r Monte Carlo Solutions Convergence 3.5A Monte equations o f Monte Carlo are given Carlo solutions Solutions. o f homogeneous p a r t i a l d i f f e r e n t i a l by N 0, i=l where f o r problems Let the recorded the random measure o f type values variable t r i a l s , the Central i s given distributed Limit f o r a given a s ,7=W. UN^ by a factor random Q ) ± be denoted by 1 Q of 0jj(? »t ) o ± o i s obtained a on T Theorem, It 0 0]^(? »' ) t o o (3.40) w i l l be n e a r l y therefore- follows that normally the probability .05 t h a t To reduce the standard o f 2, f o r^example, walks. o 'Y 0 ' by t h e s t a t i s t i c a l convergence is ( r , t by of 0^(r ,t^), which of values > Hence, i s replaced ± 0, (r , t ) = 1 v a r f o r N large. approximately 0 The v a r i a n c e 0. var is 0^, of the fluctuations different From B a n d D, 21 var. 0 N • (3.41) o f 0]\j-( >t ) r o deviation i t Is o to 0(r ,t ) o o' o7 n , / v a r 0T, (r , t ).' V N o' o necessary T v to simulate 4N 46 3*5B Number of. Random Walks for.Homogeneous P a r t i a l Differential Equations An required If an with estimate f o r a given error o f t h e number tolerable 0 (r ,t ) N probability Q o ;05 i s ? N > is a var sufficient 0 number - gives a lower an •estimate error o greater Q tolerable, then f Y a f d r W : canobe that from than € , as occurring inequality (3.41) (3.42) walks. that E o r some f o r these f o r N. When cases special v a r 0 cannot obtained 'by"noting- of 0 max i s t h e maximum t h e r e q u i r e d number value o f random 40 Por that example, be c a l c u l a t e d , that whereas i f (3.43) of 0 0 walks A pessimistic i s € then = f o r .01, then € estimate therefore 2 i f the p a r t i a l d i f f e r e n t i a l equation = 1, 0 cases, condition var 0 < 0 ^ where are follows. g A. o f random bound walks can be determined 0(r yt ) can be c a l c u l a t e d , , so (3.42) N o f random = .05, N should N should i s scaled be g r e a t e r be g r e a t e r than than 40,000, so 1,600? 47 3.5C Number o f Random Walks f o r Nonhomogeneous Differential The equations Partial Equations. s o l u t i o n of nonhomogeneous p a r t i a l differential of type E i s g i v e n by 0(r ) = 0 (r ) + Q 1 0 (r ,t )dt / Q 2 o Q .(3.35) o -oo Por a Monte C a r l o s o l u t i o n , 0 ^ ( r ) i s approximated by Q 0J_-JJ(^ ') • O and the i n t e g r a l i s approximated by M . I = ) i-1 ^ ^ ( ^ . i A t (3.45) J where the Ct ^ depend upon the numerical i n t e g r a t i o n t h a t i s used. s u b s c r i p t L i n d i c a t e s that each value o f 0 ( r , t •) i s t o ber The o 2 r obtained u s i n g L random walks. O O The s e l e c t i o n o f numbers N and L w i l l now be c o n s i d e r e d . L e t the Monte C a r l o approximation t o 0 ( r ) be denoted by 0 u j ( ) > then r J o o M v a r 0 NL ( r o } = v a r 0 IN ( r o } V a i v a r 0 2L ( V i A t o } i=l (3.46) 48 If v a r0~ x ( r ,j A t ) i s t h e maximum 2L 1=1, o . . . value o f v a r 0 {v ,i>At nr o ,oi ^2L o . M , a n d i f Ct^ a r e c h o s e n ). by thetrapezoidal rule; i . e . , A t i = a a = A t ± =~2 ' M a ' a i o = 2,3 . . ^.47) .(M-l) then 0 var N L 0 (? ) (? ) < v a r Q IN + v a r 0 Q 2 L (r Q , jA t ) ( A t ) ' ( M - §) 2 Q 0 (3.48) 0-^ a n d 0^ ^ Let 02j (r , j A t j Q Q t h e random e ) a r e formed; var 0 „(r var 0 ) - T v a variables from which 0jjj( ) r r 0 1 <. c max • 0 2 0 c o o = v a 2 r 0 — ^ andH „ a r e t h e maximum max c max function It r T 0 ( -^) T a dfunction H(r ), n O therefore Q follows The a r numbers side where of this 0 N L ( r o } 2 ^ H d H max L" absolute (3.49) (3-50) • values o f t h e boundary " respectively, f o rt h e problem. + 2 _ ^ - ( W a n d :L c a nhe chosen expression Q i s thetotal n that 0 v a then (r,,,j At.) 2L o subject number A t 0 ) 2 ( M t o minimize - § ) the right-hand to. t h e c o n s t r a i n t o f random walks (3.51) that N+ML = Q , a r e taken.to 49 obtain a value of 0(r). The minimization /M gives !'/H - (3.52) This results, gave I when = 133 for example, the time integral I value 0 of was l N used N = Q 1,000 required only (r ). with about the and to Poisson M = 19. obtain twice the equation Thus, a Monte time at in least Carlo required Section for value to of obtain 5.4, this the a 50 4. COMPUTER M E C H A N I Z A T I O N OP MONTE PARTIAL 4.1 Monte upon Carlo the system following operations. with for the The equations solutions computing 1. DIFFERENTIAL METHODS FOR SOLVING , EQUATIONS Introduction Based the CARLO for of given partial in Chapters differential implementing the methods must stochastic differential equations of 2 and for 3 equations, perform Section a the 2.4, namely || + A (x,y,z,t) = B (x,y,z,t)N (t) (2.27) |£ + A (x,y,z,t) = B (x,y,z,t)N (t) (2.28) | | + A (x,y,z,t) = B (x,y,z,t)N (t) (2.29) i n i t i a l partial 1 1 2 3 2 2 5 conditions r(t differential 1 ) = 3 r Q equations must he simulated. that contain 0 In addition, itself, functional T J = exp - d[r(t),t]dt *o must he generated. (3.16) 51 2. t The s t o c h a s t i c = 0 This 3. of or whenever requires The a The 4. must the boundary method i n i t i a l t h e random process or walks be terminated C of f o r storing boundary must region R is 0^ at at time reached. and d e t e c t i n g values be a either boundaries. the terminal points generated. average N ^ i=l or N i=l • for U very which a large solution must is 5. The s t o c h a s t i c for each ment of (? >"fc ) after In 1, this 2 and 3 are 4 and 5 are be process walk. 0 carried must at be Automatic each chapter carried obtained each point ( r 0 >"t ) f o r 0 desired. random 0 be set a initiated, readout of o f N random computing system out by an analog terminated and 0^(^ '^ ) o walks out by an associated i s d i g i t a l n d also i n which computer a o and reset adjustdesirable. operations operations computer w i l l described. The Electronics Logistics experimental Associates Research studies Inc. ALWAC PACE III-E were carried 231 R-V d i g i t a l out analog computer. on an computer The and design a and construction computers of interface was a n i n t e g r a l equipment part of f o r hydridizing the project. t h e two Details of this Q aspect 4*2 of t h e work Simulation 4»2A Analog is of simulated defined of f i r s t and nonautonomous. equations heat of order, the noise stochastic shown this and V7 0 2 computer are of a for generation single diagram (2.27) form. 0=0, involve of The and the integration simply variable. with whenever A2 s h o w n variable x» Special o f a more i n i t s most diode general function closed-form techniques 4-1 used track-and-hold i n mathematical functions are form. form generators o r whenever t h e 1"5 i s the indicated general i n Figure This f o r simulating generation f o r the functions functions Integrator t h e random only nonlinear differential y f equations equations autonomous equation The f u n c t i o n multipliers a r e known hold" linear block equation 4-1* expressions of the stochastic (2.29) N^(t)* can be r e a l i z e d quarter-square only however, differential are coupled, sto- to (2.27) differential = ~^+» f o r example, analog i n Figure I. Computer the general equations These they partial f o r Laplace's differential figure computer. independent, terms An is to on an Analog methods, by differential P o r many equations equation, Carlo and i n general importance* reduce stochastic Monte on t h e analog are Process and i n Appendix Setup the proposed process engineering i n the literature the Stochastic Computer In chastic appear to required "track feature i s and used 53 Figure Block 4-1. Diagram for Simulation Differential to hold the at the terminal value i n i t i a l a or constant computer. boundary value The of while 0^ mode-control 0^ or random ( 7^0^) synchronize the compute i n i t i a l - c o n d i t i o n modes Al. The and generation comparators For and the of these d i g i t a l problems in c modes ^ and of and from r, (Section read by the l o g i c a l integrator respectively computer the s r, its mode-control which Stochastic vector generated signal track-and-hold a Equation the value of is signals discussed functional 7 / 4.4) d i g i t a l inverse with A2 of consequently c the integrator from in must electronic Section be 4.3. generated, 54 the following implicit method is used. Prom equation (3-16), ="7d[r(t),t] (4.1) and 0 An analog computer block in Pigure 4-2. 'X is that the A3. 1 7(t ) Note diagram available mode of for at these the integrator equations output A3 is of also is shown integrator c o n t r o l l e d by r(t) d[r(t),t] 7(tJ= l t + 7d[r(t), Pigure 4-2. Block Diagram for Generation of t] c. 55 4.2B. Noise Source The theory are physically derived If uncorrelated (Section Gaussian the t i e s Requirements 2.4) must gas noise of he but tube's, analog errors resulting analog computer Noise with is and limited larger computer, from finite not the noise then noise with number than i t specified can are sources. that CL)^ c a n bandwidth be the approximately generators"*" the in sources bandwidth bandwidths noise by sources pseudo-random b a n d w i d t h CO ^ the white approximated realizable'. distributions from Gaussian assumed etc. 4 capabili- that caused by In case the be any the of a c PACE 231 R-V analog radians/sec. to be computer. The the computer analog In of the computer, above effect noise of is addition solving time hours. Without special sources To tions that f a i l were in larger than 10 of the capabilities some in many this study, within the the s t a t i s t i c s complete be several commercially bandwidth • C. could requirement. noise-source encountered during problems precautions, this 4.2 requirements, stationary for to.meet Section bandwidth be which overcome bandwidth be limited-bandwidth amplifier the must problem noise a should considered to sources the 60^ available 4 and the s t a b i l i t y l i m i t a - multichannel noise Q source described produces - 5.0 volts, bandwidth Gaussian by stable of in Appendix was developed. discrete-interval binary and has the analog distributed low-pass II f i l t e r i n g an adjustable computing noise the can be binary noise bandwidth elements. This with that noise source levels can exceed the Approximately obtained from 14 noise. I t was this found noise in source the 56 experimental be obtained the step to the in r(t) made study by size size of of noise. One, precisely the and the 4.2C. obtain into to the the grator by of i f scale walks at CO is a extremely small u n t i l be so could good the the use results, compared the that the from change assumptions the noise Two, the discrete the step R. Bandwidths on stochastic size on is Solution infinite-bandwidth noise etc.) the an were due in of to have known nature d i f f e r e n t i a l oscilloscope, small Times and i t analog would 4-1 the Some bandwidths a l l computing are ideal transfer comput- be to insight is elements except function inte- 15 (4.2) - the are extremely rate.. finite Assume Figure an binary d i f f e r e n t i a l equation a r b i t r a r i l y high integrator A l = realizable, stochastic of of monitored region shown measure condition, result f o l l o w i n g , means. T(s) where For small, scaling can limitations source Let is solutions directly. this easily. in the Finite time noise A l . checked (amplifiers the At response size time-scaling obtained Under advantages adjusted of random be Carlo approximated. helpful theory, elements possible are be is the Effect time noise must R. Monte s t a t i s t i c a l properties can scaling In and the since to response small good binary region 2.4 response compared ing a the inherent and equations the the Section Some of using during in however.that bandwidth of the a m p l i f i e r , and Q 57 is a time-scaling factor computer v a r i a b l e (*§-) + fr" T where = CCt x satisfies the computer variable of the response to to choosing the with made The of small. of for whenever are computer equations f o r section. terminating r novel generators in that are the In the reaches (2.27), but reduce that must values equation deviate checking at from several c a n be of the the Hence, to experimentally. experimental results statistics negligible. compromise determined By good small, statistics the equation be equation; solution be made This is solution solutions points, the larg- ascertained. Boundaries An a n a l o g previous be Cl u n t i l CL f o r Detection ential large. differential Ct t e r m must kept F o r the approximate differential derivative CL c a n b e s t partial value 4.3 be closely the (4.3) 1 variable. CL s h o u l d b e increasing obtained est error to stochastic second GL s h o u l d done.by of the minimize time in of x differential 1 scaled-time of effect following assumptions, = B (x,y,z, T)N (T) 1 the Under these the A (x,y,z,T) + is (gain). simulation of random v e c t o r this section, stochastic a boundary only C of Hence, was methods process electronic required. r the a at a stochastic discussed will given r e g i o n R. comparators special be in differthe outlined time t = 0 The methods and diode purpose or given function equipment such 4 as,an oscilloscope mask and a phototube detector is not required. 58 Upon control in the signal the detection c must be i n i t i a l - c o n d i t i o n mode. are fiers in the hold mode. In on C, or terminal point r(0) i controlled or after the is the from the is to held the and a from a the new signals mode-control comparators d i g i t a l f l i p - f l o p c the computer. is shown places c a is is are reversed can be computer or from scheme 4-3 • -3<—* c -=s—• c d i g i t a l computer Triggering of by triggered Control 4-5. value Immediately Tip-Flop Figure r^ terminal Mode- From ampli- conveniently JT From t=0 comparator ampli- point detection OR integrators these boundary- comparators mode- initiated. triggering Figure a l l computer. that analog The in c place while walk and the =0, boundary computer, f l i p - f l o p on c fixed random t track-and-hold the d i g i t a l at to of state, computer, mode-control the reversal this or order Since d i g i t a l mode-control From c, in the electronic pulse boundary to The generated by transferred transfer d i g i t a l from a reversed fiers 0 of Mode-Control Flip-Flop for a the 59 A pulse at input ( l ) terminates a s i m u l a t i o n of the s t o c h a s t i c d i f f e r e n t i a l equations, and a pulse at input s i m u l a t i o n of the equations. (2) i n i t i a t e s a new With t h i s scheme, the problem of d e t e c t i n g boundaries and time t = 0 i s reduced to the problem of e n e r g i z i n g e l e c t r o n i c comparators whenever a boundary i s reached or whenever t = 0 . c from mode-control f l i p - f l o p to OR gate of modecontrol F i g u r e 4-4.- flip-flop D e t e c t i o n of Termination Time t = 0 The use of an e l e c t r o n i c comparator to detect time t = 0 f o r random walks s t a r t i n g at time t A signal c Q i s shown i n F i g u r e i s obtained from the comparator when t = 0 . 4-4. Note that c c o n t r o l s the mode of the i n t e g r a t o r t h a t i s shown i n t h i s figure. Hence, t h i s i n t e g r a t o r i s placed i n the i n i t i a l - c o n d i t i o n mode a t t = 0 or when a boundary i s reached, and i n the compute mode at t = t . o 60 4.3A D e t e c t i o n of Boundaries f o r Problems with One Space Variable Por problems with one space v a r i a b l e x, and at p o i n t s x^^ and x^g- "t n e boundaries boundary d e t e c t i o n comparators are energized by comparing the random v o l t a g e x with v o l t a g e s and x, . 9 (see Pigure x^^ 4-5). from analog c i r c u i t simulating the s t o c h a s t i c d i f f e r e n t i a l equations to of OR gate mode-control flip-flop xb l F i g u r e 4-5. v b2 Boundary D e t e c t i o n f o r Problems with One Variable. When x reaches x ^ or X - ^ J "the mode-control gered by e i t h e r comparator output c^ or c^. flip-flop Space is trig r 61 4.3B D e t e c t i o n of Boundaries f o r Problems with Two Space Variables Consider f i r s t the simple two-dimensional with boundary C as shown i n F i g u r e region R 4-6. Y F i g u r e 4-6• Two-Dimensional Region The boundary of t h i s r e g i o n i s composed of two C-^ = C-^X) curves and Cg = C^CX), each of which i s a s i n g l e - v a l u e d f u n c t i o n of X. A t y p i c a l random walk with instantaneous compon- ents (x,y) i s a l s o shown i n the f i g u r e . It i s c l e a r from F i g u r e 4-6 a boundary whenever that a random walk reaches 62 or This boundary computer by and c (x) y = c,(x) block diagram l detection Cg(x) Figure = comparing C^(x) in y that of criterion the are this (4.4) random set simple on is implemented variable diode boundary y with function on the analog functions generators. detection scheme A is shown 4-7. 2 To OR gate of mode-control f l i p - f l o p Figure Now dividing line single-valued This type considered special of 4-7. Two-Dimensional consider D can be more region of a general constructed functions w i l l previously case a in simple of be Boundary such U measured called which a U was region. region Detection R in that.C^ along simple D, which and (see region. coincident with Cg a are Figure The X,is 4-8), region a 63 Y A F i g u r e 4-,8. Coordinate Transformation used f o r Boundary- D e t e c t i o n of Two-Dimensional Simple The boundaries Regions. of an a r b i t r a r y simple r e g i o n are detected by t r a n s f o r m i n g the random v a r i a b l e s x and y to new v a r i a b l e s u and v f o r which the boundary d e t e c t i o n equations v = C (u) 1 (4.5) and can be used. v = The new C (u) 2 v a r i a b l e s u and v are obtained from x 64 and y by the u transformation = x c o s fj - y sinyCj? - a (4.6) v where to x = x constants detect and y, scheme this of cannot be each the AND a gate, R^ case, than the that boundary of a R signal b defined used region in Figure variables with . is the u and Hence, 4-8. v boundary region is region can above. C defined from be instead of detection, the (X + b a ) the expression. d e t e c t e d by . (Y the dividing or method a l l variable given. region the line more random By with an simple boundaries for an + d c ) When even example, equation 2 two simple leaves a R, Consider, by of the each r which into exit problems mathematical boundaries the o b t a i n e d when the in d e t e c t e d by obtained is R divided and engineering simple given are are • 2 hence many j2 - boundary, the signals and In by R-^, simple combining cribed and c o s ^ complicated regions fouhd, r y 4-7. more regions regions b type Figure simple from a, + respectively, For D siny$ 2 _ n are this simpler an des- is the method e l l i p t i c a l 65 The function f(x, ) = y is generated y, and compared at the boundary. are by with required meters a, b, c Whenever Hence, detect d only this of two type the 4-9- This simple region with a was the horizontal is example vertical axis visible) for distributed two regions. A dot each random walk. on was from by this a a the in is comparator the be a and para- varied simply solution can is be 5.3). d e t e c t i o n methods region exposing by random variable were between the one parameters, photograph photograph at can x walk Since which the circular random produced and region of driven circle random boundary. continuously axis driven of boundary of variables the 1 problems the photograph by = of.Section evident taken random multipliers function v e r s a t i l i t y of proposed the e l l i p t i c a l as (see 2 f(x,y) point, Figure uniformly from some The (not c voltage, easily. walks (y % ) d^ analog handled the + 2 an at display a multipliers and desired been % > b x toll- to adjusting have < the x. shown within an in a oscilloscope variable The started that y and random at boundaries termination^,point points of of the 66 * Figure Photograph 4-9• Detection 4.3C of Illustrating Boundaries for a Detected Problems Boundary with Three Space in Section 4.3B by using a dividing and below the. p l a n e the plane. "Variables The be generalized plane is a such that in not the the of boundary function simple two dividing case, method would of above position mathematical variables plane, however, have regions surface this that special to be used. on expressions define method 13 techniques discussed three-dimensional the which functions below is to single-valued regions the dividing-line is purpose the easy are For known surface to apply. function can for above If and this generation 67 The type of boundaries symmetry described for the region cubic comparators in be with detected two the a 5-6 manner problems. Generation At is In is regions. a single addition, manner for as combining detected by that expression, same ing of the by this (Figure the some methods example, using 3 pairs pair is boundaries example with For used that corresponding of for can ellipsoids, be can boundaries are of r. on in \. out i n i t i a l of x, of a y and single dividing boundary time t = or 0 a is the methods have discussed. the x, the y, and analog with with or values so z r function is are that are used The can are be as expressed detecting conveniently these above known the generated be whenever simple as a functions function in which boundaries, a values components can problems as of boundary multipliers two-dimensional for trigger- constant and from prescribed values The a amplifiers as i n i t i a l and from terminal values available generators they the generators generation For been boundary triggered track-and-hold computer. whenever D of boundary variable. the mode function and/or line that places hold function z terminal Values f l i p - f l o p generated carried the Boundary mode-control in The the instant and the components 0^ I n i t i a l f l i p - f l o p 4-1) voltages of the reached, comparator a Section same the d e t e c t e d by two-dimensional single in be regions dimensions. 4-4 C of three-dimensional often one-and one-dimensional defined can of function the of 68 the variable u defined When t h e analog the computer d i g i t a l along values the 0^ cannot techniques,they computer. dividing can When t h e generation,the components position vector r^ the computer determine value the must d i g i t a l scanned, be However, is read more with terminal are or by the are x, value of d i g i t a l consuming d i g i t a l components y computer is and the and z of table method computer and z analog i t of is the used more to than with slow d i g i t a l generation. to walk one additional function th within used, possible i for terminal since procedure by within stored is Since than conveniently be;generated 0^. equipment x, y other required, this time fast always read; then a some corresponding operations equipment the is or generated d i g i t a l function r(0) be line. store with a S "fc track-and-hold walk. are Thus, i f the s u f f i c i e n t l y d i g i t a l while time is For tion within computer to a patching } a computer procedure wasted between problems the analog gating is them x, y the i and and th z efficient can.be the in the (i d i g i t a l walk simulating very during equipment for is can (i that l ) s l) computer read be + + and the carried out ^ random essentially no walks. in which voltages computer arrangement single analog-to- an amplifier EAI read values generation analog This and conversion fast,the function the walk. ing arrangement must is often d i g i t a l equipped an electronic SPDT switch that be realized. This switch is is be from more read by with By in for this Appendix one loca- d i g i t a l for electronic suitable described the necessary converter. than multiplex- suitably switching purpose III. 9 can 69 4.5 Operations The walk The are terminal generated main average P e r f o r m e d . . b y ...the D i g i t a l function of the values by of the the 0. (or Y.0.) techniques d i g i t a l terminal values Computer that computer and to for each random have been described. is to control compute the the analog comi puter during the The a solution value complete average ° is computer. A completed is t a l l y kept a of the by is typed method, is necessary to - the The are carried and by a computer These out to the logic used for the analog the in ,t ) o o stored within of random walks the A d i g i t a l computer, at operation extremely large because dynamic have been N walks least for range each d i g i t a l that after this which sequence, sum or at a N is the d i g i t a l large required precisely. functions logic the mode-control lines and control multiplexing, performed (flags) logic and other the of d i g i t a l f l i p - f l o p running unit electronic by the (Section from the analog switches and switching computer 4-3) d i g i t a l computer. relays that' > operations on computer. The analog adding, (r computer, and memory lines number by point d i g i t a l through of p a r t i a l for control group are Carlo sum formed each time. the out. 40,000)^an obtain is solving for T to average (1,000 0-. (r , t ) H o o desired ( o r i "Y^fi^) 0^ problem methods complete is computer shown are hybrid in Pigure converted analog-to-digital system to converter for 4-10. implementing Voltage binary-coded of the EAI the levels decimal d i g i t a l Monte on form the by voltmeter. A-D Converter Interface (Digital Voltmeter) hold logic lines Analog Digital Mode- Computer Computer Control Flip-Flop Stepping Motors Driving Potentiometers o Figure 4-10. Hybrid Computer System The interface, the binary-coded the input for the the under register is of of the data initiated, mode-control described control in from f l i p - f l o p . prescribed rate of 100 in of accordance rather slow, Monte but Carlo for each of random set R The the detailed program flow for used diagram, the flow for given Appendix in the a this analog class a the the d i g i t a l signal from interface is is As sent the achieved by driving explained in Appendix to a stepping motor of pulses transmitted. conversion scheme is number digital-to-analog of the starting I, at voltage of the of complete (Figure Carlo a to adequate This for conversion, is points 4-11) system of a methods. computer is terminal values corresponding »t ) . after to the is hybrid In of a ^^0^). (or above to flow by computer terms equivalent 0^ clarified this subroutine A diagram machineis IV. are practicability large by to procedure wiper-arm since Monte hybrid chapter entire "with walks. the program are the diagram the The of transforms compatible computer operation cause adjustment generation The to with operation language in pulses methods only is described, motors. economical, required that analog 71 computer, computer. conversion stepping number form been The d i g i t a l . I. pulses/sec. change the with a the has Digital-to-analog a the d i g i t a l as Appendix potentiometers of information!; to transfer computer .. of computer used of in Monte partial methods the that following Carlo methods differential have been chapter for to solving equations. outlined demonstrate 72 Start Set r and t pote n t i o m e t e r s t o d e s i r i d v a l u e "by- s e n d i n g p u l s e s stepping motors. i a to ' \ Read the v a l u e s of r arid' t have been s e t on t h e analog computer and type out r and that t Q . Place analog computer i n compute mode b y t r i g g e r i n g t h e m o d e - c o n t r o l f l i p - f l o p . R e a d 0. (or y.0.) from the analog c o m p u t e r w h e n the" m o d e - c o n t r o l f l i p - f l o p i s placed i n the hold mode. f Add 0 (or y0) ± sum. ± > No R values •u of /"ide sum R have ' XX ' Yes by partial y.0.) X read. the i (or 0. J been to then 1 output \ Ro The a l l solution has been obtained points (r , t ) desired. at Q Yes Stop Figure 4-11. Flow Diagram for a Typical Hybrid Computer Program 5. 5.1 HYBRID COMPUTER OP ILLUSTRATIVE PROBLEMS Introduction Hybrid erential are to SOLUTIONS computer equations given in this substantiate to that the type results exact with the 5.2 One-Dimensional Carlo of methods. The analytical solutions Monte Three Carlo relationship density examples show, for that the are special of have Carlo been that problems could Boundary-Value between spectral conditions, a partial techniques be put can found were chosen forward be were d i f f - expected also for as chosen so comparison solutions. examples actually of i l l u s t r a t i v e problems indicate Monte number Monte that that Example The by methods the with solved a new from ment of the as is were chapter. well which solutions the the noise Monte exact case in of duration various the given Problems this the of Carlo second, random source. equation section. The f i r s t , demonstrates walks and the second and third parameters solutions The and are in a power boundary close agree- solutions. 1, d ^ _ 2 0 * x d -o 0(-D = - 1 0(+l) 1 2 The stochastic simulated for of (Section type Monte line Carlo C Carlo this one-dimensional 3.3) solutions in. P i g u r e 5-1 • solutions, differential = equation Laplace + that equation must be which is is of To this problem i l l u s t r a t e the numerous solutions are shown a l o n g variance that were of the obtained the ir 1 = 0 = 0 Monte at x Q 7 4 0 i.o 4 -1.0 -.6 -.2 .2 .6 1.0 2 Figure 5-1. Solutions of D, 1 ^ + K P~ d = x o 0. o 75 are l i s t e d in of solutions of this with Table is order only of This useful for source N-^(t). of a is related problem, As walk to the are deviation boundary typical in this values. for set Deviations solutions obtained walks. determining random largest of 2.41$ magnitude random 1,000 The 5-2. is which the the power t r i v i a l power shown starting is in at spectral Appendix x to = x spectral V, and Q density set up, density the is extremely of 2D-^ average through noise duration terminating at 2D^ a x = - equation AV-10. 1 I Since be T(x ), Q for determined. random walks Table 1 Por 2T(o) unit = 100 5-2. this 1 ~ of X , x 1 o 2 = Q is q example at = x = - 2 D f ) value starting l D where any ^o - the 0 was units 72 2 easily measured, average 290 duration ms. Prom T(0) this /sec. volts. 0.21 1.61 0.61 -2.19 0.41 -0.59 0.81 -2.39 1.01 -0.79 -0.98 2.41 2.41 -0.99 -0.59 -1.39 -2.19 -0.79 Values D^ of iqO 0 (O) N obtained with N = 1000.• can of value 1 76 As AV-lOy a values of graph is graph T(x a f o r . D^ in and by measuring prior Figure since to the 5-3. i t complex Average of a = units equipment and equation values and two " s e t s / s e c , was plotted. of measured This 5-3. above is computer 1.72 important T(0), more the the theoretical Figure Since up on comparing ), shown check problem is extremely parameter D^ can often worthwhile to be simple easily run this to set determined problem problems. Time for a Random One-Dimensional Walk Laplace used for Equation. the Solution 77 Example 2, D,1 df0 + Z d0_ TT dx_ dxo = 0(-D A 0 = -1 0(+l) = +1 The s t o c h a s t i c d i f f e r e n t i a l equation f o r t h i s example of Problem C is i f - K = N i ( t ) - S o l u t i o n curves f o r | •"l = 0, 0.5 and 2.0 2 with = 1.72 u n i t / s e c . (from Example 1.) a r e shown i n Pigure .5-1. Example 3. *-§ - ( l dx: 2 x 0 ( - l ) = -1 )0 = 0 0 0(+l) = A T h i s i s an example o f Problem D, S e c t i o n 3.3- The s t o c h a s t i c d i f f e r e n t i a l equation i s If - i<*> H and the r e l a t e d f u n c t i o n a l i s "Y e x P (1 - x ^ ) d t ( 78 79 The integral the noise than 2 Carlo source as computer Laplace's convenient in function Carlo are of shown for at the for problem d e t e c t e d by Two point portion Figure of Q of and 5-5. A = that of 10,000 2 sets since rather 2T>^ of compared Monte -.75, d time x are D^ Monte with direct 5-4. Figure walks. comparing Two differential X 1,000 density by Dimensions position 1,000 A, Figure partial centre each in scaled equation. values in is spectral demonstrates the for expression power three solving centre in the example for the has Equation solutions required were N^(t) solutions potential 0 shown functional i m p l i e d by This The the solutions, analog 5.3 in of y = Q 5-5 0 is the of 2 at the this example with 1 of the and per a Monte solution 2 minutes the (x point* as circle. walks a are region determined inner random methods equations approximately In + y Carlo - was boundaries d) 2 + y 2 2 with (.25) varied 5.4 . simply Poisson's The by centre position adjusting Equation in a d Two equation, ~ \ 2 \ 0 = c region R chosen to (see insert satisfy the in ^Jo 2 Figure Poisson 2 oy = 0 2 condition solved \ 2 + oo boundary ^ }is was Dimensions x with circle potentiometer. \ 2 Poisson's inner 2 + ^b on the boundary C of 2 5-6). equation The so boundary that an condition exact was solution, 80 Figure 5-5. Solutions of Laplace's Boundary Equation Position. as a Function of a 8 1 could be found. solution is however, cannot be choice of boundary independent of the predicted by the shape computer condition of so R. that the exact This, no loss of results. As this this actually generality of For outlined problem in Section is.given Problem 3-3, E, the solution by 0 0(r ) 0 (? ) + = Q 1 Q J" 0 (vt )dt - where 0j[_(^) > o f ° r this Q 2 OO example, is the solution equation Cbx _ y b- with boundary J 0 with o o is i n i t i a l the y, = - £ + - £ C 2 o condition x, 0 (r ,t ) ~ 2 2 o solution on c. d of the heat condition 0 (r ,O) 2 Q (3.35) o = -2 C of equation R. of Laplace's 82 and zero boundary The example conditions stochastic on C of differential R, equations used for are-' ! ? = »2<*> Figure 5-6. Solutions of Equation Poisson's in the Equation Region and Shown. Laplace's this 83 0 @ x =y =.4 Q 0 2 * Monte Carlo Solutions Interpolated 240 Figure Solutions 5-7. of of with of D^ = Dg time, = D. the Heat Poisson's Since the computer Equation = 133) Solution 320 -t used i n the (ms.) c Solution Equation. the function time (1 variable $2^ o'^o^ T t must i he s a f u scaled n c " t i n l 0 n accord- | ance with D. The c o r r e c t scaling i s t = Dt o Monte are shown example, respect 0^ at from a Figure i n Figure is to x- Carlo 5-6. t h e sum o f t Q of = y Q = .4 i s 0^ at 0^ trapezoidal 5-7 solutions is X .44 rule -.2 7 . q of 0(r ) along Q The s o l u t i o n 0 at at .4 = y . X Q q = y = The = Q As .4. Hence, 0 at X of q X the line q = y Q q of 0g at = .4 is X of q y Q with 5-6, = y 0g = f o r .4, i n Figure the values = y = Q X and the i n t e g r a l given integral integration . c Q = given .4, i n 84 .44 - .27 Pigure = • .17 This value is one of the values walks and plotted in 5-6. For walks were These values, ance with time for 5.5 Heat this problem, simulated N the each = for each and 1,000 analysis of value 0(r ) Equation of in Solutions value L = One, was the Two of and 0^, The respectively. total approximately Three random 133 determined C. 3.5 and heat 0^ were 133, Section Q of random 1,000 in accord- solution minutes. 12 Dimensions equation with 0 i n i t i a l (r, ) = conditions at +1, the 0 (r ) o Q centre of = a -1, and line, a boundary square conditions and a cubic region C D are of D shown in Figure Problem A, = Section units 1.72 comparators important to reach of the to to a in and In using the that three were 3.2, detect boundary problem. established /sec. note The 5-8. the problems, solved two, four boundaries. average using or For time significantly a l l T(0) Appendix cases V. f a l l s noise six these T(0) decreases which for with within are examples sources with electronic problems,it a random the the is walk dimensionbounds 85 Figure 5-8. Solutions a of Line, the a Heat Square Equation and a at Cubic the Centre Region. of 86 5•6 Laplace's Equation in Three Dimensions 2 The in z the cubic - 1. = c ( b ? are is ( x shown satisfy is of region bounded by planes Carlo solutions b " in Figure the known b z } + ( a l l x b " z 5-9. Laplace for y b> detect used for to equation , y o' o and For this the boundaries, generate each 5.7 point close were set up the 0 of obtained the " y boundary so line x = = Q 1, y Q 0, and = Z x q for the that b b z + x b b z c o n d i t i o n was the exact chosen analytical to solution z . o six and (r^). e l e c t r o n i c comparators quarter-square Approximately were multipliers 5 minutes were used were required in Results this with a given study, exact and the in many Monte solutions. other Carlo In a l l s t r a i g h t - f o r w a r d manner examples solutions cases, without were good the that in results need of adjustments. For-most gave average example, examples during agreement c r i t i c a l walks y 0 = solution. Discussion In were equation, = - 1, x along V t + The J to Laplace's condition = } example Monte boundary 0 f i n a l results of about time with a fast d i g i t a l fast point solutions satisfactory 5 minutes analog computer was for be was (20 found verifying required computer could i t mc reduced for that the each methods. solution. bandwidth) to about 1,000 1 coupled sec*;. . random An This to a 87 0 .8 .6 ) x\ .4 [\ : / .2 1—JS -1.0 -.8 -.6 * 0 .2 .6 .4 .8 Monte Carlo Solutions (N = 1000) o Monte Carlo Solutions (N= = 2000) — Figure -.2 - . 4 Analytical Solutions 5-9. 1.0 x o~ o~ o y Solution of Laplace's Equation in Three Dimensions. i Even with slow can computers, few points be for finite-difference obtained finite-difference obtained values, unique about solutions methods, ease demonstrated position in Monte on the a however, Carlo same fast solutions time that d i g i t a l solutions at at is a required computer. many points With are simultaneously. The was however, and can in shape be feature with which the of boundary example regions, of as Section well altered very easily, of Carlo the Monte positions i t 5.3. can Since as boundary is suggested methods could be be changed ' the and that used i n i t i a l this to z 88 advantage solution in of value must point could computer, grid and boundary engineering a be be design found solving or problem to solved however, give boundary a For in a which This require complete value. example, a a boundary particular easily. would for design. Monte or of problem setting up a set of boundary potential at type new potentials Carlo on a specified a d i g i t a l finite-difference for each t r i a l 89 CONCLUSIONS 6. Monte approximate and Carlo solutions homogeneous equations e l l i p t i c solved of a to much more Monte have partial general treated in Carlo tested. techniques use the computer as dynamic of range of program, and boundary values On the example about cases, the a solutions. does upon be the not advantage well class report been as of homogeneous c a n now 4 proposed be the memory are and for and high-speed boundaries, Hence, techniques Problems system random walks fast hybrid were maximum for the the hybrid simulated Thus, parallel and easy i n i t i a l to and i n system about i n i t i a l 1 or be used however, sec. In 1,000 walks, to solve simulated boundary random engineering was could obtained with w i t h 1,000 many that 1,000 nearly random value of solutions problems are in a l l walks the with obtained time. the in a that the accuracy obtained point or of reasonable 1,000 With have e l l i p t i c , equations. computer computer. obtaining modified. PACE-A1WAC could w i t h i n 5$ In are the to parameters, easily solutions sufficient in are methods d i g i t a l equation 5 minutes. walks exact the problems, random were analog than Hybrid for nonhomogeneous Michigan the operation and form implementing The Carlo developed differential the methods. Monte been homogeneous parabolic equations by methods methods a have been developed, p o i n t - b y - p o i n t manner. depend total that upon number of the solutions solutions The at that the solution solutions at neighboring are obtained. one points Por 90 this reason the that require many points methods solutions are are at required, particularly well only a few points. suited If to problems solutions f i n i t e - d i f f e r e n c e methods are at more efficient. The Monte require only methods for a analog large Carlo a f a c i l i t i e s methods. small solving methods Carlo or a that where i t methods hybrid that computer have whereas been proposed finite-difference p a r t i a l d i f f e r e n t i a l equations large have d i g i t a l been would not computer. developed be seem possible to require Hence, ideal the for employ either Monte small other hybrid computing 91 APPENDIX INTERFACE FOR TRANSFER AND A from block t h e PACE OF DATA BETWEEN T H E P A C E THE ALWAC diagram t o t h e ALWAC i s (DVM) o f t h e PACE version. The f l i p - f l o p s f l i p - f l o p s shown i s that o f t h e ALWAC f o r transfer i n Figure used AI-1. of i n the figure are normally data The d i g i t a l f o r analog-to-digital a r e shown that R-V 231 III-E* of the interface voltmeter input I con- are the set from the flexowriter. The value PACE t o t h e ALWAC led, normally ALWAC the application the puts a signal This sign a g 1 0 or l ) next * l ' s of the analog The s i g n g which (8). and each allows i s then supplied. from t o t h e ALWAC This i s digit as follows. the sign allows a About plus voltage decimal f l i p - f l o p s transferred to enter 5-digit allows sign binary- available are has been detailed read. After description at transferred T h e ALWAC accumulator. t h e 10,000's 1,000's The data and the process value. out- t h e DVM t o e n t e r the binary-coded F F 1 , F F 2 , FF3 a n d FF4• signal- 30 m s . a f t e r i s a l l digits i s FF4. The digit F F 1 on i t s way t o t h e accumulator. which from t h e i s t o read a then F o r a more f l i p - f l o p , signal i s digit T h e ALWAC of the hold f e r r e d iro" t h e " a c c u m u l a t o r , the manner. t o t h e DVM. t o t h e ALWAC f l i p - f l o p s transferred signal equivalent outputs enter a i s "hold" DVM o u t p u t . signal i n the following supplies sequentially voltage v i a the mode-control The coded-decimal of an analog (either T h e ALWAC digit then continued to trans- until o f t h e DVM h a v e of the interface, see reference ^sf F l e x o w r i t e r A I D ] — b. Sign J g 10' AND 8 2l HAND 1 — c OR FFI 1 z Am 4 102 i '1 d g 92 AND ggj F l e x o w r i t e r -—j 1 g 8 Analog Input HAND I— d OR FF2 OR FF? OR F F 4 z g 4 <AND I—• d, IL 10' AND 2 11 1 AND l. Flexowriter l 41 Hold 8 AND 4 1 AND. 4 to g 2 g i l AND. 4_1 AID 1. Flexowriter 1 5 1 8- 15_L 4- AND g 2 5 1 AND g 1- 51 AND Digital "Voltmeter Figure AI-1. Interface b, AND for l 4 Interface x Transfer ALWAC x of Data ALWAC Between III-E PACE and 93 been read from the into the ALWAC. accumulator, The entire the "hold" reading is released by a operation requires about signal 10 ms. The must be held registered by the at the conveniently led analog by an is by a rotation 15° rotation. 12-to-l has voltage this of The on on volts the a scheme, while a pulse are gears. i t , arm 100 by can u n t i l ms.). This the ALWAC motors. from input at coupled the to be 144 pulses An example a 20 volts sent pulses/sec. to is a ALWAC the DVM has is .the accomplished that to the is PACE stepping input motor are a 10-turn causes shown in stepping in the a -15° through potentiometer required program through causes potentiometers a control- motors instructions stepping other of the 4-10), The dummy of to circuit Figure Therefore,.if arm. pulses approximately stepping one wiper least (see from originating across transferred track-and-hold at wiper at f l i p - f l o p by motors is (^30 pulse reduction - 100 change single value transferred pulses A + analog driven ALWAC. that number mode-control potentiometers driven constant correct Data are a voltage for to 10-volt change Figure motor a at the AI-2. a rate By 94 P l a c e t h e Number 288 i n the E-Register Dummy (Send a Instruction Pulse Decrease E E>0 to Number by AI-2. in 1 Compare E Figure Motor) Instructions for = 0 Activating Stepping Motor 95 APPENDIX MULTICHANNEL DISCRETE-INTERVAL Numerous quired for 3-channel AII-1. 0 "k" Monte The —*- Schmitt 1 state applied cyclically If f , the is essentially For output to the zero levels 0 A is E ( T ) = E the pulse AND gate from 2 | T I ^> volts, is an the rate N^(t) an shown ring of f of re- economical in average are function are Figure rate of of the counter lowis pulses/sec. c essentially each channel ^ c the (1 - f a and 2 of zero-crossings at N (t) at SOURCE* npise diagram properties autocorrelation for - block by N-^t), wide-band triggered sharp each outputs and A these trigger source. Q uncorrelated with BINARY-NOISE stable, changes/sec. noise » of methods. source quality k channels Carlo noise II autocorrelation \T\ ) function \T\ <i is ^ c = The power spectral correlation 0 |T| density function cj? ( C d ) * For (9) a more (GJ) = 2f E detailed to -± c this (AII.l) auto- is 1 Cp corresponding > 2 - c analysis COS , (<£—) , c (All.2) CO 2 of this noise source see reference Lowqualitynoise source N-^t) Schmitt Trigger Clock of requency F l i p Flop 3 AND FlipFlop Level Shifterl AND FlipFlop Level Shifter F l i p Flop Level Shifter stage Ring _N^(t) Counter 3f AND VO Figure AII-1. Block Diagram of 3-Channel Noise Source. 97 The obtained with Monte k = Carlo .4 solutions mc/sec, f = given in 20kc/sec. Chapter 5 were and 5 volts. E = c With width these of b i l i t i e s values the of noise the the criterion channels analog is k ^> greater computer. f is than met, the and the hand- bandwidth capa- 98 APPENDIX AN By with The suitably electronic required plugs as feedback switching, in capacitor on mode-control the c 0 volts, In = this mode - Y-^ Q u t V-J-Q switch = - = + from t o - V-j-Q i n 1 0 0 a SWITCH PACE fast 231 SPDT AIII-1. a 1 T-^ a n d switch by can be placement equipped realized. of bottle replaces ohm resistor R - V j ^ and When c = + so that V conduct amplifier patching ; M c. R-V This between signal gate SPDT accomplished with transistor V a switched electronic For ^out be C V and to is Pigure output the patching patching shown ^ ELECTRONIC III the - and V-^ 5 volts, ^. = electronic - allows under the control transistor VJQ. gate the T^ When are open. V^. 100 - volts V-^ jjisec. to and - V-^ Vj = - in 160 N 100 volts,the jjisec. and output from 100K -AA/VV IC lOOK IC PS O put O Coil Q Coil \ a • 1 / 1 / • F W W 1 a 0 meg f r o m mode control circuitry - c o n n e c t i o n s made by b o t t l e plugs r e p l a c e C by R by p a t c h i n g as shown Figure AIII-1. Circuit and Patching for a SPDT Switch 100 APPENDIX A PROGRAM An similar to Section 4.5 b4 POR ALWAC those is I M P L E M E N T I N G MONTE C A R L O III-E program indicated given IV in that the carries flow METHODS.. out diagram operations of Pigure 4-11, below: 1 00 83b5 5 7 0 f 80 01 4917 fffO 81 02 dfOO d903 82 03 0001 0000 83 04 ffaO 1704 84 05| f 9 e 0 f9eO 85 06 dlOc dfda 86 07 03e8 0000 87 08 5703 118c 88 09 fie 5 fffO 89 Oa lb08 2800 8a ob 0000 0013 8b Oc, 5 7 0 5 2800 8c 0d| f f e O 1320 8d oe 6d8b 2 4 0 0 |8e of 0090 0000 8f 10 4913 4 9 1 7 90 11 4913 1 7 1 4 91 12 4d8b 1 9 8 0 |92 13 0 0 0 0 0 0 0 0 9 3 14 f9e0 fffO 94 15 6117 95 16 1116 0 0 0 0 |96 17 18 7913 fffO 98 19 e b l b 3 2 0 0 9 9 l a 0000 0 0 0 0 |9a l b |05f5 e l O O 9 b IC 6117 fffO 9c I d 0 0 0 0 |9e |oooo OeOO d580 f 5 c 8 |9d l e jOOOO If loooo 0000 97 0000 9f 8fb649be Immediately of Of) are multiplex sent the These the total of are numbers out. motor,and a r 19 #l) is Q 07) upon added have motor allows i t are then signals been is initiated, read, to 144 process times is stepping of Another the program (flag computer numbers 1,000 typed after (contents analog the to signal Immediately numbers after a for is typed read pulses the then repeated. The (contents of 8b). a T Q (contents of r to be as A read. thousand fixed terminal they are to process the is of f l i p - f l o p . read. together^the sent . One mode-control added are of out. from p a r t i a l sum and pulses adjustment the ; value from read 144 sum After is stepping repeated a 101 APPENDIX V AVERAGE DURATION OP RANDOM WALKS In t h i s appendix a p a r t i a l d i f f e r e n t i a l equation i s d e r i v e d f o r the average time T '(r ) that i s r e q u i r e d f o r a random walk s t a r t i n g a t r time. age The equation Q t o reach a boundary f o r the f i r s t i s solved f o r s p e c i a l cases t o give the aver- d u r a t i o n o f a random walk t h a t i s used f o r the s o l u t i o n of Laplace's equation i n a one, a two and a three-dimensional ized s p h e r i c a l r e g i o n . general- The approach that i s used i s s i m i l a r t o , but not as i n v o l v e d as, the method of Wasow f o r c a l c u l a t i n g the 1 fi mean d u r a t i o n o f d i s c r e t e random walks. From the d e f i n i t i o n of g C r ^ t ^ | r , t ) and from o Chapman-Kolmogorov equation J^vM vV^b = C Q (2.2) i t f o l l o w s that yy^'SlA'V^b^i^il vV i d r E C (AV.l) i s the p r o b a b i l i t y d e n s i t y f o r a random walk t o reach a boundary f o r the f i r s t time a t t, i f i t s t a r t e d a t ( r , t ). The b o o average d u r a t i o n of a random walk s t a r t i n g a t ( r , t ) i s t h e r e o f o r e g i v e n by -©o Q dr, dt, b b oo oo ( t R -oo b - C Vfz w\ I ^l^i^W^i^i I { vV^i C (AV.2) 102 OO = JJ(\ R J ~V - o o «< Jg(? ,t | -t ) b Q 5 b l f IV V d r b d V ^ 1 ' % I t )dr dt f(r .,t | 1 b b 1 1 R (AV..3) Therefore, T ( r , t ) = JH\,\WTV\ o \ ? ,t )d o 0 0 r i R - t ) j + f Q ^ r ^ d r , (AV.4) R The l a s t term f o l l o w s from the f a c t that oo (AV.5) - oo c f o r random walks that are c e r t a i n t o terminate at a boundary. Now l e t t-, = t 1 a T a y l o r s e r i e s about r Chapter 2. Q o + A t and expand T ( r , , t + A t ) i n 1' o i n the same manner that was done i n I f t h i s i s done and equation (2,9) and the l i m i t s (2.11) to (2.21) are used, i t f o l l o w s that 6t (AY.6) r Q o ^ o ? o' o t ) d r 103 I f the operator L- ^ i s independent of t , then o' o Q T ( r , t ) i s a l s o independent of t . o Q For t h i s case T ( r ,t ) can be denoted by T ( r ) and L- T ( r ) + 1 = 0 o The (AV.7) boundary c o n d i t i o n f o r T ( r ) i s T ( r ^ ) = 0 Q I f Lof Laplace's o i s the operator that i s used f o r t h e . s o l u t i o n equation,then D y T ( ? ) +,1 2 Q = 0 (AV.8) For an n - d i m e n s i o n a l j g e n e r a l i z e d depends only upon r D r 1 n-1 o Q dr = |r | sphere of r a d i u s "a", T ( r ) o , therefore, Q r^dTC^) d r + 1 = 0 o T(a) = 0 (AV.9) i The'solution of the problem given by a 2 - r 2 T h i s r e s u l t shows e x p l i c i t l y how the d u r a t i o n of a random walk depends upon the s t a r t i n g r a d i u s r sphere. By e n c l o s i n g any (AV.9) .is Q and the dimension of the other shape of r e g i o n with a g e n e r a l - i z e d s p h e r i c a l region,an upper bound on the average d u r a t i o n of 104 a random walk can be obtained. A lower bound can be obtained by e n c l o s i n g a g e n e r a l i z e d s p h e r i c a l r e g i o n by the r e g i o n f o r which the lower bound i s d e s i r e d . For example, the average d u r a t i o n T(0) of a random walk s t a r t i n g at the centre of a square r e g i o n w i t h s i d e s 2a i s (AV.ll) The average d u r a t i o n T(0) of a random walk s t a r t i n g at the centre of a cubic r e g i o n with edges 2a i s h < T ( 0 ) < % (AV.12) 105 REFERENCES F o r s y t h e , G . E . , and Wasow, W.R., F i n i t e - D i f f e r e n c e M e t h o d s f o r P a r t i a l D i f f e r e n t i a l . E q u a t i o n s . John.. W i l e y a n d S o n s I n c . , New Y o r k , I960. C u r t i s s , T . J . H . , "Sampling Methods A p p l i e d to D i f f e r e n t i a l and D i f f e r e n c e E q u a t i o n s " , P r o c . Seminar on S c i e n t i f i c C o m p u t a t i o n , I n t e r n a t i o n a l B u s i n e s s M a c h i n e s C o r p . , New Y o r k , N . Y . , November 1949. - 1 M e y e r , H e r b e r t A . , E d i t o r , Symposium., on M o n t e . - C a r l o . M e t h o d s , J o h n W i l e y a n d S o n s I n c . , New Y o r k , 1956... Chuang, K., K a z d a , I.F., and Windeknecht, T., "A S t o c h a s t i c Method of S o l v i n g P a r t i a l Differential. Equations using an E l e c t r o n i c Analog Computer", P r o j e c t M i c h i g a n R e p o r t 2900-91-T. W i l l o w Run l a b o r a t o r i e s , U n i v e r s i t y of M i c h i g a n , June I960. MacKay, D.M., and F i s h e r , U l t r a - H i g h Speed. Chapter I n c . , New Y o r k , 1962. M.E., Analogue 16, John W i l e y Karplus, Walter J . , Analog Simulation, B o o k C o m p a n y , I n c . , New Y o r k , 1958. Computing and Sons McGraw at . H i l l Middleton, David, S t a t i s t i c a l Communication Theory, C h a p t e r s 1 and 10, McGraw H i l l Book Company, Inc., New Y o r k , I960. Soudack, A . C , and L i t t l e , W.D.,]"An E c o n o m i c a l H y b r i d i z i n g Scheme f o r A p p l y i n g Monte C a r l o M e t h o d s the S o l u t i o n of P a r t i a l D i f f e r e n t i a l Equations", S i m u l a t i o n , V o l . 5, N o . 1, pp. 9 - 1 1 , J u l y , 1965. Kohne, H. , L i t t l e , Multichannel Noise November, 1965- W.D., Soudack, A . C , Source", Simulation. to "An Economical V o l . 5, N o . 8, Bharucha-Reid, A.T., "Elements of the Theory of Markov P r o c e s s e s a n d t h e i r A p p l i c a t i o n s , C h a p t e r 3, M c G r a w H i l l B o o k C o m p a n y , I n c . , New Y o r k , I960. 1 Wang, M i n g C h e n , and U h l e n b e c k , G . E . , "On t h e T h e o r y of Brownian Motion II", Reviews of Modern..Physics. V o l . 1 7 , N o s . 2 a n d 3, p p . 3 2 3 - 3 4 2 , A p r i l - J u l y 1945. D a r l i n g , D.A., and S i e g e r t , A . J . , "A S y s t e m a t i c A p p r o a c h to a C l a s s of Problems i n the Theory of Noise and Other R a n d o m P h e n o m e n a , P a r t I", IRE T r a n s , on Information T h e o r y . V o l . I T - 3 , p p . 3 2 -37, M a r c h , 1957. 106 W i l k i n s o n , R.H., "A M e t h o d o f G e n e r a t i n g F u n c t i o n s o f Several V a r i a b l e s using Analog Diode L o g i c " , IEEE T r a n s . On E l e c t r o n i c Computers. V o l . EC-12, pp. 112129, A p r i l , 1963. Hampton, R . L . T . , "A H y b r i d A n a l o g - D i g i t a l N o i s e G e n e r a t o r " , S i m u l a t i o n . V o l . 4 , No.. 185, March, 1965. Pseudo 3, pp. Random 179- T o m o v i c , R., and K a r p l u s , W., H i g h - s p e e d A n a l o g C o m p u t e r s , C h a p t e r 5, J o h n W i l e y a n d S o n s Inc.., New York, 1962. Wasow, W o l f g a n g , "On t h e Mean D u r a t i o n o f Random W a l k s " , Journal of Research of the National Bureau of Standards. V o l . 46, No. 6, p p . 462 - 4 7 1 , J u n e , 1 9 5 1 . Addendum Since the p r e p a r a t i o n of t h i s t h e s i s , the f o l l o w i n g hooks have been brought to the author's a t t e n t i o n : Dynkin, E.B.. Markov Processes. V o l . I and V o l . I I , Academic Press I n c . P u b l i s h e r s . , New York, 1965. These books c o n t a i n an extensive treatment processes. of Markov I n p a r t i c u l a r , Chapter 13 of Volume I I has a t h e o r e t i c a l d i s c u s s i o n of problems s i m i l a r to those d i s c u s s e d i n S e c t i o n 3.3 of t h i s thesis.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Hybrid computer solutions of partial differential equations...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Hybrid computer solutions of partial differential equations by Monte Carlo methods Little, Warren David 1965
pdf
Page Metadata
Item Metadata
Title | Hybrid computer solutions of partial differential equations by Monte Carlo methods |
Creator |
Little, Warren David |
Publisher | University of British Columbia |
Date Issued | 1965 |
Description | A continuous Markov process is examined for the purpose of developing Monte Carlo methods for solving partial differential equations. Backward Kolmogorov equations for conditional probability density functions and more general equations satisfied by auxiliary probability density functions are derived. From these equations and the initial and boundary conditions that the density functions satisfy, it is shown that solutions of partial differential equations at an interior point of a region can be written as the expected value of randomly-selected initial and boundary values. From these results, Monte Carlo methods for solving homogeneous and nonhomogeneous elliptic, and homogeneous parabolic partial differential equations are proposed. Hybrid computer techniques for mechanizing the Monte Carlo methods are given. The Markov process is simulated on the analog computer and the digital computer is used to control the analog computer and to form the required averages. Methods for detecting the boundaries of regions using analog function generators and electronic comparators are proposed. Monte Carlo solutions are obtained on a hybrid system consisting of a PACE 231 R-V analog computer and an ALWAC III-E digital computer. The interface for the two computers and a multichannel discrete-interval binary-noise source are described. With this equipment, solutions having a small variance are obtained at a rate of approximately five minutes per solution. Example solutions are given for Laplace's equation in two and three dimensions, Poisson's equation in two dimensions and the heat equation in one, two and three dimensions. |
Subject |
Differential equations, Partial |
Genre |
Thesis/Dissertation |
Type |
Text |
Language | eng |
Date Available | 2011-09-20 |
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. |
DOI | 10.14288/1.0104848 |
URI | http://hdl.handle.net/2429/37501 |
Degree |
Doctor of Philosophy - PhD |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-UBC_1965_A1 L5.pdf [ 4.93MB ]
- Metadata
- JSON: 831-1.0104848.json
- JSON-LD: 831-1.0104848-ld.json
- RDF/XML (Pretty): 831-1.0104848-rdf.xml
- RDF/JSON: 831-1.0104848-rdf.json
- Turtle: 831-1.0104848-turtle.txt
- N-Triples: 831-1.0104848-rdf-ntriples.txt
- Original Record: 831-1.0104848-source.json
- Full Text
- 831-1.0104848-fulltext.txt
- Citation
- 831-1.0104848.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-0104848/manifest