Markov renewal processes
113
Definition 17.1 The random sequence
)
,0
n
Sn≥ is called a random walk
starting at x
0
, whose
()
,1
n
Xn≥ are the successive steps.
If x
0
=0, the random walk is said to start at the origin.
Example 17.1 If the distribution of r.v. X
n
is concentrated on a two-point set
{
1,1− with
(1),(1)(1),
nn
pPX q p PX===−=≠ (17.6)
then the associated random walk is called the simple random walk or the
Bernoulli random walk.
The interpretation is quite simple: let us consider for instance a physical particle
moving on a straight line starting at the origin.
This particle takes a first unit step to the right with probability p or to the left
with probability q and so on.
Clearly, the r.v. S
n
will give the position of the particle on the line after the nth
step.
Though very particular, the notion of a simple random walk has a lot of
important applications in insurance, finance and operations research. A very
classical application is the so-called gambler's ruin problem.
Let us consider a game with two players such that at each trial, each gambler
wins 1 monetary unit with probability p and loses 1
monetary unit with
probability ( 1 )qp
− .
If u is the initial "fortune" of one player, he will be ruined at trial n iff, for the
first time, his fortune just after this trial becomes strictly negative.
He will be ruined before or at trial n iff he is ruined at one time k, k
≤ n.
The probability of this last event will be noted by
(,)un
and the probability of
being ruined precisely at time n will be noted by
(,)un
.
Clearly, we have:
0
(,) (, )
n
k
un uk
υ
=
Ψ=
∑
(17.7)
and
(,) (,) (, 1).un un un
Ψ−Ψ− (17.8)
The probability of not being ruined on
]
0, n , that is to say after any trial on
[]
0, n , will be represented by ( , )un
, and of course, we have:
(,) 1 (,)un un
−Ψ . (17.9)
Probabilities ( , )un
and
(,)unΨ
are called respectively the non-ruin probability
and the ruin probability on
[]
0, n starting at time 0 with an initial fortune - also
called reserve or equities for insurance companies - of amount u.