# First Hitting Place Probabilities for a Discrete Version of the Ornstein-Uhlenbeck Process

Authors: Mario Lefebvre; Jean-Luc Guilbault
Journal: International Journal of Mathematics and Mathematical Sciences
 (2009)

---

## Abstract

A Markov chain with state space{0,…,N} and transition probabilities depending on the current state is studied. The chain can be
considered as a discrete Ornstein-Uhlenbeck process. The probability that the process hits N before 0 is computed explicitly. Similarly, the
probability that the process hits N before −M is computed in the case when the state space is {−M,…,0,…,N} and the transition probabilities pi,i+1 are not necessarily the same when i is positive and i is negative.


---

## Body

## 1. Introduction

The Ornstein-Uhlenbeck process{X(t),t≥0} is defined by the stochastic differential equation(1.1)dX(t)=-cX(t)dt+dW(t),
where {W(t),t≥0} is a standard Brownian motion and c is a positive constant. Discrete versions of this very important diffusion process have been considered by various authors. In particular, Larralde [1, 2] studied the discrete-time process {Xn,n=0,1,…} for which(1.2)Xn+1=γXn+Yn+1,(X0=x0),
where the random variables Yn+1 are i.i.d. with zero mean and a common probability distribution. Larralde computed the probability that {Xn,n=0,1,…} will hit the negative semiaxis for the first time at the nth step, starting from X0=0. The problem was solved exactly in the case when the distribution of the random variables Yn is continuous and such that(1.3)fYn(y)=12e-|y|
for y∈ℝ and for all n∈{1,2,…}.Versions of the discrete Ornstein-Uhlenbeck process have also been studied by, among others, Renshaw [3], Anishchenko et al. [4, page  53], Bourlioux  et al. [5, page 236], Sprott [6, page 234], Kontoyiannis and Meyn [7], and Milstein et al. [8]. In many cases, the distribution of the Yn's is taken to be N(0,σ2).For discrete versions of diffusion processes, in general, see Kac [9] and the references therein. A random walk leading to the Ornstein-Uhlenbeck process is considered in Section 4 of Kac's paper.Next, consider a Markov chain for which the displacements take place everyΔt units of time. When the process is in state x, it moves to x+Δx (resp., x-Δx) with probability θ(x) (resp., ϕ(x)) and remains in x with probability 1-θ(x)-ϕ(x).Assume that(Δx)2=AΔt, and let(1.4)θ(x)=12A[α(x)+β(x)Δx],ϕ(x)=12A[α(x)-β(x)Δx],
where A is a positive constant such that α(x)<A for all x. Then, when Δx and Δt decrease to zero, the Markov chain converges to a diffusion process having infinitesimal mean β(x) and infinitesimal variance α(x) (see [10, page 213]). In the case of the Ornstein-Uhlenbeck process, β(x)=-cx (with c>0) and α(x)≡1. Hence, with A=2, we have that(1.5)θ(x)=14(1-cxΔx),ϕ(x)=14(1+cxΔx).In the present paper, we first consider the Markov chain with state space{0,…,N} and(1.6)pi,i+1=14(1-ci),pi,i-1=14(1+ci),pi,i=12
for i=1,…,N-1. Notice that pi,i+1 (resp., pi,i-1) could be denoted by θi (resp., ϕi). To respect the condition pi,j∈[0,1]  for all i,j, the positive constant c must be such that(1.7)c<1N-1.This Markov chain with state-dependent transition probabilities may also clearly be regarded as a discrete version of the Ornstein-Uhlenbeck process. It corresponds to the case whenγ=1 in (1.2) and(1.8)Yn+1={-1withprobabilitypXn,Xn-1,0withprobability12,1withprobabilitypXn,Xn+1,
for Xn∈{1,2,…,N-1}.In Section2, the probability(1.9)pi:=P[Xτ=N∣X0=i],
where(1.10)τ:=inf{n>0:Xn=0orN}
and i∈{1,2,…,N-1}, will be computed explicitly. In Section 3, the problem will be extended by assuming that the state space of the Markov chain {Xn,n=0,1,…} is {-M,…,0,…,N}. Furthermore, the transition probabilities pi,j will be assumed to be (possibly) sign-dependent (see [11]). Finally, some concluding remarks will be made in Section 4.


## 2. First Hitting Place Probabilities

To obtain the first hitting place probability defined in (1.9), we may try to solve the following difference equation:(2.1)pi=(1-ci)4pi+1+12pi+(1+ci)4pi-1⇔pi=(1-ci)2pi+1+(1+ci)2pi-1
for i=1,…,N-1, subject to the boundary conditions(2.2)p0=0,pN=1.
For N small, it is a relatively simple task to calculate explicitly pi for all i by solving a system of linear equations. However, we want to obtain an exact expression for any positive N.Next, settingx=i-1 and letting y(x)=pi-1,  (2.1) can be rewritten as(2.3)[1-c(x+1)2]y(x+2)-y(x+1)+[1+c(x+1)2]y(x)=0
for x=0,…,N-2 (with y(0)=0 and y(N)=1). This second-order homogeneous equation with linear coefficients is called the hypergeometric difference equation, due to the fact that its solutions can be expressed in terms of the hypergeometric function (see [12, page 68]).Equation (2.3) can be transformed into its normal form, namely,(2.4)(x+β1+β2+2)y(x+2)-[(ρ1+ρ2)(x+1)+β1ρ2+β2ρ1]y(x+1)+ρ1ρ2xy(x)=0.
In our case, we have (see [12, pages 68-69])(2.5)ρ1=1,ρ2=-1,β1=-1,β2=-1-2c,
so that we must solve(2.6)(x-a)y(x+2)+ay(x+1)-xy(x)=0,
where(2.7)a:=2c.
Furthermore, the variable x now belongs to the set {1+1/c,…,N-1+1/c} (because the new argument of the function y is x′=x+β3, where β3=1+1/c in our problem).Using the results in Batchelder [12, Chapter III], we can state that a fundamental system of solutions of  (2.6) is(2.8)y1(x)≡γ∈ℝ,y2(x)=(-1)xΓ(x)Γ(x-a)F(-a,1,x-a,12),
where F(·,·,·,·) is the hypergeometric function defined by (see [13, page 556])(2.9)F(α,β,γ,z)=∑n=0∞(α)n(β)n(γ)nznn!
with(2.10)(α)n:=α(α+1)⋯(α+n-1),(and(α)0=1).Remark 2 s.
(i) The functionF is sometimes denoted by 2F1. It can also be expressed as (see, again, [13, page 556])
(2.11)F(α,β,γ,z)=Γ(γ)Γ(α)Γ(β)∑n=0∞Γ(α+n)Γ(β+n)Γ(γ+n)znn!.
(ii) The ratioF(α,β,γ,z0)/Γ(γ) is an entire function of α, β, and γ if z0 is fixed and such that |z0|<1 (see [14, page 68]).
Now, because of the term(-1)x, the function y2(x) defined previously is generally complex-valued. Since the function y(x) in our application is obviously real, we can take the real part of y2(x). That is, we simply have to replace (-1)x by cos(πx). Alternatively, because [x] = [i+1+1/c] = i+1+[1/c], where [] denotes the integer part, we can write that
(2.12)(-1)x=(-1)[x]+1/c-[1/c].
With the difference equation (2.6) being homogeneous, we can state that
(2.13)y2(x)=(-1)[x]Γ(x)Γ(x-a)F(-a,1,x-a,12)
is a real-valued function that is also a solution of this equation. Hence, the general solution of (2.6) can be expressed as
(2.14)y(x)=γ1+γ2(-1)[x]Γ(x)Γ(x-a)F(-a,1,x-a,12),
where γ1 and γ2 are arbitrary (real) constants.
(iii) We must be careful when the constantc is of the form
(2.15)c=1N+j,
where j∈{0,1,…}. Indeed, because β1=-1,  (2.6) is reducible. Moreover, it is completely reducible if β2 is also a negative integer (see [12, pages 123-124]), that is, if
(2.16)β2=-1-2c=-k
with k∈{1,2,…}. Since c must be smaller than 1/(N-1) (see (1.7)), this condition translates into
(2.17)c=1N+jorc=22(N+j)-1,
where j∈{0,1,…}. We find that the case when c=2/[2(N+j)-1] does not really cause any problem. However, when c=1/(N+j), we can show that although y1(x)≡γ and y2(x) defined in (2.13) are obviously linearly independent when we consider all possible values of the argument x, it turns out that in our problem y2(x) always takes on the same value. More precisely, we can show that
(2.18)y2(x)=(-1)[x]Pa(x),
where Pa(x) is a polynomial of degree a, with
(2.19)a=2c=2(N+j),
given by
(2.20)Pa(x)=a!x(-12)a∑n=0a(-2)nx(n+1)n!,
with
(2.21)x(i):=x(x-1)⋯(x-i+1)
for any natural number i.Remark
The formula forPa(x) is valid if a=2(N+j)-1 as well, so that we can set a equal to 2N+j, with j∈{-1,0,1,…}, above.Now, we find that(2.22)y2(x)=(-1)a+1a!2aifx=1,2,…,a+1.
For example, suppose that N=3, so that the state space of the Markov chain is {0,1,2,3}, and that c=1/3. Because x=i+4, the possible values of x are 4,5,6,7. Furthermore, a=2/c=6. The solution y2(x) can be written as(2.23)y2(x)=(-1)[x]{x6-24x5+4552x4-1080x3+2674x2-3216x+57154}.
It is a simple matter to show that this function satisfies  (2.6) with a=6. However, we calculate(2.24)y2(x)=-454forx∈{1,2,…,7}.
Thus, y1(x) and y2(x) are both constant for the values of interest of x in our problem.Actually we easily find thatp1=1/13 and p2=3/13 in this example. Therefore, we cannot make use of y1(x) and y2(x) to obtain pi. Nevertheless, because y2(x) is a continuous function of the parameter c, we simply have to take the limit as c tends to 1/(N+j) to get the solution we are looking for.Next, we have obtained the general solution of  (2.6) in (2.14). We must find the constants γ1 and γ2 for which the boundary conditions(2.25)y(1+a2)=0,y(N+1+a2)=1
are satisfied. We can state the following proposition.Proposition 2.1.
Whenc≠2/[2(N+j)-1] for j∈{0,1,…}, the probability pi defined in (1.9) is given by
(2.26)pi=y(i+1+1c),
where the function y(·) is defined in (2.14), with
(2.27)γ2=(-1)[a/2]{a2πΓ(a/2)Γ((1-a)/2)-(-1)NΓ(N+1+a/2)Γ(N+1-a/2)F(-a,1,N+1-a2,12)}-1,γ1=γ2(-1)[a/2]a2πΓ(a/2)Γ((1-a)/2).
In the case when c=2/[2(N+j)-1], the constants γ1 and γ2 become
(2.28)γ1=0,γ2=(-1)NΓ(N+1-a/2)Γ(N+1+a/2)F(-a,1,N+1-a/2,1/2).Proof.
We find (see [13, page 557]) that y2(x) evaluated at x=1+a/2 (i.e., i=0) can be expressed as
(2.29)y2(1+a2)=(-1)1+[a/2]a2πΓ(a/2)Γ((1-a)/2).
This is actually obtained as a limit when c=1/(N+j) with j∈{0,1,…}. Moreover, it follows that as c tends to 2/[2(N+j)-1], we have
(2.30)y2(1+a2)→0.
Hence, for any c≠2/[2(N+j)-1], the constants γ1 and γ2 are uniquely determined from the boundary conditions (2.25), while c=2/[2(N+j)-1] immediately yields that γ1=0 and that γ2 is as in (2.28).Remark 2 s.
(i) We see that the case when the difference equation is completely reducible is rather special. Whenc=2/[2(N+j)-1], the constant γ1 vanishes, while when c=1/(N+j), the probability pi is obtained by taking the limit of the previous solution when c tends to this particular value.
(ii) We can obtain an approximate formula for the probabilitypi, valid for N large, by proceeding as follows. First, because (by assumption) c<1/(N-1), we can write that
(2.31)c=1N-1+κ⇔1c=N-1+κ,
where κ>0. Hence,
(2.32)1c≈N-1+[κ]+12=N+[κ]-12.
Notice that the relative error ϵr committed by replacing 1/c by its approximate value is such that
(2.33)ϵr≤1/2N-1+κ,
so that it is negligible when N is large. Moreover, for this approximate value of the constant c, we can express the solution in terms of the polynomial in (2.20), with a=2(N+[κ])-1. Making use of the boundary conditions, we deduce that
(2.34)y(x)≈(-1)[x]Pa(x)(-1)NPa(N+1+a/2).
We can simply write that
(2.35)y(x)≈|Pa(x)Pa(N+1+a/2)|.
Since Pa(x) is a polynomial of degree a, we find that we have approximated the function y(x) by a polynomial of degree 2[1/c]+1.
In the next section, the state space of the Markov chain will be extended to{-M,…,0,…,N} and the (possibly) asymmetric case will be treated.


## 3. The Asymmetric Case

We extend the problem considered in the previous section by assuming that the state space of the Markov chain{Xn,n=0,1,…} is the set(3.1)S:={-M,…-1,0,1…,N},
where M∈{1,2,…}. Furthermore, we set(3.2)p0,1=p0,p0,-1=q0,p0,0=12,
where p0,q0∈(0,1) and p0+q0=1/2.Wheni is a negative state, we define(3.3)pi,i+1=1-di4,pi,i-1=1+di4,pi,i=12
for i∈{-M+1,…,-1}. In order to respect the condition pi,j∈[0,1]  for all i,j, we find that the positive constant d must be such that(3.4)d<1M-1.Let(3.5)T=inf{n>0:Xn=Nor-M}.
We want to compute the first hitting place probability(3.6)πi:=P[XT=N∣X0=i]
for i∈{-M+1,…,0,…,N-1}. We have(3.7)πN=1,π-M=0.Let us denote the probabilitypi defined in (1.9) by pN(i) and define(3.8)pM(i)=P[Xσ=-M∣X0=i],
where i∈{-M+1,…,-1}, and(3.9)σ:=inf{n>0:Xn=-Mor0}.
Proceeding as in Section 2, we can show that(3.10)pM(i)=l1+l2(-1)i+1+[1/d]Γ(i+1+1/d)Γ(i+1-1/d)F(-2d,1,i+1-1d,12),
where the constants l1 and l2 are uniquely determined from the boundary conditions(3.11)pM(-M)=1,pM(0)=0.
Again, we must be careful in the case when the difference equation is completely reducible.Next, we define the events(3.12)Ei=theprocesshitsNbefore-Mfromi∈S;Fi=theprocesshitsNbefore0fromi>0;Gi=theprocesshits-Mbefore0fromi<0.
Assume first that i is positive. Then, we can write that(3.13)πi≡P[Ei]=P[Ei∩Fi]+P[Ei∩Fic]=pN(i)+2[1-pN(i)]{π1p0+π-1q0}.
When i is negative, we have(3.14)πi=P[Ei∩Gi]+P[Ei∩Gic]=P[Ei∩Gic]=2pM(i){π1p0+π-1q0}.Settingi=1 (resp., -1) in (3.13) (resp., (3.14)), we obtain a system of two linear equations for π1 and π-1:(3.15)π1=pN(1)+2[1-pN(1)]{π1p0+π-1q0},π-1=2pM(-1){π1p0+π-1q0}.Proposition 3.1.
The probabilityπi defined in (3.6) is given for i>0 (resp., i<0) by (3.13) (resp., (3.14)), in which
(3.16)π1=pN(1)[1-2q0pM(-1)]1-2q0pM(-1)-2p0[1-pN(1)],π-1=2p0pM(-1)pN(1)1-2q0pM(-1)-2p0[1-pN(1)].Remark 3 s.
(i) Ifp0=q0=1/4, the formulas for π1 and π-1 reduce to
(3.17)π1=pN(1)[2-pM(-1)]1-pM(-1)+pN(1),π-1=pM(-1)pN(1)1-pM(-1)+pN(1).
Moreover, if M=N and d=c, then (by symmetry) pM(-1)=pN(1) and
(3.18)π1=pN(1)[2-pN(1)],π-1=pN2(1).
(ii) The probability
(3.19)νi:=P[XT=-M∣X0=i]
is of course given by 1-πi, for i=-M+1,…,0,…,N-1.


## 4. Concluding Remarks

In Section2, we computed the probability pi that a Markov chain with transition probabilities given by (1.6) and state space {0,1,…,N} will hit N before 0, starting from i∈{1,…,N-1}. If we let c decrease to 0 in (1.6), we obtain that(4.1)pi,i+1=pi,i-1=14,pi,i=12fori∈{1,2,…,N-1}.
That is, the Markov chain {Xn,n=0,1,…} is a (generalized) symmetric random walk having a probability pi,i=1/2 of remaining in its current state on each transition. The fact that pi,i>0 should not influence the probability pi. Taking the limit as c decreases to 0 (i.e., a→∞) in Proposition 2.1, we indeed retrieve the well-known formula(4.2)pi=iNfori=0,1,…,N.In Section3, we were able to compute explicitly the probability πi defined in (3.6) for a (possibly) asymmetric Markov chain with state space {-M,…,0,…,N}. This type of Markov chain could have applications in mathematical finance, in particular. Indeed, if one is looking for the probability that the value of a certain stock reaches a given level before a lower one, it can be more realistic to assume that the stock price does not vary in the same way when the price is high or low. Hence, the assumption that the transition probabilities may be different when Xn>0 and Xn<0 seems plausible in some applications. In the application we have just mentioned, 0 could be the centered current value of the stock.Next, another problem of interest is the determination of the average timeDi the process, starting from i, takes to hit either 0 or N (in Section 2), or -M or N (in Section 3). To obtain an explicit expression for Di, we must solve a nonhomogeneous linear difference equation. Finding a particular solution to this equation (in order to obtain the general solution by using the solution to the homogeneous equation obtained in the present work) is a surprisingly difficult problem.Finally, we could try to take the limit of the Markov chain{Xn,n=0,1,…} in such a way as to obtain the Ornstein-Uhlenbeck process as a limiting process. We should retrieve the known formula for the probability pi in the case of this process considered in the interval [0,N] and generalize this formula to the asymmetric case, based on Section 3.



---

*Source: 909835-2009-11-25.xml*