• No results found

Asymptotic survival probability of random walks on a semi-infinite line

N/A
N/A
Protected

Academic year: 2022

Share "Asymptotic survival probability of random walks on a semi-infinite line"

Copied!
8
0
0

Loading.... (view fulltext now)

Full text

(1)

Asymptotic survival probability of random walks on a semi-infinite line

K P N M U R T H Y

Reactor Engineering and Design Group, Reactor Research Centre, Kalpakkam 603 102, India

MS received 8 April 1985; revised I7 June 1985

Abstract. Symmetric and asymmetric random walks on a segment ( - ~ , T > O) of the real line are considered. There is a non-zero probability for the random walk to get absorbed at a site it visits. We derive for such random walks, expressions for survival probabilities in the asymptotic limit of T--* ~ . An application of this asymptotic formulation to the problem of radiation transport through thick shields is presented.

Keywords. Random walks; first passage time; diffusion; Monte-Carlo simulation; radiation transport; variance reduction techniques.

PACS No. 02-50, 05-60, 28-20.

1. Introduction

We consider r a n d o m walks on the real line extending f r o m X = - o0 to T > 0. T h e r a n d o m walk starts at origin with probability unity a n d terminates either by a b s o r p t i o n at a site it visits or by crossing or reaching the barrier set at X = T. T h e p r o b a b i l i t y o f a b s o r p t i o n at a site is I - C. Let L be a r a n d o m variable called leakage that assigns a real n u m b e r to each r a n d o m walk. L = 1 if the r a n d o m walk survives a n d crosses the barrier a n d L = 0, otherwise. The p u r p o s e o f the paper is to obtain expressions for the m o m e n t s o f leakage in the asymptotic limit o f T--* oo.

We present in § 2 a general formulation to obtain a s y m p t o t i c m o m e n t s o f leakage using Wald identity. We illustrate the formulation by considering gaussian a n d exponential r a n d o m walks. These are presented in §§ 3 a n d 4. Exponential r a n d o m walk has a n i m p o r t a n t application in M o n t e - C a r l o simulation o f radiation t r a n s p o r t in shields, a n d this is presented in § 5. T h e principal conclusions o f this w o r k are b r o u g h t out in §6.

2. G e n e r a l f o r m u l a t i o n

In the present formulation, we prevent the r a n d o m walk f r o m getting a b s o r b e d at a site.

Thus, the r a n d o m walk gets terminated only by crossing the barrier. T h e effect o f a b s o r p t i o n on leakage is suitably taken care o f by a redefinition o f the r a n d o m variable L.

Let us d e n o t e by A the set o f all possible r a n d o m walks on ( - ~ , T ) line, with their 231

(2)

starting point at origin and with C = 1, implying n o absorption. A r a n d o m walk belonging to A is defined by

X . = X . _ t + x ; X 0 = 0 , (1)

where X . is the position o f the r a n d o m walk after n steps, x is r a n d o m displacement with a probability density, formally denoted by f ( x ) . Let # be the mean o f x. The moment-generating function o f x is defined as,

f'?

re(O) = exp(Ox)f(x) dx. (2)

