Steven R. Dunbar
Department of Mathematics
203 Avery Hall
University of Nebraska-Lincoln
Lincoln, NE 68588-0130
http://www.math.unl.edu
Voice: 402-472-3731
Fax: 402-472-8466

Stochastic Processes and
Advanced Mathematical Finance

__________________________________________________________________________

Hitting Times and Ruin Probabilities

_______________________________________________________________________

Note: These pages are prepared with MathJax. MathJax is an open source JavaScript display engine for mathematics that works in all browsers. See http://mathjax.org for details on supported browsers, accessibility, copy-and-paste, and other features.

_______________________________________________________________________________________________

Rating

Rating

Mathematically Mature: may contain mathematics beyond calculus with proofs.

_______________________________________________________________________________________________

Section Starter Question

Section Starter Question

What is the probability that a simple random walk with p = 12 = q starting at the origin will hit value a > 0 before it hits value b < 0, where b > 0? What do you expect in analogy for the standard Wiener process and why?

_______________________________________________________________________________________________

Key Concepts

Key Concepts

  1. With the Reflection Principle, we can derive the p.d.f of the hitting time Ta.
  2. With the hitting time, we can derive the c.d.f. of the maximum of the Wiener Process on the interval 0 u t.

__________________________________________________________________________

Vocabulary

Vocabulary

  1. The Reflection Principle says the Wiener process reflected about a first passage has the same distribution as the original motion.
  2. The hitting time Ta is the first time the Wiener process assumes the value a. In notation from analysis
    Ta = inf{t > 0 : W(t) = a}.

__________________________________________________________________________

Mathematical Ideas

Mathematical Ideas

Hitting Times

Consider the standard Wiener process W(t), which starts at W(0) = 0. Let a > 0. The hitting time Ta is the first time the Wiener process hits a. In notation from analysis

Ta = inf{t > 0 : W(t) = a}.

Note the very strong analogy with the duration of the game in the gambler’s ruin.

Some Wiener process sample paths will hit a > 0 fairly directly. Others will make an excursion to negative values and take a long time to finally reach a. Thus Ta will have a probability distribution. We determine that probability distribution by a heuristic procedure similar to the first step analysis we made for coin-flipping fortunes.

Specifically, we consider a probability by conditioning, that is, conditioning on whether or not Ta t, for some given value of t.

W(t) a = W(t) a|Ta t Ta t + W(t) a|Ta > t Ta > t

Now note that the second conditional probability is 0 because it is an empty event. Therefore:

W(t) a = W(t) a|Ta t Ta t.

Now, consider Wiener process “started over” again at the time Ta when it hits a. By the shifting transformation from the previous section, the “started-over” process has the distribution of Wiener process again, so

W(t) a|Ta t = W(t) a|W(Ta) = a,Ta t = W(t) W(Ta) 0|Ta t = 12.

This argument is a specific example of the Reflection Principle for the Wiener process. It says that the Wiener process reflected about a first passage has the same distribution as the original motion.

Thus

W(t) a = (12) Ta t.

or

Ta t = 2 W(t) a = 2 2πta exp(u2(2t))du = 2 2πat exp(v22)dv

(note the change of variables v = ut in the second integral) and so we have derived the c.d.f. of the hitting time random variable. One can easily differentiate to obtain the p.d.f

fTa(t) = a 2πt32 exp(a2(2t)).

Actually, this argument contains a serious logical gap, since Ta is a random time, not a fixed time. That is, the value of Ta is different for each sample path, it varies with ω. On the other hand, the shifting transformation defined in the prior section depends on having a fixed time, called h in that section. To fix this logical gap, we must make sure that “random times” act like fixed times. Under special conditions, random times can act like fixed times. Specifically, this proof can be fixed and made completely rigorous by showing that the standard Wiener process has the strong Markov property and that Ta is a Markov time corresponding to the event of first passage from 0 to a.

Note that deriving the p.d.f. of the hitting time is much stronger than the analogous result for the duration of the game until ruin in the coin-flipping game. There we were only able to derive an expression for the expected value of the hitting time, not the probability distribution of the hitting time. Now we are able to derive the probability distribution of the hitting time fairly intuitively (although strictly speaking there is a gap). Here is a place where it is simpler to derive a quantity for Wiener process than it is to derive the corresponding quantity for random walk.

Let us now consider the probability that the Wiener process hits a > 0, before hitting b < 0 where b > 0. To compute this we will make use of the interpretation of the standard Wiener process as being the limit of the symmetric random walk. Recall from the exercises following the section on the gambler’s ruin in the fair (p = 12 = q) coin-flipping game that the probability that the random walk goes up to value a before going down to value b when the step size is Δx is

 to a before b  = bΔx (a + b)Δx = b a + b

