Renewal theory

Introduction The renewal process is a generalization of the Poisson process. In essence, the Poisson process is a continuous-time Markov process on the positive integers (usually starting at zero) which has independent exponentially distributed holding times at each integer i before advancing to the next integer, i+1. In a renewal process, the holding times need not have an exponential distribution; rather, the holding times may have any distribution on the positive numbers, so long as the holding times are independent and identically distributed (IID) and have finite mean. Formal definition Let (S_i)_{i \geq 1} be a sequence of positive independent identically distributed random variables with finite expected value : 0 We refer to the random variable S_i as the "i-th holding time". Define for each n > 0 : : J_n = \sum_{i=1}^n S_i, each J_n is referred to as the "n-th jump time" and the intervals [J_n,J_{n+1}] are called "renewal intervals". Then (X_t)_{t\geq0} is given by random variable : X_t = \sum^\infty_{n=1} \operatorname{\mathbb{I}}_{\{J_n \leq t\}}=\sup \left\{\, n: J_n \leq t\, \right\} where \operatorname{\mathbb{I}}_{\{J_n \leq t\}} is the indicator function :\operatorname{\mathbb{I}}_{\{J_n \leq t\}} = \begin{cases} 1, & \text{if } J_n \leq t \\ 0, & \text{otherwise} \end{cases} (X_t)_{t\geq0} represents the number of jumps that have occurred by time t, and is called a renewal process. Interpretation If one considers events occurring at random times, one may choose to think of the holding times \{ S_i : i \geq 1 \} as the random time elapsed between two consecutive events. For example, if the renewal process is modelling the numbers of breakdown of different machines, then the holding time represents the time between one machine breaking down before another one does. The Poisson process is the unique renewal process with the Markov property, as the exponential distribution is the unique continuous random variable with the property of memorylessness. ==Renewal-reward processes==

Let W_1, W_2, \ldots be a sequence of IID random variables (rewards) satisfying :\operatorname{E}|W_i| Then the random variable :Y_t = \sum_{i=1}^{X_t}W_i is called a renewal-reward process. Note that unlike the S_i, each W_i may take negative values as well as positive values. The random variable Y_t depends on two sequences: the holding times S_1, S_2, \ldots and the rewards W_1, W_2, \ldots These two sequences need not be independent. In particular, W_i may be a function of S_i. Interpretation In the context of the above interpretation of the holding times as the time between successive malfunctions of a machine, the "rewards" W_1,W_2,\ldots (which in this case happen to be negative) may be viewed as the successive repair costs incurred as a result of the successive malfunctions. An alternative analogy is that we have a magic goose which lays eggs at intervals (holding times) distributed as S_i. Sometimes it lays golden eggs of random weight, and sometimes it lays toxic eggs (also of random weight) which require responsible (and costly) disposal. The "rewards" W_i are the successive (random) financial losses/gains resulting from successive eggs (i = 1,2,3,...) and Y_t records the total financial "reward" at time t. ==Renewal function==

We define the renewal function as the expected value of the number of jumps observed up to some time t: :m(t) = \operatorname{E}[X_t].\, Elementary renewal theorem The renewal function satisfies :\lim_{t \to \infty} \frac{1}{t} m(t) = \frac 1 {\operatorname{E}[S_1]}. : Elementary renewal theorem for renewal reward processes We define the reward function: :g(t) = \operatorname{E}[Y_t].\, The reward function satisfies :\lim_{t \to \infty} \frac{1}{t}g(t) = \frac{\operatorname{E}[W_1]}{\operatorname{E}[S_1]}. Renewal equation The renewal function satisfies :m(t) = F_S(t) + \int_0^t m(t-s) f_S(s)\, ds where F_S is the cumulative distribution function of S_1 and f_S is the corresponding probability density function. : ==Key renewal theorem==

Let X be a renewal process with renewal function m(t) and interrenewal mean \mu. Let g:[0,\infty) \rightarrow [0,\infty) be a function satisfying: • \int_0^\infty g(t)\, dt • g is monotone and non-increasing The key renewal theorem states that, as t\rightarrow \infty: :\int_0^t g(t-x)m'(x) \, dx \rightarrow \frac{1}{\mu}\int_0^\infty g(x)\, dx Renewal theorem Considering g(x)=\mathbb{I}_{[0, h]}(x) for any h>0 gives as a special case the renewal theorem: :m(t+h)-m(t)\rightarrow \frac{h}{\mu} as t\rightarrow \infty The result can be proved using integral equations or by a coupling argument. Though a special case of the key renewal theorem, it can be used to deduce the full theorem, by considering step functions and then increasing sequences of step functions. ==Asymptotic properties==

Renewal processes and renewal-reward processes have properties analogous to the strong law of large numbers, which can be derived from the same theorem. If (X_t)_{t\geq0} is a renewal process and (Y_t)_{t\geq0} is a renewal-reward process then: : \lim_{t \to \infty} \frac{1}{t} X_t = \frac{1}{\operatorname{E}[S_1]} : \lim_{t \to \infty} \frac{1}{t} Y_t = \frac{1}{\operatorname{E}[S_1]} \operatorname{E}[W_1] almost surely. : Renewal processes additionally have a property analogous to the central limit theorem: :\frac{X_t-t/\mu}{\sqrt{t\sigma^2/\mu^3}} \to \mathcal{N}(0,1) ==Inspection paradox==

A curious feature of renewal processes is that if we wait some predetermined time t and then observe how large the renewal interval containing t is, we should expect it to be typically larger than a renewal interval of average size. Mathematically the inspection paradox states: for any t > 0 the renewal interval containing t is stochastically larger than the first renewal interval. That is, for all x > 0 and for all t > 0: : \operatorname{P}(S_{X_t+1} > x) \geq \operatorname{P}(S_1>x) = 1-F_S(x) where FS is the cumulative distribution function of the IID holding times Si. A vivid example is the bus waiting time paradox: For a given random distribution of bus arrivals, the average rider at a bus stop observes more delays than the average operator of the buses. The resolution of the paradox is that our sampled distribution at time t is size-biased (see sampling bias), in that the likelihood an interval is chosen is proportional to its size. However, a renewal interval of average size is not size-biased. : ==Superposition==

Unless the renewal process is a Poisson process, the superposition (sum) of two independent renewal processes is not a renewal process. However, such processes can be described within a larger class of processes called the Markov-renewal processes. However, the cumulative distribution function of the first inter-event time in the superposition process is given by :R(t) = 1 - \sum_{k=1}^K \frac{\alpha_k}{\sum_{l=1}^K \alpha_l} (1-R_k(t)) \prod_{j=1,j\neq k}^K \alpha_j \int_t^\infty (1-R_j(u))\,\text{d}u where Rk(t) and αk > 0 are the CDF of the inter-event times and the arrival rate of process k. ==Example application==

Eric the entrepreneur has n machines, each having an operational lifetime uniformly distributed between zero and two years. Eric may let each machine run until it fails with replacement cost €2600; alternatively he may replace a machine at any time while it is still functional at a cost of €200. What is his optimal replacement policy? : ==See also==