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? Commented Nov 21, 2012 at 0:03
• Sorry. It's a leftover from previous badly worded version of my question. I'll edit it accordingly. Commented Nov 21, 2012 at 13:42