Thus, the probability of hitting a > 0 before hitting b < 0 does not depend on the step size, and also does not depend on the time interval. Therefore, passing to the limit in the scaling process for random walks, the probabilities should remain the same. Here is a place where it is easier to derive the result from the coin-flipping game and pass to the limit than to derive the result directly from Wiener process principles.

The Distribution of the Maximum

Let t be a given time, let a > 0 be a given value, then

max 0utW(u) a = Ta t = 2 2πat exp(y22)dy

Sources

This section is adapted from: Probability Models, by S. Ross, and A First Course in Stochastic Processes Second Edition by S. Karlin, and H. Taylor, Academic Press, 1975. The technical note about the algorithm combines discussion about Donkser’s principle from Freedman’s Brownian Motion and Diffusions, Breiman’s, Probability, Khoshnevisan’s notes, and Peled’s notes

_______________________________________________________________________________________________

Algorithms, Scripts, Simulations

Algorithms, Scripts, Simulations

Algorithm

Set a time interval length T sufficiently long to have a good chance of hitting the fixed value a before fixed time t < T. Set a large value n for the length of the random walk used to create the Wiener process, then fill an n × k matrix with Bernoulli random variables. Cumulatively sum the Bernoulli random variables to create a scaled random walk approximating the Wiener process. For each random walk, find when the hitting time is encountered. Also find the maximum value of the scaled random walk on the interval [0,t]. Since the approximation is piecewise linear, only the nodes need to be examined. Compute the fraction of the k walks which have a hitting time less than t or a maximum greater than a on the interval [0,t]. Compare the fraction to the theoretical value.

Technical Note: The careful reader will note that the hitting time Ta = inf{t > 0 : W(t) = a} and the events [Ta t] and [max 0utW(u) a] are “global” events on the set of all Wiener process paths. However, the definition of Wiener process only has prescribed probability distributions on the values at specified times. Implicit in the definition of the Wiener process is a probability distribution on the “global” set of Wiener processes, but the proof of the existence of the probability distribution is beyond the scope of this text. Moreover, there is no easy distribution function to compute the probability of such events as there is with the normal probability distribution.

The algorithm approximates the probability by counting how many of k scaled binomial random variables hit a value greater than or equal to a at a node which corresponds to a time less than or equal to t. Convergence of the counting probability to the global Wiener process probability requires justification with Donsker’s Invariance Principle. The principle says that the piecewise linear processes ŴN(t) converge in distribution to the Wiener process.

To apply Donsker’s Principle, consider the functional

ϕ(f) = h(max 0utf(u))

where h() is a bounded continuous function. The convergence in distribution from the Invariance Principle implies that

𝔼 ϕ(ŴN(t)) 𝔼 ϕW.

Now taking h() to be an approximate indicator function on the interval [a,) shows that the counting probability converges to the global Wiener process probability. The details require careful analysis.

Geogebra

GeoGebra.

R

R script for hitting time..

1T <- 10 
2a <- 1 
3time <- 2 
4 
5p <- 0.5 
6n <- 10000 
7k <- 1000 
8 
9Delta = T/n 
10 
11winLose <- 2 * (array( 0+(runif(n*k) <= p), dim=c(n,k))) - 1 
12# 0+ coerces Boolean to numeric 
13totals <- apply( winLose, 2, cumsum) 
14 
15paths <- array( 0 , dim=c(n+1, k) ) 
16paths[2:(n+1), 1:k] <- sqrt(Delta)*totals 
17 
18hitIndex <- apply( 0+(paths <= a), 2, (function(x) match(0, x, nomatch=n+2))) 
19# If no hiting on a walk, nomatch=n+2 sets the hitting 
20# time to be two more than the number of steps, one more than 
21# the column length.  Without the nomatch option, get NA which 
22# works poorly with the comparison 
23 
24hittingTime = Delta*(hitIndex-1) 
25## subtract 1 since vectors are 1-based 
26 
27probHitlessTa <- sum( 0+(hittingTime <= time))/k 
28probMax = sum( 0+( apply(paths[1:((time/Delta)+1),], 2, max) >= a ) )/k 
29theoreticalProb = 2*pnorm(a/sqrt(time), lower=FALSE) 
30 
31cat(sprintf("Empirical probability Wiener process paths hit %f before %f: %f \n", a, time, probHitlessTa )) 
32cat(sprintf("Empirical probability Wiener process paths greater than %f before %f: %f \n", a, time, probMax )) 
33cat(sprintf("Theoretical probability: %f \n", theoreticalProb ))
Octave

