The Theory of Renewal Processes
Mathematics for Selling Drugs and Changing Lightbulbs
Introduction
Renewal processes are stochastic processes which model events which occur randomly in time. These events are referred to as renewals or arrivals. In this article, I’ll explain some of the basic theory behind renewal processes, and give a very interesting application of a renewal process.
Renewal Processes are generalizations of Poisson Processes, which I won’t talk about here. To learn more about Poisson Processes, the following article does a pretty good job of explaining it.
The Renewal Process
As a simple metaphor, let’s imagine a single lightbulb maintained by a very diligent janitor. The janitor replaces the lightbulb immediately after it burns out. Denote the lifetime of the i-th lightbulb by tᵢ. Assume that the probability for which the lifetime of the i-th lightbulb is less than t is given by
We also require that the times t₁, t₂, … between each events are independent. Assuming that the first bulb (labeled 1) starts at time 0, then the time at which the n-th bulb burns out is given by
Now denote the number of light bulbs which have been replaced at time t by
Thus, we can define N={N(t): t≥ 0} to be a renewal process.
The Law of Large Numbers
One of the most important results about renewal processes is the following law of large numbers:
Theorem. Suppose the mean interarrival time for each tᵢ is given by
If P(t ᵢ >0)>0, then with probability 1,
Intuitively, what this says is that if a light bulb lasts on average μ years, then in t years, we will use up about t/μ light bulbs.
The Alternating Renewal Process
In reality, a lightbulb wouldn’t immediately replaced, but rather, it would spend a certain amount of time burnt out before being replaced. For this reason, we need to consider a specific kind of renewal process called an alternating renewal process, in which we consider an event to alternate between two states.
As before, suppose Z₁, Z₂,… are independent random variables (the lifetimes of each lightbulb) with distribution F. Now assume that when the i-th lightbulb burns out, the amount of time before it is replaced is Yᵢ , and has distribution G.
Now suppose that the average lifetime of each lightbulb and the average time it takes for each lightbulb to be replaced is given by
Now the important question we need to ask is, on average, what fraction of time does the lightbulb spend working? how much time does it spend being broken before being repaired? Which leads us to the following Theorem about Alternating Renewal Processes:
In an alternating renewal process, the limiting fraction of time in state 1 (the state in which the lightbulb is working) is given by
Example Application: Drug Dealing
Imagine a drug dealer standing on a street corner. Customers arrive at times according to a Poisson Process with rate λ.The customer and the dealer then disappear from the street for an amount of time with distribution G while the transaction is completed. Customers that arrive while a transaction is in process leave and do not return.
- At what rate does the dealer make sales?
We can model this as an alternating renewal process, where Zᵢ is the time spent waiting for customers, having a Poisson distribution, and Yᵢ is the time spent conducting the transaction, having some arbitrary distribution G.
The total time it takes to complete a transaction is the time spent waiting for a customer, plus the time actually spent conducting the transaction. So define this by
Then the rate at which the dealer makes sales is simply the 1/E[Xᵢ]:
Where we use the fact that a Poisson process with rate λ has an expected value of 1/λ.
2. What fraction of customers are lost?
A customer is only lost if they arrive while a transaction is already in process. So, in the long run, this can be thought of as the fraction of time it takes to complete a drug deal. This is the average time spent in the ‘transaction’ state. So by using the results above on alternating renewal process, the fraction of customers lost is given by:
Conclusion
We looked at some of the basics of Renewal Processes, and saw a very simple application of them. To learn more about renewal processes, I posted some good resources below.
