Discrete-Time Renewal Processes
Renewal processes provide a theoretical framework for investigating the occurrence of patterns in repeated independent trials. Roughly speaking, the reason for using the term “renewal” comes from the basic assumption that when the pattern of interest occurs for the first time, the process starts a new, in the sense that the initial situation is reestablished. This means that, starting from this “renewal instant,” the waiting time for the second occurrence of the pattern has the same distribution as the time needed for the first occurrence. The process continues like this indefinitely.
Renewal Chains
Let??be a sequence of extended positive integer-valued random variables,?
a.s. for n ≥ 1 (we use the term “extended” in the sense that
can take the value ∞). Denote by
?the associated sequence of partial sums:
.
An arrival time sequence , for the waiting times
form an i.i.d. sequence and
, is called a renewal chain, and every
is called a renewal time.?There are many real situations which could be modeled by renewal chains.
Example. Consider the following DNA sequence of HEV (hepatitis E virus):
Suppose that the bases {A, C, G, T } are independent of each other and have the same probability of appearing in a location, which is equal to 1/4. Thus the occurrences of one of them, say, C, form a renewal chain. The inter-arrival distribution is geometric with parameter equal to 1/4.
It is worth stressing here an important phenomenon which is specific to discrete-time renewal processes. As , the waiting time between two successive occurrences of a renewal is at least one unit of time. Consequently, in a finite interval of time, of length, say, n, we can have at most n renewals. As will be seen in the sequel, this is the reason why many variables of interest can be expressed as finite series of basic quantities, whereas in a continuous-time setting the corresponding series are infinite. This is one advantage of a renewal theory carried out in a discrete-time setting.
Let f, g : N → R. The discrete-time convolution product of f and g is the function f ? g : N → R:.?
For notational convenience, we use both and
for denoting the convolution. The generating functions of
and
are related by
.
(solution of a discrete-time renewal equation). If??and?
?then the discrete-time renewal equation has the unique solution?
This example shows that there is a correspondence in both senses between renewal chains and Markov chains. For this reason, techniques and results developed for Markov chains can be applied to renewal chains and vice versa.?A function of great importance in renewal theory is the renewal function , n ∈ N, defined as the expected number of renewals up to time n:
As?, we get?
.
Some authors define the renewal function without taking into account the renewal that occurs at the origin; if this were the case, we would have . There is only a question of convenience for technical reasons, and we have chosen here to include the renewal at the origin.
The renewal function can be expressed in terms of?. Indeed,?
(strong law of large numbers for N(n)).?For a recurrent renewal chain??we have
(central limit theorem for N(n)).?Consider a positive recurrent renewal chain?, with?
?and?
. Then?
.
(elementary renewal theorem).?For a recurrent renewal chain??we have?
.
The renewal theorem in a continuous-time setting states that for a continuous-time recurrent aperiodic renewal process, for any h > 0, we have
.
The same result holds true for a continuous-time recurrent periodic renewal process of period d, provided that h is a multiple of d.
Delayed Renewal Chains
Delayed renewal chains are used for modeling the same type of phenomenon as renewal chains do, with the only difference that we do not consider the origin as the occurrence of the first order renewal, that is, . In other words, we want to observe a normal renewal chain, but we missed the beginning and we denote by
the time when we observe the first renewal, which is not identically 0 but follows a certain distribution.
An arrival time sequence for the waiting times
form an i.i.d. sequence and
is independent of
is called a delayed renewal chain and every
is called a renewal time. The chain
is an ordinary renewal chain, called the associated renewal chain. Note that
is a renewal chain iff
a.s.
Example. Consider a sequence of i.i.d. Bernoulli trials. We can prove that the times of occurrence of different finite patterns form renewal chains, generally delayed. For instance, suppose we have the following sequence issued from repeated i.i.d. Bernoulli trials
and suppose that we are interested in the occurrence of the pattern SFS in this sample. Two different counting procedures can be considered. First, suppose that the counting starts anew when the searched pattern occurs, that is, we do not allow overlapping. Note that SFS occurs in the 6th and 11th trials. Note also that SFS occurs in the 13th trial, but we do not count this occurrence, because we do not allow overlapping, so we have started anew the counting at the 12th trial (that is, after the occurrence of SFS in the 11th trial). Second, suppose that we allow overlapping. In this case, the pattern SFS occurs in the 6th, 11th and 13th trial. In both situations the occurrence times of the pattern SFS is a delayed renewal chain.
A delayed renewal chain is called aperiodic (resp. periodic of period d > 1) if the associated renewal chain is aperiodic (resp. periodic of period d > 1). Similarly, a delayed renewal chain is said to be transient or positive (null) recurrent if the associated renewal chain is a such.
The Stationary Renewal Chain
The objective is to construct a particular case of delayed renewal chain which has important stationary or time-invariant properties. The question we want to answer is the following: For what kind of delayed renewal chain is? constant with respect to n ? Let us consider
a delayed renewal chain such that
, i.e.,
is a proper distribution. Suppose that
for all n ∈ N. Consequently, the generating function
is given by
?and by using the relation?
, then we obtain
,?
.
Equalizing the coefficients of in the left-hand and right-hand side, for n ∈ N, we get
,
.
Taking into account the fact that?, and using?
, we obtain
,
provided that the delayed renewal chain is positive recurrent. Thus, we have shown that if a positive recurrent delayed renewal chain satisfies??for all?
, then?
?and?
.
A positive recurrent delayed renewal chain such that
for all n ∈ N, we want to prove that
for all n ∈ N. For 0 ≤ s < 1, the generating function of the first occurrence of a renewal is
.
From above, we obtain
,
so??for all?
.
This entire discussion can be summarized in the following result.