Octave script for hitting time..

1T = 10; 
2a = 1; 
3time = 2; 
4 
5p = 0.5; 
6n = 10000; 
7k = 1000; 
8 
9Delta = T/n; 
10 
11winLose = 2 * (rand(n,k) <= p) - 1; 
12# -1 for Tails, 1 for Heads 
13totals = cumsum(winLose); 
14# -n..n (every other integer) binomial rv sample 
15 
16paths = sqrt(Delta)*[zeros(1,k); totals]; 
17hittingTime = zeros(1,k); 
18for j = 1:k 
19  hitIndex = find(paths(:,j) >= a); 
20  if ( !rows(hitIndex) ) 
21    hittingTime(j) = Delta * (n+2); 
22    ## If no hitting on a walk, set hitting time to be two 
23    ##  more than the number of steps, one more than the column length. 
24  else 
25    hittingTime(j) = Delta * (hitIndex(1)-1); 
26    ## some hitting time 
27    ## subtract 1 since vectors are 1-based 
28  endif 
29endfor 
30 
31probHitlessTa = sum( (hittingTime <= time) ) /k; 
32probMax = sum( max(paths(1:((time/Delta)+1),:)) >= a)/k; 
33theoreticalProb = 2*(1 - normcdf(a/sqrt(time))); 
34 
35printf("Empirical probability Wiener process paths hit %f before %f: %f \n", a, time, probHitlessTa ) 
36printf("Empirical probability Wiener process paths greater than %f before %f: %f \n", a, time, probMax ) 
37printf("Theoretical probability: %f \n", theoreticalProb )
Perl

Perl PDL script for hitting time.

1use PDL::NiceSlice; 
2 
3sub pnorm { 
4    my ( $x, $sigma, $mu ) = @_; 
5    $sigma = 1 unless defined($sigma); 
6    $mu    = 0 unless defined($mu); 
7 
8    return 0.5 * ( 1 + erf( ( $x - $mu ) / ( sqrt(2) * $sigma ) ) ); 
9} 
10 
11$T    = 10; 
12$a    = 1; 
13$time = 2; 
14 
15$p = 0.5; 
16$n = 10000; 
17$k = 1000; 
18 
19$Delta = $T / $n; 
20 
21$winLose = 2 * ( random( $k, $n ) <= $p ) - 1; 
22$totals = ( cumusumover $winLose->xchg( 0, 1 ) )->transpose; 
23 
24$paths = zeroes( $k, $n + 1 ); 
25 
26# use PDL:NiceSlice on next line 
27$paths ( 0 : ( $k - 1 ), 1 : $n ) .= sqrt($Delta) * $totals; 
28 
29$hita = $paths->setbadif( $paths <= $a ); 
30 
31$hitIndex = 
32    ( $hita (,)->xchg( 0, 1 )->minimum_ind )->inplace->setbadtoval( $n + 1 ); 
33 
34$hittingTime = $Delta * $hitIndex; 
35 
36$probHitlessTa = sumover( $hittingTime < $time ) / $k; 
37$probMax       = sumover( 
38    maximum( 
39        $paths ( 0 : ( $k - 1 ), 0 : ( $time / $Delta ) - 1 )->xchg( 0, 1 ) 
40        ) >= $a 
41) / $k; 
42$theoreticalProb = 2 * ( 1 - pnorm( $a / sqrt($time) ) ); 
43 
44print "Empirical probability Wiener process paths hit ", $a, "before ", $time, 
45    "is ", $probHitlessTa, "\n"; 
46print "Empirical probability Wiener process paths greater than ", $a, 
47    "before ", $time, "is ", $probMax, "\n"; 
48print "Theoretical probability:", $theoreticalProb, "\n";
SciPy

Scientific Python script for hitting time..

