I have come recently to the following real world problem concerning licence renewals of a software product. I have just rudimentary knowledge of the basics in this field and I mostly interested in solving this problem, but I would love to learn something along the way.

The input is vector of renewed licenses $(r_i)_{i=1}^n$ indexed by days and a vector of expiring licenses for each day $(e_i)_{i=1}^{n+k}$. That is $r_i$ is number of licenses renewed on day $i$ and $e_i$ is the number of expiring licenses on day $i$. The renewals depend very much at the weekday. E.g. there are lot of renewals on Mondays and Sundays and not very much on Thursdays.

The problem is to predict or extrapolate the vector of renewals $(r_i)$ for $i=n+1, \ldots, k$.

What I find interesting about this problem is the fact that $r_i$ does not depend only on $e_i$ but also on neighbouring values since people often decide to renew the license before it expires or after it expires. In fact, you know that on average 95% of people renews the license in 60 days centred around the day their license expires and even more - you have a histogram of these renewals $(h_j)_{j=-30}^{30}$. If I understood the data correctly, the value $h_j$ represents the part of renewals that happen on average $j$ days before (or after depending on sign of $j$) the license expires for $j=-30,\ldots, 30$ and the values for $j=-30,30$ cover the renewals that happened more than one month after or before the expiry. In particular $\sum_{j=-31}^{31} h_j = 1$.

Q1: What is the best approach for this type of problem?

After some thought I came up with the following. Let $c_{ij}$ be the proportion of licenses that expire on day $j$ and are renewed on day $i$ to the total number of licenses that expire on day $j$. Then $$r_i = \sum_{j=1}^n c_{ij}e_j$$ or in matrix form $r = Ce$. Moreover we have $$h_j \approx \frac{1}{n} \sum_{i=1}^n \frac{c_{i+j,i}}{t_i},$$ where $t_i = \sum_{j=1}^n c_{ji}$ is the quotient of renewed licenses to all expiring licenses at day $j$. This gives me $n+60$ equations for $n^2$ variables.

Q2: Is hidden Markov model the right approach here? I know nothing about them so if this approach is the right one I would appreciate some links to materials from which I can learn the theory as well as links to implementations.

We can cut down the number of variables by setting $c_{ij} = 0$ for $|i-j| > 30$ but that still leaves us with very underdetermined system. Right now I am about to try out replacing $c_{ij}$ by $h_{i-j}t_j$. This will give me $n$ equations for $n$ unknowns. Which I can hopefully solve and then I will just extrapolate the values $p_i$ for $i=n+1, \ldots, k$ and estimate the renewals by $r_i = \sum_{j=-30}^{30} h_{i-j}t_je_j$.

Update: The solutions oscillate towards $i\to n$.

Disclaimer: Crossposted at math.stackexchange

-
You mention sales at one point. Did you mean 'renewals' there, or is sales another variable in the problem? – Glen_b Nov 21 '12 at 0:03
Sorry. It's a leftover from previous badly worded version of my question. I'll edit it accordingly. – Vít Tuček Nov 21 '12 at 13:42

The way I would approach this would be to start with that histogram, and with an "average" renewal rate. This should be enough to give you the expected number of renewals that would occur on a particular day (by looking at how many would be expected from the 60 days in the histogram window) at an average renewal rate and average seasonality.

Next, I would accommodate daily seasonality, because you seem to indicate renewals are more likely to occur on some days of the week than others.

At the end of this would will have a baseline and can then look for patterns in the actual due to gradual declines/increases in the renewal rate, whether promotions increase the renewal rate overall or just accelerate the timing, and so forth. That will give you an idea of how you need to model promotion effects (and introduction of competitive products).

-

The number of renewals could be predicted from the number of licenses expiring, the history of expired licenses , the future number of expired licenses, the day-of-the-week , the day-of-the month , holiday effects and of course level shifts and trends waiting to be discoverd . Additionally there maybe non-constant error variance which can be remedied by incororating an ARIMA structure reflecting the impact of prior renewals, changes in parameters or determinstic changes in the error process. You could also incorporate promotion effects into the model. In general this is called a Transfer Function and falls under the class of Generalized Least Squares. If you wish you can post your data or actually send it to me at dave@autobox.com and I will post it and perform an analysis which could include some of the structure mentioned herein. Data like this is common in the cable industry.

-