We restrict our attention to r a n d o m walks with p ~> 0, and thus are assured that every r a n d o m walk belonging to A will cross the barrier with probability unity (Gambler's ruin; see Bartlett 1966).

Let us define a r a n d o m variable N, over the set A as the n u m b e r o f steps the random walk takes to cross the barrier. In other words, N is the 'first passage time' defined as the m i n i m u m value o f n such that X . ~> T. Let ~ ( N ) denote the probability density o f N.

N o t e that i f / ~ / > 0, ~ ( N ) is well defined and for /~ = 0 all the m o m e n t s o f N are u n b o u n d e d .

T o get the m o m e n t s o f leakage using the space o f r a n d o m walks, we redefine leakage as a r a n d o m variable that assigns to each member o f A a real n u m b e r C N -J. Note that there are N - 1 collisions in an N step r a n d o m walk. Thus, the K t h m o m e n t o f leakage is formally given by

( L K ) = C -~ ~ CrNdp(N). (3)

N f f i l

T o obtain analytical expressions for ( L r ) we start with Wald identity (Bartlett 1966) given by

(exp(OXN) {m(0)}-N ) = 1, (4)

where the angular bracket denotes an average over A. T h e above identity is valid, in general, for values o f 0 for which Im(O)l >1 1.

However for r a n d o m walks on the real line segment with left b o u n d a r y at - ~ , considered in this paper, the identity holds good when the real part o f 0 is non-negative.

Besides we shall impose the conditions (Bartlett 1966) that re(O) exists for all real 0 and m(O) ~ oo as 0 ~ + ~ . It is clear from equation (2) that m"(O) > 0 for all real 0, where the dashes denote differentiation with respect to 0. Hence the condition above implies that m(O) has only one minimum at, say 0.,. If/~ = 0 then 0m = 0. But if/~ =/: 0 then 0m 0 and m(O.,) < m(O = 0) = 1. It follows that the equation m(O) = e with e > m(Om) has two real roots and only one o f these is positive when e > 1.

Let us consider the asymptotic limit o f T - - , oo, under which the identity given by (4) can be approximated as follows. Equation (4) can be explicitly written as

I ~ dXNexp(OXN){m(O)}-Ntp(XN, N ) , (5)

N = I . T

where ~P (XN, N ) dXN is the joint probability that the r a n d o m walker is between XN and X N + d X N after N steps. Since N is first passage time, XN >1 T. If the r a n d o m walker executes jumps, each o f small size as compared to T (i.e. if p and a o f the r a n d o m

(3)

variable x is small compared to T ) then we can consider XN and N to be independent o f each other and (5) can be written as

I °° dXNexp(OXN){m(O)}-NrI(XN)dP(N)=

1, (6)

N ~ I ~ T

where tl)(N ) is the first passage time probability density a n d r/(XN ) is the probability density o f XN. Indeed, if the j u m p sizes are small, XN is most likely to be nearly T, for every random walk (Bartlett 1966) and r/(Xu ) can be approximated to a one-sided delta function

~ ( X N ) ~

6(XN-T)

X N >~T

= 0 XN < T.

(7)

Substituting the above in (6) and carrying out the integration over XN, keeping track o f normalization, we get

{m(O)}-Ndp(N)

= e x p ( - 0T). (8)

N = I

Consider now the following equation

re(O)

= C-K, (9)

which defines 0 as a function o f C (and K). For particular values o f C (0 < C < 1) and K (K = 1, 2 . . . . ), there is only one positive real value o f 0 that satisfies (9), as explained earlier. Let us denote this root by 0~. w e multiply both sides o f (8) by

6(m(O) - C -~)

and integrate over 0 from 0 to ~ . Then, comparing the resulting equation with (3) we get

( L K ) = C -r ~ cKNCp(N)=exp(--OIT)C -K

(10)

N ~ I

which is the required asymptotic expression for the K t h m o m e n t o f leakage.

To obtain the first passage time density (I)(N) we first set

re(O)

= exp(S). (11)

We select 01 (S), the positive root of the above equation and obtain, following the same procedure described earlier,

~ e x p ( - S N ) ~ ( N ) = e x p [ - 0 1 ( S ) T ] . (12)

N = I

Replacing the summation in the above by integration over N from 0 to ~ , we see that

~( N ) can be formally expressed as

• ( N ) = .L~'-' [exp{

-O,(S)T}],

(13)

where .LP-~ denotes inverse Laplace transform operator and S is the transform variable.

In what follows, we consider specific cases ofgaussian and exponential random walks and derive explicitly asymptotic expressions for the moments o f leakage.

(4)

3. Gaussian random walks

Craussian r a n d o m walks provide a useful model in the study o f diffusion phenomena.

T h e moment-generating function for a gaussian o f mean p and variance cv 2 is given by

re(O) = exp{p0 + tr202/2}. (14)