1import scipy 
2 
3T = 10.0 
4# note type float 
5a = 1 
6time = 2 
7 
8p = 0.5 
9n = 1000 
10k = 50 
11 
12Delta = T/n 
13 
14winLose = 2*( scipy.random.random((n,k)) <= p ) - 1 
15totals = scipy.cumsum(winLose, axis = 0) 
16 
17paths = scipy.zeros((n+1,k), dtype=float) 
18paths[ 1:n+1, :] = scipy.sqrt(Delta) * totals 
19 
20def match(x,arry,nomatch=None): 
21    if arry[scipy.where( (arry >= x))].any(): 
22        return  scipy.where( (arry >= x) )[0][0] - 1 
23    else: 
24        return nomatch 
25# arguments: x is a scalar, arry is a python list, value of nomatch is scalar 
26# returns the first index of first  of its first argument in its second argument 
27# but if a is not there, returns the value nomatch 
28# modeled on the R function "match", but with less generality 
29 
30hitIndex = scipy.apply_along_axis(lambda x:( match(a,x,nomatch=n+2)), 0, paths) 
31# If no ruin or victory on a walk, nomatch=n+2 sets the hitting 
32# time to be two more than the number of steps, one more than 
33# the column length. 
34 
35hittingTime = Delta * hitIndex 
36 
37probHitlessTa = (scipy.sum( hittingTime < time).astype(float))/k 
38probMax = (scipy.sum( scipy.amax( paths[ 0:scipy.floor(time/Delta)+1, : ], axis=0) >= a).astype(float))/k 
39from scipy.stats import norm 
40theoreticalProb = 2 * (1 - norm.cdf(a/scipy.sqrt(time))) 
41 
42print "Empirical probability Wiener process paths hit ", a, "before ", time, "is ", probHitlessTa 
43print "Empirical probability Wiener process paths greater than ", a, "before ", time, "is ", probMax 
44print "Theoretical probability:", theoreticalProb

_______________________________________________________________________________________________

Problems to Work

Problems to Work for Understanding

  1. Differentiate the c.d.f. of Ta to obtain the expression for the p.d.f of Ta.
  2. Show that 𝔼 Ta = for a > 0.
  3. Suppose that the fluctuations of a share of stock of a certain company are well described by a Wiener process. Suppose that the company is bankrupt if ever the share price drops to zero. If the starting share price is A(0) = 5, what is the probability that the company is bankrupt by t = 25? What is the probability that the share price is above 10 at t = 25?
  4. Suppose you own one share of stock whose price changes according to a Wiener process. Suppose you purchased the stock at a price b + c, c > 0 and the present price is b. You have decided to sell the stock either when it reaches the price b + c or when an additional time t goes by, whichever comes first. What is the probability that you do not recover your purchase price?
  5. Modify the scripts by setting p > 0.5 or p < 0.5. What happens to the hitting time?
    1. Modify the scripts to plot the probability that the hitting time is less than or equal to a as a function of a.
    2. Modify the scripts to plot the probability that the hitting time is less than or equal to a as a function of t. On the same set of axes plot the theoretical probability as a function of t.

__________________________________________________________________________

Books

Reading Suggestion:

References

[1]   Leo Breiman. Probability. Addison Wesley, 1968.

[2]   David Freedman. Brownian Motion and Diffusions. Holden-Day, 1971. QA274.75F74.

[3]   S. Karlin and H. Taylor. A Second Course in Stochastic Processes. Academic Press, 1981.

[4]   Davar Khoshnevisan. Leture notes on donsker’s theorem. http://www.math.utah.edu/~davar/ps-_pdf-_files/donsker.pdf, 2005. accessed June 30, 2013.

[5]   Ron Peled. Random walks and brownian motion. http://www.math.tau.ac.il/~peledron/Teaching/RW_and_BM_2011/index.htm, 2011.

[6]   Sheldon M. Ross. Introduction to Probability Models. Elsevier, 8th edition, 2003.

__________________________________________________________________________

Links

Outside Readings and Links:

  1. Russell Gerrard, City University, London, Stochastic Modeling . Notes for the MSc in Actuarial Science, 2003-2004. Contributed by S. Dunbar October 30, 2005.

__________________________________________________________________________

I check all the information on each page for correctness and typographical errors. Nevertheless, some errors may occur and I would be grateful if you would alert me to such errors. I make every reasonable effort to present current and accurate information for public use, however I do not guarantee the accuracy or timeliness of information on this website. Your use of the information from this website is strictly voluntary and at your risk.

I have checked the links to external sites for usefulness. Links to external websites are provided as a convenience. I do not endorse, control, monitor, or guarantee the information contained in any external website. I don’t guarantee that the links are active at all times. Use the links here with the same caution as you would all information on the Internet. This website reflects the thoughts, interests and opinions of its author. They do not explicitly represent official positions or policies of my employer.

Information on this website is subject to change without notice.

Steve Dunbar’s Home Page, http://www.math.unl.edu/~sdunbar1

Email to Steve Dunbar, sdunbar1 at unl dot edu

Last modified: Processed from LATEX source on August 1, 2016