Substituting the above in (6) we get a quadratic equation in 0, whose roots are 01.2 = a - 2 [ - i t + (itz - 2 K~ 2 In C01/2]. (15) O f the two roots, we select 01 as explained earlier. T h e n f r o m (10) we get the desired asymptotic b e h a v i o u r o f the moments o f leakage as

( L K ) = exp{ [ # T - - T ( I t 2 - 2Kcr 2 tn C) I/2]/a2}/C ~c. (16) Let us now set m(O) = exp(S), then we can o b t a i n the first passage time density as

* ( N ) = .W -1 [exp

{ (itT-

T (itz + 2aeS)l/2)/tr 2 } ]

= T N - 3/2 exp { - ( T - I t S )2/2aZN }/a x/2n. (17) In the above if we set It = 0, we get the first passage time density for symmetric walks and for this case it is easily verified that all m o m e n t s o f N are unbounded.

4. Exponential random walks

Symmetric exponential r a n d o m walks provide a model for radiation transport in a medium with isotropic scatterers. These r a n d o m walks are generated by the following density

f ( x ) = exp{ - I x l }/2. (18)

We shall introduce a right bias to the above symmetric density, the reasons for which would become clear in § 5. There are many ways o f introducing the right bias and we consider here a specific case o f asymmetric exponential walks generated by the density given below

( 1 - b 2 ) e x p { - ( 1 - b ) x } / 2 x >10

g ( b , x ) = ( 1 - b 2 ) e x p { + ( l + b ) x } / 2 x < 0 . (19) In the above, b is a parameter that can take a value between zero and unity. It is clear that when b = O, g(b, x) reduces t o f ( x ) given by (18). We shall derive in this section results for the asymmetric exponential r a n d o m walks and obtain the corresponding results for the symmetric case by setting b = 0.

T h e mean o f displacement x is given by

It = 2 b / ( l - b 2 ) . (20)

It is seen from the above that as b ~ 0,/~ -~ 0 (symmetric case) and as b --, 1, It ~ ~ . Therefore, for b near unity, the asymptotic approximation made in § 2 is not valid.

The moment-generating function o f x is given by

m(O) = (1 - b 2 ) / { 1 - (b + 0) 2 }. (21)

(5)

Substituting the a b o v e in (9) and solving the resulting quadratic equation in O, we get the two roots as

01, 2 = - b + [1 - C ~ ( 1 - b 2 ) ] 1/2. (22)

As explained earlier, we select the root 01, and substitute this in (10), to get

( L K ) = exp

{ b T -

T [ 1 -

C K

(1 - b2)] '/2

}/C K.

(23) The above gives exact m o m e n t s for b <~ 1.

If we set b = 0 , we get the asymptotic moments o f leakage for the symmetric exponential r a n d o m walks. We give below the expressions for the mean Pc and variance a2L o f leakage, for the symmetric case, since we shall require them in § 5.

PL = ( L ) = exp { --T(1 - C) 1/2 }/C, (24)

a2L = ( L 2 ) -- ( L ) 2 = { e x p [ - - T ( l - C 2 ) 1/2"]

- - e x p [ -- 2T(1 - C ) 1/2 ]

}/C 2.

(25)

5. Application of exponential random walks

Let us consider a situation where we seek to estimate the mean leakage/at, o f symmetric exponential r a n d o m walks by explicitly simulating them o n a computer, using r a n d o m numbers. This numerical technique, caUed Monte-Carlo, essentially consists o f selecting a sample AM o f M r a n d o m walks from the space A. T h e required mean #L is estimated by taking an average o f leakage L over As¢. Let #~ d e n o t e the sample estimate o f #L.

F r o m central limit theorem, as M --, ~ , the probability density o f p~ tends to a gaussian with m e a n / z z and variance

a[/M.

A finite sample estimate p~ o f the mean leakage is thus associated with a statistical error given by one-sigma confidence limit,

+_ aL/ ~/M.

In practice, we use the sample estimate o f az for obtaining the statistical error.

Consider a p r o b l e m where the quantity aL/#L which is a measure o f the relative statistical error, is very large. This implies that to obtain a statistically reliable estimate o f # , , we must generate a very large number o f r a n d o m walks. This m a y not always be possible due to the constraints on the availability o f c o m p u t e r time and cost. This is precisely the situation we face in the study o f radiation transport. Let us illustrate the problem by considering (24) and (25). We present in figure I the variation o f

OL/pL

as a function o f T for different typical values o f C. It is clear that as T becomes large and C small the statistical e r r o r associated with a sample estimate Of PL, would be large. Such problems with large T are k n o w n as deep penetration problems in radiation transport literature (see e.g. Levitt 1969).

T o overcome the above difficulties associated with M o n t e - C a r l o simulation o f deep penetration problems, we resort to variance reduction techniques. Essentially, these techniques help us distort the original problem in such a way that the new distorted problem constructed, has the same mean/z L o f the original p r o b l e m but significantly reduced variance. We shall consider in this paper, one o f the variance reduction devices called importance sampling, and derive an optimal scheme, on the basis o f results obtained f r o m the exponential r a n d o m walks discussed in § 4.

(6)

1 0 7 [

10 4

10 2

10 °

Figure 1.

0.5

0 . 9

2 0 . 0 4 0 . 0 6 0 . 0

T

Variation o f

~L/PL

as a function o f T for different values o f C.

An example o f importance sampling consists o f using a right-biased exponential density (19) called importance function, to generate the r a n d o m walks, instead o f the symmetric exponential density (18). However, mean leakage must be preserved, and this is assured by redefining the random variable L, as follows

N

L = C N-' l-[ f(x,)/g(b, x,), (26)

i = 1

w h e r e f ( x ) is the 'analogue' density (18) and g(b, x) is the biased density (19); xi, i = 1, 2 . . . . N are the step displacements in the r a n d o m walk. Using (18) and (19) we get L explicitly as

L = C N-' exp( - bXN)/(I - b 2 ) N. (27)

In the above, we can set X N = T, under asymptotic approximation and express K t h m o m e n t o f l e a k a g e f o r m a l l y as

: V

<LK> = c , , ~ . , \T-5-~/ ¢(N). (28)

C o m p a r e the above with (8). It is clear that if w e set re(O) = (C/I - b ~) %

we obtain K t h m o m e n t of L as

(29)

( L r ) = exp( - b K T - 01" T )/C r, (30)

(7)

where 01, the positive root o f (29), is given by

0x = -- b + [1 -

Cx/(1 - b2)X-l] 1/2.

(31)

N o t e that

m(O)

for the present case is given by (21). Thus we get analytical expression for the moments o f leakage as

( Lr>

= e x p { - b T ( K - 1 ) - T [ 1

-CK/(1 -b2)X-']l/2}/C K.

(32) The above is exact for T--. oo. However for a finite T, it gives exact results for b ,~ 1 and C >> 0. In (32), if we substitute K = 1, we recover (24)and this shows that mean leakage is indeed preserved under importance sampling. The variance of leakage for the biased problem is given by

02Ln

= [ e x p { - b T - T ( 1

-C2/1

- b 2 ) 1/2 } - e x p { - 2 T ( 1

-C)X/2}]/C 2.

(33) We present in table 1 the variance reduction ratio o~n/o 2 as a function o f b for C = 0-5, 0-7 and 0-9 with T = 30. From table 1 it is clear that the variance o f leakage for the biased problem is significantly smaller than that for original problem, when the parameter b is properly chosen. Indeed if we choose b = (1 - C ) 1/2, we get zero variance.

A practical problem o f neutron transport through shields is quite formidable and is not amenable to easy solution, numerical or otherwise. The difficulties arise mainly due to strong energy dependence o f the various interaction processes and complex

T a b l e 1. V a r i a n c e reduction under b i a s i n g (T = 30).

2 2

ff LB/ff L

b C - 0 . 5 C - 0 - 7 C - 0 . 9

0.0 1 "0 1-0 1 "0

0-05 2-26 ( - 1 ) * 2-29 ( - 1 ) 2-37 ( - 1 )

0-10 5-20 ( - 2 ) 5-52 ( - 2 ) 6"36 ( - 2 )

0-15 1-23 (--2) 1"41 ( - 2 ) 1"88 ( - 2 )

0-20 2"97 (--3) 3"81 ( - 3 ) 5"65 (--3)

0-25 7"34 ( - 4 ) 1.10 ( - 3 ) 1.40 ( - 3 )

0-30 1.90 ( - 4 ) 3.40 ( - 4 ) 8-04 ( - 5 )

0-35 5-07 ( - 5 ) 1-11 ( - 4 ) 4-56 ( - 4 )

0-40 1-41 ( - 6 ) 3-74 ( - 5 ) 7.40 ( - 3 )

0-45 4-15 (--6) 1-17 ( - 5 ) 1-26 ( - 2 )

0.50 1"28 (--6) 2"38 (--6) - -

0.55 4"08 ( - 7 ) 5"73 ( - 9 ) - -

0-60 1.25 ( - 7 ) 4.35 ( - 6 ) - -

0-65 2.86 ( - 8) 4.73 ( - 5) - -

0-70 4.51 ( - 1 0 ) 4o01 ( - 3 ) - -

0.75 2"39 (--8) - - - -

0.80 3.83 ( - 7 ) - - - -

0-85 1"28 (--4) - - - -

0-90 - - - - - -

0.95 - - - - - -

x/1 - C 0-0 0.0 0.0

* R e a d a s 2"26 x 1 0 - t

(8)

geometry. Added to this, is the problem of deep penetration that forbids us from obtaining reliable statistical estimates of leakage within reasonable computer time.

Perforce one has to take resort to variance reduction techniques, important amongst which is exponential biasing. (see e.g. Kahn 1950; Clark 1966; Dubi and Dudziak 1979;

Murthy 1982 and the literature cited therein), This technique essentially consists of sampling the intercollision distance from a biased exponential density instead of the analogue. Recently, an improvement to exponential biasing has been proposed by Dwivedi (1982). This consists of coupling exponential biasing to scattering angle biasing. One-dimensional version of this new coupled scheme leads to the asymmetric exponential random walk generator given by (19). Table 1 demonstrates the variance reduction capabilities of this coupled scheme.

6. Conclusions

A general formulation to obtain asymptotic behaviour of moments of leakage of random walks from a line segment is presented. We have obtained expressions for first passage time density and moments of leakage for gaussian random walks. Application of this formulation to asymmetric exponential random walks provided a means of quantifying the variance reduction characteristics of a recently proposed biasing schefne for radiation transport problems. We show that optimal biasing is obtained for values of b = (1

- C ) ~/z,

and this should prove useful in practical problems.

Acknowledgements

The author is thankful to T M John and R Indira for helpful discussions. He is also thankful to the referee for a careful review of the paper and valuable criticisms.

References

Bartlett M S 1966 An introduction to stochastic processes (Cambridge: University Press)

Clark F H 1966 The exponential transform as an importance sampling device--A Review, Report ORNL- RSIC-14, Oak Ridge National Laboratory

Dubi A and Dudziak J 1979 Nucl. Sci. Eng. 70 1 Dwivedi S R 1982 Ann. NucL Ener. 9 359 Kahn H 1950 Nucleonics 6 27, 60 Levitt L B 1969 Nucl. ScL Eng. 31 500

Murthy K P N 1982 in Proc. Workshop on Monte-Carlo Methods (Bombay: Bhabha Atomic Research Centre)

References

Related documents

Besides its core role of increasing shelf life of food, preserving food nutrients in the supply chain and providing fortified products targeted at micronutrient deficiencies, it

The Macroeconomic Policy and Financing for Development Division of ESCAP is undertaking an evaluation of this publication, A Review of Access to Finance by Micro, Small and Medium

studies include: Achieving Sustainable De- velopment in Africa through Inclusive Green Growth – agriculture, ecosystems, energy, in- dustry and trade (ECA, 2015a); Inclusive green

Attempts to identify poly- observed in all the gels were excluded from the morphic loci from general protein zymograms general pherogram pattern The relative mobility have

These gains in crop production are unprecedented which is why 5 million small farmers in India in 2008 elected to plant 7.6 million hectares of Bt cotton which

I hereby certify that I have validated the tool of 301612564, M.SC(N)MEDICAL SURGICAL NURSING., II YEAR student Sresakthimayeil Institute of Nursing and Research,

The petitioner also seeks for a direction to the opposite parties to provide for the complete workable portal free from errors and glitches so as to enable

Consultant / Firms should have at least 10 years of experience in preparation of Campus Master Plan for educational and health care institutions of the scale of NIMHANS